機器學習演算法——kNN（k-近鄰演算法）

• 2020 年 10 月 12 日
• 筆記
• k-近鄰, kNN, 機器學習, 演算法, 演算法詳解

演算法概述

通過測量不同特徵值之間的距離進行 [分類]

• 優點:精度高、對異常值不敏感、無數據輸入假定。
• 缺點:計算複雜度高、空間複雜度高。
• 適用數據範圍: 數值型 和 標稱型 。

演算法流程

• 數據
  • 樣本數據（多維多行數據 + 標籤）
  • 預測數據（多維一行數據）

• 比較預測數據與樣本數據的距離

  • 歐氏距離
    

• 將樣本數據按照距離從小到大排序

• 選取前 k 個樣本數據，取出現次數最多的樣本標籤作為預測數據的分類標籤

程式碼示例

import collections
import numpy as np

def culEuDistance(x1, x2):
    """
    計算歐氏距離
    """
    return ((x1 - x2)**2).sum()**0.5

def knn(X, dataSet, labels, k):
    """
    比較預測數據與歷史數據集的歐氏距離，選距離最小的k個歷史數據中最多的分類。
    :param X:           需要預測的數據特徵
    :param dataSet:     歷史數據的數據特徵
    :param labels:      與dataSet對應的標籤
    :param k:           前k個
    :return:            label標籤
    """
    if isinstance(dataSet, list):
        dataSet = np.array(dataSet)
    rowNum = dataSet.shape[0]
    X = np.tile(X,(rowNum,1))
    distances = np.empty(rowNum)
    for row in range(rowNum):
        distances[row] = culEuDistance(X[row], dataSet[row])
    sortedIdx = distances.argsort()
    candidates = []
    for i in range(k):
        candidates.append(labels[sortedIdx[i]])
    return collections.Counter(candidates).most_common(1)[0][0]

if __name__ == "__main__":
    # print(culEuDistance(np.array([3,4]), np.array([2,1])))
    X = [101,20]
    dataSet = [[3,104],[2,100],[1,81],[101,10],[99,5],[98,2]]
    labels = ['愛情片','愛情片','愛情片','動作片','動作片','動作片']
    print(knn(X,dataSet,labels,k=3))

    # 動作片