一、k近鄰演算法的概述

k-近鄰演算法（k-Nearest Neighbour algorithm），又稱為KNN演算法，KNN的作業原理：給定一個已知標簽類別的訓練資料集，輸入沒有標簽的新資料后，在訓練資料集中找到與新資料最鄰近的k個實體，如果這k個實體的多數屬于某個類別，那么新資料就屬于這個類別，可以簡單理解為：由那些離X最近的k個點來投票決定X歸為哪一類，

如上圖所示
當k的范圍改變，綠色圓點會有不一樣的類別
當k=3時（實線范圍），綠色圓點屬于紅色三角這種類別；
當k=5時（虛線范圍），綠色圓點屬于藍色方塊這種類別，

那如何判斷一部電影屬于愛情片還是動作片呢？

我們將表中已有資料作為樣本資料，打斗鏡頭和接吻鏡頭作為資料特征，如何用knn演算法給出新電影的電影型別呢？
將資料放在坐標圖中可以發現，新電影更加偏向于愛情片，那么從k近鄰角度來說，它主要通過未知點和已知資料集中的資料點之間的距離進行判斷得出最終結果，
在二維平面角度距離公式：
那么在多維空間里，歐式距離公式可以幫我們很好地解決：
k近鄰演算法的主要步驟：
(1) 計算已知類別資料集中的點與當前點之間的距離；
(2) 按照距離遞增次序排序；
(3) 選取與當前點距離最小的k個點；
(4) 確定前k個點所在類別的出現頻率；
(5) 回傳前k個點出現頻率最高的類別作為當前點的預測類別，
當k=4時，那么在這個電影例子中，把距離按照升序排列，距離綠點電影最近的前4個的電影分別是《后來的我們》、《前任3》、《無問西東》和《紅海行動》，這四部電影的類別統計為愛情片:動作片=3:1，出現頻率最高的類別為愛情片，所以在k=4時，綠點電影的類別為愛情片，這個判別程序就是k-近鄰演算法，
然而k的選取得不同也得到不一樣的結果，那么如何確定k的值呢？
李航書上講到，我們一般選取一個較小的數值，通常采取交叉驗證法來選取最優的k值，（也就是說，選取k值很重要的關鍵是實驗調參，類似于神經網路選取多少層這種，通過調整超引數來得到一個較好的結果）

二、用python實作k近鄰演算法

1.演算法實作

import pandas as pd

#匯入資料，將其轉換成dataframe格式
rowdata={'電影名稱':['無問西東','后來的我們','前任3','紅海行動','唐人街探案','戰狼2'],
'打斗鏡頭':[1,5,12,108,112,115],
'接吻鏡頭':[101,89,97,5,9,8],
'電影型別':['愛情片','愛情片','愛情片','動作片','動作片','動作片']}
movie_data= pd.DataFrame(rowdata)

#根據上面距離公式,求出距離
new_data = [24,67]
dist = list((((movie_data.iloc[:6,1:3]-new_data)**2).sum(1))**0.5)

#首先對資料進行切分，然后升序排列求出前四
dist_l = pd.DataFrame({'dist': dist, 'labels': (movie_data.iloc[:6, 3])})
dr = dist_l.sort_values(by = 'dist')[: 4]

#統計前k個出現的類別頻率
re = dr.loc[:,'labels'].value_counts()

#選擇頻率最高的輸出
result = []
result.append(re.index[0])
print(result)

2.封裝函式

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
print(classify0(inX,dataSet,k))

三、k近鄰演算法案例應用

import matplotlib as mpl
import matplotlib.pyplot as plt

datingTest=pd.read_table('datingTestSet.txt',header=None) #匯入資料
#把不同標簽用顏色區分
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('每年飛行公里數')
plt.ylabel('消費冰淇淋公斤數')

fig3=pl.add_subplot(223)
plt.scatter(datingTest.iloc[:,0],datingTest.iloc[:,2],marker='.',c=Colors)
plt.xlabel('每年飛行公里數')
plt.ylabel('玩游戲所占時間比')
plt.show()
#資料歸一化'''
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)  #對資料進行切分結合，axis=1保留縱軸
#資料進行切分
"""
將資料切分為訓練集和測驗集
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])  #test資料進行排序
    return train,test
train,test=randSplit(datingT)
#分類器
def datingclassify(train,test,k):
    n=train.shape[1]-1   #列數
    m=train.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()    #確認準確率mean取巧的程序
    print(f'模型預測準確率為{acc}')
    return test

print(datingclassify(train,test,5))

在距離公式中差值最大的屬性對計算結果的影響最大，原因僅僅是因為它的數值比較大，所以我們要進行數值歸一化的處理，使得這三個特征的權重相等，
資料歸一化的處理方法有很多種，比如0-1標準化、Z-score標準化、Sigmoid壓縮法等等，在這里我們使用最簡單
的0-1標準化，公式如下：

四、總結

1.k近鄰演算法核心思想是，即是給定一個訓練資料集，對新的輸入實體，在訓練資料集中找到與該實體最鄰近的K個實體，這K個實體的多數屬于某個類，就把該輸入實體分類到這個類中，

2.與該實體最近鄰的k個實體，這個最近鄰的定義是通過不同距離函式來定義，我們最常用的是歐式距離，

3.為了保證每個特征同等重要性，我們這里對每個特征進行歸一化，

4.k值的選取，既不能太大，也不能太小，何值為最好，需要實驗調整引數確定！

希望對大家有所幫助！

參考：
機器學習（周志華），機器學習實戰，李航《統計學習方法》,橘安醬的機器學習