引言

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

1協同過濾系統

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

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

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

基于用戶的算法以用戶為出發(fā)點，先根據已打過分的物品信息計算用戶U與其他用戶之間的相似度，得到最為鄰近的k個用戶，將這k個用戶的集合標記為U，然后根據相似度加權得到5。用sim(u,u)表示兩用戶之間的相似度,Pu.s表示預測的分數，則最通用的加權預測公式：

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

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

2.1明考斯基(Minkowski)距離法

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

由于在明考斯基距離法中，距離值越小，表示兩用戶越相似，因此在利用上述預測公式時，需要對距離進行一步轉換：

通過轉換，便可得到相似度值，并滿足預測公式的對相似度值的要求。

2.2Pearson相關系數法

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

Pearson相關系數的值在［-1，1］之間變化。1表示相似度最高，-1表示相似度最低。

但是上述公式有一個嚴重的缺點：需要多趟遍歷數據。這大大提高了算法的時間復雜度。因此一般釆用下述的Pearson相關系數的近似公式：

式中：Sxy 表示用戶 x 和 y 共同打分的物品的集合，card（Sxy）為集合 Sxy 中元素的個數。該近似公式看似復雜，但只需遍歷一遍數據即可，因此，一般用此近似公式來計算 Pearson 相關系數。

2.3Cosine相似性

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

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

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

基于用戶的協同過濾算法利用兩兩用戶之間的相似度來做出預測，相似度算法的選擇決定了預測的精度。上述三種計算相似度的方法是最常見，此外還有許多其它已被提出的計算相似度的方法。

3基于物品(Item-Based)的協同過濾

基于用戶的協同過濾算法在過去已經取得了很大的成功，但隨著它的廣泛應用，漸漸發(fā)現了兩方面的主要問題:

一是規(guī)模性：獲得最鄰近用戶的計算量隨著用戶數和物品數的增加而迅速上升。有著百萬用戶和物品的網絡推薦系統在使用基于用戶的協同過濾算法時將遇到非常嚴重的規(guī)模性問題。

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

此外，基于用戶之間相似度的方案需要實時計算相似度。而且，計算相似度要求必須已知最少數量的物品打分，如果已知的數據太少，計算相似度的結果會非常不準確，進而無法給用戶做出合理的推薦。

3.1AdjustedCosine相似性

基于物品的協同過濾算法一般也需要計算相似度，但是與基于用戶的協同過濾算法的不同之處在于：前者計算的是物品之間的相似度，而后者計算的是用戶之間的相似度。計算物品的相似度，也可以利用上述的Cosine相似性算法，但是利用Cosine相似性算法有一個嚴重的缺點：沒有考慮不同用戶打分習慣的不同。而AdjustedCosine相似性算法作為Cosine相似性算法的改進，通過減去相應用戶打分的平均值，來消除Cosine相似性算法的缺陷。利用AdjustedCosine相似性算法計算物品i和j之間的相似度的公式為：

其中云為用戶u的所有打分平均值。根據物品之間的相似度得到最相似物品集合i后，利用加權方式預測用戶u對物品i的打分:

3.2Slopeone

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

計算物品i相對于物品，的打分偏差公式：

用WeightedSlopeone方法預測用戶u對物品j的打分公式為：

式中：j表示對物品i和j都打過分的用戶集合，cji=card（Uj表示集合Uj中用戶的數量。

Slopeone算法在有著較高精確度的前提下，具有易實現、復雜度低的優(yōu)點。最關鍵的是，Slopeone算法的第一步是可以在系統空閑的時刻提前計算的，這大大降低了查詢時刻的計算量，極大地提高了系統的推薦效率。

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

4結語

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

20211121_619a03831ebe1__協同過濾算法的研究