機器學習基礎——簡單易懂的K鄰近演算法，根據鄰居「找自己」

2020 年 3 月 11 日
筆記

本文始發於個人公眾號：TechFlow，原創不易，求個關注

今天的文章給大家分享機器學習領域非常簡單的模型——KNN，也就是K Nearest Neighbours演算法，翻譯過來很簡單，就是K最近鄰居演算法。這是一個經典的無監督學習的演算法，原理非常直觀，易於理解。

監督與無監督

簡單介紹一下監督這個概念，監督是supervised的直譯，我個人覺得不太準確，翻譯成有標註和無標註可能更加準確。也就是說如果模型在學習的時候，既能夠看到樣本的特徵又可以看到樣本的結果，那麼就是有監督學習，如果只能看到特徵，但是並不能知道這些特徵對應的結果，那麼就是無監督學習。

之前我們介紹的線性回歸和邏輯回歸模型就是典型的有監督模型，因為模型在訓練的時候知道樣本的結果，並且根據我們設計的損失函數朝著貼近樣本真實結果的方向「努力」。而今天介紹的KNN演算法則是一個經典的無監督學習模型，演算法在訓練的時候並不知道正確的結果是什麼，也因此模型根本沒有損失函數這個概念，那麼自然整個演算法的運行原理也很監督模型大相徑庭。

演算法概述

其實KNN演算法的原理非常簡單，簡單到只有一句話，就是找到樣本的K個鄰居，然後這K個鄰居出現次數最多的結果就是答案。

但是我們怎麼定義鄰居，又怎麼找到這些鄰居呢？

在回答這個問題之前，我們先來看一個例子。

假設現在有這麼一個問題，我需要知道全城的用戶有哪些用戶有車，但是我們只知道用戶的家庭地址，那麼該怎麼辦呢？

很顯然，我需要在全城做一個調查，也就是對全城市民做一個抽樣，抽取一部分做個是否有車的調研。對於剩下的用戶呢，我去尋找離他最近的幾個鄰居，看看他的這幾個鄰居是否有車。如果離他近的鄰居大多數都有車，那麼，我可以認為，該用戶可能住在富人區，他有車的概率比較大。如果他的鄰居都沒有車，可能他住在窮人區，他很有可能也沒有車。

你可能會說中國不像美國可以劃分成窮人區和富人區，往往在一個區域內窮富是雜居的，用這種方法得出的結果準確率肯定不高。

的確存在這個問題，所以我們可以在此基礎上做一點優化，很簡單，我們只知道用戶住在哪裡是不夠的，我們可能還需要了解用戶的收入情況。在尋找他最近的鄰居的過程當中，除了要考慮距離上的遠近之外，還需要保證收入儘可能接近。

如果能知道和他距離和收入都接近的鄰居是否有車，那麼大概率可以判斷這個用戶是否有車。重複這個演算法，我就可以通過少量的樣本，算出全體樣本是否有車的情況。

說到這裡，想必你應該能明白，在KNN演算法的範疇當中，「鄰居」指的不是地理上的鄰近關係，而指的是樣本空間的接近。

我們都知道，對於向量A(a1,a2,a3…an)，B(b1,b2,b3…bn)

在機器學習當中，我們通常會把一條樣本數據當做向量空間中的一條向量。比如在剛剛的問題當中，用戶A，他的樣本可能是(120.3213, 30.1312, 10.5)，指的是居住地點的經緯度和年收入。也可能是(城東, 涇河花園, 10.5)，或者是(城東, 沿河西路, 涇河花園, 10.5)等等。

同樣的一條樣本，表示成向量就有多種形式。對於不同的問題而言，不同的表示方法擁有不同的效果。在當前問題當中，我們需要計算向量和向量之間的距離，顯然，使用第一種經緯度的表示方式更好。

演算法原理

通過上面這個例子，其實我們已經把演算法的整個運行過程講解清楚了。所謂的k-鄰近演算法，其實就是使用距離樣本最近的k個樣本的結果來代表當前樣本的結果。

整個演算法的流程如下：

採集一批有標註結果的樣本，設為s
遍歷每一個未知結果的樣本 $x_i$
遍歷s，計算s中的每一個樣本和 $x_i$ 的距離
根據距離進行排序，選出距離最小的k個樣本
選出這k個樣本中出現頻次最多的類別作為 $x_i$ 的結果

演算法流程不難理解，但是其中有幾個注意點：

首先，每一個樣本其實指的是樣本空間里的一個向量。既然是向量，並且要計算樣本之間的距離，那麼向量的每一個維度都必須是實數。一般情況下，字元串是無法作為特徵計算距離的。

其次，向量距離的計算方法。常規來說，向量之間的距離可以理解成空間中兩個點的距離，關於這個距離常規上有幾種計算的公式。

第一種叫做歐式公式，就是我們剛才列的也是最常見的歐幾里得距離公式：

第二種叫做曼哈頓距離，曼哈頓是紐約的CBD，既然是街區，從一個路口到另一個路口的距離顯然是不能從街區中跨越的。所以兩個路口的距離，其實是兩點的直角連線距離。

假設一個點坐標是(3, 4) ，另一個點的坐標是(5, 1)，這兩點的距離d = | 3 – 5| + | 4 – 1| = 5

公式為：

在距離計算的方法當中，歐氏距離和曼哈頓距離最常用，除了這兩種之外還有切比雪夫距離和閔可夫斯基距離等，一般不太常用，我們不多做贅述，感興趣的可以自行Google。

程式碼實現

下面就到了我們緊張刺激的程式碼實現環節，KNN的原理不算難，只要能理解，稍微思考一下我想大部分同學應該都能寫出來。所以之前阿里的校招經常用KNN作為筆試題，考察一下同學的程式碼能力以及對基礎模型的理解情況。所以實現是一方面，將程式碼寫漂亮，實現完美又是另一方面。

仔細想一下當我們的數據有了之後，KNN主體就只有一個函數，我們先來看一下不使用任何庫函數進行實現的程式碼：

def classify(vector, dataSet, labels, k):
    dis = []
    for i in range(len(dataSet)):
        data = dataSet[i]
        d = calculate_distance(vector, data)
        dis.append(d)
    dis_index = sorted(enumerate(dis), key=lambda x: x[1])
    label_map = {}
    for i in range(k):
        label = labels[dis_index[i][0]]
        if label in label_map:
            label_map[label] += 1
        else:
            label_map[label] = 1
    maxi = 0
    label = None
    for i in label_map:
        if label_map[i] > maxi:
            maxi = label_map[i]
            label = i

    return label

其中calculate_distance是計算兩個向量距離的函數，實現也很簡單，就是套用一下上面剛才提到的距離公式，基本沒有難度：

def calculate_distance(vectorA, vectorB):
    d = 0
    for i in range(len(vectorA)):
      d += (vectorA[i] - vectorB[i]) * (vectorA[i] - vectorB[i])
    return math.sqrt(d)

但是顯然這是沒有必要的，我們多做了很多無用功。靈活地使用庫函數，可以將程式碼縮減到不可思議的地步：

import random

import numpy as np
from collections import Counter


def classify(x, dataset, labels, K):
    x, dataset = np.array(x), np.array(dataset)
    # 通過numpy計算距離，numpy有廣播機制
    # 會自動將x和dataset當中的每一行計算距離
    dis = np.sqrt(np.sum((x - dataset) ** 2, axis=1))
    # 按照距離排序，返回結果對應的下標
    topKIdices = np.argsort(dis)[:K]
    labels = np.array(labels)
    # 使用Counter進行計數，返回數量最多的
    counter = Counter(labels[topKIdices])
    return counter.most_common(1)[0][0]

不知道大家看到有沒有覺得有點不可思議，我們一個for循環都沒有用到就實現了KNN演算法，只有短短5行。其中Numpy是我們做機器學習非常常用的包，由於Numpy有非常多的API可以非常方便地進行計算，所以我們會在之後單獨開一個Numpy專題。關於Counter等庫函數的用法，在之前介紹collections的文章當中介紹過，如果有遺忘的同學可以在公眾號回復collections獲取文章。

最後，我們創造一個簡單的sample來驗證一下：

def create_data_set():
    dataset = np.array([[0.5, 0], [0, 0.5], [1.5, 1], [1, 1.5]])
    labels = ['A', 'A', 'B', 'B']
    return dataset, labels

運行程式得到的結果是A。

優化

到這裡我們還沒有結束，還有一個問題值得討論。在我們剛才敘述演算法流程的過程當中，有一個關鍵點被我們忽略了。

我們的樣本由特徵構成，我們對特徵向量計算距離。問題是這些特徵並不是一個維度的，還用上面的例子。我們為了判斷一個用戶是否有車，用到了三個特徵，分別是他家的經度、緯度和年收入。注意，經緯度和年收入並不是一個量綱下的變數，從數學上我們當然可以對它們當做是一個量綱來計算，但是這樣顯然是不準確的。最主要的問題是，不同量綱的特徵波動的幅度可能完全不同。

這一點應該不難理解，對於經緯度而言，取值範圍假設是[0, 360]，但是年收入的浮動範圍可能是上千萬。顯然如果我們直接來計算距離的話，那麼主要的權重就落在了年收入上，這個模型就發生了傾斜，這顯然是我們不想看到的，因為會影響模型最終的效果。為了解決這個問題，我們需要將這些量綱歸一化，消除量綱帶來的影響。這也是KNN關鍵的優化。

歸一化的方式很多，比較常用的有兩種。一種是Standardization，又稱為Z-score normalization，歸一化之後的數據服從正態分布，它的公式如下：