[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. 以頻率最高者當作未知類別的預測分類

這樣改變的好處在於如過當已知數列非常大時，可以減少大量資料在記憶體中排序產生的空間問題．

實作程式碼在這：https://github.com/bryanyang0528/machine-learning-python/blob/master/KNN.ipynb

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)