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

?

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

參考文獻(xiàn)
[1] HAN J W,，KAMBER M.數(shù)據(jù)挖掘概念與技術(shù)[M].范明,，孟小峰，譯.北京：機(jī)械工業(yè)出版社,，2007：440.
[2] 魯為.協(xié)作過濾算法及其在個(gè)性化推薦系統(tǒng)中的應(yīng)用[D].
北京：北京郵電大學(xué),，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] 鄧愛林.電子商務(wù)推薦系統(tǒng)關(guān)健技術(shù)研究[D].上海：復(fù)旦大學(xué),，2003.