K最近鄰(kNN，k-NearestNeighbor)分類(lèi)算法

??是數(shù)據(jù)挖掘分類(lèi)技術(shù)中最簡(jiǎn)單的方法之一。所謂K最近鄰，就是k個(gè)最近的鄰居的意思，說(shuō)的是每個(gè)樣本都可以用它最接近的k個(gè)鄰居來(lái)代表。
　　kNN算法的核心思想是如果一個(gè)樣本在特征空間中的k個(gè)最相鄰的樣本中的大多數(shù)屬于某一個(gè)類(lèi)別，則該樣本也屬于這個(gè)類(lèi)別，并具有這個(gè)類(lèi)別上樣本的特性。該方法在確定分類(lèi)決策上只依據(jù)最鄰近的一個(gè)或者幾個(gè)樣本的類(lèi)別來(lái)決定待分樣本所屬的類(lèi)別。 kNN方法在類(lèi)別決策時(shí)，只與極少量的相鄰樣本有關(guān)。由于kNN方法主要靠周?chē)邢薜泥徑臉颖?，而不是靠判別類(lèi)域的方法來(lái)確定所屬類(lèi)別的，因此對(duì)于類(lèi)域的交叉或重疊較多的待分樣本集來(lái)說(shuō)，kNN方法較其他方法更為適合。

KNN算法的機(jī)器學(xué)習(xí)基礎(chǔ)

??顯示相似數(shù)據(jù)點(diǎn)通常如何彼此靠近存在的圖像
　　大多數(shù)情況下，相似的數(shù)據(jù)點(diǎn)彼此接近。KNN算法就是基于這個(gè)假設(shè)以使算法有用。KNN利用與我們童年時(shí)可能學(xué)過(guò)的一些數(shù)學(xué)相似的想法(有時(shí)稱(chēng)為距離、接近度或接近度)，即計(jì)算圖上點(diǎn)之間的距離。例如，直線距離(也稱(chēng)為歐氏距離)是一個(gè)流行且熟悉的選擇。
　　KNN通過(guò)查找查詢(xún)和數(shù)據(jù)中所有示例之間的距離來(lái)工作，選擇最接近查詢(xún)的指定數(shù)字示例( K )，然后選擇最常用的標(biāo)簽(在分類(lèi)的情況下)或平均標(biāo)簽(在回歸的情況下)。
　　在分類(lèi)和回歸的情況下，我們看到為我們的數(shù)據(jù)選擇正確的K是通過(guò)嘗試幾個(gè)K并選擇最有效的一個(gè)來(lái)完成的。

KNN算法的步驟

1. 加載數(shù)據(jù)
2. 將K初始化為你選擇的鄰居數(shù)量
3. 對(duì)于數(shù)據(jù)中的每個(gè)示例
   3.1 根據(jù)數(shù)據(jù)計(jì)算查詢(xún)示例和當(dāng)前示例之間的距離。
   3.2 將示例的距離和索引添加到有序集合中
4. 按距離將距離和索引的有序集合從最小到最大(按升序)排序
5. 從已排序的集合中挑選前K個(gè)條目
6. 獲取所選K個(gè)條目的標(biāo)簽
7. 如果回歸，返回K個(gè)標(biāo)簽的平均值
8. 如果分類(lèi)，返回K個(gè)標(biāo)簽的模式'

為K選擇正確的值

??為了選擇適合你的數(shù)據(jù)的K，我們用不同的K值運(yùn)行了幾次KNN算法，并選擇K來(lái)減少我們遇到的錯(cuò)誤數(shù)量，同時(shí)保持算法在給定之前從未見(jiàn)過(guò)的數(shù)據(jù)時(shí)準(zhǔn)確預(yù)測(cè)的能力。
　　一些trick：
　　1）當(dāng)我們將K值降低到1時(shí)，我們的預(yù)測(cè)會(huì)變得不穩(wěn)定。相反，隨著K值的增加，由于多數(shù)投票/平均，我們的預(yù)測(cè)變得更加穩(wěn)定，因此更有可能做出更準(zhǔn)確的預(yù)測(cè)(直到某一點(diǎn))。最終，我們開(kāi)始看到越來(lái)越多的錯(cuò)誤。正是在這一點(diǎn)上，我們知道我們把K的價(jià)值推得太遠(yuǎn)了。
　　2）如果我們?cè)跇?biāo)簽中進(jìn)行多數(shù)投票(例如，在分類(lèi)問(wèn)題中選擇模式)，我們通常會(huì)將K設(shè)為奇數(shù)，以便有一個(gè)決勝局。'

算法優(yōu)劣

1）優(yōu)勢(shì)
　　該算法簡(jiǎn)單易行。
　　沒(méi)有必要建立模型，調(diào)整多個(gè)參數(shù)，或者做額外的假設(shè)。
　　該算法是通用的。它可以用于分類(lèi)、回歸和搜索。'

2）缺點(diǎn)
　　隨著示例和/或預(yù)測(cè)器/獨(dú)立變量數(shù)量的增加，算法變得非常慢。KNN的主要缺點(diǎn)是隨著數(shù)據(jù)量的增加變得非常慢，這使得在需要快速做出預(yù)測(cè)的環(huán)境中，變成了一個(gè)不切實(shí)際的選擇。此外，有更快的算法可以產(chǎn)生更準(zhǔn)確的分類(lèi)和回歸結(jié)果。
　　然而，如果你有足夠的計(jì)算資源來(lái)快速處理你用來(lái)預(yù)測(cè)的數(shù)據(jù)，KNN仍然有助于解決那些有依賴(lài)于識(shí)別相似對(duì)象的解決方案的問(wèn)題。

k-NN classification problem

取一個(gè)新的觀測(cè)向量x，將它分到 K 個(gè)離散的類(lèi) Ck (k=1,2,…,K) 之一。一般來(lái)說(shuō)，類(lèi)之間是互不相容的，因此，每一個(gè)觀測(cè)只能被分到一個(gè)類(lèi)中。

大間隔最近鄰居(Large margin nearest neighbor，LMNN)

大間隔最近鄰居分類(lèi)算法是統(tǒng)計(jì)學(xué)的一種機(jī)器學(xué)習(xí)算法。該算法是在k近鄰分類(lèi)其中學(xué)習(xí)一種歐式距離度量函數(shù)。基于歐式距離度量學(xué)習(xí)函數(shù)的大間隔最近鄰居分類(lèi)算法能夠很好的改善k近鄰算法分類(lèi)效果。

為什么KNN分類(lèi)中為什么有白色區(qū)域？

答：沒(méi)有獲得任何一個(gè)區(qū)域的投票
　　這白色區(qū)域應(yīng)該是KNN無(wú)法決策的區(qū)域，比如KNN的類(lèi)中有2個(gè)或2個(gè)以上的是最近的，要減少白色區(qū)域可以調(diào)整K值，或者修改最近鄰的決策條件，再或者修正距離公式。

課件中的demo

??地址：http://vision./teaching/cs231n-demos/knn/
　　1）k=1，其他參數(shù)任選，基本上不會(huì)有白色區(qū)域，因?yàn)榭偰茉趖raining data中找到最鄰近的sample和相應(yīng)的class，如果有兩個(gè)sample的距離相等，那就對(duì)應(yīng)了classes之間的邊界。
　　如下圖所示。但是k=1時(shí)，很容易出現(xiàn)過(guò)擬合。

2）k>1，如下圖所示，出現(xiàn)了該問(wèn)題中的白色區(qū)域?；卮疬@個(gè)問(wèn)題先要弄清楚，k>1時(shí)，如何預(yù)測(cè)。
　　若k=2，那么先計(jì)算得到與test sample相距最鄰近的兩個(gè)training samples，如果這兩個(gè)samples屬于相同的class，比如A，那么該test sample將被劃為class A所在的區(qū)域。 但是如果這兩個(gè)samples分別屬于不同的class，比如A和B，那么在課程的例子中，就會(huì)被劃為白色區(qū)域。 但是可以通過(guò)一些策略打破，比如當(dāng)k=7，結(jié)果中3個(gè)A class的samples，3個(gè)B class的samples和1個(gè)C class的samples，那么必須從A和B中選擇一個(gè)，而非劃為White region。
　　另外，k=2非常特殊，與k=7相比，更容易出現(xiàn)White region。比較k=2和k=7的結(jié)果，可以看出來(lái)，也很容易理解。
　　如下圖，k=2，很容易出現(xiàn)大面積的白色區(qū)域

如下圖，k=7，相比k=2，不容易出現(xiàn)白色區(qū)域