基于重要性的信任感知推薦方法

譚晏松，宋鐵成

(1.重慶電子工程職業(yè)學院 人工智能與大數(shù)據(jù)學院，重慶 401331； 2.重慶郵電大學 通信與信息工程學院，重慶 400065)

0 引 言

由于近幾十年來互聯(lián)網(wǎng)上的信息爆炸，推薦系統(tǒng)(recomme-ndation systems，RS)已經(jīng)成為大多數(shù)電子商務(wù)和社交網(wǎng)絡(luò)系統(tǒng)中的重要模塊[1,2]，成為解決日益增長的信息過載問題的有效方法。在各種推薦方法中，協(xié)同過濾(collaborative filtering，CF)是一種最成功的方法，它利用許多用戶的反饋來尋找相似的用戶和項目，作為推薦的基礎(chǔ)。但該技術(shù)也存在一些固有缺陷，如數(shù)據(jù)稀疏、冷啟動和推薦結(jié)果失真[3]。推薦系統(tǒng)的關(guān)鍵作用導(dǎo)致了該領(lǐng)域的大量研究，而如何克服傳統(tǒng)推薦系統(tǒng)的不足也成為研究的關(guān)鍵。

為了解決傳統(tǒng)推薦系統(tǒng)存在的冷啟動和準確率低等問題，基于機器學習的推薦模型得到了廣泛關(guān)注[4]。Zou等[5]提出一種社會推薦方法，使用自適應(yīng)鄰居選擇來提高預(yù)測的準確性。Wu等[6]提出了一種融合潛在社交信任模型的協(xié)同過濾推薦算法，以提高推薦質(zhì)量。Hai等[7]提出了一種基于時空感知的推薦方法。考慮到用戶的社會關(guān)系，通過構(gòu)建用戶、地點、時間、活動和朋友的信息網(wǎng)絡(luò)，獲得推薦活動。Wei等[8]提出了一種將離散內(nèi)容與興趣貼近度相結(jié)合的算法，用以提高推薦質(zhì)量與性能。Li等[9]提出了一種結(jié)合社會標簽和信任關(guān)系的社會網(wǎng)絡(luò)推薦方法。Wu等[10]提出一種將社會網(wǎng)絡(luò)結(jié)構(gòu)與用戶項目交互行為的內(nèi)在聯(lián)系有機結(jié)合起來的社會推薦神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)。

已有的信任感知推薦系統(tǒng)大多認為不同項目對用戶具有相同的重要性，但是現(xiàn)實生活中并非如此。本文基于不同人口統(tǒng)計學背景下項目重要性不一致的概念，提出了一種基于重要性的信任感知推薦方法，該方法通過用戶的人口統(tǒng)計上下文來衡量項目對用戶的重要性，然后以項目重要性來評估委托人和受托人之間的信任級別，從而有效地適應(yīng)用戶偏好的動態(tài)變化。

1 混合蛙跳算法

混合蛙跳算法[11](shuffled frog leaping algorithm，SFLA)在2003年由Eusuff等提出，是一種新型仿生學的群體進化算法，屬于啟發(fā)式智能優(yōu)化算法。在這種算法中，一組青蛙(或初始解決方案)協(xié)同感知最大的食物來源。通過同時使用局部和全局搜索，SFLA對各種優(yōu)化問題都是有效的[12]。

混合蛙跳算法描述如下：首先隨機初始化P只青蛙的種群，在D維搜索空間中，Xi=(Xi1,Xi2,…,XiD)表示第i個青蛙的位置。適應(yīng)度函數(shù)用于評估每個個體的適應(yīng)度。然后，按照青蛙的健康程度降序排列。種群中最好青蛙的位置用Xg表示。然后，將整個種群劃分為m個模因叢，每個模因叢包含n只青蛙(即P=m×n)。為此，第((i-1)×m+j)個青蛙被分配給第j個模因叢(i,j=1,2,…,m)。然后，對于每一個模因，最差青蛙的位置通過進化過程得到改善。讓Xw,j和Xb,j分別列出第j個模因叢中最差和最好青蛙的位置。在第j個模因進化過程中，最差的青蛙跳向位置Xb,j。第j個模因進化中最差的青蛙的跳躍步長計算如下

ΔXw,j=rand×(Xb,j-Xw,j)- ΔXmax≤ΔXw,j≤ΔXmax

(1)

式中：rand是(0.1)中的隨機數(shù)，而ΔXmax是最大允許步長。因此，SFLA確定最差青蛙的新位置如下

Xw,j(new)=Xw,j+ΔXw,j

(2)

如果Xw,j(new)比Xw,j具有更好的適應(yīng)值，那么當前位置將被新位置替換。另外，Xw,j是根據(jù)全局最佳青蛙的位置進行了改進。為此，用Xg代替Xb,j來重復(fù)式(1)和式(2)。如果仍然沒有改進，SFLA用一個新的隨機生成的解決方案替換最差的青蛙。進化過程在預(yù)定的迭代次數(shù)內(nèi)繼續(xù)。然后，執(zhí)行洗牌過程以形成下一代的新種群。重復(fù)這些過程，直到滿足終止條件。

2 基于重要性的信任感知推薦方法

傳統(tǒng)的CF方法面臨兩個主要問題：稀疏性和冷啟動。信任感知的RS通過使用用戶之間信任網(wǎng)絡(luò)中的其它信息來克服這些問題?；谛湃蔚姆椒梢苑譃轱@式和隱式方法。在顯式方法中，用戶顯式表達對其他用戶的信任。顯式方法的主要缺點是用戶可能對提供顯式信任語句不感興趣，從而導(dǎo)致稀疏的信任網(wǎng)絡(luò)。與顯式方法相反，隱式方法從用戶評級行為推斷信任關(guān)系。因此，隱式方法比顯式方法更實用。但是，已有的信任感知推薦方法均假定不同項目對用戶具有相同的重要性，但是在現(xiàn)實生活中，項目的重要性對于個人用戶來說并不盡然相同且是動態(tài)變化的，取決于性別、年齡、受教育程度等很多人口統(tǒng)計特征因素。例如，越流行的產(chǎn)品對年輕人群的重要性要大于年老人群。在本文中，提出了一種基于重要性的信任感知推薦方法，該方法在計算用戶之間的信任時考慮了項目的重要性。針對用戶的人口統(tǒng)計上下文定義了此方法中使用的重要性度量。因此，所提出的方法可以適應(yīng)用戶興趣的動態(tài)變化。

圖1給出了提出的基于重要性的信任感知推薦方法的框架。從圖中可以看出，提出的方法包含在線和離線兩個階段，離線階段主要用于用戶的集群，在線主要用于推薦列表的生產(chǎn)。在離線階段，混合蛙跳算法用于根據(jù)用戶的人口統(tǒng)計特征對用戶進行聚類。在線階段包括5個步驟：首先識別與活動用戶最相似的群集，以獲得候選鄰域集，即鄰居預(yù)選步驟；其次，計算活動用戶與每個候選鄰居之間的基于重要性的信任值，即基于重要性的信任計算步驟；再次，選擇最合適的候選者作為最終鄰居，即鄰居選擇步驟；然后，根據(jù)所選鄰居的偏好來預(yù)測活動用戶的未知評分，即評分預(yù)測步驟；最后，將前n個項目推薦給活動用戶，即推薦列表生成步驟。下面給出每個階段的詳細描述。

圖1 提出方法的框架

2.1 離線階段

圖2 青蛙的結(jié)構(gòu)

對于每個解決方案，計算用戶和每個集群中心之間的人口統(tǒng)計相似性，以將用戶分配到最近的集群。用戶u與質(zhì)心Zk之間的相似度計算為其對應(yīng)特征向量的余弦相似度

(3)

式中：DSimi(u,Zk)∈[0,1]是解Xi中u與第k個集群中心的人口統(tǒng)計學相似性。

下一步的目標是使用適應(yīng)度函數(shù)評估每個解決方案，利用SFLA算法從中選擇適應(yīng)度最高的值作為最優(yōu)解。集群解的適應(yīng)度基于集群內(nèi)距離之和確定，如式(4)所示

(4)

式中：Fitness(Xi)是青蛙Xi的適應(yīng)度。顯然，當集群內(nèi)距離之和較小時，解的質(zhì)量較高。

在模因進化過程中，每個模因叢中最壞的青蛙的位置是基于局部最優(yōu)或全局最優(yōu)青蛙的位置或基于隨機位置進行改進的。Xw,j是第j個模因叢中最差青蛙的位置。根據(jù)跳躍的步長(i.e.,ΔXw,j)，確定最差青蛙(i.e.,ΔXw,j(new))的新位置。由于位置向量的二元表示，將Xw,j(new)離散為二元向量，為此，使用改進的離散SFLA。在這個改進的算法中，用下列公式代替式(2)計算Xw,j(new)的第dbit

t=1/(1+exp(-ΔXwd,j))

(5)

式中：下標d∈{1,2,…,K×L}表示對應(yīng)向量的第d位，δ稱為靜態(tài)概率。當達到預(yù)定義的迭代次數(shù)時，滿足停止條件。

2.2 在線階段

提出算法的在線階段主要目標是生成推薦意見，此階段可以分為鄰居預(yù)選、信任計算、鄰居選擇、評級預(yù)測和推薦列表生成5步。

2.2.1 鄰居預(yù)選

在第一步中，識別與活動用戶最相似的集群。這些集群的所有成員都被選為活動用戶的候選鄰居。設(shè)CNau為活動用戶au的候選鄰居。對CNau的定義如下

CNau={u∈ck|ck∈C∧DSim(au,Zk)≥α}

(6)

式中：α是相似度閾值。如果α小，則人口統(tǒng)計學相似性相對較低的那些用戶也被視為候選鄰居；當α大時，候選鄰居的數(shù)量不足以識別可信賴的鄰居。

2.2.2 基于重要性的信任計算

根據(jù)活動用戶對候選鄰居的共同評價項以及這些項對活動用戶的重要性來計算活動用戶對候選鄰居的隱式信任。為了實現(xiàn)這一目標，定義了一個新的顯著性度量，它基于人口統(tǒng)計學背景下的項目評級。然后，提出了一種新的信任度量方法，該方法考慮了項目的重要性。

首先是顯著性計算，通過計算項目i的平均評級和評級的用戶的百分比兩個測量指標來計算項目i的重要性。假定si表示項目i的顯著性，其最小值為0(非顯著)和最大值為1(非常顯著)。為了確保si介于0和1之間，額定值標準化為[0,>1]。使用最小-最大標準化方法，將原始評級r轉(zhuǎn)換為標準化評級r′∈[0,1]，如下所示

(7)

式中：最小值是最小額定值，最大值是系統(tǒng)中的最大額定值。

設(shè)ru,i為從用戶u到項目i的標準化評級，設(shè)Ui={u∈U|ru,i≠·}為項目i評級的用戶集，符號ru,i=·表示u沒有對項目i進行評級，項目的重要性評價計算如下

(8)

式中：#表示集合的基數(shù)。

對于具有不同人口學特征的不同用戶，項目的重要性是不同的。此外，用戶的個人偏好可能在整個生命周期(從童年到老年)中發(fā)生變化。因此，當前對用戶重要的項在將來可能變得不那么重要。為了處理這一事實，在測量項目對u的重要性時考慮了用戶u的人口統(tǒng)計學背景。為此，將式(8)修改如下

(9)

式中：si,k∈[0,1]是集群ck用戶i項的重要性，Uk是集群ck用戶的集合，Ui,k={u∈ck|ru,i≠·}是集群ck用戶中對i項評級的集合。

其次是對信任進行計算。本文采用的信任度量包含了項目的重要性。從用戶u到用戶v，STrustu→v∈[0,1]的基于顯著性的信任定義如下

(10)

(11)

(12)

根據(jù)式(12)，直接信任值由相應(yīng)用戶之間的共同評級項目數(shù)加權(quán)。這種傳播方法的基本原理是，直接信任關(guān)系的可靠性隨著共同評級項目的數(shù)量而增加。因此，如果兩個用戶有更多的共同評價項，那么在傳播過程中，他們之間的關(guān)系權(quán)重會更大。信任網(wǎng)絡(luò)中任意兩個用戶之間的間接信任可以通過等式(12)的重復(fù)應(yīng)用來計算。如果網(wǎng)絡(luò)中兩個用戶之間存在多個路徑，則計算從可選路徑推斷的所有信任值的算術(shù)平均值。

2.2.3 鄰居選擇

從候選集中選擇活動用戶最可信的鄰居。為此，選擇信任值大于或等于指定閾值的候選對象作為鄰居。讓FNau表示活動用戶au的最后鄰居集。FNau定義如下

FNau={u∈CNau|STrustau→u≥θ}

(13)

式中：θ是信任閾值。

2.2.4 評分預(yù)測

選擇的鄰居用于預(yù)測活動用戶的偏好。目標項的活動用戶的未知分級估計如下

(14)

式中：pau,i是活動用戶au對目標項目i∈I1Iu的預(yù)測評級。

2.2.5 生成推薦列表

最后，使用預(yù)測的評級為活動用戶生成top-n推薦列表。目標項目根據(jù)其預(yù)測評級進行排名。然后，系統(tǒng)會推薦級別最高的項目。

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

3.1 數(shù)據(jù)集

實驗數(shù)據(jù)集采用MovieLens 1M1(ML)和Book-Crossing(BX2)兩個不同領(lǐng)域的公開來源真實數(shù)據(jù)集，ML和BX均包含用戶的人口統(tǒng)計信息。

ML數(shù)據(jù)集由6040個用戶為3952部電影提供的1 000 209個評級組成。評級從1分(差)到5分(優(yōu))。其稀疏度為95.809%。除了評級數(shù)據(jù)外，ML還提供了一些用戶的人口統(tǒng)計信息，包括年齡、性別和職業(yè)。性別是“M”(男性)或“F”(女性)。在這個數(shù)據(jù)集中，有21種不同的職業(yè)，如工程師、藝術(shù)家、醫(yī)生等。

BX數(shù)據(jù)集包含1 149 780個評級，來自271 379本書的278 858個用戶。有433 681個明確的評級，等級為1到10，716 109個隱含評級(值為0)。在這個數(shù)據(jù)集中，人口信息包括年齡和地點(國家)。刪除沒有評級的用戶和項目，數(shù)據(jù)集包含407 332個明確的評級，來自178 647本書的74 085個用戶(99.996%稀疏度)。

對于這兩個數(shù)據(jù)集，將用戶的人口統(tǒng)計特征表示為二進制特征向量，其中1和0分別表示特征的存在和不存在。用戶人口統(tǒng)計學向量的結(jié)構(gòu)見表1。

表1 數(shù)據(jù)集基本參數(shù)

根據(jù)表1，年齡、性別、職業(yè)和地點被定義為分類屬性。有4個年齡類別，2個性別類別，21個職業(yè)類別和30個地點類別。如果用戶屬于某個類別，則相應(yīng)的比特設(shè)置為1；否則為0。因此，對于每個分類屬性，只有一個位是1，其余的是0。對于ML數(shù)據(jù)集，人口統(tǒng)計學向量的長度為27，而對于另一個數(shù)據(jù)集，長度為34。在這兩種情況下，向量的前四位表示年齡類別。對于ML，第5和第6位表示用戶的性別，其余的位對應(yīng)于職業(yè)類別。對于BX，用戶的位置由位5-34指定(表1)。

3.2 實驗設(shè)置

在這項研究中，所有的實驗都使用5倍交叉驗證。評級數(shù)據(jù)被隨機分成5個大小相等的子集。在每次評估運行中，一個子集用作測試數(shù)據(jù)，而另一個子集用作訓(xùn)練數(shù)據(jù)。以5次平均成績作為總成績。從兩個不同的角度進行實驗：①所有用戶，其中對所有用戶及其評級進行評估;以及②冷用戶，主要關(guān)注評級低于10的用戶。

選用配置為Intel Corei5 @2.53 GHz和4 GB RAM的機器測試，調(diào)整每種方法的參數(shù)以獲得盡可能好的結(jié)果。對于所提出的方法，對SFLA進行微調(diào)以獲得最佳結(jié)果。SFLA的參數(shù)值見表2。

表2 SFLA參數(shù)設(shè)置

3.3 評價指標

為了評估推薦算法的性能，在實驗中預(yù)測精度是由均值絕對誤差(mean absolute error，MAE)來評估的，均值絕對誤差衡量的是預(yù)測值和實際值之間的誤差，其值越小說明算法性能越好。讓T表示要估計的額定值集(即測試集)。MAE定義如下

(15)

預(yù)測的質(zhì)量根據(jù)覆蓋率進行評估。評級覆蓋率(rating coverage，RC)是指系統(tǒng)可以預(yù)測的測試評級百分比，其值越大說明算法預(yù)測質(zhì)量越好

(16)

式中：pu,i≠·表示用戶u對項目i的評級是可預(yù)測的。

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

在第一個實驗中，驗證算法在離線、在線階段對參數(shù)的敏感性。圖3給出了離線階段集群K數(shù)量對算法的影響。從圖中可以看出，隨著K的增加，所提算法的MAE先下降后上升，ML和BX數(shù)據(jù)集分別在K=14和17時取得最優(yōu)。

圖3 集群K對算法的影響

圖4給出了在線階段相似度閾值α對算法的影響。從圖中可以看出，RC隨著α的增大而減小，并且較低的α值會導(dǎo)致較高覆蓋率和較低的準確性。對于兩個數(shù)據(jù)集，α分別取0.6和0.5時，可以獲得最佳的MAE。

圖4 相似度閾值α對算法的影響

在第二個實驗中，將提出的方法的整體性能與SRANS[5]、

DTTN[13]、TCFACO[14]這3種流行算法進行了比較。所有用戶(包括冷啟動和非冷啟動用戶)都參與了這個實驗。兩個數(shù)據(jù)集的MAE和RC結(jié)果見表3。

表3 ML和BX數(shù)據(jù)集的所有用戶視圖的MAE和RC結(jié)果

如表3所示，提出的方法在兩個數(shù)據(jù)集中的MAE最低。這驗證了基于重要性的信任度量在提高信任感知推薦系統(tǒng)性能方面的能力。此外，基于重要性的信任感知推薦方法具有比其它方法更高的RC。由于人口統(tǒng)計信息的利用，即使沒有評級數(shù)據(jù)，它也能為用戶找到足夠的鄰居。

第三個實驗，評估了提出的方法在緩解冷啟動問題方面的有效性。評級低于10項的用戶被視為冷啟動用戶，設(shè)N為測試用戶觀察到的評級數(shù)。通過改變評級的數(shù)量來評估預(yù)測和建議的質(zhì)量。對于每個測試用戶，保留N個培訓(xùn)等級，其余的則丟棄。實驗進行了N等于2，4，6和8的實驗。結(jié)果如圖5-圖10所示。

圖5 不同算法在ML數(shù)據(jù)集冷用戶視圖的MAE結(jié)果

圖5-圖6分別給出了4種不同方法在ML數(shù)據(jù)集的預(yù)測精度和質(zhì)量結(jié)果，從圖5中可以看出，所提出的方法比其它3種方法的MAE值要低，當評級數(shù)N越高時MAE值越低；圖6展示了它們在ML數(shù)據(jù)集冷用戶視圖的RC結(jié)果對比，同樣從圖中可以看出，所提出的方法的RC值均高于其它3種方法，當評級數(shù)N越高時RC值也越高。圖7-圖8則給出了4種方法在BX數(shù)據(jù)集的表現(xiàn)，結(jié)果與在ML數(shù)據(jù)集的表現(xiàn)相似?；谥匾缘男湃胃兄扑]方法，在預(yù)測精度和預(yù)測質(zhì)量上均優(yōu)于對比的方法。結(jié)果表明，將人口統(tǒng)計信息納入基于重要性的信任感知推薦方法有助于解決冷啟動問題。

圖6 不同算法在ML數(shù)據(jù)集冷用戶視圖的RC結(jié)果比較

圖7 不同算法在BX數(shù)據(jù)集冷用戶視圖的MAE結(jié)果

圖8 不同算法在BX數(shù)據(jù)集冷用戶視圖的RC結(jié)果比較

圖9給出了不同推薦方法在ML和BX數(shù)據(jù)集上的執(zhí)行時間對比結(jié)果。從圖中可以看出，在所有方法中，提出方法的執(zhí)行時間最短。由于采用了兩層鄰居選擇策略，DTTN的執(zhí)行時間較長。SRANS比DTTN慢是因為SRANS需要復(fù)雜的過程來識別初始鄰居集合并以自適應(yīng)方式對其進行優(yōu)化。TCFACO具有最長的執(zhí)行時間，因為它同時使用信任和相似性信息來構(gòu)造用戶映射，然后在該映射上應(yīng)用ACO搜索策略來查找用戶的最佳鄰居。

圖9 不同算法的執(zhí)行時間對比結(jié)果

圖10 不同傳播距離下的執(zhí)行時間

為了更好地理解所提推薦方法的效率，圖10比較了不同方法對MPD的不同值的執(zhí)行時間。MPD是決定信任者與被信任者之間最大距離的參數(shù)?；谠搮?shù)，重復(fù)使用信任傳播式(12)來計算用戶u與其他用戶之間的信任。從圖中可以看出，隨著傳播距離的增加，其它方法的效率急劇下降，所提方法的在不同傳播距離下執(zhí)行時間最短，該方法優(yōu)勢隨著距離的增加而變得更加明顯。

4 結(jié)束語

本文針對傳統(tǒng)推薦系統(tǒng)存在的局限，提出了一種基于重要性的信任感知推薦方法，該方法的研究重點是一種基于項目重要性的信任度量。本文方法分為兩個關(guān)鍵階段，在離線階段，項目采用混合蛙跳算法(SFLA)，對用戶的重要性是根據(jù)用戶的人口統(tǒng)計特征來衡量的，以此可以實現(xiàn)用戶偏好的動態(tài)變化。在線階段根據(jù)活動用戶的信任鄰居的偏好為其生成top-n推薦列表。實驗結(jié)果表明，通過與幾種最新推薦方法的比較，在預(yù)測精度和預(yù)測質(zhì)量上，提出的方法優(yōu)于其它方法。