基于PCA降維的協同過濾推薦算法

李遠博，曹 菡

(陜西師范大學 計算機科學學院,陜西 西安 710062)

基于PCA降維的協同過濾推薦算法

李遠博，曹 菡

(陜西師范大學 計算機科學學院,陜西 西安 710062)

在信息過載的時代，推薦系統通過分析用戶的歷史行為，為用戶興趣建模，主動給用戶推薦能夠滿足他們興趣和需求的信息,已經被廣泛應用于電子商務等多個領域。但是在推薦系統中，用戶評分數據極端稀疏，矩陣的稀疏性導致推薦算法在相似性計算時存在較大誤差，進而導致最近鄰居選擇的不準確，從而影響推薦質量。針對上面存在的問題，文中通過對評分矩陣采用PCA降維的方法，降低了評分矩陣的稀疏性，保留了最能代表用戶興趣的維數，使得相似性計算更加準確，保證了最近鄰居選擇的準確性，從而提高了推薦質量。實驗結果表明，在公開數據集上與傳統的協同過濾推薦算法相比較，文中提出的算法具有較高的準確度和覆蓋度。

主成分分析;降維;協同過濾;推薦算法

1 概 述

隨著人類進入到信息化時代，信息呈現出快速、爆炸式增長，信息出現過載。推薦系統[1]通過對用戶的歷史記錄的分析，為用戶建立興趣模型，主動給用戶推薦能夠滿足他們興趣和需求的信息。從電子商務、音樂視頻網站，到在線廣告和個性化閱讀，到處都是推薦系統的應用。

在推薦系統中，協同過濾(Collaborative Filtering，CF)[2]是應用最廣泛的個性化推薦算法。首先通過分析歷史數據，計算出用戶之間或者項目之間的相似度；其次根據相似度建立起近鄰關系[3]，然后在近鄰關系中，選擇與目標距離最近的用戶對項目的評分數據來預測目標用戶對特定項目的評分；最后針對目標用戶產生相應的推薦。

隨著電子商務信息規模的不斷擴大，數據量都在增加，針對以前的推薦系統，很少有用戶對項目進行評分，這就導致推薦系統評分數據的稀疏性[4]。對于任何一個優秀的推薦系統，用戶對項目的評分數據往往只占有一小部分，而未評分數據常常比用戶的已有評分更多，由于用戶之間選擇的差異也會加重數據的稀疏性。在傳統的向量空間模型中，評分矩陣的稀疏性對于推薦系統中使用的統計方法都會產生計算不準確的影響。在推薦系統中，用戶的最近鄰居就是通過統計學方法進行相似性計算，因此如何解決矩陣的稀疏性成為推薦系統的關鍵。

為了降低評分矩陣的稀疏性，早期Pirasteh等通過將電影的類型和導演信息進行填充，進而來降低矩陣的稀疏性問題[5]，該方法需要用戶額外評價電影類型和導演等信息；Wang等首先對用戶已經評分的數據進行聚類，然后結合Slope One算法來對未評分數據進行預測填充，以此來降低矩陣的稀疏性問題[6]；Pitsilis等首先使用已有的評分數據建立信任關系模型，進而來預測未評分的數據，通過該方法可以有效解決矩陣的稀疏性問題和冷啟動問題[7]，但是此方法并不是社會網中真正意義上的信任關系；文獻[8]中首先使用K-means算法對項目進行聚類分析，然后將聚類分類后的結果結合已評分的數據來計算用戶相似性；黃創光等針對傳統K近鄰算法中存在K固定這一缺陷，提出了利用不確定近鄰K來進行計算的最近鄰居推薦[9]等。

2004年美國《連線》雜志主編ChrisAnderson發表了題為《TheLongTail》一文[10]。作者認為，基于互聯網的銷售方式以及其他因素已經將媒體和娛樂產業推向后一種模式為主導的世界，那些不起眼的產品“長尾”吸引了大量的用戶，ChrisAnderson指出“你可以在長尾中找到任何想要的，有以前的舊專輯，他們仍然被人們懷念和喜愛并不斷涌現出新的粉絲；有現場制作的音樂，B面的內容，混錄版歌曲，設置封面；還有數千種風格流派不同的利基項目：例如整個TowerRecords唱片公司在80年代推崇的長發樂隊或節奏電子音樂”。在互聯網時代，由于網絡貨架成本的低廉，電子商務中物品不受貨架的限制，大多數不熱門商品都有機會銷售，這些商品由于其數量龐大，總體銷售額往往超過熱門商品。在長尾分布中，熱門商品代表著大部分用戶的選擇，而長尾商品則代表了用戶的個性化選擇。因此，在研究用戶的興趣需求的同時，如何挖掘長尾商品，來提高對用戶的個性化推薦，進而提升銷售額，這正是個性化推薦必須解決的主要問題。

在推薦系統中，通過對商品長尾分布的分析，挖掘用戶的歷史記錄，分析用戶的個性化需求，從而將那些不容易發現的但是用戶感興趣的長尾商品精確地推薦給用戶。推薦系統本質上旨在向用戶展示那些不那么廣泛流行的項目，但這些項目符合用戶的興趣，這一點可以從他們過去的購買歷史中推斷。

文中通過對評分矩陣采用PCA降維，降低了評分矩陣的稀疏性，保留了最能代表用戶興趣的維數，使得相似性計算更加準確，保證了最近鄰居選擇的準確性，從而提高了推薦質量，并且驗證了算法具有較高的準確度和覆蓋度。

2 現有算法分析

協同過濾推薦算法推薦原理：如果大多數用戶對項目的評分數據相似，那么當前用戶也會有類似的項目評分[11]。協同過濾推薦利用用戶對項目數據的評分記錄，進而生成評分矩陣來分析用戶的興趣，利用統計學知識在已評分的用戶中找到與目標興趣相似的用戶，從而找到目標用戶的最近鄰居，再結合這些鄰居用戶對項目的評分進行預測并產生推薦。傳統的協同過濾算法步驟如下：

(1)求解用戶和項目間的相似度矩陣；

(2)根據相似度矩陣求出目標的最近鄰居；

(3)對未評分項目進行預測并進行推薦。

2.1 相似性計算

在推薦系統中，算法的第一步就是計算用戶和用戶之間的相似性。余弦相似度、皮爾遜相關系數和修正的余弦相似度[12]是目前最重要的度量方法。

(1)余弦相似度。

通過計算空間夾角的余弦值來求解用戶之間的相似性。在推薦系統中，用戶的評分被看作是n維向量空間，用戶i和用戶j之間的相似性可以表述為：

(1)

(2)皮爾遜相關系數。

它是一種線性相關系數，通過兩個變量之間的協方差和標準差的商來計算，其表達式為：

(2)

(3)修正的余弦相似度。

余弦相似度在計算相似性時沒有考慮不同用戶的評分尺度，在推薦系統中，通常評分區間為1-5，有的用戶喜歡打高分，有的用戶打低分。此計算方法通過減去用戶的平均評分來改善這一缺陷。其表達式為：

(3)

2.2 基于用戶的協同過濾算法

基于用戶的協同過濾算法，首先會生成用戶的評分矩陣，其次根據用戶評分矩陣，利用相似性計算方法得到用戶之間的相似性，求出K近鄰，最后根據K近鄰來對未評分項目進行預測，并產生推薦。計算公式[13]如下：

(4)

2.3 傳統的相似性計算分析

在傳統的計算方法中，相似性是利用用戶對所有項目的評分數據來計算，這就會導致最終的評分矩陣數據維數高，評分向量的維數過高會增加相似性計算的復雜度，而且維數過高的向量對于相似性的度量也會造成負面影響。在統計學中對于已知的樣本數目，存在維數的極限值，當使用的數據向量的維數一直增加時，算法的性能并不會隨著維數的增加而增加，維數超過極限值之后，算法性能反而會退化。隨著電子商務規模的不斷擴大，用戶和項目數據都在快速增長，但是數據量卻極度稀疏，尤其是評分數據，在大型電子商務網站中，用戶評分的項目數據一般不會超過總數的1%[14]。

文中對MovieLens數據集進行統計分析，其中有8.8%的電影僅僅被一個用戶進行過評分，18%的電影被超過一百個用戶進行過評分。如果將所有的項目都用來進行相似性計算，不僅不能區分用戶之間的相似性，反而會給相似性計算帶來誤差，流行性物品不能反映用戶的興趣，而評分極其少的物品又會增加矩陣的稀疏性，對統計學方法而言沒有意義。

基于此，文中在分析數據集的基礎上提出了基于PCA降維的方法，將數據集進行簡化，在保留主要特征的同時降低數據集的維數，同時明顯降低了簡化后的評分矩陣的稀疏性，由于降低了稀疏性，使得相似性計算更加準確，提升了最近鄰居選擇的準確性，從而提高了推薦質量。

3 基于PCA降維的算法

3.1 數據表述

表1 用戶-項目評分矩陣

在統計學中，當維數很高時，導致可用數據很稀疏，然而從統計學意義上說，稀疏性也是一個重要問題。在推薦系統中，用戶的最近鄰居搜索就是通過相似性進行分組，然而在高維數據空間中，所有的可用數據變得很稀疏，因此使得相似性計算非常不準確。

3.2 項目流行度分析

對很多互聯網數據的研究發現，互聯網上的很多數據都滿足一種稱為PowerLaw的分布，這個分布在互聯網領域稱為長尾分布，其流行度滿足表達式：

f(x)=axk

(5)

長尾分布出現在各個領域，其實長尾分布最早是被統計學家發現的。1932年，哈佛大學的語言學家Zipf在研究英文單詞的詞頻時發現，如果將單詞按照出現的頻率進行排列，那么每個單詞出現的頻率和它在熱門排行榜中排名的常數次冪成反比，這個分布后來被稱為Zipf定律。為了研究項目的流行度是否具有長尾分布，文中對MovieLens數據集進行分析。

圖1顯示了MovieLens數據集中電影流行度的分布曲線。電影的流行度是指對電影進行過評分的用戶總數。圖中的曲線是雙對數曲線，而長尾分布曲線就是這種雙對數曲線，從而證明物品流行度具有長尾分布。

圖1 MovieLens數據集中物品流行度的長尾分布

3.3 PCA降維

主成分分析(Principal Component Analysis，PCA)是一種分析、簡化數據集的技術。主成分分析通常用于減少數據集的維數，同時保持數據集中對方差貢獻最大的特征[15]。該方法依據樣本空間中的位置分布，把樣本點在多維空間中的最大變化方向，即方差最大方向，作為判斷向量來實現特征提取。主成分分析由卡爾·皮爾遜于1901年提出，用于分析數據及建立數理模型。其方法主要是通過對協方差進行特征分解，以得出數據的主成分與它們的權值。

對于一個給定的樣本空間Xm×n，用PCA對矩陣Xm×n進行降維分析，具體步驟如下：

(1)求出樣本均值。

(2)計算Xm×n的協方差矩陣公式為：

(3)計算協方差矩陣的特征值和特征向量，其中特征值按照從大到小排列：

λ=(λ1,λ2,…,λn),λ1≥λ2…≥λn

(4)計算在每一維的投影：

得到一個降維的投影矩陣，該投影矩陣就是該樣本空間的主成分并且按照主成分從大到小排列。

3.4 基于PCA降維的推薦

傳統的向量空間模型存在數據災難，對于成百上萬的項目來說，用戶的項目評分維度就會增加。在高維空間中的數據集可以通過削弱減至低維空間，而不必失去其重要性質。這一點可以通過降維方法有效反映。

在文中提出的基于PCA降維的協同過濾推薦算法中，計算用戶和用戶的相似性時先采用PCA方法對評分矩陣進行降維處理，然后進行相似性計算。Sarwar利用MovieLens數據集對余弦相似度、皮爾遜相關系數和修正的余弦相似度進行了對比[11]并將MAE作為評測指標。實驗結果表明，利用修正的余弦相似度進行K近鄰計算，進而進行評分預測推薦可以獲得最優的MAE。因此文中采用修正的余弦相似度來進行相似度計算，在得到用戶的相似度之后采用最近鄰推薦。

鑒于降維的優點，文中引入PCA降維技術對用戶評分矩陣進行降維，然后通過降維后的用戶評分矩陣計算用戶的相似性，提高相似性計算的準確性，保證最近鄰居選擇的準確性。

算法流程如圖2所示。

圖2 基于PCA降維的協同過濾推薦算法基本流程

4 實驗分析

4.1 數據集

文中以MovieLens數據集為例，來評測文中提出的基于PCA降維的協同過濾算法和傳統的基于用戶的協同過濾算法。在該數據集中，包含了943個用戶對1 682個項目的10萬條評分記錄，每一個用戶至少對20部電影進行評分，電影類別為19類，用戶的評分范圍為1-5。

4.2 評價標準

在推薦系統中，平均絕對誤差(MAE)和覆蓋度(Coverage)是兩個最重要的評價指標。

MAE數值越低說明推薦算法越精準，計算公式如下：

(6)

覆蓋度是一項被廣泛應用于評價推薦算法發掘長尾的能力，覆蓋率越高，說明推薦算法越能夠將長尾中的物品推薦給目標用戶。計算公式如下：

(7)

其中，IP(u)是推薦算法為用戶u推薦的項目集；IR(u)是用戶u在測試集上進行評分的項目集。

4.3 實驗結果

最近鄰K的個數往往能夠影響推薦的效果，因此在實驗中，針對不同的K，分別利用兩種算法進行了MAE和Coverage的分析比較。

實驗中通過PCA方法將用戶評分矩陣維數降低到用戶個數的矩陣，即將R943×1682降低到R943×943，實驗結果如圖3和圖4所示。

由圖3和圖4可以看出，文中提出的基于PCA降維的協同過濾推薦算法具有較小的MAE和較大的Coverage。這是因為在計算用戶相似性時，對用戶評分矩陣進行了PCA降維，通過PCA降維，將用戶評分矩陣中最能反映用戶興趣的特征進行了保留，去除了不能反映用戶興趣的噪聲數據，使得評分矩陣的維數和稀疏性都有了明顯降低。在此基礎上進行用戶相似性的計算更加準確，保證最近鄰居選擇的準確性，從而使算法的推薦更準確。

圖3 不同推薦算法的MAE比較

圖4 不同推薦算法的Coverage比較

5 結束語

文中首先分析在用戶評分數據極度稀疏的情況下統計學方法在計算用戶相似性時存在的問題。針對用戶評分矩陣的稀疏性，文中提出了如何用PCA方法對推薦系統中的用戶評分數據進行降維處理，通過降維不僅降低了稀疏性，而且使得相似性計算中保留的數據是最能代表用戶興趣的特征向量，使得在計算相似性時更加準確，從而保證了最近鄰居選擇的準確性。通過對MovieLens數據進行降維處理，并通過實驗驗證了提出的算法可以降低評分矩陣的維數，并且有效降低了評分矩陣的稀疏性，解決了傳統相似性度量方法在高維數據中存在的弊端，提高了推薦系統的推薦質量。

[1]KonstanJA.Introductiontorecommendersystems:algorithms

andevaluation[J].ACMTransactionsonInformationSystems,2004,22(1):1-4.

[2]BobadillaJ,OrtegaF,HernandoA,etal.Improvingcollaborativefilteringrecommendersystemresultsandperformanceusinggeneticalgorithms[J].Knowledge-basedSystems,2011,24(8):1310-1316.

[3]BellRM,KorenY.Improvedneighborhood-basedcollaborativefiltering[C]//Procof13thACMSIGKDDinternationalconferenceonknowledgediscoveryanddatamining.[s.l.]:ACM,2007.

[4]LiuLM,ZhangPX,LinL,etal.Researchofdatasparsitybasedoncollaborativefilteringalgorithm[J].AppliedMechanicsandMaterials,2014,462:856-860.

[5]PirastehP,JungJJ,HwangD.Item-basedcollaborativefilteringwithattributecorrelation:acasestudyonmovierecommendation[M]//Intelligentinformationanddatabasesystems.[s.l.]:SpringerInternationalPublishing,2014:245-252.

[6]WangJ,LinK,LiJ.Acollaborativefilteringrecommendationalgorithmbasedonuserclusteringandslopeonescheme[C]//Procof8thinternationalconferenceoncomputerscience&education.[s.l.]:IEEE,2013:1473-1476.

[7]PitsilisG,KnapskogSJ.Socialtrustasasolutiontoaddresssparsity-inherentproblemsofrecommendersystems[C]//ProcofACMrecommendersystemworkshoponrecommendersystem&thesocialweb.[s.l.]:ACM,2009:33-40.

[8]WeiS,YeN,ZhangS,etal.Collaborativefilteringrecommendationalgorithmbasedonitemclusteringandglobalsimilarity[C]//Procoffifthinternationalconferenceonbusinessintelligenceandfinancialengineering.[s.l.]:IEEE,2012:69-72.

[9] 黃創光,印 鑒,汪 靜,等.不確定近鄰的協同過濾推薦算法[J].計算機學報,2010,33(8):1369-1377.

[10]AndersonC.Thelongtail[J].WiredMagazine,2004,12(10):170-177.

[11] 項 亮．推薦系統實踐[M]．北京:人民郵電出版社，2012:44-64．

[12]SarwarB,KarypisG,KonstanJ,etal.Item-basedcollaborativefilteringrecommendationalgorithms[C]//Proceedingsofthe10thinternationalconferenceonWorldWideWeb.[s.l.]:ACM,2001:285-295.

[13] 羅 辛,歐陽元新,熊 璋,等.通過相似度支持度優化基于K近鄰的協同過濾算法[J]．計算機學報,2010,33(8):1437-1445.

[14]LindenG,SmithB,YorkJ.Amazon.comrecommendations:item-to-itemcollaborativefiltering[J].IEEEInternetComputing,2003,7(1):76-80.

[15]RaikoT,IlinA,KarhunenJ.Principalcomponentanalysisforlargescaleproblemswithlotsofmissingvalues[C]//ProcofECML2007.Berlin:Springer,2007:691-698.

Collaborative Filtering Recommendation Algorithm Based on PCA Dimension Reduction

LI Yuan-bo,CAO Han

(School of Computer Science,Shaanxi Normal University,Xi’an 710062,China)

In the era of information overload,recommender system can help users find their interest and recommend the satisfactory information to analyze their historical behavior,so it is widely used in electronic commerce and other fields.But the user rating matrix is extremely sparse in recommender systems.The sparsity of the matrix leads to great error in the calculation of similarity of recommendation algorithms,bringing about the nearest neighbor sections is not accurate,thus affecting the quality of recommendation.Aiming at the problems above,a dimension reduction method based on PCA was proposed to reduce the sparsity of user rating matrix,by this method the remain matrix retain the most representative characteristic of the user interest,so that the similarity calculation is more accurate to ensure the accuracy of the nearest neighbors,thereby improving the quality of the recommendation.The experimental results show that compared with the traditional collaborative filtering algorithm,the algorithm proposed reaches a high accuracy and coverage.

PCA;dimension reduction;collaborative filtering;recommendation algorithm

2015-01-28

2015-05-17

時間：2016-01-26

國家自然科學基金資助項目(41271387)；陜西師范大學院士創新基金資助項目(999521)；西安市科技計劃基金資助項目(SF1228-3)作者簡介：李遠博(1988-)，男，碩士研究生，研究方向為高性能計算、數據挖掘；曹 菡，博士，教授，研究方向為數據挖掘、智慧旅游、高性能計算。

http://www.cnki.net/kcms/detail/61.1450.TP.20160126.1517.002.html

TP301.6

A

1673-629X(2016)02-0026-05

10.3969/j.issn.1673-629X.2016.02.006