陳 希，李玲娟

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

0 引 言

隨著信息技術與互聯(lián)網(wǎng)的迅猛發(fā)展，人們進入了一個信息“爆炸”的時代，如何從海量信息中找到自己感興趣的信息，如何讓自己釋放的信息脫穎而出受到關注都成為迫切需要解決的問題[1]。個性化的推薦系統(tǒng)成為繼分類目錄和搜索引擎后解決信息過載問題的代表性方案。推薦系統(tǒng)不需要用戶提供明確需求，而是通過分析用戶的歷史行為記錄主動推薦滿足用戶需求的信息。

在現(xiàn)有的推薦技術中，基于協(xié)同過濾的推薦算法使用最為廣泛，主要分為基于用戶和基于項目兩種協(xié)同過濾，原理都是通過用戶—項目評分矩陣計算相似度進行推薦[2]。可是隨著用戶與項目數(shù)量的不斷增加，出現(xiàn)了評分矩陣稀疏、搜索最近鄰耗時久等問題，導致傳統(tǒng)的協(xié)同過濾算法推薦質量有所下降。為解決數(shù)據(jù)稀疏性問題，大部分研究人員采用填充法(0，均值，眾數(shù))來補全缺失值，但不能從根本上解決數(shù)據(jù)稀疏性問題；文獻[3]提出使用奇異值分解(SVD)來解決數(shù)據(jù)稀疏性問題，但當數(shù)據(jù)量龐大時SVD效率會很低；文獻[4-6]中都構建了基于用戶聚類的協(xié)同推薦算法，通過對用戶評價矩陣進行分析，采用K-means聚類算法把興趣和偏好相似程度較高的用戶分到同一個簇中,以減少搜索最近鄰的時間，但會因為初始質心的選取不當導致推薦質量下降；有人嘗試采用BP神經(jīng)網(wǎng)絡來預測評分[7]，此方法雖然可以降低數(shù)據(jù)稀疏性所帶來的影響，但需花費更長的近鄰查找時間。

文中設計了一種基于主成分分析法(principal component analysis，PCA)和二分K-means聚類的新算法(命名為PK-CF算法)，對輸入的用戶-項目高維稀疏矩陣使用PCA進行降維，提取主成分因子，并在降維后的數(shù)據(jù)上進行二分K-means聚類，尋找當前用戶的所屬類別，進而快速確定其最近鄰，最后通過最近鄰相似度加權計算出當前用戶對未評測項目的預測值。

1 相關知識

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

如果部分用戶對某些項目的感興趣程度比較類似，則他們對其他項目的感興趣程度也會比較相似，可以把他們歸為同一個群體?；谟脩舻膮f(xié)同過濾推薦算法以此為前提，通過分析目標用戶的最近鄰居(最相似的若干用戶)對某個項目的評分來預測目標用戶對該項目的評分[8]。該算法主要包括兩個步驟：

(1)查找與目標用戶有相似興趣的用戶集合；

(2)將用戶集合中用戶最感興趣且目標用戶未使用的項目推薦給目標用戶。

此類算法的核心是計算用戶間的相似度，計算方法包括Jaccard、皮爾遜相關系數(shù)、歐幾里德距離和余弦距離。其中的皮爾遜相關系數(shù)方法在數(shù)據(jù)不規(guī)范時能給出更好的計算結果，具體公式如下：

(1)

文中將通過求皮爾遜相關系數(shù)來計算用戶間的相似性。

1.2 PCA降維技術

降維是應用最為廣泛的數(shù)據(jù)預處理方法之一，這種方法通過去除高維數(shù)據(jù)中的噪聲和無關緊要的特征，提升數(shù)據(jù)處理的速度進而節(jié)省大量的時間和成本。雖然降維造成了一定的信息損失，但在實際的應用中，通常只需要保留數(shù)據(jù)最重要的特征，一定范圍內的信息損失是可允許的[9]。降維的方法有線性和非線性之分，線性降維將n維的高維數(shù)據(jù)通過某種線性投影的方法映射到一個p維的低維空間，即用線性無關的p個新特征取代n個舊特征并保留數(shù)據(jù)的主成分(包含信息量最大的維度)，從而實現(xiàn)在保留原數(shù)據(jù)較多特性的情況下將n維數(shù)據(jù)降到p維的目的。

PCA(主成分分析)是最常用的線性降維方法之一，經(jīng)過PCA降維后的數(shù)據(jù)將轉換到一個新的坐標系中。新坐標系的坐標軸方向為數(shù)據(jù)方差最大的方向，方差反映的是數(shù)據(jù)與其均值之間的偏離程度，通常認為方差越大數(shù)據(jù)的信息量就越大。計算原數(shù)據(jù)中方差最大的方向，把它作為第一個坐標軸，第二個新坐標軸選擇的是與第一個新坐標軸正交且方差次大的方向，重復該過程，重復次數(shù)為原始數(shù)據(jù)的特征維數(shù)[10]。在最后獲得的新坐標系中，最先確定的坐標軸包含了數(shù)據(jù)最具特征的維度，余下坐標軸所包含的信息量幾乎為0，可忽略不計。因此，只保留前面幾個坐標軸，也就實現(xiàn)了對數(shù)據(jù)特征的降維處理。PCA算法的主要步驟如下：

輸入：數(shù)據(jù)集X為m個n維的樣本x1,x2,…,xm。

Step1:將X的每一維進行去均值化，即減去這一維的均值。

Step2:用式2計算樣本的協(xié)方差矩陣。

(2)

Step3:求出協(xié)方差矩陣特征值及對應的特征向量。

Step4:將特征向量按對應特征值大小從上到下按行排列成矩陣，取前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ù)挖掘的主要任務之一是聚類分析，它將物理或抽象對象的集合劃分成多個類簇，同一個簇中的對象彼此相似，不同簇中的對象彼此相異[11]。

K-means聚類算法在眾多聚類算法中應用最為普遍。該算法首先根據(jù)數(shù)據(jù)集大小隨機確定k個初始點為質心；然后將數(shù)據(jù)集中的每一個點分配到一個簇中，即為每一個點找到距其最近的質心，并將其分配給該質心所對應的簇；最后，每一個簇的質心更新為該簇所有點的平均值，重復以上步驟，直到質心不再變化[12]。K-means算法對初始質心的選擇比較敏感，隨機生成的k個質心可能出現(xiàn)質心聚集的情況，導致聚類效果可能是局部最優(yōu)的。

誤差平方和SSE是一種用于度量聚類效果的指標，其值是所有簇中的全部數(shù)據(jù)點到簇中心的誤差距離的平方累加和。SSE公式如下：

(4)

其中，k為指定的簇數(shù)；ci為第i個簇的質心；x為質心為ci的簇中的數(shù)據(jù)；dist計算的是兩個向量的歐幾里得距離。SSE的值越小，說明全部數(shù)據(jù)點越靠近于它們各自所屬的簇的中心(即質心)，聚類效果也越好。

作為K-means算法的優(yōu)化算法，二分K-means聚類算法首先將所有數(shù)據(jù)點看成一個簇，然后將該簇一分為二，并選擇一個簇進行k均值(k=2)劃分。選擇的標準是被劃分的簇能最大限度降低SSE的值，以此進行下去，直到簇的數(shù)目等于用戶給定的數(shù)目k為止。該算法與K-means算法相比，聚類速度更快，受初始質心的影響更小，聚類效果更好。

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

2.1 基本思路

針對傳統(tǒng)基于用戶的協(xié)同過濾推薦算法所存在的評分矩陣稀疏性與擴展性的問題，文中設計了一種高效的協(xié)同過濾推薦算法—基于PCA降維技術和二分K-means聚類的協(xié)同過濾推薦算法PK-CF(collaborative filtering recommendation algorithm based on PCA dimension reduction and bisecting K-means clustering)。

(1)稀疏性問題的解決思路。

利用PCA對評分矩陣進行降維處理，保留最能代表用戶興趣的主成分，同時緩解評分矩陣高稀疏性問題。

(2)相似度計算時耗問題的解決思路。

協(xié)同過濾算法需要先計算每兩個對象間的相似度，再搜索最近鄰進行推薦，但隨著用戶和項目的不斷增加，相似度的計算量變得非常龐大，傳統(tǒng)算法的可擴展性問題也凸顯出來。為此，一些學者使用了數(shù)據(jù)挖掘中的K-means算法，根據(jù)用戶的歷史評分記錄，計算其與每個簇質心的相似度，把目標用戶劃歸到所屬的簇內，縮小最近鄰搜索范圍再進行相似度的計算，減小計算量。但是K-means算法對初始質心的敏感性可能導致聚類效果是局部最優(yōu)的，會影響最終的推薦準確度。

為此，文中在基于用戶的協(xié)同過濾算法中引入二分K-means算法，首先將數(shù)據(jù)集中所有用戶—項目評分數(shù)據(jù)看成一個簇，然后將簇一分為二，當簇值小于指定的K值時，以被劃分的簇能最大限度降低SSE的值為標準，選擇一個簇進行k均值(k=2)劃分，直到簇的數(shù)值等于K值時，算法停止。

2.2 PK-CF算法流程

PK-CF算法的流程如下：

Step1：將評分數(shù)據(jù)轉換成用戶—項目評分矩陣，然后對每行缺失值進行填充，填充值為此行評分值的均值。

Step2：按圖1所示的流程運用PCA算法提取數(shù)據(jù)中的主成分(保留精度為99%)，得到降維后的矩陣R并記錄特征值與特征向量。

圖1 PCA降維過程

Step3：利用圖2所示的流程對降維后的矩陣R進行二分K-means聚類，得到多個簇及各簇的質心。

Step4：當要預測用戶u時，根據(jù)特征值與特征向量求出用戶u在主成分向量空間的坐標，并用式1計算其與各簇質心的相似度，用戶u屬于與其相似度最高的質心對應的簇，再求出u與簇內各用戶的相似度，形成一個用戶相似度矩陣X。

Step5：用基于最近鄰的預測方法[13]來預測用戶u對未評分項目i的評分，具體公式如下：

(5)

圖2 二分K-means聚類過程

Step6：根據(jù)預測評分進行TopN推薦，形成推薦列表。

3 實驗與結果分析

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

實驗使用美國明尼蘇達大學GroupLens項目組提供的MoviesLen數(shù)據(jù)集，該數(shù)據(jù)集包括943名用戶對1 682部電影的100 000條評分記錄，記錄包含user_id、itme_id、rating和timestamp四個字段，對應用戶ID、電影ID、評分值和評分時間四個屬性。通過計算在整個數(shù)據(jù)集中未評分項目所占的比例，得出數(shù)據(jù)的稀疏程度為93.695 3%，適合檢驗PK-CF算法在數(shù)據(jù)稀疏狀況下的推薦效果。

3.2 評判標準

實驗采用平均絕對誤差[14](mean absolute error，MAE)作為推薦預測準確度的評判標準，MAE反映預測的用戶評分與實際的用戶評分之間的偏差，偏差越小推薦質量越高。MAE計算公式如下：

(6)

TopN推薦的預測準確度一般通過召回率Recall與準確率Precision來度量[15]。召回率描述的是推薦正確的項目評分記錄數(shù)與測試集中的所有項目評分記錄數(shù)之比，準確率描述的是推薦正確的項目評分記錄數(shù)與所有推薦的項目評分記錄數(shù)之比。推薦結果Recall和Precision越高，推薦質量越好。召回率與準確率計算公式分別如下：

(7)

(8)

其中，R(u)為對用戶u推薦的N個項目的集合；T(u)為用戶u在測試集上喜歡的物品的集合。

在實際應用中，需要綜合考慮召回率與準確率，最常用的方法是F-Score，它是Recall和Precision加權調和平均。F-Score得分越高，說明推薦準確度也高[16]，計算公式如下：

(9)

3.3 結果分析

實驗前測得最終分類個數(shù)在12

文中共進行4次實驗來驗證PK-CF算法的有效性。隨機地把數(shù)據(jù)集按照4∶1的比例分為訓練集與測試集，每次選擇不同的訓練集與測試集分別運行傳統(tǒng)的基于用戶的協(xié)同過濾算法，基于K-means用戶聚類的協(xié)同過濾算法和文中的PK-CF算法，對結果取均值。

(1)推薦預測準確度測試。

實驗結果如圖3所示。

圖3 推薦預測質量比較

可以看出，在最近鄰個數(shù)L=25時，三種算法都取得了較好的推薦質量；而文中的PK-CF算法的MAE值在不同最近鄰個數(shù)下都比傳統(tǒng)的基于用戶的算法和基于K-means用戶聚類的算法要小，能夠有效地提高推薦質量。

(2)TopN推薦的預測指標對比。

表1與表2的數(shù)據(jù)都是在最近鄰個數(shù)為25狀況下的實驗結果。

表1 近鄰個數(shù)為25，N=10時不同算法的指標

表2 近鄰個數(shù)為25，N=20時不同算法的指標

可以看出，文中的PK-CF算法能有效提高推薦的召回率、準確率和F-Score值，而且當TopN推薦的N為20時，基于K-means的算法和文中的PK-CF算法的F-Socre值都大于N為10時的F-Score值，所以為了提高推薦質量可以適當增大N的值即推薦數(shù)量。在算法運行的時間方面，PK-CF算法和基于K-means的算法運行時長基本相同，但與傳統(tǒng)的協(xié)同過濾算法相比運行時長明顯減小很多。

4 結束語

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