2015年8月7日 星期五

[Algorithm] [python] K-鄰近算法(KNN k-nearest neighbors) 實作


機器學習演算法通常分為監督式學習以及非監督式學習兩種,監督式學習指已知部分要分類的對象的分類結果(例如男性女性),用這些已知的部分來學習分類的模式,將未知的對象來做分類;非監督式學習則是單純從屬性差異來將對象分類.今天要介紹的KNN(K鄰近算法)屬於監督式學習的一種,透過已知的分類結果來給予未知對象分類.


KNN的原理乃是利用未知對象與已知對象在屬性上的距離,找出最相似(相近)的幾個已知對象,根據這些已知的結果來決定未知對象的分類.例如一個人如果年紀超過50歲,同時具有榮民屬性,如果我們知道有這樣屬性的的人,通常都支持馬小久,那也會判斷這個人也會支持馬小九.

一般的操作定義如下:

  1. 計算已知類別數據中的點與當前未知點之間的距離
  2. 按照距離遞增次序排序
  3. 選取與未知點距離最小的K個點
  4. 確定這K個點的類別出現頻率
  5. 以頻率最高者當作未知類別的預測分類

這個定義很簡單,所以實作上我稍微改變了一下方式:
  1. 計算已知類別數據中的點與當前未知點之間的距離
  2. 在未排序的情況下選取前K個點當成備選
  3. 依序比較其餘距離與備選數據中的距離
  4. 如果有距離小於倍選數據中的距離,則替換之
  5. 當掃過所有數據後,計算備選中已知K個點的類別出現頻率
  6. 以頻率最高者當作未知類別的預測分類
這樣改變的好處在於如過當已知數列非常大時,可以減少大量資料在記憶體中排序產生的空間問題.



def knn(x, dataset, labels, k):
    ##計算x與各點之間距離
    distance = (((group - x) ** 2).sum(axis=1)) ** 0.5
    ##創造候選人array
    ##將距離和label結合
    distance = np.vstack((distance,labels)).T
    
    #初始值
    candidate = np.sort(distance[:k], axis=0)
        
    for i in range(k, len(distance)):
        #print candidate
        if distance[i][0] < candidate[:,0].any():
            ##把最大的數踢走,加入剛剛小的數字
            candidate = np.sort(np.vstack((candidate[:-1,:], distance[i])), axis=0)
                     
    result=np.zeros(len(candidate))
    for i in candidate[:,1]:
        result[i] += 1

    return np.argmax(result)