分類算法——K-鄰近

   K-鄰近分類方法通過計(jì)算待分類目標(biāo)和訓(xùn)練樣例之間的距離，選取與待分類目標(biāo)距離最近的K個訓(xùn)練樣例，根據(jù)K個選取樣例中占多數(shù)的類別來確定待分類樣例。距離類型有很多，大致有歐式距離，曼哈頓距離，切比雪夫距離，閩科夫斯基距離，標(biāo)準(zhǔn)化歐式距離，馬氏距離，夾角余弦，漢明距離，相關(guān)系數(shù)，信息熵等。 

  KNN算法的具體步驟：

1、計(jì)算待分類目標(biāo)與每個訓(xùn)練樣例之間的距離dist；

2、對dist進(jìn)行排序，選擇前K個訓(xùn)練樣例作為K-最鄰近樣例；

3、統(tǒng)計(jì)K個訓(xùn)練樣例中每個類別出現(xiàn)的頻次；

4、選擇出現(xiàn)頻次最大的類別作為待分類目標(biāo)的類別。

  依據(jù)上述流程，給出實(shí)現(xiàn)代碼：

from numpy import *
import operator
def knn(x,transet,labels,k,type = 0):
    '''
    k-近鄰算法
    :param x:待分類特征
    :param transet: 已知特征
    :param labels: 特征標(biāo)簽
    :param k:
    :param type:
        距離類型：0：歐式，1：曼哈頓，2：切比雪夫，3：閩科夫斯基，4：標(biāo)準(zhǔn)化歐式，5：馬氏，6：夾角余弦
                  7：漢明距離，8：杰卡德，9：相關(guān)系數(shù)，11:信息熵
    :return:
    '''
    distances = zeros_like(labels)
    if type == 0:
        tranSize = shape(transet)
        diffMat = tile(x,(tranSize[0],1)) - transet
        distances = ((diffMat**2).sum(axis=1))**0.5
    #TODO：根據(jù)不同的類型計(jì)算距離
    sortedIndex = distances.argsort()
    classCount = {}
    for i in labels[sortedIndex[:k]]:
        classCount[i] = classCount.get(i,0) + 1
    sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
    return sortedClassCount;

  KNN算法的優(yōu)點(diǎn)：理論簡單，實(shí)現(xiàn)簡單。

  KNN算法的缺點(diǎn)：1）對K值的選取依賴大，不同的K值選取可能產(chǎn)生不同的結(jié)果?？梢酝ㄟ^實(shí)驗(yàn)選取分類誤差最小的K值。2）由于需要計(jì)算特征的距離，所以需要特征進(jìn)行量化和標(biāo)準(zhǔn)化。