k-近鄰算法

原理

• k-近鄰算法是一種簡單的分類算法；
• 通過計算測試點(diǎn)與數(shù)據(jù)集點(diǎn)的距離，根據(jù)距離最小的前k個點(diǎn)的類別，來判斷測試點(diǎn)的類別。該判斷有些類似生活中的選舉投票。

參考維基百科上kNN詞條的圖

實(shí)現(xiàn)步驟（摘自書本 ）

1. 計算已知類別的數(shù)據(jù)點(diǎn)與測試點(diǎn)之間的距離；
2. 按照距離遞增排序；
3. 選取與當(dāng)前距離最小的k個點(diǎn)；
4. 確定前k個點(diǎn)所在類別的出現(xiàn)頻率；
5. 返回頻率最高的類別作為當(dāng)前點(diǎn)的類別。

k近鄰算法的實(shí)現(xiàn)(python)

def kNN(testSet, dataSet, labels, k):
    # 計算歐拉距離
    dataSetSize = dataSet.shape[0]
    diffMat = tile(testSet, (dataSetSize,1)) - dataSet
    sqDiffMat = diffMat**2
    sqDistances = sqDiffMat.sum(axis = 1)
    distances = sqDistances**0.5
    sortedDistIndicies = distances.argsort()

    # 查找最近K個點(diǎn)的類別
    classCount = {}
    for i in range(k):
        votelabel = labels[sortedDistIndicies[i]]
        classCount [votelabel] = classCount.get(votelabel,0) + 1
    sortedClassCount = sorted(classCount.iteritems(),\
                       key = operator.itemgetter(1), reverse = True)
    # 返回應(yīng)屬類別
    return sortedClassCount[0][0]

• 需要說明的地方:
  argsort()的返回值為距離排序后的大小序號，比如:

distances = np.array([1.2, 0.5, 4.2, 3.7])
print np.argsort(distances) # [1 0 3 2]

• 在查找最近k個點(diǎn)的類別過程中，累計每個鄰近點(diǎn)的類別出現(xiàn)的次數(shù)，返回頻率最高的類別作為當(dāng)前點(diǎn)的類別
• K的取值不一樣，導(dǎo)致的結(jié)果也將不太一樣

實(shí)例

測試集來自

https://archive.ics.uci.edu/ml/datasets/Breast+Cancer+Wisconsin+%28Original%29

樣例：
1000025,5,1,1,1,2,1,3,1,1,2
1002945,5,4,4,5,7,10,3,2,1,2

特征含義:

除了id，其余9維特征可以作為我們的特征向量，而最后的預(yù)測結(jié)果為: 2（良性），4（惡性）

由于元數(shù)據(jù)含有缺失值，如:（1057013,8,4,5,1,2,?,7,3,1,4 ）
可以考慮將這部分樣例刪去

實(shí)例代碼

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from numpy import *
import operator
import pandas as pd
import random

def getMat():
    fr = open('breast-cancer-wisconsin.data')
    lines = fr.readlines()
    raw_lines = lines

    # 刪除含有缺失值的樣本
    for line in lines:
        if line.find('?') != -1:
            raw_lines.remove(line)

    numberOfline = len(raw_lines)
    returnMat = zeros((numberOfline, 10))
    index = 0
    for line in raw_lines:
        line = line.strip().split(',')
        line1 = [int(x) for x in line]
        returnMat[index:] = line1[1:]
        index += 1
    return returnMat

def kNN(testSet, dataSet, labels, k):
    # 計算歐拉距離
    dataSetSize = dataSet.shape[0]
    diffMat = tile(testSet, (dataSetSize,1)) - dataSet
    sqDiffMat = diffMat**2
    sqDistances = sqDiffMat.sum(axis = 1)
    distances = sqDistances**0.5
    sortedDistIndicies = distances.argsort()

    # 查找最近K個點(diǎn)的類別
    classCount = {}
    for i in range(k):
        votelabel = labels[sortedDistIndicies[i]]
        classCount [votelabel] = classCount.get(votelabel,0) + 1
    sortedClassCount = sorted(classCount.iteritems(),\
                       key = operator.itemgetter(1), reverse = True)
    # 返回應(yīng)屬類別
    return sortedClassCount[0][0]

if __name__ == '__main__':
    dataMat = getMat()
    ratio = 0.2 # 樣本中20%的數(shù)據(jù)用于測試
    numberTest = int(0.2 * len(dataMat))
    random.shuffle(dataMat) # 將樣本隨機(jī)化

    dataTrain = dataMat[numberTest:len(dataMat), 0:-1]
    dataTrainLabel = dataMat[numberTest:len(dataMat), -1]
    dataTest = dataMat[0:numberTest, 0:-1]
    dataTestLabel = dataMat[0:numberTest, -1]
    errorNum = 0
    for i in range(numberTest):
        testResult = kNN(dataTest[i,:], dataTrain, dataTrainLabel, 7)
        print "came back: %d, the true answer is: %d" % (testResult, dataTestLabel[i])
        if (testResult != dataTestLabel[i]):
            errorNum += 1
    print "error rate is: %f" % (errorNum/float(numberTest))
    print errorNum, numberTest

運(yùn)行結(jié)果如下：

結(jié)果分析

可以看出kNN算法準(zhǔn)確性比較高
但是計算量大，需要計算大量的點(diǎn)距離，當(dāng)樣本特征較多時（1000+），運(yùn)行效率較低，因此不太適合大數(shù)據(jù)運(yùn)算

參考：

1. https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm
2. http://blog.topspeedsnail.com/archives/10287