簡單地說，k近鄰算法採用測量不同特徵值之間的距離方法進行分類。
k-近鄰算法
優點：精度高、對異常值不敏感、無數據輸入假定。 缺點：計算複雜度高、空間複雜度高。 適用數據範圍：數值型和標稱型。
本書講解的第一個機器學習算法是k-近鄰算法（kNN)，它的工作原理是：存在一個樣本數據集合，也稱作訓練樣本集，並且樣本集中每個數據都存在標籤，即我們知道樣本集中每一數據與所屬分類的對應關係。輸入沒有標籤的新數據後，將新數據的每個特徵與樣本集中數據對應的特徵進行比較，然後算法提取樣本集中特徵最相似數據（最近鄰）的分類標籤。一般來說，我們只選擇樣本數據集中前k個最相似的數據，這就是k-近鄰算法中k的出處，通常k是不大於20的整數。最後，選擇k個最相似數據中出現次數最多的分類，作為新數據的分類。
現在我們回到前面電影分類的例子，使用k近鄰算法分類愛情片和動作片。有人曾經統計過很多電影的打鬥鏡頭和接吻鏡頭，圖2-1顯示了6部電影的打鬥和接吻鏡頭數。假如有一部未看過的電影，如何確定它是愛情片還是動作片呢？我們可以使用kNN來解決這個問題。
圖2-1 使用打鬥和接吻鏡頭數分類電影
首先我們需要知道這個未知電影存在多少個打鬥鏡頭和接吻鏡頭，圖2-1中問號位置是該未知電影出現的鏡頭數圖形化展示，具體數字參見表2-1。
表2-1 每部電影的打鬥鏡頭數、接吻鏡頭數以及電影評估類型
電影名稱 打鬥鏡頭 接吻鏡頭 電影類型 California Man 3 104 愛情片 He』s Not Really into Dudes 2 100 愛情片 Beautiful Woman 1 81 愛情片 Kevin Longblade 101 10 動作片 Robo Slayer 3000 99 5 動作片 Amped ll 98 2 動作片 ? 18 90 未知即使不知道未知電影屬於哪種類型，我們也可以通過某種方法計算出來。首先計算未知電影與樣本集中其他電影的距離，如表2-2所示。此處暫時不要關心如何計算得到這些距離值，使用Python實現電影分類應用時，會提供具體的計算方法。
表2-2 已知電影與未知電影的距離
電影名稱 與未知電影的距離 California Man 20.5 He』s Not Really into Dudes 18.7 Beautiful Woman 19.2 Kevin Longblade 115.3 Robo Slayer 3000 117.4 Amped ll 118.9現在我們得到了樣本集中所有電影與未知電影的距離，按照距離遞增排序，可以找到k個距離最近的電影。假定k=3，則三個最靠近的電影依次是He』s Not Really into Dudes、Beautiful Woman和California Man。k近鄰算法按照距離最近的三部電影的類型，決定未知電影的類型，而這三部電影全是愛情片，因此我們判定未知電影是愛情片。
本章主要講解如何在實際環境中應用k近鄰算法，同時涉及如何使用Python工具和相關的機器學習術語。按照1.5節開發機器學習應用的通用步驟，我們使用Python語言開發k近鄰算法的簡單應用，以檢驗算法使用的正確性。
k近鄰算法的一般流程
- 收集數據：可以使用任何方法。
- 準備數據：距離計算所需要的數值，最好是結構化的數據格式。
- 分析數據：可以使用任何方法。
- 訓練算法：此步驟不適用於k近鄰算法。
- 測試算法：計算錯誤率。
- 使用算法：首先需要輸入樣本數據和結構化的輸出結果，然後運行k近鄰算法判定輸入數據分別屬於哪個分類，最後應用對計算出的分類執行後續的處理。
2.1.1 準備：使用Python導入數據
首先，創建名為kNN.py的Python模塊，本章使用的所有代碼都在這個文件中。讀者可以按照自己的習慣學習代碼，既可以按照本書學習的進度，在自己創建的Python文件中編寫代碼，也可以直接從本書的源代碼中複製kNN.py文件。我推薦讀者從頭開始創建模塊，按照學習的進度編寫代碼。
無論大家採用何種方法，我們現在已經有了kNN.py文件。在構造完整的k近鄰算法之前，我們還需要編寫一些基本的通用函數，在kNN.py文件中增加下面的代碼：
from numpy import *
import operator
def createDataSet:
group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
labels = [\'A\',\'A\',\'B\',\'B\']
return group, labels
在上面的代碼中，我們導入了兩個模塊：第一個是科學計算包NumPy；第二個是運算符模塊，k近鄰算法執行排序操作時將使用這個模塊提供的函數，後面我們將進一步介紹。
為了方便使用createDataSet函數，它創建數據集和標籤，如圖2-1所示。然後依次執行以下步驟：保存kNN.py文件，改變當前路徑到存儲kNN.py文件的位置，打開Python開發環境。無論是Linux、Mac OS還是Windows都需要打開終端，在命令提示符下完成上述操作。只要我們按照默認配置安裝Python，在Linux/Mac OS終端內都可以直接輸入python，而在Windows命令提示符下需要輸入c:Python2.6python.exe，進入Python交互式開發環境。
進入Python開發環境之後，輸入下列命令導入上面編輯的程序模塊：
>>> import kNN
上述命令導入kNN模塊。為了確保輸入相同的數據集，kNN模塊中定義了函數createDataSet，在Python命令提示符下輸入下屬命令：
>>> group,labels = kNN.createDataSet
上述命令創建了變量group和labels，在Python命令提示符下輸入下列命令，輸入變量的名字以檢驗是否正確地定義變量：
>>> group
array([[ 1. , 1.1],
[ 1. , 1. ],
[ 0. , 0. ],
[ 0. , 0.1]])
>>> labels
[\'A\', \'A\', \'B\', \'B\']
這裡有4組數據，每組數據有兩個我們已知的屬性或者特徵值。上面的group矩陣每行包含一個不同的數據，我們可以把它想像為某個日誌文件中不同的測量點或者入口。由於人類大腦的限制，我們通常只能可視化處理三維以下的事務。因此為了簡單地實現數據可視化，對於每個數據點我們通常只使用兩個特徵。
向量labels包含了每個數據點的標籤信息，labels包含的元素個數等於group矩陣行數。這裡我們將數據點(1, 1.1)定義為類A，數據點(0, 0.1)定義為類B。為了說明方便，例子中的數值是任意選擇的，並沒有給出軸標籤，圖2-2是帶有類標籤信息的四個數據點。
圖2-2 k近鄰算法：帶有4個數據點的簡單例子
現在我們已經知道Python如何解析數據，如何加載數據，以及kNN算法的工作原理，接下來我們將使用這些方法完成分類任務。
2.1.2 實施kNN分類算法
本節使用程序清單2-1的函數運行kNN算法，為每組數據分類。這裡首先給出k近鄰算法的偽代碼和實際的Python代碼，然後詳細地解釋每行代碼的含義。該函數的功能是使用k近鄰算法將每組數據劃分到某個類中，其偽代碼如下：
對未知類別屬性的數據集中的每個點依次執行以下操作：
1. 計算已知類別數據集中的點與當前點之間的距離；
2. 按照距離遞增次序排序；
3. 選取與當前點距離最小的k個點；
4. 確定前k個點所在類別的出現頻率；
5. 返回前k個點出現頻率最高的類別作為當前點的預測分類。
Python函數classify0如程序清單2-1所示。
程序清單2-1 k近鄰算法
def classify0(inX, dataSet, labels, k):
dataSetSize = dataSet.shape[0]
#❶（以下三行）距離計算
diffMat = tile(inX, (dataSetSize,1)) - dataSet
sqDiffMat = diffMat**2
sqDistances = sqDiffMat.sum(axis=1)
distances = sqDistances**0.5
sortedDistIndicies = distances.argsort
classCount={}
#❷ （以下兩行）選擇距離最小的k個點
for i in range(k):
voteIlabel = labels[sortedDistIndicies[i]]
classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
sortedClassCount = sorted(classCount.iteritems,
#❸ 排序
key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
classify0函數有4個輸入參數：用於分類的輸入向量是inX，輸入的訓練樣本集為dataSet，標籤向量為labels，最後的參數k表示用於選擇最近鄰居的數目，其中標籤向量的元素數目和矩陣dataSet的行數相同。程序清單2-1使用歐氏距離公式，計算兩個向量點xA和xB之間的距離❶：
例如，點(0, 0)與(1, 2)之間的距離計算為：
如果數據集存在4個特徵值，則點(1, 0, 0, 1)與(7, 6, 9, 4)之間的距離計算為：
計算完所有點之間的距離後，可以對數據按照從小到大的次序排序。然後，確定前k個距離最小元素所在的主要分類❷，輸入k總是正整數；最後，將classCount字典分解為元組列表，然後使用程序第二行導入運算符模塊的itemgetter方法，按照第二個元素的次序對元組進行排序❸。此處的排序為逆序，即按照從最大到最小次序排序，最後返回發生頻率最高的元素標籤。
為了預測數據所在分類，在Python提示符中輸入下列命令：
>>> kNN.classify0([0,0], group, labels, 3)
輸出結果應該是B，大家也可以改變輸入[0, 0]為其他值，測試程序的運行結果。
到現在為止，我們已經構造了第一個分類器，使用這個分類器可以完成很多分類任務。從這個實例出發，構造使用分類算法將會更加容易。
2.1.3 如何測試分類器
上文我們已經使用k近鄰算法構造了第一個分類器，也可以檢驗分類器給出的答案是否符合我們的預期。讀者可能會問：「分類器何種情況下會出錯？」或者「答案是否總是正確的？」答案是否定的，分類器並不會得到百分百正確的結果，我們可以使用多種方法檢測分類器的正確率。此外分類器的性能也會受到多種因素的影響，如分類器設置和數據集等。不同的算法在不同數據集上的表現可能完全不同，這也是本部分的6章都在討論分類算法的原因所在。
為了測試分類器的效果，我們可以使用已知答案的數據，當然答案不能告訴分類器，檢驗分類器給出的結果是否符合預期結果。通過大量的測試數據，我們可以得到分類器的錯誤率——分類器給出錯誤結果的次數除以測試執行的總數。錯誤率是常用的評估方法，主要用於評估分類器在某個數據集上的執行效果。完美分類器的錯誤率為0，最差分類器的錯誤率是1.0，在這種情況下，分類器根本就無法找到一個正確答案。讀者可以在後面章節看到實際的數據例子。
上一節介紹的例子已經可以正常運轉了，但是並沒有太大的實際用處，本章的後兩節將在現實世界中使用k近鄰算法。首先，我們將使用k近鄰算法改進約會網站的效果，然後使用k近鄰算法改進手寫識別系統。本書將使用手寫識別系統的測試程序檢測k近鄰算法的效果。