Python協同過濾演算法入門（1）相似度計算篇

04-12

一.基於用戶的協同過濾演算法簡介

在推薦系統的眾多方法之中，基於用戶的協同過濾是誕最早的，原理也比較簡單。基於協同過濾的推薦演算法被廣泛的運用在推薦系統中，比如影視推薦、猜你喜歡等、郵件過濾等。該演算法1992年提出並用於郵件過濾系統，兩年後1994年被 GroupLens 用於新聞過濾。一直到2000年，該演算法都是推薦系統領域最著名的演算法。

當用戶A需要個性化推薦的時候，可以先找到和他興趣詳細的用戶集群G，然後把G喜歡的並且A沒有的物品推薦給A，這就是基於用戶的協同過濾。

根據上述原理，我們可以將演算法分為兩個步驟：

1. 找到與目標興趣相似的用戶集群

2. 找到這個集合中用戶喜歡的、並且目標用戶沒有聽說過的物品推薦給目標用戶。

二、常用的相似度計算方法

下面，簡單的舉例幾個機器學習中常用的樣本相似性度量方法：

歐式距離（Euclidean Distance）
夾角餘弦（Cosine）
漢明距離（Hamming distance）

1、歐式距離（Euclidean Distance）

歐式距離是最易於理解的一種距離計算方式，源自歐式空間中兩點間的距離公式。

平面空間內的 $a(x1,y1)$ 與 $b(x2,y2 )$ 間的歐式距離：

$d = sqrt{(x1 - x2)^2 + (y1-y2)^2}$

2. 三維空間里的歐式距離：

$d = sqrt{(x1 - x2)^2 + (y1-y2)^2+(z1-z2)^2}$

3. Python 代碼簡單實現：

import numpy as nparr1 = np.array([1,0,0,0,0,1])arr2 = np.array([1,1,1,2,3,1])arr3 = np.array([3,2,2,2,2,3])def EuclideanDistance(x,y): d = 0 for a,b in zip(x,y): d += (a-b)**2 return d**0.5print(EuclideanDistance(arr1,arr2)) # 3.87298334621print(EuclideanDistance(arr1,arr3)) # 4.89897948557

2、夾角餘弦（Cosine）

首先，樣本數據的夾角餘弦並不是真正幾何意義上的夾角餘弦，只不過是借了它的名字，實際是借用了它的概念變成了是代數意義上的「夾角餘弦」，用來衡量樣本向量間的差異。

幾何意義上的夾角餘弦

夾角越小，餘弦值越接近於1，反之則趨於-1。我們假設有x1與x2兩個向量：

$cos( heta) = frac{sum_{k=1}^{n}{x_{1k}}x_{2k}}{sqrt{sum_{k=1}^{n}{x_{1k}}^2}sqrt{sum_{k=1}^{n}{x_{2k}}^2}}$

Python 代碼的簡單按公式還原：

import numpy as nparr1 = np.array([1,0,0,0,0,1])arr2 = np.array([1,1,1,2,3,1])arr3 = np.array([3,2,2,2,2,3])arr4 = np.array([-1,-1,-1,-2,-3,-1])def cosine(x,y): sum_xy = 0.0; normX = 0.0; normY = 0.0; for a,b in zip(x,y): sum_xy += a*b normX += a**2 normY += b**2 if normX == 0.0 or normY == 0.0: return None else: return sum_xy / ((normX*normY)**0.5) print(cosine(arr1,arr2)) # 0.342997170285print(cosine(arr1,arr3)) # 0.727606875109print(cosine(arr2,arr4)) # -1.0

歐式距離和夾角餘弦的區別：

對比以上的結果的 arr1 與 arr3 和 arr1 與 arr2 這兩組，會發現 arr1 與 arr3 的歐式距離比較大，而夾角餘弦卻更加的接近1，即夾角餘弦更能反映兩者之間的變動趨勢，兩者有很高的變化趨勢相似度，而歐式距離較大是因為兩者數值有很大的區別，即兩者擁有很高的數值差異。

3、漢明距離（Hamming distance）

漢明距離表示的是兩個字元串（相同長度）對應位不同的數量。比如有兩個等長的字元串 str1 = "11111" 和 str2 = "10001" 那麼它們之間的漢明距離就是3（這樣說就簡單多了吧。哈哈）。漢明距離多用於圖像像素的匹配（同圖搜索）。

Python 的矩陣漢明距離簡單運用：

import numpy as nparr1 = np.array([1,0,0,0,0,1])arr2 = np.array([1,1,1,2,3,1])def hammingDistance(x,y): distanceArr = x - y #[0 -1 -1 -2 -3 0] return arr1.shape[0] - np.sum(distanceArr == 0)d = hammingDistance(arr1,arr2)print(d) # 4

三、皮爾遜相關係數（Pearson Correlation Coefficient）

如何理解皮爾遜相關係數（Pearson Correlation Coefficient）？?

www.zhihu.com

假如之不先介紹夾角餘弦的話，第一次接觸你絕對會對皮爾遜相關係數一臉懵逼。那麼現在，讓我們再來理解一下皮爾遜相關係數的公式：

$sim(x_1,x_2) = frac{sum_{k=1}^{n}{(x_{1k} - ar{x_1})}(x_{2k} - ar{x_2})}{sqrt{sum_{k=1}^{n}{(x_{1k} - ar{x_1})}^2}sqrt{sum_{k=1}^{n}{(x_{2k} - ar{x_2})}^2}}$

皮爾遜相關係數公式實際上就是在計算夾角餘弦之前將兩個向量減去各個樣本的平均值，達到中心化的目的。從知友的回答可以明白，皮爾遜相關函數是餘弦相似度在維度缺失上面的一種改進方法。

Python 代碼實現皮爾遜相關係數：

import numpy as nparr1 = np.array([1,0,0,0,0,1])arr2 = np.array([1,1,1,2,3,1])arr3 = np.array([3,2,2,2,2,3])def Pearson(x,y): sum_XY = 0.0 sum_X = 0.0 sum_Y = 0.0 normX = 0.0 normY = 0.0 count = 0 for a,b in zip(x,y): count += 1 sum_XY += a * b sum_X += a sum_Y += b normX += a**2 normY += b**2 if count == 0: return 0 # denominator part denominator = (normX - sum_X**2 / count)**0.5 * (normY - sum_Y**2 / count)**0.5 if denominator == 0: return 0 return (sum_XY - (sum_X * sum_Y) / count) / denominatorprint(Pearson(arr1,arr2)) # -0.462910049886print(Pearson(arr1,arr3)) # 1.0

四、實現基於用戶協同過濾演算法

以下題目和數據均來自於千里碼，一個優質的程序員答題網站，由於站長食年常年失蹤，於是我就無恥的分享出來啦。

現在從豆瓣的用戶中抽取了500左右個比較活躍的用戶，這些用戶都是忠實的電影迷，大部分人涉獵了上百部電影。
這裡有個80多萬行的文本文件，文件的每行是三個數字，分別是 userid，movieid，rating。代表一個用戶對一部電影的評分。rating代表評分的星級，如上圖中的紅框所示，星級從低到高依次是1-5。
接下來有個行數為10001的文本文件（第一行為title），文件的每行為2個數字，分別代表userid和movieid，請你預測如果該用戶觀看了這部電影，會給該電影打多少分，你的預測值為1個大小為1-5的整數。
本題的答案是一個長度為1萬的字元串，字元串的第k位代表你對第k行的預測結果。
如果你的預測結果和實際答案的差值的絕對值的和小於6000，通過該題。

千里碼答案提交鏈接：http://www.qlcoder.com/task/7650

import numpy as np# Pearson Correlation Coefficientdef Pearson(x,y): sum_XY = 0.0 sum_X = 0.0 sum_Y = 0.0 normX = 0.0 normY = 0.0 count = 0 for key in x: if key in y: a = x[key] b = y[key] count += 1 sum_XY += a * b sum_X += a sum_Y += b normX += a**2 normY += b**2 if count == 0: return 0 denominator = (normX - sum_X**2 / count)**0.5 * (normY - sum_Y**2 / count)**0.5 if denominator == 0: return 0 else: return (sum_XY - (sum_X * sum_Y) / count) / denominatorwith open(train.txt) as f: data = f.read() data = data.split( ) # data structure # userid,movieid,rating lists = {} for item in data[1:-1]: item = item.split(,) if item[0] not in lists: lists[item[0]] = {} lists[item[0]][item[1]] = int(item[2]) else: lists[item[0]][item[1]] = int(item[2]) # lists = {userId:{movieId:rate}} with open(test.txt) as t: t_data = t.read() t_data = t_data.split( ) number = 0 result = # t_data = [userId,movieId] for i in t_data[1:]: arr = i.split(,) t_userid = arr[0] t_moveid = arr[1] testList = lists[t_userid] userList = list(testList.values()) score = 0 resultRate = 0 max_score = -1 for userid in lists: if userid != t_userid: nearList = lists[userid] checkList = [] if t_moveid in nearList: for umoveid in testList: if umoveid in nearList: checkList.append(nearList[umoveid]) new_score = Pearson(userList,checkList) new_score = 0.5 + 0.5 * new_score # 歸一化將[-1:1]的取值範圍變成[0:1] if new_score > score: resultRate = nearList[t_moveid] score = new_score number += 1 print(number) result = result + str(resultRate) with open(result.txt,w) as res: res.write(result)

提交答案，結果誤差在9500-10000之間，沒有達到題目的要求，說明光基於皮爾遜相關係數進行協同過濾的精確度偏差比較大，推薦結果不盡如人意，強烈懷疑部分數據具有干擾性（千里碼捐題人的正常操作。。。）那麼接下來的文章，我們將會通過矩陣奇異值分解（SVD），非負矩陣分解（NMF）等演算法更深入的學習優化協同過濾演算法，使我們的演算法精確度更高，歡迎關注後續文章。

歡迎點贊，歡迎評論一起交流學習，感謝支持。