海綿寶寶：“派大星，你為什麼叫派大星”
派大星：“因為我是上帝拍下來保護你的大星星”
歡迎通路我的部落格
Sky’s blog
一、Concept
1.1Language Description
K最近鄰(k-Nearest Neighbor，KNN)分類算法，是一個理論上比較成熟的方法，也是最簡單的機器學習算法之一。該方法的思路是：如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數屬于某一個類别，則該樣本也屬于這個類别。即是給定一個訓練資料集，對新的輸入執行個體，在訓練資料集中找到與該執行個體最鄰近的K個執行個體（也就是所說的K個鄰居）， 這K個執行個體的多數屬于某個類，就把該輸入執行個體分類到這個類中。
KNN 算法的核心思想和最近鄰算法思想相似，都是通過尋找和未知樣本相似的類别進行分類。但 NN 算法中隻依賴 1 個樣本進行決策，在分類時過于絕對，會造成分類效果差的情況，為解決 NN 算法的缺陷，KNN 算法采用 K 個相鄰樣本的方式共同決策未知樣本的類别,這樣在決策中容錯率相對于 NN 算法就要高很多，分類效果也會更好。
1.2 graphic
例子：要區分“貓”和“狗”，通過“claws”和“sound”兩個feature來判斷的話，圓形和三角形是已知分類的了，那麼這個“star”代表的是哪一類呢？
k＝3時，這三條線連結的點就是最近的三個點，那麼圓形多一些，是以這個star就是屬于貓。
二、Algorithmic Description
1.pseudo code
2.steps
- 初始化距離為最大值
- 計算未知樣本和每個訓練樣本的距離dist
- 得到目前K個最鄰近樣本中的最大距離maxdist
- 如果dist小于maxdist，則将該訓練樣本作為K-最近鄰樣本
- 重複步驟2,3,4，直到未知樣本和所有訓練樣本的距離都算完
- 統計K個最近鄰樣本中每個類别出現的次數
- 選擇出現頻率最大的類别作為未知樣本的類别
三、KNN‘s three elements of model
1.Distance measure
距離度量，說白了就是距離計算公式。
常見的距離計算公式有如下：
1.歐氏距離
2.曼哈頓距離
3.餘弦距離
4.皮爾遜系數
5.傑卡德距離
6.闵可夫斯基距離
7.切比雪夫距離
8.漢明距離
9.萊文斯坦距離
1.1Euclidean distance
歐氏距離是最常見的兩點之間或多點之間的距離表示法，又稱之為歐幾裡得度量，它定義于歐幾裡得空間中，是闵可夫斯基距離=2特殊情形.
def d_euc(x, y):
d = np.sqrt(np.sum(square(x - y)))
return d
1.2Manhattan Distance
def d_man(x, y):
d = np.sum(abs(x - y))
return d
2.Selection of K Value
不要小看了這個K值選擇問題，因為它對K近鄰算法的結果會産生重大影響。
如果選擇較小的K值，就相當于用較小的領域中的訓練執行個體進行預測，“學習”近似誤差會減小，隻有與輸入執行個體較近或相似的訓練執行個體才會對預測結果起作用，與此同時帶來的問題是“學習”的估計誤差會增大，換句話說，K值的減小就意味着整體模型變得複雜，容易發生過拟合；
如果選擇較大的K值，就相當于用較大領域中的訓練執行個體進行預測，其優點是可以減少學習的估計誤差，但缺點是學習的近似誤差會增大。這時候，與輸入執行個體較遠（不相似的）訓練執行個體也會對預測器作用，使預測發生錯誤，且K值的增大就意味着整體的模型變得簡單。
K=N，則完全不足取，因為此時無論輸入執行個體是什麼，都隻是簡單的預測它屬于在訓練執行個體中最多的累，模型過于簡單，忽略了訓練執行個體中大量有用資訊。
3.Classification Decision Rules
1.多數表決法
多數表決法類似于投票的過程，也就是在 K 個鄰居中選擇類别最多的種類作為測試樣本的類别。
2.權重表決法
根據距離的遠近，對近鄰的投票進行權重，距離越近則權重越大，通過權重計算結果最大值的類為測試樣本的類别。