KNN算法

• • 1.算法概述
  • 2.算法步骤
  • 3.算法实现
  • 4.算法优化

1.算法概述

• k最近邻算法(k-NearestNeighbor，kNN)，顾名思义，即由某样本k个邻居的类别来推断出该样本的类别。
• 给定测试样本，基于特定的某种距离度量方式找到与训练集中最接近的k个样本，然后基于这k个样本的类别进行预测。

2.算法步骤

1. 准备数据，对数据进行预处理
2. 选用合适的测试元组和合适的数据存储结构训练数据
3. 维护一个大小为k，按距离由大到小的优先级队列，用于存储最近邻训练元组。随机从训练元组中选取k个元组作为初始的最近邻元组，分别计算测试元组到这k个元组的距离，将训练元组标号和距离存入优先级队列
4. 遍历训练元组集，计算当前训练元组与测试元组的距离。之后将所得距离L与优先级队列中的最大距离L_max进行比较。若L≥L_max，则舍弃该元组，遍历下一个元组。若L<L_max，删除优先级队列中最大距离的元组，将当前训练元组存入优先级队列
5. 遍历完毕后，计算优先级队列中k 个元组的多数类，并将其作为测试元组的类别
6. 测试元组集测试完毕后计算误差率，继续设定不同的k值重新进行训练，最后取误差率最小的k值

3.算法实现

• 自定义实现

  from numpy import *
  
  def createDataSet():
      # 构造训练集
      group = array([[90, 100], [88, 90], [85, 95], [10, 20], [30, 40], [50, 30]])
      # 样本点数据
      labels = ['A', 'A', 'A', 'D', 'D', 'D']
  
      return group, labels
  
  
  def KNNClassify(newInput, dataSet, labels, k):
      # 记录训练集个数
      nums = dataSet.shape[0]
  
      # 计算欧氏距离
      diff = tile(newInput, (nums, 1)) - dataSet  # 计算元素属性值得差
      squaredDiff = diff ** 2  # 对差值取平方
      squaredDist = sum(squaredDiff, axis=1)  # 按行求和
      distance = squaredDist ** 0.5  # 计算距离
  
      # 对距离进行排序(升序)
      sortedDistIndices = argsort(distance)
  
      classCount = {}
      for i in range(k):
          # 选择k个最短距离
          voteLabel = labels[sortedDistIndices[i]]
          # 记录累计的出现次数
          classCount[voteLabel] = classCount.get(voteLabel, 0) + 1
  
      # 投票数最多的分类
      maxCount = 0
      maxIndex = 0
  
      for key, value in classCount.items():
          if value > maxCount:
              maxCount = value
              maxIndex = key
  
      return maxIndex
  
  
  # 创建训练集和样本点
  dataSet, labels = createDataSet()
  
  # 测试集1
  testX = array([15, 50])
  k = 3
  outputLabel = KNNClassify(testX, dataSet, labels, k)
  print("第一组测试数据为：", testX, ",分类结果为：", outputLabel)
  
  # 测试集2
  testX = array([80, 70])
  k = 3
  outputLabel = KNNClassify(testX, dataSet, labels, k)
  print("第二组测试数据为：", testX, ",分类结果为：", outputLabel)
  

• 利用Sklearn库实现

  from sklearn import neighbors, datasets
  
  # 初始化K近邻分类器
  knn = neighbors.KNeighborsClassifier()
  
  # 加载数据集
  iris = datasets.load_iris()
  print(iris)
  
  # 讲训练数据集和标签种类进行归类学习
  knn.fit(iris.data, iris.target)
  
  # 测试样本预测
  predictedLabel = knn.predict([[0.1, 0.2, 0.3, 0.4]])
  print(predictedLabel)
  

4.算法优化

• 引入邻居权值

  为了优化KNN的分类效果，可以在其中引入权值机制作为对样本距离机制的补充。

  基本思想是：为与测试样本距离更小的邻居设置更大的权值，衡量权值累积以及训练样本集中各种分类的样本数目，来对算法中的K值进行调整，进而达到更合理或者平滑的分类效果。

• 特征降维与模式融合

  KNN算法的主要缺点是，当训练样本数量很大时将导致很高的计算开销。

  为了对KNN的分类效率进行优化，可以在数据预处理阶段利用一些降维算法或者使用特征融合算法，对KNN训练样本集的维度进行简化，排除对分类结果影响较小的属性。通过优化训练样本集的分类，提高得出待分类样本类别的效率。该改进经常在类域的样本容量比较大时使用。