轉(zhuǎn)自：?http://www.cnblogs.com/qwertWZ/p/4582096.html

本章介紹了《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》這本書(shū)中的第一個(gè)機(jī)器學(xué)習(xí)算法：k-近鄰算法，它非常有效而且易于掌握。首先，我們將探討k-近鄰算法的基本理論，以及如何使用距離測(cè)量的方法分類物品；其次我們將使用Python從文本文件中導(dǎo)入并解析數(shù)據(jù)；再次，本文討論了當(dāng)存在許多數(shù)據(jù)來(lái)源時(shí)，如何避免計(jì)算距離時(shí)可能碰到的一些常見(jiàn)錯(cuò)誤；最后，利用實(shí)際的例子講解如何使用k-近鄰算法改進(jìn)約會(huì)網(wǎng)站和手寫(xiě)數(shù)字識(shí)別系統(tǒng)。

回到頂部

1. k-近鄰算法概述

簡(jiǎn)單地說(shuō)，k-近鄰算法采用測(cè)量不同特征值之間的距離方法進(jìn)行分類。

k-近鄰算法

優(yōu)點(diǎn)：精度高、對(duì)異常值不敏感、無(wú)數(shù)據(jù)輸入假定。
缺點(diǎn)：計(jì)算復(fù)雜度高、空間復(fù)雜度高
適用數(shù)據(jù)范圍：數(shù)值型和標(biāo)稱型

k-近鄰算法（kNN）的工作原理是：存在一個(gè)樣本數(shù)據(jù)集合，也稱作訓(xùn)練樣本集，并且樣本集中每個(gè)數(shù)據(jù)都存在標(biāo)簽，即我們知道樣本集中每一數(shù)據(jù)與所屬分類的對(duì)應(yīng)關(guān)系。輸入沒(méi)有標(biāo)簽的新數(shù)據(jù)后，將新數(shù)據(jù)的每個(gè)特征與樣本集中數(shù)據(jù)對(duì)應(yīng)的特征進(jìn)行比較，然后算法提取樣本集中特征最相似數(shù)據(jù)（最近鄰）的分類標(biāo)簽。一般來(lái)說(shuō)，我們只選擇樣本數(shù)據(jù)集中前k個(gè)最相似的數(shù)據(jù)，這就是k-近鄰算法中k的出處，通常k是不大于20的整數(shù)。最后，選擇k個(gè)最相似數(shù)據(jù)中出現(xiàn)次數(shù)最多的分類，作為新數(shù)據(jù)的分類。

現(xiàn)在我們回到前面電影分類的例子，使用k-近鄰算法分類愛(ài)情片和動(dòng)作片。有人曾經(jīng)統(tǒng)計(jì)過(guò)很多電影的打斗鏡頭和接吻鏡頭，圖1顯示了6部電影的打斗和接吻鏡頭數(shù)。假如有一部未看過(guò)的電影，如何確定它是愛(ài)情片還是動(dòng)作片呢？我們可以使用kNN來(lái)解決這個(gè)問(wèn)題。

?

圖1 使用打斗和接吻鏡頭數(shù)分類電影

首先我們需要知道這個(gè)未知電影存在多少個(gè)打斗鏡頭和接吻鏡頭，圖1中問(wèn)號(hào)位置是該未知電影出現(xiàn)的鏡頭數(shù)圖形化展示，具體數(shù)字參見(jiàn)下表。

表1 每部電影的打斗鏡頭數(shù)、接吻鏡頭數(shù)以及電影評(píng)估類型

電影名稱	打斗鏡頭	接吻鏡頭	電影類型
California Man	3	104	愛(ài)情片
He’s Not Really into Dudes	2	100	愛(ài)情片
Beautiful Woman	1	81	愛(ài)情片
Kevin Longblade	101	10	動(dòng)作片
Robo Slayer 3000	99	5	動(dòng)作片
Amped II	98	2	動(dòng)作片
?	18	90	未知

計(jì)算未知電影與樣本集中其他電影的距離，我們可以比較其相似度：

表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 II	118.9

現(xiàn)在我們得到了樣本集中所有電影與未知電影的距離，按照距離遞增排序，可以找到k個(gè)距離最近的電影。假定k=3，則三個(gè)最靠近的電影依次是He’s Not Really into Dudes、Beautiful Woman和California Man。k-近鄰算法按照距離最近的三部電影的類型，決定未知電影的類型，而這三部電影全是愛(ài)情片，因此我們判定未知電影是愛(ài)情片。

k-近鄰算法的一般流程

收集數(shù)據(jù)：可以使用任何方法。?
準(zhǔn)備數(shù)據(jù)：距離計(jì)算所需要的數(shù)值，最好是結(jié)構(gòu)化的數(shù)據(jù)格式。?
分析數(shù)據(jù)：可以使用任何方法。?
測(cè)試算法：計(jì)算錯(cuò)誤率。?
使用算法：首先需要輸入樣本數(shù)據(jù)和結(jié)構(gòu)化的輸出結(jié)果，然后運(yùn)行k-近鄰算法判定輸入數(shù)據(jù)分別屬于哪個(gè)分類。

1.1 準(zhǔn)備：使用Python導(dǎo)入數(shù)據(jù)

創(chuàng)建名為kNN.py的Python模塊，在kNN.py文件中增加下面的代碼：

1 2 3 4 5 6 7

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

這個(gè)函數(shù)創(chuàng)建了我們將要使用的樣例數(shù)據(jù)集。

在Python shell中輸入下列命令測(cè)試上面的函數(shù)：

1 2	>>> import kNN >>> group, labels = kNN.createDataSet()

1.2 實(shí)施kNN算法

k-近鄰算法的偽代碼

對(duì)未知類型屬性的數(shù)據(jù)集中的每個(gè)點(diǎn)依次執(zhí)行以下操作：
(1) 計(jì)算已知類別數(shù)據(jù)集中的點(diǎn)與當(dāng)前點(diǎn)之間的距離；
(2) 按照距離增序排序；
(3) 選取與當(dāng)前點(diǎn)距離最近的k個(gè)點(diǎn)；
(4) 決定這k個(gè)點(diǎn)所屬類別的出現(xiàn)頻率；
(5) 返回前k個(gè)點(diǎn)出現(xiàn)頻率最高的類別作為當(dāng)前點(diǎn)的預(yù)測(cè)分類。

函數(shù)實(shí)現(xiàn)如下：

總結(jié)

以上是生活随笔為你收集整理的K最近邻分类器的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。