目標(biāo)

1、理解KNN算法的核心思想
2、理解KNN算法的實(shí)現(xiàn)
3、掌握KNN算法的應(yīng)用步驟：數(shù)據(jù)處理、建模、運(yùn)算和結(jié)果判定

1. kNN分類(lèi)算法原理

1.1概述

K最近鄰（k-Nearest Neighbor，KNN）分類(lèi)算法是最簡(jiǎn)單的機(jī)器學(xué)習(xí)算法。
KNN算法的指導(dǎo)思想是“近朱者赤，近墨者黑”，由你的鄰居來(lái)推斷出你的類(lèi)別。

本質(zhì)上，KNN算法就是用距離來(lái)衡量樣本之間的相似度

1.2 算法圖示

• 從訓(xùn)練集中找到和新數(shù)據(jù)最接近的k條記錄，然后根據(jù)多數(shù)類(lèi)來(lái)決定新數(shù)據(jù)類(lèi)別。
• 算法涉及3個(gè)主要因素：

1. 訓(xùn)練數(shù)據(jù)集
2. 距離或相似度的計(jì)算衡量

3. k的大小

   
   
   image.png

• 算法描述

1. 已知兩類(lèi)“先驗(yàn)”數(shù)據(jù)，分別是藍(lán)方塊和紅三角，他們分布在一個(gè)二維空間中
2. 有一個(gè)未知類(lèi)別的數(shù)據(jù)（綠點(diǎn)），需要判斷它是屬于“藍(lán)方塊”還是“紅三角”類(lèi)
3. 考察離綠點(diǎn)最近的3個(gè)（或k個(gè)）數(shù)據(jù)點(diǎn)的類(lèi)別，占多數(shù)的類(lèi)別即為綠點(diǎn)判定類(lèi)別

1.3 算法要點(diǎn)

1.3.1 計(jì)算步驟

• 計(jì)算步驟如下：
  1. 算距離：給定測(cè)試對(duì)象，計(jì)算它與訓(xùn)練集中的每個(gè)對(duì)象的距離
  2. 找鄰居：圈定距離最近的k個(gè)訓(xùn)練對(duì)象，作為測(cè)試對(duì)象的近鄰
  3. 做分類(lèi)：根據(jù)這k個(gè)近鄰歸屬的主要類(lèi)別，來(lái)對(duì)測(cè)試對(duì)象分類(lèi)

1.3.2、相似度的衡量

• 距離越近應(yīng)該意味著這兩個(gè)點(diǎn)屬于一個(gè)分類(lèi)的可能性越大。
  但，距離不能代表一切，有些數(shù)據(jù)的相似度衡量并不適合用距離
• 相似度衡量方法：包括歐式距離、夾角余弦等。

（簡(jiǎn)單應(yīng)用中，一般使用歐氏距離，但對(duì)于文本分類(lèi)來(lái)說(shuō)，使用余弦(cosine)來(lái)計(jì)算相似度就比歐式(Euclidean)距離更合適）

1.3.3、類(lèi)別的判定

• 簡(jiǎn)單投票法：少數(shù)服從多數(shù)，近鄰中哪個(gè)類(lèi)別的點(diǎn)最多就分為該類(lèi)。
• 加權(quán)投票法：根據(jù)距離的遠(yuǎn)近，對(duì)近鄰的投票進(jìn)行加權(quán)，距離越近則權(quán)重越大（權(quán)重為距離平方的倒數(shù)）

1.4 算法不足之處

1. 樣本不平衡容易導(dǎo)致結(jié)果錯(cuò)誤

• 如一個(gè)類(lèi)的樣本容量很大，而其他類(lèi)樣本容量很小時(shí)，有可能導(dǎo)致當(dāng)輸入一個(gè)新樣本時(shí)，該樣本的K個(gè)鄰居中大容量類(lèi)的樣本占多數(shù)。
• 改善方法：對(duì)此可以采用權(quán)值的方法（和該樣本距離小的鄰居權(quán)值大）來(lái)改進(jìn)。

2. 計(jì)算量較大

• 因?yàn)閷?duì)每一個(gè)待分類(lèi)的文本都要計(jì)算它到全體已知樣本的距離，才能求得它的K個(gè)最近鄰點(diǎn)。
• 改善方法：事先對(duì)已知樣本點(diǎn)進(jìn)行剪輯，事先去除對(duì)分類(lèi)作用不大的樣本。
  該方法比較適用于樣本容量比較大的類(lèi)域的分類(lèi)，而那些樣本容量較小的類(lèi)域采用這種算法比較容易產(chǎn)生誤分。

代碼示例1 (sklearn)

import numpy as np
from sklearn.neighbors import KNeighborsClassifier
x_train = np.array([[100,100,100],[90,98,97],[90,90,100],[100,90,95],[80,90,70],[100,80,100],
                    [95,95,95],[95,97,80],[90,95,90],[95,95,90],[100,100,95]])
y_train = ['清華','北大','北郵','北大','北郵','北大','清華','北郵','北郵','北郵','清華']
x_test = np.array([[97,96,92]])
clf = KNeighborsClassifier(n_neighbors=2,weights='uniform',algorithm='auto')
clf.fit(x_train,y_train)
pred = clf.predict(x_test)
print(pred)

代碼示例2 (numpy)

import numpy as np
#from sklearn.neighbors import KNeighborsClassifier
import operator
x_train = np.array([[100,100,100],[90,98,97],[90,90,100],[100,90,95],[80,90,70],[100,80,100],
                    [95,95,95],[95,97,80],[90,95,90],[95,95,90],[100,100,95]])
y_train = ['清華','北大','北郵','北大','北郵','北大','清華','北郵','北郵','北郵','清華']
x_test = np.array([[97,96,92]])
def classify0(x_test, x_train, labels, k):#對(duì)每組數(shù)據(jù)進(jìn)行分類(lèi)，inX為用于分類(lèi)的輸入向量
    dataSetSize = x_train.shape[0]
    # 計(jì)算歐氏距離
    diffMat = np.tile(x_test, (dataSetSize, 1)) - x_train
    SQdiffMat = diffMat ** 2
    distances = SQdiffMat.sum(axis=1)
    # 對(duì)索引值進(jìn)行排序排序
    sorted_distances = distances.argsort()
    # 以字典形式存儲(chǔ)數(shù)據(jù)，便于索引
    class_count = {}
    for i in range(k):
        voteLabel = labels[sorted_distances[i]]
        class_count[voteLabel] = class_count.get(voteLabel,0) + 1
        # 將classCount字典分解為元祖列表，排序k個(gè)距離值
        sortedClassCount = sorted(class_count.items(), key=operator.itemgetter(1),
                                  reverse=True)
        return sortedClassCount[0][0]  # 返回發(fā)生頻率最高的元素標(biāo)簽
classifier = classify0(x_test,x_train,y_train,k=2)
print(classifier)

兩種計(jì)算結(jié)果所得分類(lèi)均為-北郵