Onn

本文从kazenoyumechen.wordpress.com上迁移过来

KNN是機器學習中最簡單的算法之一，它即可以用來解決回歸（regression）問題，同時也可以用來解決分類（classification）問題。

假設目前已有一定的訓練數據，訓練數據的格式是 $(val, v_1, v_2, \ldots, v_n) \in C \times R^n$ 。C表示的是分類問題中的離散取值空間。同時，對一測試數據 $x^*$ ，測試數據的格式爲 $(v_1, v_2, \ldots, v_n)$ 。

爲了對 $x^*$ 進行分類，KNN將在訓練集中選取與 $x^*$ 最近的k個節點。並且根據這k個節點的標記值 $（val）$ 從而決定 $x^*$ 的取值。

距離度量：距離度量的方式多種多樣，對連續數據來說，一種常見的方法爲使用歐氏距離 $\sum_{i=1}^{n}(x_i - {x^*}_i)^2$ 來對兩個節點之間進行距離度量。對離散數據，如文本，則可用另外的度量方式（如Hamming distance）。

投票（vote）：投票是指根據KNN所選出的k個節點的信息對 $x^*$ 進行分類的過程。一種常見的投票方法爲將 $x^*$ 分類爲k個節點中標籤值最多的標籤。然而，若訓練數據中某個標籤的數目特別多， $x^*$ 被分類成該標籤的概率相當的大（major voting）。一種改進方法就是按照節點與 $x^*$ 的距離進行有權重的投票，與 $x^*$ 第i近的節點的投票權重爲 $\frac{1}{i}$ 。

k值的選擇：KNN算法中的k值大小是由算法實現者自行決定的。k選得過大的時候，就很容易出現major voting問題。而k選取過小又容易使得算法分類效果不好。現在的算法實現中，k值一般可通過Large Margin Nearest Neighbour或Neighbourhood component analysis進行學習。

由於對於每一測試數據均查找與該數據最近的前k個節點，最簡單的實現方法爲需要遍歷所有的訓練數據，當測試數據規模爲m時，該實現的算法復雜度爲O(nm）。當m數據比較大時，該算法就會慢得不可忍受。可通過使用cover tree或k-d tree對該算法進行改進，使得查找前k個節點的算法復雜度下降，整體算法復雜度降至O(mlogn)。

以下爲最爲簡單的KNN算法實現，在Kaggle的Digit Recognize上分率準確率能達到96.486%。

import numpy as np
import heapq
def dist(a, b):
    #歐氏距離
    return np.linalg.norm(a - b)
 
def find_k_neigh(x, trainX, trainY, k):
    Q = [] #使用堆保存離x節點最近的前k個節點
    for i in range(trainX.shape[0]):
        d = dist(x, trainX[i])
        #python只支持小根堆，將數值反轉實現大根堆的功能
        heapq.heappush(Q, (-d, i))
        if len(Q) > k:
            heapq.heappop(Q)
    #將堆中元素按照與k距離大小從小到大排序
    Q.sort()
    Q.reverse()
    return map(lambda x: x[1], Q)
 
def k_neigh_vote(idxs, trainY, k):
    M = {}
    for i in range(10): M[i] = 0
    maxLabel = 0
    for i in range(k):
        idx = idxs[i]
        label = trainY[idx]
        weight = 1. / (1 + i)
        M[label] += weight
        maxLabel = maxLabel if M[maxLabel] > M[label] else label
    return maxLabel
 
def knn(testX, trainX, trainY, k):
    testY = []
    for i in range(testX.shape[0]):
        neighs = find_k_neigh(testX[i], trainX, trainY, k)
        testY.append(int(k_neigh_vote(neighs, trainY, k)))
    return testY

KNN (K nearest neighbours)