前面文章分別簡單介紹了線性回歸，邏輯回歸，貝葉斯分類，并且用python簡單實現。這篇文章介紹更簡單的 knn， k-近鄰算法（kNN，k-NearestNeighbor）。

k-近鄰算法（kNN，k-NearestNeighbor），是最簡單的機器學習分類算法之一，其核心思想在于用距離目標最近的k個樣本數據的分類來代表目標的分類（這k個樣本數據和目標數據最為相似）。

原理

kNN算法的核心思想是用距離最近(多種衡量距離的方式)的k個樣本數據來代表目標數據的分類。

具體講，存在訓練樣本集， 每個樣本都包含數據特征和所屬分類值。

輸入新的數據，將該數據和訓練樣本集匯中每一個樣本比較，找到距離最近的k個，在k個數據中，出現次數做多的那個分類，即可作為新數據的分類。

如上圖：

需要判斷綠色是什么形狀。當k等于3時，屬于三角。當k等于5是，屬于方形。

因此該方法具有一下特點：

監督學習：訓練樣本集中含有分類信息 算法簡單， 易于理解實現 結果收到k值的影響，k一般不超過20. 計算量大，需要計算與樣本集中每個樣本的距離。 訓練樣本集不平衡導致結果不準確問題

接下來用oython 做個簡單實現， 并且嘗試用于約會網站配對。

python簡單實現

def classify(inX, dataSet, labels, k):  """  定義knn算法分類器函數  :param inX: 測試數據  :param dataSet: 訓練數據  :param labels: 分類類別  :param k: k值  :return: 所屬分類  """  dataSetSize = dataSet.shape[0] #shape（m, n）m列n個特征  diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet  sqDiffMat = diffMat ** 2  sqDistances = sqDiffMat.sum(axis=1)  distances = sqDistances ** 0.5 #歐式距離  sortedDistIndicies = distances.argsort() #排序并返回index  classCount = {}  for i in range(k):    voteIlabel = labels[sortedDistIndicies[i]]    classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1 #default 0  sortedClassCount = sorted(classCount.items(), key=lambda d:d[1], reverse=True)  return sortedClassCount[0][0]

算法的步驟上面有詳細的介紹，上面的計算是矩陣運算，下面一個函數是代數運算，做個比較理解。

def classify_two(inX, dataSet, labels, k):  m, n = dataSet.shape  # shape（m, n）m列n個特征  # 計算測試數據到每個點的歐式距離  distances = []  for i in range(m):    sum = 0    for j in range(n):      sum += (inX[j] - dataSet[i][j]) ** 2    distances.append(sum ** 0.5)  sortDist = sorted(distances)  # k 個最近的值所屬的類別  classCount = {}  for i in range(k):    voteLabel = labels[ distances.index(sortDist[i])]    classCount[voteLabel] = classCount.get(voteLabel, 0) + 1 # 0:map default  sortedClass = sorted(classCount.items(), key=lambda d:d[1], reverse=True)  return sortedClass[0][0]