本文包含：

1.走近k近鄰 - 你周圍的人決定了你是怎樣的人
2.重要概念
3.k近鄰算法的數(shù)學形式
4.k近鄰模型的直觀認識
5.如何計算距離
6.k值的選擇
7.k近鄰算法的損失函數(shù)
8.kd樹數(shù)據(jù)結(jié)構(gòu)
9.搜索kd樹

KNN模型Python復(fù)現(xiàn)，使用了線性掃描；權(quán)值優(yōu)化兩種算法：

舟曉南：k近鄰（KNN）模型python復(fù)現(xiàn) - 線性掃描；帶權(quán)值的近鄰點優(yōu)化方法

1.走近k近鄰 - 你周圍的人決定了你是怎樣的人：

人是群居動物，這不僅是因為整個社會運轉(zhuǎn)需要各種各樣的人才進行勞動分工和資源交換，還因為人本性上需要認同感，不僅是身份認同，還希望對他的行事風格的，性格的，愛好的，外表的等等方面的認同。

基于這點，大部分的人類個體都會在生活中逐漸與一群于自己相似的人類個體組成一個個圈子，我們可以將這個圈子認為是一個類。

而在這個圈子里，不說全部，至少絕大部分的人類個體都會有共同點，這些共同點，就可以用來判斷一個新來的人最有可能被哪一個圈子所接受，或者他最有可能長久地加入哪個圈子，這就是分類。

人是群居動物

這其實就是近朱者赤，近墨者黑的思想，但在k近鄰算法中，我們并不關(guān)心到底是因為他本來就是赤的所以近朱，還是因為他近墨而變黑，我們也不關(guān)心他的變化過程，我們只關(guān)心當前狀態(tài)下，可以將他分類為赤者，還是黑者。

在明白k近鄰算法的大致思路后，我們需要了解它的數(shù)學形式。

2.重要概念：

在正式介紹k近鄰模型之前，需要先對一些基本概念有所了解，如果明白這些概念可以直接跳過。

泛化能力：指通過機器學習獲得模型后，該模型對新輸入的實例進行正確預(yù)測的能力。如果在學習模型中，僅使用了相同的驗證集來驗證模型，那么在對模型不斷的改進中的參照物實際上就是一個不變的驗證集，因此訓練出來的模型可能僅對這個特定的驗證集的預(yù)測能力較高，但對新的數(shù)據(jù)集的預(yù)測能力較差，這就是所謂的泛化能力低。

近似誤差：更關(guān)注于訓練集。當新輸入的實例更依賴于訓練集進行預(yù)測，則近似誤差較小，也就是對訓練集的預(yù)測較好，但該預(yù)測僅僅是依據(jù)訓練集而言，其泛化能力可能比較差。

估計誤差：更關(guān)注于模型的泛化能力。模型泛化能力越強，其估計誤差越低，但是往往這樣的模型的近似誤差較高。

噪聲：被錯誤標記的實例，或者數(shù)據(jù)的波動。噪聲對過于依賴訓練集的模型影響非常大，因為這樣訓練出來的模型將訓練集中的噪聲也考慮了進去，而在新的需要進行預(yù)測的數(shù)據(jù)集中的噪聲與訓練集中的噪聲并不一樣，所以這樣的模型泛化能力較弱。換一種給說法就是這種算法或模型對噪聲敏感。

過擬合：訓練集中難免會產(chǎn)生噪聲，如果一個模型將訓練集中的噪聲也進行了學習，該模型對新數(shù)據(jù)的預(yù)測的表現(xiàn)會很差，這個情況稱為過擬合。

欠擬合：欠擬合是指模型對訓練集的預(yù)測和對新的數(shù)據(jù)的預(yù)測都表現(xiàn)不好的情況。

下圖中，M代表擬合多項式的次數(shù)，當M=0和1時都產(chǎn)生了欠擬合，當M=9時產(chǎn)生了過擬合，當M=3時，其擬合程度較好。

交叉驗證：一種常用的模型選擇方法。在訓練集數(shù)據(jù)充足的情況下，將訓練集隨機地切分成三個部分，分別為新的訓練集、驗證集和測試集。訓練集用來訓練模型，驗證集用于模型的選擇，而測試集用于最終對模型的評估。對多個模型而言，可以選擇對驗證集有最小預(yù)測誤差的模型。

如果數(shù)據(jù)量并不充足，可以采用交叉驗證方法。交叉驗證的基本想法是重復(fù)地使用數(shù)據(jù)，比如將數(shù)據(jù)隨機切分成A，B，C，D，E五組，使用其中的四組進行模型的訓練，用剩下的一組對模型進行驗證。驗證完成后，再用不同的四組組合成新的訓練集，用剩下的另一組驗證模型。這一過程重復(fù)進行5次，即A，B，C，D，E輪流作為驗證集使用。

當然，我們也可以將數(shù)據(jù)集切分成不同數(shù)量的組，這種交叉驗證的方法被稱作S折交叉驗證，S代表數(shù)據(jù)集被切分后的組數(shù)，比如上面提到的為5折交叉驗證。

多數(shù)表決：一種分類依據(jù)，比如對新輸入實例有三個表決認為應(yīng)該歸為A類，五個表決認為應(yīng)該歸為B類，則將該實例歸為B類。

經(jīng)驗風險：模型關(guān)于訓練集的平均損失。

3.k近鄰算法的數(shù)學形式：

給定一個訓練數(shù)據(jù)集，對新的輸入實例，在訓練數(shù)據(jù)集中找到與該實例最鄰近的k個實例，這k個實例的多數(shù)屬于某個類，就把該輸入實例分為這個類。

過程：

(1) 根據(jù)給定的距離度量，在訓練集T中找出與最鄰近的k個點，涵蓋這k個點的x的鄰域記作Nk(x)。

(2) 在Nk(x)中根據(jù)分類決策規(guī)則（如多數(shù)表決）決定x的類別y。

數(shù)學表達如下：

I為指示函數(shù)，即當yi=cj時I為1，否則為0。N是x的鄰域中實例的數(shù)量，Cj是某一種類別，K是實例種類的數(shù)量。

上式用文字描述為，在鄰域內(nèi)遍歷每個樣本點，并得到分到每個類別的樣本點的個數(shù)，個數(shù)最多的類別認為是新輸入實例y的類別。

需要指出的是，對于領(lǐng)域的定義根據(jù)對距離的定義不同而改變，距離定義比較常見的有歐式距離和曼哈頓距離等，接下來會在如何計算距離這一節(jié)中談到這一點。

4.k近鄰模型的直觀認識：

k近鄰法中，當訓練集、距離度量（如歐氏距離）、k值（近鄰點的數(shù)量）及分類決策規(guī)則（如多數(shù)表決）確定后，對于任何一個新的輸入實例，它所屬的類可以被確定并且為唯一的類。

特征空間中，對每個訓練實例點x，距離該點比其他點更近的所有點（這里指特征空間中的所有點，而非單指實例點）組成一個區(qū)域，叫作單元。每個訓練實例點擁有一個單元，所有訓練實例點的單元構(gòu)成對特征空間的一個劃分。

在該實例點對應(yīng)的單元中的每個點都被歸為該實例點的類中。如果有一個新的實例點落入某一單元內(nèi)，則該點被劃分為這個單元所對應(yīng)的類中。

接下來講解如何確定訓練集實例與新輸入實例之間的距離。

5.如何計算距離：

k近鄰模型的特征空間一般是n維實數(shù)向量空間Rn。使用的距離是歐氏距離，但也可以是其他距離，如更一般的L距離或Minkowski距離。

對于兩點xi，xj之間的距離的一般公式可以用Lp定義：

其中p為距離公式的參數(shù)，xi和xj都是n維特征空間中的向量：

舉例來說，對于在二維特征空間中的兩個實例x1(3,3)，x2(4,5)：

當p=2時，稱為歐氏距離。

當p=1時，稱為曼哈頓距離。

當p=∞時，它是各個坐標距離的最大值。

下圖代表在二維空間中p取不同值時，與原點的L距離為1的點圍成的圖形。

在k近鄰算法中，我們通常采用歐氏距離。我們有了距離之后，還需要決定到底要考慮多少個點來決定新輸入實例的類，也就是k值到底選多大比較合適。

6.k值的選擇：

k代表與新的輸入實例距離最近的實例的數(shù)量。

如果選擇較小的k值，就相當于用較小的鄰域中的訓練實例進行預(yù)測，“學習”的近似誤差會減小，只有與輸入實例較近的訓練實例才會對預(yù)測結(jié)果起作用。但缺點是“學習”的估計誤差會增大。預(yù)測結(jié)果會對近鄰的實例點非常敏感，而遠處的實例點則對此沒有影響，如果鄰近的實例點恰巧是噪聲，預(yù)測就會出錯。

k值的減小就意味著整體模型變得復(fù)雜，容易發(fā)生過擬合。

如果選擇較大的k值，就相當于用較大鄰域中的訓練實例進行預(yù)測。其優(yōu)點是可以減少學習的估計誤差，但缺點是學習的近似誤差會增大。這時與輸入實例較遠的訓練實例也會對預(yù)測起作用，使預(yù)測發(fā)生錯誤。k值的增大就意味著整體的模型變得簡單，容易發(fā)生欠擬合。

在應(yīng)用中，k值一般取一個比較小的數(shù)值。通常采用交叉驗證法來選取最優(yōu)的k值。

在了解了如何選擇k值的方法后，我們需要一個具體的數(shù)值來代表不同的k對應(yīng)的模型的好壞，也就是損失函數(shù)。接下來講解k近鄰算法的損失函數(shù)。

7.k近鄰算法的損失函數(shù)：

k近鄰法中的分類決策規(guī)則往往是多數(shù)表決，即由輸入實例的k個鄰近的訓練實例中的多數(shù)類決定輸入實例的類。

多數(shù)表決有如下解釋：如果分類的損失函數(shù)為0-1損失函數(shù)（即分類錯誤則為1，分類正確則為0，要極小化該損失函數(shù)，讓分類錯誤的數(shù)量下降），分類函數(shù)為：

即共有K個類。

那么，誤分類的概率 =（1 - 正確分類的概率）：

其中I是指示函數(shù)。

要使誤分類率最小即經(jīng)驗風險最小，就要使? $\sum_{x_{i}\in N_{k}(x) }^\cdot I(y_{i} =c_{j} )$ ?最大，所以多數(shù)表決規(guī)則等價于經(jīng)驗風險最小化，因為多數(shù)表決使得正確分類的個數(shù)最大化，而經(jīng)驗風險最小化是使被誤分類的個數(shù)最小化，兩者等價。

就像上一節(jié)所說，可以通過交叉驗證法選擇最合適的k值，具體就是對多個k值訓練多個模型，然后通過交叉驗證法找到經(jīng)驗風險最小的k值，就是最優(yōu)k值。

現(xiàn)在有了選擇k值的具體方法，但是在實際應(yīng)用中，如果實例數(shù)量很多，計算每個新輸入實例與每個訓練實例的距離，再選擇其中與各個輸入實例較近的k個訓練實例（這種暴力的方法叫做線性掃描），將消耗大量算力和時間。那么有沒有提高計算效率的方法呢？答案就是采用kd樹數(shù)據(jù)結(jié)構(gòu)對數(shù)據(jù)進行存儲（并非唯一的方法，這里僅參照《統(tǒng)計學習方法》講解該法）。

8. kd樹數(shù)據(jù)結(jié)構(gòu)：

具體的kd樹方面的知識需要專門學習數(shù)據(jù)結(jié)構(gòu)，在《統(tǒng)計學習方法》這本書中僅是簡單地介紹了以下kd樹的構(gòu)造和搜索方法和原理。

構(gòu)造kd樹的方法如下：

(1) 構(gòu)造根結(jié)點：在特征空間中選擇一個維度，選擇所有實例在該維度上的中位數(shù)作為切分點，將特征空間分割為兩個部分。

(2) 生成子結(jié)點：在分割出來的兩個子空間中選擇在當前維度小于切分點的子空間，并選擇另一個維度，按照1的方法確定切分點，將該子區(qū)域再次分割為兩個部分，并將該切分點對應(yīng)的實例特征存儲在左子結(jié)點。如果選擇當前維度大于切分點的子空間，則把新的切分點對應(yīng)實例特征存儲在右子結(jié)點。

(3) 重復(fù)步驟2，直到特征空間中的子空間中不存在實例點。

注意：

(1) 通常，依次選擇坐標軸對空間切分。

(2) 如果樣本點數(shù)量為偶數(shù)，數(shù)學上中位數(shù)應(yīng)當是中間兩個數(shù)的平均值，但在kd樹中一個結(jié)點不能為空，因此可以選擇中間兩個數(shù)中的一個作為切分點。

(3) 按照上述方法得到的kd樹是平衡的，但平衡的kd樹搜索時的效率未必是最優(yōu)的。所謂平衡樹，是指左右子樹的高度相差不超過 1 的樹。

現(xiàn)在舉一個書中的例子，方便更好理解：

對以下實例建立kd樹：

首先選擇橫軸作為切分軸，我們將所有實例的橫軸坐標從小到大排列為(2, 4, 5, 7, 8, 9)，那么中位數(shù)應(yīng)該是（5+7）/2 = 6，但因為沒有實例點的橫坐標為6，而kd樹中不能存在空結(jié)點，于是采用5或7為切分點，這里采用7為切分點，對應(yīng)的根結(jié)點為（7，2）。

接著在切分的子空間中，都選擇豎軸作為切分軸，左空間的中位數(shù)是4，右空間的中位數(shù)是6，因此根結(jié)點左邊的子結(jié)點存儲（5，4），右節(jié)點存儲（9，6），以此類推，得到圖中的kd樹。

可以看到對于根節(jié)點而言，左子樹高度為2，右子樹高度也為2，高度差為0。對于（5，4）這個結(jié)點來說，左右高度差為0。對于（9，6）來說，左右高度差為1，不超過1。因此該樹是平衡樹。