李寒芳,吳東月,高 強(qiáng)

（天津理工大學(xué)自動(dòng)化學(xué)院，天津,300384）

基于二分網(wǎng)絡(luò)的用戶聚類電影推薦系統(tǒng)構(gòu)建

李寒芳,吳東月,高 強(qiáng)

（天津理工大學(xué)自動(dòng)化學(xué)院，天津,300384）

針對(duì)已經(jīng)存在的推薦算法中數(shù)據(jù)的稀疏性問題，提出一種基于聚類算法的二分圖信任網(wǎng)絡(luò)構(gòu)造算法，通過聚類技術(shù)把項(xiàng)目評(píng)分相似的用戶聚集起來，形成若干個(gè)用戶群組，在每個(gè)群組內(nèi)部通過二分圖建立連接，利用信任機(jī)制在群組內(nèi)部和群組間建立連接，進(jìn)而構(gòu)造出推薦系統(tǒng)。實(shí)驗(yàn)是在MovieLens數(shù)據(jù)集上進(jìn)行的，采用平均絕對(duì)誤差（MAE）為評(píng)測指標(biāo)，驗(yàn)證了方法的有效性，從而得出該系統(tǒng)使得數(shù)據(jù)稀疏性對(duì)最終推薦結(jié)果的負(fù)面影響變小。

二分圖; 聚類; 推薦系統(tǒng)；數(shù)據(jù)稀疏性；信任機(jī)制

1 系統(tǒng)構(gòu)建

在大量的電影中，用戶往往對(duì)和自己興趣相似的用戶推薦的電影比較感興趣。系統(tǒng)構(gòu)建過程分為三步。第一步進(jìn)行用戶聚類，先提取用戶對(duì)所有項(xiàng)目的評(píng)分?jǐn)?shù)據(jù)，然后依據(jù)聚類算法對(duì)評(píng)分相似的用戶進(jìn)行聚類，形成k個(gè)用戶聚類分組。第二步在子網(wǎng)中構(gòu)建二分圖，在每個(gè)聚類內(nèi)部的用戶間建立二分網(wǎng)絡(luò)。第三步在子網(wǎng)間建立長距離連接，從而使得構(gòu)造出的網(wǎng)絡(luò)有較短的特征路徑長度。

2 算法設(shè)計(jì)

2.1 用戶聚類

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

步驟1首先在已有的用戶中隨機(jī)選擇一個(gè)點(diǎn)作為第一個(gè)中心點(diǎn)。

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

步驟5利用被選出來的這k個(gè)初始的聚類中心來運(yùn)行標(biāo)準(zhǔn)的K-means算法。

圖2 二分圖網(wǎng)絡(luò)中的資源分配過程

2.2 構(gòu)建二分網(wǎng)絡(luò)

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

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

通過資源二次分配建立項(xiàng)目資源分配矩陣，用戶ui對(duì)項(xiàng)目Ij的推薦預(yù)測值Fij是把和待推薦項(xiàng)目Ij相連的所有項(xiàng)目貢獻(xiàn)的資源加權(quán)求和，由此建立用戶-項(xiàng)目推薦矩陣如下所示：

2.3 長距離連接

在得到k個(gè)子網(wǎng)的基礎(chǔ)上，在存在關(guān)聯(lián)的子網(wǎng)間添加必要的連接，進(jìn)而在保證網(wǎng)絡(luò)連通性的基礎(chǔ)上，有效地加強(qiáng)了子網(wǎng)之間的關(guān)系。每個(gè)聚類中的用戶都與該聚類中心有著高度的相似性，所以可以通過計(jì)算各個(gè)聚類中心之間的相似性來推斷各個(gè)聚類子網(wǎng)之間的相關(guān)性，并將相關(guān)的聚類子網(wǎng)編號(hào)存入每個(gè)聚類子網(wǎng)的一個(gè)列表，進(jìn)而形成k個(gè)關(guān)聯(lián)子網(wǎng)列表。通過公式4計(jì)算每個(gè)子網(wǎng)中節(jié)點(diǎn)的平均信任度，將平均信任度大于或等于設(shè)定閾值的節(jié)點(diǎn)存入一個(gè)列表，形成k個(gè)最可信的用戶列表。對(duì)于所有存在關(guān)聯(lián)的子網(wǎng)Si和Sj，計(jì)算Ti和Tj中節(jié)點(diǎn)所代表用戶間的直接信任度，選取信任度最大的節(jié)點(diǎn)作為這組關(guān)聯(lián)的關(guān)鍵節(jié)點(diǎn)，通過每組關(guān)鍵節(jié)點(diǎn)，在對(duì)應(yīng)的關(guān)聯(lián)子網(wǎng)間建立遠(yuǎn)程連接。

2.4 產(chǎn)生推薦

2.5 算法描述

輸入：用戶評(píng)分?jǐn)?shù)據(jù)D，目標(biāo)用戶u，用戶鄰居數(shù)Nx，聚類個(gè)數(shù)k。

輸出：目標(biāo)用戶u的推薦項(xiàng)目集合。

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

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

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

3.2 系統(tǒng)評(píng)測指標(biāo)

本次實(shí)驗(yàn)采用MAE（Mean Absolute Error）評(píng)價(jià)推薦系統(tǒng)推薦質(zhì)量，數(shù)據(jù)稀疏度計(jì)算，通過計(jì)算評(píng)分矩陣中0所占的比例來表示。N為測試集中的評(píng)分條數(shù)，pi為系統(tǒng)預(yù)測用戶對(duì)項(xiàng)目i的評(píng)分，qi為用戶對(duì)項(xiàng)目i的實(shí)際評(píng)分,。設(shè)用戶項(xiàng)目的評(píng)分矩陣是由m個(gè)用戶對(duì)n個(gè)項(xiàng)目的評(píng)分構(gòu)成的的矩陣，Ns為矩陣中評(píng)分為0的個(gè)數(shù)。

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

實(shí)驗(yàn)1在間接信任度t2不變的情況下，改變直接信任度t1的值，隨著直接信任度t1的增大，MAE的值也相應(yīng)的增大，結(jié)果如圖3所示，所以直接信任度t1的值選擇為0.1。

圖3 直接信任度的選取

4 結(jié)束語

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

[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] 項(xiàng)亮.推薦系統(tǒng)實(shí)踐[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-），女，碩士研究生，研究方向：推薦系統(tǒng)，

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

天津市自然科學(xué)基金（15JCYB51800）資助