k近鄰(k-Nearest Neighbor，kNN)算法是經典的帶監督的分類算法，核心思想是如果一個樣本在特征空間中的k個最相鄰的樣本中的大多數屬于某一個類別，則針對該樣本的劃分結果也屬于這個類別。

準備訓練數據和測試數據；

確定參數 k；

計算測試數據與各個訓練數據之間的距離，距離的遞增關系進行排序；

選取距離最小的 k 個點；

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

返回前 k 個點中出現頻率最高的類別作為測試數據的預測分類。

# python 3.7.2

from numpy import *
import operator

def kNNClassify(testData, trainData, labels, k):
    dataSize = trainData.shape[0]  # 測試數據矩陣的行數，4
    diffMat = tile(testData, (dataSize, 1)) - trainData  # numpy中的tile用于重復矩陣中的元素，構造和dataSize規格一樣
    sqDiffMat = diffMat ** 2
    sqDistances = sqDiffMat.sum(axis=1)  # 計算矩陣的行和
    distances = sqDistances ** 0.5  # 采用歐式距離計算
    sortedDisindexes = distances.argsort()  # 返回排序后對應的索引數據
    classCount = {}
    for i in range(k):
        voteLabel = labels[sortedDisindexes[i]]
        classCount[voteLabel] = classCount.get(voteLabel, 0) + 1
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)  # 根據第2維進行排序
    return sortedClassCount[0][0]
    

假設訓練數據為：

trainData= [[1, 1.1], [1, 1], [0, 0], [0, 0.1]]
labels = ["A", "A", "B", "B"]

測試數據為：

testData = [[1.1 , 1], [0.1, 0]]

小明在某約會網站上瀏覽妹子，對看到的每一個妹子進行評價：largeDoses,smallDoses,didntLike，評價的依據有3條：

每年旅行里程數

玩游戲占一天時間比重

每周吃的甜品數量

收集了1000條相關數據，存儲在datingTestSet.txt文件中

40920    8.326976    0.953952    largeDoses
14488    7.153469    1.673904    smallDoses
26052    1.441871    0.805124    didntLike
75136    13.147394    0.428964    didntLike
38344    1.669788    0.134296    didntLike
72993    10.141740    1.032955    didntLike
35948    6.830792    1.213192    largeDoses
42666    13.276369    0.543880    largeDoses
67497    8.631577    0.749278    didntLike
35483    12.273169    1.508053    largeDoses
50242    3.723498    0.831917    didntLike
63275    8.385879    1.669485    didntLike
5569    4.875435    0.728658    smallDoses
51052    4.680098    0.625224    didntLike
...

2.2.1 讀取文本文件數據，構造矩陣

def file2Matrix(filename):
    love_dictionary = {"largeDoses": 1, "smallDoses": 0, "didntLike": -1}
    fr = open("datingTestSet.txt")
    arrayOfLines = fr.readlines()
    numOfLines = len(arrayOfLines)
    dataMatrix = zeros((numOfLines, 3))  # 數據矩陣
    classLabels = []  # 標簽數組
    index = 0
    for line in arrayOfLines:
        line = line.strip()
        listFromLine = line.split("	")
        dataMatrix [index, :] = listFromLine[0:3]
        classLabels.append(love_dictionary.get(listFromLine[-1]))
        index += 1
    return returnMat, classLabels

2.2.2 數據歸一化處理

各個維度的數值差異較大，直接使用會嚴重影響分類效果，因此需要進行歸一化處理:
newValue = (oldVlue -min) / (max - min)

def autoNorm(dataSet):
    minVals = dataSet.min(0)  # min(0)返回列的最小值， min(1)返回行的最小值
    maxVals = dataSet.max(0)  # max(0)返回列的最大值， max(1)返回行的最大值
    ranges = maxVals - minVals
    normDataSet = zeros(shape(dataSet))
    m = normDataSet.shape[0]
    normDataSet = dataSet - tile(minVals, (m, 1))
    normDataSet = normDataSet / tile(ranges, (m, 1))
    return normDataSet 

最后調用kNNClassify函數進行測試。此處省略

簡單，易于理解，易于實現；

適合數值型屬性分類；

適合于多分類問題(multi-modal，對象具有多個類別標簽)， kNN比SVM的表現要好。

當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的k個鄰居中大容量類的樣本占多數，分類出現偏差。

計算量較大，每一個待分類的文本都要計算它到全體已知樣本的距離。

改進策略主要分成了分類效率和分類效果兩個方向：

分類效率：事先對樣本屬性進行約簡，刪除對分類結果影響較小的屬性。該算法比較適用于樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域采用這種算法比較容易產生誤分。

分類效果：① 采用權值的方法（和該樣本距離小的鄰居權值大）來改進，如可調整權重的k最近鄰居法WAkNN (weighted adjusted k nearest neighbor)；② 依照訓練集合中各種分類的文件數量，選取不同數目的最近鄰居，來參與分類；③ 類中心算法，求出各個樣本的類中心到測試數據的距離，劃分到最近的類。

《機器學習實戰》