這篇博客來總結一下k近鄰法(k-nearest neighbor, K-NN)的相關內容。對K-NN並不能嚴格的從模型、學習準則和優化方法三方面進行總結，因爲K-NN是一種無參數學習的算法，它是基於實例的，這就意味這K-NN並沒有顯式的學習模型，而是利用訓練數據集對特徵向量空間進行劃分。所以在K-NN中，並沒有對參數的學習準則和優化方法，優化更多是從模型層面來做的。

k近鄰法(K-nearest neighbor)

1. 定義

​ 簡單來說，k近鄰法假設給定一個訓練數據集，其中的實例類別已經確定。在對新的不確定類別的實例進行分類時，根據離其最近的k個訓練實例的類別，通過多數表決等方式對其類別進行預測。由以上簡單定義，我們可以得出，k值的選擇、實例點間的距離度量和分類決策規則是k近鄰法的三個基本要素，也是K-NN方法的核心部分。如下圖所示，我們需要對圖中兩個叉點進行類別預測時，距離度量採用歐氏距離， $k=1$k=1，分類決策規則選擇多數表決，則兩個點的類別可以根據圖中點的相對位置很容易的確定。但這只是低維的情況，如果數據維度增加，數據間的相對位置關係將不再那麼容易直接看出。同時，隨着數據維度和數據量的增加，採用簡單的線性掃描方法通過比較待預測點和數據集中每個點的距離來得到距離最小點的時間複雜度將大大提高，這使得我們需要一種新的算法來更快的完成k個近鄰點的選擇過程，否則時間複雜度的快速提高將使得KNN在大數據上的應用變得無法實現。

​ 接下來給出k近鄰法的數學定義和一個簡單的算法流程：

​ 設輸入數據集爲 $T=\{(x_{1},y_{1}),(x_{2},y_{2}),\cdots ,(x_{N},y_{N})\}$T={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)}，其中 $x_{i}\in R^{n}$xi​∈Rn爲實例的特徵向量， $y_{i}\in \textbf{y}=\{c_{1},c_{2},\cdots ,c_{k}\}$yi​∈y={c1​,c2​,⋯,ck​}爲實例的類別， $i=1,2,\cdots ,N$i=1,2,⋯,N；待預測的實例特徵向量爲 $x$x;

​ 輸出：實例 $x$x所屬的類別 $y$y。

1. 根據給定的__距離度量方法__，在訓練集 $T$T中找出與 $x$x最鄰近的 $k$k個點 ，涵蓋這 $k$k個點的 $x$x的鄰域記作 $N_{k}(x)$Nk​(x)；

2. 在 $N_{k}(x)$Nk​(x)中根據__分類決策規則__決定 $x$x的類別 $y$y。例如，當選擇多數表決策略時，預測點的最終類別的數學定義如下：

   $y=\underset{c_{j}}{argmax}\ \ \sum_{x_{i}\in N_{k}(x)}I(y_{i}=c_{j}), \quad i=1,2,\cdots ,N;j=1,2,\cdots ,K$y=cj​argmax​  xi​∈Nk​(x)∑​I(yi​=cj​),i=1,2,⋯,N;j=1,2,⋯,K

   ​ 其中， $I$I爲指示函數，即當 $y_{i}=c_{j}$yi​=cj​時 $I$I爲1，否則 $I$I爲0。

   接下來，首先詳細介紹一下K-NN的模型，再分別討論K-NN算法的三個基本要素：距離度量、k值的選擇和分類決策規則

2. K-NN模型

​ 在K-NN中，當訓練集、距離度量、k值和分類決策規則確定後，對於一個新的輸入實例，它所屬的類別是唯一確定的。這等價於根據上述要素將特徵空間劃分爲一些子空間，確定子空間裏的每個點所屬的類。具體來說，特徵空間中的每個點的類別都是和與其相近的那些點相關的，所以這就要求我們能採用恰當的距離度量方法來找出與待預測點最接近的那些點，同時當前待預測點的類別究竟由幾個與其最接近的點的類別決定，也是需要我們手動定義的。最後，在得到了會對待預測點的類別產生影響的k個最近點後，我們採用確定的分類決策規則來得到待預測點的最終類別。

​ 更形象一點來說，在特徵空間中，對每個訓練實例點 $x_{i}$xi​，距離該點比其他點更近的所有點組成的一個區域，叫做__單元(cell)__。每個訓練實例點都擁有這樣一個單元，所有實例點的單元構成對特徵空間的一個劃分。顯然，如果訓練集或者距離度量方法發生變化，對特徵空間的劃分都將改變。一個對特徵空間進行劃分的例子如下圖所示。

​

3. 距離度量

​ 特徵空間中的兩個實例點的距離實際上是兩個實例點的相似程度的反映，距離越小說明兩個實例點越相似，一般常用的距離度量方法總結如下。

3.1 閔可夫斯基距離(Minkowski Distance，也叫 $L_{p}$Lp​距離)

​ 閔可夫斯基距離的一般定義爲：

$L_{2}(x,y)=(\sum_{i=1}^{n}\left | x_{i}-y_{i}\right |^{p})^{\frac{1}{p}}$L2​(x,y)=(i=1∑n​∣xi​−yi​∣p)p1​

​ 閔可夫斯基距離比較直觀，但是它與數據的分佈無關，具有一定的侷限性，如果 x 方向的幅值遠遠大於 y 方向的值，這個距離公式就 會過度放大 x 維度的作用。所以，在計算距離之前，我們可能還需要對數據進行 z-transform 處理，即減去均值，除以標準差（即 標準化歐式距離）。
　　這種方法在假設數據各個維度不相關的情況下利用數據分佈的特性計算出不同的距離。如果維度相互之間數據相關（例如：身高較高的 信息很有可能會帶來體重較重的信息，因爲兩者是有關聯的），這時候就要用到馬氏距離（Mahalanobis distance）了。

​ 根據p值的不同， 閔可夫斯基距離可以有幾種不同的形式。

3.1.1 歐式距離(Euclidean distance)

​ 當 $p=2$p=2時，稱爲歐式距離：

​ $L_{2}(x,y)=(\sum_{i=1}^{n}\left | x_{i}-y_{i}\right |^{2})^{\frac{1}{2}}$L2​(x,y)=(i=1∑n​∣xi​−yi​∣2)21​

​ 歐幾里得距離或歐幾里得度量是歐幾里得空間中兩點間「普通」（即直線）距離 ， 是一個通常採用的距離定義，指在m維空間中兩個點之間的真實距離，或者向量的自然長度（即該點到原點的距離） 。

3.1.2 曼哈頓距離(Manhattan Distance)

​ 當 $p=1$p=1時，稱爲曼哈頓距離：

$L_{1}(x,y)=\sum_{i=1}^{n}\left | x_{i}-y_{i}\right |$L1​(x,y)=i=1∑n​∣xi​−yi​∣

曼哈頓距離爲在歐幾里德空間的固定直角座標系上兩點所形成的線段對軸產生的投影的距離總和 。 想象你在曼哈頓要從一個十字路口開車到另外一個十字路口，駕駛距離是兩點間的直線距離嗎？顯然不是，除非你能穿越大樓。實際駕 駛距離就是這個「曼哈頓距離」,也稱爲城市街區距離(City Block distance) 。

3.1.3 切比雪夫距離(Chebyshev distance)

​ 當$p\rightarrow \infty $，稱爲切比雪夫距離：

$L_{\infty }(x,y)=\underset{i}{max}\left | x_{i}-y_{i} \right |$L∞​(x,y)=imax​∣xi​−yi​∣

​ 切比雪夫距離是向量空間中的一種度量，二個點之間的距離定義是其各座標數值差絕對值的最大值 .

3.2 標準化歐式距離(Standardized Euclidean distance)

​ 當數據各維分量的分佈尺度不一樣時(比如第一維範圍爲 $[1000,1000]$[1000,1000],第二維範圍爲 $[0.1,1]$[0.1,1])，不同的維度對最終距離的貢獻是不一樣的，這有可能會造成某些維度對最終結果的影響接近於0，很顯然，這並不是件好事，所以我們在很多時候需要提出一種度量策略，來平衡各個維度的尺度對最終距離的影響。標準化歐氏距離先將各個分量都「標準化」到均值、方差相等，這樣就實現了尺度上的統一。假設樣本集 $X$X的均值(mean)爲 $m$m ，標準差(standard deviation)爲 $s$s ， $X $的「標準化變量」表示爲：

$X^{'}=\frac{X-m}{s}$X′=sX−m​

​ 則標準化後的歐氏距離爲：

$L_{2}(x,y)=(\sum_{i=1}^{n}\left | \frac{x_{i}-y_{i}}{s_{i}} \right|^{2})^{\frac{1}{2}}$L2​(x,y)=(i=1∑n​∣∣∣∣​si​xi​−yi​​∣∣∣∣​2)21​

3.3 餘弦相似度(Cosine Similarity)

​ 餘弦相似度的定義如下：

$CosineSimilarity(x,y)=\frac{x\cdot y}{\left | x \right |\cdot \left | y \right |}$CosineSimilarity(x,y)=∣x∣⋅∣y∣x⋅y​

​ 餘弦相似度更多的是從方向上區分差異，度量兩個向量之間夾角的餘弦值，而對絕對的數值不敏感。因此沒法衡量每個維數值的差異，會導致這樣一個情況：比如用戶對內容評分，5分制，X 和 Y 兩個用戶對兩個內容的評分分別爲(1,2)和(4,5)，使用餘弦相似度得出的結果是0.98，兩者極爲相似，但從評分上看 X 似乎不喜歡這2個內容，而 Y 比較喜歡，餘弦相似度對數值的不敏感導致了結果的誤差，需要修正這種不合理性，就出現了調整餘弦相似度，即所有維度上的數值都減去一個均值，比如 X 和 Y 的評分均值都是3，那麼調整後爲(-2,-1)和(1,2)，再用餘弦相似度計算，得到-0.8，相似度爲負值並且差異不小，但顯然更加符合現實。

​ 餘弦距離的定義爲：

​ $CosineDistance(x,y)=1-CosineSimilarity(x,y)$CosineDistance(x,y)=1−CosineSimilarity(x,y)

3.4 調整餘弦相似度(Adjust Cosine Similarity)

​ 修正cosine相似度的目的是解決cosine相似度僅考慮向量維度方向上的相似而沒考慮到各個維度的量綱的差異性，所以在計算相似度的時候，做了每個維度減去均值的修正操作。定義如下：

$L(x,y)=\frac{\sum_{i}^{n} ((x_{i}-m_{i})\cdot (y_{i}-m_{i}))}{\left | x \right |\cdot \left | y \right |}$L(x,y)=∣x∣⋅∣y∣∑in​((xi​−mi​)⋅(yi​−mi​))​

​ 其中， $m_{i}$mi​爲所有數據第 $i$i維的平均值。

3.3 馬氏距離(Mahalanobis distance)

​ 這一塊目前還不是太想看，就先留着大佬的鏈接( https://www.cnblogs.com/Zhouwl/p/9482874.html )，之後有空再來填坑吧。

​ 馬氏距離的兩個實例點之間的距離是和整體樣本分佈有關的，可以考慮各種特性之間的聯繫，同時可以不受量綱的影響，這和其他的距離度量方式不一樣。

3.4 漢明距離(Hamming Distance)

​ 兩個等長字符串 s1 與 s2 的漢明距離爲：將其中一個變爲另外一個所需要作的最小字符替換次數。 同時這裏也可以瞭解一下__編輯距離__，都是度量字符串相似度的方法。

3.5 傑卡德距離(Jaccard Distance)

​ 傑卡德距離(Jaccard Distance) 是用來衡量兩個集合差異性的一種指標，它是傑卡德相似係數的補集，被定義爲1減去Jaccard相似係數。而傑卡德相似係數(Jaccard similarity coefficient)，也稱傑卡德指數(Jaccard Index)，是用來衡量兩個集合相似度的一種指標。

3.6 相關距離(Correlation distance)

​ 相關係數是衡量隨機變量X與Y相關程度的一種方法，相關係數的取值範圍是[-1,1]。相關係數的絕對值越大，則表明X與Y相關度越高。當X與Y線性相關時，相關係數取值爲1（正線性相關）或-1（負線性相關）：

相關距離爲：

4. k值的選擇

​ k值的選擇上，其實並沒有太多理論的內容可以討論，更多的還是要通過實驗的方法，來確定適合當前數據集的最優k值。

k值	誤差	缺點	結果
較小的值	近似誤差減小，估計誤差增大	預測結果會對鄰近的實例點非常敏感	模型變複雜，容易發生過擬合
較大的值	近似誤差增大，估計誤差減小	與待預測點較遠的(不相似的)訓練實例也會對預測起作用	模型變簡單，容易發生欠擬合

5. 分類決策規則

​ 在得到與待預測點最近的k個最近鄰點的標籤後，就需要根據分類決策規則確定待預測點的類別

• 多數表決規則：這種規則很好理解，其實就是將k個最近鄰點中包含實例點最多的類別作爲待預測點的預測類別。當然，這裏還需要解決一個問題，就是當有多個類別對應的實例點數相等且最大時，我們應該選擇哪種類別作爲待預測點的類別。
• 核方法：多數表決規則只考慮了k個近鄰點的類別信息，而沒有考慮近鄰點和待預測點之間的距離信息。但直觀上，我們可以知道，和待預測點距離較近的那些點對最終結果的影響應該比那些距離較遠的點更大。核方法的引入，可以在進行決策時將兩個點之間的距離信息考慮進來。簡單而言，其實就相當於通過核函數給每個點對應的標籤加一個權重，這個權重和距離成反比，距離越大權重越小，距離越小權重越大。
  

6. k近鄰法的實現：kd樹

​ kd樹是一種對k維空間中的實例點進行存儲以便對其進行快速檢索的樹形數據結構。kd樹是二叉樹，表示對k維空間的一個劃分。構造kd樹相當於不斷地用垂直於座標軸的超平面對k維空間進行切分，構成一系列的k維超矩形區域。kd樹的每個結點對應於一個k維超矩形區域。

k-NN中的k和kd樹中的k意義是不同的：

• k-NN中的k表示的要選擇k個近鄰點
• kd樹中的k表示樹中存儲的數據的維度爲k維

​ 下面分別來說明一下kd樹的構建過程和搜索kd樹找到k個近鄰點的過程

6.1 kd樹的構建

​ 首先，要明確的是最終構建的kd樹是一棵平衡二叉排序樹，保證樹是平衡能得到最好的搜索效率。那麼問題來了：

1. 如何選擇排序的標準？
2. 如何保證樹是平衡的？

​ 針對第一個問題，kd樹中的排序標準爲實例點中某一維的值。那麼在構建子樹時應該選擇哪一維作爲排序標準呢？最簡單的情況當然是順序選擇數據的維度作爲排序標準，即在kd樹中深度爲 $j$j的節點選擇的維度 $d$d爲 $d=j(mod \ \ k) + 1$d=j(mod  k)+1。我們也可以採用__最大方差法__找到當前數據域中方差最大的一維作爲排序標準，方差越大說明數據越分散，那我們可以更容易的將其中的數據分開。

​ 至於第二個問題，當我們確定當前深度採用哪一維作爲排序標準後，我們只需要取這一維的中位數對應的點作爲當前子樹的根節點，即可保準二叉樹的平衡性。

構造平衡kd樹的過程如下：

​

​ 下面給出一個例子說明一下這種通過超平面來分隔超矩形空間的例子。給定一個二維空間的數據集：

$T=\{ (2,3)^{T},(5,4)^{T},(9,6)^{T},(4,7)^{T},(8,1)^{T},(7,2)^{T} \}$T={(2,3)T,(5,4)T,(9,6)T,(4,7)T,(8,1)T,(7,2)T}

​ 結果如下圖所示，給出了劃分超平面中的點在kd樹中的深度和二維平面的劃分結果。

6.2 kd樹的最近鄰搜索

​ kd樹的搜索過程：給定一個目標點，搜索其最近鄰。首先找到包含目標點的葉節點；然後從該葉節點出發，依次退回到父節點；不斷查找與目標點最鄰近的節點，當確定不可能存在更近的結點時終止。這樣的搜索就被限制在空間的局部區域上，效率大爲提高。

​ 利用kd樹進行k近鄰搜索，可以省去對大部分數據點的搜索，這個過程其實就是一個對二叉樹的剪枝過程，我們基於一定的策略剪掉那些一定不會存在更優解的子樹，這樣在平均情況下能大大提高kd樹的搜索效率。

​ kd樹的最近鄰搜索過程如下：

​

​ 這個算法中，有兩個問題需要重點關注：

1. 爲什麼需要有(1)步，首先找到目標點對應的劃分子空間？
2. 在回溯的過程中，如果確定是否需要對當前節點的父節點的另一棵子樹進行遍歷

​ 第一個問題，需要有(1)步是爲了剪枝的考慮。當我們首先將目標點定位到其對應的劃分子空間後，一般情況下，目標點對應劃分空間中的節點有很大概率會是最近點或者離最近點非常近的點，這樣有助於算法能儘可能多的實現剪枝。

​ 針對第二個問題，其實也很好理解，首先我們知道算法需要尋找的是比當前最小距離更小的點，我們只需要確定當前目標點和最短距離確定的搜索域和當前節點的父節點的另一棵子樹對應的區域有沒有交集即可，如果沒有交集，則可以進行剪枝，因爲那個區域中所有的點到目標點的距離都會大於當前最小距離。如果有交集，則需要對另一棵子樹進行遍歷，首先找到從當前維度起目標節點在該子樹中對應的劃分區域，然後重複回溯過程。下面兩個圖能幫助我們更好的理解，很明顯可以看出，當沒有交集時，我們是不需要考慮由 $y=4$y=4劃分出的上方超平面的，而有交集時，我們需要考慮這個超平面中是否存在更近點。

6.3 將最近鄰搜索推廣到k近鄰搜索

​ 其實這也是一個很簡單的過程，我們只需要在遞歸的過程中首先選定最早遇到的k各點作爲候選k近鄰點，然後根據這k個點到目標點的距離進行排序，每次只更新到目標點距離最大的那個點即可。因爲kd樹中每個節點只保存一個數據，所以我們每次必定只能選擇是否更新到目標點距離最大的那個點，如果當前點到目標點的距離小於這個值則進行更新，然後重新排序，否則不更新。這個過程其實和最近鄰搜索是完全一樣的，只是在初始化時，先選出了k個候選。

References

1. K近鄰算法的kd樹實現
2. ML筆記：機器學習中的幾種距離度量方法比較
3. 李航《統計學習方法 第二版》
4. 距離度量方法