基于屬性值差異度的推薦多樣性改進算法

張 駿 丁艷輝 金連旭

(1.山東師范大學信息科學與工程學院 濟南 250014)(2.山東省物流優化與預測工程技術研究中心 濟南 250014)

基于屬性值差異度的推薦多樣性改進算法

張 駿1,2丁艷輝1,2金連旭1,2

(1.山東師范大學信息科學與工程學院 濟南 250014)(2.山東省物流優化與預測工程技術研究中心 濟南 250014)

推薦多樣性日益成為評價推薦系統性能的重要指標。現有的提高推薦多樣性方法缺少對項目屬性值差異度問題的考慮。論文提出一種基于屬性值差異度的推薦多樣性改進算法。首先,針對屬性值差異度以及項目差異度進行度量;其次,基于項目差異度進行項目聚類;最后,結合聚類信息對現有的推薦算法生成的初始Top-N推薦列表進行優化。實驗結果表明論文所提出的算法在保證推薦結果準確率的同時能有效提高推薦的多樣性。

推薦系統; 差異度; 多樣性; Top-N推薦; 聚類

Class Number TP391

1 引言

個性化推薦通過分析用戶的歷史信息來幫助用戶過濾出其感興趣的信息而無需用戶提供明確的需求[1～2]。經過十幾年的發展,個性化推薦已經成為了最受歡迎的信息過濾技術,并廣泛應用于電子商務、新聞、電影、社交網絡等領域[3～4]。過去的十幾年,對個性化推薦的研究主要集中在如何提高算法的準確率。然而,一味地追求推薦準確率可能會傷害推薦系統。SM Mcnee等[5]指出僅僅強調準確率會造成用戶的視野被限定在一個相對狹窄的范圍內,從而忽略了用戶可能感興趣的信息。Hu R等[6]實驗證明推薦多樣性對于提高用戶滿意度具有積極而重要的作用。

近年來,推薦多樣性問題已經成為推薦領域關注的熱點問題之一。張富國等[7]提出一種基于社會網絡信任的推薦多樣性算法,通過選擇多樣性好的信任鄰居從而提高推薦結果的多樣性。李滿天等[8]提出多樣性和效用值兩個定義用于度量推薦列表多樣性和準確率,并將其建模為一個整數規劃問題進行求解。Ziegler等[9]基于用戶對特定主題的興趣提出主題多樣性推薦算法,對User-based CF推薦算法、Item-based CF推薦算法生成的推薦列表進行優化,獲得多樣性好的一組項目作為最終的推薦列表。T Aytekin等[10]提出一種基于聚類的Top-N推薦多樣性提高算法,根據項目評分進行聚類,通過聚類權重再分配從各類集中篩選項目生成最終推薦列表。現有的方法從不同角度對推薦多樣性進行了研究,然而缺少對項目屬性值差異度問題的考慮。針對以上問題,本文提出一種基于屬性值差異度的推薦多樣性改進算法(DivImproved)。首先,針對屬性值差異度以及項目差異度進行度量。其次,基于項目差異度進行項目聚類。最后,在現有的推薦算法生成的初始推薦列表的基礎上結合項目聚類信息,從中獲取一組多樣性好的項目作為最終推薦列表。實驗結果表明,本文所提算法在保證推薦結果準確率的同時能有效提高推薦的多樣性。

2 基于屬性值差異度的推薦多樣性改進算法

2.1 相關概念

項目通常具有多種屬性且每種屬性具有多種屬性值。設項目數據集DS=(U,A,V),項目集合U={U1,U2,…,Uk},k為項目個數。屬性集合A={A1,A2,…,Am},m為屬性個數。屬性值集合為V={V1,1,V1,2,…,V1,p1,…,Vi,1,Vi,2,…,Vi,pi,Vi+1,1,…},Vi,pi表示屬性Ai的一個屬性值,pi表示屬性Ai不同屬性值個數。

定義1(屬性值差異度) 屬性值差異度即屬性值間的不相似程度。同一屬性下的屬性值間的差異并不是非0即1的關系,定義Ai屬性下Vi,α與Vi,β兩個不同屬性值之間的差異度為σ(Vi,α,Vi,β)。

定義2(項目差異度) 項目差異度即項目間的不相似程度。項目差異度通過項目間屬性值差異度進行度量,定義項目差異度為Diversity(U1,U2)。

定義3(共現關系) 在某一項目中,Ai屬性的屬性值為Vi,α,Aj屬性的屬性值為Vj,β,稱Vi,α與Vj,β為共現關系,記為(Vi,α,Vj,β)。

定義5(共現行向量) 假設某個項目Ai屬性的屬性值為Vi,α,在項目集合U中,其與非Ai屬性的其他所有屬性值共現次數構造行向量稱為共現行向量,記為

2.2 算法描述

本文提出DivImproved算法,對User-based CF算法[11]、Item-based CF算法[12]等現有推薦算法生成的推薦列表進行多樣性改進。算法思想為將系統中全部項目聚類成不同的類,現有的推薦算法生成的初始推薦列表中的項目屬于不同的類,基于項目的類信息從初始推薦列表中獲取一組多樣性好且預測評分高的項目構建最終的推薦列表。本算法具有以下優勢:首先,算法考慮了屬性值之間的差異,基于屬性值差異的項目差異度度量更加準確；其次,本算法僅需一次項目聚類,無需對每位用戶的初始推薦列表中項目進行聚類,具有算法復雜度低的特點。

本算法主要包含以下三個步驟：

Step1:差異度度量。基于屬性值差異度得到項目差異度,用于項目聚類中項目間距離表示及多樣性度量。

Step2:項目聚類。基于項目差異度采用k-means聚類[13]思想對項目進行聚類,是推薦列表優化的前提工作。

Step3:推薦列表優化。基于現有的推薦算法生成的初始推薦列表,優化得到一組多樣性好的項目組合。

2.3 差異度度量

在推薦多樣性研究中,通常缺少對同一屬性下的不同屬性值之間的差異度的考慮。以電影類型屬性為例,“恐怖電影”與“災難電影”的差異程度要低于“恐怖電影”與“喜劇電影”的差異程度。以職位信息中的公司規模屬性為例,“大規模公司”與“中等規模公司”的差異程度要低于“大規模公司”與“小規模公司”。通過相關領域的專家可以對同一屬性下的不同屬性值之間的差異度給出度量標準,然而該方法工作量大,缺乏一定的科學依據,且不可復制到其他應用領域。本文提出一種基于向量距離的差異度度量方法,有效解決上述問題。

在某一項目中,屬性Ai的屬性值Vi,α與其他屬性的屬性值之間存在緊密的聯系。以職位信息為例,薪資屬性中“高薪資”屬性值通常對應著企業性質中“外資企業”、“國有企業”屬性值,公司規模屬性中“大規模公司”。某一屬性值的含義可由其與其他屬性的不同屬性值在項目中共同出現的次數進行描述。統計項目集合U中屬性Ai的屬性值Vi,α與非Ai屬性的全部屬性值共同出現在某一項目中的次數并構建行向量,對屬性值Vi,α進行描述,并在余弦相似度基礎上對Ai屬性下Vi,α與Vi,β兩個不同屬性值之間的差異度σ(Vi,α,Vi,β)進行度量。

本文使用如下屬性值差異度度量方法:

(1)

屬性值差異度σ(Vi,α,Vi,β)的計算依賴于屬性值的相似度計算,本文采用了余弦相似度進行相似度計算。由于行向量的每一項均為非負值,因此式(1)中,σ(Vi,α,Vi,β)∈[0,1]。Vi,α與Vi,β差異越大,σ(Vi,α,Vi,β)值越大。

項目差異度即對項目間不相似程度。通過項目間差異度度量,從而實現項目基于差異度聚類。項目差異度取決于項目間對應屬性值間的差異度,項目間對應屬性差異度越大,則項目差異度越大。

本文使用如下項目差異度度量方法:

(2)

其中,σ(Vi,α,Vi,β)為項目U1與U2在{A1,A2,A3,…,Am}屬性中相應的屬性值Vi,α,Vi,β間的差異度,由于σ(Vi,α,Vi,β)∈[0,1],因此Diversity(U1,U2)∈[0,m]。項目U1與U2之間差異越大,Diversity(U1,U2)值越大。

2.4 項目聚類

結合項目差異度度量算法獲得|U|*|U|維度的項目差異度列表Diversity-list,采用k-means聚類思想對項目進行聚類處理。

項目聚類過程如下：

輸入：項目集U,項目差異度列表Diversity-list,聚類個數N(聚類個數等于推薦列表長度)。

輸出：N個聚類(N-cluster)。

Step1：從數據集中隨機選取N個項目作為初始的聚類中心。

Step2：根據Diversity-list列表查找每個項目到類中心距離,將其分配到距離最近的類中去。

Step3：所有項目分配完成后,選取距離所在類中各項目距離和最小的項目作為新的類中心。

Step4：重復Step2,Step3過程,直到各類中心不再變化為止。

2.5 推薦列表優化

推薦列表優化是指初始推薦列表的基礎上結合項目聚類信息對推薦列表進行優化,從中獲取一組多樣性好的項目組合推薦給用戶。

推薦列表優化過程如下：

輸入：數據集U,項目聚類結果N-cluster,推薦列表長度N。

輸出：Top-N推薦列表。

Step1：使用現有的推薦算法生成初始推薦列表以及推薦列表中項目的預測評分。一般而言,初始推薦列表長度為最終推薦項目列表長度的數倍。

Step2：根據項目聚類結果N-cluster記錄初始推薦列表中項目所在的類,統計初始推薦列表中項目共屬于k個類。

Step3：假設k=N,從每個類中選出預測評分最高的項目,構建Top-N推薦列表,推薦結束。

Step4：假設k

2.6 算法復雜度分析

假設項目個數m,屬性個數n,屬性值個數i,聚類迭代次數t,聚類簇數k,推薦優化迭代次數r,初始推薦列表長度為w。本文算法主要涉及屬性值差異度與項目差異度計算,項目聚類以及推薦列表優化。屬性值差異度算法的時間復雜度為O(n*i2)。項目差異度算法的時間復雜度為O(n3)。聚類算法的時間復雜度為O(mtk)。推薦列表優化算法的時間復雜度為O(wr)。通常情況下,n

3 實驗

MovieLens數據集是推薦系統領域廣泛使用的數據集,本文采用Movielens1M數據集(http://www.grouplens.org/)作為測試數據,該數據集為6040用戶對3900部電影的1000000條5分制評分數據集。實驗使用電影類型與電影年份作為屬性進行電影差異度度量,將數據集按照60:40的比例劃分為訓練集和測試集。實驗中初始推薦列表長度為最終推薦列表長度的3倍。采用結合item-based CF生成的初始推薦列表的Item-DivImproved本文算法與傳統item-based CF算法以及文獻[8]使用的DivEnhance多樣性增強算法進行準確率與多樣性比較。由于文獻[8]設置了參數β,用于調整不同等級的多樣性與準確率。當β=0.8時,多樣性與準確率都保持在一個較好的水平,因此本文實驗默認β取值為0.8。

3.1 評價指標

本文對算法的多樣性與準確率進行實驗對比,分別采用列表內差異度(Intra-list Dissimilar,ILD)、平均絕對偏差(MAE)對算法的性能進行評價。其中,ILD是在Ziegler等[9]提出的列表內相似度(Intra-list Similar,ILS)基礎上進行的改進。

(3)

式中R代表Top-N推薦列表,i和j代表兩個不同的推薦項目,n表示推薦列表的長度,Diversity(i,j)為推薦列表中項目與j的差異度。ILD值越大,推薦結果的多樣性越好。

(4)

其中pi表示預測用戶對項目i的評分值,qi為實際用戶對項目i的評分值,n為推薦列表長度。MAE值越小,推薦準確率越高。

3.2 實驗結果與分析

實驗對比發現,本文提出的DivImproved算法較傳統算法能大幅提高推薦多樣性。多樣性提高達到30%～60%。由于項目聚類操作,被推薦的項目間差異度保持在一個較高的水平。伴隨著推薦列表Top-N的增加,傳統Item-based的多樣性基本保持穩定,本文算法多樣性呈現降低趨勢,這是由于推薦項目數量的增多,造成位于相同類中的項目同時出現在推薦列表中概率增加造成的。與文獻[8]提出的DivEnhance算法對比,DivImproved算法同樣更加優秀。在推薦列表數目小的情況下,效果更為明顯。

圖1 不同算法在多樣性方面對比

圖2 不同算法在準確度方面對比

從圖2可以看出,本文提出的DivImproved算法的平均絕對偏差要高于優化前的算法,MAE大約增加0.03,準確率仍然保持在一個可接受的范圍。本文算法與DivEnhance算法相比,準確率基本保持持平。結合算法的推薦多樣性對比,本文提出的DivImproved算法在稍微降低推薦準確率的情況下較大幅提高推薦多樣性。

4 結語

多樣性作為評判推薦效果的一個重要指標,越來越受到人們的重視。傳統的多樣性算法往往忽略了屬性值差異度。本文提出基于屬性值差異度的推薦多樣性改進算法,考慮了項目不同屬性值之間的差異。實驗表明,在保證推薦結果準確率的同時能有效提高推薦的多樣性。本文算法也存在不足,沒有給出不同屬性權重度量標準,這將是下一步的研究方向。此外,該算法僅限于提高推薦的個體多樣性,并沒有涉及到推薦的總體多樣性。

[1] Hill W, Stead L, Rosenstein M, et al. Recommending and evaluating choices in a virtual community of use[C]//Human Factors in Computing Systems, CHI ’95 Conference Proceedings, Denver, Colorado, Usa,1995:194-201.

[2] Resnick P, Varian H R. Recommender systems[J]. Communications of the Acm,1997,40(3):56-58.

[3] Kim J E, Kim H G. Music recommendation method with respect to message service: US, US8410347[P]. 2013.

[4] 王晟,王子琪,張銘.個性化微博推薦算法[J].計算機科學與探索,2012,6(10):895-902. WANG Sheng, WANG Ziqi, ZHANG Ming. Personalized Recommendation Algorithm on Microblogs[J]. Journal of Frontiers of Computer Science and Technology,2012,6(10):895-902.

[5] Mcnee S M, Riedl J, Konstan J A. Being accurate is not enough: how accuracy metrics have hurt recommender systems[C]//CHI’06 Extended Abstracts on Human Factors in Computing Systems. ACM,2006:1097-1101.

[6] Hu R, Pu P. Helping users perceive recommendation diversity[C]//Workshop on novelty and diversity in recommender systems, DiveRS. Chicago,2011.

[7] 張富國,徐升華.基于信任的電子商務推薦多樣性研究[J].情報學報,2010,29(2):350-355.

ZHANG Fuguo, XU Shenghua. Research on Recommendation in Trust Based E-commerce Recommender Systems[J]. Journal of The China Society for Scientific and Technical Information,2010,29(2):350-355.

[8] 李滿天,王勁林,鄧浩江.一種多樣性增強的推薦列表選擇算法[J].計算機應用研究,2013,30(9):2591-2593. LI Mantian, WANG Jinlin, DENG Haojiang. Recommendation list selection algorithm with diversity enhancement[J]. Application Research of Computers,2013,30(9):2591-2593.

[9] Ziegler C N, McNee S M, Konstan J A, et al. Improving recommendation lists through topic diversification[C]//Proceedings of the 14th international conference on World Wide Web. ACM,2005:22-32.

[10] Aytekin T, Karakaya M. Clustering-based diversity improvement in top- N, recommendation[J]. Journal of Intelligent Information Systems,2014,42(1):1-18.

[11] 李濤,王建東,葉飛躍,等.一種基于用戶聚類的協同過濾推薦算法[J].系統工程與電子技術,2007,29(7):1178-1182. LI Tao, WANG Jiandong, YE Feiyue, et al. Collaborative filtering recommendation algorithm based on clustering basal users[J]. Systems Engineering and Electronics,2007,29(7):1178-1182.

[12] 鄧愛林,朱揚勇,施伯樂.基于項目評分預測的協同過濾推薦算法[J].軟件學報,2003,14(9):1621-1628. DENG Ailin, ZHU Yangyong, SHI Baile. A Collaborative Filtering Recommendation Algorithm Based on Item Rating Prediction[J]. Journal of Software,2003,14(9):1621-1628.

[13] Hartigan J A, Wong M A. A K-means clustering algorithm[J]. Applied Statistics,2013,28(1):100-108.

An Improved Algorithm for Recommendation Diversity Based on the Dissimilarity of Attribute Value

ZHANG Jun1,2DING Yanhui1,2JIN Lianxu1,2

(1. School of Information Science and Engineering, Shandong Normal University, Jinan 250014) (2. Shandong Provincial Logistics Optimization and Predictive Engineering Technology Research Center, Jinan 250014)

Recommendation diversity is increasingly becoming an important indicator to evaluate the performance of the recommendation system. There is little consideration of the dissimilarity of the item attribute value for the existing methods of improving the recommendation diversity. In this paper, an improved algorithm for recommendation diversity based on the dissimilarity of attribute value is proposed. Firstly, the dissimilarity of attribute value and item is measured. Secondly, items are clustered according to the item dissimilarity. Finally, combined with clustering information, the initial Top-N recommendation list generated by the existing recommendation algorithm is optimized. Experimental results show that the proposed algorithm can effectively improve the recommendation diversity while maintaining an acceptable level of recommendation accuracy.

recommendation system, dissimilarity, diversity, Top-N recommendation, clustering

2016年8月10日,

2016年9月28日

國家自然科學基金青年項目(編號:61303007);山東省優秀中青年科學家科研獎勵基金(編號:BS2013DX044)資助。

張駿,男,碩士研究生,研究方向:推薦系統、數據挖掘。丁艷輝,男,教授,研究方向:web數據集成、推薦系統。金連旭,男,碩士研究生,研究方向:推薦系統、數據挖掘。

TP391

10.3969/j.issn.1672-9722.2017.02.003