基于概念分層的估值填充推薦算法

蔣　雯

（福州理工學院管理工程系，福建福州350506）

?

基于概念分層的估值填充推薦算法

蔣雯

（福州理工學院管理工程系，福建福州350506）

摘要：為解決傳統協同過濾算法中存在的數據稀疏性問題，在原有估值公式的基礎上對傳統的協同過濾算法進行改進，提出一種基于概念分層的估值填充推薦的改進算法，并對此算法進行仿真實驗。結果表明，該算法在稀疏數據集上有著良好的推薦效果。

關鍵詞：協同過濾；項目推薦；概念分層；估值填充

協同過濾推薦系統是電子商務網站提高經濟效益的有效技術手段，能夠主動快速地挖掘出潛在的購買用戶，并幫助他們找到感興趣的商品，在增加網站的商品銷量的同時也增加了用戶對商品網站的忠誠度。但隨著電子商務規模的不斷壯大，用戶和項目數據急劇增加，用戶評分數據變得極端稀疏［1］，嚴重影響著推薦結果的準確性。針對數據稀疏問題，研究學者已提出了眾多解決方法，但至今沒有一種方法能夠徹底解決此問題。Sarwar［2］等人提出了利用單值分解的方法對原始稀疏數據進行數據處理，這種方法能夠提高推薦效果，但是在分解過程中卻造成了數據的遺失。BP神經網絡的填充方法、聚類技術近年來也被用于解決數據稀疏性問題，但這些方法的最大缺點是可擴展性問題，其計算量會隨著數據量增大而急劇增加，推薦速度變慢。鑒于此，針對稀疏性問題，協同過濾推薦算法依然有很大的改進空間。

1　協同過濾推薦概述

協同過濾推薦（collaborative filtering）［3］又稱為社會過濾。Goldberg等學者于1992年首次提出了該概念。協同過濾推薦的關鍵在于假設目標客戶的興趣可以根據其他類似客戶的興趣進行預測推薦，突出了人與人之間的協作。傳統的協同過濾推薦算法是指基于用戶的協同過濾算法，其基本思想是通過計算用戶間相似度，找出目標用戶的鄰居用戶，基于最近鄰居的評分數據對用戶未購買的項目進行預測評分，并向目標用戶產生推薦。整個算法可以概括為3個階段:建立用戶模型、獲取最近鄰居、產生推薦列表［4］。

1）建立用戶模型。協同過濾算法中用戶評分數據可以用一個m×n維的用戶-項目矩陣Rst描述，

式中m是用戶數，n是項目數，rst是用戶s對項目t的評分，Rs表示用戶us在n維項目空間上的評分向量，以表1為例。

表1　協同過濾舉例Tab.1 Exam p les of collaborative filtering

2）獲取最近鄰居。利用用戶-項目評分矩陣Rst計算用戶之間的相似度，找出目標用戶的最近鄰居集合。

3）產生推薦。根據最近鄰居已購買（瀏覽或評價）但目標用戶us尚未發現的項目形成候選項目集合，然后預測目標用戶對候選項目的評分，產生top-N項目推薦集，進而產生推薦，如圖1所示。

圖1　協同過濾推薦過程Fig.1 Process of collaborative filtering

2　基于概念分層的估計填充商品推薦算法

鑒于數據稀疏性問題對提高推薦算法的準確性有重大影響，提出了基于概念分層的估值填充商品推薦算法。首先，在原有的用戶估值公式基礎上利用概念分層思想進行了改進，使得該算法在各項目種類上確認“用戶打分尺度”和“商品受歡迎度”，并生成新的用戶模型；然后，利用Pearson相關性方法［2］進行用戶相似性計算，結合top-N推薦產生用戶鄰居集合；再從鄰居的歷史記錄找出候選項目集，通過計算用戶對候選項目集的興趣度，并按降序排列，結合top-N進行項目推薦；最后，利用仿真實驗驗證了該算法在稀疏數據集上有著良好的推薦效果。

2.1 用戶估值填充公式

針對用戶評分矩陣的數據稀疏性問題，原有估值填充公式是在“用戶評分尺度”和“商品受歡迎度”的基礎上提出來的［5］，填充項rst為，

公式（2）在一定程度上能夠解決用戶評分矩陣數據稀疏性問題，但在填充過程中并未考慮項目所屬類別。項目種類不同，用戶感興趣程度不同，用戶打分尺度也不盡相同。因此，利用該估值公式填充矩陣產生的推薦結果不夠精準。即，用戶us對與項目t所屬類別相差比較大的其他項目的評分不具參考性，若以用戶us對所有項目的平均打分尺度來衡量用戶us，則對商品t的評分明顯不夠精準。

2.2 基于概念分層的用戶估值填充

概念分層是一種廣泛應用于數據挖掘領域的數據分類方法。它定義一個映射序列，將低層概念映射到更一般的較高層概念［6］。它實質上是以層次的形式、偏序的關系來表示數據或概念。一般用樹結構來表示，其中樹的節點代表概念，樹枝代表偏序關系。概念分層可以由領域專家人工地提供，或根據數據分布的統計分析自動生成。

考慮維location（地點）的概念分層。location（地點）的城市值包括溫哥華、多倫多、紐約和芝加哥。每個city（城市）可以映射到它們所屬的省或州。比如，溫哥華可以映射到不列顛哥倫比亞；芝加哥映射到伊利諾伊；這些省和州又可以映射到它們所屬的國家，如加拿大或美國。這些映射形成維location（地點）的概念分層，將低層概念（城市）映射到更一般的較高層概念（國家）。維location（地點）的概念分層樹詳見圖2。

圖2　維location（地點）的概念分層樹Fig.2 Concept hierarchy tree of location

針對稀疏性問題，原有估值填充公式預測結果不夠精準。為避免其缺陷，文中對算法進行了改進，運用基于概念層次樹的用戶-項目種類估值填充數據矩陣。改進的思路大致為:利用概念分層思想引入了項目分類，在項目種類上確認“用戶評分尺度”和“商品受歡迎度”，以完成更加精準的估值計算，進而提高商品推薦質量。改進后的基于概念分層評分估值填充公式如下，

其中，將用戶us對項目t所屬種類ct的評分作為用戶評分尺度Rsct；

2.3 評分數據轉換模型

一般而言，協同過濾推薦電子商務系統只提供用戶-項目評分數據，并沒有用戶-項目種類評分資料。如何將用戶-項目評分轉換為用戶-項目種類評分數據成為問題關鍵所在，因此，建立了數據轉換模型。

2.3.1 評分數據轉換的假定前提

為了使該模型更科學地進行數據轉換，設計了以下假定前提:

1）每位用戶對所有項目種類的總評分都是S。統一總評分的設定保證了各用戶在同一評分范圍內對所有項目種類進行評分預測。

2）因為一個項目可能同時歸屬于多個種類。假定在項目t所屬的個種類中，每個種類分攤的評分值相等。其中，f t（）?C是項目t所屬種類的子集。

3）概念層次樹中的各路徑結點的分值自底向上逐層遞減。因為在概念層次樹中，路徑結點越往下項目種類就越細致。而數據填充時，評估的種類越細致，受用戶關注程度就越高。所以，在概念層次樹中路徑結點越往下分配的評分值自然就越多。

2.3.2 評分數據轉換過程

總評分S分配到概念層次樹各結點（即各項目種類）的過程如下:

1）對于稀疏的評分矩陣的空白項rst，在進行估值填充時，按照分攤比例從S中分享評分。即，空白項 rst獲取的 Rsct的初始分值 S（ct），其公式為:

2）將獲取的用戶評分尺度Rsct的初始分值S（ct）按照一定規則分配到概念層次樹各路徑的各結點，各結點獲取的分值s（pt） ，其公式為:

3）匯總種類ct中的各結點獲取的分值，即可得出用戶評分尺度Rsct的最終分值。

4）重復上述步驟1～3獲取Rs′ct的最終分值。

5）重復上述步驟1～4，再結合基于概念層次的估值公式完成整個稀疏矩陣的填充工作。

2.4 生成最近鄰居

協同過濾算法的關鍵在于尋找與目標用戶興趣愛好相似的鄰居，根據鄰居已經瀏覽或評價或購買但目標用戶還未發現的項目向目標用戶產生推薦。在尋找鄰居的過程中:首先，利用Pearson相關方法計算用戶之間的相似度，并將計算出的相似度按照從高到低的順序進行排列，形成目標用戶的相似度集合；然后，根據預定的相似度閾值或預定的鄰居個數進行top-N選擇，以確定目標用戶us的鄰居集合。

利用Pearson相關方法計算的用戶ui和用戶uj的相似度sim（ui，uj），公式如下:

其中，Iij為用戶ui和用戶uj共同評分過的項目集合；Rick或Rjck為用戶ui或uj獲取的對項目所屬種類ck的評分。

2.5 形成推薦

3　實驗設計

利用MovieLens網站www.grouplens.org提供的數據集，并參考eBay網中的電影分類構建概念層次樹進行實驗，用戶對電影的評分值為1～5的整數。實驗中，將提出的基于概念分層的估計填充商品推薦算法CF1與原有的評估填充算法CF從推薦準確性以及推薦全面性角度進行了對比分析。

3.1 實驗對比指標

（1）準確率（100%）指標

用均值絕對誤差（mean absolute error，MAE）衡量整個檢驗集合中的平均誤差，公式如下:式中，CI′s?CIs為top-N=3時進行推薦的項目集1合；pst為預測的用戶us對項目it∈CI′s的評分；rst為用戶us對項目it的真實評分。

（2）查全率（100%）指標

為了對推薦算法的全面性進行驗證，引入了查全率，主要驗證推薦項目占用戶實際感興趣項目的比重。表示對用戶us的推薦與其真實感興趣相重疊的項目集合。

3.2 實驗方法

提取的實驗數據針對的是評分項目數為0～160時的用戶。因為在該區間內，用戶數隨著用戶評分項目的增加而增加，該區間的數據具有層次性，實驗效果比較明顯。式中，TRs為用戶us的真實感興趣的項目集合，在測試數據集中體現為評分≥4的項目集合；

圖3　用戶評分分布圖Fig.3 User rating distribution

實驗中，為簡便計算，分別從用戶評分的項目數位于0～40、40～80、80～120、120～160區間內的用戶集合中各選取3位代表用戶，4個區間總共產生12位代表用戶。

然后，對每位代表用戶在各自的評分項目數區間內，采用4折交叉驗證技術［6］，產生4次推薦，取其平均值作為該代表用戶的推薦評估結果；按照同樣方法，計算出12位代表用戶在各評分項目數區間內的推薦評估結果；最后，將這12位代表用戶的推薦評估結果平均化，以作為推薦算法在該用戶集合（用戶評分的項目數≤160）上的最終推薦評估結果。

3.3 實驗結論及分析

將提出的基于概念分層的估計填充商品推薦算法CF1與原有的評估填充算法CF從推薦準確性以及推薦全面性角度進行了對比分析。

圖4　算法CF1與CF的均值絕對誤差MAE對比結果Fig.4 The com parison between mean absolute error （M AEtive）results of algorithm CF1 and CF

如圖4所示，所提出的基于概念分層的估計填充商品推薦算法CF1的均值絕對誤差MAE相比算法CF更小一些；并且，隨著用戶評分項目的增多，算法CF1與CF的MAE曲線均呈現下降趨勢（用戶評分項目越多，項目種類也就越多，尋找的鄰居也就越準確，從而算法的均值絕對誤差也就越小）。

從圖5可知，所提出的推薦算法CF1的查全率相比算法CF更高一些。并且，隨著用戶評分項目的增多，算法CF1與CF的查全率曲線均呈現上升趨勢（用戶評分項目越多，項目種類也就越多，算法的查全率也就越高）。

通過以上對比分析，顯然所提出的基于概念分層的估計填充推薦算法能夠提高推薦質量，對于數據稀疏問題起到了一定的改善作用。

圖5　算法CF1與CF的查全率對比結果Fig.5 The comparison of recall rate between the results of algorithm CF1 and CF

4　結語

針對推薦系統中的數據稀疏性問題，提出了一種基于概念分層的估值填充推薦改進算法，在項目種類上確認“用戶評分尺度”和“商品受歡迎度”，以提高項目推薦結果的質量。最后，通過實驗驗證了該算法的可行性以及有效性。然而該問題依然有很大的研究空間，比如:

1）將理論運用到實際電商網站，通過線上反饋進行進一步的算法優化。

2）數據填充雖然在一定程度上解決了數據稀疏性問題，但不能解決高維矩陣的降維問題，即數據可擴展性問題仍待解決。

3）所提出的算法主要是利用用戶-項目評分數據等顯性信息進行推薦，在隱性數據挖掘方面尚待研究。

參考文獻：

［1］Samak A C.An experimental study of reputation with heterogeneous goods［J］.Decision Support Systems，2013，54（2）: 1134-1149.

［2］工業和信息化部.電子商務“十二五”發展規劃［R］.北京:工業和信息化部，2012.

［3］Goldberg D，Nichols D，Oki BM，etal.Using collaborative filtering toweave an information tapestry［J］.Communications of the ACM，1992，35（12）:61-70.

［4］朱郁筱，呂琳媛.推薦系統評價指標綜述［J］.電子科技大學學報，2012，41（2）:163-175.

［5］姜錦虎，李皓，袁帥.基于多智能體系統的分布式信譽機制研究［J］.管理工程學報，2013，27（1）:77-87.

［6］Tan P N，Steinbach M，Kumar V.數據挖掘導論［M］.北京:人民郵電出版社，2006.

（責任編輯：肖錫湘）

中圖分類號：TB23

文獻標志碼：A

文章編號：1672-4348（2016）03-0302-05

doi：10.3969/j.issn.1672-4348.2016.03.017

收稿日期:2016-04-27

基金項目:福建省中青年教師教育科研項目（JAS150738）

作者簡介:蔣雯（1983-），女，福建漳州人，講師，碩士，研究方向:營銷管理。

A recommended algorithm of valuation filling based on concept hierarchy

Jiang Wen
（Management Engineering Department，Fuzhou Polytechnic College，Fuzhou 350506，China）

Abstract:To dealwith data sparseness problems in the traditional collaborative filtering algorithm，a new recommendation algorithm of valuation filling based on concept hierarchy was proposed through improving the traditional collaborative filtering algorithm.Simulation experiments of the new recommendation algorithm were conducted.The results indicate that the proposed algorithm has favourable recommendation effect in sparse data sets and can improve the quality of recommendations. Keywords:collaborative filtering；projects recommendation；concept hierarchy；valuation filling