朵 琳，楊 丙

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

1 概 述

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

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

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

2 相關(guān)介紹

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

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

2.1.1 查找“最近鄰”

相似度度量可以找到目標(biāo)用戶的“最近鄰”用戶，相似度度量考慮已評分項目的評分，來計算目標(biāo)用戶和其他用戶之間的相似度.

1)修正的余弦相似性

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

(1)

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

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

(2)

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

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

(3)

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

4) Jaccard

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

(4)

式中，|Iu∩Iv|為用戶u和用戶v共同評價過的項目個數(shù).

2.1.2 預(yù)測推薦

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

(5)

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

2.2 概念格

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

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

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

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

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

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

3 RRP-UICL方法

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

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

3.1 “最近鄰”模塊

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

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

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

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

對于一個形式概念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)用戶的“最近鄰”.然后，通過用戶興趣概念格來確定與目標(biāo)用戶最相似的用戶.最后，將“最近鄰”與最相似用戶進(jìn)行比較，以此來劃分直接“最近鄰”和間接“最近鄰”.下面將詳細(xì)介紹該過程：

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

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

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

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

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

3.2 推薦模塊

確定了目標(biāo)用戶的直接“最近鄰”和間接“最近鄰”后，就可以計算用戶之間的相似度，以此來推算出目標(biāo)用戶對某個項目的感興趣程度，感興趣程度可以通過預(yù)測評分值來表示.

3.2.1 計算相似度

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

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

(6)

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

3.2.2 預(yù)測評分值

計算了相似度后，接下來是對評分值進(jìn)行預(yù)測.

首先，計算推薦項目的平均評分.對于推薦項目i，采用式(7)計算平均評分.

(7)

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

(8)

4 實驗結(jié)果

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

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

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

4.2 評價指標(biāo)

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

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

(9)

其中，n表示預(yù)測的所有評分的個數(shù)，ri表示項目i的實際評分值，pi表示項目i的預(yù)測評分值.

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

(10)

4.3 結(jié) 果

為了驗證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)行了實驗，對五種方法進(jìn)行了比較，并給出了精度指標(biāo).

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

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

圖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個不同的推薦項目下，圖6和圖7分別展示了5種方法在數(shù)據(jù)集-1和數(shù)據(jù)集-2中的RMSE值隨推薦項目變化的實驗結(jié)果.

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

從圖6和圖7中可以看出，與MAE值相似，RRP-UICL方法在兩個數(shù)據(jù)集中的RMSE值也都小于其余的4種方法.當(dāng)數(shù)據(jù)集的稀疏度不斷增大時，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é)同過濾方法有更好的預(yù)測精度.

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

5 結(jié)束語

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