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

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

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

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

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

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

3 協(xié)同過濾算法

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

評(píng)分矩陣X的行向量表示形式[14]為：

評(píng)分矩陣X也可以用列向量的形式來描述：

其中，列向量im表示所有N個(gè)用戶對(duì)特定商品的評(píng)分。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 整合相似度

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

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

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

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

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

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

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

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

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

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

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

步驟1輸入評(píng)分和電影類型表，如表1所示。

Table 1 User rating and movie type表1 用戶評(píng)分和電影類型表

步驟2通過評(píng)分表計(jì)算每個(gè)用戶的平均評(píng)分。

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

Table 2 User rating type表2 用戶評(píng)分類型表

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟1輸入評(píng)分和電影類型表，如表1所示。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟3基于用戶評(píng)分使用式（4）計(jì)算用戶相似度。

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

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

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

步驟1輸入評(píng)分和電影類型表，如表1所示。

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

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

步驟4基于用戶評(píng)分類型表，使用式（4）計(jì)算用戶之間的相似度。

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

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

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

步驟1輸入評(píng)分和電影類型表，如表1所示。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

下面通過實(shí)驗(yàn)回答以下4個(gè)問題：

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

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

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

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

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

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

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上，同樣是基于商品標(biāo)簽-商品-用戶關(guān)系的算法表現(xiàn)最好，其最優(yōu)MAE和RMSE分別在λ等于0.5和0.6時(shí)取得。此外還可以發(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)的λ，因?yàn)檫@些算法都只考慮了一組關(guān)系，沒有進(jìn)行不同信息的整合，更沒有相似度的整合。

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

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

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

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

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

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

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

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

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

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

7 結(jié)束語

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

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

Fig.13 MAE and RMSE of user tag-item-user algorithm on data set 2圖13 基于用戶標(biāo)簽-商品-用戶關(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)域?yàn)閿?shù)據(jù)挖掘，機(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)域?yàn)閿?shù)據(jù)挖掘，機(jī)器學(xué)習(xí)。

張林（1963—），男，四川樂山人，1999年于日本山口大學(xué)獲得博士學(xué)位，現(xiàn)為西南石油大學(xué)教授，主要研究領(lǐng)域?yàn)橛?jì)算機(jī)圖像處理，網(wǎng)絡(luò)安全。完成國際合作項(xiàng)目5項(xiàng)，省部級(jí)項(xiàng)目2項(xiàng)，其中1項(xiàng)獲國家科學(xué)技術(shù)進(jìn)步三等獎(jiǎng)，1項(xiàng)獲航空航天部重大科技成果二等獎(jiǎng)，在國際學(xué)術(shù)期刊和會(huì)議上發(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)域?yàn)闄C(jī)器學(xué)習(xí)，代價(jià)敏感研究。發(fā)表學(xué)術(shù)論文110余篇，其中SCI/EI檢索70余篇，主持國家自然科學(xué)基金等多項(xiàng)科研項(xiàng)目。

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