基本思想

我們根據涂色樣本點和未涂色樣本點 X 的距離給涂色樣本點編號1-6，即：1號樣本點距離X最近，其余次之。

那么問題來了：樣本點 X 應該屬于哪種顏色呢？是藍色還是綠色？

其實，我們可以根據 X 的相鄰樣本點來判定。例如，和 X 距離最近的三個樣本點中綠色占多數，那么 X 就屬于為綠色；和 X 距離最近的 5 個樣本點中藍色占多數，那么 X 就屬于藍色。

這種解決問題的思路正是 K 近鄰算法的基本思想：根據 K 個近鄰樣本的 y 值來預測自身的 y 值。具體到上面例子中的 y 值就是樣本點的顏色。

K 近鄰是監督學習中比較簡單的一種算法，它既可以解決分類問題，也可以解決回歸問題。

上面的涂色問題本質上就是利用 K 近鄰算法給顏色未知的樣本進行分類。顏色已知的樣本屬于訓練樣本，顏色未知的樣本屬于測試樣本。

我們已經知道 K 近鄰算法的基本思想是根據 K 個近鄰樣本的 y 值來預測自身的 y 值。具體到分類問題中，y 值就是樣本類別的取值，一般采用多數表決的原則來對測試樣本的類別進行預測。

那么如何使用 K 近鄰來解決回歸問題呢？請看下圖：

回歸問題中預測的 y 值是一個連續值，上圖中每個樣本點周圍的數字代表其 y 值，K近鄰是將離 X 最近的 K個樣本的 y 值的平均值作為 X 的預測 y 值。例如：K=3 時，X 的預測輸出 y = (1.2+3.4+8.3)/3 = 4.3；K=5 時，X 的預測輸出 y = (1.2+3.4+8.3+5.5+4.5)/5 = 4.58 。

歐氏距離

圖中的 a 和 b 代表兩個樣本，更具體一點說是樣本的特征向量，每個樣本的特征向量維度是2，即：每個樣本都有兩個特征。

a 和 b 其實是二維特征空間中的兩個點，拓展到更高維的空間的距離公式是類似的：

發現規律了嗎？其實就是先計算向量 a 和向量 b 對應維度數值差的平方和，然后再開方。由此我們可以寫出任意維特征向量 a 和 b 的歐式距離公式：

算法流程

本門課中主要探討 K 近鄰在分類問題上的應用，下面我們來看一下 K 近鄰分類算法的流程：

第一步：準備訓練樣本集：data = {[x1,x2,…,xn,y],…}，其中 x1,x2,…,xn 是樣本特征，y 是樣本類別取值。

例如我們有一個特征維數為 2、樣本數量為 3 的訓練集：data = {[1,2,0],[3,1,0],[2,3,1]}，則其中的樣本分別為 [1,2,0]、[3,1,0]、[2,3,1]，樣本特征分別為 [1,2]、[3,1]、[2,3]，樣本類別分別為 0、0、1。

第二步：輸入測試樣本 A：[x1,x2,…,xn]，例如測試樣本的特征是二維的 [1,4]

第三步：計算測試樣本 A 和所有訓練樣本的距離。

具體來講，可以是第二步中的測試樣本 [1,4] 和第一步中的訓練樣本 [1,2]、[3,1]、[2,3] 分別計算歐式距離。

第四步：按照距離遞增排序。

第五步：選取與 A 距離最小的 K 個樣本。

第六步：計算這 K 個樣本所在類別的出現頻率。

第七步：返回出現頻率最高的類別作為 A 的預測分類。

K 近鄰中的 K 值是人為設定的參數， K 值的選取會對預測結果產生影響。除了 K 值外，K 近鄰的預測結果還受距離度量和決策規則的影響。
距離度量實際上是衡量兩個樣本的相似程度：距離越小，相似程度越高。常見的相似性度量函數有：歐氏距離、余弦相似性、皮爾遜相關系數

代碼

# 1. 導入工具包
import numpy as np
import pandas as pd
from collections import Counter# 2. 歐式距離定義
def euclidean_distance(vec1,vec2):return np.sqrt(np.sum(np.square(vec1 - vec2)))# 3. 構造數據集  
train_data = {'寶貝當家':[45,2,9,'喜劇片'],'美人魚':[21,17,5,'喜劇片'],'澳門風云3':[54,9,11,'喜劇片'],'功夫熊貓3':[39,0,31,'喜劇片'],'諜影重重':[5,2,57,'動作片'],'葉問3':[3,2,65,'動作片'],'我的特工爺爺':[6,4,21,'動作片'],'奔愛':[7,46,4,'愛情片'],'夜孔雀':[9,39,8,'愛情片'],'代理情人':[9,38,2,'愛情片'],'新步步驚心':[8,34,17,'愛情片'],'倫敦陷落':[2,3,55,'動作片']}train_df =  pd.DataFrame(train_data).T
train_df.columns = ['搞笑鏡頭','擁抱鏡頭','打斗鏡頭','電影類型']test_data = {'唐人街探案':[23,3,17]} # 4. 確定K值和分類的電影
K = 5
movie = '唐人街探案'# 5. 計算歐式距離
distance_list = []
for train_X in train_df.values[:,:-1]:test_X = np.array(test_data[movie])distance_list.append(euclidean_distance(train_X,test_X))# 6. 按照距離遞增排序
distance_df = pd.DataFrame({"歐式距離":distance_list},index=train_df.index)
result = pd.concat([train_df,distance_df],axis=1).sort_values(by="歐式距離")# 7. ToDo：輸出分類結果
d = Counter(result.head(K)['電影類型'])
print(movie,max(d,key=d.get))

基于近鄰用戶的協同過濾

假定有一個場景：某個周日的下午，你感覺很無聊，然后從電腦上打開了一個視頻網站，想看下最近有什么好看的電影。然而你發現網站上的熱門電影基本都看過，其他的電影又太多，不知道該看什么。想使用搜索框去查一下，但是又不知道該搜什么關鍵詞，這個時候你的內心很焦灼，總不能挨個去嘗試吧，那時間成本也太大了…

仔細想想還是有辦法的，那就是問一下你的好朋友，他最近喜歡看什么電影，讓他給你推薦幾部好看的電影，這樣就省去了自己去挑選和嘗試的時間了。

這種思想其實就是基于近鄰用戶的協同過濾算法（簡稱UserCF）：給用戶 A 推薦和他有著相似觀影興趣的用戶 B 喜歡觀看的電影。如圖所示：

從圖中可以看出，用戶 A 的好友用戶 B 喜歡看電影 2、3、4，恰好電影 3 和電影 4 用戶 A 沒有看過，所以就可以把電影 3 和電影 4 推薦給用戶 A 。

基于近鄰用戶的協同過濾算法很容易給出的推薦理由是：和你興趣相似的人還喜歡下面的電影。

那為什么說用戶 A 和用戶 B 的觀影興趣相似呢？生活中的經驗告訴我們：物以類聚人以群分。既然 A 和 B 能夠成為好朋友，那么他們必然就有著某些共同的價值觀和興趣愛好。

體現在上面的這幅圖中為：用戶 A 和用戶 B 都觀看過電影 2 。

基于近鄰用戶的協同過濾算法，第一個要理解的點是近鄰用戶，也就是興趣相似的用戶；第二個要理解的點是協同過濾算法到底指的是什么？

所謂的協同過濾，其實指的是一類算法的稱呼：根據用戶的行為數據給用戶產生推薦結果的一類算法。

上面我們是根據用戶的觀影記錄，即每個用戶看過哪些電影，來進行電影推薦，所以它屬于協同過濾的一種。

既然可以將用戶 B 喜歡的電影推薦給用戶 A，那么用戶 A 喜歡的電影也可以推薦給用戶 B。所以，基于近鄰用戶的協同過濾算法是在觀影興趣相似的用戶間互相推薦電影。如圖所示：

細心觀察可以發現，電影 2 并沒有在用戶 A 和用戶 B 中進行推薦。原因是：推薦系統的本質是建立用戶和物品的連接，電影 2 在用戶 A 和用戶 B 上已經存在連接了，所以也就不需要再進行推薦了。

另一方面，看過的電影一般就不再推薦了，這個也符合生活常識。

假如用戶 A 前兩天剛看過電影 2，然后你又給他推薦電影 2，這顯然不是用戶 A 想要的結果。

這里有一個發散性的想法：如果電影 2 是用戶 A 和用戶 B 十多年前看過的電影，是不是可以再推薦給他們懷舊一下呢，哈哈~

通過這個發散性的想法，我想表達的一個觀點是：推薦系統要做的事情其實是分析用戶的心理，讓用戶滿意，給到他們想要的東西，也給到使他們驚喜和意外的東西。

下面我們來梳理一下基于近鄰用戶的協同過濾算法實現的流程：

比如我們需要給用戶 A 推薦電影，那么首先要找到和用戶 A 觀影興趣最相似的 K 個用戶，然后再從這 K 個用戶喜歡的電影中，找到用戶 A 沒有看過的電影，推薦給 A。

如圖所示，先不考慮相似度的計算方法，K=3 的情況下，和用戶 A 最相似的 3 個用戶依次是用戶 B、C、D，從這 3 個用戶喜歡的電影集合中過濾掉用戶 A 看過的電影，然后計算 A 對剩下的電影感興趣的程度，從中選取最感興趣的的 3 個電影推薦給用戶 A 。這里的推薦數量根據產品需求來設定，不一定是 3。

這里的感興趣程度計算方法是將每個電影上有觀看行為的用戶相似度求和得到的，例如 A 對電影 2 的感興趣程度為：用戶 B 的 0.8 + 用戶 C 的 0.6 = 1.4

基于近鄰物品的協同過濾

推薦系統會根據你過往看過的電影，從電影庫中查找相似的電影推薦給你，這種方法叫做基于近鄰物品的協同過濾算法（簡稱ItemCF）。如圖所示：

用戶 A 看過電影 1，那么就給他推薦相似的電影 2；用戶 D 看過電影 2，那么就給他推薦相似的電影 1。電影 1 和電影 2 相似是因為他們有著共同的觀影群體（B和C）。基于近鄰物品的協同過濾算法常見的推薦理由是：看了該電影的用戶還看了如下電影

基于近鄰物品的協同過濾算法，第一個要理解的點是近鄰物品，也就是用戶群體相似的物品；第二個要理解的點是協同過濾，這個前面已經講過，核心是利用了用戶行為數據，此處不再贅述。

從上面的圖中可以看出，推薦系統只在電影 2 和用戶 A 之間、電影 1 和用戶 D 之間建立了推薦路線，原因是用戶 B 和用戶 C 之前都和這兩個電影有過觀看連接。

換個說法，因為用戶 B 看過電影 1 和電影 2，所以只能給用戶 B 推薦和電影 1 或電影 2 相似的電影，而不是推薦電影 1 和電影 2 本身。圖示僅作示意，實際上還有很多電影可以和用戶 B 建立連接，前提是要滿足用戶 B 的興趣。

總結一下：基于近鄰物品的協同過濾算法是給用戶推薦和他過去喜歡的電影相似的電影。具體的算法流程是：比如我們要給用戶 A 推薦電影，首先要在用戶 A 喜歡的電影中分別找到 K 個最相似的電影，然后再從這些電影中找到用戶 A 沒看過的電影推薦給 A 。

這里的感興趣程度計算方法是將每個候選電影上的電影相似度求和得到的，例如 A 對電影 4 的感興趣程度為：電影 4 和電影 1 的相似度 0.5 + 電影 4 和電影 2 的相似度 0.4 = 0.9

杰卡德相似度

前面我們講的兩種基于近鄰的協同過濾算法有一個共同點，那就是計算相似度。其實在本章第 1節課中我們已經提到了幾種相似度的計算方法，比如歐氏距離、余弦相似性、皮爾遜相關系數。

下面我們再介紹一種相似度的計算方法：杰卡德（Jaccard）相似度，杰卡德相似度是指兩個集合的交集元素個數在并集中所占的比例。先來看一幅圖片：

圖中展現的是代表用戶觀影記錄的行為矩陣，矩陣中的 1 表示用戶看過對應的電影，0 表示沒看過。據此，我們可以根據杰卡德相似度定義分別計算出用戶的相似度矩陣和電影的相似度矩陣。先來看用戶相似度矩陣：

圖中用戶相似度矩陣的取值是關于對角線對稱的，實際上我們需要的只有右上角的 6個值。那么這些值是怎么算出來的呢？

就拿用戶 B 和用戶 D 的相似度 1/3 舉例吧，杰卡德相似度其實就是交集和并集的占比，如圖所示：