一種基于系統主題挖掘的協同過濾算法

李 雪,高心丹

(東北林業大學 信息與計算機工程學院,哈爾濱 150040) E-mail:gaoxd@nefu.edu.cn

1 引 言

隨著互聯網信息與網絡服務(如:電影、音樂)的爆炸式增長,信息過載成為一大難題,個性化推薦系統應運而生,它的出現有效地提高了信息處理效率和服務質量.當前在電子商務[1]、餐飲[2]、交通運輸[3]等領域都存在著各種形式的推薦系統.協同過濾算法[3]是眾多推薦系統中應用最廣泛、最成功的推薦技術之一,在眾多領域得到了應用.然而隨著系統數據多維化、稀疏化情況的加劇,近鄰尋找的復雜度急劇增加,推薦系統性能顯著下降.為了解決這些問題,很多學者采用聚類算法來提高推薦效果[4,6-7].由于項目分類標簽與項目內容有較高的相關性,獨立于評分數據的系統本身就存在一種自然的群組,基于信息缺失的稀疏矩陣的聚類雖然能夠提高推薦精度,但存在聚類結果解釋性較差、聚類數量的選擇帶有主觀性、聚類空間較大等問題.本文通過更新聚類算法、改變聚類對象,生成可解釋性較高的系統主題分類以改善傳統方法的不足,同時兼顧項目的時間和評分屬性尋找近鄰.在解決項目的主題跨度問題方面,本文引入一種主題偏重系數來衡量系統內項目的內容傾向,最后得到相應主題下用戶對未評分目標項目的偏好,并依據偏好度排序得到推薦結果.

2 相關工作

2.1 項目屬性對推薦的影響

傳統推薦算法是基于用戶項目評分矩陣計算項目相似度或用戶相似度,由于用戶項目評分數據是一種有缺失值的、稀疏的數據,在傳統相似度計算過程中會產生一定量的誤差,這種誤差會降低推薦系統的性能.為了提高推薦性能一些研究者采用矩陣填充的方法來改善相似度計算的數據基礎,如鄧愛林等[8]通過對用戶評分并集中的未評分項目進行預測評分達到局部填充的效果,在此基礎上進行相似度計算.張鋒等[9]利用BP神經網絡算法對用戶未評分項目進行預測評分,增強數據密度,基于填充矩陣進行相似度計算.然而填充過程存在預測誤差并且計算復雜度較高.也有一些研究者通過降維技術增加數據緊密度,如Sarwar B M等[11]通過奇異值分解減少項目空間維數,在降維后的緊密數據上計算用戶關聯度,但降維會導致信息丟失,對推薦系統的影響不一定是正面的.上述文獻中相似度計算是以應用填充或降維技術處理后的用戶評分矩陣為基礎,在項目或用戶關系中僅僅考慮了用戶評分的影響,計算得到的相似度是一種單一相似度,在刻畫項目關聯性時具有片面性、局限性,所以又有一些學者在相似度計算過程中增加了項目屬性,如劉健等[10]引入項目標簽,分別計算用戶與標簽、標簽與項目的關聯度,構建用戶興趣模型.張新猛等[5]在相似度計算過程中考慮了項目的評分相似性與類別相似性,提升了項目間的關聯度.上述改進方案增加了項目關聯的緊密度、弱化了評分數據稀疏性的影響,提升了推薦質量,可見項目屬性對于提升關系描述準確度具有積極的作用.本文在相似度計算過程中融入了項目的評分與時間屬性,通過平衡因子協調項目評分相似度與項目時間相似度.

2.2 基于聚類的推薦算法

聚類算法的應用有效的縮小了近鄰搜索空間、提升了計算效率、增強了推薦性能,如Rashid等[12]在評分矩陣的基礎上進行用戶聚類,聚類中心作為聚類的代理用戶,然后基于目標用戶的最相似代理用戶進行最近鄰推薦.鄧愛林等[6]采用K-means算法對評分矩陣進行項目的聚類,得到k個項目分類,然后在與目標項目最相似的幾個類中通過計算評分矩陣的相似度來搜索近鄰并排序產生推薦.George等[13]使用聯合聚類方法基于評分矩陣對項目與用戶同時聚類.

上述方法基于評分數據分別對項目、用戶進行聚類,然而系統項目評分數據是一種高維的、有缺失的、信息稀疏的數據,影響聚類的準確性;同時,上述聚類算法應用時,需要事先人為確定分類數量,存在一定的主觀因素,并且產生的聚類中心并非真實存在數據.為了改善上述問題,本文改變了聚類對象,引入一種低維的項目-類別矩陣,降低了聚類空間,并且在聚類階段應用了一種較新的高效聚類算法—近鄰傳播聚類算法(AP聚類),該算法不需要事先指定聚類個數,聚類中心是原始數據中真實存在的值,且多次執行結果完全一樣.本文利用AP算法對項目-類別矩陣進行聚類,從而生成新的分類,聚類中心作為新分類的主題描述.

3 改進的推薦算法

3.1 基于分類標簽的AP聚類

3.1.1 項目分類標簽相似度

分類標簽指系統中實際存在的、描述性的類別標注,如果兩個分類標簽(如喜劇、愛情)在項目分布上趨向一致,說明這兩個標簽在內容表達上具有一定的聯動性.

表1 項目-類別標簽矩陣
Table 1 Matrix of item-genre

基于上述思想,在系統中構建與表1同樣的項目-類別標簽矩陣.可以使用Jaccard系數計算標簽之間的相似性,設分類標簽c和d標注的項目集為Ic和Id,則c和d之間的相似性sim(c,d)如公式(1)所示:

(1)

通過相似度計算得到的分類標簽相似度矩陣作為AP聚類的輸入.

3.1.2 AP聚類

AP聚類的基本思想[7]:給定N個數據點,計算數據點兩兩之間的相似度構造矩陣S.在相似度矩陣S基礎上,依靠兩點之間的消息傳遞迭代更新,即計算吸引度R(i,k)和歸屬度A(i,k),R(i,k)和A(i,k)值越大,點k作為聚類中心和i屬于以k為聚類中心的簇的可能性越大.當迭代次數達到上限或收斂程度符合要求時,停止迭代,產生n個符合要求的聚類中心,再根據聚類中心與普通點的相似度,將普通點劃分到不同的聚類中,完成整個聚類過程.

R(i,k)和A(i,k)的計算公式如下:

R(i,k)=S(i,k)-max{A(i,k)+S(i,j)}

(2)

(3)

R(k,k)=P(k)-max{A(k,j)+S(k,j)}

(4)

其中,j∈{1,2,3,…,N,j≠k}

引入阻尼系數λ控制迭代的收斂,每次迭代都需要考慮上一次的吸引度和歸屬度,加權更新如下:

Ri=(1-λ)×Ri+λ×Ri-1

(5)

Ai=(1-λ)×Ai+λ×Ai-1

(6)

其中,λ∈[0.5,1).

下面給出聚類的具體流程:

Step1.計算分類標簽相似度矩陣S,S作為AP聚類的輸入.

Step2.選取參考度閥值P(P為點i作為聚類中心的標準,本文取相似度矩陣S的中值).

Step3.計算吸引度和歸屬度,根據R(k,k)+ A(k,k)的值來判斷k是否為聚類中心.

Step4.若迭代次數達到上限或者聚類中心已經不在發生變化,轉Step 5,否則,返回Step 3.

Step5.將其余點根據相似度劃分到各個聚類中,生成新類別.

Step6.根據項目初始標簽所屬的新類別進行項目類別劃分,允許跨類分布,聚類結束.

3.2 類內項目相似度

在計算項目相似度時考慮了項目的時間、評分屬性,即認為同一主題下同時代分布的項目更加相似.

在計算項目年代相似性時,以年代作為項目時間分布的單位,由于項目具有固定的生產或發布時間,在時間分布上具有唯一性,所以在計算相似度時,相同年代項目間相似度為1,不同年代項目間的相似度為0.建立項目—時間相似度矩陣T(n,n),Tij值為0或1.

余弦相似度:

(7)

修正余弦相似度:

(8)

皮爾森相似度:

(9)

本文引入了平衡因子α協調項目時間相似性和評分相似性對項目相似性的影響,由此定義的項目間相似性度量公式作為項目i和項目j之間類內相似性度量的標準,如公式(10)所示.

simk(i,j)=αsimr(i,j)+(1-α)T(i,j)

(10)

3.3 產生推薦

3.3.1 主題偏重系數

由于存在跨主題分布項目,所以類內評分不能作為項目最終的評分,所以引入了主題偏重系數W作為項目所跨主題的系統偏重.設項目h橫跨主題集合為M={M1,M2…Mn},Mk∈M,k=1,2,…n,對應的項目集合為IM=IM1∪IM2∪…∪IMn,則項目所跨主題對應的偏重系數為:

(11)

式中CMIMk為IMk在集合M中的補集.

3.3.2 預測推薦

由于系統存在單一主題項目和多主題項目,所以分兩種方式進行計算.

(12)

(13)

4 實驗結果及分析

4.1 實驗數據集及度量標準

實驗數據采用GroupLens站點(http://www.grouplens.org/)提供的MovieLens 數據集,GroupLens項目組提供了不同大小的數據集,本文采用ml-100k數據集,該數據集包含943位用戶對1628部電影的1000 000個評分,且評分范圍為1-5,每個用戶至少對20部以上的電影進行了評分,數據稀疏度為93.7%.

實驗采用的數據集包含1682部電影、19種電影類型標簽,忽略掉僅含2部電影且信息缺失的unknown類型,數據集更新為1680部電影18種類型.18個電影類型依次對應0、1、…、17,一部電影對應有1-7個類型標簽.電影發行時間的時間軸為1922-1998年,橫跨8個年代,以年代為單位對電影進行劃分,年代類型依次對應0、1、…、7.具體實驗取數據集中u.data的評分子集:隨機選取400名用戶作為實驗數據集,隨機選取80%數據作為訓練集,20%數據作為測試集,訓練集稀疏度為94.0%.

本文使用MAE方法[14]度量預測準確度,主要通過計算測試集中用戶的預測評分與實際評分之間的平均偏差來度量預測算法的準確性,可以直觀地度量推薦質量,MAE越小,推薦質量越高.MAE定義為:

(14)

式中pi為預測評分、qi為真實評分、N為測試集數量.

4.2 實驗分析

算法中有2個參數需要選擇:聚類算法中的參考度P、相似度平衡因子α,參考度P取項目標簽相似度的中值,平衡因子α,通過實驗進行選取.

表2 聚類結果
Table 2 Result of clustering

類別組 成描述1聚類中心:Action標簽:Action、War、Horror、Western、Sci-Fi、Thriller、Adventure偏打斗場景2聚類中心:Children's標簽:Children's、Animation、Fantasy、Musical適合兒童3聚類中心:Documentary標簽:Documentary紀錄片4聚類中心:Film-Noir標簽:Film-Noir、Crime、Mystery社會陰暗面5聚類中心:Romance標簽:Romance、Drama、Comedy浪漫、輕松

AP聚類算法對項目分類標簽進行聚類,產生5個聚類集,如表2所示.

平衡因子α是調節項目相似性的參數,可以使相似性的計算更加合理,實驗1設計α的取值為0-1.0,每次增加0.1,設定鄰居數為20.圖1表示在本文提出的協同過濾算法中不同評分相似度下α對預測性能的影響.

實驗結果表明,融合評分相似度和時間相似度的算法優于單一相似度算法(α=0.0、1.0)的預測效果.隨著α的增加,MAE呈遞減趨勢,評分越來越接近實際評分.在實驗對比階段,選擇對應相似度下的最優α值進行實驗.

4.3 實驗對比

為驗證本文算法的有效性,設計實驗與傳統協同過濾算法的預測性能進行對比.最早在MovieLens數據集上應用傳統協同過濾算法的是GroupLens研究小組的Sarwar教授等人.

圖1 平衡因子對MAE的影響Fig.1 Influence of α to MAE

在文獻[14]中,Sarwar教授等人通過實驗得到Item-based方法的推薦效果要略好于User-based方法的結論,并且對傳統Item-based方法在MovieLens數據集上的性能進行了評估,如圖2所示.

圖2 傳統協同過濾的預測效果Fig.2 Effect of traditional collaborative filtering

傳統Item-based方法在不同相似度下預測效果不同,其中基于修正余弦相似度(AdjustedCosine)Item-based方法表現最佳.本文將與文獻[14]中傳統協同過濾在MovieLens數據集上的最佳預測效果即基于修正余弦相似度Item-based方法的MAE值進行對比實驗,如圖3所示.

圖3 預測精度比較Fig.3 Accuracy comparison of algorithm

從預測精度的比較可以看出,本文提出的方法在Cosine度量標準下,鄰居數量大于80,MAE值較優;在AdjustedCosine度量標準下,鄰居數量大于30,MAE值較優;在Pearson度量標準下,鄰居數量大于30,MAE值較優,且整體預測效果最優.從對比實驗可以看出,本文提出的基于系統主題挖掘的協同過濾算法對推薦效果的準確性有明顯的提升作用.

5 結 論

針對傳統推薦算法在近鄰尋找時忽略了系統本身的群組特性的問題,本文引入了系統主題模型,充分挖掘系統項目本身的特點,改善了傳統算法對評分矩陣的依賴性,緩解了新物品的初始群組問題.實驗表明本文提出的方法可以顯著提高推薦算法的準確性.本文方法雖然一定程度上緩解了數據稀疏問題對推薦精度的影響,但仍存在冷啟動、鄰居稀疏等問題,因而未來將會重點研究結合矩陣填充、圖論等知識的推薦算法以降低推薦算法的局限性.

[1] Ai Dan-xiang,Zuo Hui,Yang Jun.C2C e-commerce recommender system based on three-dimensional[J].Computer Engineering and Design,2013,34(2):702-706.

[2] Xiong Cong-cong,Deng Ying,Shi Yan-cui,et al.Food recommendation algorithm based on collaborative filtering [J].Application Research of Computers,2017,34(7):1-5.

[3] Shao Kuo-yi,Ban Xiao-juan,Wang Xiao-kun,et al.Geographic information recommender system optimized by transportation network data [J].Chinese Journal of Engineering,2015,37(12):1651-1657.

[4] Li Tao,Wang Jian-dong,Ye Fei-yue.Collaborative filtering recommendation algorithm based on clustering basal users[J].System Engineering and Electronics,2007,29(7):1177-1178.

[5] Zhang Xin-meng,Li Song.Collaborative filtering recommendation algorithm considering data weight and item attributes[J].Automation and Instrumentation,2016,36(9):69-73.

[6] Deng Ai-lin,Zuo Zi-ye,Zhu Yang-yong.Collaborative filtering recommendation algorithm based on clustering [J].Mini-Micro Systems,2004,25(9):1665-1670.

[7] Hu Ji-hua,Cheng Zhi-feng,Zhan Cheng-zhi.AP algorithm for public transportation station clustering [J].Computer Engineering,2011,37(S1):223-225+232.

[8] Deng Ai-lin,Zhu Yang-yong,Shi Bo-le.A collaborative filtering recommendation algorithm based on item rating prediction [J].Journal of Software,2003,14(9):1621-1628.

[9] Zhang Feng,Chang Hui-you.Employing BP neural networks to alleviate the sparsity issue in collaborative filtering recommendation algorithms[J].Journal of Computer Research and Development,2006,49(4):667-672.

[10] Liu Jian,Zhang Kun,Chen Xuan.Personalized recommendation algorithm based on tags and collaborative filtering [J].Computer and Modernization,2016,32(2):62-65+71.

[11] Sarwar B,Karypis G,Konstan J,et al.Application of dimensionality reduction in recommender system-a case study[R].Minnesota Univ,Minneapolis Dept.of Computer Science,2000.

[12] Rashid A M,Lam S K,Karypis G,et al.ClustKNN:a highly scalable hybrid model- & memory-based CF algorithm[C].Proceeding of Web Knowledge Discovery and Data Mining(Web KDD),2006.

[13] George T,Merugu S.A scalable collaborative filtering framework based on co-clustering[C].IEEE 5th International Conference on Data Mining(ICDM),2005:625-628.

[14] Sarwar B,Karypis G,Konstan J,et al.Item-based collaborative filtering recommendation algorithms[C].Proceedings of the 10th International World Wide Web Conference(WWW),2001:285-295.

附中文參考文獻：

[1] 艾丹祥,左 暉,楊 君.基于三維協同過濾的C2C電子商務推薦系統[J].計算機工程與設計，2013，34(2)：702-706.

[2] 熊聰聰,鄧 瀅,史艷翠,等.基于協同過濾的美食推薦算法[J].計算機應用研究,2017,34(7):1-5.

[3] 邵闊義,班曉娟,王笑琨,等.基于交通網絡數據優化的地理信息推薦系統[J].工程科學學報,2015,37(12):1651-1657.

[4] 李 濤,王建東,葉飛躍.一種基于用戶聚類的協同過濾推薦算法[J].系統工程與電子技術,2007,29 (7):1177-1178.

[5] 張新猛,李 松.基于項目屬性與數據權重的協同過濾推薦算法[J].自動化與儀表,2016,36(9):69-73.

[6] 鄧愛林,左子葉,朱揚勇.基于項目聚類的協同過濾推薦算法[J].小型微型計算機系統,2004,25(9):1665-1670.

[7] 胡繼華,程智鋒,詹承志.一種用于公交站點聚類的AP算法[J].計算機程,2011,37(S1):223-225+232.

[8] 鄧愛林,朱揚勇,施伯樂.基于項目評分預測的協同過濾推薦算法[J].軟件學報,2003,14(9):1621-1628.

[9] 張 鋒,常會友.使用BP神經網絡緩解協同過濾推薦算法的稀疏性問題[J].計算機研究與發展,2006,49(4):667-672.

[10] 劉 健,張 琨,陳 旋.基于標簽和協同過濾的個性化推薦算法[J].計算機與現代化,2016,32(2):62-65+71.