分類算法之K最近鄰算法(KNN)的Python實現(xiàn)
KNN的定義
所謂K近鄰算法，即是給定一個訓練數(shù)據(jù)集轮蜕，對新的輸入實例昨悼，在訓練數(shù)據(jù)集中找到與該實例最鄰近的K個實例，這K個實例的多數(shù)屬于某個類肠虽，就把該輸入實例分類到這個類中幔戏。
介紹
如下圖所示，有兩類不同的樣本數(shù)據(jù)税课，分別用藍色的小正方形和紅色的小三角形表示闲延，而圖正中間的那個綠色的圓所標示的數(shù)據(jù)則是待分類的數(shù)據(jù)。也就是說韩玩，現(xiàn)在垒玲， 我們不知道中間那個綠色的數(shù)據(jù)是從屬于哪一類（藍色小正方形or紅色小三角形），下面找颓，我們就要解決這個問題：給這個綠色的圓分類合愈。
我們常說，物以類聚，人以群分佛析，判別一個人是一個什么樣品質(zhì)特征的人益老，常常可以從他/她身邊的朋友入手寸莫，所謂觀其友捺萌，而識其人。我們不是要判別上圖中那個綠色的圓是屬于哪一類數(shù)據(jù)么膘茎，好說桃纯，從它的鄰居下手。但一次性看多少個鄰居呢披坏？從上圖中态坦，你還能看到：
如果K=3，綠色圓點的最近的3個鄰居是2個紅色小三角形和1個藍色小正方形棒拂，少數(shù)從屬于多數(shù)伞梯，基于統(tǒng)計的方法，判定綠色的這個待分類點屬于紅色的三角形一類着茸。
如果K=5壮锻，綠色圓點的最近的5個鄰居是2個紅色三角形和3個藍色的正方形，還是少數(shù)從屬于多數(shù)涮阔，基于統(tǒng)計的方法猜绣，判定綠色的這個待分類點屬于藍色的正方形一類。
于此我們看到敬特，當無法判定當前待分類點是從屬于已知分類中的哪一類時掰邢，我們可以依據(jù)統(tǒng)計學的理論看它所處的位置特征，衡量它周圍鄰居的權(quán)重伟阔，而把它歸為(或分配)到權(quán)重更大的那一類辣之。這就是K近鄰算法的核心思想。
KNN 算法本身簡單有效皱炉，它是一種 lazy-learning 算法怀估，分類器不需要使用訓練集進行訓練，訓練時間復雜度為0合搅。KNN 分類的計算復雜度和訓練集中的文檔數(shù)目成正比多搀，也就是說，如果訓練集中文檔總數(shù)為 n灾部，那么 KNN 的分類時間復雜度為O(n)康铭。
K 近鄰算法使用的模型實際上對應于對特征空間的劃分。K 值的選擇赌髓，距離度量和分類決策是該算法的三個基本要素：
K 值的選擇會對算法的結(jié)果產(chǎn)生重大影響从藤。K值較小意味著只有與輸入實例較近的訓練實例才會對預測結(jié)果起作用催跪，但容易發(fā)生過擬合；如果 K 值較大夷野，優(yōu)點是可以減少學習的估計誤差懊蒸，但缺點是學習的近似誤差增大，這時與輸入實例較遠的訓練實例也會對預測起作用悯搔，使預測發(fā)生錯誤榛鼎。在實際應用中，K 值一般選擇一個較小的數(shù)值鳖孤，通常采用交叉驗證的方法來選擇最優(yōu)的 K 值。隨著訓練實例數(shù)目趨向于無窮和 K=1 時抡笼，誤差率不會超過貝葉斯誤差率的2倍苏揣，如果K也趨向于無窮，則誤差率趨向于貝葉斯誤差率推姻。
該算法中的分類決策規(guī)則往往是多數(shù)表決平匈，即由輸入實例的 K 個最臨近的訓練實例中的多數(shù)類決定輸入實例的類別。
距離度量一般采用 Lp 距離藏古，當p=2時增炭，即為歐氏距離，在度量之前拧晕，應該將每個屬性的值規(guī)范化隙姿，這樣有助于防止具有較大初始值域的屬性比具有較小初始值域的屬性的權(quán)重過大。
在KNN中厂捞，通過計算對象間距離來作為各個對象之間的非相似性指標输玷，避免了對象之間的匹配問題，在這里距離一般使用歐氏距離或曼哈頓距離(其中x,y為2個樣本靡馁，n為維度欲鹏，x(k),y(k)為x，y第k個維度上的特征值臭墨。)：
算法描述
計算步驟：
- 算距離：給定測試對象赔嚎，計算它與訓練集中的每個對象的距離
- 找鄰居：圈定距離最近的k個訓練對象，作為測試對象的近鄰
- 做分類：根據(jù)這k個近鄰歸屬的主要類別胧弛，來對測試對象分類
算法實現(xiàn)(python)
#coding:utf-8
import numpy
def classify(inX,dataSet,labels,k):
"""
:param inX: example
:param dataSet: dataSet 2D List
:param labels: 1D List
:param k the number of neighbor
:return: The label of the example as classify result.
"""
if len(dataSet) != len(labels):
raise ValueError("DataSet or labels was too less!"
"The length of DataSet is %s"
"But the length of labels is %s"%(len(dataSet),len(labels)))
dArrays = numpy.array(dataSet)
inArray = numpy.array(inX)
result = (((dArrays-inArray)**2).sum(axis=1))**0.5
index_list = result.argsort() #argsort函數(shù)返回的是數(shù)組值從小到大的索引值
classCount = dict()
for i in range(k):
label = labels[index_list[i]]
classCount[label] = classCount.get(label,0) + 1
return sorted(classCount,key=lambda x:classCount[x],reverse=True)[0]
案例演示
電影分類數(shù)據(jù)集：
| 電影名稱 | 搞笑鏡頭 | kiss鏡頭 | 打斗鏡頭 | 標簽 |
|---|---|---|---|---|
| 美人魚 | 45 | 2 | 9 | 喜劇片 |
| 功夫熊貓3 | 39 | 0 | 31 | 喜劇片 |
| 諜影重重 | 5 | 2 | 57 | 動作片 |
| 葉問3 | 3 | 2 | 65 | 動作片 |
| 怦然心動 | 7 | 46 | 4 | 愛情片 |
| 泰坦尼克號 | 9 | 39 | 8 | 愛情片 |
-
我們構(gòu)建一個已分好類的數(shù)據(jù)集
movie_data = {"美人魚":[45,2,9,"喜劇片"], "功夫熊貓3":[39,0,1,"喜劇片"], "諜影重重":[5,2,57,"動作片"], "葉問3":[3,2,65,"動作片"], "怦然心動":[7,46,4,"愛情片"], "泰坦尼克號":[9,39,8,"愛情片"]} -
計算一個新樣本與數(shù)據(jù)集中所有數(shù)據(jù)的距離
這里的新樣本就是："唐人街探案": [23, 3, 17, "尤误？"]。使用歐氏距離來計算叶圃。
x為："唐人街探案": [23, 3, 17, "袄膏？"]，y為："諜影重重": [5, 2, 57, "動作片"]掺冠，則兩者之間的距離為：
d = ((23-5)**2+(3-2)**2+(17-57)**2)**0.5
代碼實現(xiàn)：
x = [23, 3, 17] KNN = [] for k,v in movie_data.items(): d = math.sqrt((x[0] - v[0]) ** 2 + (x[1] - v[1]) ** 2 + (x[2] - v[2]) ** 2) KNN.append([k,round(d,2)]) #round為取精度沉馆，兩位小數(shù)码党。 return KNN #output [["葉問3",52.01],["功夫熊貓3",22.83],["泰坦尼克號",39.66],["美人魚",23.43],["諜影重重",43.87],["怦然心動",47.69]] -
按照距離大小進行遞增排序
KNN.sort(key=lambda dis: dis[1]) #output [["功夫熊貓3",22.83],["美人魚",23.43],["泰坦尼克號",39.66],["諜影重重",43.87],["怦然心動",47.69],["葉問3",52.01]] 選取距離最小的k個樣本
KNN=KNN[:3] #取前3個，K=3
#output
[["功夫熊貓3",22.83],["美人魚",23.43],["泰坦尼克號",39.66]]-
確定前k個樣本所在類別出現(xiàn)的頻率斥黑，并輸出出現(xiàn)頻率最高的類別
labels = {"喜劇片":0,"動作片":0,"愛情片":0} for s in KNN: label = movie_data[s[0]] labels[label[3]] += 1 labels =sorted(labels.items(),key=lambda l: l[1],reverse=True) return labels #output {"喜劇片":2,"愛情片":1,"動作片":0} 所以可以把"唐人街探案"這部電影打上喜劇片的標簽
算法評估
- KNN算法不僅可以用于分類揖盘，還可以用于回歸。通過找出一個樣本的k個最近鄰居锌奴，將這些鄰居的屬性的平均值賦給該樣本兽狭，就可以得到該樣本的屬性。
- 該算法在分類時有個主要的不足是鹿蜀，當樣本不平衡時箕慧，如一個類的樣本容量很大，而其他類樣本容量很小時茴恰，有可能導致當輸入一個新樣本時颠焦，該樣本的K個鄰居中大容量類的樣本占多數(shù)。 該算法只計算“最近的”鄰居樣本往枣，某一類的樣本數(shù)量很大伐庭，那么或者這類樣本并不接近目標樣本，或者這類樣本很靠近目標樣本分冈。無論怎樣圾另，數(shù)量并不能影響運行結(jié)果〉癯粒可以采用權(quán)值的方法（和該樣本距離小的鄰居權(quán)值大）來改進集乔。
- 該方法的另一個不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離蘑秽，才能求得它的K個最近鄰點饺著。目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本肠牲。該算法比較適用于樣本容量比較大的類域的自動分類幼衰，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。
行業(yè)應用
字符識別缀雳、文本分類渡嚣、圖像識別
客戶流失預測、欺詐偵測等（更適合于稀有事件的分類問題）
