牟斌皓，張智恒，張 林，閔 帆+

1.西南石油大學(xué) 計算機科學(xué)學(xué)院，成都 610500

2.西南石油大學(xué) 理學(xué)院，成都 610500

基于四部圖的協(xié)同過濾推薦算法比較研究*

牟斌皓1，張智恒2，張 林1，閔 帆1+

1.西南石油大學(xué) 計算機科學(xué)學(xué)院，成都 610500

2.西南石油大學(xué) 理學(xué)院，成都 610500

MOU Binhao,ZHANG Zhiheng,ZHANG Lin,et al.Comparison study of collaborative filtering algorithms based on quadripartite graph.Journal of Frontiers of Computer Science and Technology,2017,11(6)：875-886.

推薦系統(tǒng)通常利用商品屬性、用戶信息以及用戶對商品的已有評分來獲取用戶或者商品之間的相似度，進而預(yù)測未知評分。構(gòu)造了關(guān)于這些信息的四部圖，然后根據(jù)圖中不同部分的組合獲得了10類推薦算法，并比較了它們的時間復(fù)雜度。前兩類算法基于用戶與商品之間的關(guān)系，為經(jīng)典的協(xié)同過濾算法。中間4類算法以用戶或商品為中心，利用相應(yīng)的標簽信息進行相似度的計算并預(yù)測評分。后4類算法為中間4類算法的部分拓展，進一步考慮了評分信息。以MAE（mean absolute error）和RMSE（root-mean-square error）為評價指標，在兩個MovieLens數(shù)據(jù)集上的測試結(jié)果表明，商品之間的相似度比用戶之間的相似度更可靠，商品標簽也比用戶標簽更有用，而且某些信息的簡單線性組合可以提高推薦質(zhì)量。

推薦系統(tǒng)；協(xié)同過濾；四部圖；協(xié)同過濾標簽

1 引言

協(xié)同過濾（collaborative filtering，CF）是推薦系統(tǒng)[1-4]中應(yīng)用最早并且最成功的算法之一。協(xié)同過濾算法根據(jù)一系列的信息來預(yù)測用戶對商品的喜好。一般來說，這些信息來源于用戶對商品的評分、用戶的檔案和商品屬性等[5]。協(xié)同過濾算法可以分為基于用戶的算法[6-9]和基于商品的算法[10-11]。

考慮測試用戶對測試商品的未知評分，基于用戶的協(xié)同過濾算法首先需要計算測試用戶與其他用戶之間的相似度，而基于商品的協(xié)同過濾算法則需要計算測試商品與其他商品之間的相似度。獲得相似度后，基于用戶的算法會根據(jù)用戶相似度得知與測試用戶相似的其他用戶，然后根據(jù)他們對測試商品的已知評分來預(yù)測未知評分。同樣的，對于基于商品的算法，則根據(jù)測試用戶對相似商品的已知評分來預(yù)測未知評分。

盡管協(xié)同過濾算法已經(jīng)獲得了很大的成功，但是它們的性能仍然受限于數(shù)據(jù)的稀疏性。這樣一來，研究者們向經(jīng)典的協(xié)同過濾框架中添加了一些額外的信息，比如用戶標簽信息和商品標簽信息等。協(xié)同過濾標簽系統(tǒng)允許用戶自由地給商品打標簽，在很大程度上為解決數(shù)據(jù)稀疏性的問題提供了可能性[12]。協(xié)同過濾標簽對于用戶并沒有特別的技術(shù)性要求，這個特點使得它克服了用戶詞匯量有限的問題，擴展了商品間關(guān)系的語義，甚至衍生出多種分類[13]。

近年來，許多基于資源擴散的推薦算法研究得到了廣泛的開展，這些算法在難以管理的稀疏性系統(tǒng)上實現(xiàn)了相對準確的推薦。在基于資源擴散的推薦算法中，用戶或者商品所擁有的資源可以擴散到與其相連接的其他用戶或者商品，資源擴散過程結(jié)束后便可以得到用戶或者商品之間的相似度，進而根據(jù)相似度來預(yù)測未知評分。

本文將評分和標簽等不同類型的信息進行組合，并構(gòu)造了一個四部圖，根據(jù)四部圖中不同信息的組合獲取了10種基于資源擴散的協(xié)同過濾推薦算法，并比較了不同算法的時間復(fù)雜度，進而使用MAE（mean absolute error）和RMSE（root-mean-square error）評價指標來評價不同算法的性能。

在MovieLens數(shù)據(jù)集上的實驗結(jié)果表明：（1）商品之間的相似度比用戶之間的相似度更可靠，而商品標簽也比用戶標簽更有用。（2）某些信息的簡單線性組合可以提高預(yù)測評分的準確度。

2 推薦系統(tǒng)四部圖

定義1（推薦系統(tǒng)四部圖）推薦系統(tǒng)四部圖G是一個五元組，其具體形式為：

其中，U={u1,u2,…,un}是全體用戶構(gòu)成的集合；I= {I1,I2,…,Im}是商品的集合；T={T1,T2,…,Tk}是商品標簽的集合；T′={T1′,T2′,…,Tr′}是用戶標簽的集合；E是四部圖中連接用戶、商品和標簽的所有邊的集合。

Fig.1 Quadripartite graph of recommender system圖1 推薦系統(tǒng)四部圖

一個四部圖中包含了關(guān)于用戶描述、商品內(nèi)容、商品屬性和用戶評分等豐富的信息。同時，四部圖中還包含了用戶、商品以及各種標簽之間的關(guān)系，每一組關(guān)系都可以用兩個鄰接矩陣來描述。一個推薦系統(tǒng)四部圖如圖1所示。

3 協(xié)同過濾算法

下面分別介紹基于用戶和商品的協(xié)同過濾算法。針對N個用戶和M個商品，用戶對商品的評分信息可以用一個N×M的評分矩陣X來描述。X中的每個元素xn,m表示用戶n對商品m的評分，如果xn,m=0表示用戶n對商品m沒有評分。

評分矩陣X的行向量表示形式[14]為：

評分矩陣X也可以用列向量的形式來描述：

其中，列向量im表示所有N個用戶對特定商品的評分。

3.1 基于用戶的協(xié)同過濾算法

基于用戶的協(xié)同過濾算法通過來源于相似用戶的信息來預(yù)測用戶對測試商品的興趣。

如圖2所示，預(yù)測評分可以通過相似用戶的已知評分來獲得，并且如果相似用戶給出的評分越多，則它對預(yù)測商品評分的貢獻就越大。相似用戶可以通過施用閾值或者選擇top-N的方法來確認。

Fig.2 User-based rating prediction圖2 基于用戶的評分預(yù)測

定義2（top-N相似用戶集合）用戶k的top-N相似用戶集合[14]為：

其中，|Su(uk)|=N，su(uk,ua)表示用戶k和用戶a之間的相似度。

本文采用基于資源擴散的相似度指標度量用戶間的相似度。假設(shè)要計算用戶u和用戶v之間的相似度，首先假定用戶v有一個單位的資源。

定義3（商品從用戶獲得的資源）在四部圖中，假設(shè)存在用戶v和商品i，則用戶v分配給商品i的資源為：

其中，k(v)表示四部圖中用戶v的度，如果用戶與商品i在圖中有連線，那么avi=1，否則avi=0。

Fig.3 User-based diffusion process圖3 基于用戶的資源擴散過程

定義4（基于資源擴散的用戶相似度）假設(shè)存在用戶u和用戶v，則用戶間的基于資源擴散的相似度[15]為：

其中，k(i)是圖中商品i的度；k(v)表示用戶v的度；I是商品的全集。如果用戶u對商品i有評分，aui=1，否則aui=0。同理可以得到avi的取值。實際上，suv的本質(zhì)是用戶v通過圖傳給用戶u的資源數(shù)量。

定義了基于資源擴散的相似度后，便可以根據(jù)圖中各個部分的連接情況來計算不同用戶之間的相似度。在一個四部圖中，基于用戶的資源擴散過程一共有3個狀態(tài)：第一個狀態(tài)如圖3（a）所示，是資源擴散的初始狀態(tài)，在這個狀態(tài)中假設(shè)用戶u1被分配了一個單位的初始資源。第二個狀態(tài)如圖3（b）所示，這個狀態(tài)下用戶的初始資源將擴散到與其連接的所有商品和標簽。最后一個狀態(tài)下，資源將從商品和標簽返回與其連接的所有用戶，其過程如圖3（c）所示。需要說明的是，為了保持圖的易讀性，本例假設(shè)只有用戶u1擁有一個單位的資源，在真實的數(shù)據(jù)集中，每一個用戶都有可能擁有一個單位的初始資源數(shù)。

定義5（基于用戶的預(yù)測評分）在得到用戶之間的相似度后，測試用戶u對測試商品i的預(yù)測評分為：

3.2 基于商品的協(xié)同過濾算法

基于商品的協(xié)同過濾算法遵循同樣的思想，只是它計算商品而不是用戶之間的相似度。如圖4所示，測試用戶針對測試商品的未知評分可以通過測試用戶對相似商品的已知評分來獲得。

Fig.4 Item-based rating prediction圖4 基于商品的評分預(yù)測

其中，k(j)表示四部圖中商品j的度；如果用戶u與商品j有連線，那么aju=1，否則aju=0。

定義6（用戶從商品獲得的資源）用戶u從商品j獲得的資源為：

定義7（基于資源擴散的商品相似度）對于圖中的兩個商品i和商品j，它們之間的相似度為：

其中，k(u)是用戶u的度；k(j)為商品j的度；U為用戶的全集。

基于商品的協(xié)同過濾的資源擴散過程也分為3個狀態(tài)。初始狀態(tài)下，假設(shè)只有商品i1擁有一個單位的資源，如圖5（a）所示。接著資源將從商品擴散到與其連接的用戶和標簽，如圖5（b）所示。最后資源將從用戶和標簽返回到與其連接的商品，如圖5（c）所示。

定義8（基于商品的預(yù)測評分）基于商品的協(xié)同過濾算法獲得商品相似度后，測試用戶u對測試商品i的預(yù)測評分為：

3.3 整合相似度

Tso[16]和Zhang[17]等人通過整合不同的相似度明顯提高了推薦的準確性。受其啟發(fā)，本文采用簡單的線性整合方法來整合用戶或者商品相似度。

定義9（整合相似度）假設(shè)有兩個相似度sij和sij′，則整合的相似度為：

其中，λ為取值從0到1之間的可變參數(shù)。

4 基于四部圖的協(xié)同過濾算法

下面詳細說明從四部圖中提取出來的10種協(xié)同過濾算法的具體運行步驟，這些算法來源于圖中不同信息的部分組合。

4.1 基于用戶-商品關(guān)系的算法

基于用戶和商品關(guān)系的算法是經(jīng)典的協(xié)同過濾算法，被分為基于用戶和基于商品的算法，這兩個算法都僅僅考慮了用戶對商品的評分信息而忽略了標簽信息。因為這兩個算法并沒有考慮標簽信息，所以此時的四部圖模型實際上退化為只包含用戶-商品關(guān)系的二部圖。

基于用戶的經(jīng)典協(xié)同過濾算法首先根據(jù)用戶評分信息計算用戶平均評分，然后使用式（4）計算用戶相似度，最后使用式（5）計算預(yù)測評分。對于基于商品的情形，首先根據(jù)評分表計算商品的平均評分，然后分別使用式（7）和式（8）計算商品之間的相似度和預(yù)測評分。

4.2 基于商品標簽-用戶-商品關(guān)系的算法

基于商品標簽-用戶-商品關(guān)系的算法同時考慮了用戶和商品之間以及用戶與整合商品標簽之間的關(guān)系，這兩個關(guān)系構(gòu)成了一個三部圖。本算法的一個例子如下：

Fig.5 Item-based diffusion process圖5 基于商品的資源擴散過程

步驟1輸入評分和電影類型表，如表1所示。

Table 1 User rating and movie type表1 用戶評分和電影類型表

步驟2通過評分表計算每個用戶的平均評分。

步驟3根據(jù)表1的評分以及電影類型信息獲得整合用戶評分類型表，如表2所示。

Table 2 User rating type表2 用戶評分類型表

步驟4根據(jù)表1中的評分信息，使用式（4）計算用戶之間的相似度suv。

步驟5根據(jù)步驟3獲得的用戶評分類型信息，使用式（4）來計算另一個用戶相似度suv′。

步驟6根據(jù)步驟4和步驟5中的兩個用戶相似度，使用式（9）計算整合相似

步驟7根據(jù)步驟2的用戶平均評分以及步驟6的整合相似度，使用式（5）計算預(yù)測評分。

4.3 基于用戶標簽-用戶-商品關(guān)系的算法

基于用戶標簽-用戶-商品關(guān)系的算法同時考慮了用戶標簽和用戶之間以及用戶和商品之間的關(guān)系。在實際應(yīng)用中，用戶標簽的類型有很多，比如用戶的年齡和職業(yè)標簽。下面以用戶職業(yè)標簽為例說明算法實現(xiàn)步驟：

步驟1輸入用戶評分和用戶職業(yè)表，如表3所示。

步驟2根據(jù)表3的評分信息計算用戶的平均評分。

步驟3基于評分表，使用式（4）計算用戶之間的相似度，記為suv。

Table 3 User rating and user occupation type表3 用戶評分和職業(yè)類型表

步驟4根據(jù)表3的用戶職業(yè)類型信息，使用式（4）計算用戶之間的相似度，記為

步驟5根據(jù)步驟3和步驟4中獲得的兩種相似度，使用式（9）計算整合相似度

步驟6根據(jù)步驟2中的平均評分以及步驟5中的整合相似度，使用式（5）計算預(yù)測評分。

4.4 基于商品標簽-商品-用戶關(guān)系的算法

基于商品標簽-商品-用戶關(guān)系的算法考慮了商品與用戶以及商品標簽與商品之間的關(guān)系。算法的具體步驟如下：

步驟1輸入評分和電影類型表，如表1所示。

步驟2根據(jù)表1用戶評分計算商品的平均評分。

步驟3基于表1評分信息，使用式（7）計算商品之間的相似度，記為sij。

步驟4根據(jù)表1中的電影類型信息，使用式（7）計算商品之間的相似度，記為sij′。

步驟5根據(jù)步驟3和步驟4中的兩種商品相似度，使用式（9）計算整合相似度，記為

步驟6根據(jù)步驟2中得到的平均評分以及步驟5中計算出的整合相似度，使用式（8）計算預(yù)測評分。

4.5 基于用戶標簽-商品-用戶關(guān)系的算法

基于用戶標簽-商品-用戶關(guān)系的算法考慮了商品和用戶之間以及整合后的用戶標簽與商品之間的關(guān)系。算法的具體步驟如下：

步驟1輸入用戶評分和職業(yè)表，如表3所示。

步驟2根據(jù)表3評分信息計算商品的平均評分。

步驟3根據(jù)表3的用戶評分以及用戶職業(yè)信息獲取整合后的商品-職業(yè)類型表，如表4所示，這個表說明了看過某個電影的用戶的職業(yè)信息。

步驟4基于評分信息，使用式（7）計算商品之間的相似度，記為sij。

Table 4 Item-occupation type表4 商品-職業(yè)類型表

步驟5根據(jù)表4使用式（7）計算另一個商品之間的相似度，記為

步驟6根據(jù)步驟3和步驟4的兩個商品相似度，使用式（9）計算整合相似度，記為

步驟7根據(jù)步驟2中的平均評分以及步驟6中的整合相似度，使用式（8）計算預(yù)測評分。

4.6 基于用戶標簽-用戶關(guān)系的算法

基于用戶標簽-用戶關(guān)系的算法僅僅考慮了用戶和用戶標簽之間的關(guān)系。算法的具體步驟如下：

步驟1輸入評分和職業(yè)類型表，如表3所示。

步驟2根據(jù)用戶評分表計算用戶的平均評分。

步驟3基于用戶評分使用式（4）計算用戶相似度。

步驟4根據(jù)步驟2中得到的平均評分以及步驟3中的用戶相似度，使用式（5）計算預(yù)測評分。

4.7 基于商品標簽-用戶關(guān)系的算法

基于商品標簽-用戶關(guān)系的算法只考慮了用戶與整合商品標簽之間的關(guān)系。算法的具體步驟如下：

步驟1輸入評分和電影類型表，如表1所示。

步驟2根據(jù)用戶評分表計算用戶的平均評分。

步驟3根據(jù)評分表以及電影類型信息來獲得整合后的用戶評分類型表，如表2所示。

步驟4基于用戶評分類型表，使用式（4）計算用戶之間的相似度。

步驟5根據(jù)步驟2中的平均評分以及步驟4中得到的用戶相似度，使用式（5）計算預(yù)測評分。

4.8 基于商品標簽-商品關(guān)系的算法

基于商品標簽-商品關(guān)系的算法只考慮了商品標簽與商品之間的關(guān)系。算法的具體步驟如下：

步驟1輸入評分和電影類型表，如表1所示。

步驟2根據(jù)用戶評分表計算商品的平均評分。

步驟3根據(jù)表1中的電影類型信息，使用式（7）計算商品之間的相似度。

步驟4根據(jù)步驟2中得到的平均評分以及步驟3中的商品相似度，使用式（8）計算預(yù)測評分。

4.9 基于用戶標簽-商品關(guān)系的算法

基于用戶標簽-商品關(guān)系的算法考慮了用戶標簽與商品之間的關(guān)系。算法的具體步驟如下：

步驟1輸入評分和用戶職業(yè)表，如表3所示。

步驟2根據(jù)用戶評分表計算商品的平均評分。

步驟3根據(jù)用戶評分表以及表3中的用戶職業(yè)信息獲取整合后的商品-職業(yè)類型表，如表4所示，這個表說明了看過某個電影的用戶的職業(yè)信息。

步驟4根據(jù)表4中商品-職業(yè)類型信息，使用式（7）計算商品之間的相似度。

步驟5根據(jù)步驟2中得到的平均評分以及步驟4中的商品相似度，使用式（8）計算預(yù)測評分。

5 算法時間復(fù)雜度分析

在實際的推薦系統(tǒng)應(yīng)用中，各種類型的數(shù)據(jù)量相當(dāng)大，除了考慮算法推薦的準確度外，還應(yīng)當(dāng)考慮算法實施的效率，本文分析了10種協(xié)同過濾算法的時間復(fù)雜度。

考慮一個含有n個用戶、m個商品、k個用戶標簽和r個商品標簽的推薦系統(tǒng)。以基于用戶標簽-用戶-商品的算法為例，首先根據(jù)評分表和用戶標簽信息表計算兩個用戶的相似度矩陣，它們的時間復(fù)雜度分別為O(n2m)和O(n2k)，然后花費O(n2)時間計算整合用戶相似度，接著需要O(mn)+O(n2m)的時間來預(yù)測評分，因此總的時間復(fù)雜度為O(n2m)+O(n2k)。如果考慮商品標簽-商品-用戶算法，根據(jù)評分表和商品標簽分別計算商品相似度矩陣的時間復(fù)雜度為O(nm2)和O(rm2)，計算整合相似度的時間復(fù)雜度為O(m2)，而預(yù)測評分的復(fù)雜度為O(nm2)+O(mn)，因此總的時間復(fù)雜度為O(nm2)+O(rm2)。10種算法的時間復(fù)雜度如表5所示。

從表5中可以看出，對于同樣是基于用戶或者同樣基于商品的算法來說，雖然同時考慮了評分和標簽信息的算法的時間復(fù)雜度更高，但也只呈線性增長，如表5中第三和第一個算法。此外，只考慮了標簽信息的算法和只考慮了評分信息的算法在時間復(fù)雜度上的差距不大，比如表5中第二和第十個算法。在實際實驗中某些標簽的數(shù)量可能遠遠小于用戶或者商品的數(shù)量，因此某些考慮了標簽信息的算法可能會由于標簽類型的不同而在時間復(fù)雜度上有明顯的差距。

Table 5 Time complexity of 10 algorithms表5 10種算法的時間復(fù)雜度

6 實驗結(jié)果與分析

下面通過實驗回答以下4個問題：

（1）哪種算法效果更好？

（2）用戶標簽與商品標簽?zāi)膫€更有用？

（3）用戶相似度與商品相似度哪個可靠？

（4）不同信息的簡單線性整合方法是不是有用？

本實驗運行在兩個MovieLens數(shù)據(jù)集上：數(shù)據(jù)集1包含943個用戶和1 682個電影，數(shù)據(jù)集2包含6 040個用戶和3 952個電影。實驗中的標簽信息來源于用戶描述、商品信息以及從中提取出來的復(fù)合標簽信息。實驗使用leave-one-out的交叉驗證方法來預(yù)測評分，也就是說從原始數(shù)據(jù)集中抽取一個評分作為測試集，而剩下的部分全部作為訓(xùn)練集。實驗采用MAE和RMSE評價了文中的10種算法，并通過調(diào)整參數(shù)λ的值找出了不同算法的最優(yōu)值。

從表6中可以看出，在943×1 682的MovieLens數(shù)據(jù)集上，基于商品標簽-商品-用戶關(guān)系的算法表現(xiàn)最好，此算法在參數(shù)λ等于0.4時具有全局最優(yōu)MAE，在λ等于0.5時具有全局最優(yōu)RMSE，這說明在引入商品標簽信息后，推薦算法的預(yù)測準確度得到了很好的提高。而對于表6中第三、第四和第六個算法，它們的MAE和RMSE最優(yōu)值都在λ等于1時取得，也就是說在沒有引入標簽信息時預(yù)測效果反而更好，這說明了不同信息的簡單線性整合方式并不一定能夠提高預(yù)測評分的準確度。

Table 6 Optimal MAE and RMSE of 10 algorithms on data set 1表610種算法在數(shù)據(jù)集1上的最佳MAE和RMSE

表7的結(jié)果說明在6 040×3 952的數(shù)據(jù)集2上，同樣是基于商品標簽-商品-用戶關(guān)系的算法表現(xiàn)最好，其最優(yōu)MAE和RMSE分別在λ等于0.5和0.6時取得。此外還可以發(fā)現(xiàn)，10種算法在數(shù)據(jù)集2上的表現(xiàn)都要優(yōu)于其在數(shù)據(jù)集1上的表現(xiàn)。

Table 7 Optimal MAE and RMSE of 10 algorithms on data set 2表710種算法在數(shù)據(jù)集2上的最佳MAE和RMSE

表6和表7的前兩種以及最后4種算法都沒有最優(yōu)的λ，因為這些算法都只考慮了一組關(guān)系，沒有進行不同信息的整合，更沒有相似度的整合。

綜合兩個表可以看出，基于商品的推薦算法要明顯優(yōu)于基于用戶的推薦算法，而且商品標簽要比用戶標簽更有用，商品之間相似度也要比用戶之間相似度更可靠。

為了進一步說明中間4種算法MAE和RMSE隨參數(shù)λ的變化趨勢，給出了圖6~圖13。

圖6~圖9說明了不同算法在數(shù)據(jù)集1上的表現(xiàn)，從這4個圖可以看出：隨著λ的增大，基于商品標簽-商品-用戶關(guān)系算法的MAE和RMSE值都會先減小再增大，由此可以得到一個最小值，而其他3個算法的MAE和RMSE值則會一直減小，并在λ等于1.0時取得最小值。此時這3個算法實際上并沒有考慮標簽信息而僅僅考慮了評分信息。

Fig.6 MAE and RMSE of item tag-user-item algorithm on data set 1圖6 基于商品標簽-用戶-商品關(guān)系的算法在數(shù)據(jù)集1上的MAE和RMSE

Fig.7 MAE and RMSE of user tag-user-item algorithm on data set 1圖7 基于用戶標簽-用戶-商品關(guān)系的算法在數(shù)據(jù)集1上的MAE和RMSE

Fig.8 MAE and RMSE of item tag-item-user algorithm on data set 1圖8 基于商品標簽-商品-用戶關(guān)系的算法在數(shù)據(jù)集1上的MAE和RMSE

Fig.9 MAE and RMSE of user tag-item-user algorithm on data set 1圖9 基于用戶標簽-商品-用戶關(guān)系的算法在數(shù)據(jù)集1上的MAE和RMSE

Fig.10 MAE and RMSE of item tag-user-item algorithm on data set 2圖10 基于商品標簽-用戶-商品關(guān)系的算法在數(shù)據(jù)集2上的MAE和RMSE

Fig.11 MAE and RMSE of user tag-user-item algorithm on data set 2圖11 基于用戶標簽-用戶-商品關(guān)系的算法在數(shù)據(jù)集2上的MAE和RMSE

圖10~圖13是算法在數(shù)據(jù)集2上的結(jié)果，從這幾個圖中可以看出，不同算法的MAE和RMSE曲線與其在數(shù)據(jù)集1上的曲線的變化趨勢基本吻合，除了基于商品標簽-商品-用戶關(guān)系算法的MAE和RMSE隨著λ的增大出現(xiàn)先減小再增大的趨勢外，其他3個算法的MAE和RMSE都呈現(xiàn)出遞減的趨勢。

7 結(jié)束語

本文構(gòu)造了關(guān)于用戶評分和標簽信息的四部圖，根據(jù)四部圖中不同部分的組合獲得了10種推薦算法，并分析了不同算法的時間復(fù)雜度。本文使用MAE和RMSE指標評價不同算法的表現(xiàn)，在兩個MovieLens數(shù)據(jù)集上的實驗結(jié)果表明：基于商品標簽-商品-用戶關(guān)系的算法在兩個數(shù)據(jù)集上的表現(xiàn)都優(yōu)于其他算法，商品相似度比用戶相似度更可靠，商品標簽比用戶標簽更有用，而且不同信息的簡單線性整合可以提高預(yù)測評分的準確度。

Fig.12 MAE and RMSE of item tag-item-user algorithm on data set 2圖12 基于商品標簽-商品-用戶關(guān)系的算法在數(shù)據(jù)集2上的MAE和RMSE

Fig.13 MAE and RMSE of user tag-item-user algorithm on data set 2圖13 基于用戶標簽-商品-用戶關(guān)系的算法在數(shù)據(jù)集2上的MAE和RMSE

[1]Bobadilla J,Ortega F,Hernando A,et al.Recommender systems survey[J].Knowledge-Based Systems,2013,46(1): 109-132.

[2]Schafer J B,Frankowski D,Herlocker J,et al.Collaborative filtering recommender systems[M]//The Adaptive Web. Berlin,Heidelberg:Springer,2007:291-324.

[3]Li Yao,Zhang Zhihen,Chen Wenbin,et al.TDUP:an approach to incremental mining of frequent itemsets with threeway-decision pattern updating[J].International Journal of Machine Learning and Cybernetics,2015:1-13.

[4]Zhou Tao,Ren Jie,Medo M,et al.Bipartite network projection and personal recommendation[J].Physical Review E, 2007,76(4):046115.

[5]Hofmann T.Latent semantic models for collaborative filtering [J].ACM Transactions on Information Systems,2004,22 (1):89-115.

[6]Breese J S,Heckerman D,Kadie C.Empirical analysis of predictive algorithms for collaborative filtering[C]//Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence,Madison,USA,Jul 24-26,1998.San Francisco,USA:Morgan Kaufmann Publishers Inc,1998:43-52.

[7]Shi Yue,Larson M,Hanjalic A.Exploiting user similarity based on rated-item pools for improved user-based collaborative filtering[C]//Proceedings of the 3rd ACM Conference on Recommender Systems,New York,Oct 23-25,2009. New York:ACM,2009:125-132.

[8]Jin Rong,Chai J Y,Si Luo.An automatic weighting scheme for collaborative filtering[C]//Proceedings of the 27th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval,Sheffield,UK,Jul 25-29,2004.New York:ACM,2004:337-344.

[9]Zhao Zhidan,Shang Mingsheng.User-based collaborativefiltering recommendation algorithms on Hadoop[C]//Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining,Phuket,Thailand,Jan 9-10,2010.Washington:IEEE Computer Society,2010:478-481.

[10]Mobasher B,Burke R,Bhaumik R,et al.Effective attack models for shilling item-based collaborative filtering systems[C]//Proceedings of the 2005 Web KDD Workshop, Chicago,USA,Aug 21,2005.New York:ACM,2005.

[11]Karypis G.Evaluation of item-based top-nrecommendation algorithms[C]//Proceedings of the 10th International Conference on Information and Knowledge Management,Atlanta, USA,Nov 5-10,2001.New York:ACM,2001:247-254.

[12]Shang Mingsheng,Zhang Zike.Diffusion-based recommendation in collaborative tagging systems[J].Chinese Physics Letters,2009,26(11):250-253.

[13]Hotho A,J?schke R,Schmitz C,et al.Information retrieval in folksonomies:search and ranking[C]//LNCS 4011:Proceedings of the 3rd European Semantic Web Conference, Budva,Montenegro,Jun 11-14,2006.Berlin,Heidelberg: Springer,2006:411-426.

[14]Wang Jun,De Vries A P,Reinders M J T.Unifying userbased and item-based collaborative filtering approaches by similarity fusion[C]//Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval,Seattle,USA,Aug 6-11, 2006.New York:ACM,2006:501-508.

[15]Ou Qing,Jin Yingdi,Zhou Tao,et al.Power-law strengthdegree correlation from a resource-allocation dynamics on weighted networks[J].Physical Review E,2007,75(2): 021102.

[16]Tso-Sutter K H L,Marinho L B,Schmidt-Thieme L.Tagaware recommender systems by fusion of collaborative filtering algorithms[C]//Proceedings of the 2008 ACM Symposium on Applied Computing,Fortaleza,Brazil,Mar 16-20,2008.New York:ACM,2008:1995-1999.

[17]Zhang Zike,Zhou Tao,Zhang Yicheng.Personalized recommendation via integrated diffusion on user-item-tag tripartite graphs[J].Physica A:Statistical Mechanics and Its Applications,2010,389(1):179-186.

MOU Binhao was born in 1992.He is an M.S candidate at Southwest Petroleum University.His research interests include data mining and machine learning.

牟斌皓（1992—），男，四川瀘州人，西南石油大學(xué)碩士研究生，主要研究領(lǐng)域為數(shù)據(jù)挖掘，機器學(xué)習(xí)。

ZHANG Zhiheng was born in 1990.He is a Ph.D.candidate at Southwest Petroleum University.His research interests include data mining and machine learning.

張智恒（1990—），男，重慶梁平人，西南石油大學(xué)博士研究生，主要研究領(lǐng)域為數(shù)據(jù)挖掘，機器學(xué)習(xí)。

張林（1963—），男，四川樂山人，1999年于日本山口大學(xué)獲得博士學(xué)位，現(xiàn)為西南石油大學(xué)教授，主要研究領(lǐng)域為計算機圖像處理，網(wǎng)絡(luò)安全。完成國際合作項目5項，省部級項目2項，其中1項獲國家科學(xué)技術(shù)進步三等獎，1項獲航空航天部重大科技成果二等獎，在國際學(xué)術(shù)期刊和會議上發(fā)表論文10余篇。

MIN Fan was born in 1973.He received the Ph.D.degree from University of Electronic Science and Technology of China in 2003.Now he is a professor and Ph.D.supervisor at Southwest Petroleum University.His research interests include machine learning and cost sensitive research.He has authored over 110 papers in various journals and conferences.

閔帆（1973—），男，重慶人，2003年于四川電子科技大學(xué)獲得博士學(xué)位，現(xiàn)為西南石油大學(xué)教授、博士生導(dǎo)師，主要研究領(lǐng)域為機器學(xué)習(xí)，代價敏感研究。發(fā)表學(xué)術(shù)論文110余篇，其中SCI/EI檢索70余篇，主持國家自然科學(xué)基金等多項科研項目。

Comparison Study of Collaborative Filtering Algorithms Based on Quadripartite Graph*

MOU Binhao1,ZHANG Zhiheng2,ZHANG Lin1,MIN Fan1+
1.School of Computer Science,Southwest Petroleum University,Chengdu 610500,China
2.School of Sciences,Southwest Petroleum University,Chengdu 610500,China
+Corresponding author:E-mail:minfanphd@163.com

A recommender system often collects information about user profiles,item attributes and explicit ratings of users to items,which are further used to make predictions about unknown ratings.This paper constructs a quadripartite graph about the information and acquires ten algorithms from different parts of the graph.The first two algorithms are the classical user-and item-based collaborative filtering and only take into account the rating information. Four more algorithms take user or item as center and use relevant tags to compute user or item similarity.To extend the previous four algorithms,four more algorithms take into account the user-item relationship along with tag information.This paper compares the time complexity of different algorithms on two MovieLens data sets,and uses MAE(mean absolute error)and RMSE(root-mean-square error)metrics to evaluate the performance of different algorithms.The experimental results demonstrate that the similarity of items is more reliable than that of users,and item tags are more useful than user tags.Besides,some simple linear integrations of different information are capable of enhancing recommendation performance.

was born in 1963.He

the Ph.D.degree from Yamaguchi University in 1999.Now he is a professor at Southwest Petroleum University.His research interests include image processing and network security.

A

TP181

*The National Natural Science Foundation of China under Grant No.61379089(國家自然科學(xué)基金);the Natural Science Foundation of Department of Education of Sichuan Province under Grant No.16ZA0060(四川省教育廳自然科學(xué)基金).

Received 2016-04,Accepted 2016-06.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-06-23,http://www.cnki.net/kcms/detail/11.5602.TP.20160623.1139.012.html

Key words:recommender system;collaborative filtering;quadripartite graph;collaborative filtering tag