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

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

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

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

KNN算法的步驟

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

為K選擇正確的值

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

算法優(yōu)劣

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

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

k-NN classification problem

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

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

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

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

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

課件中的demo

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

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

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