基于降維和聚類的協(xié)同過濾推薦算法

陳 希，李玲娟

(南京郵電大學(xué) 計算機(jī)學(xué)院，江蘇 南京 210003)

0 引 言

隨著信息技術(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ù)測值。

1 相關(guān)知識

1.1 基于用戶的協(xié)同過濾推薦算法

如果部分用戶對某些項目的感興趣程度比較類似，則他們對其他項目的感興趣程度也會比較相似，可以把他們歸為同一個群體?；谟脩舻膮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ù)來計算用戶間的相似性。

1.2 PCA降維技術(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%信息特征。

1.3 K-means聚類與二分K-means聚類

數(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ì)心的影響更小，聚類效果更好。

2 基于PCA和二分K-means協(xié)同過濾推薦算法設(shè)計

2.1 基本思路

針對傳統(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值時，算法停止。

2.2 PK-CF算法流程

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推薦，形成推薦列表。

3 實驗與結(jié)果分析

3.1 數(shù)據(jù)集

實驗使用美國明尼蘇達(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ù)稀疏狀況下的推薦效果。

3.2 評判標(biāo)準(zhǔn)

實驗采用平均絕對誤差[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)

3.3 結(jié)果分析

實驗前測得最終分類個數(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é)同過濾算法相比運行時長明顯減小很多。

4 結(jié)束語

文中將傳統(tǒng)協(xié)同過濾推薦算法與PCA降維和二分K-means相結(jié)合，設(shè)計出新的協(xié)同過濾推薦算法。該算法用PCA降維技術(shù)緩解數(shù)據(jù)集稀疏問題，同時使用二分K-means聚類方法對用戶聚類減少查找相似用戶的時耗。實驗結(jié)果表明，該算法能夠有效提高推薦質(zhì)量。