基于概念格的稀疏數(shù)據(jù)協(xié)同過濾校正自然噪聲方法

朵 琳, 楊 丙

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

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

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

1 預(yù)備知識(shí)

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

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

1.2 協(xié)同過濾推薦

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

(1)

1.3 概念格

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

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

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

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é)點(diǎn), 其中A是形式概念Z的外延, 記為Ext(Z),B是其內(nèi)涵, 記為Int(Z).

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

2 方 法

2.1 自然噪聲檢測

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

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

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

3) 強(qiáng)評(píng)級(jí)集合Su={r(u,i)|?i∈I,r(u,i)≥vu}.

同理, 可將每個(gè)項(xiàng)目i評(píng)級(jí)分組到下列集合Wi,Ai,Si中:

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

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

3) 強(qiáng)評(píng)級(jí)集合Si={r(u,i)|?u∈U,r(u,i)≥vi}.

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

表1 用戶-項(xiàng)目分類

類似地, 將用戶和項(xiàng)目分為弱類、 平均類、 強(qiáng)類和可變類. 用戶、 項(xiàng)目和評(píng)級(jí)被分類后, 通過分析類之間存在的矛盾尋找有噪聲的評(píng)級(jí). 表2定義了用戶-項(xiàng)目-評(píng)級(jí)類之間的關(guān)系.

表2 用戶-項(xiàng)目-評(píng)級(jí)類之間的關(guān)系

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

算法1自然噪聲檢測.

輸入： 含自然噪聲的用戶-項(xiàng)目評(píng)級(jí)矩陣;

輸出： 自然噪聲集合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為強(qiáng)用戶;

16) else;

17)u為可變用戶;

18) 重復(fù)以上循環(huán), 對(duì)每個(gè)項(xiàng)目i進(jìn)行分類;

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

20) if (u為弱用戶,i為弱項(xiàng)目,r(u,i)不為弱評(píng)級(jí));

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

22) if (u為平均用戶,i為平均項(xiàng)目,r(u,i)不為平均評(píng)級(jí));

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

24) if (u為強(qiáng)用戶,i為強(qiáng)項(xiàng)目,r(u,i)不為強(qiáng)評(píng)級(jí));

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

2.2 自然噪聲校正

圖1 用戶-項(xiàng)目評(píng)級(jí)矩陣Fig.1 User-item rating matrix

圖2 用戶-項(xiàng)目評(píng)級(jí)形式背景Fig.2 User-item rating context

圖3 概念格Fig.3 Concept lattice

圖4 外延格Fig.4 Epitaxial lattice

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

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

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

(2)

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

(3)

算法2CFSD-CL預(yù)測.

輸入： 用戶-項(xiàng)目評(píng)級(jí)矩陣;

輸出： 預(yù)測評(píng)級(jí)值;

2) 基于用戶-項(xiàng)目評(píng)級(jí)矩陣, 構(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 時(shí)間復(fù)雜度分析

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

3 實(shí)驗(yàn)設(shè)置

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

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

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

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

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

(4)

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

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

(5)

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

4.1 用戶-項(xiàng)目分類

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

4.2 噪聲評(píng)級(jí)修正

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

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

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

4.3 性能比較

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

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

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

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

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

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

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

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