一種基于系統(tǒng)主題挖掘的協(xié)同過濾算法

李 雪,高心丹

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

1 引 言

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

2 相關(guān)工作

2.1 項目屬性對推薦的影響

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

2.2 基于聚類的推薦算法

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

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

3 改進的推薦算法

3.1 基于分類標(biāo)簽的AP聚類

3.1.1 項目分類標(biāo)簽相似度

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

表1 項目-類別標(biāo)簽矩陣
Table 1 Matrix of item-genre

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

(1)

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

3.1.2 AP聚類

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

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}

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

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

(5)

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

(6)

其中,λ∈[0.5,1).

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

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

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

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

Step4.若迭代次數(shù)達(dá)到上限或者聚類中心已經(jīng)不在發(fā)生變化,轉(zhuǎn)Step 5,否則,返回Step 3.

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

Step6.根據(jù)項目初始標(biāo)簽所屬的新類別進行項目類別劃分,允許跨類分布,聚類結(jié)束.

3.2 類內(nèi)項目相似度

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

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

余弦相似度:

(7)

修正余弦相似度:

(8)

皮爾森相似度:

(9)

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

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

(10)

3.3 產(chǎn)生推薦

3.3.1 主題偏重系數(shù)

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

(11)

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

3.3.2 預(yù)測推薦

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

(12)

(13)

4 實驗結(jié)果及分析

4.1 實驗數(shù)據(jù)集及度量標(biāo)準(zhǔn)

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

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

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

(14)

式中pi為預(yù)測評分、qi為真實評分、N為測試集數(shù)量.

4.2 實驗分析

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

表2 聚類結(jié)果
Table 2 Result of clustering

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

AP聚類算法對項目分類標(biāo)簽進行聚類,產(chǎn)生5個聚類集,如表2所示.

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

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

4.3 實驗對比

為驗證本文算法的有效性,設(shè)計實驗與傳統(tǒng)協(xié)同過濾算法的預(yù)測性能進行對比.最早在MovieLens數(shù)據(jù)集上應(yīng)用傳統(tǒng)協(xié)同過濾算法的是GroupLens研究小組的Sarwar教授等人.

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

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

圖2 傳統(tǒng)協(xié)同過濾的預(yù)測效果Fig.2 Effect of traditional collaborative filtering

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

圖3 預(yù)測精度比較Fig.3 Accuracy comparison of algorithm

從預(yù)測精度的比較可以看出,本文提出的方法在Cosine度量標(biāo)準(zhǔn)下,鄰居數(shù)量大于80,MAE值較優(yōu);在AdjustedCosine度量標(biāo)準(zhǔn)下,鄰居數(shù)量大于30,MAE值較優(yōu);在Pearson度量標(biāo)準(zhǔn)下,鄰居數(shù)量大于30,MAE值較優(yōu),且整體預(yù)測效果最優(yōu).從對比實驗可以看出,本文提出的基于系統(tǒng)主題挖掘的協(xié)同過濾算法對推薦效果的準(zhǔn)確性有明顯的提升作用.

5 結(jié) 論

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

[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] 艾丹祥,左 暉,楊 君.基于三維協(xié)同過濾的C2C電子商務(wù)推薦系統(tǒng)[J].計算機工程與設(shè)計，2013，34(2)：702-706.

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

[3] 邵闊義,班曉娟,王笑琨,等.基于交通網(wǎng)絡(luò)數(shù)據(jù)優(yōu)化的地理信息推薦系統(tǒng)[J].工程科學(xué)學(xué)報,2015,37(12):1651-1657.

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

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

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

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

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

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

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