電影分析——K近鄰算法

周末，小迪與女朋友小西走出電影院，回味著剛剛看過的電影。

小迪：剛剛的電影很精彩，打斗場景非常真實，又是一部優(yōu)秀的動作片！

小西：是嗎？我怎么感覺這是一部愛情片呢？真心被男主女主的愛情感動了，唔。。。

小迪：是動作片好不好？不信的話我們用K近鄰來分類！

小西：K近鄰是什么，怎么分類？

小迪：我們以接吻鏡頭與打斗鏡頭作為兩種電影的特征，只要知道一部電影的接吻鏡頭與打斗鏡頭的個數，利用現有的帶標簽數據集便可以對未知類型的電影進行類型預測。

小西：不是很明白，可以講簡單點嗎？

小迪：我們可以這樣理解，假設有一個未知的x，我們盡量讓特征相近的的點靠近，這樣想要知道x是什么性質的，我們可以觀察它鄰近的k個點，這些點多數是什么性質的，那么x的性質也就是可以預測出來了。

小西：哦哦，明白了。有點像那句俗語——物以類聚人以群分呢！

小迪：是啊，是有這么個意思！我們回去用python實現一下這個算法吧。

小西：好的，走！

K近鄰算法概述

k-近鄰算法（k-Nearest Neighbour algorithm），又稱為KNN算法，是數據挖掘技術中原理最簡單的算法。KNN的工作原理：給定一個已知標簽類別的訓練數據集，輸入沒有標簽的新數據后，在訓練數據集中找到與新數據最鄰近的k個實例，如果這k個實例的多數屬于某個類別，那么新數據就屬于這個類別。

如上圖中有紅色三角和藍色方塊兩種類別，現在需要判斷綠色圓點屬于哪種類別

當k=3時，綠色圓點屬于紅色三角這種類別；

當k=5時，綠色圓點屬于藍色方塊這種類別。

K近鄰分類電影類型

小迪回到家，打開電腦，想實現一個分類電影的案例。于是他找了幾部前段時間比較熱門的電影，然后根據接吻鏡頭與動作鏡頭打上標簽，用k-近鄰算法分類一個電影是愛情片還是動作片（打斗鏡頭和接吻鏡頭數量為虛構）。

表中就是已有的數據集合，也就是訓練樣本集。這個數據集有兩個特征——打斗鏡頭數和接吻鏡頭數。除此之外，每部電影的所屬類型也是已知的，即分類標簽。粗略看來，接吻鏡頭多的就是愛情片，打斗鏡頭多的就是動作片。多年來的經驗就是如此。如果現在有一部新的電影，告知電影中的打斗鏡頭和接吻鏡頭分別是多少，那么多數人可以根據給出的信息進行判斷，這部電影是屬于愛情片還是動作片。而k-近鄰算法也可以像人類一樣做到這一點。但是，這僅僅是兩個特征，如果特征變成10，100，1000甚至更多，恐怕人類就難以完成這樣的任務了。但是有了算法的計算機是不怕疲勞而且精于計算的，這樣的問題可以輕松解決！

已經知道k-近鄰算法的工作原理，根據特征比較，然后提取樣本集中特征最相似數據（最近鄰）的分類標簽。那么如何進行比較呢？比如表中新出的電影，該如何判斷它所屬的電影類別呢？如下圖所示。

從散點圖中大致推斷，這個未知電影有可能是愛情片，因為看起來距離已知的三個愛情片更近一點。而在k-近鄰算法中是利用距離進行判斷的。這個電影分類例子中有兩個特征，也就是在二維平面中計算兩點之間的距離，這很容易可以聯想到中學時代學過的距離公式：

如果是多個特征擴展到N維空間，怎么計算？可以使用歐氏距離（也稱歐幾里得度量），如下所示：

通過計算可以得到訓練集中所有電影與未知電影的距離，如下表所示：

通過上面表中的計算結果，小迪知道綠點標記的電影到愛情片《后來的我們》距離最近，為29.1。如果僅僅根據這個結果，判定綠點電影的類別為愛情片，是不是這樣呢？答案是不是，這個算法叫做最近鄰算法，只看距離最近的一個點，而不是k個點，所以不是k-近鄰算法。k-近鄰算法步驟如下：

(1) 計算已知類別數據集中的點與當前點之間的距離；
(2) 按照距離遞增次序排序；
(3) 選取與當前點距離最小的k個點；
(4) 確定前k個點所在類別的出現頻率；
(5) 返回前k個點出現頻率最高的類別作為當前點的預測類別。

小迪設定K=4，那么在這個電影例子中，把距離按照升序排列，距離綠點電影最近的前4個的電影分別是《后來的我們》、《前任3》、《無問西東》和《紅海行動》，這四部電影的類別統(tǒng)計為愛情片:動作片=3:1，出現頻率最高的類別為愛情片，所以在k=4時，綠點電影的類別為愛情片。這個判別過程就是k-近鄰算法。

K近鄰算法的Python實現

1. 算法實現

1.1構建已經分類好的原始數據集

為了方便驗證，這里使用python的字典dict構建數據集，然后再將其轉化成DataFrame格式。

import pandas as pd

rowdata={'電影名稱':['無問西東','后來的我們','前任3','紅海行動','唐人街探案','戰(zhàn)狼2'],
'打斗鏡頭':[1,5,12,108,112,115],
'接吻鏡頭':[101,89,97,5,9,8],
'電影類型':['愛情片','愛情片','愛情片','動作片','動作片','動作片']}
movie_data= pd.DataFrame(rowdata)
movie_data

2.計算已知類別數據集中的點與當前點之間的距離

new_data = [24,67]
dist = list((((movie_data.iloc[:6,1:3]-new_data)2).sum(1))0.5)
dist

3.將距離升序排列，然后選取距離最小的k個點

dist_l = pd.DataFrame({'dist': dist, 'labels': (movie_data.iloc[:6, 3])})
dr = dist_l.sort_values(by = 'dist')[: 4]
dr

4.確定前k個點所在類別的出現頻率

re = dr.loc[:,'labels'].value_counts()
re

5.選擇頻率最高的類別作為當前點的預測類別

result = []
result.append(re.index[0])
result

2. 封裝函數

完整的流程已經實現了，下面我們需要將這些步驟封裝成函數，方便我們后續(xù)的調用。

import pandas as pd
"""
函數功能：KNN分類器
參數說明：
new_data:需要預測分類的數據集
dataSet:已知分類標簽的數據集（訓練集）
k:k-近鄰算法參數，選擇距離最小的k個點
返回：
result：分類結果
"""

def classify0(inX,dataSet,k):
result = []
dist = list((((dataSet.iloc[:,1:3]-inX)2).sum(1))0.5)
dist_l = pd.DataFrame({'dist':dist,'labels':(dataSet.iloc[:, 3])})
dr = dist_l.sort_values(by = 'dist')[: k]
re = dr.loc[:, 'labels'].value_counts()
result.append(re.index[0])
return result

測試函數運行結果

inX = new_data
dataSet = movie_data
k = 3
classify0(inX,dataSet,k)

這就是我們使用k-近鄰算法構建的一個分類器，根據我們的“經驗”可以看出，分類器給的答案還是比較符合我們的預期的。

算法總結

小迪：k近鄰算法雖然是機器學習算法中最簡單的算法，沒有之一，但是它確實也是蠻厲害呢！

小西：是呀，沒想到這么簡單的算法還有這么厲害的作用呢！那是不是這種算法永遠不會出錯呢？

小迪：那當然不是啦。沒有哪個模型是完美的。分類器并不會得到百分百正確的結果，我們可以使用很多種方法來驗證分類器的準確率。此外，分類器的性能也會受到很多因素的影響，比如k的取值就在很大程度上影響了分類器的預測結果，還有分類器的設置、原始數據集等等。為了測試分類器的效果，我們可以把原始數據集分為兩部分，一部分用來訓練算法（稱為訓練集），一部分用來測試算法的準確率（稱為測試集）。同時，我們不難發(fā)現，k-近鄰算法沒有進行數據的訓練，直接使用未知的數據與已知的數據進行比較，得到結果。因此，可以說，k-近鄰算法不具有顯式的學習過程。

小西：原來如此，今天還是收獲滿滿呢！

總結

1. 優(yōu)點

• 簡單好用，容易理解，精度高，理論成熟，既可以用來做分類也可以用來做回歸

• 可用于數值型數據和離散型數據

• 無數據輸入假定

• 適合對稀有事件進行分類

2. 缺點

• 計算復雜性高；空間復雜性高；

• 計算量太大，所以一般數值很大的時候不用這個，但是單個樣本又不能太少，否則容易發(fā)生誤分。

• 樣本不平衡問題（即有些類別的樣本數量很多，而其它樣本的數量很少）

• 可理解性比較差，無法給出數據的內在含義

K近鄰番外篇——小艾相親記

小迪跟小西有一個好朋友叫小艾。小艾與小迪是同事，在一家公司做數據分析。

小艾一直使用在線約會網站尋找適合自己的約會對象，盡管約會網站會推薦不同的人選，但他并不是每一個都喜歡，經過一番總結，她發(fā)現曾經交往的對象可以分為三類：

• 不喜歡的人

• 魅力一般的人

• 極具魅力得人

小艾收集約會數據已經有了一段時間，他把這些數據存放在文本文件datingTestSet.txt中，其中各字段分別為：

1. 每年飛行?？屠锍?/p>

2. 玩游戲視頻所占時間比

3. 每周消費冰淇淋公升數

1. 準備數據

datingTest = pd.read_table('datingTestSet.txt',header=None)
datingTest.head()

datingTest.shape
http://datingTest.info()

2. 分析數據

小艾使用 Matplotlib 創(chuàng)建散點圖，查看各數據的分布情況。

%matplotlib inline
import matplotlib as mpl
import matplotlib.pyplot as plt

把不同標簽用顏色區(qū)分

Colors = []
for i in range(datingTest.shape[0]):
m = datingTest.iloc[i,-1]
if m=='didntLike':
Colors.append('black')
if m=='smallDoses':
Colors.append('orange')
if m=='largeDoses':
Colors.append('red')

繪制兩兩特征之間的散點圖

plt.rcParams['font.sans-serif']=['Simhei'] #圖中字體設置為黑體
pl=plt.figure(figsize=(12,8))
fig1=pl.add_subplot(221)
plt.scatter(datingTest.iloc[:,1],datingTest.iloc[:,2],marker='.',c=Colors)
plt.xlabel('玩游戲視頻所占時間比')
plt.ylabel('每周消費冰淇淋公升數')

fig2=pl.add_subplot(222)
plt.scatter(datingTest.iloc[:,0],datingTest.iloc[:,1],marker='.',c=Colors)
plt.xlabel('每年飛行?？屠锍?#39;)
plt.ylabel('玩游戲視頻所占時間比')

fig3=pl.add_subplot(223)
plt.scatter(datingTest.iloc[:,0],datingTest.iloc[:,2],marker='.',c=Colors)
plt.xlabel('每年飛行常客里程')
plt.ylabel('每周消費冰淇淋公升數')
plt.show()

3. 數據歸一化

下表是提取的4條樣本數據，小艾想要計算樣本1和樣本2之間的距離，于是使用歐幾里得計算公式：

小艾發(fā)現，上面公式中差值最大的屬性對計算結果的影響最大，也就是說每年飛行?？屠锍虒τ嬎憬Y果的影響遠遠大于其他兩個特征，原因僅僅是因為它的數值比較大，但是在小艾看來這三個特征是同等重要的，所以接下來要進行數值歸一化的處理，使得這三個特征的權重相等。

數據歸一化的處理方法有很多種，比如0-1標準化、Z-score標準化、Sigmoid壓縮法等等，在這里使用最簡單的0-1標準化，公式如下：

函數功能：歸一化
參數說明：
dataSet:原始數據集
返回：0-1標準化之后的數據集
"""

def minmax(dataSet):
minDf = dataSet.min()
maxDf = dataSet.max()
normSet = (dataSet - minDf )/(maxDf - minDf)
return normSet

小艾將數據集帶入函數，進行歸一化處理

datingT = pd.concat([minmax(datingTest.iloc[:, :3]), datingTest.iloc[:,3]], axis=1)
datingT.head()

4. 劃分訓練集和測試集

為了測試分類器的效果，小艾把原始數據集分為訓練集和測試集兩部分，訓練集用來訓練模型，測試集用來驗證模型準確率。

關于訓練集和測試集的切分函數，網上有很多，Scikit Learn官網上也有相應的函數比如modelselection 類中的traintest_split 函數也可以完成訓練集和測試集的切分。

通常只提供已有數據的90%作為訓練樣本來訓練模型，其余10%的數據用來測試模型。這里需要注意的10%的測試數據一定要是隨機選擇出來的，由于小艾提供的數據并沒有按照特定的目的來排序，所以這里可以隨意選擇10%的數據而不影響其隨機性。

"""
函數功能：切分訓練集和測試集
參數說明：
dataSet:原始數據集
rate:訓練集所占比例
返回：切分好的訓練集和測試集
"""

def randSplit(dataSet,rate=0.9):
n = dataSet.shape[0]
m = int(n*rate)
train = dataSet.iloc[:m,:]
test = dataSet.iloc[m:,:]
test.index = range(test.shape[0])
return train,test

train,test = randSplit(datingT)
train
test

5. 分類器針對于約會網站的測試代碼

接下來，小艾開始構建針對于這個約會網站數據的分類器，上面已經將原始數據集進行歸一化處理然后也切分了訓練集和測試集，所以函數的輸入參數就可以是train、test和k(k-近鄰算法的參數，也就是選擇的距離最小的k個點)。

"""
函數功能：k-近鄰算法分類器
參數說明：
train:訓練集
test：測試集
k:k-近鄰參數，即選擇距離最小的k個點
返回：預測好分類的測試集
"""

def datingClass(train,test,k):
n = train.shape[1] - 1
m = test.shape[0]
result = []
for i in range(m):
dist = list((((train.iloc[:, :n] - test.iloc[i, :n]) ** 2).sum(1))**5)
dist_l = pd.DataFrame({'dist': dist, 'labels': (train.iloc[:, n])})
dr = dist_l.sort_values(by = 'dist')[: k]
re = dr.loc[:, 'labels'].value_counts()
result.append(re.index[0])
result = pd.Series(result)
test['predict'] = result
acc = (test.iloc[:,-1]==test.iloc[:,-2]).mean()
print(f'模型預測準確率為{acc}')
return test

最后，測試上述代碼能否正常運行，使用上面生成的測試集和訓練集來導入分類器函數之中，然后執(zhí)行并查看分類結果。

datingClass(train,test,5)

從結果可以看出，小艾的模型準確率還不錯，這是一個不錯的結果了，離找女朋友更近了一步。