KNNアルゴリズム

61756 ワード
マシン学習
KNNとは
KNN(K-nearest neighbor)、すなわちK近隣アルゴリズムである.その動作原理は非常に簡単です. 
例えば、映画に登場する戦闘シーンとキスシーンの数によって、恋愛映画とアクション映画に分けられるトレーニングセットのデータがあります.
映画のタイトル
ファイト?シーン
キスシーン
映画の種類
California Man
3
104
ラブ映画
He's Not Really into Dudes
2
100
ラブ映画
Beautiful Woman
1
81
ラブ映画
Kevin Longblade
101
10
アクションフィルム
Robo Slayer 3000
99
5
アクションフィルム
Amped II
98
2
アクションフィルム
?
18
90
不明
では、次のような未知の映画をどのように分類しますか? 
映画のタイトル
ファイト?シーン
キスシーン
映画の種類
?
18
90
不明
KNNは、新しいデータの各特徴をサンプルセットの各サンプルと比較する、サンプルとの距離を算出する方法を採用する.そしてk個の距離が最も近いサンプルを探し出す.これらのサンプルが属する分類が最も多い分類は、そのデータの分類である. 
例えば、映画「?」上記サンプルセットの各サンプルと計算する、距離を得る.Kが3を取ると「?3つの恋愛映画との距離が一番近いので、「?ラブ映画でもあります. 
アルゴリズムを以下に示す. 
アルゴリズムの詳細
PythonでKNNアルゴリズムを実現し、上述の分類問題を解決した. 
まず、アルゴリズムで使用されるデータセットを生成します.
 
     
     
      
  1. def createDataSet():
    2.  
      
  2.  '''
    3.  
      
  3.       
    4.  
      
  4.  '''
    5.  
      
  5.  group = np.array([[3, 104], [2, 100], [1, 81], [101, 10],[99, 5], [98, 2]])
    6.  
      
  6.  labels = ['A', 'A', 'A', 'D','D', 'D']
    7.  
      
  7.  return group, labels
    8.

然后写出 KNN 分类算法： 
 
     
     
      
  1. def classify0(inX, dataSet, labels, k):
    2.  
      
  2.  '''
    3.  
      
  3.  KNN   
    4.  
      
  4.  :param inX: 
    5.  
      
  5.  :param dataSet: 
    6.  
      
  6.  :param labels: 
    7.  
      
  7.  :param k: 
    8.  
      
  8.  :return: 
    9.  
      
  9.  '''
    10.  
      
  10.  dataSetSize = dataSet.shape[0]
    11.  
      
  11.  diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet
    12.  
      
  12.  sqDiffMat = diffMat ** 2
    13.  
      
  13.  sqDistances = sqDiffMat.sum(axis=1)
    14.  
      
  14.  distances = sqDistances ** 0.5
    15.  
      
  15.  sortedDistIndicies = distances.argsort()
    16.  
      
  16.  classCount = {}
    17.  
      
  17.  for i in range(k):
    18.  
      
  18.  voteIlabel = labels[sortedDistIndicies[i]]
    19.  
      
  19.  classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
    20.  
      
  20.  sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    21.  
      
  21.  print(sortedClassCount)
    22.  
      
  22.  return sortedClassCount[0][0]
    23.

KNN 算法在使用的时候，一般需要对特征数据进行归一化处理： 
 
     
     
      
  1. def autoNorm(dataSet):
    2.  
      
  2.  '''
    3.  
      
  3.     
    4.  
      
  4.  :param dataSet: 
    5.  
      
  5.  :return: 
    6.  
      
  6.  '''
    7.  
      
  7.  minVals = dataSet.min(0)
    8.  
      
  8.  maxVals = dataSet.max(0)
    9.  
      
  9.  ranges = maxVals - minVals
    10.  
      
  10.  normDataSet = np.zeros(np.shape(dataSet))
    11.  
      
  11.  m = dataSet.shape[0]
    12.  
      
  12.  normDataSet = dataSet - np.tile(minVals, (m, 1))
    13.  
      
  13.  normDataSet = normDataSet/np.tile(ranges, (m,1))
    14.  
      
  14.  return normDataSet, ranges, minVals
    15.


我们也可以使用 matplotlib 画出二维空间的散点图 
 
     
     
      
  1. def plot(dataSet):
    2.  
      
  2.  fig = plt.figure()
    3.  
      
  3.  ax = fig.add_subplot(111)
    4.  
      
  4.  ax.scatter(dataSet[:, 0], dataSet[:, 1])
    5.  
      
  5.  plt.show()
    6.


整体代码如下： 
 
     
     
      
  1. #!/usr/bin/python
    2.  
      
  2. # -*- coding: UTF-8 -*-
    3.  
      
  3. import numpy as np
    4.  
      
  4. import operator
    5.  
      
  5. import matplotlib
    6.  
      
  6. import matplotlib.pyplot as plt
    7.  
      
    8.  
      
  8. def createDataSet():
    9.  
      
  9.  '''
    10.  
      
  10.       
    11.  
      
  11.  '''
    12.  
      
  12.  group = np.array([[3, 104], [2, 100], [1, 81], [101, 10],[99, 5], [98, 2]])
    13.  
      
  13.  labels = ['A', 'A', 'A', 'D','D', 'D']
    14.  
      
  14.  return group, labels
    15.  
      
    16.  
      
  16. def classify0(inX, dataSet, labels, k):
    17.  
      
  17.  '''
    18.  
      
  18.  KNN   
    19.  
      
  19.  :param inX: 
    20.  
      
  20.  :param dataSet: 
    21.  
      
  21.  :param labels: 
    22.  
      
  22.  :param k: 
    23.  
      
  23.  :return: 
    24.  
      
  24.  '''
    25.  
      
  25.  dataSetSize = dataSet.shape[0]
    26.  
      
  26.  diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet
    27.  
      
  27.  sqDiffMat = diffMat ** 2
    28.  
      
  28.  sqDistances = sqDiffMat.sum(axis=1)
    29.  
      
  29.  distances = sqDistances ** 0.5
    30.  
      
  30.  sortedDistIndicies = distances.argsort()
    31.  
      
  31.  classCount = {}
    32.  
      
  32.  for i in range(k):
    33.  
      
  33.  voteIlabel = labels[sortedDistIndicies[i]]
    34.  
      
  34.  classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
    35.  
      
  35.  sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    36.  
      
  36.  print(sortedClassCount)
    37.  
      
  37.  return sortedClassCount[0][0]
    38.  
      
    39.  
      
  39. def autoNorm(dataSet):
    40.  
      
  40.  '''
    41.  
      
  41.     
    42.  
      
  42.  :param dataSet: 
    43.  
      
  43.  :return: 
    44.  
      
  44.  '''
    45.  
      
  45.  minVals = dataSet.min(0)
    46.  
      
  46.  maxVals = dataSet.max(0)
    47.  
      
  47.  ranges = maxVals - minVals
    48.  
      
  48.  normDataSet = np.zeros(np.shape(dataSet))
    49.  
      
  49.  m = dataSet.shape[0]
    50.  
      
  50.  normDataSet = dataSet - np.tile(minVals, (m, 1))
    51.  
      
  51.  normDataSet = normDataSet/np.tile(ranges, (m,1))
    52.  
      
  52.  return normDataSet, ranges, minVals
    53.  
      
    54.  
      
  54. def plot(dataSet):
    55.  
      
  55.  fig = plt.figure()
    56.  
      
  56.  ax = fig.add_subplot(111)
    57.  
      
  57.  ax.scatter(dataSet[:, 0], dataSet[:, 1])
    58.  
      
  58.  plt.show()
    59.  
      
    60.  
      
  60. if __name__ == '__main__':
    61.  
      
  61.  dataSet, labels = createDataSet()
    62.  
      
  62.  dataSet, _, _ = autoNorm(dataSet)
    63.  
      
  63.  print(dataSet)
    64.  
      
  64.  plot(dataSet)
    65.  
      
  65.  print(classify0([18, 90], dataSet, labels,4))
    66.

KNN

KNN . KNN . ，KNN ， . 
postGISに基づく室内地図最短経路アルゴリズム2
Leetcode: Implement strStr()