一種新型有趣的餐飲體驗已經出現在世界各地的城市中，顧客在一個完全黑暗的餐廳裡接受服務，而服務員在僅憑觸覺和聽覺記憶的路上小心地移動。這些餐廳的魅力在于這樣的信仰：去掉一個人的視覺感官輸入将會增強他的味覺和嗅覺，進而可以使他以一種全新的方式來體驗食物。當發現廚師已經準備好的美味時，他的每一口食物都提供了新奇感。
你能夠想象用餐者是如何體驗看不到的食物嗎？對于第一口，感覺就消失。占主導地位的味道是什麼？食物嘗起來是鹹還是甜？食物的味道類似于以前吃的什麼東西嗎？就個人而言，我用一句稍加修改的諺語來想象這一探索過程：如果該食物聞起來像隻鴨子，并且嘗起來也像隻鴨子，那麼你就很可能在吃鴨子。
這闡述了一個可以用于機器學習的思想—就像另一句有關鳥類的格言：有一樣羽毛的鳥會聚集在一起（即“物以類聚，人以群分”）。換句話說就是：相似的東西很可能具有相似的屬性。利用這個原理，機器學習可以對資料進行分類，将其劃分到同一類别，比如相似或者“最近”的鄰居中。本章将專門讨論使用這種方法進行分類，你将會學到：
定義近鄰分類器的關鍵概念，以及為什麼它們被認為是“懶惰”（lazy）學習器。
通過距離來測量兩個案例相似性的方法。
應用一種流行的名為knn的近鄰分類器。
如果所有這些關于食物的話題讓你感到餓了，那麼随意吃些點心。我們的第一個任務就是通過安排一個持續較長的有關烹饪的讨論來使用knn方法，進而了解knn方法。
用一句話來說，近鄰分類器就是把無标記的案例歸類為與它們最相似的帶有标記的案例所在的類。盡管這個想法很簡單，但是近鄰分類方法是極其強大的，它們已經成功地應用在下列領域中：
計算機視覺應用，包括在靜止圖像和視訊中的光學字元識别和面部識别。
預測一個人是否會喜歡推薦的電影或者音樂。
識别基因資料的模式，或許使用它們可以檢測特定的蛋白質或者疾病。
一般來說，近鄰分類器非常适用于這樣的分類任務，其中的特征和目标類之間的關系是衆多的、複雜的或極難了解的，但是具有相似類的項目又是非常近似的。也就是說，如果一個概念很難定義，但是當你看到它時你知道它是什麼，那麼近鄰分類就可能是合适的方法。另一方面，如果資料是噪聲資料，于是組與組之間沒有明确的界限，那麼近鄰算法可能難以确定類邊界。
用于分類的近鄰方法可以通過k近鄰（k-nearest neighbor, knn）算法舉例說明。雖然這可能是最簡單的機器學習算法之一，但它仍被廣泛使用。
該算法的優缺點如下表所示：
knn算法源于這樣一個事實：它使用關于一個案例的k個近鄰的資訊來分類無标記的例子。字母k是一個可變選項，表示任意數目的近鄰都可以使用。在標明k之後，該算法需要一個已經分成幾個類别的案例組成的訓練資料集，類别由名義變量來标記。然後，對于測試資料集中的每一個無标記的記錄，knn确定訓練資料集中與該記錄相似度“最近”的k條記錄，将無标記的測試例子配置設定到k個近鄰中占比最大的那個類中。
為了說明這個過程，讓我們回顧引言中所描述的黑暗餐廳用餐的經曆。假設在吃一頓神秘的膳食之前，我們已經建立了一個品味資料集，在這個資料集中，記錄了我們對于之前所品嘗過的很多配料的印象。為了簡單起見，我們隻估算了每種配料（ingredient）的兩個特征，第一個特征是配料的脆度（crunchiness），從1～10；第二個特征是配料的甜度（sweetness），從1～10。然後，我們标記配料為3種類型之一：水果ruit）、蔬菜（vegetable）或者蛋白質（protein）。該資料集的前幾行可能具有如下所示的結構：
knn算法将特征處理為一個多元特征空間内的坐标。由于我們的資料集隻包含了兩個特征，是以特征空間是二維的。我們可以繪制二維資料散點圖，次元x表示配料的甜度，次元y表示配料的脆度。在品味資料集中增加更多的配料後，散點圖看起來可能類似于下圖。
你注意到上圖了嗎？相似類型的食物趨向于聚集得更近。如下圖所示，vegetable（蔬菜）往往是脆而不甜的；fruit（水果）往往是甜的，有可能是脆的，也有可能是不脆的；而protein（蛋白質）往往是既不脆也不甜的。
假設在建立此資料集後，我們決定用它來解決一個古老的問題：蕃茄（tomato）是水果（fruit），還是蔬菜（vegetable）？我們可以使用一種近鄰方法來确定哪類更适合蕃茄（tomato），如下圖所示。
1.通過距離度量相似性
定位tomato（蕃茄）的近鄰需要一個距離函數或者一個用來度量兩個案例之間相似性的公式。
計算距離有許多種不同的方法。傳統上，knn算法采用歐式距離（euclidean distance），如果可能，這種距離可以通過用尺子連接配接兩個點來測量，在上圖中，我們通過虛線将蕃茄（tomato）與它的鄰居連接配接在一起。
歐式距離通過“直線距離”（as the crow flies）來度量，即最短的直接路線。另一種常見的距離度量是曼哈頓距離（manhattan distance），該距離基于一個行人在城市街區步行所采取的路線。如果你有興趣了解更多關于距離度量的方法，可以使用?dist指令，閱讀r中的距離函數文檔（該文檔本身就是一個很有用的工具）。
歐式距離通過如下的公式定義，其中p和q是需要比較的案例，它們都有n個特征，項p1代表案例p的第一個特征的值，而q1代表案例q的第一個特征的值：
距離公式涉及比較每個特征的值。例如，為了計算蕃茄（tomato）（sweetness（甜度）= 6, crunchiness（脆度）=4）和綠豆（green bean）（sweetness（甜度）=3, crunchiness（脆度）=7）之間的距離，可以使用如下公式：
與此類似，可以計算蕃茄（tomato）與它的幾個近鄰之間的距離，如下表所示。
為了将蕃茄（tomato）歸類為蔬菜（vegetable）、蛋白質（protein），或者水果（fruit），我們先從把蕃茄（tomato）歸類到離它最近的一種食物所在的類型開始。因為這裡k=1，是以這稱為1nn分類。橙子（orange）是蕃茄（tomato）的近鄰，距離是1.4。因為橙子（orange）是一種水果，是以1nn算法把蕃茄（tomato）歸類為一種水果。
如果我們使用k=3的knn算法，那麼它會在3個近鄰即橙子（orange）、葡萄（grape）和堅果（nuts）之間進行投票表決。因為這3個鄰居的大多數歸類為水果（2/3的票數），是以蕃茄（tomato）再次歸類為水果。
2.選擇一個合适的k
确定用于knn算法的鄰居數量将決定把模型推廣到未來資料時模型的好壞。過度拟合和低度拟合訓練資料之間的平衡問題稱為偏差-方差權衡（bias-variance tradeoff）。選擇一個大的k會減少噪聲資料對模型的影響或者減少噪聲導緻的模型波動，但是它會使分類器産生偏差，比如，它有忽視不易察覺但卻很重要模式的風險。
假設我們采取一個極端的情況，即設定一個非常大的k，它等于訓練資料中所有觀測值的數量。由于每一個訓練案例都會在最後的投票表決中出現，是以最常見的訓練類總會獲得大多數的票。是以，模型總會預測為數量占大多數的那個訓練類，而不管哪個鄰居是最近的。
在相反的極端情況下，使用一個單一的近鄰會使得噪聲資料或者異常值過度影響案例的分類。例如，假設一些訓練案例被意外地貼錯了标簽，而另一些無标記的案例恰好是最接近于被錯誤标記的訓練案例，那麼即使其他的9個近鄰有不同的投票，它也會被預測到錯誤的類中。
顯然，最好的k值應該取這兩個極端值之間的某個值。
下圖更一般地說明了決策邊界（由虛線表示）如何受到較大的或者較小的k值的影響。較小的k值會給出更複雜的決策邊界，它可以更精細地拟合訓練資料。但問題是，我們并不知道是直線邊界還是曲線邊界能更好地代表我們将要學習的正确概念。
在實際中，k的選取取決于要學習概念的難度和訓練資料中記錄的數量。一種常見的做法就是從k等于訓練集中案例數量的平方根開始。在我們之前研究的食物分類器中，我們可以設定k=4，因為訓練資料中有15個案例，15的平方根是3.87。
然而，這樣的規則可能并不總是産生一個最好的k值。另一種方法是基于各種測試資料集來測試多個k值，并選擇一個可以提供最好分類性能的k值。也就是說，除非資料的噪聲非常大，否則大的訓練資料集可以使k值的選擇并不那麼重要。這是因為即使是微小的概念，也将有一個足夠大的案例池來進行投票，以便選舉出近鄰。
一個不太常見但很有趣的解決這個問題的方法是選擇一個較大的k值，但是同時應用一個權重投票（weighted voting）過程，在這個過程中，認為較近鄰的投票比遠鄰的投票更有權威。許多knn的實作提供這樣的選擇。
3.準備knn算法使用的資料
在應用knn算法之前，通常将特征轉換為一個标準的範圍内。這個步驟的合理性在于，距離公式高度依賴于特征是如何被度量的。特别地，如果某個特征具有比其他特征更大範圍的值，那麼距離的度量就會強烈地被這個具有較大範圍的特征所支配。而對于食物品味案例，這并不算是一個問題，因為甜度（sweetness）和脆度（crunchiness）的度量都是在1～10的範圍内。
然而，假設我們在資料集中增加一個額外的特征來表示食物的辛辣度（spiciness），并使用史高維爾名額來測量它。如果你不熟悉這個名額，它是辛辣熱量的一種标準化度量，範圍從0（完全不辣）到超過100萬（最火辣的辣椒）。因為辛辣食物和非辛辣食物之間的差異可能會超過100萬，而甜食和非甜食或者脆食和非脆食之間的差異至多是10，是以尺度的差異使得辛辣對于距離函數的影響水準遠遠超過其他兩個因素。如果沒有調整我們的資料，我們可能會發現距離度量隻能通過食物的辛辣度來加以差別，而脆度和甜度的影響将會由于辛辣度對于距離的貢獻而顯得相形見绌。
解決的方法便是通過收縮或者放大它們的範圍來重新調整特征，使得每個特征對距離公式的貢獻相對平均。例如，如果甜度和脆度都在範圍1～10，那麼我們也希望辛辣度在範圍1～10，有一些方法可以完成這樣的尺度調整。
對knn算法的特征進行重新調整的傳統方法是min-max标準化（min-max normali-zation），該過程變換特征，使它的所有值都落在0～1範圍内。将特征進行min-max标準化的公式如下所示：
本質上，該公式就是特征x的每一個值減去它的最小值再除以特征x的極差。
min-max标準化的特征值可以這樣解釋：按0%～100%來說，在原始最小值和原始最大值的範圍内，原始值到原始最小值的距離有多遠。
另一種常見的變換稱為z-分數标準化（z-score standardization）。下面的公式是減去特征x的均值後，再除以x的标準差：
這個公式是基于第2章所介紹的正态分布的性質（即根據每一個特征的值落在均值上下的标準差的數量）來重新調整每一個特征的值，所得到的值稱為z分數（z-score）。z分數落在一個無界的負數和正數構成的範圍内，它們與min-max标準化後的值不同，沒有預定義的最小值和最大值。
用于knn訓練資料集的同一個重新調整方法必須也應用于算法之後将要分類的樣本。對于min-max标準化，這可能會導緻一種棘手的情形，即未來樣本的最小值或者最大值可能在訓練資料中觀測值的範圍之外。如果你事先知道合理的最小值或者最大值，你可以使用這些常量，而不是觀測值。另外，你也可以使用z分數标準化，基于這樣的假設：作為訓練樣本，未來樣本具有相似的均值和标準差。
歐式距離公式并不是為名義資料定義的。是以，為了計算名義特征之間的距離，需要将它們轉化成數值型格式。一種典型的解決方案就是利用啞變量編碼（dummy coding），其中1表示一個類别，0表示其他類别。例如，可以如下建構性别變量的啞變量編碼：
注意對含有兩個可能取值的（二進制）性别變量進行啞變量編碼産生一個新的名為male的特征，而為female建構一個單獨的特征是沒有必要的，因為兩種性别是互斥的，知道其中一個就足夠了。
這種方法實際上可以更廣泛地應用。一個具有n個類别的名義特征可以通過對特征的（n－1）個水準建立二進制訓示變量來進行啞變量編碼。例如，為一個具有3個類别的溫度變量（比如，hot、medium或者cold）進行啞變量編碼，可以用（3－1）＝2個特征來進行設定，如下式所示：
隻要知道hot和medium的值同時為0就足以說明溫度是cold，是以我們不需要為cold類設定第3個特征。
啞變量編碼的一個友善之處就在于啞變量編碼的特征之間的距離總是為1或者0，是以，與min-max标準化的數值資料一樣，這些值落在了一個相同的标度内，不需要進行額外的變換。
如果名義特征是有序的（可以将溫度變量作為例子），那麼一種啞變量編碼的替代方法就是給類别編号并且應用min-max标準化。例如，cold、warm和hot可以編号為1、2和3，min-max标準化後為0、0.5和1。使用該方法要注意的是，隻有當類别之間的步長相等時，才能應用該方法。例如，對于收入分類，盡管poor、middle class和wealthy是有序的，但是poor和middle class之間的差異與middle class和wealthy之間的差異可能是不同的。由于組别之間的步長不相等，是以啞變量編碼是一種更保險的方法。
基于近鄰方法的分類算法被認為是懶惰學習（lazy learning）算法，因為從技術上來說，沒有抽象化的步驟。抽象過程和一般化過程都被跳過了，這就破壞了第1章給出的學習的定義。
基于學習這個概念的嚴格定義，懶惰學習并不是真正在學習什麼。相反，它僅僅是一字不差地存儲訓練資料，這樣訓練階段并不是實際訓練什麼，于是就進行得很快。當然，不利因素就是進行預測的過程相對于訓練往往會變得相對較慢。由于高度依賴于訓練執行個體而不是一個抽象的模型，是以懶惰學習又稱為基于執行個體的學習（instance-based learning）或者機械學習（rote learning）。
由于基于執行個體的學習算法并不會建立一個模型，是以該方法歸類為非參數（non-parametric）學習方法，即沒有需要學習的資料參數。因為沒有産生關于資料的理論，是以非參數方法限制了我們了解分類器如何使用資料的能力。另一方面，它允許學習算法發現資料中的自然模式，而不是試圖将資料拟合為一個預先設定的可能的偏差函數形式。
盡管knn分類器可能被認為是懶惰的，但它們還是很強大的，正如你不久就會看到的，近鄰學習的簡單原則可以用于癌症的自動化篩查過程。