一種基于用戶興趣概念格的推薦評(píng)分預(yù)測(cè)方法

朵 琳，楊 丙

(昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院，昆明 650500)

1 概 述

近年來(lái)，隨著互聯(lián)網(wǎng)和信息技術(shù)的飛速發(fā)展，推薦系統(tǒng)[1-3]被廣泛應(yīng)用于電子商務(wù)網(wǎng)站中.推薦系統(tǒng)支持消費(fèi)者從過(guò)載的信息中選擇所需的產(chǎn)品或服務(wù).協(xié)同過(guò)濾(collaborative filtering，CF)[4]是最常用的推薦算法，被廣泛應(yīng)用于文學(xué)和工業(yè)領(lǐng)域，它利用用戶的評(píng)分來(lái)構(gòu)建用戶-用戶或項(xiàng)目-項(xiàng)目的相似度指標(biāo)，并識(shí)別用戶或項(xiàng)目的鄰域來(lái)生成推薦.

然而,CF推薦算法存在這樣的問(wèn)題:當(dāng)用戶-項(xiàng)目評(píng)分矩陣非常稀疏，用戶只對(duì)少數(shù)項(xiàng)目進(jìn)行評(píng)分時(shí)，CF推薦算法的推薦質(zhì)量極大地受到影響[5].Luo等人[6]提出將用戶相似度分為局部用戶相似度和全局用戶相似度兩部分來(lái)解決數(shù)據(jù)稀疏問(wèn)題.此外，Patra等人[7]使用全局相似度和一個(gè)新的局部相似度來(lái)解決稀疏性的問(wèn)題.他們使用Bhattacharya系數(shù)作為全局相似度的度量，利用數(shù)據(jù)庫(kù)中所有可用的評(píng)分來(lái)計(jì)算用戶-用戶或項(xiàng)目-項(xiàng)目之間的相似度.張俊等人[8]根據(jù)興趣向量來(lái)計(jì)算用戶的興趣相似性度，并引入專(zhuān)家信任度來(lái)進(jìn)行評(píng)分預(yù)測(cè)填充,以此降低數(shù)據(jù)稀疏性.林建輝等人[9]針對(duì)傳統(tǒng)的相似性度量只考慮用戶對(duì)項(xiàng)目評(píng)分的問(wèn)題，提出通過(guò)用戶之間的相似性與信任關(guān)系來(lái)查找“最近鄰”，有效地緩解了稀疏性問(wèn)題.Guo等人[10]提出通過(guò)多類(lèi)型輔助反饋信息來(lái)解決稀疏性問(wèn)題.Xu等人[11]通過(guò)嵌入在用戶評(píng)論中的形容詞特征來(lái)解決數(shù)據(jù)稀疏性問(wèn)題.

本文提出了一種基于用戶興趣概念格的推薦評(píng)分預(yù)測(cè)(Recommendation Rating Prediction Based on User Interest Concept Lattice,簡(jiǎn)稱(chēng)RRP-UICL)方法.該方法通過(guò)用戶興趣概念格將“最近鄰”分為直接“最近鄰”和間接“最近鄰”兩類(lèi).然后計(jì)算目標(biāo)用戶與直接“最近鄰”和間接“最近鄰”的相似度，最后，將計(jì)算所得的相似度值用于預(yù)測(cè)目標(biāo)用戶的不可見(jiàn)項(xiàng)目評(píng)分值，解決了傳統(tǒng)CF推薦算法的稀疏性問(wèn)題.

2 相關(guān)介紹

2.1 基于鄰域的協(xié)同過(guò)濾

基于鄰域的協(xié)同過(guò)濾推薦算法[12]的主要目標(biāo)是基于目標(biāo)用戶的鄰居用戶向其推薦項(xiàng)目，根據(jù)計(jì)算相似度對(duì)象的不同而劃分為基于用戶和基于項(xiàng)目?jī)深?lèi)算法.本文的研究基礎(chǔ)為基于用戶的算法，主要包括查找“最近鄰”和預(yù)測(cè)推薦兩個(gè)步驟.

2.1.1 查找“最近鄰”

相似度度量可以找到目標(biāo)用戶的“最近鄰”用戶，相似度度量考慮已評(píng)分項(xiàng)目的評(píng)分，來(lái)計(jì)算目標(biāo)用戶和其他用戶之間的相似度.

1)修正的余弦相似性

修正的余弦相似性(Adjusted Cosine,ACos)采用式(1)計(jì)算用戶u與用戶v之間的相似度.

(1)

2) 皮爾遜相關(guān)

皮爾遜相關(guān)(Pearson Correlation,PC)采用式(2)計(jì)算用戶u與用戶v之間的相似度.

(2)

3) 受約束的皮爾遜相關(guān)

受約束的皮爾遜相關(guān)(Constrained PC,CPC)采用式(3)計(jì)算用戶u與用戶v之間的相似度.

(3)

式中，rmed為評(píng)分等級(jí)的中位數(shù).

4) Jaccard

采用式(4)計(jì)算用戶u與用戶v之間的Jaccard相似度.

(4)

式中，|Iu∩Iv|為用戶u和用戶v共同評(píng)價(jià)過(guò)的項(xiàng)目個(gè)數(shù).

2.1.2 預(yù)測(cè)推薦

向目標(biāo)用戶推薦項(xiàng)目，首先需要預(yù)測(cè)未評(píng)分項(xiàng)目的評(píng)分，然后推薦前N個(gè)高評(píng)分項(xiàng)目[13].使用式(5)預(yù)測(cè)目標(biāo)用戶u對(duì)項(xiàng)目i的評(píng)分.

(5)

式中，Sim(u,v)為用戶u與用戶v的相似度，Nu為用戶u的“最近鄰”集合.

2.2 概念格

形式概念分析(FCA,formal concept analysis)理論[14-16]是由R Wille提出的，它是一種數(shù)據(jù)分析和知識(shí)表示的方法.形式概念分析的兩大基本內(nèi)容是形式背景和形式概念，其基本的數(shù)據(jù)結(jié)構(gòu)是概念格[17].

對(duì)于一個(gè)形式背景K=(G,M,I)，其中，G是對(duì)象集合，M是屬性集合，I是G和M之間的一個(gè)關(guān)系，I?G×M.在形式背景的對(duì)象集A?G和屬性集B?M之間定義如下兩個(gè)映射：

f(A)={b∈M|?a∈A,aIb}
g(B)={a∈G|?b∈B,aIb}

其中，f(A)是A中所有對(duì)象所共有的屬性，g(B)是B中所有屬性所共有的對(duì)象.

由形式背景K生成的概念格中的每個(gè)節(jié)點(diǎn)Z=(A,B)是一個(gè)二元組，滿足：A?G，B?M，f(A)=B，g(B)=A，則二元組Z稱(chēng)為形式概念，其中，A是形式概念Z的外延，記作Ext(Z)，B是它的內(nèi)涵，記作Int(Z).

若Z1=(A1,B1)和Z2=(A2,B2)是概念格中兩個(gè)形式概念，滿足A1?A2(B1?B2),則稱(chēng)Z1為Z2的亞概念，Z2為Z1的超概念，記為Z1≤Z2，其中“≤”為一個(gè)偏序關(guān)系.

3 RRP-UICL方法

RRP-UICL方法的主要步驟如圖1所示.從圖1可以看出，RRP-UICL方法主要分為兩個(gè)模塊:一是“最近鄰”模塊，二是推薦模塊.下面將介紹這兩個(gè)模塊的細(xì)節(jié)部分.

圖1 RRP-UICL方法模型Fig.1 RRP-UICL method model

3.1 “最近鄰”模塊

3.1.1 構(gòu)造用戶興趣概念格

在這一階段，首先將用戶對(duì)系統(tǒng)中已有項(xiàng)目的所有評(píng)分組成的評(píng)分矩陣R轉(zhuǎn)化為二進(jìn)制矩陣.在二進(jìn)制矩陣中，評(píng)分較高的項(xiàng)目被認(rèn)為是用戶感興趣的項(xiàng)目.本研究是在1～5的評(píng)分等級(jí)上面進(jìn)行的，則將評(píng)分4和5視為最高評(píng)分，其值在二進(jìn)制矩陣中設(shè)置為<1>，其他值均設(shè)置為<0>.該二進(jìn)制矩陣可以看作是一個(gè)用戶興趣形式背K=(U,I,R)，其中U是所有用戶集合，I是所有項(xiàng)目集合，R是U和I之間的一個(gè)關(guān)系.然后通過(guò)用戶興趣形式背景K可以構(gòu)造用戶興趣概念格[18]，用Lc表示K的概念格，圖2給出了實(shí)例分析.

為了加快推薦過(guò)程，需要?jiǎng)h除用戶興趣概念格Lc中一些多余的形式概念，本文定義了兩個(gè)條件對(duì)形式概念進(jìn)行刪除：

常愛(ài)蘭愛(ài)上馱子的事其實(shí)我們嶺北周村的人是不大看好的。村上的周老相公就奚落過(guò)幾次，說(shuō)常愛(ài)蘭愛(ài)馱子，肯定是愛(ài)馱子的錢(qián)。馱子有錢(qián)么？周老相公就說(shuō)，你們看，馱子到嶺北周村來(lái)幾年了，從來(lái)沒(méi)有回過(guò)家，那么他的錢(qián)用到哪里去，咱們村，噢，不用說(shuō)村了，就是整個(gè)嶺北鎮(zhèn)就那么屁股點(diǎn)大的地方，他去哪里用錢(qián)，他一年彈棉花彈到頭了，錢(qián)肯定是有不少的。而常愛(ài)蘭呢，她有什么？她就是一個(gè)寡婦，今年寡這個(gè)，明年寡那個(gè)，寡上誰(shuí)誰(shuí)倒霉。

對(duì)于一個(gè)形式概念Z：

1)若?Z∈Lc，使得|Ext(Z)|=1，即可刪除Z.

2)若?Z,Z′∈Lc，使得Int(Z)∈Int(Z′)，即可刪除Z.

圖3顯示了圖2(c)刪除多余形式概念后的結(jié)果，為最終的用戶興趣概念格Lc.

3.1.2 劃分直接“最近鄰”和間接“最近鄰”

在這一階段，首先，需要查找目標(biāo)用戶的“最近鄰”.然后，通過(guò)用戶興趣概念格來(lái)確定與目標(biāo)用戶最相似的用戶.最后，將“最近鄰”與最相似用戶進(jìn)行比較，以此來(lái)劃分直接“最近鄰”和間接“最近鄰”.下面將詳細(xì)介紹該過(guò)程：

在基于鄰域的協(xié)同過(guò)濾方法中，對(duì)相同項(xiàng)目具有相似偏好的用戶被視為“最近鄰”用戶.本文也采用了協(xié)同過(guò)濾方法來(lái)查找目標(biāo)用戶的“最近鄰”，選擇與目標(biāo)用戶u興趣相近的若干用戶作為“最近鄰”Nu.以圖2(a)的評(píng)分矩陣為例，若向目標(biāo)用戶1推薦項(xiàng)目5，從評(píng)分矩陣中可以看出，用戶U2、U3和U6均參與了對(duì)項(xiàng)目5的評(píng)分，這些用戶都有可能向目標(biāo)用戶1推薦項(xiàng)目5，則目標(biāo)用戶1的Nu為{U2,U3,U6}.

圖2 構(gòu)造用戶興趣概念格實(shí)例分析Fig.2 Example analysis of constructing user interest concept lattice

然后，查找與目標(biāo)用戶u最相似的用戶MNu，在用戶興趣概念格Lc中，采用由底部到頂部的搜索方法來(lái)查找MNu，MNu的定義如下：

MNu={Ext(Z)|max(|Int(Z)∩I′u|),Z∈Lc}

圖3 最終的用戶興趣概念格Fig.3 Final user interest concept lattice

3.2 推薦模塊

確定了目標(biāo)用戶的直接“最近鄰”和間接“最近鄰”后，就可以計(jì)算用戶之間的相似度，以此來(lái)推算出目標(biāo)用戶對(duì)某個(gè)項(xiàng)目的感興趣程度，感興趣程度可以通過(guò)預(yù)測(cè)評(píng)分值來(lái)表示.

3.2.1 計(jì)算相似度

對(duì)于直接“最近鄰”用戶，由于直接“最近鄰”用戶的評(píng)分在評(píng)分預(yù)測(cè)過(guò)程中影響更加明顯，他們與目標(biāo)用戶直接相關(guān)，所以，直接“最近鄰”用戶與目標(biāo)用戶之間的相似度值被設(shè)置為<1>.

對(duì)于間接“最近鄰”用戶，本文提出了一種新的方法來(lái)計(jì)算間接“最近鄰”用戶與目標(biāo)用戶之間的相似度.在基于用戶的協(xié)同過(guò)濾推薦方法中，采用式(6)計(jì)算用戶u與用戶v的相似度.

(6)

式中，Iu為間接“最近鄰”用戶u評(píng)分過(guò)的項(xiàng)目集，Iv為目標(biāo)用戶v評(píng)分過(guò)的項(xiàng)目集，|Iu|為用戶u評(píng)分過(guò)的項(xiàng)目個(gè)數(shù).從式(6)可以看出，本文提出的相似度計(jì)算方法只需要使用用戶的評(píng)分項(xiàng)目集，避免了用戶之間的共同評(píng)分項(xiàng)目的影響，從而，解決數(shù)據(jù)稀疏問(wèn)題.

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

計(jì)算了相似度后，接下來(lái)是對(duì)評(píng)分值進(jìn)行預(yù)測(cè).

首先，計(jì)算推薦項(xiàng)目的平均評(píng)分.對(duì)于推薦項(xiàng)目i，采用式(7)計(jì)算平均評(píng)分.

(7)

然后，預(yù)測(cè)推薦項(xiàng)目的評(píng)分，使用式(8)預(yù)測(cè)目標(biāo)用戶u對(duì)項(xiàng)目i的評(píng)分Ru.i.式中，a是評(píng)分集合的最高評(píng)分.

(8)

4 實(shí)驗(yàn)結(jié)果

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

本文使用的數(shù)據(jù)集為MOVIELENS 100 K，MovieLens數(shù)據(jù)集是評(píng)價(jià)推薦算法有效性最常用的數(shù)據(jù)集之一.該數(shù)據(jù)集包含了943名用戶對(duì)1682部電影的所有評(píng)分，在1～5的評(píng)分等級(jí)范圍內(nèi)有100000個(gè)匿名評(píng)分，每個(gè)用戶至少對(duì)20部電影進(jìn)行了評(píng)級(jí).如果評(píng)分為1意味著用戶不喜歡這部電影，評(píng)分為2意味著用戶對(duì)這部電影的喜愛(ài)程度很低，評(píng)分為3意味著用戶對(duì)這部電影持中立態(tài)度，評(píng)分為4意味著用戶喜歡這部電影，評(píng)分為5意味著用戶非常喜歡該部電影.

原始數(shù)據(jù)集中可用評(píng)級(jí)的密度偏大，由于該模型需要在不同高度稀疏的數(shù)據(jù)集上進(jìn)行測(cè)試，因此從MovieLens數(shù)據(jù)集中隨機(jī)的抽取300個(gè)用戶對(duì)500個(gè)隨機(jī)電影的評(píng)分，生成了兩個(gè)樣本數(shù)據(jù)集.然后，將兩個(gè)樣本數(shù)據(jù)集中的可用評(píng)級(jí)隨機(jī)更改為零，以形成兩個(gè)稀疏度不同的數(shù)據(jù)集.數(shù)據(jù)集-1的可用評(píng)級(jí)為3026，稀疏度約為98%，數(shù)據(jù)集-2的可用評(píng)級(jí)為1656，稀疏度約為99%.

4.2 評(píng)價(jià)指標(biāo)

本文采用平均絕對(duì)誤差(mean absolute error,MAE)[19]和均分根誤差(rooted mean squared error,RMSE)[20]來(lái)評(píng)價(jià)所提方法的準(zhǔn)確性.

MAE表示預(yù)測(cè)評(píng)級(jí)與實(shí)際評(píng)級(jí)之間的偏差，可用于度量預(yù)測(cè)的精度.通常情況下，MAE越小，預(yù)測(cè)的精度越高，MAE的計(jì)算使用公式(9).

(9)

其中，n表示預(yù)測(cè)的所有評(píng)分的個(gè)數(shù)，ri表示項(xiàng)目i的實(shí)際評(píng)分值，pi表示項(xiàng)目i的預(yù)測(cè)評(píng)分值.

另一個(gè)與MAE相似的度量是均方根誤差(RMSE)，該值表示預(yù)測(cè)評(píng)級(jí)與實(shí)際評(píng)級(jí)之間的平均誤差，它反映了實(shí)際值與預(yù)測(cè)值之間的偏離程度，RMSE越小，預(yù)測(cè)的精度越高，使用公式(10)計(jì)算.

(10)

4.3 結(jié) 果

為了驗(yàn)證RRP-UICL方法的有效性，將RRP-UICL方法與傳統(tǒng)的基于修正的余弦相似性度量(UCF-ACos)、基于皮爾遜相關(guān)度量(UCF-PC)、基于受約束的皮爾遜相關(guān)度量(UCF-CPC)、基于Jaccard度量(UCF-Jaccard)四種方法分別在數(shù)據(jù)集-1和數(shù)據(jù)集-2上進(jìn)行了實(shí)驗(yàn)，對(duì)五種方法進(jìn)行了比較，并給出了精度指標(biāo).

當(dāng)推薦項(xiàng)目為5、10、15、20時(shí)，對(duì)于數(shù)據(jù)集-1和數(shù)據(jù)集-2兩種不同稀疏度的數(shù)據(jù)集，五種方法的MAE隨推薦項(xiàng)目變化的實(shí)驗(yàn)結(jié)果分別見(jiàn)圖4和圖5.

從圖4和圖5中可以看出，在5種方法中，RRP-UICL方法在兩個(gè)數(shù)據(jù)集中的MAE值都小于其余的4種方法.隨著稀疏度的增加，UCF-ACos方法和UCF-PC方法的MAE值明顯地在增大，受數(shù)據(jù)稀疏的影響較大.UCF-CPC方法和UCF-Jaccard方法的MAE值變化不是很明顯.RRP-UICL方法在整個(gè)稀疏度實(shí)驗(yàn)范圍內(nèi)均取得了較小的MAE值，在數(shù)據(jù)集稀疏度較高的情況下有明顯的優(yōu)勢(shì).總結(jié)來(lái)說(shuō)，在稀疏場(chǎng)景下，本文方法比傳統(tǒng)的協(xié)同過(guò)濾方法有更好的預(yù)測(cè)精度.

圖4 數(shù)據(jù)集-1不同方法的MAE值比較Fig.4 MAE value comparison of the different methods for dataset-1

圖5 數(shù)據(jù)集-2不同方法的MAE值比較Fig.5 MAE value comparison of the different methods for dataset-2

同樣的，在5、10、15和20這4個(gè)不同的推薦項(xiàng)目下，圖6和圖7分別展示了5種方法在數(shù)據(jù)集-1和數(shù)據(jù)集-2中的RMSE值隨推薦項(xiàng)目變化的實(shí)驗(yàn)結(jié)果.

圖6 數(shù)據(jù)集-1不同方法的RMSE值比較Fig.6 RMSE value comparison of the different methods for dataset-1

從圖6和圖7中可以看出，與MAE值相似，RRP-UICL方法在兩個(gè)數(shù)據(jù)集中的RMSE值也都小于其余的4種方法.當(dāng)數(shù)據(jù)集的稀疏度不斷增大時(shí)，RRP-UICL方法仍然保持較低的RMSE值，而UCF-ACos方法和UCF-PC方法的RMSE值卻在不斷的變大，從圖7中可以清楚地看到，UCF-ACos方法和UCF-PC方法的RMSE值比RRP-UICL方法大很多.UCF-CPC方法和UCF-Jaccard方法的RMSE值增加幅度不是很大，但也明顯大于RRP-UICL方法的RMSE值.因此，RRP-UICL方法比傳統(tǒng)的協(xié)同過(guò)濾方法有更好的預(yù)測(cè)精度.

圖7 數(shù)據(jù)集-2不同方法的RMSE值比較Fig.7 RMSE value comparison of the different methods for dataset-2

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

本文提出的RRP-UICL方法，解決了傳統(tǒng)的基于協(xié)同過(guò)濾推薦算法中存在的數(shù)據(jù)稀疏的問(wèn)題.該方法考慮到目標(biāo)用戶的“最近鄰”用戶在評(píng)分預(yù)測(cè)過(guò)程中的影響程度不同，所以通過(guò)用戶興趣概念格將“最近鄰”分為直接“最近鄰”和間接“最近鄰”兩類(lèi).然后采用不同方法計(jì)算直接“最近鄰”和間接“最近鄰”與目標(biāo)用戶的相似度.最后，通過(guò)計(jì)算所得的相似度值來(lái)預(yù)測(cè)目標(biāo)用戶的不可見(jiàn)項(xiàng)目評(píng)分值.在真實(shí)的電影評(píng)分?jǐn)?shù)據(jù)集上，驗(yàn)證了RRP-UICL方法對(duì)稀疏數(shù)據(jù)提高預(yù)測(cè)準(zhǔn)確度的有效性.在今后的工作中，我們將研究概念格的構(gòu)造算法，在本來(lái)稀疏用戶-項(xiàng)目興趣數(shù)據(jù)集上高效地構(gòu)造概念格，從而提高算法的效率.