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

蔣　雯

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

?

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

蔣雯

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 用戶估值填充公式

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

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

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

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

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

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

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

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

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

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

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

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

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

2）因?yàn)橐粋€(gè)項(xiàng)目可能同時(shí)歸屬于多個(gè)種類。假定在項(xiàng)目t所屬的個(gè)種類中，每個(gè)種類分?jǐn)偟脑u分值相等。其中，f t（）?C是項(xiàng)目t所屬種類的子集。

3）概念層次樹中的各路徑結(jié)點(diǎn)的分值自底向上逐層遞減。因?yàn)樵诟拍顚哟螛渲校窂浇Y(jié)點(diǎn)越往下項(xiàng)目種類就越細(xì)致。而數(shù)據(jù)填充時(shí)，評估的種類越細(xì)致，受用戶關(guān)注程度就越高。所以，在概念層次樹中路徑結(jié)點(diǎn)越往下分配的評分值自然就越多。

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

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

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

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

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

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

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

2.4 生成最近鄰居

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

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

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

2.5 形成推薦

3　實(shí)驗(yàn)設(shè)計(jì)

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

3.1 實(shí)驗(yàn)對比指標(biāo)

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

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

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

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

3.2 實(shí)驗(yàn)方法

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

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

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

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

3.3 實(shí)驗(yàn)結(jié)論及分析

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

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

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

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

通過以上對比分析，顯然所提出的基于概念分層的估計(jì)填充推薦算法能夠提高推薦質(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ù)稀疏性問題，提出了一種基于概念分層的估值填充推薦改進(jìn)算法，在項(xiàng)目種類上確認(rèn)“用戶評分尺度”和“商品受歡迎度”，以提高項(xiàng)目推薦結(jié)果的質(zhì)量。最后，通過實(shí)驗(yàn)驗(yàn)證了該算法的可行性以及有效性。然而該問題依然有很大的研究空間，比如:

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

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

3）所提出的算法主要是利用用戶-項(xiàng)目評分?jǐn)?shù)據(jù)等顯性信息進(jìn)行推薦，在隱性數(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)評價(jià)指標(biāo)綜述［J］.電子科技大學(xué)學(xué)報(bào)，2012，41（2）:163-175.

［5］姜錦虎，李皓，袁帥.基于多智能體系統(tǒng)的分布式信譽(yù)機(jī)制研究［J］.管理工程學(xué)報(bào)，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

基金項(xiàng)目:福建省中青年教師教育科研項(xiàng)目（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