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

廣東外語(yǔ)外貿(mào)大學(xué) 思科信息學(xué)院，廣州 510006

1 引言

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

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

隨著Web2.0的快速發(fā)展，社會(huì)化標(biāo)簽系統(tǒng)[7]（又稱(chēng)為協(xié)同標(biāo)簽系統(tǒng)）已成為Web2.0一種主要應(yīng)用，它允許用戶(hù)用隨意的單詞或短語(yǔ)標(biāo)記喜愛(ài)的資源（URL、電影、圖片、音樂(lè)等），這些短語(yǔ)和單詞就稱(chēng)為T(mén)ag，反映了用戶(hù)的偏好。最近，不少研究將社會(huì)化標(biāo)簽應(yīng)用到推薦系統(tǒng)中[8]，文獻(xiàn)[9]應(yīng)用標(biāo)簽系統(tǒng)，構(gòu)建用戶(hù)-標(biāo)簽-項(xiàng)目關(guān)系，在一定程度上解決了冷啟動(dòng)問(wèn)題。

不同的推薦算法均存在各自的缺陷，把多種推薦算法進(jìn)行結(jié)合，提出混合推薦算法，具有比獨(dú)立的推薦算法更好的準(zhǔn)確率。Melville等[10]利用基于文本分析的方法在協(xié)同過(guò)濾系統(tǒng)中用戶(hù)的打分向量上增加一個(gè)附加打分，附加分高的用戶(hù)的信息優(yōu)先推薦給其他用戶(hù)。Yoshii等[11]利用協(xié)同過(guò)濾算法和音頻分析技術(shù)進(jìn)行音樂(lè)推薦。本文提出基于網(wǎng)絡(luò)和標(biāo)簽的混合推薦算法，采用TF-IDF（Term Frequency-Inverse Document Frequency）方法和支持度兩種方法構(gòu)建用戶(hù)對(duì)標(biāo)簽的偏好模型，然后對(duì)基于網(wǎng)絡(luò)推薦算法模型與兩種用戶(hù)偏好模型進(jìn)行線(xiàn)性組合推薦。在標(biāo)準(zhǔn)數(shù)據(jù)集MovieLens上進(jìn)行了測(cè)試，實(shí)驗(yàn)結(jié)果表明，該算法在推薦精度、個(gè)性化程度、用戶(hù)偏好程度等方面均有改進(jìn)。

2 相關(guān)研究

2.1 基于網(wǎng)絡(luò)的推薦模型

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

其中，ail的值為：

k(Ul)表示用戶(hù)l的度，即用戶(hù)l連接到項(xiàng)目的邊數(shù)。k(Ij)表示項(xiàng)目j的度，即項(xiàng)目j連接到用戶(hù)的邊數(shù)。

用戶(hù)Ui對(duì)項(xiàng)目Ij預(yù)測(cè)評(píng)分模型為：

其中項(xiàng)目Ij為用戶(hù)Ui未選擇的項(xiàng)目，1≤j≤n，aji=0。

2.2 基于TF-IDF的項(xiàng)目表征

在基于內(nèi)容的推薦中，最常用的用戶(hù)興趣模型構(gòu)建方法是TF-IDF[12]。TF-IDF是一種統(tǒng)計(jì)方法，用以評(píng)估字詞對(duì)于一個(gè)文件集或一個(gè)語(yǔ)料庫(kù)中的其中一份文件的重要程度。字詞的重要性隨著它在文件中出現(xiàn)的次數(shù)成正比增加，但同時(shí)會(huì)隨著它在語(yǔ)料庫(kù)中出現(xiàn)的頻率成反比下降。TF表示詞條在文檔d中出現(xiàn)的頻率，IDF表示反文檔頻率，以總文件數(shù)目除以包含該詞語(yǔ)文件的數(shù)目，再將得到的商取對(duì)數(shù)得到。

基于內(nèi)容推薦根據(jù)用戶(hù)已選擇的項(xiàng)目，對(duì)項(xiàng)目提取關(guān)鍵詞，用關(guān)鍵詞的TF-IDF值所構(gòu)成的向量表示用戶(hù)配置文件，對(duì)候選項(xiàng)目同樣采用項(xiàng)目關(guān)鍵詞的TF-IDF值所構(gòu)成的向量來(lái)表示[12]，采用如夾角余弦等方法計(jì)算用戶(hù)與項(xiàng)目的相似度，將相似度最高的項(xiàng)目推薦給用戶(hù)。該方法通常應(yīng)用于內(nèi)容特征較多的文件推薦，比如，F(xiàn)ab是一個(gè)網(wǎng)頁(yè)推薦系統(tǒng)，系統(tǒng)中用一個(gè)網(wǎng)頁(yè)中最重要的100個(gè)關(guān)鍵詞來(lái)表征這個(gè)網(wǎng)頁(yè)。Syskill和Webert系統(tǒng)用128個(gè)信息量最多的詞表示一個(gè)文件。

3 基于網(wǎng)絡(luò)和標(biāo)簽的混合推薦模型

3.1 基于標(biāo)簽TF-IDF值的用戶(hù)偏好模型

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

其中tfik為用戶(hù)Ui選擇標(biāo)簽Tk的頻率，idfk為標(biāo)簽Tk的反文檔頻率，tfik計(jì)算公式定義為：

nik為用戶(hù)i所選項(xiàng)目中標(biāo)簽Tk出現(xiàn)的次數(shù)，tfik表示用戶(hù)Ui所選項(xiàng)目中標(biāo)簽Tk出現(xiàn)的頻率，顯然頻率越大，用戶(hù)對(duì)該標(biāo)簽的偏好程度越大。

idfk表示標(biāo)簽Tk在項(xiàng)目中出現(xiàn)的普遍程度，值越小表示該標(biāo)簽越普遍，定義為：

其中n為項(xiàng)目總數(shù)，nk為包含標(biāo)簽Tk的項(xiàng)目數(shù)量。

可見(jiàn)標(biāo)簽Tk的在某一用戶(hù)Ui所選項(xiàng)目中出現(xiàn)頻率越高，而該標(biāo)簽在項(xiàng)目中出現(xiàn)的頻率越低，用戶(hù)Ui對(duì)標(biāo)簽的權(quán)重越大，即對(duì)該標(biāo)簽的偏好程度越大。

在分類(lèi)屬性聚類(lèi)算法中，采用對(duì)象與簇在各屬性上的平均相似度作為對(duì)象與簇的相似度[13]，本文借鑒此方法，取項(xiàng)目中所有標(biāo)簽對(duì)應(yīng)的用戶(hù)偏好配置文件中權(quán)重平均值作為用戶(hù)對(duì)項(xiàng)目的偏好，用戶(hù)Ui對(duì)項(xiàng)目Ij基于標(biāo)簽TF-IDF的偏好表達(dá)式為：

|T(Ij)|表示項(xiàng)目Ij的標(biāo)簽集合T(Ij)的元素個(gè)數(shù)。

圖1為一個(gè)用戶(hù)-項(xiàng)目-標(biāo)簽關(guān)系示意圖，用戶(hù)集U={U1，U2}，項(xiàng)目集I={I1，I2，I3}，標(biāo)簽集T={T1，T2，T3，T4}，用戶(hù)U1的項(xiàng)目集I(U1)={I1，I2}，用戶(hù)U2的項(xiàng)目集I(U2)={I2，I3}，項(xiàng)目I1的標(biāo)簽集T(I1)={T1，T3}，項(xiàng)目I2的標(biāo)簽集T(I2)={T1，T3，T4}，項(xiàng)目I3的標(biāo)簽集T(I3)={T2，T3，T4}，用戶(hù)U1的標(biāo)簽集T(U1)={T1，T3，T4}，用戶(hù)U2的標(biāo)簽集T(U2)={T1，T2，T3，T4} 。 用 戶(hù) 對(duì) 各 標(biāo) 簽 的TF值 分 別 為tf11=2/5，tf13=2/5，tf14=1/5，tf21=1/6，tf22=1/6，tf23=1/3，tf24=1/3，各標(biāo)簽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)。用戶(hù)U1對(duì)項(xiàng)目I3的預(yù)測(cè)偏好值P(U1，I3)=(0+tf13×idf3+tf14×idf4)/3=(2/5×ln1.001+1/5×ln1.501)/3=0.027 208 704。用戶(hù)U2對(duì)項(xiàng)目I1的預(yù)測(cè)偏好值P(U2，I1)=(tf21×idf1+tf23×idf3)/2=(1/6×ln 1.501+1/3×ln1.01)/2=0.035 502 685。

圖1 用戶(hù)-項(xiàng)目-標(biāo)簽

3.2 基于標(biāo)簽支持度的用戶(hù)偏好模型

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

nik為用戶(hù)Ui選擇項(xiàng)目中包含該標(biāo)簽Tk的項(xiàng)目數(shù)目，Nk為具有標(biāo)簽Tk的項(xiàng)目總數(shù)目，支持度Sik表示用戶(hù)Ui選擇具有標(biāo)簽Tk的項(xiàng)目數(shù)占該類(lèi)別項(xiàng)目總數(shù)的比值，若用戶(hù)選擇了所有具有某類(lèi)標(biāo)簽的項(xiàng)目，達(dá)到最大值1，若用戶(hù)沒(méi)有選擇任何具有該標(biāo)簽的項(xiàng)目，達(dá)到最小值0，顯然該值的范圍為[0，1]，比值越大，表示該用戶(hù)對(duì)該類(lèi)別項(xiàng)目偏好程度越大。

如項(xiàng)目總數(shù)為1 000，用戶(hù)選擇的總項(xiàng)目數(shù)為300，選擇A類(lèi)項(xiàng)目的數(shù)量為10，A類(lèi)項(xiàng)目的總數(shù)為20，選擇B類(lèi)項(xiàng)目的數(shù)量為20，B類(lèi)項(xiàng)目的總數(shù)為100，經(jīng)過(guò)計(jì)算用戶(hù)對(duì)兩類(lèi)項(xiàng)目的TFIDF值是相同的，而A類(lèi)項(xiàng)目支持度為10/20=0.5，B類(lèi)項(xiàng)目支持度為20/100=0.2，而實(shí)際應(yīng)用中，B類(lèi)項(xiàng)目比較流行，用戶(hù)可以很方便地獲取，而A類(lèi)項(xiàng)目，用戶(hù)卻難以發(fā)現(xiàn)，因此推薦給用戶(hù)A類(lèi)項(xiàng)目，更能獲得用戶(hù)喜愛(ài)。

一個(gè)項(xiàng)目包含多個(gè)標(biāo)簽，參照文獻(xiàn)[15]，取用戶(hù)對(duì)項(xiàng)目中包含的標(biāo)簽的支持度的平均值作為用戶(hù)對(duì)項(xiàng)目的支持度，用戶(hù)Ui對(duì)項(xiàng)目Ij的支持度表示為：

|T(Ij)|為項(xiàng)目Ij包含的標(biāo)簽個(gè)數(shù)，用戶(hù)Ui對(duì)項(xiàng)目Ij的支持度取項(xiàng)目包含標(biāo)簽的支持度的平均值。如圖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 基于網(wǎng)絡(luò)和標(biāo)簽混合推薦模型

推薦算法混合的形式有多種，可以是串行方式，首先用一種推薦技術(shù)產(chǎn)生一個(gè)較為粗略的候選結(jié)果，在此基礎(chǔ)上使用第二種推薦技術(shù)進(jìn)一步精確地推薦，也可以將多種推薦技術(shù)的計(jì)算結(jié)果加權(quán)混合產(chǎn)生推薦。采用串行方式，需要分別運(yùn)行推薦算法，時(shí)間復(fù)雜度為兩種推薦算法的復(fù)雜度和，而加權(quán)混合方式，多種推薦算法可在相同的遍歷中同時(shí)進(jìn)行運(yùn)算，時(shí)間開(kāi)銷(xiāo)較小。本文算法采用加權(quán)混合方式，在基于網(wǎng)絡(luò)的評(píng)分基礎(chǔ)上，增加兩種用戶(hù)偏好值的附加分量。用戶(hù)U i對(duì)項(xiàng)目Ij的預(yù)測(cè)評(píng)分表達(dá)式為：

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

4 算法描述

算法主要有三個(gè)步驟：第一步統(tǒng)計(jì)用戶(hù)及項(xiàng)目的相關(guān)統(tǒng)計(jì)信息，構(gòu)建基于TF-IDF和支持度的偏好模型；第二步計(jì)算項(xiàng)目間資源分配矩陣；第三步根據(jù)基于網(wǎng)絡(luò)和標(biāo)簽的混合推薦模型為某用戶(hù)計(jì)算未選擇項(xiàng)目的預(yù)測(cè)評(píng)分。

第一步構(gòu)建用戶(hù)基于標(biāo)簽的偏好模型。

輸入：用戶(hù)集U，項(xiàng)目集I，訓(xùn)練集T

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

（2）統(tǒng)計(jì)每個(gè)用戶(hù)Ul的度，記為k(Ul)

（3）統(tǒng)計(jì)每個(gè)項(xiàng)目Ii的度，記為k(Ii)

（4）得到每個(gè)項(xiàng)目Ii所連接用戶(hù)集合，記為U(Ii)

（5）統(tǒng)計(jì)用戶(hù)Ul選擇標(biāo)簽Tk的次數(shù)nlk

（6）統(tǒng)計(jì)標(biāo)簽Tk被選擇總次數(shù)Nk

（7）Endfor

（8）計(jì)算用戶(hù)各標(biāo)簽的TF-IDF值，得到用戶(hù)偏好配置文件

（9）計(jì)算用戶(hù)對(duì)各標(biāo)簽的支持度SUP(Ul，Tk)

第二步計(jì)算項(xiàng)目間資源分配矩陣。

輸入：用戶(hù)集U，項(xiàng)目集I，訓(xùn)練集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

第三步為某個(gè)用戶(hù)計(jì)算所有未選擇項(xiàng)目預(yù)測(cè)評(píng)分。

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

輸出：用戶(hù)Ul對(duì)未選擇項(xiàng)目的評(píng)分集合

（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的長(zhǎng)度；最后再取評(píng)分最高top-N個(gè)項(xiàng)目推薦給用戶(hù)Ul。

從算法流程中可以看出，兩種用戶(hù)對(duì)標(biāo)簽的偏好模型的構(gòu)建都穿插在NBI算法流程中，主要增加的行有5～6及24～29，并沒(méi)有過(guò)多額外的時(shí)間開(kāi)銷(xiāo)。

5 實(shí)驗(yàn)分析

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

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

個(gè)性化推薦結(jié)果的評(píng)價(jià)通常從精確度和個(gè)性化程度進(jìn)行評(píng)價(jià)[3]，本文通過(guò)推薦精度和召回率驗(yàn)證推薦精確度，利用命中項(xiàng)目平均度及多樣性驗(yàn)證推薦的個(gè)性化程度。給定了推薦列表的長(zhǎng)度L，系統(tǒng)把排名最靠前的L個(gè)項(xiàng)目推薦給用戶(hù)，觀察所推薦的L個(gè)項(xiàng)目，假設(shè)二部圖邊Ui-Ij出現(xiàn)在測(cè)試集中，如果Ij為所推薦的L個(gè)項(xiàng)目之一，那么稱(chēng)項(xiàng)目Ij被算法命中。本文分別在給定推薦列表長(zhǎng)度L為5、10、20、50、100的情況下，對(duì)算法進(jìn)行了實(shí)驗(yàn)和討論。

5.2 推薦精度

推薦精度和召回率是評(píng)價(jià)推薦結(jié)果精確度的兩個(gè)度量值，精度是推薦結(jié)果中命中項(xiàng)目數(shù)量與推薦項(xiàng)目總數(shù)的比值，召回率是推薦結(jié)果命中項(xiàng)目數(shù)量與測(cè)試集中用戶(hù)實(shí)際選擇的項(xiàng)目數(shù)量的比值。

召回率計(jì)算公式為：

精度計(jì)算公式為：

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

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

5.3 個(gè)性化程度

除了測(cè)量推薦結(jié)果精度，推薦結(jié)果的個(gè)性化程度也是評(píng)價(jià)推薦效果的一個(gè)有意義的指標(biāo)，比如推薦給用戶(hù)10部電影，其中8部是非常流行的，而另外2部是適合用戶(hù)偏好的，流行的電影通常可以在更多的場(chǎng)所得到推薦（比如電視、網(wǎng)絡(luò)、電影院等），而符合用戶(hù)偏好的非流行電影卻難以被用戶(hù)發(fā)現(xiàn)，因此這2部非流行的電影對(duì)用戶(hù)的意義更大。為測(cè)試推薦結(jié)果個(gè)性化程度，分別采用推薦項(xiàng)目流行度和多樣化兩種方法進(jìn)行測(cè)量。

項(xiàng)目流行度以推薦項(xiàng)目的平均度來(lái)測(cè)量，項(xiàng)目的度為項(xiàng)目被用戶(hù)選擇的次數(shù)，度越大，說(shuō)明項(xiàng)目越流行，將流行項(xiàng)目推薦給用戶(hù)，雖然能得到用戶(hù)認(rèn)可，推薦命中率提高，但推薦結(jié)果個(gè)性化程度較低。給定推薦長(zhǎng)度為L(zhǎng)，所有被推薦項(xiàng)目的平均度作為流行度的測(cè)量標(biāo)準(zhǔn)，推薦項(xiàng)目的平均度越小，在一定程度上反映推薦項(xiàng)目更考慮了用戶(hù)偏好。

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

圖2 典型推薦長(zhǎng)度下命中項(xiàng)目平均度

表1 典型推薦列表長(zhǎng)度的命中項(xiàng)目總數(shù)、精度及召回率

圖3 典型推薦長(zhǎng)度下推薦項(xiàng)目用戶(hù)間平均漢明距離

6 結(jié)束語(yǔ)

NBI算法根據(jù)用戶(hù)-項(xiàng)目二分圖結(jié)構(gòu)計(jì)算項(xiàng)目之間的推薦程度，根據(jù)用戶(hù)已選擇項(xiàng)目計(jì)算未選擇項(xiàng)目的推薦程度獲取推薦列表，核心思想采用了項(xiàng)目與項(xiàng)目之間的關(guān)系。而本文算法在NBI算法的基礎(chǔ)上，根據(jù)用戶(hù)選擇項(xiàng)目的標(biāo)簽信息，分別采用TF-IDF和標(biāo)簽支持度的方法構(gòu)建用戶(hù)偏好模型，根據(jù)待預(yù)測(cè)項(xiàng)目的標(biāo)簽計(jì)算用戶(hù)對(duì)項(xiàng)目的偏好程度，并與NBI推薦模型進(jìn)行線(xiàn)性組合推薦。經(jīng)過(guò)在數(shù)據(jù)集上測(cè)試證明，在推薦精度、個(gè)性化程度等方面均比單純的基于網(wǎng)絡(luò)的推薦均有所改進(jìn)。但本文對(duì)各模型的加權(quán)組合方法尚待進(jìn)一步探討，各模型權(quán)重需要一種更為科學(xué)的方法確定，同時(shí)本文算法需要進(jìn)一步在更多數(shù)據(jù)集，尤其大數(shù)據(jù)集上進(jìn)行測(cè)試驗(yàn)證。

[1]劉建國(guó)，周濤，汪秉宏.個(gè)性化推薦系統(tǒng)的研究進(jìn)展[J].自然科學(xué)進(jìn)展，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]張新猛，蔣盛益.基于加權(quán)二部圖的個(gè)性化推薦算法[J].計(jì)算機(jī)應(yīng)用，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]王國(guó)霞，劉賀平.個(gè)性化推薦系統(tǒng)綜述[J].計(jì)算機(jī)工程與應(yīng)用，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]劉斌，楊帆.支持多維標(biāo)簽云的移動(dòng)餐廳推薦系統(tǒng)仿真研究[J].計(jì)算機(jī)工程與應(yīng)用，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.