基于網絡和標簽的混合推薦算法

張新猛，蔣盛益，李 霞，張倩生

廣東外語外貿大學 思科信息學院，廣州 510006

1 引言

隨著Internet的迅速發展，World Wide Web信息呈指數級增長態勢，新內容的快速增長帶來信息超載問題：過多的信息使用戶難以獲取個人想要的內容，反而使信息使用效率降低。搜索技術允許人們通過關鍵字在海量數據中搜索想要的信息，但是沒有考慮用戶的個性化需求，為所有用戶提供了相同的搜索結果。個性化推薦采用知識發現技術根據用戶的喜好為用戶推薦個性化的信息，是一種解決信息過載的有效工具。目前幾乎所有大型的電子商務系統，如Amazon（圖書推薦）、CDNOW（音樂推薦）、Netflix（電影推薦）等，都不同程度地使用了各種形式的推薦系統。個性化推薦系統已經給電子商務領域帶來巨大的商業利益。據VentureBeat統計，Amazon的推薦系統為其提供了35%的商品銷售額[1]。目前，主要的個性化推薦方法有基于規則的推薦、協同過濾推薦（Collaborative Filtering，CF）、基于內容的推薦（Content-Based）、混合推薦系統以及基于網絡（Network-Based）的推薦等。

近年來，網絡理論成為理解和分析復雜系統有效的工具，節點代表實體，邊代表實體之間的聯系。二分圖是復雜網絡中的一種，包含兩類節點，只有不同類別的節點之間才有邊相連接。周濤首先提出依賴用戶與項目之間的網絡結構關系的推薦算法[2]，并進一步討論了減少流行項目的初始資源配置，能夠進一步提升推薦精度和個性化程度[3]。文獻[4]考慮用戶與項目的度的相關性，在資源分配模型中引入用戶與項目的度乘積的λ指數，λ指數為可調參數[4]。文獻[5]等在初始資源分配時同時考慮用戶的度及用戶的興趣，以用戶選擇的項目的平均度定義為用戶的興趣，根據用戶的興趣與項目的度的距離進行初始資源的分配，強化了流行項目的影響，同時弱化了非流行項目的影響。張新猛等[6]考慮了二分圖邊權，按照邊權重比例進行資源分配，高評分項目得到優先推薦，推薦結果個性化程度更高。

隨著Web2.0的快速發展，社會化標簽系統[7]（又稱為協同標簽系統）已成為Web2.0一種主要應用，它允許用戶用隨意的單詞或短語標記喜愛的資源（URL、電影、圖片、音樂等），這些短語和單詞就稱為Tag，反映了用戶的偏好。最近，不少研究將社會化標簽應用到推薦系統中[8]，文獻[9]應用標簽系統，構建用戶-標簽-項目關系，在一定程度上解決了冷啟動問題。

不同的推薦算法均存在各自的缺陷，把多種推薦算法進行結合，提出混合推薦算法，具有比獨立的推薦算法更好的準確率。Melville等[10]利用基于文本分析的方法在協同過濾系統中用戶的打分向量上增加一個附加打分，附加分高的用戶的信息優先推薦給其他用戶。Yoshii等[11]利用協同過濾算法和音頻分析技術進行音樂推薦。本文提出基于網絡和標簽的混合推薦算法，采用TF-IDF（Term Frequency-Inverse Document Frequency）方法和支持度兩種方法構建用戶對標簽的偏好模型，然后對基于網絡推薦算法模型與兩種用戶偏好模型進行線性組合推薦。在標準數據集MovieLens上進行了測試，實驗結果表明，該算法在推薦精度、個性化程度、用戶偏好程度等方面均有改進。

2 相關研究

2.1 基于網絡的推薦模型

文獻[2]首先提出基于二部分圖的推薦算法（Network-Based Inference，NBI），用戶與項目構成二分圖，假設每個項目均有一定的初始資源，通過用戶-項目之間的邊將資源平均地分配給用戶，反過來，每個用戶又將自己所有分到的資源再次通過二部分圖邊平均地分配給它們所參與的項目，得到項目之間的資源推薦關系，然后根據用戶已選擇的項目對未選擇項目進行評分，將評分最高的項目推薦給用戶?？紤]一個由m個用戶n個項目所構成的二部分圖，用戶集U={U1，U2，…，Um}，項目集I={I1，I2，…，In}，二部分圖表示為G(U，I，E)，E表示二部分圖的邊，即連接用戶和項目的邊。項目j分配給項目i的資源計算公式為：

其中，ail的值為：

k(Ul)表示用戶l的度，即用戶l連接到項目的邊數。k(Ij)表示項目j的度，即項目j連接到用戶的邊數。

用戶Ui對項目Ij預測評分模型為：

其中項目Ij為用戶Ui未選擇的項目，1≤j≤n，aji=0。

2.2 基于TF-IDF的項目表征

在基于內容的推薦中，最常用的用戶興趣模型構建方法是TF-IDF[12]。TF-IDF是一種統計方法，用以評估字詞對于一個文件集或一個語料庫中的其中一份文件的重要程度。字詞的重要性隨著它在文件中出現的次數成正比增加，但同時會隨著它在語料庫中出現的頻率成反比下降。TF表示詞條在文檔d中出現的頻率，IDF表示反文檔頻率，以總文件數目除以包含該詞語文件的數目，再將得到的商取對數得到。

基于內容推薦根據用戶已選擇的項目，對項目提取關鍵詞，用關鍵詞的TF-IDF值所構成的向量表示用戶配置文件，對候選項目同樣采用項目關鍵詞的TF-IDF值所構成的向量來表示[12]，采用如夾角余弦等方法計算用戶與項目的相似度，將相似度最高的項目推薦給用戶。該方法通常應用于內容特征較多的文件推薦，比如，Fab是一個網頁推薦系統，系統中用一個網頁中最重要的100個關鍵詞來表征這個網頁。Syskill和Webert系統用128個信息量最多的詞表示一個文件。

3 基于網絡和標簽的混合推薦模型

3.1 基于標簽TF-IDF值的用戶偏好模型

項目標簽不僅可以為每個資源進行更準確的特征描述，同時也能用于構建用戶的偏好模型，進而實現更準確的個性化資源推薦[14]。本文以項目的標簽作為項目的內容特征，采用用戶已選擇項目標簽的TF-IDF值表示用戶的偏好。所有項目的標簽構成標簽集T={T1，T2，…，Tr}，用戶Ui選擇的項目集合表示為I(Ui)={Ij|1≤j≤n}，項目Ij具有標簽集合表示為T(Ij)={Tk|1≤k≤r}，用戶Ui選擇的項目所有標簽構成偏好標簽集T(Ui)={Tk|Tk∈T(Ij)，Ij∈I(Ui)} ，以向量 vi=(vi1，vi2，…，vik) 表示用戶Ui偏好配置文件，其中每個分量vik是用戶Ui已選擇標簽Tk的TF-IDF值，表示用戶Ui對標簽Tk的偏好程度，計算公式定義為：

其中tfik為用戶Ui選擇標簽Tk的頻率，idfk為標簽Tk的反文檔頻率，tfik計算公式定義為：

nik為用戶i所選項目中標簽Tk出現的次數，tfik表示用戶Ui所選項目中標簽Tk出現的頻率，顯然頻率越大，用戶對該標簽的偏好程度越大。

idfk表示標簽Tk在項目中出現的普遍程度，值越小表示該標簽越普遍，定義為：

其中n為項目總數，nk為包含標簽Tk的項目數量。

可見標簽Tk的在某一用戶Ui所選項目中出現頻率越高，而該標簽在項目中出現的頻率越低，用戶Ui對標簽的權重越大，即對該標簽的偏好程度越大。

在分類屬性聚類算法中，采用對象與簇在各屬性上的平均相似度作為對象與簇的相似度[13]，本文借鑒此方法，取項目中所有標簽對應的用戶偏好配置文件中權重平均值作為用戶對項目的偏好，用戶Ui對項目Ij基于標簽TF-IDF的偏好表達式為：

|T(Ij)|表示項目Ij的標簽集合T(Ij)的元素個數。

圖1為一個用戶-項目-標簽關系示意圖，用戶集U={U1，U2}，項目集I={I1，I2，I3}，標簽集T={T1，T2，T3，T4}，用戶U1的項目集I(U1)={I1，I2}，用戶U2的項目集I(U2)={I2，I3}，項目I1的標簽集T(I1)={T1，T3}，項目I2的標簽集T(I2)={T1，T3，T4}，項目I3的標簽集T(I3)={T2，T3，T4}，用戶U1的標簽集T(U1)={T1，T3，T4}，用戶U2的標簽集T(U2)={T1，T2，T3，T4} 。 用 戶 對 各 標 簽 的TF值 分 別 為tf11=2/5，tf13=2/5，tf14=1/5，tf21=1/6，tf22=1/6，tf23=1/3，tf24=1/3，各標簽IDF值分別為idf1=ln(3/2+0.01)，idf2=ln(3/1+0.01)，idf3=ln(3/3+0.01)，idf4=ln(3/2+0.01)。用戶U1對項目I3的預測偏好值P(U1，I3)=(0+tf13×idf3+tf14×idf4)/3=(2/5×ln1.001+1/5×ln1.501)/3=0.027 208 704。用戶U2對項目I1的預測偏好值P(U2，I1)=(tf21×idf1+tf23×idf3)/2=(1/6×ln 1.501+1/3×ln1.01)/2=0.035 502 685。

圖1 用戶-項目-標簽

3.2 基于標簽支持度的用戶偏好模型

用戶對標簽TF值或TFIDF值越大表示對該標簽的偏好程度越大，但對于一些非主流項目，該類項目總數量比較少，即使用戶對此類項目偏好程度很高，用戶選擇此類項目的比例仍然很低，因此雖然該項目的IDF值較高，由于其TF值低，無法獲得較高的TFIDF值。CBUID算法[15]通過計算對象分類屬性值在簇中的出現的頻率計算對象與簇之間的相似度，計算方法為該屬性值在簇中出現的次數除以簇的對象個數。受此啟發，將用戶選擇包含該標簽的項目個數與該類項目總數的比值作為用戶對該標簽的偏好的一種度量，這里稱為用戶對該標簽支持度。顯然，比值越大，用戶對該類標簽的興趣越大，該度量方式更注重用戶的偏好，可以將更多非主流項目推薦給用戶。用戶Ui對標簽Tk的支持度表達式為：

nik為用戶Ui選擇項目中包含該標簽Tk的項目數目，Nk為具有標簽Tk的項目總數目，支持度Sik表示用戶Ui選擇具有標簽Tk的項目數占該類別項目總數的比值，若用戶選擇了所有具有某類標簽的項目，達到最大值1，若用戶沒有選擇任何具有該標簽的項目，達到最小值0，顯然該值的范圍為[0，1]，比值越大，表示該用戶對該類別項目偏好程度越大。

如項目總數為1 000，用戶選擇的總項目數為300，選擇A類項目的數量為10，A類項目的總數為20，選擇B類項目的數量為20，B類項目的總數為100，經過計算用戶對兩類項目的TFIDF值是相同的，而A類項目支持度為10/20=0.5，B類項目支持度為20/100=0.2，而實際應用中，B類項目比較流行，用戶可以很方便地獲取，而A類項目，用戶卻難以發現，因此推薦給用戶A類項目，更能獲得用戶喜愛。

一個項目包含多個標簽，參照文獻[15]，取用戶對項目中包含的標簽的支持度的平均值作為用戶對項目的支持度，用戶Ui對項目Ij的支持度表示為：

|T(Ij)|為項目Ij包含的標簽個數，用戶Ui對項目Ij的支持度取項目包含標簽的支持度的平均值。如圖1，N1=2，N2=1，N3=3，N4=2，n11=1，n12=0，n13=2，n14=1，n21=1，n22=1，n23=2，n24=2。SUP(U1，I3)=(0+2/3+1/2)/3=7/18 ，SUP(U2，I1)=(0+1/2+2/3)/2=7/12 。

3.3 基于網絡和標簽混合推薦模型

推薦算法混合的形式有多種，可以是串行方式，首先用一種推薦技術產生一個較為粗略的候選結果，在此基礎上使用第二種推薦技術進一步精確地推薦，也可以將多種推薦技術的計算結果加權混合產生推薦。采用串行方式，需要分別運行推薦算法，時間復雜度為兩種推薦算法的復雜度和，而加權混合方式，多種推薦算法可在相同的遍歷中同時進行運算，時間開銷較小。本文算法采用加權混合方式，在基于網絡的評分基礎上，增加兩種用戶偏好值的附加分量。用戶U i對項目Ij的預測評分表達式為：

其中權重x1+x2+x3=1，其值由各模型的精確性及經驗值得出。本文通過改變公式（9）中的x1、x2、x3的值在數據集MovieLens上進行測試，在三者的比值為1∶1∶1時，取得較好的推薦效果，本文測試結果均在此權重組合下得到的，但并不代表三種模型在推薦中的作用相同。事實上，本混合推薦算法中以基于網絡的推薦為主，另外兩種用戶偏好值在數據集MovieLens上運行結果都要小于基于網絡推薦的評分，相當于在基于網絡推薦評分上增加一個附加分。本文在實驗中針對公式（10）分別統計了所有用戶項目預測中F(Ui，Ij)，SUP(Ui，Ij)，P(Ui，Ij)各項的平均值，三種模型平均值的比值約為50∶33∶17，即在最后對項目的預測分數中三種模型預測結果所占比重，表示了事實上三種模型的重要程度，比重越大，重要程度越高。

4 算法描述

算法主要有三個步驟：第一步統計用戶及項目的相關統計信息，構建基于TF-IDF和支持度的偏好模型；第二步計算項目間資源分配矩陣；第三步根據基于網絡和標簽的混合推薦模型為某用戶計算未選擇項目的預測評分。

第一步構建用戶基于標簽的偏好模型。

輸入：用戶集U，項目集I，訓練集T

輸出：用戶偏好配置文件，用戶標簽支持度SUP(Ui，Tk)（1）ForeachtinT

（2）統計每個用戶Ul的度，記為k(Ul)

（3）統計每個項目Ii的度，記為k(Ii)

（4）得到每個項目Ii所連接用戶集合，記為U(Ii)

（5）統計用戶Ul選擇標簽Tk的次數nlk

（6）統計標簽Tk被選擇總次數Nk

（7）Endfor

（8）計算用戶各標簽的TF-IDF值，得到用戶偏好配置文件

（9）計算用戶對各標簽的支持度SUP(Ul，Tk)

第二步計算項目間資源分配矩陣。

輸入：用戶集U，項目集I，訓練集T

輸出：資源分配矩陣W=(wij)n×n

（10）ForeachIiinI

（11）ForeachIjinI

（12）wij=0

（13） ForeachUlinU(Ii)∩U(Ij)

（14）wij=wij+ail×ajl/k(Ul)

（15） Endfor

（16）wij=wij/k(Ij)

（17）Endfor

（18）Endfor

第三步為某個用戶計算所有未選擇項目預測評分。

輸入：用戶Ul，項目集I，資源分配矩陣W=(wij)n×n

輸出：用戶Ul對未選擇項目的評分集合

（19）ForeachIiinI

（20）F(Ul，Ii)=0

（21）ForeachIjinI(Ul)

（22）F(Ul，Ii)=F(Ul，Ii)+wij×alj

（23）Endfor

（24）ForeachTkinT(Ii)

（25）P(Ul，Ii)=P(Ul，Ii)+vlk

（26）SUP(Ul，Ii)=SUP(Ul，Ii)+Slk

（27）Endfor

（28）P(Ul，Ii)=P(Ul，Ii)/|T(Ii)|

（29）SUP(Ul，Ii)=SUP(Ul，Ii)/|T(Ii)|

（30）score(Ul，Ii)=x1F(Ul，Ii)+x2SUP(Ul，Ii)+x3P(Ul，Ii)

（31）Endfor

|I|表示集合I的長度；最后再取評分最高top-N個項目推薦給用戶Ul。

從算法流程中可以看出，兩種用戶對標簽的偏好模型的構建都穿插在NBI算法流程中，主要增加的行有5～6及24～29，并沒有過多額外的時間開銷。

5 實驗分析

5.1 實驗數據

采用標準數據集MovieLens（http：//www.grouplens.org）檢測算法的有效性。MovieLens數據集包含1 682部電影，943個用戶，共有100 000條用戶對電影的評分。評分在1～5之間，1表示最不喜歡，5表示最喜歡，其中評分在3分及以上的記錄有82 520條，如果評分至少3分表示用戶推薦該電影，將3分及以上的評分記錄構建“用戶-電影”二部分圖，那么“用戶-電影”二部分圖共有82 520條邊。為了便于對比實驗，按照文獻[2]中方法將數據集隨機選取其中90%作為訓練集，剩余10%作為測試集。本文實驗每次隨機劃分數據集后，分別用NBI和本文算法進行評分預測，進行10次取平均值比較推薦結果，因此實驗結果是在訓練集與測試集都完全相同的情況下進行的對比測試。

個性化推薦結果的評價通常從精確度和個性化程度進行評價[3]，本文通過推薦精度和召回率驗證推薦精確度，利用命中項目平均度及多樣性驗證推薦的個性化程度。給定了推薦列表的長度L，系統把排名最靠前的L個項目推薦給用戶，觀察所推薦的L個項目，假設二部圖邊Ui-Ij出現在測試集中，如果Ij為所推薦的L個項目之一，那么稱項目Ij被算法命中。本文分別在給定推薦列表長度L為5、10、20、50、100的情況下，對算法進行了實驗和討論。

5.2 推薦精度

推薦精度和召回率是評價推薦結果精確度的兩個度量值，精度是推薦結果中命中項目數量與推薦項目總數的比值，召回率是推薦結果命中項目數量與測試集中用戶實際選擇的項目數量的比值。

召回率計算公式為：

精度計算公式為：

L為推薦長度，本文采用Nr/(Lmt)算平均精度，即命中項目的總數與總推薦數的比值。

表1為文本算法與NBI算法在不同推薦長度下，各種算法組合情況下命中項目總數、精度及召回率，其中NBIT、NBIS、NBITS分別表示NBI與標簽支持度組合、NBI與TF-IDF組合、NBI與標簽支持度及TF-IDF組合。從表1中可知，NBITS算法效果最好，NBIT及NBIS也均優于NBI算法。

5.3 個性化程度

除了測量推薦結果精度，推薦結果的個性化程度也是評價推薦效果的一個有意義的指標，比如推薦給用戶10部電影，其中8部是非常流行的，而另外2部是適合用戶偏好的，流行的電影通?？梢栽诟嗟膱鏊玫酵扑]（比如電視、網絡、電影院等），而符合用戶偏好的非流行電影卻難以被用戶發現，因此這2部非流行的電影對用戶的意義更大。為測試推薦結果個性化程度，分別采用推薦項目流行度和多樣化兩種方法進行測量。

項目流行度以推薦項目的平均度來測量，項目的度為項目被用戶選擇的次數，度越大，說明項目越流行，將流行項目推薦給用戶，雖然能得到用戶認可，推薦命中率提高，但推薦結果個性化程度較低。給定推薦長度為L，所有被推薦項目的平均度作為流行度的測量標準，推薦項目的平均度越小，在一定程度上反映推薦項目更考慮了用戶偏好。

推薦結果多樣性指為不同用戶推薦結果差異程度，采用用戶間推薦項目列表的漢明距離評定推薦結果多樣性，設用戶Ui與Uj推薦項目列表重疊項目的數量Q、L為推薦項目個數，其漢明距離為Hij=1-Q/L。通常來講，漢明距離越大推薦結果個性化程度越高，計算所有用戶之間的漢明距離并取平均值作為評價推薦結果個性化的強度，記為S=＜Hij＞，若為所有用戶推薦相同的項目，S=0，若所有用戶推薦項目列表沒有相同的項目，則S=1。圖2是本文算法和基于網絡的推薦算法NBI在不同推薦列表長度情況下的命中項目平均度，顯然NBITS的平均度較小，表明更考慮了用戶的偏好，而不是將最流行的項目推薦給用戶。圖3是各算法在不同推薦長度下用戶間平均漢明距離，NBITS算法漢明距離較大，表明NBITS算法為不同用戶推薦了更多不同的項目。NBIT命中項目平均度低于NBIS，且NBIT命中項目漢明距離高于NBIS，說明TF-IDF方法對提高個性化程度更明顯。

圖2 典型推薦長度下命中項目平均度

表1 典型推薦列表長度的命中項目總數、精度及召回率

圖3 典型推薦長度下推薦項目用戶間平均漢明距離

6 結束語

NBI算法根據用戶-項目二分圖結構計算項目之間的推薦程度，根據用戶已選擇項目計算未選擇項目的推薦程度獲取推薦列表，核心思想采用了項目與項目之間的關系。而本文算法在NBI算法的基礎上，根據用戶選擇項目的標簽信息，分別采用TF-IDF和標簽支持度的方法構建用戶偏好模型，根據待預測項目的標簽計算用戶對項目的偏好程度，并與NBI推薦模型進行線性組合推薦。經過在數據集上測試證明，在推薦精度、個性化程度等方面均比單純的基于網絡的推薦均有所改進。但本文對各模型的加權組合方法尚待進一步探討，各模型權重需要一種更為科學的方法確定，同時本文算法需要進一步在更多數據集，尤其大數據集上進行測試驗證。

[1]劉建國，周濤，汪秉宏.個性化推薦系統的研究進展[J].自然科學進展，2009，19（1）：1-15.

[2]Zhou Tao，Ren Jie，Medo M，et al.Bipartite network projection and personal recommendation[J].Physical Review E，2007，76（4）：6116-6123.

[3]Zhou Tao，Jiang Luoluo，Su Riqi，et al.Effect of initial configuration on network-based recommendation[J].Europhys Lett，2008，81（5）：8004-8008.

[4]Pan Xin，Deng Guishi，Liu Jianguo.Weighted bipartite network and personalized recommendation[J].Physics Procedia，2010，3（5）：1867-1876.

[5]Liu Jianguo，Zhou Tao，Wang Binghong，et al.Effects of user tastes on personalized recommendation[J].International Journal of Modern Physics C，2009，20（12）：1925-1932.

[6]張新猛，蔣盛益.基于加權二部圖的個性化推薦算法[J].計算機應用，2012，32（3）：654-657.

[7]Scott A G，Bernardo A H.Usage patterns of collaborative tagging systems[J].Journal of Information Science，2006，32（2）：198-208.

[8]Zhang Zike，Zhou Tao，Zhang Yicheng.Tag-aware recommendersystems：a state-of-the-artsurvey[J].Journalof Computer Science and Technology，2011，26（5）：767-777.

[9]Zhang Zike，Liu Chuang，Zhang Yichen，et al.Solving the cold-start problem in recommender systems with social tags[J].Europhysics Letters，2010，92（2）：8002-8008.

[10]Melville P，Mooney R J，Nagarajan R.Content-boosted collaborative filtering for improved recommendations[C]//Proceedings of the 18th National Conference on Artificial Intelligence，Edmonton，2002：187-192.

[11]Yoshii K，Goto M，Komatani K，et al.An efficient hybrid music recommender system using an incrementally trainable probabilistic generative model[J].IEEE Transactions on Audio Speech and Language Processing，2008，16（2）：435-447.

[12]王國霞，劉賀平.個性化推薦系統綜述[J].計算機工程與應用，2012，48（7）：70-80.

[13]Pazzani M J，Billsus D.Content-based recommendation systems[M]//The Adaptive Web：Methods and Strategies of Web Personalization.Berlin，Heidelberg：Springer-Verlag，2007：325-341.

[14]劉斌，楊帆.支持多維標簽云的移動餐廳推薦系統仿真研究[J].計算機工程與應用，2012，48（4）：240-243.

[15]Jiang Shengyi，Song Xiaoyu，Wang Hui，et al.A clusteringbased method for unsupervised intrusion detections[J].Pattern Recognition Letters，2006，27（7）：802-810.