協(xié)同過(guò)濾算法的研究

引言

二十一世紀(jì)互聯(lián)網(wǎng)的迅猛發(fā)展,把人們推向了一個(gè)信息爆炸的時(shí)代。基于互聯(lián)網(wǎng)的系統(tǒng)相比于過(guò)去，數(shù)據(jù)量每時(shí)每刻都在迅速地增長(zhǎng)。用戶從海量的信息中挑選自己需要的信息，將變得愈加困難。為了使用戶能夠感受到良好的體驗(yàn)從而吸引更多的用戶，面向用戶的系統(tǒng)需要對(duì)海量信息進(jìn)行篩選、過(guò)濾，預(yù)測(cè)用戶最可能關(guān)注和感興趣的信息并呈現(xiàn)在用戶面前。這即提高了系統(tǒng)工作的效率，也節(jié)省了用戶篩選信息的時(shí)間。因此對(duì)信息的篩選和過(guò)濾成為一個(gè)系統(tǒng)重要組成部分。搜索引擎可以在一定程度上解決信息篩選問(wèn)題，但還遠(yuǎn)遠(yuǎn)無(wú)法滿足需求。搜索引擎需要用戶提供關(guān)鍵詞來(lái)對(duì)信息進(jìn)行篩選。但當(dāng)用戶無(wú)法準(zhǔn)確描述自己的需求時(shí)，捜索引擎的篩選效果將大打折扣。在此背景下，推薦系統(tǒng)出現(xiàn)了，推薦系統(tǒng)的任務(wù)就是解決上述的問(wèn)題。

1協(xié)同過(guò)濾系統(tǒng)

協(xié)同過(guò)濾系統(tǒng)是第一代被提出并得到廣泛應(yīng)用的推薦系統(tǒng)，其最大的優(yōu)點(diǎn)是對(duì)推薦對(duì)象沒(méi)有特殊的要求，能處理音樂(lè)、電影等難以進(jìn)行文本結(jié)構(gòu)表示的對(duì)象。其原理就是利用已知的物品信息和用戶打分信息，去預(yù)測(cè)某用戶對(duì)某物品的打分,并根據(jù)預(yù)測(cè)的分?jǐn)?shù)來(lái)決定是否向用戶推薦該物品。設(shè)U={U1，"2，…，Un}為所有用戶集合,S={S1，S2,…，sN}為所有物品的集合，5為用戶"對(duì)物品s的打分，而這個(gè)打分是未知的，需要通過(guò)協(xié)同過(guò)濾系統(tǒng)的算法去預(yù)測(cè)。得到了預(yù)測(cè)分?jǐn)?shù)后，再根據(jù)此預(yù)測(cè)分?jǐn)?shù)所在的分?jǐn)?shù)區(qū)間，判斷用戶是否有可能對(duì)該物品感興趣。若經(jīng)過(guò)判斷，用戶可能對(duì)該物品感興趣，貝懵該物品推薦給用戶。

協(xié)同過(guò)濾系統(tǒng)的算法可以分為兩類:一是基于用戶(User-Based)的算法，二是基于物品(Item-based)的算法。

2基于用戶(User-Based)的協(xié)同過(guò)濾算法

基于用戶的算法以用戶為出發(fā)點(diǎn)，先根據(jù)已打過(guò)分的物品信息計(jì)算用戶U與其他用戶之間的相似度，得到最為鄰近的k個(gè)用戶，將這k個(gè)用戶的集合標(biāo)記為U，然后根據(jù)相似度加權(quán)得到5。用sim(u,u)表示兩用戶之間的相似度,Pu.s表示預(yù)測(cè)的分?jǐn)?shù)，則最通用的加權(quán)預(yù)測(cè)公式：

公式中用戶u和u越相似，sim(u,u)的值越大，從而饑將具有更大的權(quán)重用于計(jì)算用戶可能的打分Pu,s。

最常用的計(jì)算相似度的方法有明考斯基(Minkowski)距離法、Pearson相關(guān)系數(shù)法和Cosine相似性法。

2.1明考斯基(Minkowski)距離法

明考斯基距離法非常直觀，且易于計(jì)算，復(fù)雜度較低。距離越短，說(shuō)明用戶x和y之間的相似度越高。用戶x和y之間的明考斯基距離公式：

由于在明考斯基距離法中，距離值越小，表示兩用戶越相似，因此在利用上述預(yù)測(cè)公式時(shí)，需要對(duì)距離進(jìn)行一步轉(zhuǎn)換：

通過(guò)轉(zhuǎn)換，便可得到相似度值，并滿足預(yù)測(cè)公式的對(duì)相似度值的要求。

2.2Pearson相關(guān)系數(shù)法

在實(shí)際中，不同用戶給物品打分的習(xí)慣不同：有的人會(huì)避免極端分?jǐn)?shù)(避免最高和最低分);有的只在某個(gè)分?jǐn)?shù)段內(nèi)打分。這會(huì)導(dǎo)致不同用戶對(duì)同一產(chǎn)品打的分?jǐn)?shù)所代表的意義不同。在這種情況下，直接利用明考斯基距離法，可能會(huì)無(wú)法如實(shí)反映用戶之間的相似度。利用Pearson相關(guān)系數(shù)表示相似度,可以解決明考斯基距離法隱含的缺陷，有效的解決用戶打分習(xí)慣不同這一問(wèn)題。

Pearson相關(guān)系數(shù)的值在［-1，1］之間變化。1表示相似度最高，-1表示相似度最低。

但是上述公式有一個(gè)嚴(yán)重的缺點(diǎn)：需要多趟遍歷數(shù)據(jù)。這大大提高了算法的時(shí)間復(fù)雜度。因此一般釆用下述的Pearson相關(guān)系數(shù)的近似公式：

式中：Sxy 表示用戶 x 和 y 共同打分的物品的集合，card（Sxy）為集合 Sxy 中元素的個(gè)數(shù)。該近似公式看似復(fù)雜，但只需遍歷一遍數(shù)據(jù)即可，因此，一般用此近似公式來(lái)計(jì)算 Pearson 相關(guān)系數(shù)。

2.3Cosine相似性

計(jì)算相似性時(shí)，只會(huì)用到用戶共同打分的產(chǎn)品的信息，其余產(chǎn)品信息，在計(jì)算兩個(gè)用戶之間相似性時(shí)是必須拋棄的，因此上述兩種方法必須首先找到兩個(gè)用戶共同打分的物品，才能計(jì)算相似度。在許多系統(tǒng)中，單個(gè)用戶只會(huì)給龐大的物品集合中有限的物品打分。此時(shí)，若采用上述兩種方法，會(huì)有大量操作和時(shí)間用在查找兩用戶共同打分的物品上。

Cosine相似性法［3,8］可以有效的解決上述問(wèn)題。在Cosine相似性法中，用戶x和y都用n(n為全部物品的個(gè)數(shù))維向量表示x,y,向量的元素為用戶對(duì)所有產(chǎn)品的評(píng)分，若用戶對(duì)該產(chǎn)品沒(méi)有打分，則用零值表示。因此用戶之間的相似性可用它們對(duì)應(yīng)的向量之間的余弦值表示：

其中x·y表示兩個(gè)向量的點(diǎn)積，S為整個(gè)物品集合。在計(jì)算過(guò)程中，由于乘法的作用，會(huì)自然消除兩用戶沒(méi)有共同打分的物品對(duì)相似度計(jì)算的影響。由于不必專門(mén)去查找兩用戶共同打分的物品，這極大地提高了效率，因此該算法非常適用于有效數(shù)據(jù)非常稀疏的情形。

基于用戶的協(xié)同過(guò)濾算法利用兩兩用戶之間的相似度來(lái)做出預(yù)測(cè)，相似度算法的選擇決定了預(yù)測(cè)的精度。上述三種計(jì)算相似度的方法是最常見(jiàn)，此外還有許多其它已被提出的計(jì)算相似度的方法。

3基于物品(Item-Based)的協(xié)同過(guò)濾

基于用戶的協(xié)同過(guò)濾算法在過(guò)去已經(jīng)取得了很大的成功，但隨著它的廣泛應(yīng)用，漸漸發(fā)現(xiàn)了兩方面的主要問(wèn)題:

一是規(guī)模性：獲得最鄰近用戶的計(jì)算量隨著用戶數(shù)和物品數(shù)的增加而迅速上升。有著百萬(wàn)用戶和物品的網(wǎng)絡(luò)推薦系統(tǒng)在使用基于用戶的協(xié)同過(guò)濾算法時(shí)將遇到非常嚴(yán)重的規(guī)模性問(wèn)題。

二是稀疏性：許多商業(yè)推薦系統(tǒng)(例如，亞馬遜圖書(shū)推薦系統(tǒng))擁有巨大的物品集合。即使最活躍的用戶購(gòu)買(mǎi)書(shū)的數(shù)量也不到所有書(shū)籍總量的1%。。所以，用戶很有可能與其他任何用戶都沒(méi)有共同打分的書(shū)籍。在這樣的情況下，基于用戶的推薦系統(tǒng)很有可能無(wú)法給一個(gè)用戶做出任何推薦。

此外，基于用戶之間相似度的方案需要實(shí)時(shí)計(jì)算相似度。而且，計(jì)算相似度要求必須已知最少數(shù)量的物品打分，如果已知的數(shù)據(jù)太少，計(jì)算相似度的結(jié)果會(huì)非常不準(zhǔn)確，進(jìn)而無(wú)法給用戶做出合理的推薦。

3.1AdjustedCosine相似性

基于物品的協(xié)同過(guò)濾算法一般也需要計(jì)算相似度，但是與基于用戶的協(xié)同過(guò)濾算法的不同之處在于：前者計(jì)算的是物品之間的相似度，而后者計(jì)算的是用戶之間的相似度。計(jì)算物品的相似度，也可以利用上述的Cosine相似性算法，但是利用Cosine相似性算法有一個(gè)嚴(yán)重的缺點(diǎn)：沒(méi)有考慮不同用戶打分習(xí)慣的不同。而AdjustedCosine相似性算法作為Cosine相似性算法的改進(jìn)，通過(guò)減去相應(yīng)用戶打分的平均值，來(lái)消除Cosine相似性算法的缺陷。利用AdjustedCosine相似性算法計(jì)算物品i和j之間的相似度的公式為：

其中云為用戶u的所有打分平均值。根據(jù)物品之間的相似度得到最相似物品集合i后，利用加權(quán)方式預(yù)測(cè)用戶u對(duì)物品i的打分:

3.2Slopeone

Slopeones算法既使用了兩兩物品的打分的相對(duì)關(guān)系信息，也使用了用戶對(duì)除待預(yù)測(cè)物品以外其他物品的打分信息。Slopeone算法可以被分成兩個(gè)部分：一、事先（在用戶訪問(wèn)量較少的時(shí)刻，如午夜）計(jì)算出兩兩物品之間打分的偏差;二、預(yù)測(cè)用戶對(duì)待預(yù)測(cè)物品的打分。Slopeone算法有多種，其中WeightedSlopeone算法是比較常用的。

計(jì)算物品i相對(duì)于物品，的打分偏差公式：

用WeightedSlopeone方法預(yù)測(cè)用戶u對(duì)物品j的打分公式為：

式中：j表示對(duì)物品i和j都打過(guò)分的用戶集合，cji=card（Uj表示集合Uj中用戶的數(shù)量。

Slopeone算法在有著較高精確度的前提下，具有易實(shí)現(xiàn)、復(fù)雜度低的優(yōu)點(diǎn)。最關(guān)鍵的是，Slopeone算法的第一步是可以在系統(tǒng)空閑的時(shí)刻提前計(jì)算的，這大大降低了查詢時(shí)刻的計(jì)算量，極大地提高了系統(tǒng)的推薦效率。

基于物品的協(xié)同過(guò)濾算法利用物品之間的關(guān)系，很好地解決了上述基于用戶的協(xié)同過(guò)濾算法的稀疏性問(wèn)題，且Slopeone算法中物品之間的打分偏差都在事先計(jì)算出來(lái)，在一定程度上解決了基于用戶的協(xié)同過(guò)濾算法的規(guī)模性問(wèn)題。

4結(jié)語(yǔ)

協(xié)同過(guò)濾系統(tǒng)中每種算法都有其最適用的場(chǎng)合，綜合各種算法，協(xié)同過(guò)濾系統(tǒng)有著非常廣泛的應(yīng)用。構(gòu)建協(xié)同過(guò)濾系統(tǒng)時(shí)，應(yīng)該仔細(xì)分析系統(tǒng)的數(shù)據(jù)特點(diǎn)，綜合考量各種算法的優(yōu)缺點(diǎn)，選擇最適合的。但是，協(xié)同過(guò)濾系統(tǒng)算法也存在著共同的制約問(wèn)題。隨著數(shù)據(jù)量的增大，使用各種算法構(gòu)建的系統(tǒng)都面臨計(jì)算負(fù)荷越來(lái)越大的問(wèn)題。比較可行的方案是設(shè)計(jì)某種近似的動(dòng)態(tài)算法，每次都利用到以前的計(jì)算結(jié)果，而不需要完全重新的計(jì)算。關(guān)于這方面算法的研究若取得進(jìn)展，則可以極大地提高推薦系統(tǒng)的效率。

20211121_619a03831ebe1__協(xié)同過(guò)濾算法的研究