“k 近法”在算法層面理解容易，可以從使用“k 近鄰法”處理分類問題入手，解釋機器學習中的各種概念和一般流程。
k 近鄰法的基本思想
“k 近鄰法” 幾乎是所有機器學習算法中最簡單的算法，它用于分類的核心思想就是“物以類聚，人以群分”，即未標記樣本的類別由距離其最近的 個鄰居投票來決定。
（圖片來自周志華《機器學習》第 10 章第 1 節(jié)）
有監(jiān)督學習、分類學習、回歸
有監(jiān)督學習的數(shù)據(jù)包含了“特征”和“標簽”。根據(jù)這些數(shù)據(jù)對新的數(shù)據(jù)的分類進行預測或預測，如果待預測的目標變量是離散值，那么這一類問題稱之為“分類問題”；如果待預測的目標變量是連續(xù)值，那么這一類問題稱之為“回歸”問題。
評估算法時不能使用在訓練過程中出現(xiàn)過的數(shù)據(jù)
這一點很像我們以前學習的時候，常常會買一本練習冊做題，如果這本練習冊沒有參考答案，你就不知道自己做對與否。而真正檢驗你學習水平的大型考試，例如期中考試、期末考試、中考、高考都是重新出題，如果使用以前出現(xiàn)過的題目，則不能檢驗你學習的真實水平，因為你有可能是記住了問題的解法，而沒有理解它。
這就是分離訓練數(shù)據(jù)集和測試數(shù)據(jù)集的必要性。因此采集到的所有帶標簽的樣本，應該分離一部分用于測試。那么評估算法應該采用什么指標呢？
評估算法好壞的指標
一般地，“ 近鄰法”用于分類問題使用“準確率”作為指標。但是在數(shù)據(jù)分布不平衡的時候，就不能使用準確率了，而應該使用精準率、召回率、混淆矩陣等，甚至應該看看 auc。
超參數(shù)
超參數(shù)是算法執(zhí)行之前認為定義的?！?img class="math-inline" src="https://math.jianshu.com/math?formula=k" alt="k" mathimg="1"> 近鄰法” 中的 就是一個超參數(shù)，它決定了模型的復雜度。
“ 近鄰法” 還有其它超參數(shù)，使用的距離的定義是歐氏距離還是閔式距離，閔式距離的參數(shù)
是多少，投票的時候是“平票”還是“加權(quán)投票”。
模型的復雜度、過擬合、欠擬合
越小，模型就越復雜。極端情況下
，新來的預測數(shù)據(jù)的類別取決于訓練樣本中離他最近的那個樣本的類別，如果這個樣本恰好是標記錯誤的樣本，預測就可能發(fā)生錯誤，因為它看不到更多數(shù)據(jù)，就有可能過擬合，學習到的不是樣本數(shù)據(jù)的一般規(guī)律。
越大，模型就越簡單。極端情況下
等于所有訓練樣本的個數(shù)，此時每新來一個數(shù)據(jù)做預測的時候，就直接把訓練樣本中出現(xiàn)最多的類別數(shù)返回就行了，這樣的模型過于簡單，以致于失去了算法真正的意義，所有的預測數(shù)據(jù)都返回同一個值，對數(shù)據(jù)不能很好的預測，這是欠擬合。
網(wǎng)格搜索與交叉驗證
網(wǎng)格搜索其實就是暴力搜索，把我們認為可能合理的超參數(shù)和超參數(shù)的組合輸入算法。而評價一組超參數(shù)的好壞一定不能使用測試數(shù)據(jù)集，一般的做法是從訓練數(shù)據(jù)集中再分離出一部分數(shù)據(jù)用于驗證超參數(shù)的好壞，并且這種驗證超參數(shù)好壞的做法要使用不同的訓練數(shù)據(jù)集的子集重復多次，這就是交叉驗證。
交叉驗證用于選擇超參數(shù)，由于分離數(shù)據(jù)集其實帶有一定的隨機性，把所有的數(shù)據(jù)集都看一遍，多次取平均的做法，比起一次性隨機地使用訓練數(shù)據(jù)集的一部分子集作為測試數(shù)據(jù)集要靠譜。
網(wǎng)格搜索中就用到了交叉驗證，通過框架被封裝了起來，不用我們手動實現(xiàn)。
數(shù)據(jù)標準化
數(shù)據(jù)標準化是我剛開始接觸學習機器學習算法的時候經(jīng)常被忽略的。由于 k 近鄰法使用距離作為度量，數(shù)據(jù)在量綱上的統(tǒng)一是十分重要的，數(shù)據(jù)標準化則可以避免計算出來的距離被量綱大的特征所主導。
后面我們可以看到數(shù)據(jù)標準化在梯度下降中也發(fā)揮很大的作用，還有 SVM、K-means 這些距離度量的算法，都要求我們對數(shù)據(jù)進行標準化。
例如：《機器學習實戰(zhàn)》提供的例子。
在數(shù)據(jù)標準化這件事上，還要注意：訓練數(shù)據(jù)集和測試數(shù)據(jù)集一定都使用相同的標準化方式，即訓練數(shù)據(jù)集的標準化方式，請看下面的公式。
測試數(shù)據(jù)集在標準化的時候，一定也要使用“訓練數(shù)據(jù)集”的平均值和“訓練數(shù)據(jù)集”的標準差，而不能使用測試數(shù)據(jù)集的。
原因其實很簡單：
1、標準化其實可以視為算法的一部分，既然數(shù)據(jù)集都減去了一個數(shù)，然后除以一個數(shù)，這兩個數(shù)對于所有的數(shù)據(jù)來說，就要一視同仁；
2、訓練數(shù)據(jù)集其實很少，在預測新樣本的時候，新樣本就更少得可憐，如果新樣本就一個數(shù)據(jù)，它的均值就是它自己，標準差是 0 ，這根本就不合理。
k 近鄰算法的三要素
1、超參數(shù)： ；
2、距離的定義（例如：歐氏距離）；
3、決策的規(guī)則（例如：投票表決，或者加權(quán)投票）。
手寫 k 近鄰法的核心代碼
Python 代碼：
distances = [np.linalg.norm(point - X) for point in X_train]
print("打印每個點距離待測點的距離：")
for index, distance in enumerate(distances):
print("[{}] {}".format(index, np.round(distance, 2)))
sorted_index = np.argsort(distances)
print(y_train[sorted_index])
k = 6
topK = y_train[sorted_index][:k]
print(topK)
from collections import Counter
votes = Counter(topK)
mc = votes.most_common(n=1)
print(mc)
print("根據(jù)投票得出的點 X 的標簽為：", mc[0][0])
通過 k 近鄰法了解機器學習項目的執(zhí)行流程
使用 iris 鳶尾花數(shù)據(jù)集。
1、分割訓練數(shù)據(jù)集和測試數(shù)據(jù)集；
2、只用訓練數(shù)據(jù)集 fit 得到均值和標準差；
3、分別對訓練數(shù)據(jù)集和測試數(shù)據(jù)集進行 transform，注意：這里只需要傳入 X_train 和 y_train 就可以了，不用傳入標簽；
4、使用 k 近鄰法進行評分，注意：傳入的特征矩陣一定要經(jīng)過數(shù)據(jù)標準化。
k? 近鄰法的特點
在整理這部分內(nèi)容的時候，發(fā)現(xiàn)優(yōu)點和缺點其實要在一定的前提下討論，所以就干脆放在一起，說一說 k 近鄰法的特點。
k 近鄰法是一個懶惰學習的算法，沒有顯式的學習過程，即沒有它沒有訓練的步驟，是一個基于記憶的學習算法。
k 近鄰法是一種在線學習技術(shù)，新數(shù)據(jù)可以直接加入數(shù)據(jù)集而不必進行重新訓練，但與此同時在線學習計算量大，對內(nèi)存的需求也較大?；镜?k 近鄰法每預測一個“點”的分類都會重新進行一次全局運算，對于樣本容量大的數(shù)據(jù)集計算量比較大。k 近鄰法的優(yōu)化實現(xiàn)：kd 樹，即給訓練數(shù)據(jù)建立樹結(jié)構(gòu)一樣的索引，期望快速找到 個鄰居，以防止線性掃描。
“多數(shù)表決”規(guī)則等價于“經(jīng)驗風險最小化”，即算法在訓練數(shù)據(jù)集上“風險”最小。
對異常值和噪聲有較高的容忍度，在算距離的時候，異常值和噪聲離待預測的點的距離會比較遠，且個數(shù)較少，就不會參與最終結(jié)果的投票。
近鄰算法天生就支持多分類，類似還有決策樹、樸素貝葉斯分類，它們區(qū)別于感知機、邏輯回歸、SVM 這類原生只用于二分類問題的算法。
維度災難
在高維空間中計算距離的時候，就會變得非常遠。
樣本不平衡時，預測偏差會比較大。
值大小的選擇得依靠經(jīng)驗或者交叉驗證得到，不能自己拍腦門隨便指定一個。
增加鄰居的權(quán)重，距離越近，權(quán)重越高，參數(shù)：weights。
當數(shù)據(jù)采樣不均勻的時候，使用一定半徑內(nèi)的點，該算法可以取得更好的性能，可以參考 from sklearn.neighbors import RadiusNeighborsClassifier。
k 近鄰法還可以用于回歸，找最近的鄰居，然后計算它們的平均值就可以了。
參考資料
[1] 李航. 統(tǒng)計學習方法（第 2 版，第 3 章“ 近鄰法”）. 北京：清華大學出版社，2019.
說明：介紹了 kd 樹，并給出了例子。
[2] 周志華. 機器學習（第 10 章第 1 節(jié)）. 北京：清華大學出版社.
說明：只簡單介紹了思想，并給出了 k 近鄰算法雖簡單但預測效果在一定情況下比最優(yōu)貝葉斯估計強的結(jié)論（我的這個概括待推敲），沒有《統(tǒng)計學習方法》介紹詳細。
[3] [美] Peter Harrington 著，李銳，李鵬，曲亞東 等 譯.機器學習實戰(zhàn)（第 2 章）.北京：人民郵電出版社.
說明：想吐槽一下這本書在這一章節(jié)給出的示例代碼，很簡單的一個算法，它給出的代碼變得很復雜，其實并不利于理解 k 近鄰算法的基本思想。
（本節(jié)完）
以下為草稿，我自己留著備用，讀者可以忽略，歡迎大家批評指正。
想說一說“k 近鄰算法”在機器學習中的地位
“k 近鄰算法” 可以說是最容易理解的機器學習算法，所以可以用“k 近鄰算法”來作為入門機器學習算法的基本流程的最好材料，因為我們在理解算法上不須要花太多時間。
下面簡單說說，“k 近鄰算法” 給我們帶來了什么。
- 超參數(shù)：k 就是一個超參數(shù)，這是我們得根據(jù)經(jīng)驗，在算法運行之前指定的；
- 數(shù)據(jù)集分離：我們不能使用所有的樣本訓練數(shù)據(jù)，我們還要評估算法的性能，即使是同一個算法，不同的超參數(shù)還須要評估好壞，因此，必須從數(shù)據(jù)集中分離出一部分數(shù)據(jù)，進行算法好壞，超參數(shù)選擇的驗證；
- 評估算法好壞的準則：k 近鄰算法用于分類問題，一個最容易理解的評價指標就是準確率（或者錯誤率，因為錯誤率=1-準確率）；
- 交叉驗證：交叉驗證用于選擇超參數(shù)，比起簡單地那一部分數(shù)據(jù)作為測試數(shù)據(jù)集要靠譜，因為分離數(shù)據(jù)集帶有一定隨機性；
- 網(wǎng)格搜索：其實就是暴力搜索，把我們認為可能合理的超參數(shù)和超參數(shù)的組合輸入算法，而在其中評估算法好壞，超參數(shù)的選擇也用到了交叉驗證的過程；
- 數(shù)據(jù)標準化：這一步是一開始學習機器學習算法的時候經(jīng)常被忽略的，后面我們可以看到數(shù)據(jù)標準化在梯度下降中也發(fā)揮很大的作用；
- 模型復雜度：理解下面這句話
的值越小，模型越復雜，
- 決策邊界：這是分類問題的一個重要且簡單的概念。
算法執(zhí)行的步驟
1、選擇 和距離的度量；
2、計算待標記的數(shù)據(jù)樣本和數(shù)據(jù)集中每個樣本的距離，取距離最近的 個樣本。待標記的數(shù)據(jù)樣本所屬的類別，就由這
個距離最近的樣本投票產(chǎn)生。
k 近鄰算法的訓練過程，即是利用訓練數(shù)據(jù)集，對特征向量空間進行劃分
說明：從這張圖中，你可以看到?jīng)Q策邊界。
-
- “多數(shù)表決”規(guī)則等價于“經(jīng)驗風險最小化”（我們的算法在訓練數(shù)據(jù)集上“風險”最?。?；
-
近鄰算法的應用領(lǐng)域
文本分類、模式識別、聚類分析，多分類領(lǐng)域。
近鄰算法的優(yōu)點
-
-
- 準確性高：對異常值和噪聲有較高的容忍度；
-
近鄰算法的缺點
基本的
維度災難：在高維空間中計算距離的時候，就會變得非常遠；
樣本不平衡時，預測偏差比較大，例如：某一類的樣本比較少，而其它類樣本比較多；
從 近鄰算法說開
- 增加鄰居的權(quán)重，距離越近，權(quán)重越高，參數(shù)：weights；
維基百科最近鄰居法詞條中是這樣介紹的：
無論是分類還是回歸，衡量鄰居的權(quán)重都非常有用，使較近鄰居的權(quán)重比較遠鄰居的權(quán)重大。例如，一種常見的加權(quán)方案是給每個鄰居權(quán)重賦值為
，其中
是到鄰居的距離。
使用一定半徑內(nèi)的點，當數(shù)據(jù)采樣不均勻的時候，該算法可以取得更好的性能：
from sklearn.neighbors import RadiusNeighborsClassifier；
