簡介

鄰近算法，或者說K最近鄰(kNN，k-NearestNeighbor)分類算法是數據挖掘分類技術中最簡單的方法之一。所謂K最近鄰，就是k個最近的鄰居的意思，說的是每個樣本都可以用它最接近的k個鄰居來代表。

kNN算法的核心思想是如果一個樣本在特征空間中的k個最相鄰的樣本中的大多數屬于某一個類別，則該樣本也屬于這個類別，并具有這個類別上樣本的特性。該方法在確定分類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。 kNN方法在類別決策時，只與極少量的相鄰樣本有關。由于kNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對于類域的交叉或重疊較多的待分樣本集來說，kNN方法較其他方法更為適合。

本文將采用Python和numpy庫實現KNN的核心算法，并使用一個簡單的例子進行驗證。

KNN核心算法的實現

對于KNN算法實現，首先我們計算歐式空間距離，然后根據距離排序，找到k個緊鄰，找出最相近的分類。

from numpy import tile import operator  def do_knn_classifier(in_array, data_set, labels, k):  '''''  classify the in_array according the data set and labels  '''   #計算距離適量  data_set_size = data_set.shape[0]  diff_matrix = tile(in_array, (data_set_size, 1)) - data_set  sq_diff_matrix = diff_matrix ** 2  sq_distance = sq_diff_matrix.sum(axis=1)  distances = sq_distance ** 0.5   #argsort函數返回的是數組值從小到大的索引值， 距離排序  sorted_dist_indicies = distances.argsort()    # 選擇K個緊鄰  class_count = {}  for i in range(k):  vote_label = labels[sorted_dist_indicies[i]]  class_count[vote_label] = class_count.get(vote_label, 0) + 1   #排序，并返回最相鄰的分類  sorted_class_count = sorted(class_count.iteritems(), key=operator.itemgetter(1), reverse=True)   return sorted_class_count[0][0] 

數值的歸一化

多數情況下，由于選擇的特征值取值范圍比較大。在處理這種不同取值范圍的特征值時，通常需要采用的方法就是將數值歸一化，如將取值范圍處理到0到1或-1到1之間。下面的公式可以將任意取值范圍的特征值轉化為0到1的區(qū)間內的值：
newValue = (oldValue - min) / (max - min)
其中min和max分別是數據集中的最小特征值和最大特征值。

from numpy import tile import operator  def auto_normalize_data(data_set):  '''''  對數據集進行歸一化操作  '''  # 參數0使函數可以從列中選取最小值，而不是當前行的最小值  min_vals = data_set.min(0)  max_vals = data_set.max(0)  ranges = max_vals - min_vals    # 歸一化處理  m = data_set.shape[0]  norm_data_set = data_set - tile(min_vals, (m, 1))  norm_data_set = norm_data_set / tile(ranges, (m, 1))   return norm_data_set, ranges, min_vals