基于異質(zhì)信息網(wǎng)絡(luò)的模糊推薦算法*

李 嫻,趙 霞,張澤華,張晨威

(1.太原理工大學(xué)信息與計(jì)算機(jī)學(xué)院,山西 晉中 030600;2.伊利諾伊大學(xué)芝加哥分校計(jì)算機(jī)科學(xué)學(xué)院,芝加哥 60607)

1 引言

推薦系統(tǒng)預(yù)測(cè)用戶可能感興趣的項(xiàng)目，是解決信息過載的有用工具[1]。近年來，推薦系統(tǒng)在數(shù)字化進(jìn)程中扮演著越來越重要的角色，例如微博的好友推薦、淘寶的產(chǎn)品推薦、Netflix的電影推薦、Pandaro的音樂推薦等。

協(xié)同過濾作為推薦系統(tǒng)中最經(jīng)典的模型之一，是研究2個(gè)對(duì)象(user和item)相似性的算法。換句話說，用戶購買物品時(shí)可能會(huì)參考朋友的建議(userCF)或者考慮用戶歷史購買記錄(itemCF)。然而，數(shù)據(jù)稀疏問題仍然是推薦系統(tǒng)面臨的一大挑戰(zhàn)。針對(duì)數(shù)據(jù)稀疏問題，Jamali等人[2]探索社交網(wǎng)絡(luò)找到用戶信任的鄰域，通過聚合用戶鄰域的評(píng)級(jí)來進(jìn)行推薦。Zhang等人[3]過濾項(xiàng)目-用戶矩陣中不重要的評(píng)級(jí)，通過融合相似用戶群和相似項(xiàng)目群預(yù)測(cè)未評(píng)級(jí)項(xiàng)目。Jesús等人[4]采用Jaccard相似度為與鄰居用戶相似的活躍用戶投票。這些推薦算法在一定程度上解決了數(shù)據(jù)稀疏問題，但是用戶選擇某一項(xiàng)目的原因不僅來自于朋友關(guān)系。這種單一的關(guān)系類型，不利于挖掘用戶偏好。

基于評(píng)級(jí)歷史的用戶之間的相似性計(jì)算在許多實(shí)際應(yīng)用中是不準(zhǔn)確的，并且應(yīng)該使用諸如用戶的人口統(tǒng)計(jì)數(shù)據(jù)之類的其他信息，因?yàn)檫@些數(shù)據(jù)反映了用戶之間的相關(guān)性。通過融合用戶的各種屬性比僅根據(jù)評(píng)級(jí)歷史作推薦更嚴(yán)格。近年來，異質(zhì)信息網(wǎng)絡(luò)HIN(Heterogeneous Information Network)為推薦系統(tǒng)的研究提供了一種新的思路[5]。Shi等人[6]提出異質(zhì)信息網(wǎng)絡(luò)融合多種類型的輔助信息。Hu等人[7]利用異質(zhì)信息網(wǎng)絡(luò)中的元路徑表示用戶偏好。在實(shí)際推薦系統(tǒng)中異質(zhì)信息網(wǎng)絡(luò)融合了電影的導(dǎo)演、演員和類型等多種對(duì)象關(guān)系類型來改善推薦性能。然而，離散的用戶評(píng)分無法合理表達(dá)用戶的實(shí)際情況。例如，離散的評(píng)分無法表達(dá)用戶評(píng)分為3～4分時(shí)的喜好程度。為此，本文借鑒模糊集理論構(gòu)建三角模糊評(píng)分模型將電影用戶離散的評(píng)分模糊化，還加入了電影的演員、導(dǎo)演等屬性信息生成元路徑；在此基礎(chǔ)上提出了一種新的相似性度量，并預(yù)測(cè)評(píng)分獲得最終的推薦結(jié)果。

本文的主要貢獻(xiàn)包括2個(gè)方面：

(1)提出了基于異質(zhì)信息網(wǎng)絡(luò)的模糊推薦系統(tǒng)算法HFR(Fuzzy Recommendation algoritym based on Heterogeneous information network)。該算法在異質(zhì)信息網(wǎng)絡(luò)的基礎(chǔ)上通過一種新的相似性度量預(yù)測(cè)評(píng)分，有效地解決在數(shù)據(jù)稀疏情況下推薦任務(wù)中的模糊評(píng)分問題。

(2)本文實(shí)現(xiàn)了基于異質(zhì)信息網(wǎng)絡(luò)的模糊推薦HFR算法的評(píng)測(cè)平臺(tái)。在不同數(shù)據(jù)集的不同稀疏度下，驗(yàn)證了HFR算法的可行性與有效性。

2 相關(guān)工作

2.1 異質(zhì)信息網(wǎng)絡(luò)

隨著互聯(lián)網(wǎng)數(shù)據(jù)的爆炸式增長(zhǎng)，信息的“豐富”和“稀疏”并存，如何在海量的數(shù)據(jù)中提取有用信息變得越來越困難。異質(zhì)信息網(wǎng)絡(luò)包含多種類型的對(duì)象及對(duì)象之間的關(guān)系，它的出現(xiàn)為不同類型的信息建模提供了思路。從圖的角度融合不同類型的對(duì)象關(guān)系和語義信息，解決了傳統(tǒng)同質(zhì)網(wǎng)絡(luò)信息缺失的問題。相關(guān)定義[5]如下所示：

定義1異質(zhì)信息網(wǎng)絡(luò)表示為G={ν,ε}，由對(duì)象集ν和鏈接集ε組成。異質(zhì)信息網(wǎng)絡(luò)還與對(duì)象類型映射函數(shù)Φ：ν→A和鏈接映射函數(shù)Ψ:ε→R相關(guān)聯(lián)。A和R表示預(yù)定義對(duì)象和鏈接的集合，|A|+|R|>2。

基于異質(zhì)信息網(wǎng)絡(luò)的推薦方法通常分為3個(gè)方面：(1)基于語義：Chen等人[8]通過優(yōu)化PathSim全局權(quán)重，融合項(xiàng)目的配置文件緩解推薦系統(tǒng)的數(shù)據(jù)稀疏問題；Shi等人[6]提出Sem-Rec獲得元路徑上用戶偏好的優(yōu)先權(quán)重和個(gè)性化權(quán)重。(2)基于矩陣分解：Zhu等人[9]利用矩陣分解提取出源網(wǎng)絡(luò)中的潛在因子，通過錨鏈接(Anchor Links)將提取的潛在因子從源網(wǎng)絡(luò)轉(zhuǎn)移到目標(biāo)網(wǎng)絡(luò)。(3)基于社會(huì)關(guān)系：Luo等人[10]提出基于社會(huì)異質(zhì)關(guān)系的協(xié)同過濾推薦Hete-CF(social-based Collaborative Filtering recommendation using Heterogeneous relations)有效整合所有社會(huì)關(guān)系，包括用戶-用戶、項(xiàng)目-項(xiàng)目和用戶-項(xiàng)目之間的關(guān)系，解決數(shù)據(jù)稀疏問題。Zheng等人[11]為提高用戶點(diǎn)擊率，利用用戶之間的信任信息、朋友關(guān)系和其他類型的信息提高推薦質(zhì)量。

這些研究者通過細(xì)微地描述對(duì)象關(guān)系，探索更加詳細(xì)的語義信息。可見，基于異質(zhì)信息網(wǎng)絡(luò)的推薦正在快速發(fā)展。

2.2 模糊集

社交網(wǎng)絡(luò)中存在的信息模糊性和不確定性帶來的結(jié)果隨機(jī)性直接影響用戶體驗(yàn)，從不確定的信息中挖掘用戶的實(shí)際偏好顯得尤為重要。模糊集是處理不確定信息的一種形式，通過設(shè)置閾值，判斷某個(gè)元素是否屬于這個(gè)集合。相關(guān)定義[12,13]如下：

定義3模糊集F由論域U中的隸屬函數(shù)μF(u)表示：

μF(u)：u∈U→[0,1]

(1)

定義4存在多種類型的隸屬函數(shù)，例如三角模糊數(shù)f表達(dá)喜好程度：

f=(a,b,c;w)

(2)

其中，a,c分別是上下界；b是中間值；w表示用戶決策的模糊權(quán)重，且0

(3)

Figure 1 Triangular fuzzy number f=(t1,t2,t3)圖1 三角模糊數(shù)

模糊集中，用戶的喜好程度用語言術(shù)語表達(dá)，如極高、高、低等。在現(xiàn)實(shí)世界中有很多問題不能以定量的形式評(píng)估，而是以模糊或者不精確的形式定性分析[14]。Wu等人[15]在傳統(tǒng)余弦相似度的基礎(chǔ)上引入模糊集，解決了數(shù)據(jù)稀疏問題。Kant等人[16]將用戶年齡模糊化，合理表達(dá)用戶屬性。Jiménez等人[17]驗(yàn)證了基于模糊規(guī)則的分類方法的有效性。張冰等人[18]依據(jù)模糊的評(píng)價(jià)信息得到了合理的聚類結(jié)果。同時(shí)，有很多研究者將模糊集理論應(yīng)用到醫(yī)療診斷、圖像處理等任務(wù)中[19,20]。

3 HFR算法

3.1 問題描述

在推薦任務(wù)中以網(wǎng)絡(luò)或圖的形式對(duì)用戶-項(xiàng)目之間的交互進(jìn)行建模，根據(jù)觀察到的節(jié)點(diǎn)以及節(jié)點(diǎn)之間的鏈接預(yù)測(cè)未知的評(píng)分。給定異質(zhì)信息網(wǎng)絡(luò)G={ν,ε}，從多種關(guān)系類型出發(fā)，對(duì)不同類型的關(guān)系進(jìn)行建模，并挖掘用戶的實(shí)際偏好，但忽略了用戶的不確定性，會(huì)直接影響推薦結(jié)果。在原始的用戶評(píng)分中，用離散的評(píng)級(jí)刻畫用戶的喜好程度。由于每個(gè)用戶的標(biāo)準(zhǔn)不同，評(píng)分是主觀的、模糊的、不確定的。由此，本文提出基于異質(zhì)信息網(wǎng)絡(luò)的模糊推薦算法。

3.2 異質(zhì)信息網(wǎng)絡(luò)的模糊推薦算法

HFR算法的核心是提出一種新的相似性度量，結(jié)合基于異質(zhì)信息網(wǎng)絡(luò)的用戶之間相似度與根據(jù)模糊評(píng)分計(jì)算出的用戶相似度形成最終相似度。根據(jù)用戶屬性和評(píng)分更準(zhǔn)確地反映用戶之間的相關(guān)性。每個(gè)相似度(模糊相似度/基于元路徑相似度)都將根據(jù)相似用戶數(shù)自動(dòng)計(jì)算權(quán)重。一旦計(jì)算出最終的相似度，根據(jù)用戶的鄰居預(yù)測(cè)最終的評(píng)分。具體算法步驟如下所示：

算法1基于異質(zhì)信息網(wǎng)絡(luò)的模糊推薦算法

輸入：評(píng)分矩陣r∈M,元路徑P。

輸出：預(yù)測(cè)評(píng)分矩陣R′。

步驟2MS(ua,ub)；//計(jì)算基于元路徑的相似性

for eachi//對(duì)于每一個(gè)項(xiàng)目i

FS(ua,ub)；//計(jì)算模糊相似度

ifFS(ua,ub)≤θ：

k=k+1；

end for

步驟3

SIM(ua,ub)=α×MS(ua,ub)+β×FS(ua,ub)/*基于元路徑相似性的權(quán)重為α,基于模糊相似度的權(quán)重為β,得到最終相似度*/

步驟4

3.2.1 相似性度量

現(xiàn)實(shí)網(wǎng)絡(luò)包含多種類型的對(duì)象和交互信息，將對(duì)象及其關(guān)系建模為異質(zhì)信息網(wǎng)絡(luò)。利用元路徑表示不同對(duì)象之間豐富的語義信息，本文設(shè)計(jì)UM*MU和UMU格式的元路徑，表示用戶選擇電影可能是因?yàn)橄矚g該部電影的導(dǎo)演(D)、演員(C)、類型(T)等。如圖2所示。

Figure 2 An example of heterogeneous information network圖2 異質(zhì)信息網(wǎng)絡(luò)示例

在元路徑刻畫用戶偏好的基礎(chǔ)上，采用Sun等人[21]提出的PathSim，計(jì)算基于元路徑的相似性。給定1個(gè)對(duì)稱的元路徑，用戶ua和ub基于元路徑的相似性為：

MS(ua,ub)=(2×|{pua→ub:pua→ub∈P}|)/

(|{pua→ua:pua→ua∈P}|+|{pub→ub:pub→ub∈P}|)

(4)

其中，pua→ub表示用戶ua到ub的路徑，pua→ua表示用戶ua到ua的路徑，pub→ub表示用戶ub到ub的路徑。對(duì)象之間的連通性由它們之間的路徑實(shí)例數(shù)決定。因此，MS(ua,ub)的值在0～1，越接近1，則ua和ub越相似。

在異質(zhì)信息網(wǎng)絡(luò)中，用戶的離散評(píng)分使得用戶喜好具有片面性，引入模糊集使用戶評(píng)分模糊化，可更加合理地表達(dá)用戶偏好。

以數(shù)據(jù)集MovieLens評(píng)分等級(jí)(1～5)為例，含有用戶u∈U，項(xiàng)目i∈I。根據(jù)定義2構(gòu)建三角模糊評(píng)分模型，如圖3所示。其中，VL(非常低)、L(低)、M(中)、H(高)、VH(非常高)表示用戶的喜好程度，z表示用戶對(duì)項(xiàng)目的滿意度。

Figure 3 Triangular fuzzy rating model圖3 三角模糊評(píng)分模型

每1個(gè)喜好程度對(duì)應(yīng)的評(píng)分等級(jí)模糊數(shù)如表1所示。

Table 1 Preference degree and its semantics表1 喜好程度及其語義

三角模型評(píng)分處理后，離散的電影評(píng)級(jí)通過隸屬函數(shù)模糊化。由此，得到隸屬函數(shù)：

μVL(z)=(0.25-z)/0.25,0≤z≤0.25

(5)

μVH(z)=(z-0.75)/0.25,0.75≤z≤1.0

選取用戶ua和ub共同評(píng)分的項(xiàng)目i∈Iij的模糊權(quán)重[22]為：

(6)

(7)

(8)

3.2.2 預(yù)測(cè)評(píng)分

將基于元路徑的相似性和模糊相似性賦予不同的權(quán)重，獲得最終的相似性：

SIM(ua,ub)=α×MS(ua,ub)+β×FS(ua,ub)

(9)

其中，α和β滿足以下條件：

α+β=1

(10)

(11)

其中，α、β分別表示基于元路徑相似度MS(ua,ub)的權(quán)重和模糊相似度FS(ua,ub)的權(quán)重，k表示用戶鄰居數(shù)。根據(jù)這種新的相似性度量預(yù)測(cè)最終的評(píng)分：

(12)

綜上所述，考慮多種關(guān)系類型以及用戶評(píng)分的不確定性，融合基于元路徑相似性和模糊相似性，預(yù)測(cè)最終評(píng)分。

4 實(shí)驗(yàn)設(shè)計(jì)與分析

4.1 測(cè)試數(shù)據(jù)集

為了驗(yàn)證HFR算法的性能，選擇3個(gè)真實(shí)的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。MovieLens數(shù)據(jù)集包含6 040名用戶對(duì)3 706部電影的1 000 209個(gè)評(píng)分(1～5分)。Douban Movie數(shù)據(jù)集包含13 367名用戶對(duì)12 677部電影的1 068 178個(gè)評(píng)分(1～5分)。2個(gè)電影數(shù)據(jù)集都含有電影的類型(T)、導(dǎo)演(D)、演員(C)等信息。Douban Book數(shù)據(jù)集包含13 024名用戶對(duì)22 347本書的792 026個(gè)評(píng)分(1～5分)。圖書數(shù)據(jù)集中含有書的作者(O)、出版社(Q)、出版年份(Y)等信息，數(shù)據(jù)集信息如表2所示。

Table 2 MovieLens,Douban Movie and Douban Book datadets表2 MovieLens、Douban Movie 和 Douban Book數(shù)據(jù)集

在HFR算法中，定位用戶對(duì)電影的偏好是首要問題，需要通過元路徑計(jì)算用戶相似性。為此，選擇包含用戶實(shí)體和項(xiàng)目屬性的元路徑。MovieLens和Douban Movie 2個(gè)數(shù)據(jù)集都涉及到電影推薦，Douban Book是圖書數(shù)據(jù)集。如表2中所示，UMU表示用戶看了同一部電影；UMTMU表示用戶根據(jù)電影類型進(jìn)行選擇；UMCMU表示用戶因?yàn)橄矚g某個(gè)演員而選擇電影；UMDMU表示用戶因?yàn)橄矚g某個(gè)導(dǎo)演而選擇電影。UBU表示用戶看了同一本書；UBOBU表示用戶因?yàn)橄矚g某個(gè)作者而選擇圖書；UBQBU表示用戶根據(jù)出版社選擇圖書；UBYBU表示用戶根據(jù)出版年份選擇圖書。實(shí)驗(yàn)將數(shù)據(jù)的80%作為訓(xùn)練集，20%作為測(cè)試集。為了減少隨機(jī)分割數(shù)據(jù)帶來的誤差，實(shí)驗(yàn)結(jié)果取運(yùn)行3次的平均值。

4.2 實(shí)驗(yàn)及評(píng)測(cè)指標(biāo)

為了驗(yàn)證HFR算法的性能，與以下4個(gè)算法進(jìn)行比較：

User-CF：實(shí)驗(yàn)采用推薦系統(tǒng)算法庫surprise實(shí)現(xiàn)。基于用戶的協(xié)同過濾，采用余弦相似度發(fā)現(xiàn)具有共同興趣的用戶。

Fuzzy-CF[16]：將用戶年齡模糊化，通過協(xié)同過濾引入模糊相似性度量預(yù)測(cè)評(píng)分。

Fuzzy-UBCF[15]：引入模糊集，擴(kuò)展余弦相似度，提高推薦質(zhì)量。

Hete-CF[10]：通過融合多種關(guān)系類型，緩解推薦系統(tǒng)的數(shù)據(jù)稀疏問題。

實(shí)驗(yàn)采用的評(píng)測(cè)指標(biāo)是均方根誤差(RMSE)及平均絕對(duì)誤差(MAE)，其計(jì)算公式如下所示：

(13)

(14)

其中，Γ是測(cè)試集。

為了驗(yàn)證HFR算法的性能，與User-CF、Fuzzy-CF、Fuzzy-UBCF和Hete-CF 4種算法在MovieLens、Douban Movie和Douban Book 3個(gè)數(shù)據(jù)集的不同稀疏度下進(jìn)行比較，并分析用戶鄰居數(shù)k對(duì)推薦結(jié)果的影響。

4.3 與其他推薦算法比較

HFR算法與上述4種算法的RMSE、MAE比較結(jié)果如表3所示?？梢钥闯觯c其他推薦算法相比，HFR算法具有較好的推薦效果。因?yàn)閁ser-CF算法只考慮用戶-項(xiàng)目的評(píng)分，在實(shí)際推薦任務(wù)中用戶與項(xiàng)目的交互往往很稀疏。Fuzzy-CF算法將用戶年齡模糊化，未考慮其他因素。Fuzzy-UBCF算法基于單一的朋友關(guān)系，引入模糊相似性。Hete-CF算法考慮了多種社會(huì)關(guān)系類型，如用戶-項(xiàng)目、用戶-用戶和項(xiàng)目-項(xiàng)目等關(guān)系，但是忽略了用戶評(píng)分的不確定性。而HFR算法考慮了多種關(guān)系類型并且將用戶評(píng)分模糊化，使得推薦結(jié)果更優(yōu)。

在MovieLens、Douban Movie和Douban Book數(shù)據(jù)集原有稀疏度的基礎(chǔ)上刪除一部分?jǐn)?shù)據(jù)，得到不同稀疏度下的RMSE和MAE。隨著數(shù)據(jù)稀疏度的不斷增加，User-CF算法準(zhǔn)確度下降得最快；Fuzzy-CF、Fuzzy-UBCF和Hete-CF較為平緩；由此看來，HFR算法在高稀疏度的數(shù)據(jù)集中仍然有較好的表現(xiàn)。

4.4 參數(shù)敏感性分析

參數(shù)的變化影響著實(shí)驗(yàn)結(jié)果的好壞。本節(jié)在MovieLens、Douban Movie和Douban Book數(shù)據(jù)集上分析鄰居個(gè)數(shù)k對(duì)Hete-CF算法的RMSE和MAE的的影響。

鄰居個(gè)數(shù)k直接影響著推薦結(jié)果，如圖4和圖5所示，分別取鄰居個(gè)數(shù)為10，20，…，80，觀察RMSE和MAE的變化?？梢钥闯?，當(dāng)鄰居個(gè)數(shù)為40時(shí)，HFR算法在MovieLens數(shù)據(jù)集上的效果最好；當(dāng)鄰居個(gè)數(shù)為50時(shí)，HFR算法在Douban Movie數(shù)據(jù)集上的效果最好；當(dāng)鄰居個(gè)數(shù)為70時(shí)，HFR算法在Douban Book數(shù)據(jù)集上的效果最好。Douban Movie數(shù)據(jù)集比MovieLens數(shù)據(jù)集更加稀疏，并且用戶數(shù)較多，因此獲得最優(yōu)結(jié)果時(shí)，Douban Movie需要的鄰居個(gè)數(shù)較多。整體來看，HFR算法含有豐富的用戶信息，所以在稀疏數(shù)據(jù)集上有較少的鄰居數(shù)。

Table 3 Experimental results comparison of HFR algorithm表3 HFR算法實(shí)驗(yàn)結(jié)果比較

Figure 4 Effect of k on RMSE圖4 k對(duì)RMSE的影響

Figure 5 Effect of k on MAE圖5 k對(duì)MAE的影響

綜上所述，HFR算法的優(yōu)勢(shì)在于通過多種關(guān)系挖掘用戶喜好，同時(shí)構(gòu)建三角模糊評(píng)分模型，將用戶離散的評(píng)分模糊化，使得其所攜帶的信息更加充分，解決用戶評(píng)分的模糊性。因此，在稀疏的數(shù)據(jù)集上HFR算法比傳統(tǒng)的推薦算法效果更優(yōu)。

5 結(jié)束語

本文提出了一種基于異質(zhì)信息網(wǎng)絡(luò)的模糊推薦系統(tǒng)算法，針對(duì)傳統(tǒng)協(xié)同過濾推薦算法存在的數(shù)據(jù)稀疏問題，融合用戶的多種關(guān)系類型，并且考慮用戶評(píng)分的模糊性，提出了一種新的相似性度量算法，解決了推薦任務(wù)中信息稀疏的問題。HFR算法在一定程度上能夠緩解數(shù)據(jù)稀疏問題；同時(shí)，與其他推薦系統(tǒng)算法比較，HFR算法具有較好的性能。