蔣　雯

（福州理工學(xué)院管理工程系，福建福州350506）

?

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

蔣雯

（福州理工學(xué)院管理工程系，福建福州350506）

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

關(guān)鍵詞：協(xié)同過濾；項目推薦；概念分層；估值填充

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

1　協(xié)同過濾推薦概述

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

1）建立用戶模型。協(xié)同過濾算法中用戶評分?jǐn)?shù)據(jù)可以用一個m×n維的用戶-項目矩陣Rst描述，

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

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

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

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

圖1　協(xié)同過濾推薦過程Fig.1 Process of collaborative filtering

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

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

2.1 用戶估值填充公式

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

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

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

概念分層是一種廣泛應(yīng)用于數(shù)據(jù)挖掘領(lǐng)域的數(shù)據(jù)分類方法。它定義一個映射序列，將低層概念映射到更一般的較高層概念［6］。它實質(zhì)上是以層次的形式、偏序的關(guān)系來表示數(shù)據(jù)或概念。一般用樹結(jié)構(gòu)來表示，其中樹的節(jié)點代表概念，樹枝代表偏序關(guān)系。概念分層可以由領(lǐng)域?qū)＜胰斯さ靥峁?，或根?jù)數(shù)據(jù)分布的統(tǒng)計分析自動生成。

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

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

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

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

2.3 評分?jǐn)?shù)據(jù)轉(zhuǎn)換模型

一般而言，協(xié)同過濾推薦電子商務(wù)系統(tǒng)只提供用戶-項目評分?jǐn)?shù)據(jù)，并沒有用戶-項目種類評分資料。如何將用戶-項目評分轉(zhuǎn)換為用戶-項目種類評分?jǐn)?shù)據(jù)成為問題關(guān)鍵所在，因此，建立了數(shù)據(jù)轉(zhuǎn)換模型。

2.3.1 評分?jǐn)?shù)據(jù)轉(zhuǎn)換的假定前提

為了使該模型更科學(xué)地進行數(shù)據(jù)轉(zhuǎn)換，設(shè)計了以下假定前提:

1）每位用戶對所有項目種類的總評分都是S。統(tǒng)一總評分的設(shè)定保證了各用戶在同一評分范圍內(nèi)對所有項目種類進行評分預(yù)測。

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

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

2.3.2 評分?jǐn)?shù)據(jù)轉(zhuǎn)換過程

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

1）對于稀疏的評分矩陣的空白項rst，在進行估值填充時，按照分?jǐn)偙壤龔腟中分享評分。即，空白項 rst獲取的 Rsct的初始分值 S（ct），其公式為:

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

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

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

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

2.4 生成最近鄰居

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

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

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

2.5 形成推薦

3　實驗設(shè)計

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

3.1 實驗對比指標(biāo)

（1）準(zhǔn)確率（100%）指標(biāo)

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

（2）查全率（100%）指標(biāo)

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

3.2 實驗方法

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

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

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

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

3.3 實驗結(jié)論及分析

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

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

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

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

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

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

4　結(jié)語

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

1）將理論運用到實際電商網(wǎng)站，通過線上反饋進行進一步的算法優(yōu)化。

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

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

參考文獻(xiàn)：

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

［2］工業(yè)和信息化部.電子商務(wù)“十二五”發(fā)展規(guī)劃［R］.北京:工業(yè)和信息化部，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］朱郁筱，呂琳媛.推薦系統(tǒng)評價指標(biāo)綜述［J］.電子科技大學(xué)學(xué)報，2012，41（2）:163-175.

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

［6］Tan P N，Steinbach M，Kumar V.數(shù)據(jù)挖掘?qū)д摚跰］.北京:人民郵電出版社，2006.

（責(zé)任編輯：肖錫湘）

中圖分類號：TB23

文獻(xiàn)標(biāo)志碼：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，F(xiàn)uzhou Polytechnic College，F(xiàn)uzhou 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