基于粗糙集規則提取的協同過濾推薦算法

任永功，張云鵬，張志鵬

（遼寧師范大學計算機與信息技術學院，遼寧 大連 116000）

1 引言

進入互聯網時代以來，人們能夠獲取的信息資源愈加豐富，這些信息資源在方便人們生活的同時也帶來了一定的問題，人們需要花費更多的時間和精力去搜索對他們有用的信息，因此“信息超載（information overload）”所帶來的問題越來越嚴重。推薦系統（RS,recommendation system）[1]能夠有效地解決信息超載問題，通過為用戶推薦滿足其需求的對象，實現個性化服務。

協同過濾（CF,collaborative filtering）[2]是目前推薦系統領域應用最廣泛且最成功的推薦技術之一。協同過濾就是根據用戶模型找到與之匹配的信息，然后將這些信息推薦給用戶，或者建立具有相似興趣的用戶群，在用戶群中進行信息推薦。協同過濾通常分為 2 類：基于用戶的協同過濾（UBCF,user-based collaborative filtering）和基于物品的協同過濾（IBCF,item-based collaborative filtering）[3]。基于用戶的協同過濾技術隨著用戶數量的增加，其算法時間復雜度不斷加大，具有一定的缺陷；基于物品的協同過濾技術是目前研究的熱點方向。

在實際應用中，用戶和物品數量不斷增加，導致數據稀疏程度增大，從而使協同過濾推薦算法的準確性降低[4]。對于這一問題，國內外眾多研究者開展了大量工作，給出一些解決辦法，可以概括為4 類。1)填充矩陣：使用用戶-物品矩陣行和列的加權平均值、眾數、中位數等對稀疏矩陣進行填充，以改善數據的稀疏性[5]，這種方法雖然對稀疏數據改善直觀、顯著，但對空值的預測會產生較大偏差，影響后續計算的準確性。2)新相似性方法：有效利用用戶評分數據中所包含的各種有用信息，計算用戶或物品之間的相似度，與傳統的相似性計算方法相比，這種方法具有更高的穩定性，但它并沒有從根本上改變評分矩陣的稀疏程度，導致推薦質量改善程度有限[6]。3)推薦結果融合：將不同方法計算出的用戶對物品喜愛程度進行綜合，根據綜合結果對用戶進行推薦，與單一推薦結果的計算方法相比，這種方法可以提高推薦質量[7]，但其計算結果的可解釋性差，方法的準確性會受到融合機制的影響。4)基于內容的方法：通過建立用戶描述文件和物品內容文件，把最符合用戶描述的物品內容匹配給用戶[8]，但很多物品內容是非結構化的，難以對內容進行分析，導致該方法使用受限。

針對現有方法的缺點，本文提出一種基于粗糙集規則提取的協同過濾推薦算法，該算法首先通過提取用戶屬性、物品屬性和用戶對物品的評分，構建決策表，利用粗糙集理論對決策表進行約簡，依次求出表中每一條規則的核值，通過核值決策規則，找出所有決策規則的約簡，提取規則；然后根據規則對未評分的用戶進行評分，有效填充評分矩陣中的缺失值，緩解協同過濾算法在相似度計算階段由于數據稀疏性引起的推薦問題。最后，在MovieLens 數據集上與已有的3 種推薦算法進行對比分析，實驗結果表明，相比于已有的算法，本文算法具有更大的優越性。

2 相關工作

隨著數據量的急劇增加，網站中用戶和物品數量越來越多，很多用戶通常只會對自己所喜歡的物品進行認真準確的評分，導致可以用來計算用戶-物品之間相似度的數據非常有限，甚至經常會出現2 個用戶或2 個物品之間沒有共同評分，相似度無法計算，從而使推薦系統的質量難以保證。因此，如何解決好數據稀疏性問題顯得越來越重要。

針對上述問題，國內外眾多研究者從不同角度展開一系列研究，并給出一系列解決辦法。部分研究者從填充矩陣的角度出發，提出將用戶對未評分物品的評分設為一個固定缺省值，或者設為用戶的平均評分[5]，以緩解矩陣的稀疏性問題。鄧愛林等[9]提出一種基于項目評分預測（IRP,item rating prediction）的協同過濾算法。IRP 使用基于物品的協同過濾算法對用戶進行預測評分，然后對用戶評分項中的評分空值進行填充，在填充后的數據集上對用戶之間的相似度進行計算。鄭荔平等[10]提出了一種基于粗糙集的協同過濾算法，首先利用用戶評分數量和用戶的評分值對用戶進行分類，然后利用粗糙集屬性約簡的方法剔除對用戶分類影響較小的物品，形成更小的用戶-物品評分矩陣，以降低數據的稀疏性和規模。張鋒等[11]按照用戶評分向量交集大小選取候選鄰居集合，使用BP 神經網絡預測用戶對物品的評分，緩解候選鄰居評分數據的稀疏性問題。

部分研究者有效利用用戶評分數據中所包含的各種有用信息，計算用戶或物品之間的相似度，孟桓羽等[12]通過建立基于圖的評分數據模型，將傳統的協同過濾算法與圖計算及改進的KNN 算法結合，提出一種基于圖和K 近鄰模型的協同過濾推薦算法。冷亞軍等[13]提出一種兩階段最近鄰選擇（TPNS,two-phase neighbor selection）算法。TPNS首先計算用戶之間的近鄰傾向性，將近鄰傾向性較高的用戶組合為初始近鄰集合；接著按照初始近鄰集合計算目標用戶和其他用戶之間的等價關系相似性，修正目標用戶的初始近鄰集合，獲得最近鄰集合。于洪等[14]根據用戶時間權重值的大小和用戶對新項目的偏愛程度，在充分考慮用戶、標簽、項目屬性、時間等信息基礎上，獲得個性化的預測評分值公式。朱敬華等[15]提出了融合用戶相似性、地理位置相似性和信任關系的混合推薦模型。

上述改進方法在一定程度上緩解了稀疏性對推薦準確性的影響，但還不能直觀、準確地改善稀疏數據，并且對已有評分信息的利用還很不充分，基于此，本文提出一種基于粗糙集規則提取的協同過濾算法。

3 粗糙集規則提取的協同過濾算法

由于現實生活中用戶-物品評分矩陣往往是稀疏的，基于物品的協同過濾算法無法產生較好的推薦。本文將粗糙集理論融入基于物品的協同過濾中，通過粗糙集理論提取規則，預先對用戶-物品評分矩陣中的空值進行有效的填充，緩解用戶-物品評分矩陣中數據稀疏性的問題，提高推薦的準確性。

3.1 粗糙集理論的規則提取

粗糙集（rough set）理論是Pawlak[16]在1982 年提出的一種能夠定量分析處理不精確、不一致、不完整信息與知識的數學工具。粗糙集理論方法能夠從決策表中提取經過屬性約簡和值約簡的規則，在保證決策表決策能力不變的情況下，去除冗余屬性，提供簡潔并且正確的決策規則。

利用粗糙集理論提取規則的過程即為對決策表進行值約簡的過程。首先，刪除決策表中的冗余屬性，即對決策表進行屬性約簡，屬性約簡是利用粗糙集理論挖掘規則的關鍵，屬性約簡的結果將直接影響規則挖掘的結果[17]。其次，對約簡后的決策表進行值約簡。決策表中每一條實例均可視為一條規則，冗余屬性值也包含在其中。決策規則的約簡是將每條規則中的不必要條件分別進行消除，針對每條決策規則依次刪除冗余屬性值，以便使規則最小化。決策規則相對于決策表而言，它的形式更加簡潔，又盡可能地保留了決策表中的信息。

粗糙集基于不可分辨關系，給出知識表達系統的模型，設知識表達系統S=(U,A,Va,f)，其中，U表示對象的非空有限集合，稱為論域；A表示屬性的非空有限集合；Va表示屬性a∈A的屬性值的取值范圍，即屬性a的值域；f:UA→Va是一個信息函數，它為每個對象的各種屬性賦予一個信息值，即對任意a?A,x?U，都有f(x,a)?Va。知識表達系統也叫作信息系統，也可用S=(U,A)表示，其中，U={u1,u2,...,un}，A={a1,a2,...,an}。A中的元素稱為屬性，C∪D=A，C∩D=?，C稱為條件屬性集，D稱為決策屬性集。決策表是同時具有條件屬性集和決策屬性集的知識表達系統。

在知識表達系統S=(U,A,Va,f)中，設R∈A，則不可分辨關系IND(R)={(x,y)∈U2|a(x)=a(y),a∈R}，不可分辨關系實際上就是一種等價關系。

粗糙集利用上、下近似集逼近不精確對象，為推理不精確知識提供了新思路。對于?X?U，有RX={x∈U|[x]R?x} 表示X的下近 似 ；={x∈U|[x]R∩X≠?}表示X的上近似。其中[x]R表示包含元素X∈U的R等價類，R是U上的一個等價關系；posR(x)=RX稱為X的R正域，negR(x)=U-X稱為X的R負域。posR(x)或RX是根據知識R判斷U中一定屬于X的元素的集合；根據知識R判斷U中有可能屬于X的元素的集合；negR(x)是根據知識R判斷U中一定不屬于X的元素的集合。

在知識發現和信息系統分析等領域，知識約簡有著重要的應用意義。知識能否進行約簡取決于知識之間的依賴性，這種依賴性所賦予的知識的重要性往往是知識約簡的啟發式信息。核是所有約簡計算的基礎，核包含在所有約簡之中，在知識約簡中，核是不能消去的知識特征的集合。令C和D為等價關系族，R為不可分辨關系，若pos(c-|R|)(D)=pos(c)(D)，則稱R為C中D不必要的，否則R為C中D必要的。C中所有D必要的原始關系構成的集合稱為C的D核，簡稱為核，記作coreD(C)。

3.2 粗糙集規則提取的協同過濾算法

本文首先對數據進行填充，利用粗糙集理論提取規則，對未被用戶評分的物品進行評分，構建新的用戶-物品評分矩陣，根據新評分矩陣計算物品之間相似度，最后，利用加權求和的方法對物品進行預測評分，并為用戶進行推薦，具體步驟如下。

1)對用戶-物品評分表進行填充。建立決策表S=(U,A)，A中包含用戶屬性、物品屬性和評分信息，其中用戶屬性和物品屬性為條件屬性，物品評分為決策屬性。根據決策表，刪除具有相同條件屬性和決策屬性的集合，得到新的決策表S1=(U1,A)。在S1中尋找等價關系族，令C和D為等價關系族，R是不可分辨關系，若pos(c-|R|)(D)=pos(c)(D)，則刪除R，得到決策表S2=(U1,A1)，對其中每一條U1，依次去掉一個屬性值，若沒有出現與該規則不一致的規則，則刪除該屬性值，依次求出表中每一條規則的核值，得到核值表。通過核值表的核值決策規則，找出所有決策規則的約簡，提取決策規則。根據決策規則，提取用戶屬性、物品屬性和評分信息，構建評分表，對原始的用戶-物品評分表進行填充。

2)計算物品之間相似度。2 個物品之間相似性計算的基本思想是先分離出所有對這2 個物品進行評分的用戶，然后根據相似性計算技術計算這2 個物品之間的相似性。本文選用余弦相似性計算方法，這種方法將2 個物品作為m維空間中的2 個矢量，并用這2 個矢量之間夾角的余弦值定義2 個物品之間的相似度。

其中，“·”表示2 個矢量之間的點積，分子為2個物品評分矢量的內積，分母為2 個物品矢量模的乘積。

3)預測評分。通過排列物品之間的相似性，找到物品i的鄰居集合，通過目標用戶u對物品i鄰居的評分值進行加權求和，得到最終的預測結果。

其中，S(i)表示物品i的k近鄰集合，sim(i,j)表示物品i和物品j之間的相似度，和分別表示物品i和物品j所有評分的均值，ru,j表示用戶u對物品j的實際評分。

4)產生推薦。通過預測評分，將用戶對物品的喜愛程度進行排列，將排在前面的物品推薦給用戶。

算法1粗糙集規則提取的協同過濾算法

輸入用戶-物品評分表

輸出為目標用戶推薦的N個物品

3.3 算法分析

傳統基于物品的協同過濾算法，對于物品相似度迭代計算只需要進行一次，沒有反復的迭代計算。假設用戶-物品評分矩陣中有n個物品，那么，傳統的基于物品的協同過濾算法的時間復雜度為O(n2)。

從算法描述中能夠看出，本文算法可以分為3個部分。第一部分，通過粗糙集理論對決策表進行約簡；第二部分，計算物品之間相似度；第三部分，預測評分。算法的時間開銷主要來源于前2 個部分。在通過粗糙集理論對決策表進行約簡時，要把每n個項目的m個屬性依次進行刪除并計算，因此，時間復雜度為O(mn)；在計算物品相似度階段，對于物品相似度迭代計算只需要計算一次，并沒有反復的迭代計算，時間復雜度為O(n2)。因此，本文算法的時間復雜度為O(mn)+O(n2)。但在實際計算的過程中，物品的屬性個數m并不會很大，所以本文算法的時間復雜度為O(n2)。相對于傳統的相似度計算算法，也需要迭代物品的個數，時間復雜度為O(n2)。因此本文算法在原有算法的基礎上沒有產生更高的消耗。

4 實驗及結果分析

本節通過實驗分析，驗證所提推薦算法的性能。

4.1 實驗數據集和評價指標

為了評價算法的性能，本文采用MovieLens 數據集中2 個不同規模的數據集來進行實驗。

1)MovieLens-100K 數據集。該數據集包含了943 個用戶對1 682 部電影的10 萬次評分，其中每位用戶至少對20 部電影進行過評分，評分采用5級評分制。

2)MovieLens-1M 數據集。該數據集包含了6 040 個用戶對3 952 部電影的100 萬次評分，其中每位用戶至少對20 部電影進行過評分，評分采用5 級評分制。

本文使用交叉驗證來確定模型的有效性，并對得到的結果進行分析。將原始數據集按照4:1 隨機劃分為2 個互補子集，并選取80%為訓練集，20%為測試集。首先對訓練集進行分析，然后驗證對測試集影響。為了減少可變性，本文使用不同的劃分進行多輪交叉驗證，并對每次驗證的結果進行平均，本文實驗進行了五重交叉驗證。

為了衡量所提方法的性能，本文使用了平均絕對誤差（MAE,mean absolute error）、均方根誤差（RMSE,root mean squared error ）和精度（Precision）作為評估指標。MAE 和RMSE 指標顯示了預測與實際值之間的平均誤差，這些值越低，表示推薦系統的推薦效果越好。MAE 和RMSE 分別定義為

其中，ri,j表示用戶i對物品j的實際評分，r'i,j表示用戶i對物品j的預測評分，N表示測試集中包含的評分數量。

Precision 表示推薦系統為用戶推薦的物品中用戶實際喜歡的物品所占的比例，比例越大，說明算法推薦精度越高。Preci sion 定義為

其中，R(u)表示根據用戶在訓練集上的行為給用戶做出的推薦列表；T(u)表示用戶在測試集上的行為列表，即用戶喜歡的商品；絕對值表示列表長度。

4.2 本文實驗結果和相關方法對比

為了驗證本文所提算法對推薦性能的影響，在相同的相似度計算條件下，將本文算法 RECF（rough sets rule extraction collaborative filtering）與下述3 種算法進行比較。

1)基于物品的協同過濾（IBCF,item-based collaborative filtering）算法[3]。只利用評分信息，通過度量物品間余弦相似度，進而基于物品最近鄰進行預測推薦。

2)固定缺省值的評分填充算法[5]。將用戶對未評分物品的評分設為一個固定的缺省值，本文設為物品的平均評分（MVCF,mean value collaborative filtering），利用物品歷史評分信息，計算物品平均評分，對評分矩陣進行填充，然后采用與IBCF 相同的策略進行預測推薦。

3)基于粗糙集的協同過濾（RSCF,rough set collaborative filtering）算法[10]。利用用戶評分數量和用戶的評分值，對用戶進行分類，利用粗糙集屬性約簡的方法剔除對用戶分類影響較小的物品，形成更小的用戶-物品評分矩陣，然后采用與IBCF 相同的策略進行預測推薦。

本文選取鄰居數為20、25、30、35、40、45，分別對上述3 種算法以及本文所提算法的MAE 和RMSE 進行計算。計算結果如表1 和表2 所示。

圖1 展示了在MovieLens-100K 數據集下4 種算法的結果比較。圖2 展示了在MovieLens-1M 數據集下4 種算法的結果比較。實驗結果表明，本文算法相比于另外3 種算法具有較好的推薦結果，證明了通過粗糙集理論預先進行規則提取，能有效解決數據稀疏性對推薦系統造成的負面影響。

本文選取推薦列表長度為4、6、8、10，鄰居數為20、30、40、50、60，分別對4 種算法的推薦精度進行計算，表1 展示了在MovieLens-100K 數據集下4 種算法Precision 的結果比較。表2 展示了在MovieLens-1M 數據集下4 種算法Precision 的結果比較。當推薦長度一定時，隨著鄰居數量的增長，4 種算法的推薦精度總體上呈下降趨勢，當鄰居數量和推薦長度一定時，本文算法的推薦精度大多都高于另外3 種算法。

表1 MovieLens-100K 數據集下4 種算法推薦Precision 比較

表2 MovieLens-1M 數據集下4 種算法推薦Precision 比較

4.3 實驗結果對比分析

由于數據的稀疏性，IBCF 不能給出準確的預測；MVCF 參考的是大多數人平均水平的建議，不能進行較好的填充，也無法給出較好的預測；RSCF雖然能刪除一些低質量的評分，對推薦結果有一定的改進，但遇到沒有歷史評分的物品或用戶便沒有辦法為其進行推薦；本文算法通過粗糙集理論進行規則提取，預先對物品進行評分，可以在解決稀疏性問題的同時，一定程度上解決冷啟動問題。相比于另外3 種對比算法，本文算法在3 個指標上都有更好的結果，說明將粗糙集理論引入協同過濾推薦算法中，通過粗糙集理論預先進行規則提取，能有效解決數據稀疏性對推薦系統所造成的負面影響。

圖1 4 種算法在MovieLens-100K 數據集的結果比較

圖2 4 種算法在MovieLens-1M 數據集的結果比較

從圖1 和圖2 中MAE 和RMSE 的變化趨勢可以看出，4 種算法的MAE 和RMSE 都會隨著鄰居數量的變化而變化，當鄰居數量選取較少時，由于只參考了少數人的意見，導致預測評分受個人因素影響較大，不能給出準確的預測；當鄰居數量選取過多時，由于加入較多低質量評分，會對預測產生負面的影響，導致MAE 和RMSE 有所升高，但這些低質量評分對推薦系統的影響會隨著鄰居數量的增多而趨于穩定。通過以上分析可以得出，當鄰居數量選取適中時，推薦系統的性能最好。由表1和表2 可以看出，本文算法的推薦精度總體上高于另外3 種算法。當推薦長度一定時，推薦精度大多會隨著鄰居數量的增多而降低；當鄰居數量較小時，本文算法可以達到比較理想的推薦效果。

綜上，本文所提算法相比于另外3 種算法在MAE、RMSE 和Precision 這3 個指標中均有明顯提高，驗證了將粗糙集理論提取的規則引入推薦系統中，能正確對較稀疏的用戶-物品矩陣進行填充，更好地反映用戶偏好，從而提高推薦系統的性能，為用戶提供更加準確的推薦。

5 結束語

本文分析了協同過濾算法中數據稀疏性對推薦質量的影響。由于現有的改進方法還不能充分利用已有的評分信息直觀、準確地改善稀疏數據，本文提出一種基于粗糙集規則提取的協同過濾算法，通過粗糙集理論進行規則提取并填充稀疏矩陣，緩解數據稀疏性問題。實驗表明，本文算法有效提升了稀疏數據中的推薦精度。本文利用用戶及物品的一些屬性信息，對評分進行填充，忽略用戶社交關系、時間信息等，在未來工作中，要將更多信息融入推薦過程中，以進一步改善協同過濾算法的推薦性能。