一種基于條件相對平均熵的個性化推薦算法

吳柳，陳萌，石永革

(南昌大學(xué) 信息工程學(xué)院，江西 南昌　330031)

?

一種基于條件相對平均熵的個性化推薦算法

吳柳，陳萌，石永革

(南昌大學(xué) 信息工程學(xué)院，江西 南昌330031)

為了提高現(xiàn)有推薦算法的準(zhǔn)確性，提出一種基于條件相對平均熵的個性化推薦算法.首先，采用加權(quán)的CNM算法構(gòu)建復(fù)雜網(wǎng)絡(luò)，挖掘該網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)，作為商品待推薦域；其次，利用條件互信息和條件相對平均熵生成有效的節(jié)點次序，以提升貝葉斯網(wǎng)絡(luò)構(gòu)建的準(zhǔn)確性；然后采用K2算法學(xué)習(xí)貝葉斯網(wǎng)絡(luò)，分析出用戶的消費性格，并判斷待推薦域中商品與消費性格的聯(lián)系，向用戶提供感興趣和合理的推薦；最后，基于電信運(yùn)營商的實際數(shù)據(jù)進(jìn)行實證分析，驗證了該算法的有效性.

條件相對平均熵；個性化推薦；消費性格；社團(tuán)結(jié)構(gòu)

電子商務(wù)個性化推薦的主要思路是基于各種相關(guān)關(guān)系進(jìn)行推薦，如：商品關(guān)系、用戶關(guān)系、用戶與商品關(guān)系.它們嚴(yán)重依賴歷史行為數(shù)據(jù)，即當(dāng)相關(guān)關(guān)系間的聯(lián)系缺乏時，無法通過相似度計算進(jìn)行預(yù)測，出現(xiàn)數(shù)據(jù)稀疏性問題、冷啟動問題，導(dǎo)致推薦準(zhǔn)確性低，難以滿足用戶的推薦需求.如何從海量的消費數(shù)據(jù)中挖掘出用戶感興趣的資源，并精準(zhǔn)的推薦給用戶，成為個性化推薦研究的熱點.許多學(xué)者對個性化推薦進(jìn)行了深入研究，并提出了一些推薦算法.文獻(xiàn)[1-3]分別針對評分?jǐn)?shù)據(jù)稀疏、冷啟動和瀏覽用戶不提供推薦的問題，提出了一系列商品推薦算法，但相似度計算量大耗時多，不滿足用戶的實時推薦需求和準(zhǔn)確性需求.文獻(xiàn)[4-5]針對用戶興趣描述不準(zhǔn)確的問題，提出了一種基于用戶興趣的、三維建模的個性化推薦算法，但用戶興趣模型的準(zhǔn)確建立，嚴(yán)重依賴用戶搜索行為數(shù)據(jù).文獻(xiàn)[6]通過構(gòu)建用戶之間的多維加權(quán)網(wǎng)絡(luò)，提出此網(wǎng)絡(luò)中的個性化推薦算法，有較高的查全率和準(zhǔn)確率，但算法中的參數(shù)值不易確定，有待研究.文獻(xiàn)[7-8]利用交易數(shù)據(jù)構(gòu)建商品的復(fù)雜網(wǎng)絡(luò)，提出了一種基于復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)的商品推薦方法，很好地解決推薦算法的冷啟動、計算量大以及推薦結(jié)果覆蓋度低的問題，但沒有考慮到用戶的消費性格，無法準(zhǔn)確地推薦符合該消費需求的商品.文獻(xiàn)[9]針對電子商務(wù)面臨消費個性日益凸顯，提出了一種基于消費性格的新商品推薦方法，通過判定新商品與其消費性格符合的程度，向用戶提供感興趣的推薦.

綜上，文獻(xiàn)[1-8]的個性化商品推薦方法側(cè)重于對用戶歷史行為數(shù)據(jù)的淺層次分析，忽視了用戶消費性格在商品推薦中的作用，從而導(dǎo)致推薦結(jié)果與用戶的實際消費需求差異較大，例如，筆者通過對電信企業(yè)內(nèi)部閑置資產(chǎn)交易行為的分析，發(fā)現(xiàn)當(dāng)某用戶的消費記錄偏向經(jīng)濟(jì)實惠，向其推薦的資產(chǎn)卻是多樣性的.為此，本文基于文獻(xiàn)[7]和文獻(xiàn)[9]的研究，引入條件相對平均熵，提出了一種基于條件相對平均熵的個性化推薦算法，主要工作包括：1)根據(jù)用戶歷史交易數(shù)據(jù)，構(gòu)建商品的復(fù)雜網(wǎng)絡(luò)，采用加權(quán)的CNM算法在網(wǎng)絡(luò)中發(fā)現(xiàn)和挖掘其社團(tuán)結(jié)構(gòu)，然后根據(jù)用戶已購商品的所屬社團(tuán)，去獲取相關(guān)用戶的商品待推薦域；2)利用條件互信息和條件相對平均熵生成帶權(quán)有向圖，并構(gòu)建最大權(quán)生成樹，通過拓?fù)渑判蛏捎行У某跏脊?jié)點次序作為K2算法的輸入，然后采用K2算法學(xué)習(xí)貝葉斯網(wǎng)絡(luò)，分析用戶的消費性格；3)使用學(xué)習(xí)好的貝葉斯網(wǎng)絡(luò)進(jìn)行推理，判斷用戶待推薦域的商品與用戶消費性格的聯(lián)系，得到最終的商品推薦域；4)基于實際的企業(yè)資產(chǎn)數(shù)據(jù)進(jìn)行實證分析，驗證本文研究成果的有效性.

1　基于條件相對平均熵的個性化推薦算法

用戶的消費性格是決定其消費行為的核心因素之一，同時用戶的性格特點，也會體現(xiàn)在各自的消費活動中，形成各種各樣的消費行為.按照消費態(tài)度角度的不同，消費性格[10]分為節(jié)儉型、自由型、保守型、怪癖型、順應(yīng)型5種類型.本文根據(jù)用戶的購物記錄，選用貝葉斯網(wǎng)絡(luò)作為工具推斷其消費性格.

1.1數(shù)據(jù)預(yù)處理

用戶選購商品時，將關(guān)注商品屬性，如價格、折扣、質(zhì)量、外觀等.有的屬性對決策變量的影響顯著，需要保留；有的屬性對決策變量的影響不顯著，可以忽略，因此需要對屬性變量降維，排除不重要的商品屬性.本文利用logistics多變量回歸分析

(1)

當(dāng)P≤0.05時，屬性變量對消費性格有很大影響；但P>0.05時，該屬性變量與消費性格無關(guān)，從而從屬性變量X={X1,X2,…,X12}中找到構(gòu)建貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)所需的變量X={X1,X2,…,Xm},m≤12.

貝葉斯網(wǎng)絡(luò)使用的數(shù)據(jù)是離散型的，對用戶的購買行為數(shù)據(jù)的數(shù)值型數(shù)據(jù)進(jìn)行離散化處理，見表1，其中消費性格是決策變量，其余為屬性變量.

1.2算法描述

以下算法過程的基礎(chǔ)：已經(jīng)應(yīng)用加權(quán)CNM算法完成社團(tuán)發(fā)現(xiàn)，獲取了相關(guān)用戶的商品待推薦域.

1)任意2個節(jié)點之間依賴關(guān)系的大小可以通過節(jié)點間的條件互信息[11]表示，在給定離散隨機(jī)變量C的條件下，如果節(jié)點Xi和xj節(jié)點的條件互信息值較大，說明2節(jié)點具有較強(qiáng)的相互依賴關(guān)系.

本文引入條件互信息計算降維后的屬性變量之間依賴關(guān)系，生成表示節(jié)點間依賴關(guān)系的帶權(quán)無向圖，邊的權(quán)值為條件互信息值.據(jù)用戶購買歷史記錄，計算每對屬性變量Xi與Xj之間的條件互信息I(Xi;Xj|Ck)

(2)

其中，i,j=1,2,…,m,i≠j,m≤12,k=1,2,…,5,Xi、Xj和C均為屬性變量，P為概率，xi、xj和ck為樣本中某商品在相應(yīng)屬性變量上的取值，i和j為相應(yīng)的具體屬性編號，k為相應(yīng)的具體消費性格類型.

表1　購物行為數(shù)據(jù)的離散化處理

2)信息熵用于衡量一個隨機(jī)變量Xi取值的不確定程度，定義為

(3)

當(dāng)給定變量Xi，變量Xj的不確定性程度可以用條件熵表示，定義為

(4)

本文引入條件相對平均熵[12]判斷2節(jié)點之間的依賴傾向，確定帶權(quán)無向圖中無向邊的方向，生成表示節(jié)點間依賴關(guān)系的帶權(quán)有向圖，為下一環(huán)節(jié)確定節(jié)點的先后順序做準(zhǔn)備.計算每對屬性變量Xi與Xj之間的條件相對平均熵crae(Xj→Xi)

(5)

其中，|Xi|表示Xi所有可能取值的個數(shù).

如果crae(Xj→Xi)>crae(Xi→Xj)，則邊的方向設(shè)置為從Xj指向xi，即Xj→Xi；反之，則邊的方向設(shè)置為從Xi指向Xj，即Xi→Xj.

3)構(gòu)建最大生成樹，確定K2算法的初始節(jié)點的輸入次序：假定帶權(quán)有向圖G(V,E)，初始最大生成樹為T(V,D)，邊數(shù)D為空；將圖G的邊集合E按權(quán)值降序排列；從權(quán)值最大的邊開始遍歷每條邊，直至邊集合連通了所有節(jié)點集合V，得到最大生成樹；利用拓?fù)渑判驅(qū)ι蓸渲泄?jié)點進(jìn)行排序，確定初始節(jié)點次序.

4)構(gòu)建貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)：初始一個空網(wǎng)絡(luò)，根據(jù)3)中確定的K2算法的節(jié)點順序，采用CH評分函數(shù)和后驗概率作為網(wǎng)絡(luò)結(jié)構(gòu)的評分函數(shù)，如公式(6)、(7)，依次為每一個節(jié)點添加合適的父節(jié)點，其中，父節(jié)點只能從該節(jié)點順序之前的節(jié)點集合中選出.根據(jù)式(6)確定節(jié)點間的依賴關(guān)系，當(dāng)式(7)所得概率值最高時，在2節(jié)點之間增加1條有向邊.當(dāng)所有的有向邊都確定時，就得到一個貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)圖.

(6)

(7)

其中，D是實例數(shù)據(jù)，Bs是網(wǎng)絡(luò)結(jié)構(gòu).yl為Y中各變量的取值，v(yl)為yl父節(jié)點的取值，即概率大小；h為該節(jié)點的父節(jié)點的數(shù)量；Γ()為Γ函數(shù)；?lhg為yl的第g態(tài)度，?lh=∑?lhg；Nlhg為v(yi)的第g態(tài)度，Nlh=∑Nlhg.

5)根據(jù)前述評分公式(7)，獲取分值最高的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)，以及對應(yīng)的節(jié)點概率分布表.學(xué)習(xí)決策屬性C的概率分布為P(Ck)，該概率分布表示用戶的消費性格情況，概率值大的消費性格類別即為該用戶的主導(dǎo)消費性格，將對應(yīng)的概率值作為商品推薦閾值ε.

6)離散化處理用戶待推薦域中的商品數(shù)據(jù)，并作為貝葉斯網(wǎng)絡(luò)的屬性輸入，得到待推薦域商品的消費性格分布，與設(shè)定的閾值進(jìn)行比較.若得到的消費性格類型大于設(shè)定的閾值，則說明此商品符合用戶的消費性格，將其推薦給用戶；否則不予推薦，從而得到最終的商品推薦域.

2　實證分析

實證數(shù)據(jù)來源于某省電信公司，從2014年11月至4月份的閑置資產(chǎn)交易成功記錄中隨機(jī)抽取1萬條數(shù)據(jù)，格式見表2.表2中，資產(chǎn)類、項、目、節(jié)屬性依次細(xì)化地描述閑置資產(chǎn)的分類情況，資產(chǎn)ID確定閑置資產(chǎn)的唯一性，盤活時間表示閑置資產(chǎn)成功交易的時間.

表2　閑置資產(chǎn)交易成功記錄

1)統(tǒng)計所有用戶成功交易的歷史數(shù)據(jù)，根據(jù)文獻(xiàn)[7]基于社團(tuán)發(fā)現(xiàn)算法將其進(jìn)行社團(tuán)結(jié)構(gòu)劃分，可以看到每一個資產(chǎn)都?xì)w入某一個子社團(tuán)中，圖1為社團(tuán)網(wǎng)絡(luò)的部分圖形.

賬號為xsl122785的用戶購買編號為1、4、8的資產(chǎn)，位于2個社團(tuán)，合并這2個社團(tuán)，發(fā)現(xiàn)資產(chǎn)1、4、8的共同鄰接點集為{3，5}，且邊權(quán)重w1,3+w4,3+w8,3>w1,5+w4,5+w8,5，因而當(dāng)前用戶的商品待推薦域集合為{3,5}.

2)選取賬號為xsl122785的用戶的交易數(shù)據(jù)，利用SPSS進(jìn)行l(wèi)ogistics多變量回歸分析，提取出對當(dāng)前用戶的消費性格有顯著影響的屬性變量，有：價格、折扣、質(zhì)量、銷量、新品、屬地.

3)根據(jù)表1對xsl122785用戶的交易數(shù)據(jù)進(jìn)行離散化處理，計算降維后的屬性變量間的條件互信息和條件相對平均熵，建立最大權(quán)生成樹，如圖2，利用拓?fù)渑判虻玫截惾~斯網(wǎng)絡(luò)K2算法的初始節(jié)點次序begin={消費性格，價格，屬地，銷量，折扣，新品，質(zhì)量}.

4)通過初始節(jié)點次序begin構(gòu)建評分值最高的貝葉斯網(wǎng)絡(luò)，如圖3，可以看到與消費性格直接相關(guān)的商品屬性是價格、折扣和銷量，其他間接關(guān)聯(lián).然后對該網(wǎng)絡(luò)進(jìn)行分析和學(xué)習(xí)，獲取用戶的消費性格概率分布，見表3.表中節(jié)儉型的概率值為0.498，所占的比例近50%，因而該用戶的消費性格表現(xiàn)出節(jié)儉型的特點，同時將ε=0.498作為商品推薦的閾值.

圖1　復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)Fig.1　Community structure in complex networks

圖2　最大權(quán)生成樹Fig.2　Maximum spanning tree

圖3　xsl122785的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)Fig.3　Bayesian Network of xsl122785

消費性格概率分布節(jié)儉型0.498自由型0.130保守型0.225順應(yīng)型0.103怪癖型0.044

5)在貝葉斯網(wǎng)絡(luò)中輸入1)中該用戶商品待推薦域中各商品屬性，獲取對應(yīng)的消費性格分布，見表4，得到該用戶的商品最終推薦域.

表4　推薦結(jié)果

圖4　本文算法與社團(tuán)發(fā)現(xiàn)算法準(zhǔn)確率比較Fig.4　Comparison of accuracy of this article and Community Detection

6)提取2015年5月至8月的閑置資產(chǎn)交易成功記錄，驗證該算法的合理性和有效性，如圖4.從圖4中可以看到，隨著時間的變化，用戶消費記錄的增加，引入消費性格的基于條件相對平均熵的推薦算法和社團(tuán)發(fā)現(xiàn)算法的推薦準(zhǔn)確率均有所提高，但前者準(zhǔn)確率增加的幅度明顯高于后者，準(zhǔn)確率也更高.

3　結(jié)束語

為了提高個性化推薦的準(zhǔn)確性，本文綜合考慮了用戶的消費性格和商品的社團(tuán)結(jié)構(gòu)，提出了一種基于條件相對平均熵和消費性格分析的貝葉斯網(wǎng)絡(luò)個性推薦算法，以歷史交易數(shù)據(jù)為依據(jù)，借助貝葉斯網(wǎng)絡(luò)分析消費性格，并以消費性格為紐帶，確定社團(tuán)發(fā)現(xiàn)后的推薦域，實現(xiàn)對用戶的推薦，并基于實際數(shù)據(jù)驗證了本文研究成果的有效性.

[1]鄧愛林，朱揚(yáng)勇，施伯樂.基于項目評分預(yù)測的協(xié)同過濾推薦算法[J].軟件學(xué)報，2003,14(9)：16-21.

DENG A L,ZHU Y Y,SHI B L.A collaborative filtering recommendation algorithm based on item rating prediction[J].Software Journal,2003,14(9)：16-21.

[2]郭艷紅，鄧貴仕.協(xié)同過濾系統(tǒng)項目冷啟動的混合推薦算法[J].計算機(jī)工程，2008,34(23):11-13.

GUO Y H,DENG G S.Hybrid recommendation algorithm of item cold-start in collaborative filtering system[J].Computer Engineering,2008.34(23):11-13.

[3]謝意，陳德仁，干紅華.基于瀏覽偏好挖掘的實時商品推薦方法[J].計算機(jī)應(yīng)用，2011,31(1):89-92. DOI:10.3724/SP.J.1087.2011.00089.

XIE Y,CHEN D R,GAN H H.Real-time recommendation method based on browsing preferences mining[J].Journal of Computer Application,2011,31(1):89-92.DOI:10.3724/SP.J.1087.2011.00089.

[4]王冰怡，劉楊，聶長新，等.基于用戶興趣三維建模的個性化推薦算法[J].計算機(jī)工程，2015,41(1):65-70.DOI:10.3969/j.issn.1000-3428.2015.01.012.

WANG B Y,LIU Y,NIE C X,et al.Personalized recommendation algorithm based on three-dimensional user interest modeling[J].Computer Engineering,2015,41(1):65-70.DOI:10.3969/j.issn.1000-3428.2015.01.012.

[5]LI J,ZHANG P.Mining explainable user interest from scalable user behavior data[J].Procedia Computer Science,2013,17:789-796.DOI:10.1016/j.procs.2013.05.101.

[6]張華青，王紅，滕兆明，等.多維加權(quán)社會網(wǎng)絡(luò)中的個性化推薦算法[J].計算機(jī)應(yīng)用，2011.31(9):2408-2411.DOI:10.3724/SP.J.1087.2011.02408.

ZHANG H Q,WANG H,TENG Z M,et al.Personalized recommendation algorithm in multidimensional and weighted social network[J].Journal of Computer Application,2011,31(9):2408-2411.DOI:10.3724/SP.J.1087.2011.02408.

[7]盧丹，王君博，武森.電子商務(wù)中基于復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)的商品推薦研究[J].工業(yè)技術(shù)創(chuàng)新，2015,2(1):61-65.DOI:10.14103/j.issn.2095-8412.2015.01.013.LU D,WANG J B,WU S.Research on commodity recommendation in E-commerce based on community detection in complex networks[J].Industrial Technology Innovation,2015,2(1):61-65.DOI:10.14103/j.issn.2095-8412.2015.01.013.

XIE Z,WANG X F.An overview of algorithms for analyzing community structure in complex networks[J].Complex Systems and Complexity Science,2005,2(3):1-12.

[9]張光前，白雪.基于消費性格的新商品推薦方法[J].管理科學(xué)，2015,28(2):60-68.DOI:10.3969 /j.issn.1672-0334.2015.02.006.ZHANG G Q,BAI X.Method of new commodities recommendation based on consuming personalities[J].Journal of Management Science,2015,28(2):60-68.DOI:10.3969 /j.issn.1672-0334.2015.02.006.

[10]劉魯蓉，孫順根．消費心理學(xué)[M]．北京:科學(xué)出版社，2007:5-9.

[11]SOTOCA J M, PLA F.Supervised feature selection by clustering using conditional mutual information-based distances[J].Pattern Recognition ,2010(43):2068-2081.DOI:10.1016/j.patcog.2009.12.013.

[12]JIANG J,WANG J Y,YU H,et al.Poison identification based on Bayesian network:a novel improvement on K2 algorithm via Markov blanket[J].Advances in Swarm Intelligence,2013,7929:173-182.DOI:10.1007/978-3-642-38715-9_21.

(責(zé)任編輯：孟素蘭)

A personalized recommendation algorithm based on conditional relative average entropy

WU Liu,CHEN Meng,SHI Yongge

(Information and Engineering School,Nanchang University,Nanchang 330031,China)

In order to improve the accuracy of recommendation algorithm,one personalized recommendation algorithm based on conditional relative average entropy is presented.First of all,through weighted CNM algorithm we construct complex network and excavate the network’s community structure. The result is regarded as the uncertain recommendation domain. Further more ,conditional mutual information and conditional relative average entropy are used to determine the effective node ordering as input of K2 algorithm,which can improve the accuracy of Bayesian network construction,and then learn Bayesian network by K2 algorithm and analyze the consumer characteristics. We use the relationship between the commodity and the consumer characteristics to confirm the recommendation domain.Finally,the empirical analysis of the actual data of the telecom operators is carried out to verify the validity of the above algorithm.

conditional relative average entropy;personality recommendation;consumer characteristics;community structure

10.3969/j.issn.1000-1565.2016.04.017

2015-11-17

國家自然科學(xué)基金資助項目(61163005)

吳柳(1991—)，女，江西萍鄉(xiāng)人，南昌大學(xué)在讀碩士研究生，主要從事數(shù)據(jù)挖掘、算法分析研究工作.

E-mail：1203414419@qq.com

陳萌(1977—)，男，江西南昌人，南昌大學(xué)副教授，主要從事計算機(jī)網(wǎng)絡(luò)、數(shù)據(jù)挖掘方向研究.

E-mail：chengmeng@ncu.edu.cn

TP391

A

1000-1565(2016)04-0438-06