K近鄰（k-Nearest-Neighbors，kNN）分類方法是最簡單的機器學習方法之一，也是引導你入門機器學習和分類問題的一個非常好的方式。在最基本的層面，kNN本質上是通過在訓練數據中尋找最相似的數據點進行分類，並基於分類做出有根據的推測（educated guess）。儘管非常易於理解和實現，這一方法在許多領域中得到了廣泛應用，例如推薦系統（recommendation system）、語義搜索（semantic searching）、異常檢測（anomaly detection）。
和其他機器學習問題一樣，我們必須找到將數據點表示為特徵向量（feature vector）的方式。特徵向量是數據的數學表示，由於數據所需的特性的內在形式可能並非是數值，在創建這些向量前，可能需要進行預處理和特徵工程。給定具有N個不同特徵的數據，特徵向量將是維度為N的向量，其中向量的I條目表示數據點對應特徵I的值。因此，每個特徵向量可以看成是R^N中的點。
和其他大多數分類方法不同，kNN屬於惰性學習（lazy learning），這意味著在分類之前沒有顯式的訓練階段。相反，任何概括或抽象數據的嘗試是在分類中做出的。儘管這確實意味著一旦我們有了數據，就可以立刻開始分類，這種算法有一些固有的問題。我們必須能夠將整個訓練集保存在內存中，除非我們對數據集應用了某種降維方法，進行分類可能在算力上非常昂貴，因為算法需要為每次分類解析所有數據點。基於這些原因，一般而言，kNN在並不具備很多特徵的較小的數據集上效果最好。
一旦我們加工好了訓練數據集（表示為一個M x N矩陣，其中M為數據點的數目，而N為特徵數目），我們就可以開始分類了。kNN方法的精髓是，為每個分類查詢：
計算將要分類的項目和訓練集中所有其他項目的距離
選擇k個最接近的數據點（距離最近的k個數據點）
在這些數據點間進行一次“多數投票（majority vote）”——佔統治地位的分類成為最終分類。
在進行分類前，必須做出兩個重要的決定。一個是即將使用的k值；它可能是任意決定的，也可能是通過交叉驗證（cross-validation）找到的最優值。另一個，也是最複雜的決定，是即將使用的距離測度（distance metric）。
距離是一個相當含糊的概念，因此存在很多不同的計算距離的方法。適當的測度總是由數據集和分類任務決定。不過，比較流行的兩個測度是歐幾里得距離（Euclidean distance）和餘弦相似度（Cosine similarity）。
歐幾里得距離大概是你最熟悉的測度；基本上，從要分類的點中減去訓練數據點，得到一個向量，其長度就是歐幾里得距離。
另一個常用的測度是餘弦相似度。餘弦相似度計算兩個向量的方向間的差異。
選擇測度經常很棘手，也許最好的辦法是直接通過交叉驗證決定測度，除非你具有某種先驗洞見，能夠清晰地揭示一種測度比另一種測度更好。例如，對於單詞向量，你可能想要使用餘弦相似度，因為單詞的方向比組成部分值的長度要有意義得多。一般而言，這兩個方法的運行時間差不多，也都不擅長處理高維數據。
進行所有上述步驟，決定測度之後，kNN算法的結果是一個分區R^N的判定邊界。每個分區（在下圖中使用不同顏色表示）表示分類問題中的一個分類。邊界不一定需要由實際的訓練樣本構成——它們其實是通過距離測度和現有訓練點計算出來的。將R^N切分為小塊之後，我們可以計算該區域內的假想數據點最有可能的分類，從而根據分類區域給小塊上色。
這些就是開始實現這一算法需要知道的所有信息了，實現kNN相對而言比較簡單。當然，有很多改善這一基本算法的方式。常見的修正包括加權，以及降低運算量和噪聲的特定預處理方法，比如多種特徵提取和降維算法。此外，kNN也被用於迴歸任務（不過這一用法不那麼常見），用於迴歸任務的kNN的做法和基於平均的分類器非常相似。
閱讀更多 論智 的文章
