協(xié)同過濾算法的研究
引言
二十一世紀(jì)互聯(lián)網(wǎng)的迅猛發(fā)展,把人們推向了一個信息爆炸的時代?;诨ヂ?lián)網(wǎng)的系統(tǒng)相比于過去,數(shù)據(jù)量每時每刻都在迅速地增長。用戶從海量的信息中挑選自己需要的信息,將變得愈加困難。為了使用戶能夠感受到良好的體驗(yàn)從而吸引更多的用戶,面向用戶的系統(tǒng)需要對海量信息進(jìn)行篩選、過濾,預(yù)測用戶最可能關(guān)注和感興趣的信息并呈現(xiàn)在用戶面前。這即提高了系統(tǒng)工作的效率,也節(jié)省了用戶篩選信息的時間。因此對信息的篩選和過濾成為一個系統(tǒng)重要組成部分。搜索引擎可以在一定程度上解決信息篩選問題,但還遠(yuǎn)遠(yuǎn)無法滿足需求。搜索引擎需要用戶提供關(guān)鍵詞來對信息進(jìn)行篩選。但當(dāng)用戶無法準(zhǔn)確描述自己的需求時,捜索引擎的篩選效果將大打折扣。在此背景下,推薦系統(tǒng)出現(xiàn)了,推薦系統(tǒng)的任務(wù)就是解決上述的問題。
1協(xié)同過濾系統(tǒng)
協(xié)同過濾系統(tǒng)是第一代被提出并得到廣泛應(yīng)用的推薦系統(tǒng),其最大的優(yōu)點(diǎn)是對推薦對象沒有特殊的要求,能處理音樂、電影等難以進(jìn)行文本結(jié)構(gòu)表示的對象。其原理就是利用已知的物品信息和用戶打分信息,去預(yù)測某用戶對某物品的打分,并根據(jù)預(yù)測的分?jǐn)?shù)來決定是否向用戶推薦該物品。設(shè)U={U1,"2,…,Un}為所有用戶集合,S={S1,S2,…,sN}為所有物品的集合,5為用戶"對物品s的打分,而這個打分是未知的,需要通過協(xié)同過濾系統(tǒng)的算法去預(yù)測。得到了預(yù)測分?jǐn)?shù)后,再根據(jù)此預(yù)測分?jǐn)?shù)所在的分?jǐn)?shù)區(qū)間,判斷用戶是否有可能對該物品感興趣。若經(jīng)過判斷,用戶可能對該物品感興趣,貝懵該物品推薦給用戶。
協(xié)同過濾系統(tǒng)的算法可以分為兩類:一是基于用戶(User-Based)的算法,二是基于物品(Item-based)的算法。
2基于用戶(User-Based)的協(xié)同過濾算法
基于用戶的算法以用戶為出發(fā)點(diǎn),先根據(jù)已打過分的物品信息計算用戶U與其他用戶之間的相似度,得到最為鄰近的k個用戶,將這k個用戶的集合標(biāo)記為U,然后根據(jù)相似度加權(quán)得到5。用sim(u,u)表示兩用戶之間的相似度,Pu.s表示預(yù)測的分?jǐn)?shù),則最通用的加權(quán)預(yù)測公式:
公式中用戶u和u越相似,sim(u,u)的值越大,從而饑將具有更大的權(quán)重用于計算用戶可能的打分Pu,s。
最常用的計算相似度的方法有明考斯基(Minkowski)距離法、Pearson相關(guān)系數(shù)法和Cosine相似性法。
2.1明考斯基(Minkowski)距離法
明考斯基距離法非常直觀,且易于計算,復(fù)雜度較低。距離越短,說明用戶x和y之間的相似度越高。用戶x和y之間的明考斯基距離公式:
由于在明考斯基距離法中,距離值越小,表示兩用戶越相似,因此在利用上述預(yù)測公式時,需要對距離進(jìn)行一步轉(zhuǎn)換:
通過轉(zhuǎn)換,便可得到相似度值,并滿足預(yù)測公式的對相似度值的要求。
2.2Pearson相關(guān)系數(shù)法
在實(shí)際中,不同用戶給物品打分的習(xí)慣不同:有的人會避免極端分?jǐn)?shù)(避免最高和最低分);有的只在某個分?jǐn)?shù)段內(nèi)打分。這會導(dǎo)致不同用戶對同一產(chǎn)品打的分?jǐn)?shù)所代表的意義不同。在這種情況下,直接利用明考斯基距離法,可能會無法如實(shí)反映用戶之間的相似度。利用Pearson相關(guān)系數(shù)表示相似度,可以解決明考斯基距離法隱含的缺陷,有效的解決用戶打分習(xí)慣不同這一問題。
Pearson相關(guān)系數(shù)的值在[-1,1]之間變化。1表示相似度最高,-1表示相似度最低。
但是上述公式有一個嚴(yán)重的缺點(diǎn):需要多趟遍歷數(shù)據(jù)。這大大提高了算法的時間復(fù)雜度。因此一般釆用下述的Pearson相關(guān)系數(shù)的近似公式:
式中:Sxy 表示用戶 x 和 y 共同打分的物品的集合,card(Sxy)為集合 Sxy 中元素的個數(shù)。該近似公式看似復(fù)雜,但只需遍歷一遍數(shù)據(jù)即可,因此,一般用此近似公式來計算 Pearson 相關(guān)系數(shù)。
2.3Cosine相似性
計算相似性時,只會用到用戶共同打分的產(chǎn)品的信息,其余產(chǎn)品信息,在計算兩個用戶之間相似性時是必須拋棄的,因此上述兩種方法必須首先找到兩個用戶共同打分的物品,才能計算相似度。在許多系統(tǒng)中,單個用戶只會給龐大的物品集合中有限的物品打分。此時,若采用上述兩種方法,會有大量操作和時間用在查找兩用戶共同打分的物品上。
Cosine相似性法[3,8]可以有效的解決上述問題。在Cosine相似性法中,用戶x和y都用n(n為全部物品的個數(shù))維向量表示x,y,向量的元素為用戶對所有產(chǎn)品的評分,若用戶對該產(chǎn)品沒有打分,則用零值表示。因此用戶之間的相似性可用它們對應(yīng)的向量之間的余弦值表示:
其中x·y表示兩個向量的點(diǎn)積,S為整個物品集合。在計算過程中,由于乘法的作用,會自然消除兩用戶沒有共同打分的物品對相似度計算的影響。由于不必專門去查找兩用戶共同打分的物品,這極大地提高了效率,因此該算法非常適用于有效數(shù)據(jù)非常稀疏的情形。
基于用戶的協(xié)同過濾算法利用兩兩用戶之間的相似度來做出預(yù)測,相似度算法的選擇決定了預(yù)測的精度。上述三種計算相似度的方法是最常見,此外還有許多其它已被提出的計算相似度的方法。
3基于物品(Item-Based)的協(xié)同過濾
基于用戶的協(xié)同過濾算法在過去已經(jīng)取得了很大的成功,但隨著它的廣泛應(yīng)用,漸漸發(fā)現(xiàn)了兩方面的主要問題:
一是規(guī)模性:獲得最鄰近用戶的計算量隨著用戶數(shù)和物品數(shù)的增加而迅速上升。有著百萬用戶和物品的網(wǎng)絡(luò)推薦系統(tǒng)在使用基于用戶的協(xié)同過濾算法時將遇到非常嚴(yán)重的規(guī)模性問題。
二是稀疏性:許多商業(yè)推薦系統(tǒng)(例如,亞馬遜圖書推薦系統(tǒng))擁有巨大的物品集合。即使最活躍的用戶購買書的數(shù)量也不到所有書籍總量的1%。。所以,用戶很有可能與其他任何用戶都沒有共同打分的書籍。在這樣的情況下,基于用戶的推薦系統(tǒng)很有可能無法給一個用戶做出任何推薦。
此外,基于用戶之間相似度的方案需要實(shí)時計算相似度。而且,計算相似度要求必須已知最少數(shù)量的物品打分,如果已知的數(shù)據(jù)太少,計算相似度的結(jié)果會非常不準(zhǔn)確,進(jìn)而無法給用戶做出合理的推薦。
3.1AdjustedCosine相似性
基于物品的協(xié)同過濾算法一般也需要計算相似度,但是與基于用戶的協(xié)同過濾算法的不同之處在于:前者計算的是物品之間的相似度,而后者計算的是用戶之間的相似度。計算物品的相似度,也可以利用上述的Cosine相似性算法,但是利用Cosine相似性算法有一個嚴(yán)重的缺點(diǎn):沒有考慮不同用戶打分習(xí)慣的不同。而AdjustedCosine相似性算法作為Cosine相似性算法的改進(jìn),通過減去相應(yīng)用戶打分的平均值,來消除Cosine相似性算法的缺陷。利用AdjustedCosine相似性算法計算物品i和j之間的相似度的公式為:
其中云為用戶u的所有打分平均值。根據(jù)物品之間的相似度得到最相似物品集合i后,利用加權(quán)方式預(yù)測用戶u對物品i的打分:
3.2Slopeone
Slopeones算法既使用了兩兩物品的打分的相對關(guān)系信息,也使用了用戶對除待預(yù)測物品以外其他物品的打分信息。Slopeone算法可以被分成兩個部分:一、事先(在用戶訪問量較少的時刻,如午夜)計算出兩兩物品之間打分的偏差;二、預(yù)測用戶對待預(yù)測物品的打分。Slopeone算法有多種,其中WeightedSlopeone算法是比較常用的。
計算物品i相對于物品,的打分偏差公式:
用WeightedSlopeone方法預(yù)測用戶u對物品j的打分公式為:
式中:j表示對物品i和j都打過分的用戶集合,cji=card(Uj表示集合Uj中用戶的數(shù)量。
Slopeone算法在有著較高精確度的前提下,具有易實(shí)現(xiàn)、復(fù)雜度低的優(yōu)點(diǎn)。最關(guān)鍵的是,Slopeone算法的第一步是可以在系統(tǒng)空閑的時刻提前計算的,這大大降低了查詢時刻的計算量,極大地提高了系統(tǒng)的推薦效率。
基于物品的協(xié)同過濾算法利用物品之間的關(guān)系,很好地解決了上述基于用戶的協(xié)同過濾算法的稀疏性問題,且Slopeone算法中物品之間的打分偏差都在事先計算出來,在一定程度上解決了基于用戶的協(xié)同過濾算法的規(guī)模性問題。
4結(jié)語
協(xié)同過濾系統(tǒng)中每種算法都有其最適用的場合,綜合各種算法,協(xié)同過濾系統(tǒng)有著非常廣泛的應(yīng)用。構(gòu)建協(xié)同過濾系統(tǒng)時,應(yīng)該仔細(xì)分析系統(tǒng)的數(shù)據(jù)特點(diǎn),綜合考量各種算法的優(yōu)缺點(diǎn),選擇最適合的。但是,協(xié)同過濾系統(tǒng)算法也存在著共同的制約問題。隨著數(shù)據(jù)量的增大,使用各種算法構(gòu)建的系統(tǒng)都面臨計算負(fù)荷越來越大的問題。比較可行的方案是設(shè)計某種近似的動態(tài)算法,每次都利用到以前的計算結(jié)果,而不需要完全重新的計算。關(guān)于這方面算法的研究若取得進(jìn)展,則可以極大地提高推薦系統(tǒng)的效率。
20211121_619a03831ebe1__協(xié)同過濾算法的研究