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