1272
0
0
2018-09-27 20:03:43
2018-09-27
k-近鄰算法概述
簡單地說，谷近鄰算法采用測量不同特征值之間的距離方法進(jìn)行分類。
| ■ 卜近鄰算法 ■ - i
< .
優(yōu)點：精度高、對異常值不敏感、無數(shù)據(jù)輸入假定。
缺點：計算復(fù)雜度高、空間復(fù)雜度高。
適用數(shù)據(jù)范圍：數(shù)值型和標(biāo)稱型。
16 第 2 章 A -近鄰算法
本書講解的第一個機(jī)器學(xué)習(xí)算法是 & 近鄰算法（ _ ) , 它的工作原理是：存在一個樣本數(shù)
據(jù)集合，也稱作訓(xùn)練樣本集，并且樣本集中每個數(shù)據(jù)都存在標(biāo)簽，即我們知道樣本集中每一數(shù)據(jù)
與所屬分類的對應(yīng)關(guān)系。輸人沒有標(biāo)簽的新數(shù)據(jù)后，將新數(shù)據(jù)的每個特征與樣本集中數(shù)據(jù)對應(yīng)的
特征進(jìn)行比較，然后算法提取樣本集中特征最相似數(shù)據(jù)（最近鄰）的分類標(biāo)簽。一般來說，我們
只選擇樣本數(shù)據(jù)集中前 & 個最相似的數(shù)據(jù)，這就是 &- 近鄰算法中 & 的出處 , 通常 * 是不大于 20 的整數(shù)。
最后，選擇 & 個最相似數(shù)據(jù)中出現(xiàn)次數(shù)最多的分類，作為新數(shù)據(jù)的分類。
現(xiàn)在我們回到前面電影分類的例子，使用 &- 近鄰算法分類愛情片和 1 動作片。有人曾經(jīng)統(tǒng)計過
很多電影的打斗鏡頭和接吻鏡頭，圖 2-1 顯示了 6 部電影的打斗和接吻 _ 頭數(shù)。假如有一部未看過
的電影，如何確定它是愛情片還是動作片呢？我們可以使用 _ 來解決這個問題。
California Man
He’s Not Really inlo Dudes
?
Beautiful Woman
Kevin Longblade
Robo Slayer 3000
Amped II
電影中出現(xiàn)的打斗鏡頭次數(shù)
圖2 - 1 使 用 打 斗 和 接 吻 鏡 頭 數(shù) 分 類 電 影
首先我們需要知道這個未知電影存在多少個打斗鏡頭和接吻鏡頭，圖 2-1 中問號位置是該未
知電影出現(xiàn)的鏡頭數(shù)圖形化展示，具體數(shù)字參見表 2-1 。
表 2 - 1 每部電影的打斗鏡頭數(shù)、接吻鏡頭數(shù)以及電影評估類型
電影名稱
打斗鏡頭 接吻鏡頭 電影類型
California Man 3 104 愛情片
He 's Not Really into Dudes 2 100 愛情片
Beautiful Woman 1 81 愛情片
Kevin Longblade 10】 10 動作片
Robo Slayer 3000 99 5 動作片
Amped // 98 2
動作片
? 18 90 未知
即使不知道未知電影屬于哪種類型，我們也可以通過某種方法計算出來。首先計算未知電影
與樣本集中其他電影的距離，如表 2-2 所示。此處暫時不要關(guān)心如何計算得到這些距離值，使用
Python 實現(xiàn)電影分類應(yīng)用時，會提供具體的計算方法 D
電
現(xiàn)
的
接
吻
鏡
頭
次
數(shù)
2.1 A -近鄰算法概述 17
表 2 - 2 已知電影與未知電影的距離
________________ 電影名稱 ______________ ___________________與未知電影的距離______________________
California Man m 5
He 's Not Really into Dudes 18.7
Beautiful Woman 19.2
Kevin Longblade 115.3
Robo Slayer 3000 117.4
Amped II _________________ m 3 ____________________
現(xiàn)在我們得到了樣本集中所有電影與未知電影的距離 ， 按照距離遞增排序 ， 可以找到乂個距
離最近的電影。假定 ^=3 ，貝丨』三個最靠近的電影依次是故》 #0; 辦 (7// 少如 0/3? 如 、Beautiful Woman
和。_ _ 從 氣 4- 近鄰算法按照距離最近的三部電影的類型，決定未知電影的類型，而這三部
電影全是愛情片，因此我們判定未知電影是愛情片。
本章主要講解如何在實際環(huán)境中應(yīng)用々-近鄰算法 ， 同時涉及如何使用 ?7 出(^工具和相關(guān)的機(jī)
器學(xué)習(xí)術(shù)語。按照 1.5 節(jié)開發(fā)機(jī)器學(xué)習(xí)應(yīng)用的通用步驟，我們使用 ? 乂出如語言開發(fā)&-近鄰算法的簡
單應(yīng)用，以檢驗算法使用的正確性。
k -近鄰算法的一般流程 f ,-
■ A . 廣,^a.. :?
(1) 收集數(shù)據(jù)：可以使用任何方法。
(2) 準(zhǔn)備數(shù)據(jù)：距離計算所需要的數(shù)值，最好是結(jié)構(gòu)化的數(shù)據(jù)格式。
(3) 分析數(shù)據(jù)：可以使用任何方法。
(4) 訓(xùn)練算法：此步驟不適用于 1 近鄰算法。
(5) 測試算法：計算錯誤率。
(6) 使用算法：首先需要輸入樣本數(shù)據(jù)和結(jié)構(gòu)化的輸出結(jié)果，然后運行女-近鄰算法判定輸
入數(shù)據(jù)分別屬于哪個分類，最后應(yīng)用對計算出的分類執(zhí)行后續(xù)的處理。
2 . 1 . 1 準(zhǔn) 備 ：使 用 Python 導(dǎo) 入 數(shù) 據(jù)
首先，創(chuàng) 建 名 為麵 孫的 ? 沖 0 濃 塊 ，本章使用的所有代碼都在這個文件中。讀者可以按照自
己的習(xí)慣學(xué)習(xí)代碼，既可以按照本書學(xué)習(xí)的進(jìn)度，在自己創(chuàng)建的 ?7^?^ 文件中編寫代碼，也可以直
接從本書的源代碼中復(fù)制 _ 仍文件。我推薦讀者從頭開始創(chuàng)建模塊，按照學(xué)習(xí)的進(jìn)度編寫代碼。
無論大家采用何種方法，我們現(xiàn)在已經(jīng)有了 kNN.py 文件。在構(gòu)造完整的丨 - 近鄰算法之前，我
們還需要編寫一些基本的通用函數(shù)，在 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', 'B1]
return group, labels
在上面的代碼中，我們導(dǎo)人了兩個模塊；第一個是科學(xué)計算包 > ^ ! ^ ^ 第二個是運算符模塊 ,
18 第 2 章 it -近鄰算法
女 - 近鄰算法執(zhí)行排序操作時將使用這個模塊提供的函數(shù)，后面我們將進(jìn)一步介紹。
為了方便使用。 3^ 社 60 社沾 61^) 函數(shù)，它創(chuàng)建數(shù)據(jù)集和標(biāo)簽，如圖 2-1 所示。然后依次執(zhí)行
以下步驟：保存 _ $ 7 文件，改變當(dāng)前路徑到存儲 — .?7 文件的位置，打開 ? 外 1?^ 開發(fā)環(huán)境。
Xifc^Linux、Mac OS 還是 Windows 都需要在打開終端，在命令提亦符下完成上述操作。只要我
們按照默認(rèn)配置安裝 ?3^(?, 在 01?? 幾 ^ 0 8 終端內(nèi)都可以直接輸人 97 比 01^ 而在斯 1?10 評 8 命令
提水符下需要輸人。 :\Python2 . 6\python _ exe, 進(jìn)人 ?7 也 00 交互式開發(fā)環(huán)境。
進(jìn)人 ? 丫出 (^ 開發(fā)環(huán)境之后，輸人下列命令導(dǎo)人上面編輯的程序模塊 :
>>> import kNN
上述命令導(dǎo)人臟模塊。為了確保輸人相同的數(shù)據(jù)集，麵模塊中定義了函數(shù) ^ 的七扣壯沾社，在
卩 ” 乜 0 ?命令提本符下輸入下屬命令 :
>>> g ro u p ,la b e ls = kNN.createDataSet()
上述命令創(chuàng)建了變量 910 叩和 1 沾 01 3 ，在 ? 7 出 ^ 命令提示符下，輸人變量的名字以檢驗是否正確
地定義變量：
>>> group
array([[ 1 1 . 1] ?
0.1]])
labels
['Af, 'A', 'B,, 'B']
這里有 4 組數(shù)據(jù)，每組數(shù)據(jù)有兩個我們已知的屬性或者特征值。上面的 9!^ 卩?矩陣每行包含一個
不同的數(shù)據(jù)，我們可以把它想象為某個日志文件中不同的測量點或者入口。由于人類大腦的限制，
我們通常只能可視化處理三維以下的事務(wù)。因此為了簡單地實現(xiàn)數(shù)據(jù)可視化，對于每個數(shù)據(jù)點我
們通常只使用兩個特征。
向量 1 必 61 包含了每個數(shù)據(jù)點的標(biāo)簽信息， 1 處 61 包含的元素個數(shù)等于取。叩矩陣行數(shù)。這
里我們將數(shù)據(jù)點 (1 ， 1.1) 定義為類八，數(shù)據(jù)點 (0, 0.1) 定義為類 8 。為了說明方便，例子中的數(shù)值是
任意選擇的，并沒有給出軸標(biāo)簽，圖 2-2 是帶有類標(biāo)簽信息的四個數(shù)據(jù)點。
~ ° - 0.2 0.0 0.2 0.4 0.6 0.8 1.0 1.2
? 圖 2-2 & 近鄰算法：帶有 4 個數(shù)據(jù)點的簡單例子
2.1 A -近鄰算法概述 19
現(xiàn)在我們巳經(jīng)知道 ?7??^ 如何解析數(shù)據(jù)，如何加載數(shù)據(jù)，以及 _ 算法的工作原理，接下來
我們將使用這些方法完成分類任務(wù)。
2 .1 .2 從文本文件中解析數(shù)據(jù)
本節(jié)使用程序清單 2-1 的函數(shù)運行 _ 算法，為每組數(shù)據(jù)分類。這里首先給出卜近鄰算法的偽
代碼和實際的 ? 乂出 011 代碼，然后詳細(xì)地解釋每行代碼的含義。該函數(shù)的功能是使用&-近鄰算法將
每組數(shù)據(jù)劃分到某個類中，其偽代碼如下：
對未知類別屬性的數(shù)據(jù)集中的每個點依次執(zhí)行以下操作：
(1) 計算已知類別數(shù)據(jù)集中的點與當(dāng)前點之間的距離；
(2) 按照距離遞增次序排序；
(3) 選取與當(dāng)前點距離最小的走個點；
(4) 確定前灸個點所在類別的出現(xiàn)頻率；
(5) 返回前女個點出現(xiàn)頻率最高的類別作為當(dāng)前點的預(yù)測分類。
? 丫 0?^ 函數(shù) <=13331&0 () 如程序清單 2_1 所示。
程序清單 2 - 1 各近鄰算法
def classifyO(inX, dataSet, labels, k ) ：
dataSetSize = daCaSet.shape fO]
diffMat = tile(inX, (dataSetSize,1)) - dataSet
sqDiffMat = diffMat**2
sqDistances = sqDiffMat.s u m (axis=l)
distances = sqDistances**O.5
sortedDistIndicies - distances .argaort ()
距離計算
classCount={} 選 擇 距 離 最 小 資
for 1 in range(k). 的斤個占 ^ \
voteIlabel = labels[sortedDistIndicies[i]]
classCount[votellabel] = classCount.get{voteIlabel,0) + 1
sortedClassCount = sorted(classCount.iteritems(),
key=operator.itemgetter{l), reverse=True) <~ ^
return sortedClassCount[0] [0] 辦 排 序
classifyO () 函數(shù)有 4 個輸人參數(shù) : 用于分類的輸人向量是丨必，輸人的訓(xùn)練樣本集為 (1313861,
標(biāo)簽向量為 131^13 ，最后的參數(shù)義表示用于選擇最近鄰居的數(shù)目，其中標(biāo)簽向量的元素數(shù)目和矩
陣如 1 沾 & 的行數(shù)相同。程序清單 2-1 使用歐氏距離公式，計算兩個向量點 “ 和成之間的距離 0 :
d = 」(xA0 - xB0 )2 + (xA{ - xBt )2
例如，點 (0 ， 0) 與 (1, 2) 之間的距離計算為：
V(l-0)2+(2-0)2
如果數(shù)據(jù)集存在 4 個特征值，則點 (1 ， 0, 0 ， 1) 與 (7, 6, 9 ， 4) 之間的距離計算為：
20 第 2 章 1 -近鄰算法
V(7 -1)2 + (6 - 0)2 + (9 一 0)2 + (4 一 1)2
計算完所有點之間的距離后，可以對數(shù)據(jù)按照從小到大的次序排序。然后，確定前 k 個距離
最小元素所在的主要分類 ? , 輸人々總是正整數(shù)；最后，將 < ^ 尤 0 恤字典分解為元組列表，然后
使用程序第二行導(dǎo)入運算符模塊的讓挪 9 過 te r^ m ,按照第二個元素的次序?qū)υM進(jìn)行排序?。
此處的 3# 序為逆序，即按照從最大到最小次序排序，最后返回發(fā)生頻率最高的元素標(biāo)簽。
為了預(yù)測數(shù)據(jù)所在分類，在卩沖如提示符中輸入下列命令 :
>>> kNN.classify0([0,0], group, labels, 3)
輸出結(jié)果應(yīng)該是艮大家也可以改變輸人 [0,0] 為其他值，測試程序的運行結(jié)果。
到現(xiàn)在為止，我們已經(jīng)構(gòu)造了第一個分類器，使用這個分類器可以完成很多分類任務(wù)。從這
個實例出發(fā)，構(gòu)造使用分類算法將會更加容易。
2 .1 .3 如何測試分類器
上文我們已經(jīng)使用女 - 近鄰算法構(gòu)造了第一個分類器，也可以檢驗分類器給出的答案是否符合
我們的預(yù)期。讀者可能會問： “ 分類器何種情況下會出錯？ ” 或 者 “ 答案是否總是正確的？ ” 答
案是否定的 , 分類器并不會得到百分百正確的結(jié)果 , 我們可以使用多種方法檢測分類器的正確率。
此外分類器的性能也會受到多種因素的影響，如分類器設(shè)置和數(shù)據(jù)集等。不同的算法在不同數(shù)據(jù)
集上的表現(xiàn)可能完全不同，這也是本部分的 6 章都在討論分類算法的原因所在。
為了測試分類器的效果，我們可以使用已知答案的數(shù)據(jù)，當(dāng)然答案不能告訴分類器，檢驗分
類器給出的結(jié)果是否符合預(yù)期結(jié)果。通過大量的測試數(shù)據(jù)，我們可以得到分類器的錯誤率 — 分
類器給出錯誤結(jié)果的次數(shù)除以測試執(zhí)行的總數(shù)。錯誤率是常用的評估方法，主要用于評估分類器
在某個數(shù)據(jù)集上的執(zhí)行效果。完美分類器的錯誤率為 0 , 最差分類器的錯誤率是 1.0 ,在這種情況
下，分類器根本就無法找到一個正確答案。讀者可以在后面章節(jié)看到實際的數(shù)據(jù)例子。
上一節(jié)介紹的例子已經(jīng)可以正常運轉(zhuǎn)了，但是并沒有太大的實際用處，本章的后兩節(jié)將在現(xiàn)
實世界中使用 / 卜近鄰算法。首先，我們將使用 &- 近鄰算法改進(jìn)約會網(wǎng)站的效果，然后使用々-近鄰
算法改進(jìn)手寫識別系統(tǒng)。本書將使用手寫識別系統(tǒng)的測試程序檢測々 - 近鄰算法的效果。
