《電子技術(shù)應(yīng)用》
您所在的位置:首頁(yè) > 嵌入式技術(shù) > 業(yè)界動(dòng)態(tài) > 電子商務(wù)協(xié)作過(guò)濾推薦技術(shù)的算法研究與改進(jìn)

電子商務(wù)協(xié)作過(guò)濾推薦技術(shù)的算法研究與改進(jìn)

2009-07-28
作者:賀智明,王海超,高 娟

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

?

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


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

本站內(nèi)容除特別聲明的原創(chuàng)文章之外,轉(zhuǎn)載內(nèi)容只為傳遞更多信息,并不代表本網(wǎng)站贊同其觀點(diǎn)。轉(zhuǎn)載的所有的文章、圖片、音/視頻文件等資料的版權(quán)歸版權(quán)所有權(quán)人所有。本站采用的非本站原創(chuàng)文章及圖片等內(nèi)容無(wú)法一一聯(lián)系確認(rèn)版權(quán)者。如涉及作品內(nèi)容、版權(quán)和其它問(wèn)題,請(qǐng)及時(shí)通過(guò)電子郵件或電話通知我們,以便迅速采取適當(dāng)措施,避免給雙方造成不必要的經(jīng)濟(jì)損失。聯(lián)系電話:010-82306118;郵箱:aet@chinaaet.com。