朵 琳, 楊 丙

(昆明理工大學 信息工程與自動化學院, 昆明 650504)

近年來, 推薦系統(tǒng)[1-3]被廣泛應用于電子商務網(wǎng)站中. 推薦系統(tǒng)能從大量的信息中獲取有用的數(shù)據(jù), 幫助用戶找到所需的產(chǎn)品或服務. 但目前的推薦系統(tǒng)仍存在許多問題, 如數(shù)據(jù)稀疏[4-5]、 自然噪聲和冷啟動[6-7]等. 在推薦系統(tǒng)領域中關于自然噪聲的研究目前較少. O’Mahony等[8]提出了先從用戶-項目評級矩陣中消除自然噪聲, 然后應用協(xié)同過濾預測未評級項目級別的方法解決自然噪聲, 但評級數(shù)據(jù)的稀疏性隨之增大, 因此, 消除自然噪聲的方法不能提供更高的推薦精度； Toledo等[9]對自然噪聲進行了檢測, 然后應用Pearson相關系數(shù) (Pearson’s correlation coefficient, PCC)[10]重新預測方法校正自然噪聲; Year等[11]提出了將模糊模型與重新預測方法相結(jié)合, 用于管理自然噪聲, 之后又提出了群組推薦系統(tǒng)[12-13], 通過重新預測、 模糊分析、 全局和局部噪聲管理的方法解決自然噪聲. 上述方法都使用PCC重新預測方法解決自然噪聲, 只適用于密集的數(shù)據(jù)集, 但在稀疏數(shù)據(jù)集中, PCC所涉及的共同評級較少或不存在, 導致預測值的精度較低[14], 反而會增加噪聲問題.

為解決目前PCC重新預測方法在稀疏數(shù)據(jù)中預測精度較低的問題, 本文提出一種基于概念格的稀疏數(shù)據(jù)協(xié)同過濾(collaborative filtering of sparse data based on concept lattice, CFSD-CL)校正自然噪聲的方法, 解決了推薦系統(tǒng)中的自然噪聲和數(shù)據(jù)稀疏性問題, 同時, 由于概念格在數(shù)據(jù)處理和分析方面的優(yōu)勢, 該方法更直觀.

1 預備知識

1.1 推薦系統(tǒng)中的自然噪聲

推薦系統(tǒng)數(shù)據(jù)集中的噪聲分為惡意噪聲和非惡意噪聲(自然噪聲), 惡意噪聲是由外部代理有意引入, 從而產(chǎn)生有偏差的推薦結(jié)果. 自然噪聲是由用戶不自覺引入的, 也會影響推薦結(jié)果. 目前已有很多在推薦系統(tǒng)模型中去除惡意噪聲的方法, 但在自然噪聲方面的研究較少. 自然噪聲在推薦數(shù)據(jù)集出現(xiàn)的原因可能有兩方面[15]： 1) 用戶興趣隨著時間改變; 2) 用戶引入不精確的評級. 導致第二個原因的因素有： 情緒狀態(tài)、 環(huán)境、 個人條件或社會影響. 由于自然噪聲由不同的來源產(chǎn)生, 所以自然噪聲的識別較困難.

1.2 協(xié)同過濾推薦

協(xié)同過濾推薦技術(shù)是一種常用的推薦技術(shù), 其通過計算相似度識別用戶或項目的鄰域[16], 并預測未評級項目的評級. 常用的相似度計算方法為PCC, 采用

(1)

1.3 概念格

形式概念分析(formal concept analysis, FCA)[17-19]是一種數(shù)據(jù)分析和知識表示的方法. 概念格[20]是FCA中的一個基本結(jié)構(gòu), 是數(shù)據(jù)分析與規(guī)則提取的有效工具, 廣泛應用于各領域.

定義1形式背景定義為一個三元組K=(G,M,I), 也稱為二元背景, 其中,G是對象集合,M是屬性集合,I是G和M之間的一個關系,I?G×M, ?g∈G及?m∈M, 若對象g和屬性m具有關系I, 則記為gIm.

定義2在形式背景的對象集A?G和屬性集B?M之間定義如下兩個映射：

V(A)={m∈M|?g∈A,gIm},D(B)={g∈G|?m∈B,gIm}.

若二元組Z=(A,B)滿足V(A)=B,D(B)=A, 則二元組Z稱為形式概念, 形式概念構(gòu)成了概念格中的節(jié)點, 其中A是形式概念Z的外延, 記為Ext(Z),B是其內(nèi)涵, 記為Int(Z).

定義3若(X1,B1),(X2,B2)是形式背景K的兩個概念, 并滿足(X1,B1)≤(X2,B2)?X1?X2(?B1?B1), 其中: “≤”為一個偏序關系;K的所有偏序集稱為概念格; (X1,B1)是(X2,B2)的子概念; (X2,B2)是(X1,B1)的父概念.

2 方 法

2.1 自然噪聲檢測

在自然噪聲檢測中, 首先將用戶和項目分為弱類、 平均類、 強類和可變類. 預先設置4個閾值ku,vu,ki,vi用于用戶和項目分類. 設U和I分別是用戶和項目集合, 通過閾值可將每個用戶u評級分組到下列集合Wu,Au,Su中:

1) 弱評級集合Wu={r(u,i)|?i∈I,r(u,i)≤ku};

2) 平均評級集合Au={r(u,i)|?i∈I,ku

3) 強評級集合Su={r(u,i)|?i∈I,r(u,i)≥vu}.

同理, 可將每個項目i評級分組到下列集合Wi,Ai,Si中:

1) 弱評級集合Wi={r(u,i)|?u∈U,r(u,i)≤ki};

2) 平均評級集合Ai={r(u,i)|?u∈U,ki

3) 強評級集合Si={r(u,i)|?u∈U,r(u,i)≥vi}.

本文研究在1～5的評分等級上進行, 將閾值ku和vu、ki和vi均設為2和4, 即1和2評級判為弱評級, 3評級判為平均評級, 4和5評級判為強評級, 用于所有用戶和項目的分類. 表1為用戶-項目分類, 根據(jù)表1的標準, 使用集合Wu,Au,Su或Wi,Ai,Si的基數(shù)對每個用戶或項目分類. 當用戶的弱評級基數(shù)大于等于其平均評級和強評級基數(shù)之和時, 他的評級在評級量表中就會偏到較低的一端, 則該用戶被認為是弱用戶.

表1 用戶-項目分類

類似地, 將用戶和項目分為弱類、 平均類、 強類和可變類. 用戶、 項目和評級被分類后, 通過分析類之間存在的矛盾尋找有噪聲的評級. 表2定義了用戶-項目-評級類之間的關系.

表2 用戶-項目-評級類之間的關系

檢測過程假設對來自推薦數(shù)據(jù)集的一個評級r(u,i), 如果用戶u的類和項目i的類屬于同一類, 則評級r(u,i)必屬于同一類評級. 如果不符合該條件, 則評級r(u,i)被標記為自然噪聲. 自然噪聲檢測算法步驟如下.

算法1自然噪聲檢測.

輸入： 含自然噪聲的用戶-項目評級矩陣;

輸出： 自然噪聲集合noise;

1)Wu={ },Au={ },Su={ },Wi={ },Ai={ }, noise={ }；

2) for (everyu∈U);

3) for (everyi∈I);

4) if (r(u,i)≤ku);

5) 將r(u,i)加入集合Wu;

6) else if (ki

7) 將r(u,i)加入集合Au;

8) else;

9) 將r(u,i)加入集合Su;

10) if (|Wu|≥|Au|+|Su|);

11)u為弱用戶;

12) else if (|Au|≥|Wu|+|Su|);

13)u為平均用戶;

14) else if (|Su|≥|Au|+|Wu|);

15)u為強用戶;

16) else;

17)u為可變用戶;

18) 重復以上循環(huán), 對每個項目i進行分類;

19) for (everyr(u,i));

20) if (u為弱用戶,i為弱項目,r(u,i)不為弱評級);

21) 將r(u,i)加入集合noise;

22) if (u為平均用戶,i為平均項目,r(u,i)不為平均評級);

23) 將r(u,i)加入集合noise;

24) if (u為強用戶,i為強項目,r(u,i)不為強評級);

25) 將r(u,i)加入到集合noise.

2.2 自然噪聲校正

圖1 用戶-項目評級矩陣Fig.1 User-item rating matrix

圖2 用戶-項目評級形式背景Fig.2 User-item rating context

圖3 概念格Fig.3 Concept lattice

圖4 外延格Fig.4 Epitaxial lattice

圖5 內(nèi)涵格Fig.5 Connotative lattice

在概念格中, 采用由頂部到底部的搜索方法, 還可以查找用戶u的評級項目范圍Iu, 其定義如下：

Iu={Int(Z)|u∈Ext(Z), max{|Int(Z)|},Z∈Lc}.

(2)

計算用戶u與用戶v的相似度. 其中:Iu表示用戶u的評級項目集合;Iv表示用戶v的評級項目集合; |Iu|和|Iv|表示評級項目的個數(shù);r(u,i)表示用戶u對項目i的評級. 由式(2)可見, 本文提出的相似度計算方法只需使用用戶的評級項目集合, 避免了用戶間共同評級項目的影響.

(3)

算法2CFSD-CL預測.

輸入： 用戶-項目評級矩陣;

輸出： 預測評級值;

2) 基于用戶-項目評級矩陣, 構(gòu)造概念格Lc；

3) for (everyZ∈Lc)；

4) if (i∈Int(Z) and max{|Ext(Z)|});

6) if (u∈Ext(Z) and max{|Int(Z)|});

7)Iu=Int(Z);

9) for (everyZ∈Lc);

10) if (v∈Ext(Z) and max{|Int(Z)|});

11)Iv=Int(Z);

2.3 時間復雜度分析

CFSD-CL校正自然噪聲方法的時間復雜度主要為算法1的自然噪聲檢測和算法2的CFSD-CL預測. 由算法1可知, 雙重嵌套循環(huán)時間復雜度與用戶-項目評級矩陣有關, 用Un表示用戶-項目評級矩陣中用戶的個數(shù), 用In表示用戶-項目評級矩陣中項目的個數(shù), 則雙重嵌套循環(huán)時間復雜度為O(Un×In). 單個循環(huán)時間復雜度與評級的個數(shù)有關, 用Rn表示評級的個數(shù), 則單個循環(huán)時間復雜度為O(Rn). 于是算法1的時間復雜度為max{O(Un×In),O(Rn)}. 在算法2中, 單個循環(huán)時間復雜度與概念格中形式概念的個數(shù)有關, 用Zn表示形式概念的個數(shù), 單個循環(huán)時間復雜度為O(Zn). 雙重嵌套循環(huán)主要用于計算相似度, 相似度的計算次數(shù)和目標用戶可能的最近鄰個數(shù)有關, 用Vn表示可能的最近鄰個數(shù), 則雙重嵌套循環(huán)的時間復雜度為O(Vn×Zn), 于是算法2的時間復雜度為max{O(Vn×Zn),O(Zn)}.

3 實驗設置

為驗證本文提出的CFSD-CL校正自然噪聲方法的有效性, 使用電影數(shù)據(jù)集MOVIELENS 100K進行實驗.

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

MOVIELENS 100K數(shù)據(jù)集包含943名用戶對1 682部電影的100 000個匿名評分, 分值為1～5. 用戶對電影的喜歡程度用分值大小表示, 評分為1表示用戶非常不喜歡該部電影, 評分為5表示用戶非常喜歡該部電影. 原始數(shù)據(jù)集中可用評級的密度較大, 由于該模型需在不同高度稀疏的數(shù)據(jù)集上進行測試, 因此從MOVIELENS數(shù)據(jù)集中隨機抽取300個用戶對500個隨機電影的評分, 生成了一個新的樣本數(shù)據(jù)集, 生成樣本數(shù)據(jù)集的可用評級數(shù)為11 328, 稀疏度約為92%. 隨后可用評級被隨機更改為零, 以形成稀疏度不同的數(shù)據(jù)集驗證本文算法的性能.

3.2 評價指標

由于需要通過預測精度評價算法的性能, 所以采用平均絕對誤差(mean absolute error , MAE)和均方根誤差(rooted mean squared error, RMSE)度量算法的預測精度. MAE表示預測用戶評級與實際用戶評級間的偏差, 可用于度量預測的精度. 通常情形下, MAE越小預測的精度越高, 計算公式為

(4)

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

均方誤差(MSE)的計算方法是將實際評分值和預測評分值之差的平方和除以測試集中的評分集合. RMSE通過取MSE的平方根得到, 其反映了實際值與預測值之間的偏離程度, RMSE越小預測的精度越高, 計算公式為

(5)

4 實驗結(jié)果及分析

4.1 用戶-項目分類

根據(jù)算法1對樣本數(shù)據(jù)集的用戶和項目進行分類, 結(jié)果如圖6所示. 由圖6可見, 在樣本數(shù)據(jù)集中, 10名用戶被劃分為弱用戶, 14名用戶為平均用戶, 225名用戶為強用戶, 有51名用戶未分類到任何類中； 同樣, 有68個弱項目, 42個平均項目, 296個強項目, 94個項目未被分到任何類中.

4.2 噪聲評級修正

采用CFSD-CL方法對樣本數(shù)據(jù)集中的自然噪聲進行校正的數(shù)量如圖7所示. 由圖7可見, 在樣本數(shù)據(jù)集中, 11 328個可用的評級中檢測出了821個噪聲評級, 7.25%的評級是有噪聲的. 利用噪聲校正算法, 有465個評級從平均校正為強, 306個評級從弱校正為強, 34個評級從弱校正為平均, 6個評級從平均校正為弱, 10個評級從強校正為平均.

圖6 樣本數(shù)據(jù)集用戶-項目分類Fig.6 Classification of users and items for sample dataset

圖7 樣本數(shù)據(jù)集修正評級數(shù)量Fig.7 Number of modified ratings for sample dataset

4.3 性能比較

為了驗證CFSD-CL校正自然噪聲方法的有效性, 將CFSD-CL校正自然噪聲方法和現(xiàn)有的PCC重新預測方法在數(shù)據(jù)集上分別進行實驗, 在最近鄰和稀疏度的影響下對MAE和RMSE值進行比較.

4.3.1 最近鄰的影響 先采用CFSD-CL校正自然噪聲方法和PCC重新預測方法對樣本數(shù)據(jù)集中的自然噪聲進行檢測并校正, 然后對未評級的項目進行預測. 當最近鄰數(shù)為5,7,9,11,13,15時, 分別對MAE和RMSE值進行比較, 結(jié)果分別如圖8和圖9所示. 由圖8和圖9可見, 兩種方法的MAE和RMSE值受最近鄰影響的變化趨勢相同, 本文方法的MAE和RMSE值均小于PCC重新預測方法, 因此, 本文提出的噪聲修正方法比PCC重新預測方法的性能更好, 預測精度更高.

圖8 不同最近鄰的MAE比較Fig.8 MAE comparison for different nearest neighbors

圖9 不同最近鄰的RMSE比較Fig.9 RMAE comparison for different nearest neighbors

4.3.2 稀疏度的影響 為了驗證本文方法在稀疏場景下的有效性, 本文將樣本數(shù)據(jù)集中的可用評級隨機更改為零, 以形成5個稀疏度不同的數(shù)據(jù)集, 稀疏度分別為92%,95%,97%,98%,99%. 然后將CFSD-CL校正自然噪聲方法和PCC重新預測方法分別在5個稀疏度不同的數(shù)據(jù)集上進行實驗, 最后分別比較不同方法的MAE和RMSE值, 結(jié)果分別如圖10和圖11所示. 由圖10和圖11可見, 隨著稀疏度的增加, 兩種方法的MAE和RMSE值不斷增加. 本文方法的MAE和RMSE值均小于PCC重新預測方法, 在稀疏度很高的情形下也有較大優(yōu)勢, 因此, 本文提出的自然噪聲校正方法優(yōu)于PCC重新預測方法.

圖10 不同稀疏度的MAE比較Fig.10 MAE comparison for different sparsity

圖11 不同稀疏度的RMSE比較Fig.11 RMSE comparison for different sparsity

綜上所述, 本文提出了一種CFSD-CL校正自然噪聲的方法, 解決了推薦系統(tǒng)中存在的自然噪聲和數(shù)據(jù)稀疏的問題. 本文加入了概念格的思想, 在預測評分值時能方便、 直觀地查找目標用戶的最近鄰范圍和用戶偏好.