本來這篇文章是5月份寫的，今天修改了一下內容，就成今天發表的了，CSDN這是出BUG了還是什么改規則了。。。

引文 ：決策樹和基于規則的分類器都是 積極學習方法 （eager learner）的例子，因為一旦訓練數據可用，他們就開始學習從輸入屬性到類標號的映射模型。一個相反的策略是推遲對訓練數據的建模，直到需要分類測試樣例時再進行。采用這種策略的技術被稱為 消極學習法 （lazy learner）。 最近鄰分類器 就是這樣的一種方法。

注：KNN既可以用于分類，也可以用于回歸。

1.K最近鄰分類器原理

首先給出一張圖，根據這張圖來理解最近鄰分類器，如下：

根據上圖所示，有兩類不同的樣本數據，分別用 藍色的小正方形 和 紅色的小三角形 表示，而圖正中間的那個 綠色的圓 所標示的數據則是待分類的數據。也就是說，現在， 我們不知道中間那個綠色的數據是從屬于哪一類（藍色小正方形or紅色小三角形），下面，我們就要解決這個問題：給這個綠色的圓分類。

我們常說，物以類聚，人以群分，判別一個人是一個什么樣品質特征的人，常常可以從他or她身邊的朋友入手，所謂觀其友，而識其人。我們不是要判別上圖中那個綠色的圓是屬于哪一類數據么，好說，從它的鄰居下手。但一次性看多少個鄰居呢？從上圖中，你還能看到：

• 如果K=3，綠色圓點的最近的3個鄰居是2個紅色小三角形和1個藍色小正方形，少數從屬于多數，基于統計的方法，判定綠色的這個待分類點屬于紅色的三角形一類。
• 如果K=5，綠色圓點的最近的5個鄰居是2個紅色三角形和3個藍色的正方形，還是少數從屬于多數，基于統計的方法，判定綠色的這個待分類點屬于藍色的正方形一類。

于此我們看到，當無法判定當前待分類點是從屬于已知分類中的哪一類時，我們可以依據統計學的理論看它所處的位置特征，衡量它周圍鄰居的權重，而把它歸為(或分配)到權重更大的那一類。這就是K近鄰算法的核心思想。其關鍵還在于K值的選取，所以應當謹慎。

KNN算法中，所選擇的鄰居都是已經正確分類的對象。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。

KNN 算法本身簡單有效，它是一種 lazy-learning 算法，分類器不需要使用訓練集進行訓練，訓練時間復雜度為0。KNN 分類的計算復雜度和訓練集中的文檔數目成正比，也就是說，如果訓練集中文檔總數為 n，那么 KNN 的分類時間復雜度為O(n)。

前面的例子中強調了選擇合適的K值的重要性。如果太小，則最近鄰分類器容易受到訓練數據的噪聲而產生的過分擬合的影響；相反，如果K太大，最近分類器可能會誤會分類測試樣例，因為最近鄰列表中可能包含遠離其近鄰的數據點。（如下圖所示）

?

K較大時的最近鄰分類

            
from numpy import *
import operator

class KNN:
  def createDataset(self):
    group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
    labels = ['A','A','B','B']
    return group,labels

  def KnnClassify(self,testX,trainX,labels,K):
    [N,M]=trainX.shape

  #calculate the distance between testX and other training samples
    difference = tile(testX,(N,1)) - trainX # tile for array and repeat for matrix in Python, == repmat in Matlab
    difference = difference ** 2 # take pow(difference,2)
    distance = difference.sum(1) # take the sum of difference from all dimensions
    distance = distance ** 0.5
    sortdiffidx = distance.argsort()

  # find the k nearest neighbours
    vote = {} #create the dictionary
    for i in range(K):
      ith_label = labels[sortdiffidx[i]];
      vote[ith_label] = vote.get(ith_label,0)+1 #get(ith_label,0) : if dictionary 'vote' exist key 'ith_label', return vote[ith_label]; else return 0
    sortedvote = sorted(vote.iteritems(),key = lambda x:x[1], reverse = True)
    # 'key = lambda x: x[1]' can be substituted by operator.itemgetter(1)
    return sortedvote[0][0]

k = KNN() #create KNN object
group,labels = k.createDataset()
cls = k.KnnClassify([0,0],group,labels,3)
print cls
          

            
>>>import os
>>>os.chdir("/home/liudiwei/code/data_miningKNN/")
>>>execfile("KNN.py")
          

            
$ python KNN.py
          

            
>>>import KNN
>>> KNN.k.KnnClassify([0,0],KNN.group,KNN.labels,3)