分類算法——K-鄰近

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

  KNN算法的具體步驟：

1、計算待分類目標與每個訓練樣例之間的距離dist；

2、對dist進行排序，選擇前K個訓練樣例作為K-最鄰近樣例；

3、統計K個訓練樣例中每個類別出現的頻次；

4、選擇出現頻次最大的類別作為待分類目標的類別。

  依據上述流程，給出實現代碼：

from numpy import *
import operator
def knn(x,transet,labels,k,type = 0):
    '''
    k-近鄰算法
    :param x:待分類特征
    :param transet: 已知特征
    :param labels: 特征標簽
    :param k:
    :param type:
        距離類型：0：歐式，1：曼哈頓，2：切比雪夫，3：閩科夫斯基，4：標準化歐式，5：馬氏，6：夾角余弦
                  7：漢明距離，8：杰卡德，9：相關系數，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：根據不同的類型計算距離
    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算法的優點：理論簡單，實現簡單。

  KNN算法的缺點：1）對K值的選取依賴大，不同的K值選取可能產生不同的結果。可以通過實驗選取分類誤差最小的K值。2）由于需要計算特征的距離，所以需要特征進行量化和標準化。