K近鄰算法概述

K近鄰(KNN)算法是一種簡單的監督學習方法，該方法的思路是：如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數屬于某一個類別，則該樣本也屬于這個類別。

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

K近鄰算法基本要素

K 值的選擇，距離度量和分類決策規則是該算法的三個基本要素：

1. K 值的選擇會對算法的結果產生重大影響。K值較小意味著只有與輸入實例較近的訓練實例才會對預測結果起作用，但容易發生過擬合；如果 K 值較大，優點是可以減少學習的估計誤差，但缺點是學習的近似誤差增大，這時與輸入實例較遠的訓練實例也會對預測起作用，使預測發生錯誤。在實際應用中，K 值一般選擇一個較小的數值，通常采用交叉驗證的方法來選擇最優的 K 值。隨著訓練實例數目趨向于無窮和 K=1 時，誤差率不會超過貝葉斯誤差率的2倍，如果K也趨向于無窮，則誤差率趨向于貝葉斯誤差率。通常情況下，K是不大于20的整數。
2. 該算法中的分類決策規則往往是多數表決，即由輸入實例的 K 個最臨近的訓練實例中的多數類決定輸入實例的類別
3. 距離度量一般采用 Lp 距離，當p=2時，即為歐氏距離，在度量之前，應該將每個屬性的值規范化，這樣有助于防止具有較大初始值域的屬性比具有較小初始值域的屬性的權重過大。

K近鄰算法基本步驟

1. 收集樣本數據集合，這些樣本都是分過類的。
2. 確定樣本集中各個樣本對象用于分類的特征，輸入一個待分類對象時，將待分類對象的對應特征與樣本集中的樣本特征進行比較，計算待分類樣本與樣本集中每個樣本的距離。
3. 確定K之后，根據與待分類樣本特征相似度前K個樣本集中樣本大部分屬于哪個類別，來判斷待分類樣本屬于哪個類別。

其中需要注意的是，樣本集中樣本用于分類的特征都需要設置權重來確定該特征對于分類的影響，同時還需要對特征值進行歸一化，防止某個屬性值過大過小對于距離的影響。

歸一化的計算方式如下,下面的公式可以將任意取值范圍的特征值轉化為0到1區間內的值:

newValue=(oldValue – min)/(max – min)

K近鄰算法使用示例

下面就通過一個簡單的例子來使用K近鄰算法進行分類。 在此使用python來進行分類。 首先創建一個knn.py文件來定義樣本集的具體數據以及樣本集中數據的分類情況。

from numpy import *
import operator

def createDateSet():
	group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
	labels = ['A','A','B','B']
	return group, labels

這樣就定義了一個有A，B兩個類別的樣本集。 然后創建一個分類的函數，具體的功能就是使用K近鄰算法將待分類對象劃分到某個類別中，實現思路如下： 對未知類別屬性的數據集中的每個點依次執行如下操作：

1. 計算已知類別樣本集中的樣本特征向量與當前待分類對象的特征向量之間的距離，在此使用歐氏距離。
2. 按照距離遞增次序進行排序。
3. 選取與當前待分類對象的距離最小的k個樣本集中的樣本。
4. 確定這K個樣本在各個類別中的出現頻率。
5. 返回這K個樣本出現頻率最高的類別作為待分類對象的預測分類。 具體代碼如下

   def classify0(inX,dataSet,labels,k):
   	dataSetSize = dataSet.shape[0]
   	diffMat = tile(inX,(dataSetSize,1)) - dataSet
   	sqDiffMat = diffMat**2
   	sqDistances = sqDiffMat.sum(axis=1)
   	distances = sqDistances**0.5
   	sortedDistIndicies = distances.argsort()
   	classCount={}
   	for i in range(k):
   		votelabel = labels[sortedDistIndicies[i]]
   		classCount[votelabel] = classCount.get(votelabel,0)+1
   	sortedClassCount = sorted(classCount.iteritems,
   	key=operator.itemgetter(1),reverse=True)
   	return sortedClassCount[0][0]?

   為了預測指定對象[0,0]的類別情況，在python提示符中輸入以下命令

   knn.classify0([0,0],group,labels,3)?

   輸出結果為B，則該對象被預測為B類。