陳 希,李玲娟
(南京郵電大學(xué) 計算機(jī)學(xué)院,江蘇 南京 210003)
隨著信息技術(shù)與互聯(lián)網(wǎng)的迅猛發(fā)展,人們進(jìn)入了一個信息“爆炸”的時代,如何從海量信息中找到自己感興趣的信息,如何讓自己釋放的信息脫穎而出受到關(guān)注都成為迫切需要解決的問題[1]。個性化的推薦系統(tǒng)成為繼分類目錄和搜索引擎后解決信息過載問題的代表性方案。推薦系統(tǒng)不需要用戶提供明確需求,而是通過分析用戶的歷史行為記錄主動推薦滿足用戶需求的信息。
在現(xiàn)有的推薦技術(shù)中,基于協(xié)同過濾的推薦算法使用最為廣泛,主要分為基于用戶和基于項目兩種協(xié)同過濾,原理都是通過用戶—項目評分矩陣計算相似度進(jìn)行推薦[2]??墒请S著用戶與項目數(shù)量的不斷增加,出現(xiàn)了評分矩陣稀疏、搜索最近鄰耗時久等問題,導(dǎo)致傳統(tǒng)的協(xié)同過濾算法推薦質(zhì)量有所下降。為解決數(shù)據(jù)稀疏性問題,大部分研究人員采用填充法(0,均值,眾數(shù))來補全缺失值,但不能從根本上解決數(shù)據(jù)稀疏性問題;文獻(xiàn)[3]提出使用奇異值分解(SVD)來解決數(shù)據(jù)稀疏性問題,但當(dāng)數(shù)據(jù)量龐大時SVD效率會很低;文獻(xiàn)[4-6]中都構(gòu)建了基于用戶聚類的協(xié)同推薦算法,通過對用戶評價矩陣進(jìn)行分析,采用K-means聚類算法把興趣和偏好相似程度較高的用戶分到同一個簇中,以減少搜索最近鄰的時間,但會因為初始質(zhì)心的選取不當(dāng)導(dǎo)致推薦質(zhì)量下降;有人嘗試采用BP神經(jīng)網(wǎng)絡(luò)來預(yù)測評分[7],此方法雖然可以降低數(shù)據(jù)稀疏性所帶來的影響,但需花費更長的近鄰查找時間。
文中設(shè)計了一種基于主成分分析法(principal component analysis,PCA)和二分K-means聚類的新算法(命名為PK-CF算法),對輸入的用戶-項目高維稀疏矩陣使用PCA進(jìn)行降維,提取主成分因子,并在降維后的數(shù)據(jù)上進(jìn)行二分K-means聚類,尋找當(dāng)前用戶的所屬類別,進(jìn)而快速確定其最近鄰,最后通過最近鄰相似度加權(quán)計算出當(dāng)前用戶對未評測項目的預(yù)測值。
如果部分用戶對某些項目的感興趣程度比較類似,則他們對其他項目的感興趣程度也會比較相似,可以把他們歸為同一個群體?;谟脩舻膮f(xié)同過濾推薦算法以此為前提,通過分析目標(biāo)用戶的最近鄰居(最相似的若干用戶)對某個項目的評分來預(yù)測目標(biāo)用戶對該項目的評分[8]。該算法主要包括兩個步驟:
(1)查找與目標(biāo)用戶有相似興趣的用戶集合;
(2)將用戶集合中用戶最感興趣且目標(biāo)用戶未使用的項目推薦給目標(biāo)用戶。
此類算法的核心是計算用戶間的相似度,計算方法包括Jaccard、皮爾遜相關(guān)系數(shù)、歐幾里德距離和余弦距離。其中的皮爾遜相關(guān)系數(shù)方法在數(shù)據(jù)不規(guī)范時能給出更好的計算結(jié)果,具體公式如下:
(1)
文中將通過求皮爾遜相關(guān)系數(shù)來計算用戶間的相似性。
降維是應(yīng)用最為廣泛的數(shù)據(jù)預(yù)處理方法之一,這種方法通過去除高維數(shù)據(jù)中的噪聲和無關(guān)緊要的特征,提升數(shù)據(jù)處理的速度進(jìn)而節(jié)省大量的時間和成本。雖然降維造成了一定的信息損失,但在實際的應(yīng)用中,通常只需要保留數(shù)據(jù)最重要的特征,一定范圍內(nèi)的信息損失是可允許的[9]。降維的方法有線性和非線性之分,線性降維將n維的高維數(shù)據(jù)通過某種線性投影的方法映射到一個p維的低維空間,即用線性無關(guān)的p個新特征取代n個舊特征并保留數(shù)據(jù)的主成分(包含信息量最大的維度),從而實現(xiàn)在保留原數(shù)據(jù)較多特性的情況下將n維數(shù)據(jù)降到p維的目的。
PCA(主成分分析)是最常用的線性降維方法之一,經(jīng)過PCA降維后的數(shù)據(jù)將轉(zhuǎn)換到一個新的坐標(biāo)系中。新坐標(biāo)系的坐標(biāo)軸方向為數(shù)據(jù)方差最大的方向,方差反映的是數(shù)據(jù)與其均值之間的偏離程度,通常認(rèn)為方差越大數(shù)據(jù)的信息量就越大。計算原數(shù)據(jù)中方差最大的方向,把它作為第一個坐標(biāo)軸,第二個新坐標(biāo)軸選擇的是與第一個新坐標(biāo)軸正交且方差次大的方向,重復(fù)該過程,重復(fù)次數(shù)為原始數(shù)據(jù)的特征維數(shù)[10]。在最后獲得的新坐標(biāo)系中,最先確定的坐標(biāo)軸包含了數(shù)據(jù)最具特征的維度,余下坐標(biāo)軸所包含的信息量幾乎為0,可忽略不計。因此,只保留前面幾個坐標(biāo)軸,也就實現(xiàn)了對數(shù)據(jù)特征的降維處理。PCA算法的主要步驟如下:
輸入:數(shù)據(jù)集X為m個n維的樣本x1,x2,…,xm。
Step1:將X的每一維進(jìn)行去均值化,即減去這一維的均值。
Step2:用式2計算樣本的協(xié)方差矩陣。
(2)
Step3:求出協(xié)方差矩陣特征值及對應(yīng)的特征向量。
Step4:將特征向量按對應(yīng)特征值大小從上到下按行排列成矩陣,取前s行組成矩陣P;
輸出:Y=PTX,Y即是X降到s維后的數(shù)據(jù)。
為了縮小投影的誤差,需要選取合適的s值,可用如下公式來確定s值:
(3)
其中,m表示特征的個數(shù),分子計算的是數(shù)據(jù)原始點與投影后的點距離的總和;Error表示誤差,誤差越小說明保留的主成分越多,降維的效果越好。一般控制Error的值小于0.01,即保留原數(shù)據(jù)99%信息特征。
數(shù)據(jù)挖掘的主要任務(wù)之一是聚類分析,它將物理或抽象對象的集合劃分成多個類簇,同一個簇中的對象彼此相似,不同簇中的對象彼此相異[11]。
K-means聚類算法在眾多聚類算法中應(yīng)用最為普遍。該算法首先根據(jù)數(shù)據(jù)集大小隨機(jī)確定k個初始點為質(zhì)心;然后將數(shù)據(jù)集中的每一個點分配到一個簇中,即為每一個點找到距其最近的質(zhì)心,并將其分配給該質(zhì)心所對應(yīng)的簇;最后,每一個簇的質(zhì)心更新為該簇所有點的平均值,重復(fù)以上步驟,直到質(zhì)心不再變化[12]。K-means算法對初始質(zhì)心的選擇比較敏感,隨機(jī)生成的k個質(zhì)心可能出現(xiàn)質(zhì)心聚集的情況,導(dǎo)致聚類效果可能是局部最優(yōu)的。
誤差平方和SSE是一種用于度量聚類效果的指標(biāo),其值是所有簇中的全部數(shù)據(jù)點到簇中心的誤差距離的平方累加和。SSE公式如下:
(4)
其中,k為指定的簇數(shù);ci為第i個簇的質(zhì)心;x為質(zhì)心為ci的簇中的數(shù)據(jù);dist計算的是兩個向量的歐幾里得距離。SSE的值越小,說明全部數(shù)據(jù)點越靠近于它們各自所屬的簇的中心(即質(zhì)心),聚類效果也越好。
作為K-means算法的優(yōu)化算法,二分K-means聚類算法首先將所有數(shù)據(jù)點看成一個簇,然后將該簇一分為二,并選擇一個簇進(jìn)行k均值(k=2)劃分。選擇的標(biāo)準(zhǔn)是被劃分的簇能最大限度降低SSE的值,以此進(jìn)行下去,直到簇的數(shù)目等于用戶給定的數(shù)目k為止。該算法與K-means算法相比,聚類速度更快,受初始質(zhì)心的影響更小,聚類效果更好。
針對傳統(tǒng)基于用戶的協(xié)同過濾推薦算法所存在的評分矩陣稀疏性與擴(kuò)展性的問題,文中設(shè)計了一種高效的協(xié)同過濾推薦算法—基于PCA降維技術(shù)和二分K-means聚類的協(xié)同過濾推薦算法PK-CF(collaborative filtering recommendation algorithm based on PCA dimension reduction and bisecting K-means clustering)。
(1)稀疏性問題的解決思路。
利用PCA對評分矩陣進(jìn)行降維處理,保留最能代表用戶興趣的主成分,同時緩解評分矩陣高稀疏性問題。
(2)相似度計算時耗問題的解決思路。
協(xié)同過濾算法需要先計算每兩個對象間的相似度,再搜索最近鄰進(jìn)行推薦,但隨著用戶和項目的不斷增加,相似度的計算量變得非常龐大,傳統(tǒng)算法的可擴(kuò)展性問題也凸顯出來。為此,一些學(xué)者使用了數(shù)據(jù)挖掘中的K-means算法,根據(jù)用戶的歷史評分記錄,計算其與每個簇質(zhì)心的相似度,把目標(biāo)用戶劃歸到所屬的簇內(nèi),縮小最近鄰搜索范圍再進(jìn)行相似度的計算,減小計算量。但是K-means算法對初始質(zhì)心的敏感性可能導(dǎo)致聚類效果是局部最優(yōu)的,會影響最終的推薦準(zhǔn)確度。
為此,文中在基于用戶的協(xié)同過濾算法中引入二分K-means算法,首先將數(shù)據(jù)集中所有用戶—項目評分?jǐn)?shù)據(jù)看成一個簇,然后將簇一分為二,當(dāng)簇值小于指定的K值時,以被劃分的簇能最大限度降低SSE的值為標(biāo)準(zhǔn),選擇一個簇進(jìn)行k均值(k=2)劃分,直到簇的數(shù)值等于K值時,算法停止。
PK-CF算法的流程如下:
Step1:將評分?jǐn)?shù)據(jù)轉(zhuǎn)換成用戶—項目評分矩陣,然后對每行缺失值進(jìn)行填充,填充值為此行評分值的均值。
Step2:按圖1所示的流程運用PCA算法提取數(shù)據(jù)中的主成分(保留精度為99%),得到降維后的矩陣R并記錄特征值與特征向量。
圖1 PCA降維過程
Step3:利用圖2所示的流程對降維后的矩陣R進(jìn)行二分K-means聚類,得到多個簇及各簇的質(zhì)心。
Step4:當(dāng)要預(yù)測用戶u時,根據(jù)特征值與特征向量求出用戶u在主成分向量空間的坐標(biāo),并用式1計算其與各簇質(zhì)心的相似度,用戶u屬于與其相似度最高的質(zhì)心對應(yīng)的簇,再求出u與簇內(nèi)各用戶的相似度,形成一個用戶相似度矩陣X。
Step5:用基于最近鄰的預(yù)測方法[13]來預(yù)測用戶u對未評分項目i的評分,具體公式如下:
(5)
圖2 二分K-means聚類過程
Step6:根據(jù)預(yù)測評分進(jìn)行TopN推薦,形成推薦列表。
實驗使用美國明尼蘇達(dá)大學(xué)GroupLens項目組提供的MoviesLen數(shù)據(jù)集,該數(shù)據(jù)集包括943名用戶對1 682部電影的100 000條評分記錄,記錄包含user_id、itme_id、rating和timestamp四個字段,對應(yīng)用戶ID、電影ID、評分值和評分時間四個屬性。通過計算在整個數(shù)據(jù)集中未評分項目所占的比例,得出數(shù)據(jù)的稀疏程度為93.695 3%,適合檢驗PK-CF算法在數(shù)據(jù)稀疏狀況下的推薦效果。
實驗采用平均絕對誤差[14](mean absolute error,MAE)作為推薦預(yù)測準(zhǔn)確度的評判標(biāo)準(zhǔn),MAE反映預(yù)測的用戶評分與實際的用戶評分之間的偏差,偏差越小推薦質(zhì)量越高。MAE計算公式如下:
(6)
TopN推薦的預(yù)測準(zhǔn)確度一般通過召回率Recall與準(zhǔn)確率Precision來度量[15]。召回率描述的是推薦正確的項目評分記錄數(shù)與測試集中的所有項目評分記錄數(shù)之比,準(zhǔn)確率描述的是推薦正確的項目評分記錄數(shù)與所有推薦的項目評分記錄數(shù)之比。推薦結(jié)果Recall和Precision越高,推薦質(zhì)量越好。召回率與準(zhǔn)確率計算公式分別如下:
(7)
(8)
其中,R(u)為對用戶u推薦的N個項目的集合;T(u)為用戶u在測試集上喜歡的物品的集合。
在實際應(yīng)用中,需要綜合考慮召回率與準(zhǔn)確率,最常用的方法是F-Score,它是Recall和Precision加權(quán)調(diào)和平均。F-Score得分越高,說明推薦準(zhǔn)確度也高[16],計算公式如下:
(9)
實驗前測得最終分類個數(shù)在12
文中共進(jìn)行4次實驗來驗證PK-CF算法的有效性。隨機(jī)地把數(shù)據(jù)集按照4∶1的比例分為訓(xùn)練集與測試集,每次選擇不同的訓(xùn)練集與測試集分別運行傳統(tǒng)的基于用戶的協(xié)同過濾算法,基于K-means用戶聚類的協(xié)同過濾算法和文中的PK-CF算法,對結(jié)果取均值。
(1)推薦預(yù)測準(zhǔn)確度測試。
實驗結(jié)果如圖3所示。
圖3 推薦預(yù)測質(zhì)量比較
可以看出,在最近鄰個數(shù)L=25時,三種算法都取得了較好的推薦質(zhì)量;而文中的PK-CF算法的MAE值在不同最近鄰個數(shù)下都比傳統(tǒng)的基于用戶的算法和基于K-means用戶聚類的算法要小,能夠有效地提高推薦質(zhì)量。
(2)TopN推薦的預(yù)測指標(biāo)對比。
表1與表2的數(shù)據(jù)都是在最近鄰個數(shù)為25狀況下的實驗結(jié)果。
表1 近鄰個數(shù)為25,N=10時不同算法的指標(biāo)
表2 近鄰個數(shù)為25,N=20時不同算法的指標(biāo)
可以看出,文中的PK-CF算法能有效提高推薦的召回率、準(zhǔn)確率和F-Score值,而且當(dāng)TopN推薦的N為20時,基于K-means的算法和文中的PK-CF算法的F-Socre值都大于N為10時的F-Score值,所以為了提高推薦質(zhì)量可以適當(dāng)增大N的值即推薦數(shù)量。在算法運行的時間方面,PK-CF算法和基于K-means的算法運行時長基本相同,但與傳統(tǒng)的協(xié)同過濾算法相比運行時長明顯減小很多。
文中將傳統(tǒng)協(xié)同過濾推薦算法與PCA降維和二分K-means相結(jié)合,設(shè)計出新的協(xié)同過濾推薦算法。該算法用PCA降維技術(shù)緩解數(shù)據(jù)集稀疏問題,同時使用二分K-means聚類方法對用戶聚類減少查找相似用戶的時耗。實驗結(jié)果表明,該算法能夠有效提高推薦質(zhì)量。