全文鏈接：http://tecdat.cn/?p=31502

原文出處：拓端數(shù)據(jù)部落公眾號

摘要

本課題著眼于譜聚類在社會化推薦挖掘中的應(yīng)用研究。譜聚類算法是基于圖論的數(shù)據(jù)聚類算法，與其他聚類方法相比具有明顯的優(yōu)勢：建立在譜圖理論的基礎(chǔ)之上；操作簡單，易于實(shí)現(xiàn)；具有識別非高斯分布的能力，非常適用于許多實(shí)際應(yīng)用問題。所以，譜聚類算法成為近幾年來機(jī)器學(xué)習(xí)領(lǐng)域的一個新的研究熱點(diǎn)，處理方法以及機(jī)器學(xué)習(xí)本身算法理論的學(xué)習(xí)和代碼實(shí)現(xiàn)在各領(lǐng)域具有相同性，之后同學(xué)可以在其他感興趣的領(lǐng)域結(jié)合數(shù)據(jù)進(jìn)行分析，利用此課題所學(xué)知識舉一反三。

在電影社交網(wǎng)站Flixster 數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，本文提出的改進(jìn)的社會化推薦算法在一定程度上緩解了傳統(tǒng)推薦系統(tǒng)面臨的準(zhǔn)確性、稀疏性、實(shí)時性的問題，在 MAE、準(zhǔn)確率、召回率和覆蓋率等指標(biāo)上有了明顯的提高。

基于用戶譜聚類集成的社會化推薦

聚類集成是將單個聚類算法的聚類結(jié)果合并成一個最終的聚類結(jié)果，集成后的聚類結(jié)果優(yōu)于單個聚類算法的聚類結(jié)果。目前，聚類集成技術(shù)已經(jīng)廣泛應(yīng)用于醫(yī)學(xué)診斷、基因表達(dá)、非數(shù)值型計算等領(lǐng)域[2]。

本章在已有研究基礎(chǔ)上，拓展了聚類集成技術(shù)的應(yīng)用領(lǐng)域，提出了基于用戶譜聚類集成的社會化推薦算法(SCECF)。將用戶互關(guān)聯(lián)矩陣作為譜聚類的相似度矩陣再次聚類，得到最終的聚類結(jié)果。然后，在用戶所屬類中尋找用戶最近鄰并產(chǎn)生推薦。SCECF 算法同樣可以分為離線譜聚類和在線 Top-N 推薦兩個階段。

離線譜聚類階段

輸入：原始評分矩陣 R，用戶關(guān)系矩陣 T，聚類數(shù)目 k

輸出：聚類后的用戶關(guān)系矩陣 T’

1、聚類成員生成：

Step1：從 N 個用戶中隨機(jī)選取 n 個用戶作為樣本，利用公式(2.8)以下計算樣本用戶相似度矩陣 An×n 及樣本用戶與剩余用戶的相似度矩陣 Bn× （N-n）

Step2：令 Gn× N=[A?? B]，構(gòu)造 G 矩陣的度矩陣 Dn× n，根據(jù)公式(3.7)構(gòu)造 A的規(guī)范化拉普拉斯矩陣 Lsym。

Step3：對 Lsym 進(jìn)行特征分解，即 Lsym=UΛU-1。利用 Nystro?? m 擴(kuò)展方法計算N 個用戶的規(guī)范化拉普拉斯矩陣的特征向量U—。

Step4：選U—取前 k 個特征向量 v1，v2，…vk 組成矩陣 V=[v1，v2，…vk]T并對V 進(jìn)行規(guī)范化處理。

Step5：利用 K-means 聚類方法將特征向量空間 V 聚為 k 類，即將用戶聚為k 類， 生成用戶聚類矩陣 CN× N， 當(dāng)用戶 i 與用戶 j 屬于同一類時 Cij=1，否則 Cij=0。

2、聚類集體生成：

Step6：重復(fù)執(zhí)行以上步驟 m 次，將生成的 m 個用戶聚類矩陣 CN× N 相加，得到用戶關(guān)聯(lián)矩陣 NP。

Step7：對用戶關(guān)聯(lián)矩陣 NP 進(jìn)行譜聚類。

Step8：根據(jù)譜聚類結(jié)果生成最終的用戶關(guān)系矩陣 T’，當(dāng)用戶 i 與用戶 j 屬

于同一類時 T’ij=1，否則 T’ij=0。

在線 Top-N 推薦階段

輸入：聚類后的用戶關(guān)系矩陣 T’

輸出：用戶 Top-N 推薦列表

Step1：計算聚類后的用戶相似度矩陣 PN× N。當(dāng)用戶 i 與用戶 j 屬于同一類

時 Pij=sim(i,j)，否則? Pij=0。

Step2：對 P 矩陣進(jìn)行排序，生成用戶最近鄰集合。

Step3：利用公式(2.9)計算用戶未評分項(xiàng)目的預(yù)測值，生成用戶預(yù)測評分矩

陣 Rpre。

Step4：對 Rpre 進(jìn)行排序，將預(yù)測評分最高的 Top-N 個項(xiàng)目推薦給用戶。

創(chuàng)新之處

本文的創(chuàng)新之處主要體現(xiàn)在以下幾個方面：

（1）基于Nystrom擴(kuò)展技術(shù)的譜聚類

針對譜聚類方法在大規(guī)模數(shù)據(jù)應(yīng)用中計算時間復(fù)雜度和空間復(fù)雜度較高的問題，引入Nystrom擴(kuò)展技術(shù)。首先計算所抽取的少量樣本的相似度矩陣和特征向量，跟樣本的特征向量采用Nystrom擴(kuò)展方法逼近計算整個數(shù)據(jù)集的特征向量。相對于計算整個數(shù)據(jù)集的相似度矩陣和特征向量，采用Nystrom擴(kuò)展的譜聚類方法，改善了計算的時間和空間復(fù)雜度，解決了譜聚類算法在大規(guī)模數(shù)據(jù)中的應(yīng)用問題。

（2）譜聚類集成技術(shù)

由于譜聚類算法中使用近似逼近的方法，以及譜聚類算法本身的初值敏感問題，聚類的結(jié)果并不十分穩(wěn)定，采用聚類集成策略來解決這個問題。通過尋找多個聚類結(jié)果的組合來獲得相對較優(yōu)的聚類結(jié)果，從而獲取較好的平均性能，提高聚類結(jié)果的穩(wěn)定，并且一定程度上克服了譜聚類算法對噪音、異常點(diǎn)、采樣的變動的敏感性問題。

（3）應(yīng)用領(lǐng)域創(chuàng)新

將改進(jìn)的譜聚類算法應(yīng)用到基于社交網(wǎng)絡(luò)的推薦系統(tǒng)中，克服了目前推薦系統(tǒng)中存在的準(zhǔn)確性、實(shí)時性、稀疏性等問題。譜聚類算法實(shí)質(zhì)上是對圖的劃分，而社交網(wǎng)絡(luò)中用戶之間的關(guān)系也表示為圖的形式，因此對社交網(wǎng)絡(luò)中相似用戶群的劃分可以使用譜聚類的方法。在使用譜聚類后的用戶群中，尋找用戶最近鄰，然后預(yù)測用戶對問評分項(xiàng)目的評分，最后產(chǎn)生推薦。

實(shí)驗(yàn)與結(jié)果分析

實(shí)驗(yàn)數(shù)據(jù)集

本文分別在兩個代表性的數(shù)據(jù)集Flixster上對算法進(jìn)行了測試。Flixster 是一個電影社交網(wǎng)站，在 Flixster 網(wǎng)站上用戶分享電影的評分，討論新的電影，也可以通過電影認(rèn)識有相同愛好的人。本章選取電影社交網(wǎng)站Flixster 的用戶數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)集。該數(shù)據(jù)集包含兩個部分，一部分是用戶評分?jǐn)?shù)據(jù)，包含 885個用戶對 1000個電影的評分記錄 192775 條。用戶評分值介于 0.5-5 之間，評分間隔為 0.5，數(shù)值越大，說明用戶對項(xiàng)目的喜愛程度越高，反之，說明用戶對項(xiàng)目興趣度不高；另一部分是用戶朋友關(guān)系數(shù)據(jù)，包含以上892個用戶之間的朋友關(guān)系。 數(shù)據(jù)集示例如圖 3.2 所示。 實(shí)驗(yàn)中隨機(jī)抽取用戶評分?jǐn)?shù)據(jù)集的 80%作為訓(xùn)練集，其余 20%作為測試集。

圖 3.1 Flixster 數(shù)據(jù)集（部分）

?表3.2 數(shù)據(jù)集描述

名稱描述簡介每個用戶至少評分物品Flixster對電影的評分從1到5885名用戶對1000部電影的評價100

評分預(yù)測的預(yù)測準(zhǔn)確度一般通過平均絕對誤差 （MAE） 計算，平均絕對偏差越小，預(yù)測的準(zhǔn)確度越高。

實(shí)驗(yàn)過程與結(jié)果分析

(1)確定最佳聚類數(shù)

首先，通過比較不同聚類數(shù)相應(yīng)的聚類有效性函數(shù)值來選出最佳聚類數(shù)cmax。實(shí)驗(yàn)結(jié)果如圖3.2所示。

size(sc)withinss(sc)plot(testMatrix, col=sc)

圖3.2 Flixster數(shù)據(jù)集不同聚類數(shù)對應(yīng)的聚類有效性函數(shù)值

圖3.2中的橫坐標(biāo)為聚類數(shù)，縱坐標(biāo)為相應(yīng)的4個聚類有效性函數(shù)值。由上述結(jié)果可知，在2到

的最佳搜索范圍中，不同的聚類數(shù)c得到的VPE值與VFC值呈單調(diào)趨勢，而VXB與VK函數(shù)值均在c=12時單調(diào)性發(fā)生改變。

表3.3 Xie-Beni方法確定的最佳聚類數(shù)cmax

判別函數(shù)VPEVXBVFCVKFlixster數(shù)據(jù)集cmax>25cmax=10cmax>25cmax=10

因此， 本文選取Flixster數(shù)據(jù)集的最佳聚類數(shù)cmax為12，本文選取最佳聚類數(shù)cmax為12。

（2）MAE指標(biāo)比較

模糊C均值聚類算法的關(guān)鍵步驟是確定最佳聚類簇數(shù)，為檢驗(yàn)本節(jié)給出的FCMC CF算法，我們在Movielens和Flixster數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)分析，并將其同K-means、K-medoids和K-mode聚類協(xié)同過濾算法進(jìn)行了比較，實(shí)驗(yàn)結(jié)果如圖3.4和3.5所示。

preR=matrix(1,RECOMMENDER_NUM,ncol(M)) ?for(item in 1:ncol(M)){ ? ?R<-ItemBasedRecommenderlist(item,RECOMMEN ? ? lusplot(y[,1:2], cl$cluster , color=TRUE, shade=TRUE , ? ? ? ? labels=2, lines=0)

圖3.4 ?不同算法MAE的比較

?圖3.5? 不同算法MAE的比較

在圖3.4和圖3.5中，橫軸為最近鄰個數(shù) k，縱軸為平均絕對偏差 MAE。曲線CF代表傳統(tǒng)的協(xié)同過濾算法，曲線Kmean CF代表基于K均值聚類的協(xié)同過濾算法，曲線FCMC CF代表基于模糊C均值聚類有效性的協(xié)同過濾算法，曲線K medoids CF代表基于K medoids聚類的協(xié)同過濾算法。

由圖圖3.4和圖3.5可以看到基于有效性指標(biāo)改進(jìn)的FCMC CF算法在MAE指標(biāo)上要明顯優(yōu)于其他算法。在Movielens和Flixster數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，F(xiàn)CMC CF得到的MAE值要優(yōu)于其他幾個算法。

（3）召回率和覆蓋率的比較

在接下來的TOP-N實(shí)驗(yàn)中，我們選擇FCMC CF算法與其他算法在召回率、覆蓋率指標(biāo)上進(jìn)行比較。實(shí)驗(yàn)結(jié)果如圖3.6和圖3.7所示。

圖3.6 不同算法覆蓋率的比較

plot(seq(from=5, to=50, by=10),Coverage,type="l")

圖3.7 不同算法召回率的比較

在圖3.4和圖3.5中，橫軸代表推薦列表長度N，縱軸分別為召回率和覆蓋率。其中，每個N值對應(yīng)的兩條曲線圖分別為FCMC CF與CF、Kmeans CF對應(yīng)的函數(shù)值。

FCMC CF算法與傳統(tǒng)CF算法和Kmeans CF算法相比，在不同的最近鄰水平下具有較高的召回率和覆蓋率，即新算法在推薦質(zhì)量上有所改善，有效地提升了推薦精度。

?

結(jié)論與展望

本文對社會化推薦系統(tǒng)進(jìn)行了研究，將譜聚類算法、聚類集成技術(shù)應(yīng)用到社會化推薦算法中，對傳統(tǒng)的協(xié)同過濾推薦算法進(jìn)行改進(jìn)。

主要取得了如下成果：

（1）將社交網(wǎng)絡(luò)信息和譜聚類算法應(yīng)用到傳統(tǒng)協(xié)同過濾算法中，提出了基于用戶譜聚類的社會化推薦算法，在一定程度上緩解了數(shù)據(jù)稀疏性問題。在數(shù)據(jù)集上的實(shí)驗(yàn)表明，改進(jìn)的算法提高了傳統(tǒng)算法的推薦性能。

（2 ）針對處理大規(guī)模數(shù)據(jù)集時譜聚類算法執(zhí)行效率較低的問題，使用Nystr? m 擴(kuò)展方法對譜聚類算法進(jìn)行改進(jìn)，提出了基于 Nystr? m 擴(kuò)展譜聚類的社會化推薦算法。實(shí)驗(yàn)結(jié)果表明，該算法在縮短了算法的執(zhí)行時間的同時提高了推薦的性能。

（3）為了提高聚類結(jié)果的穩(wěn)定性和準(zhǔn)確性，在推薦算法中引入了聚類集成技術(shù)，提出了基于用戶譜聚類集成的社會化推薦算法。實(shí)驗(yàn)結(jié)果表明，引入聚類集成后的推薦算法在預(yù)測準(zhǔn)確率、召回率、覆蓋率等指標(biāo)上都有了明顯提高。

?

參考文獻(xiàn)

[1]許海玲,吳瀟,李曉東,閻保平. 互聯(lián)網(wǎng)推薦系統(tǒng)比較研究[J]. 軟件學(xué)報,2009,20(2):350-362

[2]曾子明.信息推薦系統(tǒng)[M]. 北京:科學(xué)出版社, 2013.

[3]Mooney R J, Roy L. Content-based book recommending using learning for text categorization[C]. Proceedings of the 5th ACM Conference on Digial Libraries, New York, 2000:167-176.

[4]Balabonovic M, Shoham Y. Fab:content-based collaborative recommendation[C]. Communications of the ACM,1997,40(3):66-72.

最受歡迎的見解

1.R語言k-Shape算法股票價格時間序列聚類

2.R語言基于溫度對城市層次聚類、kmean聚類、主成分分析和Voronoi圖

3.R語言對用電負(fù)荷時間序列數(shù)據(jù)進(jìn)行K-medoids聚類建模和GAM回歸

4.r語言鳶尾花iris數(shù)據(jù)集的層次聚類

5.Python Monte Carlo K-Means聚類實(shí)戰(zhàn)

6.用R進(jìn)行網(wǎng)站評論文本挖掘聚類

7.R語言KMEANS均值聚類和層次聚類：亞洲國家地區(qū)生活幸福質(zhì)量異同可視化

8.PYTHON用戶流失數(shù)據(jù)挖掘：建立邏輯回歸、XGBOOST、隨機(jī)森林、決策樹、支持向量機(jī)、樸素貝葉斯模型和KMEANS聚類用戶畫像

9.R語言基于Keras的小數(shù)據(jù)集深度學(xué)習(xí)圖像分類