文章原創(chuàng),最近更新：2018-06-25
1.k近鄰算法的初步了解
2.k近鄰算法的基本概念，原理以及應(yīng)用
3.k近鄰算法中k的選取以及特征歸一化的重要性
4.將kNN分類器用于的場景
5.將kNN分類器用于的場景
6.本文的一點總結(jié)
參考鏈接:
1、 一文搞懂k近鄰（k-NN）算法（一）
2、K-最近鄰算法的應(yīng)用
3、距離產(chǎn)生美？k近鄰算法python實現(xiàn)
4、06 K-近鄰算法，初中生也能理解的機(jī)器學(xué)習(xí)
5、k-近鄰算法
前言：通過網(wǎng)上找的文章,通過歸納總結(jié)具體如下:
1.k近鄰算法的初步了解
設(shè)想你想了解一個陌生人的飲食風(fēng)格，如果你對他所知無幾，那么最容易想到的一個捷徑就是看看他生存的周圍人群的口味。但是如果你對他的信息知道更多，例如知道他的年齡、收入等，那么這個時候就最好從他周圍的人群中去挑選與他年齡、收入相近的人的飲食風(fēng)格，這樣預(yù)測會更準(zhǔn)確一點。這其中蘊含的算法就是最近鄰算法。
最近鄰算法的思想很簡單，”距離“相近的事物總會具有更多的共性。其中涉及的數(shù)學(xué)知識并不深厚。
要想運用最近鄰算法解決問題，得明確要個要點,具體如下:
- 一是設(shè)定一種距離的定義，這個距離可能是物理距離，也可能是實際屬性之間的抽象距離；
- 二是要假定物以類聚人以群分，即距離相近的事物總是有更多的共性。
最近鄰算法是一種預(yù)測型算法，它在實際操作中會忽略很多要素，只是給出結(jié)論而并不會描述結(jié)論的具體推理。例如，預(yù)測一個人的飲食風(fēng)格只是根據(jù)與他相近的人來預(yù)測的，而并沒有說明這個人的年齡、收入是如何影響他的飲食風(fēng)格的。
為什么要設(shè)置成K近鄰呢？這是因為在實際操作中，我們要首先確定一個合理的K值，假如我們需要預(yù)測一個事物的某項特征，找出被預(yù)測事物的K個最近鄰，然后讓這K個最近鄰對預(yù)測結(jié)果進(jìn)行投票，最終去投票最高的作為預(yù)測結(jié)果。
2.k近鄰算法的基本概念，原理以及應(yīng)用
k近鄰算法是一種基本分類和回歸方法。本篇文章只討論分類問題的k近鄰法。
k近鄰算法，即是給定一個訓(xùn)練數(shù)據(jù)集，對新的輸入實例，在訓(xùn)練數(shù)據(jù)集中找到與該實例最鄰近的k個實例，這k個實例的多數(shù)屬于某個類，就把該輸入實例分類到這個類中。（這就類似于現(xiàn)實生活中少數(shù)服從多數(shù)的思想）根據(jù)這個說法，咱們來看下引自維基百科上的一幅圖：
如上圖所示，有兩類不同的樣本數(shù)據(jù)，分別用藍(lán)色的小正方形和紅色的小三角形表示，而圖正中間的那個綠色的圓所標(biāo)示的數(shù)據(jù)則是待分類的數(shù)據(jù)。
這也就是我們的目的，來了一個新的數(shù)據(jù)點，我要得到它的類別是什么？好的，下面我們根據(jù)k近鄰的思想來給綠色圓點進(jìn)行分類。
如果k=3，綠色圓點的最鄰近的3個點是2個紅色小三角形和1個藍(lán)色小正方形，少數(shù)從屬于多數(shù)，基于統(tǒng)計的方法，判定綠色的這個待分類點屬于紅色的三角形一類。
如果k=5，綠色圓點的最鄰近的5個鄰居是2個紅色三角形和3個藍(lán)色的正方形，還是少數(shù)從屬于多數(shù)，基于統(tǒng)計的方法，判定綠色的這個待分類點屬于藍(lán)色的正方形一類。
從上面例子我們可以看出，k近鄰的算法思想非常的簡單，也非常的容易理解，那么我們是不是就到此結(jié)束了，該算法的原理我們也已經(jīng)懂了，也知道怎么給新來的點如何進(jìn)行歸類，只要找到離它最近的k個實例，哪個類別最多即可。
哈哈，沒有這么簡單啦，算法的核心思想確實是這樣，但是要想一個算法在實際應(yīng)用中work，需要注意的不少額~比如k怎么確定的，k為多少效果最好呢？所謂的最近鄰又是如何來判斷給定呢？
3.k近鄰算法中k的選取以及特征歸一化的重要性
3.1選取k值以及它的影響
k近鄰的k值我們應(yīng)該怎么選取呢？
如果我們選取較小的k值，那么就會意味著我們的整體模型會變得復(fù)雜，容易發(fā)生過擬合！恩結(jié)論說完了，太抽象了吧你，不上圖講解號稱通俗講解的都是流氓
好吧，那我就上圖來講解假設(shè)我們選取k=1這個極端情況，怎么就使得模型變得復(fù)雜，又容易過擬合了呢？
假設(shè)我們有訓(xùn)練數(shù)據(jù)和待分類點如下圖：
上圖中有倆類，一個是黑色的圓點，一個是藍(lán)色的長方形，現(xiàn)在我們的待分類點是紅色的五邊形。
好，根據(jù)我們的k近鄰算法步驟來決定待分類點應(yīng)該歸為哪一類。我們由圖中可以得到，很容易我們能夠看出來五邊形離黑色的圓點最近，k又等于1，那太好了，我們最終判定待分類點是黑色的圓點。
由這個處理過程我們很容易能夠感覺出問題了，如果k太小了，比如等于1，那么模型就太復(fù)雜了，我們很容易學(xué)習(xí)到噪聲，也就非常容易判定為噪聲類別，而在上圖，如果，k大一點，k等于8，把長方形都包括進(jìn)來，我們很容易得到我們正確的分類應(yīng)該是藍(lán)色的長方形！如下圖：
所謂的過擬合就是在訓(xùn)練集上準(zhǔn)確率非常高，而在測試集上準(zhǔn)確率低，經(jīng)過上例，我們可以得到k太小會導(dǎo)致過擬合，很容易將一些噪聲（如上圖離五邊形很近的黑色圓點）學(xué)習(xí)到模型中，而忽略了數(shù)據(jù)真實的分布！
如果我們選取較大的k值，就相當(dāng)于用較大鄰域中的訓(xùn)練數(shù)據(jù)進(jìn)行預(yù)測，這時與輸入實例較遠(yuǎn)的（不相似）訓(xùn)練實例也會對預(yù)測起作用，使預(yù)測發(fā)生錯誤，k值的增大意味著整體模型變得簡單。
k值增大怎么就意味著模型變得簡單了，不要急，我會解釋的！
哈哈。我們想，如果k=N（N為訓(xùn)練樣本的個數(shù)）,那么無論輸入實例是什么，都將簡單地預(yù)測它屬于在訓(xùn)練實例中最多的類。這時，模型是不是非常簡單，這相當(dāng)于你壓根就沒有訓(xùn)練模型呀！直接拿訓(xùn)練數(shù)據(jù)統(tǒng)計了一下各個數(shù)據(jù)的類別，找最大的而已！這好像下圖所示：
我們統(tǒng)計了黑色圓形是8個，長方形個數(shù)是7個，那么哈哈，如果k=N，我就得出結(jié)論了，紅色五邊形是屬于黑色圓形的（明顯是錯誤的好不）
這個時候，模型過于簡單，完全忽略訓(xùn)練數(shù)據(jù)實例中的大量有用信息，是不可取的。
恩，k值既不能過大，也不能過小，在我舉的這個例子中，我們k值的選擇，在下圖紅色圓邊界之間這個范圍是最好的，如下圖：
（注：這里只是為了更好讓大家理解，真實例子中不可能只有倆維特征，但是原理是一樣的1，我們就是想找到較好的k值大?。?/strong>
那么我們一般怎么選取呢？李航博士書上講到，我們一般選取一個較小的數(shù)值，通常采取 交叉驗證法來選取最優(yōu)的k值。（也就是說，選取k值很重要的關(guān)鍵是實驗調(diào)參，類似于神經(jīng)網(wǎng)絡(luò)選取多少層這種，通過調(diào)整超參數(shù)來得到一個較好的結(jié)果）
3.2距離的度量
在上文中說到，k近鄰算法是在訓(xùn)練數(shù)據(jù)集中找到與該實例最鄰近的k個實例，這k個實例的多數(shù)屬于某個類，我們就說預(yù)測點屬于哪個類。
定義中所說的最鄰近是如何度量呢？我們怎么知道誰跟測試點最鄰近。這里就會引出我們幾種度量倆個點之間距離的標(biāo)準(zhǔn)。
我們可以有以下幾種度量方式：
其中當(dāng)p=2的時候，就是我們最常見的歐式距離，我們也一般都用歐式距離來衡量我們高維空間中倆點的距離。
在實際應(yīng)用中，距離函數(shù)的選擇應(yīng)該根據(jù)數(shù)據(jù)的特性和分析的需要而定，一般選取p=2歐式距離表示，這不是本文的重點。
在實際應(yīng)用中，距離函數(shù)的選擇應(yīng)該根據(jù)數(shù)據(jù)的特性和分析的需要而定，一般選取p=2歐式距離表示，這不是本文的重點。
3.3特征歸一化的必要性
所以我們應(yīng)該讓每個特征都是同等重要的！這也是我們要歸一化的原因！歸一化公式如下：
講到這里，k近鄰算法基本內(nèi)容我們已經(jīng)講完了。除去之后為了提高查找效率提出的kd樹外，算法的原理，應(yīng)用等方面已經(jīng)講解完畢，由于每篇文章內(nèi)容不宜太多，kd樹等知識下篇講解，這里總結(jié)一下本文講的內(nèi)容。
4.將kNN分類器用于的場景
人們將kNN分類器用于：
- Amazon上的物品推薦
- 消費者信貸風(fēng)險的評估
- 利用圖像分析技術(shù)對地表分類
- 人臉識別
- 識別圖像中的人物性別
- 推薦Web網(wǎng)頁
- 推薦度假套餐
5.將kNN分類器用于的場景
其實，kNN算法非常簡單，可以說在訓(xùn)練過程中基本沒有算法參與，只有存儲訓(xùn)練樣本。可以說KNN算法實際上是一種識記類算法。因此，kNN雖然簡單，但是其明顯包含了以下幾個缺點：
整個訓(xùn)練過程需要將所有的訓(xùn)練樣本極其輸出label存儲起來，因此，空間成本很大。
測試過程中，每個測試樣本都需要與所有的訓(xùn)練樣本進(jìn)行比較，運行時間成本很大。
采用距離比較的方式，分類準(zhǔn)確率不高。
6.本文的一點總結(jié)
1.我們提出了k近鄰算法，算法的核心思想是，即是給定一個訓(xùn)練數(shù)據(jù)集，對新的輸入實例，在訓(xùn)練數(shù)據(jù)集中找到與該實例最鄰近的k個實例，這k個實例的多數(shù)屬于某個類，就把該輸入實例分類到這個類中。
更通俗說一遍算法的過程，來了一個新的輸入實例，我們算出該實例與每一個訓(xùn)練點的距離（這里的復(fù)雜度為0(n)比較大，所以引出了下文的kd樹等結(jié)構(gòu)），然后找到前k個，這k個哪個類別數(shù)最多，我們就判斷新的輸入實例就是哪類！
2.與該實例最近鄰的k個實例，這個最近鄰的定義是通過不同距離函數(shù)來定義，我們最常用的是歐式距離。
3.為了保證每個特征同等重要性，我們這里對每個特征進(jìn)行歸一化。
4.k值的選取，既不能太大，也不能太小，何值為最好，需要實驗調(diào)整參數(shù)確定！
