Step6：重複執行以上步驟 m 次，將生成的 m 個用戶聚類矩陣 CN× N 相加，得到用戶關聯矩陣 NP。

Step7：對用戶關聯矩陣 NP 進行譜聚類。

Step8：根據譜聚類結果生成最終的用戶關係矩陣 T』，當用戶 i 與用戶 j 屬

於同一類時 T』ij=1，否則 T』ij=0。

在線 Top-N 推薦階段

輸入：聚類後的用戶關係矩陣 T』

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

Step1：計算聚類後的用戶相似度矩陣 PN× N。當用戶 i 與用戶 j 屬於同一類

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

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

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

陣 Rpre。

Step4：對 Rpre 進行排序，將預測評分最高的 Top-N 個項目推薦給用戶。

創新之處

本文的創新之處主要體現在以下幾個方面：

（1）基於Nystrom擴展技術的譜聚類

針對譜聚類方法在大規模數據應用中計算時間複雜度和空間複雜度較高的問題，引入Nystrom擴展技術。首先計算所抽取的少量樣本的相似度矩陣和特徵向量，跟樣本的特徵向量採用Nystrom擴展方法逼近計算整個數據集的特徵向量。相對於計算整個數據集的相似度矩陣和特徵向量，採用Nystrom擴展的譜聚類方法，改善了計算的時間和空間複雜度，解決了譜聚類算法在大規模數據中的應用問題。

（2）譜聚類集成技術

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

（3）應用領域創新

將改進的譜聚類算法應用到基於社交網絡的推薦系統中，克服了目前推薦系統中存在的準確性、實時性、稀疏性等問題。譜聚類算法實質上是對圖的劃分，而社交網絡中用戶之間的關係也表示為圖的形式，因此對社交網絡中相似用戶群的劃分可以使用譜聚類的方法。在使用譜聚類後的用戶群中，尋找用戶最近鄰，然後預測用戶對問評分項目的評分，最後產生推薦。

實驗與結果分析

實驗數據集

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

圖 3.1 Flixster 數據集（部分）

表3.2 數據集描述

名稱描述簡介每個用戶至少評分物品Flixster對電影的評分從1到5885名用戶對1000部電影的評價100評分預測的預測準確度一般通過平均絕對誤差 （MAE） 計算，平均絕對偏差越小，預測的準確度越高。

實驗過程與結果分析

(1)確定最佳聚類數

首先，通過比較不同聚類數相應的聚類有效性函數值來選出最佳聚類數cmax。實驗結果如圖3.2所示。

size(sc)

withinss(sc)

plot(testMatrix, col=sc)

圖3.2 Flixster數據集不同聚類數對應的聚類有效性函數值

圖3.2中的橫坐標為聚類數，縱坐標為相應的4個聚類有效性函數值。由上述結果可知，在2到的最佳搜索範圍中，不同的聚類數c得到的VPE值與VFC值呈單調趨勢，而VXB與VK函數值均在c=12時單調性發生改變。

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

判別函數VPEVXBVFCVKFlixster數據集cmax>25cmax=10cmax>25cmax=10因此， 本文選取Flixster數據集的最佳聚類數cmax為12，本文選取最佳聚類數cmax為12。

（2）MAE指標比較

模糊C均值聚類算法的關鍵步驟是確定最佳聚類簇數，為檢驗本節給出的FCMC CF算法，我們在Movielens和Flixster數據集上進行了實驗分析，並將其同K-means、K-medoids和K-mode聚類協同過濾算法進行了比較，實驗結果如圖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中，橫軸為最近鄰個數 k，縱軸為平均絕對偏差 MAE。曲線CF代表傳統的協同過濾算法，曲線Kmean CF代表基於K均值聚類的協同過濾算法，曲線FCMC CF代表基於模糊C均值聚類有效性的協同過濾算法，曲線K medoids CF代表基於K medoids聚類的協同過濾算法。

由圖圖3.4和圖3.5可以看到基於有效性指標改進的FCMC CF算法在MAE指標上要明顯優於其他算法。在Movielens和Flixster數據集上的實驗結果表明，FCMC CF得到的MAE值要優於其他幾個算法。

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

在接下來的TOP-N實驗中，我們選擇FCMC CF算法與其他算法在召回率、覆蓋率指標上進行比較。實驗結果如圖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值對應的兩條曲線圖分別為FCMC CF與CF、Kmeans CF對應的函數值。

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

結論與展望

本文對社會化推薦系統進行了研究，將譜聚類算法、聚類集成技術應用到社會化推薦算法中，對傳統的協同過濾推薦算法進行改進。

主要取得了如下成果：

（1）將社交網絡信息和譜聚類算法應用到傳統協同過濾算法中，提出了基於用戶譜聚類的社會化推薦算法，在一定程度上緩解了數據稀疏性問題。在數據集上的實驗表明，改進的算法提高了傳統算法的推薦性能。

（2 ）針對處理大規模數據集時譜聚類算法執行效率較低的問題，使用Nyströ m 擴展方法對譜聚類算法進行改進，提出了基於 Nyströ m 擴展譜聚類的社會化推薦算法。實驗結果表明，該算法在縮短了算法的執行時間的同時提高了推薦的性能。

（3）為了提高聚類結果的穩定性和準確性，在推薦算法中引入了聚類集成技術，提出了基於用戶譜聚類集成的社會化推薦算法。實驗結果表明，引入聚類集成後的推薦算法在預測準確率、召回率、覆蓋率等指標上都有了明顯提高。

參考文獻

[1]許海玲,吳瀟,李曉東,閻保平. 網際網路推薦系統比較研究[J]. 軟體學報,2009,20(2):350-362

[2]曾子明.信息推薦系統[M]. 北京:科學出版社, 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語言對用電負荷時間序列數據進行K-medoids聚類建模和GAM回歸

4.r語言鳶尾花iris數據集的層次聚類

5.Python Monte Carlo K-Means聚類實戰

6.用R進行網站評論文本挖掘聚類

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

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

9.R語言基於Keras的小數據集深度學習圖像分類