基于二分網絡的用戶聚類電影推薦系統構建

李寒芳,吳東月,高 強

（天津理工大學自動化學院，天津,300384）

基于二分網絡的用戶聚類電影推薦系統構建

李寒芳,吳東月,高 強

（天津理工大學自動化學院，天津,300384）

針對已經存在的推薦算法中數據的稀疏性問題，提出一種基于聚類算法的二分圖信任網絡構造算法，通過聚類技術把項目評分相似的用戶聚集起來，形成若干個用戶群組，在每個群組內部通過二分圖建立連接，利用信任機制在群組內部和群組間建立連接，進而構造出推薦系統。實驗是在MovieLens數據集上進行的，采用平均絕對誤差（MAE）為評測指標，驗證了方法的有效性，從而得出該系統使得數據稀疏性對最終推薦結果的負面影響變小。

二分圖; 聚類; 推薦系統；數據稀疏性；信任機制

1 系統構建

在大量的電影中，用戶往往對和自己興趣相似的用戶推薦的電影比較感興趣。系統構建過程分為三步。第一步進行用戶聚類，先提取用戶對所有項目的評分數據，然后依據聚類算法對評分相似的用戶進行聚類，形成k個用戶聚類分組。第二步在子網中構建二分圖，在每個聚類內部的用戶間建立二分網絡。第三步在子網間建立長距離連接，從而使得構造出的網絡有較短的特征路徑長度。

2 算法設計

2.1 用戶聚類

興趣相似的用戶之間相互推薦的電影更加可信，如果一個圈內朋友和一個陌生人同時推薦電影給用戶，該用戶更青睞于圈內朋友推薦的電影。將相似度較高的用戶聚類在一起形成一個圈，這樣推薦給圈內用戶的電影更加獲得用戶的喜歡]。本文的聚類方法是基于評分相似度的用戶聚類方法，首先提取評分數據，然后采用K-means++聚類算法對用戶進行聚類。K-means++算法的主要工作體現在種子點的選擇上，它的基本原則是使得種子點之間的距離盡可能的大。以下為基本思路：

步驟1首先在已有的用戶中隨機選擇一個點作為第一個中心點。

步驟4重復2和3這兩步直到k個聚類中心被選擇出來為止。

步驟5利用被選出來的這k個初始的聚類中心來運行標準的K-means算法。

圖2 二分圖網絡中的資源分配過程

2.2 構建二分網絡

二分圖是圖計算中的一種特殊模型，它在復雜網絡的研究和應用中都具有非常重要的意義。給定圖，如果頂點集V可分為兩個互不相交的非空子集用戶集X和項目集Y，并且圖中的每條邊的兩個端點i和j分別屬于用戶集和項目集，那么就稱圖G是一個二分圖（Bipartite graph），記為。

基于二分圖的推薦算法的思想是將用戶和物品看作抽象的點，將用戶和物品分別看成兩個集合，通過用戶是否給某部電影評分來建立二分網絡。在建立用戶-物品的二分圖后，對于同一個用戶評價過的兩個物品來說，它們具有向用戶互相推薦的能力。對于被同一個用戶評價過的物品f和h來說，f具有向用戶推薦物品h的能力，記作，如果物品f的資源初始化為1的話，則。

通過資源二次分配建立項目資源分配矩陣，用戶ui對項目Ij的推薦預測值Fij是把和待推薦項目Ij相連的所有項目貢獻的資源加權求和，由此建立用戶-項目推薦矩陣如下所示：

2.3 長距離連接

在得到k個子網的基礎上，在存在關聯的子網間添加必要的連接，進而在保證網絡連通性的基礎上，有效地加強了子網之間的關系。每個聚類中的用戶都與該聚類中心有著高度的相似性，所以可以通過計算各個聚類中心之間的相似性來推斷各個聚類子網之間的相關性，并將相關的聚類子網編號存入每個聚類子網的一個列表，進而形成k個關聯子網列表。通過公式4計算每個子網中節點的平均信任度，將平均信任度大于或等于設定閾值的節點存入一個列表，形成k個最可信的用戶列表。對于所有存在關聯的子網Si和Sj，計算Ti和Tj中節點所代表用戶間的直接信任度，選取信任度最大的節點作為這組關聯的關鍵節點，通過每組關鍵節點，在對應的關聯子網間建立遠程連接。

2.4 產生推薦

2.5 算法描述

輸入：用戶評分數據D，目標用戶u，用戶鄰居數Nx，聚類個數k。

輸出：目標用戶u的推薦項目集合。

3 實驗結果及分析

3.1 實驗數據

程序采用Python語言編寫，在Linux系統下運行。本次實驗選用的實驗數據集是MovieLens數據集，該數據集一共提供了3種類型的數據集，這3種數據集的大小分別為100K、1M、10M。本次實驗將選取100K數據集進行實驗，該數據集一共有100000條電影評分，數據集內有943個用戶1682部電影。這943個用戶評分過的電影至少都是20部。數據集會按比例分為訓練集和測試集，所有的評分都是1到5之間的一個整數，評分越高表示用戶對某部電影越喜歡。

3.2 系統評測指標

本次實驗采用MAE（Mean Absolute Error）評價推薦系統推薦質量，數據稀疏度計算，通過計算評分矩陣中0所占的比例來表示。N為測試集中的評分條數，pi為系統預測用戶對項目i的評分，qi為用戶對項目i的實際評分,。設用戶項目的評分矩陣是由m個用戶對n個項目的評分構成的的矩陣，Ns為矩陣中評分為0的個數。

3.3 實驗結果分析

實驗1在間接信任度t2不變的情況下，改變直接信任度t1的值，隨著直接信任度t1的增大，MAE的值也相應的增大，結果如圖3所示，所以直接信任度t1的值選擇為0.1。

圖3 直接信任度的選取

4 結束語

本文首先分析了推薦系統中減小稀疏性影響的一些方法，針對稀疏性問題提出了基于二分圖信任網絡的用戶聚類推薦算法。本文結合聚類算法將評分相似的用戶聚集起來，聚類形成若干個用戶群組，在每個群組內部通過二分圖建立連接，有效的緩解了推薦的稀疏性問題。再通過信任機制在群組內部和群組間建立信任連接，使構建出來的推薦結果更加準確。從上面的實驗結果可以看出，和另外兩種推薦算法相比，本文設計的算法推薦的MAE值更小，對于提高推薦質量做出了貢獻。未來的工作將嘗試設計更加準確的稀疏性處理方法，并且將考慮引入其他的復雜網絡的結合來設計推薦系統，使推薦結果更準確。

[1] Cai X,Bain M,Krzywicki A,et al.Collaborative filtering for people to people recommendation in social networks[M]//AI 2010:Advances in Artificial Intelligence. Springer Berlin Heidelberg,2011:476-485.

[2] Herlocker J L Konstan J A,Terveen L G,et al.Evaluating collaborative filtering recommender systems[J].ACM Transactions on Information Systems(TOIS),2004,22(1):5-53.

[3] 項亮.推薦系統實踐[M].北京:人民郵電出版社, 2012

Construction of user clustering movie recommendation system based on bipartite graph networks

Li Hanfang,Wu Dongyue,Gao Qiang
（School of Automation,Tianjin University of Technology,Tianjin 300384,China）

According to the sparsity of data in the recommendation algorithm,a bipartite graph trust network based on clustering technology is proposed. This recommendation system is constructed by clustering the score similar users together,forming a plurality of user groups.In each group by bipartite graph to establish connection,through the trust mechanism between the groups and the group to establish a connection. Experiment was carried out in MovieLens dataset, and the mean absolute error (MAE) is used as the evaluation index,the experiment verified the validity of the method,and that the system makes the conclusion that data sparsity negative effect on the final recommendation diminish.

bipartite graph;clustering;recommender system;data sparsity;trust mechanism

TP311；

A

李寒芳（1990-），女，碩士研究生，研究方向：推薦系統，

簡介：吳東月（1983-），博士，研究方向：多相測量，生物信息學。

天津市自然科學基金（15JCYB51800）資助