摘要：電影分析近鄰算法周末，小迪與女朋友小西走出電影院，回味著剛剛看過(guò)的電影。近鄰分類電影類型小迪回到家，打開電腦，想實(shí)現(xiàn)一個(gè)分類電影的案例。分類器并不會(huì)得到百分百正確的結(jié)果，我們可以使用很多種方法來(lái)驗(yàn)證分類器的準(zhǔn)確率。

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

小迪：剛剛的電影很精彩，打斗場(chǎng)景非常真實(shí)，又是一部?jī)?yōu)秀的動(dòng)作片！

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

小迪：是動(dòng)作片好不好？不信的話我們用K近鄰來(lái)分類！

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

小迪：我們以接吻鏡頭與打斗鏡頭作為兩種電影的特征，只要知道一部電影的接吻鏡頭與打斗鏡頭的個(gè)數(shù)，利用現(xiàn)有的帶標(biāo)簽數(shù)據(jù)集便可以對(duì)未知類型的電影進(jìn)行類型預(yù)測(cè)。

小西：不是很明白，可以講簡(jiǎn)單點(diǎn)嗎？

小迪：我們可以這樣理解，假設(shè)有一個(gè)未知的x，我們盡量讓特征相近的的點(diǎn)靠近，這樣想要知道x是什么性質(zhì)的，我們可以觀察它鄰近的k個(gè)點(diǎn)，這些點(diǎn)多數(shù)是什么性質(zhì)的，那么x的性質(zhì)也就是可以預(yù)測(cè)出來(lái)了。

小西：哦哦，明白了。有點(diǎn)像那句俗語(yǔ)——物以類聚人以群分呢！

小迪：是啊，是有這么個(gè)意思！我們回去用python實(shí)現(xiàn)一下這個(gè)算法吧。

小西：好的，走！

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

如上圖中有紅色三角和藍(lán)色方塊兩種類別，現(xiàn)在需要判斷綠色圓點(diǎn)屬于哪種類別

當(dāng)k=3時(shí)，綠色圓點(diǎn)屬于紅色三角這種類別；

當(dāng)k=5時(shí)，綠色圓點(diǎn)屬于藍(lán)色方塊這種類別。

小迪回到家，打開電腦，想實(shí)現(xiàn)一個(gè)分類電影的案例。于是他找了幾部前段時(shí)間比較熱門的電影，然后根據(jù)接吻鏡頭與動(dòng)作鏡頭打上標(biāo)簽，用k-近鄰算法分類一個(gè)電影是愛情片還是動(dòng)作片（打斗鏡頭和接吻鏡頭數(shù)量為虛構(gòu)）。

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

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

從散點(diǎn)圖中大致推斷，這個(gè)未知電影有可能是愛情片，因?yàn)榭雌饋?lái)距離已知的三個(gè)愛情片更近一點(diǎn)。而在k-近鄰算法中是利用距離進(jìn)行判斷的。這個(gè)電影分類例子中有兩個(gè)特征，也就是在二維平面中計(jì)算兩點(diǎn)之間的距離，這很容易可以聯(lián)想到中學(xué)時(shí)代學(xué)過(guò)的距離公式：

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

通過(guò)計(jì)算可以得到訓(xùn)練集中所有電影與未知電影的距離，如下表所示：

通過(guò)上面表中的計(jì)算結(jié)果，小迪知道綠點(diǎn)標(biāo)記的電影到愛情片《后來(lái)的我們》距離最近，為29.1。如果僅僅根據(jù)這個(gè)結(jié)果，判定綠點(diǎn)電影的類別為愛情片，是不是這樣呢？答案是不是，這個(gè)算法叫做最近鄰算法，只看距離最近的一個(gè)點(diǎn)，而不是k個(gè)點(diǎn)，所以不是k-近鄰算法。k-近鄰算法步驟如下：

(1) 計(jì)算已知類別數(shù)據(jù)集中的點(diǎn)與當(dāng)前點(diǎn)之間的距離；
(2) 按照距離遞增次序排序；
(3) 選取與當(dāng)前點(diǎn)距離最小的k個(gè)點(diǎn)；
(4) 確定前k個(gè)點(diǎn)所在類別的出現(xiàn)頻率；
(5) 返回前k個(gè)點(diǎn)出現(xiàn)頻率最高的類別作為當(dāng)前點(diǎn)的預(yù)測(cè)類別。

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

1.1構(gòu)建已經(jīng)分類好的原始數(shù)據(jù)集

為了方便驗(yàn)證，這里使用python的字典dict構(gòu)建數(shù)據(jù)集，然后再將其轉(zhuǎn)化成DataFrame格式。

import pandas as pd

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

2.計(jì)算已知類別數(shù)據(jù)集中的點(diǎn)與當(dāng)前點(diǎn)之間的距離

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

3.將距離升序排列，然后選取距離最小的k個(gè)點(diǎn)

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

4.確定前k個(gè)點(diǎn)所在類別的出現(xiàn)頻率

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

5.選擇頻率最高的類別作為當(dāng)前點(diǎn)的預(yù)測(cè)類別

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

完整的流程已經(jīng)實(shí)現(xiàn)了，下面我們需要將這些步驟封裝成函數(shù)，方便我們后續(xù)的調(diào)用。

import pandas as pd
"""
函數(shù)功能：KNN分類器
參數(shù)說(shuō)明：
new_data:需要預(yù)測(cè)分類的數(shù)據(jù)集
dataSet:已知分類標(biāo)簽的數(shù)據(jù)集（訓(xùn)練集）
k:k-近鄰算法參數(shù)，選擇距離最小的k個(gè)點(diǎn)
返回：
result：分類結(jié)果
"""

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

測(cè)試函數(shù)運(yùn)行結(jié)果

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

這就是我們使用k-近鄰算法構(gòu)建的一個(gè)分類器，根據(jù)我們的“經(jīng)驗(yàn)”可以看出，分類器給的答案還是比較符合我們的預(yù)期的。

小迪：k近鄰算法雖然是機(jī)器學(xué)習(xí)算法中最簡(jiǎn)單的算法，沒有之一，但是它確實(shí)也是蠻厲害呢！

小西：是呀，沒想到這么簡(jiǎn)單的算法還有這么厲害的作用呢！那是不是這種算法永遠(yuǎn)不會(huì)出錯(cuò)呢？

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

小西：原來(lái)如此，今天還是收獲滿滿呢！

簡(jiǎn)單好用，容易理解，精度高，理論成熟，既可以用來(lái)做分類也可以用來(lái)做回歸

可用于數(shù)值型數(shù)據(jù)和離散型數(shù)據(jù)

無(wú)數(shù)據(jù)輸入假定

適合對(duì)稀有事件進(jìn)行分類

計(jì)算復(fù)雜性高；空間復(fù)雜性高；

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

樣本不平衡問(wèn)題（即有些類別的樣本數(shù)量很多，而其它樣本的數(shù)量很少）

可理解性比較差，無(wú)法給出數(shù)據(jù)的內(nèi)在含義

小迪跟小西有一個(gè)好朋友叫小艾。小艾與小迪是同事，在一家公司做數(shù)據(jù)分析。

小艾一直使用在線約會(huì)網(wǎng)站尋找適合自己的約會(huì)對(duì)象，盡管約會(huì)網(wǎng)站會(huì)推薦不同的人選，但他并不是每一個(gè)都喜歡，經(jīng)過(guò)一番總結(jié)，她發(fā)現(xiàn)曾經(jīng)交往的對(duì)象可以分為三類：

不喜歡的人

魅力一般的人

極具魅力得人

小艾收集約會(huì)數(shù)據(jù)已經(jīng)有了一段時(shí)間，他把這些數(shù)據(jù)存放在文本文件datingTestSet.txt中，其中各字段分別為：

每年飛行常客里程

玩游戲視頻所占時(shí)間比

每周消費(fèi)冰淇淋公升數(shù)

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

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

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

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

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"] #圖中字體設(shè)置為黑體
pl=plt.figure(figsize=(12,8))
fig1=pl.add_subplot(221)
plt.scatter(datingTest.iloc[:,1],datingTest.iloc[:,2],marker=".",c=Colors)
plt.xlabel("玩游戲視頻所占時(shí)間比")
plt.ylabel("每周消費(fèi)冰淇淋公升數(shù)")

fig2=pl.add_subplot(222)
plt.scatter(datingTest.iloc[:,0],datingTest.iloc[:,1],marker=".",c=Colors)
plt.xlabel("每年飛行常客里程")
plt.ylabel("玩游戲視頻所占時(shí)間比")

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

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

小艾發(fā)現(xiàn)，上面公式中差值最大的屬性對(duì)計(jì)算結(jié)果的影響最大，也就是說(shuō)每年飛行常客里程對(duì)計(jì)算結(jié)果的影響遠(yuǎn)遠(yuǎn)大于其他兩個(gè)特征，原因僅僅是因?yàn)樗臄?shù)值比較大，但是在小艾看來(lái)這三個(gè)特征是同等重要的，所以接下來(lái)要進(jìn)行數(shù)值歸一化的處理，使得這三個(gè)特征的權(quán)重相等。

數(shù)據(jù)歸一化的處理方法有很多種，比如0-1標(biāo)準(zhǔn)化、Z-score標(biāo)準(zhǔn)化、Sigmoid壓縮法等等，在這里使用最簡(jiǎn)單的0-1標(biāo)準(zhǔn)化，公式如下：

函數(shù)功能：歸一化
參數(shù)說(shuō)明：
dataSet:原始數(shù)據(jù)集
返回：0-1標(biāo)準(zhǔn)化之后的數(shù)據(jù)集
"""

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

小艾將數(shù)據(jù)集帶入函數(shù)，進(jìn)行歸一化處理

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

為了測(cè)試分類器的效果，小艾把原始數(shù)據(jù)集分為訓(xùn)練集和測(cè)試集兩部分，訓(xùn)練集用來(lái)訓(xùn)練模型，測(cè)試集用來(lái)驗(yàn)證模型準(zhǔn)確率。

關(guān)于訓(xùn)練集和測(cè)試集的切分函數(shù)，網(wǎng)上有很多，Scikit Learn官網(wǎng)上也有相應(yīng)的函數(shù)比如modelselection 類中的traintest_split 函數(shù)也可以完成訓(xùn)練集和測(cè)試集的切分。

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

"""
函數(shù)功能：切分訓(xùn)練集和測(cè)試集
參數(shù)說(shuō)明：
dataSet:原始數(shù)據(jù)集
rate:訓(xùn)練集所占比例
返回：切分好的訓(xùn)練集和測(cè)試集
"""

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

接下來(lái)，小艾開始構(gòu)建針對(duì)于這個(gè)約會(huì)網(wǎng)站數(shù)據(jù)的分類器，上面已經(jīng)將原始數(shù)據(jù)集進(jìn)行歸一化處理然后也切分了訓(xùn)練集和測(cè)試集，所以函數(shù)的輸入?yún)?shù)就可以是train、test和k(k-近鄰算法的參數(shù)，也就是選擇的距離最小的k個(gè)點(diǎn))。

"""
函數(shù)功能：k-近鄰算法分類器
參數(shù)說(shuō)明：
train:訓(xùn)練集
test：測(cè)試集
k:k-近鄰參數(shù)，即選擇距離最小的k個(gè)點(diǎn)
返回：預(yù)測(cè)好分類的測(cè)試集
"""

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"模型預(yù)測(cè)準(zhǔn)確率為{acc}")
return test

最后，測(cè)試上述代碼能否正常運(yùn)行，使用上面生成的測(cè)試集和訓(xùn)練集來(lái)導(dǎo)入分類器函數(shù)之中，然后執(zhí)行并查看分類結(jié)果。

datingClass(train,test,5)

從結(jié)果可以看出，小艾的模型準(zhǔn)確率還不錯(cuò)，這是一個(gè)不錯(cuò)的結(jié)果了，離找女朋友更近了一步。