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

準(zhǔn)備訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)；

確定參數(shù) k；

計(jì)算測試數(shù)據(jù)與各個(gè)訓(xùn)練數(shù)據(jù)之間的距離，距離的遞增關(guān)系進(jìn)行排序；

選取距離最小的 k 個(gè)點(diǎn)；

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

返回前 k 個(gè)點(diǎn)中出現(xiàn)頻率最高的類別作為測試數(shù)據(jù)的預(yù)測分類。

# python 3.7.2

from numpy import *
import operator

def kNNClassify(testData, trainData, labels, k):
    dataSize = trainData.shape[0]  # 測試數(shù)據(jù)矩陣的行數(shù)，4
    diffMat = tile(testData, (dataSize, 1)) - trainData  # numpy中的tile用于重復(fù)矩陣中的元素，構(gòu)造和dataSize規(guī)格一樣
    sqDiffMat = diffMat ** 2
    sqDistances = sqDiffMat.sum(axis=1)  # 計(jì)算矩陣的行和
    distances = sqDistances ** 0.5  # 采用歐式距離計(jì)算
    sortedDisindexes = distances.argsort()  # 返回排序后對(duì)應(yīng)的索引數(shù)據(jù)
    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)  # 根據(jù)第2維進(jìn)行排序
    return sortedClassCount[0][0]
    

假設(shè)訓(xùn)練數(shù)據(jù)為：

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

測試數(shù)據(jù)為：

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

小明在某約會(huì)網(wǎng)站上瀏覽妹子，對(duì)看到的每一個(gè)妹子進(jìn)行評(píng)價(jià)：largeDoses,smallDoses,didntLike，評(píng)價(jià)的依據(jù)有3條：

每年旅行里程數(shù)

玩游戲占一天時(shí)間比重

每周吃的甜品數(shù)量

收集了1000條相關(guān)數(shù)據(jù)，存儲(chǔ)在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 讀取文本文件數(shù)據(jù)，構(gòu)造矩陣

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))  # 數(shù)據(jù)矩陣
    classLabels = []  # 標(biāo)簽數(shù)組
    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 數(shù)據(jù)歸一化處理

各個(gè)維度的數(shù)值差異較大，直接使用會(huì)嚴(yán)重影響分類效果，因此需要進(jìn)行歸一化處理:
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 

最后調(diào)用kNNClassify函數(shù)進(jìn)行測試。此處省略

簡單，易于理解，易于實(shí)現(xiàn)；

適合數(shù)值型屬性分類；

適合于多分類問題(multi-modal，對(duì)象具有多個(gè)類別標(biāo)簽)， kNN比SVM的表現(xiàn)要好。

當(dāng)樣本不平衡時(shí)，如一個(gè)類的樣本容量很大，而其他類樣本容量很小時(shí)，有可能導(dǎo)致當(dāng)輸入一個(gè)新樣本時(shí)，該樣本的k個(gè)鄰居中大容量類的樣本占多數(shù)，分類出現(xiàn)偏差。

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

改進(jìn)策略主要分成了分類效率和分類效果兩個(gè)方向：

分類效率：事先對(duì)樣本屬性進(jìn)行約簡，刪除對(duì)分類結(jié)果影響較小的屬性。該算法比較適用于樣本容量比較大的類域的自動(dòng)分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。

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

《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》