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

吳柳，陳萌，石永革

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

?

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

吳柳，陳萌，石永革

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

為了提高現有推薦算法的準確性，提出一種基于條件相對平均熵的個性化推薦算法.首先，采用加權的CNM算法構建復雜網絡，挖掘該網絡的社團結構，作為商品待推薦域；其次，利用條件互信息和條件相對平均熵生成有效的節點次序，以提升貝葉斯網絡構建的準確性；然后采用K2算法學習貝葉斯網絡，分析出用戶的消費性格，并判斷待推薦域中商品與消費性格的聯系，向用戶提供感興趣和合理的推薦；最后，基于電信運營商的實際數據進行實證分析，驗證了該算法的有效性.

條件相對平均熵；個性化推薦；消費性格；社團結構

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

綜上，文獻[1-8]的個性化商品推薦方法側重于對用戶歷史行為數據的淺層次分析，忽視了用戶消費性格在商品推薦中的作用，從而導致推薦結果與用戶的實際消費需求差異較大，例如，筆者通過對電信企業內部閑置資產交易行為的分析，發現當某用戶的消費記錄偏向經濟實惠，向其推薦的資產卻是多樣性的.為此，本文基于文獻[7]和文獻[9]的研究，引入條件相對平均熵，提出了一種基于條件相對平均熵的個性化推薦算法，主要工作包括：1)根據用戶歷史交易數據，構建商品的復雜網絡，采用加權的CNM算法在網絡中發現和挖掘其社團結構，然后根據用戶已購商品的所屬社團，去獲取相關用戶的商品待推薦域；2)利用條件互信息和條件相對平均熵生成帶權有向圖，并構建最大權生成樹，通過拓撲排序生成有效的初始節點次序作為K2算法的輸入，然后采用K2算法學習貝葉斯網絡，分析用戶的消費性格；3)使用學習好的貝葉斯網絡進行推理，判斷用戶待推薦域的商品與用戶消費性格的聯系，得到最終的商品推薦域；4)基于實際的企業資產數據進行實證分析，驗證本文研究成果的有效性.

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

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

1.1數據預處理

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

(1)

當P≤0.05時，屬性變量對消費性格有很大影響；但P>0.05時，該屬性變量與消費性格無關，從而從屬性變量X={X1,X2,…,X12}中找到構建貝葉斯網絡結構所需的變量X={X1,X2,…,Xm},m≤12.

貝葉斯網絡使用的數據是離散型的，對用戶的購買行為數據的數值型數據進行離散化處理，見表1，其中消費性格是決策變量，其余為屬性變量.

1.2算法描述

以下算法過程的基礎：已經應用加權CNM算法完成社團發現，獲取了相關用戶的商品待推薦域.

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

本文引入條件互信息計算降維后的屬性變量之間依賴關系，生成表示節點間依賴關系的帶權無向圖，邊的權值為條件互信息值.據用戶購買歷史記錄，計算每對屬性變量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為樣本中某商品在相應屬性變量上的取值，i和j為相應的具體屬性編號，k為相應的具體消費性格類型.

表1　購物行為數據的離散化處理

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

(3)

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

(4)

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

(5)

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

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

3)構建最大生成樹，確定K2算法的初始節點的輸入次序：假定帶權有向圖G(V,E)，初始最大生成樹為T(V,D)，邊數D為空；將圖G的邊集合E按權值降序排列；從權值最大的邊開始遍歷每條邊，直至邊集合連通了所有節點集合V，得到最大生成樹；利用拓撲排序對生成樹中節點進行排序，確定初始節點次序.

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

(6)

(7)

其中，D是實例數據，Bs是網絡結構.yl為Y中各變量的取值，v(yl)為yl父節點的取值，即概率大小；h為該節點的父節點的數量；Γ()為Γ函數；?lhg為yl的第g態度，?lh=∑?lhg；Nlhg為v(yi)的第g態度，Nlh=∑Nlhg.

5)根據前述評分公式(7)，獲取分值最高的貝葉斯網絡結構，以及對應的節點概率分布表.學習決策屬性C的概率分布為P(Ck)，該概率分布表示用戶的消費性格情況，概率值大的消費性格類別即為該用戶的主導消費性格，將對應的概率值作為商品推薦閾值ε.

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

2　實證分析

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

表2　閑置資產交易成功記錄

1)統計所有用戶成功交易的歷史數據，根據文獻[7]基于社團發現算法將其進行社團結構劃分，可以看到每一個資產都歸入某一個子社團中，圖1為社團網絡的部分圖形.

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

2)選取賬號為xsl122785的用戶的交易數據，利用SPSS進行logistics多變量回歸分析，提取出對當前用戶的消費性格有顯著影響的屬性變量，有：價格、折扣、質量、銷量、新品、屬地.

3)根據表1對xsl122785用戶的交易數據進行離散化處理，計算降維后的屬性變量間的條件互信息和條件相對平均熵，建立最大權生成樹，如圖2，利用拓撲排序得到貝葉斯網絡K2算法的初始節點次序begin={消費性格，價格，屬地，銷量，折扣，新品，質量}.

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

圖1　復雜網絡的社團結構Fig.1　Community structure in complex networks

圖2　最大權生成樹Fig.2　Maximum spanning tree

圖3　xsl122785的貝葉斯網絡結構Fig.3　Bayesian Network of xsl122785

消費性格概率分布節儉型0.498自由型0.130保守型0.225順應型0.103怪癖型0.044

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

表4　推薦結果

圖4　本文算法與社團發現算法準確率比較Fig.4　Comparison of accuracy of this article and Community Detection

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

3　結束語

為了提高個性化推薦的準確性，本文綜合考慮了用戶的消費性格和商品的社團結構，提出了一種基于條件相對平均熵和消費性格分析的貝葉斯網絡個性推薦算法，以歷史交易數據為依據，借助貝葉斯網絡分析消費性格，并以消費性格為紐帶，確定社團發現后的推薦域，實現對用戶的推薦，并基于實際數據驗證了本文研究成果的有效性.

[1]鄧愛林，朱揚勇，施伯樂.基于項目評分預測的協同過濾推薦算法[J].軟件學報，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]郭艷紅，鄧貴仕.協同過濾系統項目冷啟動的混合推薦算法[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].計算機應用，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].計算機工程，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]張華青，王紅，滕兆明，等.多維加權社會網絡中的個性化推薦算法[J].計算機應用，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]盧丹，王君博，武森.電子商務中基于復雜網絡社團發現的商品推薦研究[J].工業技術創新，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].管理科學，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]劉魯蓉，孫順根．消費心理學[M]．北京:科學出版社，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.

(責任編輯：孟素蘭)

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

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

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

E-mail：1203414419@qq.com

陳萌(1977—)，男，江西南昌人，南昌大學副教授，主要從事計算機網絡、數據挖掘方向研究.

E-mail：chengmeng@ncu.edu.cn

TP391

A

1000-1565(2016)04-0438-06