1 什么是協(xié)同過濾

協(xié)同過濾是利用集體智慧的一個典型方法。要理解什么是協(xié)同過濾 (Collaborative Filtering, 簡稱 CF)，首先想一個簡單的問題，如果你現(xiàn)在想看個電影，但你不知道具體看哪部，你會怎么做？大部分的人會問問周圍的朋友，看看最近有什么好看的電影推薦，而我們一般更傾向于從口味比較類似的朋友那里得到推薦。這就是協(xié)同過濾的核心思想。

換句話說，就是借鑒和你相關(guān)人群的觀點來進行推薦，很好理解。

2 協(xié)同過濾的實現(xiàn)

要實現(xiàn)協(xié)同過濾的推薦算法，要進行以下三個步驟：

收集數(shù)據(jù)——找到相似用戶和物品——進行推薦

3.收集數(shù)據(jù)

這里的數(shù)據(jù)指的都是用戶的歷史行為數(shù)據(jù)，比如用戶的購買歷史，關(guān)注，收藏行為，或者發(fā)表了某些評論，給某個物品打了多少分等等，這些都可以用來作為數(shù)據(jù)供推薦算法使用，服務(wù)于推薦算法。需要特別指出的在于，不同的數(shù)據(jù)準確性不同，粒度也不同，在使用時需要考慮到噪音所帶來的影響。

4.找到相似用戶和物品

這一步也很簡單，其實就是計算用戶間以及物品間的相似度。以下是幾種計算相似度的方法(可以在Mahout的taste里的幾種相似度計算方法)：

最初用于計算歐幾里德空間中兩個點的距離，以兩個用戶x和y為例子，看成是n維空間的兩個向量x和y, xi表示用戶x對itemi的喜好值，yi表示用戶y對itemi的喜好值，他們之前的歐幾里德距離是

對應(yīng)的歐幾里德相似度，一般采用以下公式進行轉(zhuǎn)換：距離越小，相似度越大

在taste里，計算user之間和item之前歐幾里德相似度的類是EuclideanDistanceSimilarity。

皮爾遜相關(guān)系數(shù)一般用于計算兩個定距變量間線性相關(guān)的緊密程度，它的取值在[-1,+1]之間。當取值大于0時表示兩個變量是正相關(guān)的，即一個變量的值越大，另一個變量的值也會越大；當取值小于0時表示兩個變量是負相關(guān)的，即一個變量的值越大，另一個變量的值反而會越小。其計算公式如下

其中sx和sy是樣品的標準偏差

在taste里，PearsonCorrelationSimilarity的實現(xiàn)方式不是采用上述公式，而是采用3的實現(xiàn)。

就是兩個向量的夾角余弦，被廣泛應(yīng)用于計算文檔數(shù)據(jù)的相似度

在taste里，實現(xiàn)Cosine相似度的類是PearsonCorrelationSimilarity，另外一個類UncenteredCosineSimilarity的實現(xiàn)了形式化以后的cosine向量夾角，如下公式

用這種公式計算的原因如下：余弦相似度更多的是從方向上區(qū)分差異，而對絕對的數(shù)值不敏感。因此沒法衡量每個維數(shù)值的差異，會導(dǎo)致這樣一個情況：比如用戶對內(nèi)容評分，5分制，X和Y兩個用戶對兩個內(nèi)容的評分分別為(1,2)和(4,5)，使用余弦相似度得出的結(jié)果是0.98，兩者極為相似，但從評分上看X似乎不喜歡這2個內(nèi)容，而Y比較喜歡，余弦相似度對數(shù)值的不敏感導(dǎo)致了結(jié)果的誤差，需要修正這種不合理性，就出現(xiàn)了調(diào)整余弦相似度，即所有維度上的數(shù)值都減去一個均值，比如X和Y的評分均值都是3，那么調(diào)整后為(-2,-1)和(1,2)，再用余弦相似度計算，得到-0.8，相似度為負值并且差異不小，但顯然更加符合現(xiàn)實。

Tanimoto系數(shù)也稱Jaccard系數(shù)，是Cosine相似度的擴展，也多用于計算文檔相似度。計算公式如下：

其中x表示用戶x所喜好的所有item的集合，y表示用戶y所喜好的所有item的集合。

在taste里，實現(xiàn)Tanimoto相似度的類是TanimotoCoefficientSimilarity，可以看出這種計算方法適用于用戶對item的喜好是0和1那種情況。

出租車幾何或曼哈頓距離（Manhattan Distance）是由十九世紀的赫爾曼·閔可夫斯基所創(chuàng)詞匯，是種使用在幾何度量空間的幾何學(xué)用語，用以標明兩個點上在標準坐標系上的絕對軸距總和。圖中紅線代表曼哈頓距離，綠色代表歐氏距離，也就是直線距離，而藍色和黃色代表等價的曼哈頓距離。

計算公式是：

轉(zhuǎn)換后的相似度為：

在tasete里的實現(xiàn)類CityBlockSimilarity采用了簡化的計算方式，比較適用于用戶的喜歡數(shù)據(jù)時0或者1的情況

公式比較復(fù)雜，實現(xiàn)類為LogLikelihoodSimilarity，比較適用于用戶的喜歡數(shù)據(jù)時0或者1的情況

斯皮爾曼相關(guān)性可以理解為是排列后（Rank）用戶喜好值之間的Pearson相關(guān)度。《Mahout in Action》中有這樣的解釋：假設(shè)對于每個用戶，我們找到他最不喜歡的物品，重寫他的評分值為“1”；然后找到下一個最不喜歡的物品，重寫評分值為“2”，依此類推。然后我們對這些轉(zhuǎn)換后的值求Pearson相關(guān)系數(shù)，這就是Spearman相關(guān)系數(shù)。

斯皮爾曼相關(guān)度的計算舍棄了一些重要信息，即真實的評分值。但它保留了用戶喜好值的本質(zhì)特性——排序（ordering），它是建立在排序（或等級，Rank）的基礎(chǔ)上計算的。

因為斯皮爾曼相關(guān)性的計算需要花時間計算并存儲喜好值的一個排序（Ranks），具體時間取決于數(shù)據(jù)的數(shù)量級大小。正因為這樣，斯皮爾曼相關(guān)系數(shù)一般用于學(xué)術(shù)研究或者是小規(guī)模的計算。

在taste里的實現(xiàn)類為SpearmanCorrelationSimilarity

5.進行推薦

在知道了如何計算相似度后，就可以進行推薦了。

在協(xié)同過濾中，有兩種主流方法：基于用戶的協(xié)同過濾，和基于物品的協(xié)同過濾。具體怎么來闡述他們的原理呢，看個圖大家就明白了

基于用戶的 CF 的基本思想相當簡單，基于用戶對物品的偏好找到相鄰鄰居用戶，然后將鄰居用戶喜歡的推薦給當前用戶。計算上，就是將一個用戶對所有物品的偏好作為一個向量來計算用戶之間的相似度，找到 K 鄰居后，根據(jù)鄰居的相似度權(quán)重以及他們對物品的偏好，預(yù)測當前用戶沒有偏好的未涉及物品，計算得到一個排序的物品列表作為推薦。 下圖給出了一個例子，對于用戶 A，根據(jù)用戶的歷史偏好，這里只計算得到一個鄰居 - 用戶 C，然后將用戶 C 喜歡的物品 D 推薦給用戶 A。

基于物品的 CF 的原理和基于用戶的 CF 類似，只是在計算鄰居時采用物品本身，而不是從用戶的角度，即基于用戶對物品的偏好找到相似的物品，然后根據(jù)用戶的歷史偏好，推薦相似的物品給他。從計算的角度看，就是將所有用戶對某個物品的偏好作為一個向量來計算物品之間的相似度，得到物品的相似物品后，根據(jù)用戶歷史的偏好預(yù)測當前用戶還沒有表示偏好的物品，計算得到一個排序的物品列表作為推薦。下圖給出了一個例子，對于物品 A，根據(jù)所有用戶的歷史偏好，喜歡物品 A 的用戶都喜歡物品 C，得出物品 A 和物品 C 比較相似，而用戶 C 喜歡物品 A，那么可以推斷出用戶 C 可能也喜歡物品 C。

6.舉個例子來說明：

上面每一行代表一個用戶，每一列代表一個商品，比如第2行第一列的3表示用戶2對商品1的評分為3，0代表對應(yīng)的用戶還沒有購買過該商品，現(xiàn)在想預(yù)測用戶2對商品4的評分：

• 找出對商品4評過分的用戶：用戶1,3,5,8,9,10，評分分別為：4, 2, 1, 3, 3, 1
• 分別計算用戶2與用戶1,3,5,8,9,10之間的相似度，相似度的計算方法有很多，常用的分為3類：歐氏距離，余弦相似度，皮爾遜相關(guān)系數(shù)，網(wǎng)上很容易查到，這里以常用的余弦相關(guān)系數(shù)說明：

　　　　　要計算用戶2與用戶1之間的相似度，首先找到二者都評過分的商品為：商品1, 2, 9, 10,用戶1對這4個商品的評分向量為r1=[5 3 4 4],用戶2對這4個商品評分向量為r2=[3 1 1 2];所謂余弦相似度就是利用兩個向量之間夾角的余弦值來衡量兩個向量之間的相似度，顯然夾角越小，余弦值就越大，兩個向量就越靠近，即二者越相似，于是用戶2和用戶1之間的相似度就為sim2_1=(5*3 + 3*1 + 4*1 + 4*2)/ (||r1|| * ||r2||) = 0.953, 其中||r||代表向量r的模長或者2范數(shù)，類似地分別計算出用戶2與用戶3 5 8 9 10之間的sim2_3,sim2_5,sim2_8,sim2_9,sim2_10

• 最后利用相似度加權(quán)得到用戶2對商品4的預(yù)測評分：PRedict = 4*sim2_1 + 2*sim2_3 + 1*sim2_5 + 3*sim2_8 +3*sim2_9 + 1*sim2_10
• 基于物品相似度就是與上面計算過程幾乎相似，只是計算的是物品之間的相似度

1. 計算其他用戶和你的相似度，可以使用反差表忽略一部分用戶
2. 根據(jù)相似度的高低找出K個與你最相似的鄰居
3. 在這些鄰居喜歡的物品中，根據(jù)鄰居與你的遠近程度算出每一件物品的推薦度
4. 根據(jù)每一件物品的推薦度高低給你推薦物品。

package pku;

import java.io.BufferedReader;import java.io.File;import java.io.FileNotFoundException;import java.io.FileReader;import java.io.IOException;import java.util.ArrayList;import java.util.Arrays;import java.util.List;

public class Recommendation {public static final int KNEIGHBOUR = 3;public static final int COLUMNCOUNT = 8;//number of itemspublic static final int PREFROWCOUNT = 20;public static final int TESTROWCOUNT = 5;private String[] bookName = {"數(shù)據(jù)挖掘：概念與技術(shù)","金融工程","投資銀行學(xué)","算法導(dǎo)論","machine learning","經(jīng)濟學(xué)原理","金融的邏輯","Thinking in Java"};public void generateRecommendations() {int[][] preference = readFile(PREFROWCOUNT, "preference.data");int[][] test = readFile(TESTROWCOUNT, "test.data");double[][] similarityMatrix = produceSimilarityMatrix(preference);//for (int i = 0; i < similarityMatrix.length; i++) {//for (int j = 0; j < similarityMatrix[0].length; j++) {//System.out.print(similarityMatrix[i][j]+" ");//}//System.out.println();//}List<Integer> neighborSerial = new ArrayList<Integer>();for (int i = 0; i < TESTROWCOUNT; i++) {neighborSerial.clear();double max = 0;int itemSerial = 0;for (int j = 0; j < COLUMNCOUNT; j++) {if(test[i][j] == 0) {double similaritySum = 0;double sum = 0;double score = 0;neighborSerial = findKNeighbors(test[i], j, similarityMatrix);for (int m = 0; m < neighborSerial.size(); m++) {sum += similarityMatrix[j][neighborSerial.get(m)] * test[i][neighborSerial.get(m)];similaritySum += similarityMatrix[j][neighborSerial.get(m)];}score = sum / similaritySum;if(score > max) {max = score;itemSerial = j;}}}System.out.println("The book recommended for user "+i+" is: "+bookName[itemSerial]+" score: "+max);}}/** * This method is used to find the nearest K neighbors to the un_scored item * @param score * @param i * @param similarityMatrix * @return */private List<Integer> findKNeighbors(int[] score,int i,double[][] similarityMatrix) {//該方法有三個參數(shù)，score表示某一用戶對所有項目的評分；i表示某個項目的序號List<Integer> neighborSerial = new ArrayList<Integer>();double[] similarity = new double[similarityMatrix.length];for (int j = 0; j < similarityMatrix.length; j++) {if(score[j] != 0) {similarity[j] = similarityMatrix[j][i];} else {similarity[j] = 0;}}double[] temp = new double[similarity.length];for (int j = 0; j < temp.length; j++) {temp[j] = similarity[j];}Arrays.sort(temp);for(int j = 0; j < similarity.length; j++) {for (int m = temp.length - 1; m >= temp.length - KNEIGHBOUR; m--) {if (similarity[j] == temp[m] && similarity[j] != 0.0)neighborSerial.add(new Integer(j));}}return neighborSerial;}/** * This method is used to produce similarity matrix among items * @param preference * @return */private double[][] produceSimilarityMatrix(int[][] preference) {double[][] similarityMatrix = new double[COLUMNCOUNT][COLUMNCOUNT];for (int i = 0; i < COLUMNCOUNT; i++) {for (int j = 0; j < COLUMNCOUNT; j++) {if (i == j) {similarityMatrix[i][j] = 0;}else {similarityMatrix[i][j] = computeSimilarity(preference[i], preference[j]);}}}//for (int i = 0; i < similarityMatrix.length; i++) {//for (int j = 0; j < similarityMatrix[0].length; j++) {//System.out.print(similarityMatrix[i][j]);//}//System.out.println();//}//System.out.println("**********");return similarityMatrix;}/** * This method is used to compute similarity between two items * @param item1 * @param item2 * @return */private double computeSimilarity(int[] item1,int[] item2) {List<Integer> list1 = new ArrayList<Integer>();List<Integer> list2 = new ArrayList<Integer>();int j = 0;for (int i = 0; i < item1.length; i++) {if(item1[i] != 0 && item2[i] !=0) {list1.add(new Integer(item1[i]));list2.add(new Integer(item2[i]));}j++;}return pearsonCorrelation(list1,list2);}/** * This method is used to read file and store file data into arrays * @param rowCount * @param fileName * @return */private int[][] readFile(int rowCount,String fileName) {int[][] preference = new int[rowCount][COLUMNCOUNT];try {File file = new File(fileName);FileReader fr = new FileReader(file);BufferedReader br = new BufferedReader(fr);String line = "";int i = 0;while (br.ready()) {line = br.readLine();String[] data = line.split(",");for (int j = 0; j < data.length; j++) {preference[i][j] = Integer.parseInt(data[j]);}i++;}} catch (FileNotFoundException e) {e.printStackTrace();} catch (IOException e) {e.printStackTrace();}return preference;}/** * This method is used to compute Pearson Correlation between two items * @param a * @param b * @return */private double pearsonCorrelation(List<Integer> a,List<Integer> b) {int num = a.size();int sum_prefOne = 0;int sum_prefTwo = 0;int sum_squareOne = 0;int sum_squareTwo = 0;int sum_product = 0;for (int i = 0; i < num; i++) {sum_prefOne += a.get(i);sum_prefTwo += b.get(i);sum_squareOne += Math.pow(a.get(i), 2);sum_squareTwo += Math.pow(b.get(i), 2);sum_product += a.get(i) * b.get(i);}double sum = num * sum_product - sum_prefOne * sum_prefTwo;double den = Math.sqrt((num * sum_squareOne - Math.pow(sum_squareOne, 2)) * (num * sum_squareTwo - Math.pow(sum_squareTwo, 2)));double result = sum / den;return result;}public static void main (String[] args) {Recommendation application = new Recommendation();application.generateRecommendations();}}