摘 要： 推薦算法的好壞直接影響推薦系統的效率。本文提出了一種改進的基于K-中心點算法的合作聚類推薦算法，該算法有效減少了數值矩陣的行數，大大縮短了搜尋近鄰客戶的時間，從而提高了算法的執行效率和準確性。
??? 關鍵詞： 電子商務；推薦系統；K-中心點算法；客戶關系管理

?

?? 個性化推薦系統是現代商務發展的產物，協作過濾推薦技術是個性化推薦系統中的一種典型技術，其優勢是為電子商務的顧客提供個性化服務，促進一對一的銷售，使公司擁有顧客的更準確的模型，從而可以對顧客的需求有更好的了解。而服務于這些需求則可在相關產品的交叉銷售、提升銷售、產品親和力、一對一促銷、保留客戶等方面可獲得巨大的成功。
　　然而，協作過濾推薦技術也還存在一些致命的缺點，如稀疏問題、冷開始問題、假負和假正等問題。稀疏問題(Sparsity)是協作過濾推薦技術中的重要問題之一，每個用戶一般都只對很少的項目作出評價，整個數據陣變得非常稀疏，一般都在1 %以下。這種情況帶來的問題是得到用戶間的相似性不準確，鄰居用戶不可靠。冷開始問題又稱第一評價問題或新項目問題，如果一個新項目很少有人去評價它，或都不去評價它，則這個項目肯定得不到推薦，推薦系統就失去了作用。假負是指系統沒有推薦但顧客卻喜歡的產品；假正則是指系統推薦但顧客卻并不喜歡的產品[1]。這些問題都不是人們想看到的。因此，怎樣使這些問題得到有效的解決就成為目前研究的重點。
1 協作過濾推薦算法
　　協作過濾推薦算法(Collaborative Filtering Recommendation)是目前應用廣泛且效率較高的一種個性化推薦技術。它基于鄰居用戶的資料得到目標用戶的推薦，其推薦的個性化程度更高[2]。
1.1 協作過濾算法的思路
　　協作過濾推薦是基于鄰居用戶的興趣愛好預測目標用戶的興趣偏好。算法首先使用統計技術尋找與目標用戶具有相同喜好的鄰居，然后根據目標用戶的鄰居的偏好產生向目標用戶的推薦[2]。
??? 協作過濾是基于這樣一種假設[3]：如果用戶對一些項目的評分比較相似，則他們對其他項目的評分也比較相似；如果大部分用戶對一些項目的評分比較相似，則當前用戶對這些項目的評分也比較相似。
??? 協作過濾推薦系統使用統計技術搜索目標用戶的若干最近鄰，然后根據最近鄰對項目的評分預測目標用戶對項目的評分，產生對應的推薦列表。
1.2 算法模型
??? 對用戶己經購買過的商品進行建模，可以有效度量用戶之間的相似性。用戶評分數據可以用一個n×m階用戶-項目評分矩陣表示，n行代表個n用戶，m列代表m個項目，第i行j列的元素代表用戶i對項目j的評分值。這里只介紹用戶間的相似度度量公式，項目間的度量公式和用戶間的有些相似。
　　度量用戶間相似性的方法有許多種，主要有4種方法：余弦相似性度量公式(Cosine-based Similarity)、修正的余弦相似度公式(Adjusted Cosine Similarity)、相關相似度公式(Correlation-based Similarity)、求熵(互信息)的方法。通常采用前3種方法。首先得到用戶i和用戶j評分過的所有項目，然后通過不同的相似性度量方法計算用戶i和用戶j之間的相似性，記為sim(i，j)。
　　(1)余弦相似性度量
　　用戶評分看作為n維項空間上的向量，如果用戶對其項沒有進行評分，則將用戶對該項的評分設為0，用戶間的相似性通過向量間的余弦夾角度量。設用戶i和用戶j在n維項空間上的評分分別表示為向量，則用戶i和用戶j之間的相似性sim(i，j)為：
　　
式中，分子為2個用戶評分向量的內積，分母為2個用戶向量模的乘積。
　　(2)修正的余弦相似性
　　修正余弦相關性充分考慮了不同用戶的評分尺度問題，通過減去用戶對項目的評分來實現它的優點。設用戶i和用戶j評分過的相集合，則用戶i和用戶j之間的相似性sim(i，j)為：
　　
　　最近鄰居查詢的目標就是對每一個用戶a，在整個用戶空間中查找用戶集合，，使得N1與a的相似度sim(a，N1)最高，N2與a的相似度sim(a，N2)次之，依此類推。
??? (3)相關相似度
　　? 相關相似度又稱Pearson相關系數度量，設用戶i和用戶j共同評分過的項目集合用I_i，j=I₁∩I₂表示，則用戶i和用戶j的相似度sim(i，j)為：
???
1.3 鄰居集合的形成
??? 鄰居集合的形成一般有4種方法：Top-N、K近鄰法、閾值法、聚類法、貝葉斯網絡法。最常用的是前2種方法。
??? 算法的核心部分是為一個需要推薦服務的目標用戶尋找最相似的最近鄰居集。根據預先確定的鄰居數N，采用以上相似度的算法按由大到小的順序選取前N個用戶作為鄰居用戶集合?；蛘吒鶕A先確定的相似度閾值，選擇所有相似度大于閾值的作為鄰居用戶集合。
1.4 推薦產生
　　根據當前用戶最近鄰居對商品的評分信息預測當前用戶對未評分商品的評分，產生Top-N商品推薦。通過上面提出的相似性度量方法得到目標用戶的最近鄰居，下一步需要產生相應的推薦。設用戶u的最近鄰居集合用Nu表示，則用戶u對項目i預測評分P_u，i可以通過用戶u對最近鄰居集合N_u中項的評分得到，計算方法如下：
　　
式中，sim(u，n)表示用戶u與用戶n之間的相似性，R_n，i表示用戶n對項i的評分，R_u和R_n分別表示用戶u和用戶n對項的平均評分。
??? 通過上述方法預測用戶對所有未評分項的評分，然后選擇預測評分最高的前n項作為推薦結果反饋給當前的目標用戶。
2 基于K-中心點算法的合作聚類算法
　　盡管協作過濾技術在個性化推薦系統中獲得了極大的成功，但隨著電子商務系統規模的擴大，用戶數目和項數目指數級增長，導致用戶評分數據的極端稀疏性。由于用戶的最近鄰居至少對2件商品進行了共同評分，因此在用戶評分數據極端稀疏的情況下，無法搜索到某些用戶其最近鄰居，導致協作過濾推薦算法無法對這些用戶產生任何推薦。其次，在大規模數據集上搜索當前用戶的最近鄰居非常費時，難以保證協作過濾推薦算法的實時性要求。最后，協作過濾推薦算法無法發現商品之間存在的隱含關聯[4]。
　　現有許多種改進的算法來解決這一難題，如基于降維的協作過濾推薦算法、Cluster-based協作過濾推薦算法都是目前的主流算法。在基于降維的協作過濾推薦算法中，奇異值分解SVD(Singular Value Decomposetion)技術在信息檢索領域得到了廣泛應用?；赟VD技術的協作過濾推薦算法能較好地解決數據稀疏性問題，同時，因為k<2.1 Cluster-based協作過濾推薦算法
　　Cluster-based協作過濾推薦算法，將整個Web日志根據用戶的購買習慣和評分特點劃分為若干個不同的聚類，從而使得聚類內部用戶對項的評分盡可能相似，而不同聚類間用戶對商品的評分盡可能不同甚至相反。使目標用戶與其相似度最近的那個簇對其進行推薦，從而提高了精確度，也提高了最近鄰查詢的效率。
　　根據每個聚類中用戶對商品的評分信息生成一個虛擬用戶，它代表了該聚類中用戶對商品的典型評分，將所有虛擬用戶對商品的評分作為新的搜索空間，查詢當前用戶在虛擬用戶空間中的最近鄰居，產生對應的推薦結果。相對于原始的用戶空間而言，虛擬用戶空間要小得多，因此最近鄰查詢的效率也高得多，可以有效提高推薦算法的實時響應速度[4]。
2.2 改進的基于K-中心點算法的合作聚類算法
　　本文提出了一種改進的K-中心點算法(PAM)用來對整個用戶的訪問記錄和訪問特點進行聚類，主要步驟如下：
　　設站點有m個頁面，共有n個用戶訪問，由于采用協作推薦方法，設T為一個n×(m+1)的矩陣。n×m的矩陣為用戶-項目矩陣。第m+1列表征該行被加入到該矩陣中的時間，目的是為了始終讓此矩陣保持最新狀態，避免一些過時的興趣，因為客戶的興趣可能會改變。
　　輸入：初始簇K、T。
　　輸出：生成新的聚類中心Maincenter。
　　(1)k=[K/2]；????　　　　　　? //起始時取[K/2]值作為k-中心點算法的初始k值
　　(2)隨機選取k個對象作為初始的簇的中心。
　　(3)重復。
　　(4)對其他非中心點對象，計算其與中心點的距離，并將其分配到距離最近的中心點代表的簇。
　　(5)重復。
　　(6)選擇一個未被選擇的中心點O_i。
　　(7)重復。
　　(8)選取一個未被選擇的非中心點對象O_m，計算用O_m代替O_i的總代價并記錄在集合S中。
　　(9)直到所有的非中心點對象都被選擇過。
　　(10)直到所有的中心點都被選擇過。
　　(11)若在S集合中所有非中心點對象代替所有中心點后計算的總代價中存在小于0的，則找出S中最小的一個，用該非中心點替代對應的中心點。
??? (12)若在S集合中所有非中心點對象代替所有中心點后計算的總代價中存在大于0的，則找出代價最大的一個，并將其設為一個新的中心點。
??? (13)這樣形成一個新的含有k+1個中心的集合。
??? (14)直到S集合中所有的值都大于0，且k<=K。
??? (15)最后將每個用戶分配到相似性最高的聚類中。
??? (16)對新生成的聚類，計算聚類中所有用戶對項的平均評分，生成新的聚類中心。
??? (17)重復15～16，直到聚類不再發生改變為止。
　　生成聚類之后，Cluster-based協作過濾推薦算法可以分為如下2步：
??? (1)生成虛擬用戶集
??? 虛擬用戶集由聚類所得的聚類中心組成，這些聚類中心是根據不同的聚類生成的，是每個聚類中與其他用戶的距離之和最小的對象的集合，代表了其所在聚類中用戶對商品的典型評分。
??? (2)產生推薦
??? 得到虛擬用戶集之后，對其使用各種相似性度量方法以搜索當前用戶的最近鄰居，再根據這些最近鄰居對商品的評分信息來生成相應的推薦結果。其方法與協作過濾推薦算法類似，不再贅述。
　　由于采用了聚類算法壓縮了T矩陣(減少了行的個數)，當一段時間之后，一些新的用戶訪問被換入T矩陣后，就需要重新運行此算法已得到新的壓縮結果。
　　電子商務已經成為現代商務的主流，其規模也已變得越來越大，伴隨著商品同質化時代的來臨，提高客戶的滿意度、忠誠度，將是企業盈利的首要因素，對于推薦系統的要求也將越來越高。本文通過將K-中心點算法與合作聚類算法融合，可有效解決傳統推薦系統中的冷開始、數據稀疏性、假負、假正等問題，從而可以更好地獲得相近客戶，提高推薦的效果和準確性。

參考文獻
[1] HAN J W，KAMBER M.數據挖掘概念與技術[M].范明，孟小峰，譯.北京：機械工業出版社，2007：440.
[2] 魯為.協作過濾算法及其在個性化推薦系統中的應用[D].
北京：北京郵電大學，2007:22-24.
[3] BREESE J，HECKERMAN C.kadie.Empirical analysis of predictive allgorithms for collaborative filtering.In：Proceedings of the 14th Conference on Uncertinty in Aritificial Intelligence，San Francisco，CA，July 1998：44-52.
[4] 鄧愛林.電子商務推薦系統關健技術研究[D].上海：復旦大學，2003.