3.7　k-近鄰——一種惰性學(xué)習(xí)算法

本章將要討論的最后一個(gè)監(jiān)督學(xué)習(xí)算法是k-近鄰（KNN）分類器，它特別有趣，因?yàn)樗c迄今為止我們所討論過的其他學(xué)習(xí)算法有本質(zhì)的不同。

KNN是惰性學(xué)習(xí)的典型例子。所謂的惰性，并不是說它看上去很簡單，而在于它不是從訓(xùn)練數(shù)據(jù)中學(xué)習(xí)判別函數(shù)，而是靠記憶訓(xùn)練過的數(shù)據(jù)集來完成任務(wù)。

參數(shù)模型與非參數(shù)模型

機(jī)器學(xué)習(xí)算法可以分為參數(shù)模型與非參數(shù)模型。參數(shù)模型指我們從訓(xùn)練數(shù)據(jù)集估計(jì)參數(shù)來學(xué)習(xí)，一個(gè)能分類新數(shù)據(jù)點(diǎn)的函數(shù)，而不再需要原始訓(xùn)練數(shù)據(jù)集。參數(shù)模型的典型例子是感知器、邏輯回歸和線性支持向量機(jī)。相比之下，非參數(shù)模型不能用一組固定的參數(shù)來描述，參數(shù)的個(gè)數(shù)隨著訓(xùn)練數(shù)據(jù)的增加而增長。前面已經(jīng)看到兩個(gè)非參數(shù)模型的例子，決策樹分類器/隨機(jī)森林和核支持向量機(jī)。

KNN算法是基于實(shí)例的學(xué)習(xí)，屬于非參數(shù)模型。基于實(shí)例學(xué)習(xí)的模型以記憶訓(xùn)練數(shù)據(jù)集為特征，惰性學(xué)習(xí)是基于實(shí)例學(xué)習(xí)的一種特殊情況，這與它在學(xué)習(xí)過程中付出零代價(jià)有關(guān)。

KNN算法本身相當(dāng)簡單，可以總結(jié)為以下幾個(gè)步驟；

• 選擇k個(gè)數(shù)和一個(gè)距離度量。
• 找到要分類樣本的k-近鄰。
• 以多數(shù)票機(jī)制確定分類標(biāo)簽。

圖3-24顯示了在五個(gè)近鄰里，如何基于多數(shù)票機(jī)制為新數(shù)據(jù)點(diǎn)（？）分配三角形標(biāo)簽。

基于所選擇的距離度量，KNN算法從訓(xùn)練數(shù)據(jù)集中找到最接近要分類新數(shù)據(jù)點(diǎn)的k個(gè)樣本。新數(shù)據(jù)點(diǎn)的分類標(biāo)簽由最靠近該點(diǎn)的k個(gè)數(shù)據(jù)點(diǎn)的多數(shù)票決定。

基于記憶方法的主要優(yōu)點(diǎn)是當(dāng)新的訓(xùn)練數(shù)據(jù)出現(xiàn)時(shí)，分類器可以立即適應(yīng)。缺點(diǎn)是新樣本分類的計(jì)算復(fù)雜度與最壞情況下訓(xùn)練數(shù)集的樣本數(shù)呈線性關(guān)系，除非數(shù)據(jù)集只有很少的維度（特征），而且算法實(shí)現(xiàn)采用有效的數(shù)據(jù)結(jié)構(gòu)（如KD樹）[2]。此外，由于沒有訓(xùn)練步驟，因此不能丟棄訓(xùn)練樣本。因此，如果要處理大型數(shù)據(jù)集，存儲空間將面臨挑戰(zhàn)。

執(zhí)行下面的代碼可以用scikit-learn的歐氏距離度量實(shí)現(xiàn)KNN模型：

該數(shù)據(jù)集用KNN模型指定五個(gè)鄰居，得到圖3-25所示的相對平滑的決策邊界。

仲裁

在爭執(zhí)不下的情況下，用scikit-learn實(shí)現(xiàn)的KNN算法將更喜歡近距離樣本的鄰居。如果鄰居有相似的距離，該算法將在訓(xùn)練數(shù)據(jù)集中選擇最先出現(xiàn)的分類標(biāo)簽。

正確（right）選擇k值對在過擬合與欠擬合之間找到恰當(dāng)?shù)钠胶庵陵P(guān)重要。我們還必須確保選擇的距離度量適合數(shù)據(jù)集中的特征。通常用簡單的歐氏距離來度量，例如，鳶尾花數(shù)據(jù)集中的花樣本，其特征以厘米為單位度量。然而，如果用歐氏距離度量，那么對數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化也很重要，確保每個(gè)特征都能對距離起著同樣的作用。在前面代碼中使用的minkowski距離只是歐氏距離和曼哈頓（Manhattan）距離的推廣，可以表達(dá)如下：

如果參數(shù)p=2，就是歐氏距離，如果p=1，就是曼哈頓距離。在scikit-learn中還有許多其他距離度量，可以提供給metric參數(shù)。可以在http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.DistanceMetric.html找到。

維數(shù)詛咒

由于維數(shù)詛咒，KNN易于過擬合，了解這一點(diǎn)非常重要。當(dāng)固定規(guī)模的訓(xùn)練數(shù)據(jù)集的維數(shù)越來越大時(shí)，特征空間就變得越來越稀疏，這種現(xiàn)象被稱為維數(shù)詛咒。直觀地說，可以認(rèn)為即使是最近的鄰居在高維空間的距離也很遠(yuǎn)，以至于無法合適地估計(jì)。

在3.3節(jié)討論了正則化的概念，并以此作為避免過擬合的一種方法。然而，在不適用正則化的模型（如決策樹和KNN）中，可以利用特征選擇和降維技術(shù)避免維數(shù)詛咒。下一章將對此進(jìn)行更詳細(xì)的討論。