一、協同過濾算法的原理及實作 二、基于物品的協同過濾算法詳解
一、協同過濾算法的原理及實作
協同過濾推薦算法是誕生最早，并且較為著名的推薦算法。主要的功能是預測和推薦。算法通過對使用者曆史行為資料的挖掘發現使用者的偏好，基于不同的偏好對使用者進行群組劃分并推薦品味相似的商品。協同過濾推薦算法分為兩類，分别是基于使用者的協同過濾算法(user-based collaboratIve filtering)，和基于物品的協同過濾算法(item-based collaborative filtering)。簡單的說就是：人以類聚，物以群分。下面我們将分别說明這兩類推薦算法的原理和實作方法。
1.基于使用者的協同過濾算法(user-based collaboratIve filtering) 基于使用者的協同過濾算法是通過使用者的曆史行為資料發現使用者對商品或内容的喜歡(如商品購買，收藏，内容評論或分享)，并對這些喜好進行度量和打分。根據不同使用者對相同商品或内容的态度和偏好程度計算使用者之間的關系。在有相同喜好的使用者間進行商品推薦。簡單的說就是如果A,B兩個使用者都購買了x,y,z三本圖書，并且給出了5星的好評。那麼A和B就屬于同一類使用者。可以将A看過的圖書w也推薦給使用者B。
1.1尋找偏好相似的使用者 我們模拟了5個使用者對兩件商品的評分，來說明如何通過使用者對不同商品的态度和偏好尋找相似的使用者。在示例中，5個使用者分别對兩件商品進行了評分。這裡的分值可能表示真實的購買，也可以是使用者對商品不同行為的量化名額。例如，浏覽商品的次數，向朋友推薦商品，收藏，分享，或評論等等。這些行為都可以表示使用者對商品的态度和偏好程度。
從表格中很難直覺發現5個使用者間的聯系，我們将5個使用者對兩件商品的評分用散點圖表示出來後，使用者間的關系就很容易發現了。在散點圖中，Y軸是商品1的評分，X軸是商品2的評分，通過使用者的分布情況可以發現，A,C,D三個使用者距離較近。使用者A(3.3 6.5)和使用者C(3.6 6.3)，使用者D(3.4 5.8)對兩件商品的評分較為接近。而使用者E和使用者B則形成了另一個群體。
散點圖雖然直覺，但無法投入實際的應用，也不能準确的度量使用者間的關系。是以我們需要通過數字對使用者的關系進行準确的度量，并依據這些關系完成商品的推薦。 1.2歐幾裡德距離評價 歐幾裡德距離評價是一個較為簡單的使用者關系評價方法。原理是通過計算兩個使用者在散點圖中的距離來判斷不同的使用者是否有相同的偏好。以下是歐幾裡德距離評價的計算公式。 通過公式我們獲得了5個使用者互相間的歐幾裡德系數，也就是使用者間的距離。系數越小表示兩個使用者間的距離越近，偏好也越是接近。不過這裡有個問題，太小的數值可能無法準确的表現出不同使用者間距離的差異，是以我們對求得的系數取倒數，使使用者間的距離約接近，數值越大。在下面的表格中，可以發現，使用者A&C使用者A&D和使用者C&D距離較近。同時使用者B&E的距離也較為接近。與我們前面在散點圖中看到的情況一緻。
1.3皮爾遜相關度評價 皮爾遜相關度評價是另一種計算使用者間關系的方法。他比歐幾裡德距離評價的計算要複雜一些，但對于評分資料不規範時皮爾遜相關度評價能夠給出更好的結果。以下是一個多使用者對多個商品進行評分的示例。這個示例比之前的兩個商品的情況要複雜一些，但也更接近真實的情況。我們通過皮爾遜相關度評價對使用者進行分組，并推薦商品。
1.4皮爾遜相關系數 皮爾遜相關系數的計算公式如下，結果是一個在-1與1之間的系數。該系數用來說明兩個使用者間聯系的強弱程度。 相關系數的分類
- 0.8-1.0 極強相關
- 0.6-0.8 強相關
- 0.4-0.6 中等程度相關
- 0.2-0.4 弱相關
- 0.0-0.2 極弱相關或無相關
通過計算5個使用者對5件商品的評分我們獲得了使用者間的相似度資料。這裡可以看到使用者A&B，C&D，C&E和D&E之間相似度較高。下一步，我們可以依照相似度對使用者進行商品推薦。
2,為相似的使用者提供推薦物品 為使用者C推薦商品 當我們需要對使用者C推薦商品時，首先我們檢查之前的相似度清單，發現使用者C和使用者D和E的相似度較高。換句話說這三個使用者是一個群體，擁有相同的偏好。是以，我們可以對使用者C推薦D和E的商品。但這裡有一個問題。我們不能直接推薦前面商品1-商品5的商品。因為這這些商品使用者C以及浏覽或者購買過了。不能重複推薦。是以我們要推薦使用者C還沒有浏覽或購買過的商品。 權重排序推薦 我們提取了使用者D和使用者E評價過的另外5件商品A—商品F的商品。并對不同商品的評分進行相似度權重。按權重後的結果對5件商品進行排序，然後推薦給使用者C。這樣，使用者C就獲得了與他偏好相似的使用者D和E評價的商品。而在具體的推薦順序和展示上我們依照使用者D和使用者E與使用者C的相似度進行排序。
以上是基于使用者的協同過濾算法。這個算法依靠使用者的曆史行為資料來計算相關度。也就是說必須要有一定的資料積累(冷啟動問題)。對于新網站或資料量較少的網站，還有一種方法是基于物品的協同過濾算法。 基于物品的協同過濾算法(item-based collaborative filtering) 基于物品的協同過濾算法與基于使用者的協同過濾算法很像，将商品和使用者互換。通過計算不同使用者對不同物品的評分獲得物品間的關系。基于物品間的關系對使用者進行相似物品的推薦。這裡的評分代表使用者對商品的态度和偏好。簡單來說就是如果使用者A同時購買了商品1和商品2，那麼說明商品1和商品2的相關度較高。當使用者B也購買了商品1時，可以推斷他也有購買商品2的需求。
1.尋找相似的物品 表格中是兩個使用者對5件商品的評分。在這個表格中我們使用者和商品的位置進行了互換，通過兩個使用者的評分來獲得5件商品之間的相似度情況。單從表格中我們依然很難發現其中的聯系，是以我們選擇通過散點圖進行展示。
在散點圖中，X軸和Y軸分别是兩個使用者的評分。5件商品按照所獲的評分值分布在散點圖中。我們可以發現，商品1,3,4在使用者A和B中有着近似的評分，說明這三件商品的相關度較高。而商品5和2則在另一個群體中。
歐幾裡德距離評價 在基于物品的協同過濾算法中，我們依然可以使用歐幾裡德距離評價來計算不同商品間的距離和關系。以下是計算公式。 通過歐幾裡德系數可以發現，商品間的距離和關系與前面散點圖中的表現一緻，商品1,3,4距離較近關系密切。商品2和商品5距離較近。
皮爾遜相關度評價 我們選擇使用皮爾遜相關度評價來計算多使用者與多商品的關系計算。下面是5個使用者對5件商品的評分表。我們通過這些評分計算出商品間的相關度。
皮爾遜相關度計算公式 通過計算可以發現，商品1&2，商品3&4，商品3&5和商品4&5相似度較高。下一步我們可以依據這些商品間的相關度對使用者進行商品推薦。
2,為使用者提供基于相似物品的推薦 這裡我們遇到了和基于使用者進行商品推薦相同的問題，當需要對使用者C基于商品3推薦商品時，需要一張新的商品與已有商品間的相似度清單。在前面的相似度計算中，商品3與商品4和商品5相似度較高，是以我們計算并獲得了商品4,5與其他商品的相似度清單。
以下是通過計算獲得的新商品與已有商品間的相似度資料。
權重排序推薦 這裡是使用者C已經購買過的商品4,5與新商品A,B,C直接的相似程度。我們将使用者C對商品4,5的評分作為權重。對商品A,B,C進行權重排序。使用者C評分較高并且與之相似度較高的商品被優先推薦。
二、基于物品的協同過濾算法詳解
最近參加KDD Cup 2012比賽，選了track1，做微網誌推薦的，找了推薦相關的論文學習。“Item-Based Collaborative Filtering Recommendation Algorithms”這篇是推薦領域比較經典的論文，現在很多流行的推薦 算法 都是在這篇論文提出的算法的基礎上進行改進的。 一、協同過濾算法描述 推薦系統應用資料分析技術，找出 使用者 最可能喜歡的東西推薦給使用者，現在很多電子商務網站都有這個應用。目前用的比較多、比較成熟的推薦算法是協同過濾 （ Collaborative Filtering，簡稱CF ） 推薦 算法，CF的基本思想是根據使用者之前的喜好以及其他興趣相近的使用者的選擇來給使用者推薦物品。
如圖1所示，在CF中，用m×n的矩陣表示使用者對物品的喜好情況，一般用打分表示使用者對物品的喜好程度，分數越高表示越喜歡這個物品，0表示沒有買過該物品。圖中行表示一個使用者，清單示一個物品，Uij表示使用者i對物品j的打分情況。CF分為兩個過程，一個為 預測 過程，另一個為 推薦 過程。預測過程是預測使用者對沒有購買過的物品的可能打分值，推薦是根據預測階段的結果推薦使用者最可能喜歡的一個或Top-N個物品。 二、User-based算法與Item-based算法對比 CF算法分為兩大類，一類為基于memory的（ Memory-based ），另一類為基于Model的（ Model-based ），User-based和Item-based算法均屬于Memory-based類型，具體細分類可以參考 wikipedia 的說明。 User-based的基本思想是如果使用者A喜歡物品a，使用者B喜歡物品a、b、c，使用者C喜歡a和c，那麼認為使用者A與使用者B和C相似，因為他們都喜歡a，而喜歡a的使用者同時也喜歡c，是以把c推薦給使用者A。該算法用最近鄰居（nearest-neighbor）算法找出一個使用者的鄰居集合，該集合的使用者和該使用者有相似的喜好，算法根據鄰居的偏好對該使用者進行預測。 User-based算法存在兩個重大問題： 1. 資料稀疏性。一個大型的電子商務推薦系統一般有非常多的物品，使用者可能買的其中不到1%的物品，不同使用者之間買的物品重疊性較低，導緻算法無法找到一個使用者的鄰居，即偏好相似的使用者。 2. 算法擴充性。最近鄰居算法的計算量随着使用者和物品數量的增加而增加，不适合資料量大的情況使用。 Iterm-based的基本思想是預先根據所有使用者的曆史偏好資料計算物品之間的相似性，然後把與使用者喜歡的物品相類似的物品推薦給使用者。還是以之前的例子為例，可以知道物品a和c非常相似，因為喜歡a的使用者同時也喜歡c，而使用者A喜歡a，是以把c推薦給使用者A。 因為物品直接的相似性相對比較固定，是以可以預先線上下計算好不同物品之間的相似度，把結果存在表中，當推薦時進行查表，計算使用者可能的打分值，可以同時解決上面兩個問題。 三、Item-based算法詳細過程 （1）相似度計算 Item-based算法首選計算物品之間的相似度，計算相似度的方法有以下幾種： 1. 基于餘弦（Cosine-based）的相似度計算，通過計算兩個向量之間的夾角餘弦值來計算物品之間的相似性，公式如下：
其中分子為兩個向量的内積，即兩個向量相同位置的數字相乘。 2. 基于關聯（Correlation-based）的相似度計算，計算兩個向量之間的Pearson-r關聯度，公式如下：
其中
表示使用者u對物品i的打分，
表示第i個物品打分的平均值。 3. 調整的餘弦（Adjusted Cosine）相似度計算，由于基于餘弦的相似度計算沒有考慮不同使用者的打分情況，可能有的使用者偏向于給高分，而有的使用者偏向于給低分，該方法通過減去使用者打分的平均值消除不同使用者打分習慣的影響，公式如下：
其中
表示使用者u打分的平均值。 （2）預測值計算 根據之前算好的物品之間的相似度，接下來對使用者未打分的物品進行預測，有兩種預測方法： 1. 權重求和。 用過對使用者u已打分的物品的分數進行權重求和，權值為各個物品與物品i的相似度，然後對所有物品相似度的和求平均，計算得到使用者u對物品i打分，公式如下：
其中Si，N為物品i與物品N的相似度，Ru，N為使用者u對物品N的打分。 2. 回歸。 和上面權重求和的方法類似，但回歸的方法不直接使用相似物品N的打分值Ru，N，因為用餘弦法或Pearson關聯法計算相似度時存在一個誤區，即兩個打分向量可能相距比較遠（歐氏距離），但有可能有很高的相似度。因為不同使用者的打分習慣不同，有的偏向打高分，有的偏向打低分。如果兩個使用者都喜歡一樣的物品，因為打分習慣不同，他們的歐式距離可能比較遠，但他們應該有較高的相似度。在這種情況下使用者原始的相似物品的打分值進行計算會造成糟糕的預測結果。通過用線性回歸的方式重新估算一個新的Ru，N值，運用上面同樣的方法進行預測。重新計算Ru，N的方法如下：
其中物品N是物品i的相似物品，
和
通過對物品N和i的打分向量進行線性回歸計算得到，
為回歸模型的誤差。具體怎麼進行線性回歸文章裡面沒有說明，需要查閱另外的相關文獻。 四、結論 作者通過實驗對比結果得出結論：1. Item-based算法的預測結果比User-based算法的品質要高一點。2. 由于Item-based算法可以預先計算好物品的相似度，是以線上的預測性能要比User-based算法的高。3. 用物品的一個小部分子集也可以得到高品質的預測結果。 轉載請注明出處，原文位址：http://blog.csdn.net/huagong_adu/article/details/7362908