理論

kNN是監(jiān)督學(xué)習(xí)里最簡(jiǎn)單的分類(lèi)算法贞谓。思路就是搜索最匹配的測(cè)試數(shù)據(jù)十性。

在圖片里叛溢，有兩個(gè)家庭，藍(lán)方塊和紅三角烁试，我們把每一家叫做類(lèi)雇初。他們的房子顯示在他們城市地圖里，這個(gè)城市圖我們叫做特征空間减响。（你可以認(rèn)為一個(gè)特征空間就是所有數(shù)據(jù)投射的空間靖诗。比如在二維坐標(biāo)系里，每個(gè)數(shù)據(jù)有兩個(gè)特征支示，x坐標(biāo)和y坐標(biāo)刊橘。你可以吧這個(gè)數(shù)據(jù)表示在你的二維空間里，現(xiàn)在假設(shè)有三個(gè)特征颂鸿，你就需要三維空間促绵，如果是N個(gè)特征，你就需要N維空間嘴纺，這個(gè)N維空間就是特征空間）

現(xiàn)在一個(gè)新的成員進(jìn)入了城市并建了自己的家败晴，用綠色園來(lái)表示。他應(yīng)該要加入藍(lán)家庭或者紅家庭栽渴。我們把這個(gè)過(guò)程稱(chēng)為分類(lèi)尖坤。怎么做呢？由于我們?cè)诹私鈑NN闲擦，讓我們來(lái)使用這個(gè)算法慢味。

一個(gè)方法是檢查誰(shuí)是他最近的鄰居。在這個(gè)圖里墅冷，很顯然紅三角離得近纯路，所以他就加入了紅三角。這個(gè)方法被叫做簡(jiǎn)單最近鄰寞忿，因?yàn)榉诸?lèi)是基于最近鄰居.

但是這有個(gè)問(wèn)題驰唬，紅三角可能是最近的，但是如果他周?chē)泻芏嗨{(lán)的呢腔彰，那么藍(lán)方塊在那個(gè)區(qū)域比紅三角力量更大定嗓。所以只看最近的一個(gè)是不充分的蜕琴。所以我們改成檢查k個(gè)最近的家庭萍桌。他們當(dāng)中誰(shuí)更主要宵溅，新來(lái)的就屬于那類(lèi)家庭。在我們的圖片里上炎，我們讓k=3恃逻，也就是找最近的3個(gè)家庭，有兩個(gè)紅的和一個(gè)藍(lán)的藕施，（其實(shí)有兩個(gè)藍(lán)的差不多距離寇损，但是因?yàn)閗=3，我們只取其中一個(gè)）裳食，所以再一次矛市，他還是應(yīng)該屬于紅色家庭。但是如果我們?nèi)=7呢诲祸，那么他就有5個(gè)藍(lán)色家庭和2個(gè)紅色家庭了∽抢簦現(xiàn)在他應(yīng)該屬于藍(lán)色家庭，所以完全取決于k的值救氯。更有意思的是找田，如果k=4呢，有兩個(gè)紅的和兩個(gè)藍(lán)的鄰居着憨，平局墩衙！所以最好讓k取奇數(shù)。這個(gè)方法叫做k-近鄰也就是由于分類(lèi)取決于k個(gè)最近的鄰居甲抖。

再一次漆改， 在kNN中，我們考慮了k個(gè)鄰居准谚，但是我們給了他們同樣的權(quán)重挫剑，比如說(shuō)在k=4的情況下，是平局氛魁，但是2個(gè)紅的家庭里的比兩個(gè)藍(lán)的家庭更近暮顺。所以更合適加入紅色家庭。我們?cè)趺从脭?shù)學(xué)來(lái)解釋它呢秀存。我們給每個(gè)家庭一個(gè)權(quán)重捶码，根據(jù)他們和新來(lái)的人的距離。然后我們把每個(gè)家庭的權(quán)重按類(lèi)加起來(lái)或链，那個(gè)的權(quán)重和高惫恼，新來(lái)的就歸那個(gè)家庭。這個(gè)叫做modified kNN澳盐。

所以看到什么重要的事情了么

·你需要得到城里所有房子的信息祈纯，因?yàn)槲覀円獧z查新來(lái)的和原來(lái)的房子的距離來(lái)找最近的鄰居令宿。如果有很多房子和家庭，會(huì)需要很多內(nèi)存腕窥，以及很多時(shí)間來(lái)計(jì)算粒没。
·幾乎不需要時(shí)間訓(xùn)練或準(zhǔn)備。

現(xiàn)在讓我們看看OpenCV里的簇爆。

OpenCV里的kNN

我們有個(gè)小例子癞松，兩個(gè)家庭（類(lèi)），跟上面一樣.

我們把紅色家庭標(biāo)為Class-0（用0來(lái)表示）入蛆，藍(lán)色家庭是Class-1(用1表示）响蓉，我們建立25個(gè)家庭，用Class-0或Class-1來(lái)標(biāo)記他們哨毁，這些通過(guò)Numpy的隨機(jī)數(shù)生成器來(lái)完成枫甲。

然后我們用Matplotlib來(lái)繪制。紅色家庭用紅三角扼褪，藍(lán)色家庭用藍(lán)方塊想幻。

import cv2
import numpy as np
import matplotlib.pyplot as plt

# Feature set containing (x,y) values of 25 known/training data
trainData = np.random.randint(0,100,(25,2)).astype(np.float32)

# Labels each one either Red or Blue with numbers 0 and 1
responses = np.random.randint(0,2,(25,1)).astype(np.float32)

# Take Red families and plot them
red = trainData[responses.ravel()==0]
plt.scatter(red[:,0], red[:,1], 80, 'r', '^')

# Take Blue families and plot them
blue = trainData[responses.ravel()==1]
plt.scatter(blue[:,0], blue[:,1], 80, 'b', 's')

plt.show()

你可以從我們第一個(gè)圖像里得到類(lèi)似的東西。由于你使用隨機(jī)數(shù)生成器迎捺，你會(huì)在每次運(yùn)行代碼時(shí)得到不同數(shù)據(jù)举畸。

接著初始化kNN算法并傳入trainData和response來(lái)訓(xùn)練kNN(它構(gòu)建了一個(gè)搜索樹(shù))。

然后我們會(huì)拿來(lái)一個(gè)新來(lái)的凳枝，通過(guò)OpenCV里的kNN的幫助把他分類(lèi)到一個(gè)家庭抄沮。在kNN之前，我們需要知道我們的測(cè)試數(shù)據(jù)的一些事岖瑰。我們的數(shù)據(jù)應(yīng)該是大小是 測(cè)試數(shù)據(jù)的數(shù)量?* 特征的數(shù)量 的浮點(diǎn)數(shù)組叛买。然后我們找新來(lái)的最近的鄰居。我們可以指定我們要多少鄰居蹋订。它返回：

1.給新來(lái)的成員的標(biāo)簽率挣，如果你想用NN算法，只需要指定k=1.

2.k個(gè)最近鄰居的標(biāo)簽

3.從新來(lái)的到每個(gè)最近鄰居的對(duì)應(yīng)距離露戒。

所以讓我們看看怎么做的椒功。新來(lái)的被標(biāo)記為綠色。

newcomer = np.random.randint(0,100,(1,2)).astype(np.float32)
plt.scatter(newcomer[:,0],newcomer[:,1],80,'g','o')

knn = cv2.KNearest()
knn.train(trainData,responses)
ret, results, neighbours ,dist = knn.find_nearest(newcomer, 3)

print "result: ", results,"\n"
print "neighbours: ", neighbours,"\n"
print "distance: ", dist

plt.show()

得到的結(jié)果：

result:? [[ 1.]]

neighbours:? [[ 1.? 1.? 1.]]

distance:? [[ 53.? 58.? 61.]]

我們的新來(lái)的有3個(gè)鄰居智什，所有的都是藍(lán)色家庭的动漾。所以他被標(biāo)記為藍(lán)色家庭。

如果你有大量數(shù)據(jù)荠锭，你可以用數(shù)組傳旱眯。對(duì)應(yīng)的結(jié)果也是用數(shù)組返回。

# 10 new comers
newcomers = np.random.randint(0,100,(10,2)).astype(np.float32)
ret, results, neighbours, dist = knn.find_nearest(newcomer,3)
# The results also will contain 10 labels.