K-鄰近（KNN）算法

• 假設綠色和藍色是兩個不同的類
• 如下圖，紅色圓要被決定賦予哪個類，是綠色還是藍色？如果K=3，由于綠色所占比例為2/3，紅色圓将被賦予綠色那個類，如果K=10，由于藍色比例為7/10，是以紅色被賦予藍色類。

  

• 由此可見KNN算法很大程度上取決于K的選擇。
• 實驗流程圖：

  

• 簡單KNN算法實作如下：

main.py

#coding:utf-8

import sys
import KNN
from numpy import *

dataSet,labels = KNN.createDataSet()
input = array([0.0, 0.0])
K = 3
output = KNN.classify(input,dataSet,labels,K)
print("測試資料為:",input,"分類結果為：",output)
           

KNN.py

# coding:utf-8

from numpy import *
import operator

# 給出訓練資料以及對應的類别
def createDataSet():
    group = array([[0.5, 0.5], [-0.5, 0.5], [-0.2, -0.7], [0.3, 3.5], [1.3, 1.7], [-0.5, 1.8], [-1, 1], [-1.8, -0.2], [-1, -1.8], [0.2, -1.8], [1, -1]])
    labels = ['Blue', 'Green', 'Green', 'Blue', 'Blue', 'Blue', 'Blue', 'Blue', 'Green', 'Blue']
    return group, labels


# 通過KNN進行分類
def classify(input, dataSet, label, k):
    dataSize = dataSet.shape[0]
    # 計算歐式距離
    diff = tile(input, (dataSize, 1)) - dataSet
    sqdiff = diff ** 2
    squareDist = sum(sqdiff, axis=1)  ###行向量分别相加，進而得到新的一個行向量
    dist = squareDist ** 0.5

    # 對距離進行排序
    sortedDistIndex = argsort(dist)  ##argsort()根據元素的值從大到小對元素進行排序，傳回下标

    classCount = {}
    for i in range(k):
        voteLabel = label[sortedDistIndex[i]]
        # 對選取的K個樣本所屬的類别個數進行統計
        classCount[voteLabel] = classCount.get(voteLabel, 0) + 1
    # 選取出現的類别次數最多的類别
    maxCount = 0
    for key, value in classCount.items():
        if value > maxCount:
            maxCount = value
            classes = key

    return classes
           

測試結果

測試資料為: [0. 0.] 分類結果為： Green