MachineLearning-KNN

发表于 | 分类于

Machine Learning-KNN

标签 ： MachineLearning 人工智能

算法概述

  k-临近算法(k-Nearest Neighbor)属于有监督算法中分类算法。虽然是机器学习中一个思路简单，直观的分类器，但是其在样本质量良好的基础上，有精度高，对异常值不敏感，无数据输入假定的优点，但是也有计算复杂度高，空间复杂度高的缺点。其适用范围为离散的数值型和均趁型数据。

算法思路

  KNN的工作机制非常简单，其工作原理是：存在一个样本数据集合（训练样本集），样本集中每个数据都存在标签，即我们知道样本集合每一数据与所属分类的对应关系。对于需要分类处理的新样本，我们将新数据的N维特征与样本集中的对应的N维特征进行比较，基于某种距离量找出训练集中与其最近的k个训练样本，然后基于这k个样本的标签进行预测。预测的通常方法是选择k个样本中样本中出现最多的类别标记作为预测结果；在回归任务中，可使用“平均法”，即将k个样本的实值输出标记的平均值作为预测结果；还可以基于距离远近进行加权平均或加权投票。
  需要注意的是，KNN没有显式的训练过程，是“LazyLearning”的代表，此类学习算法仅仅是把样本保存起来，训练时间开销为零，待收到测试样本后再进行处理；而“EagerLearning”则是在训练阶段就对样本进行学习和处理。
  最邻近分类器作为KNN的特例，虽然简单，但是其泛化错误率并没有超过贝叶斯最优分类器的错误率的两倍。此部分的简化证明见西瓜书，更严格的证明参阅[cover and hart,1967]。

算法实现

  KNN算法的实现参考《Machine Learning in Action》.
  核心算法分为三步进行处理，首先计算新样本点到各样本集点的距离，然后选择距离最小的k个点，并选择出k个点中标签个数最多的点作为新样本的标签。本文的KNN是基于特征数N=2的样本集实现的，采用了欧式距离，计算两个向量点之间的距离，并采用k=3进行处理。
  书中的实现代码使用了几个技巧进行数据的处理。

1
diffMat = tile(inX,(dataSetSize,1)) - dataSet

   此处使用了”tile( )”函数对新样本进行扩充处理。

1
sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1), reverse=True)

   此处使用operator.itemgetter函数定义了一个函数，通过该函数作用到对象上才能获取值。对于operator.itemgetter(m,n)，其作用是获取对象的第m个域和第n个的值。sorted函数的函数原型是:
sorted(iterable[, cmp[, key[, reverse]]])
  第一个参数iterable指定要排序的list或者iterable；
  第二个参数cmp为函数，指定排序时进行比较的函数，可以指定一个函数或者lambda函数
  key为函数，指定取待排序元素的哪一项进行排序，函数用上面的例子来说明
  reverse参数是一个bool变量，表示升序还是降序排列，默认为false（升序排列）
  具体核心代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def classify(inX,dataSet,labels,k):
    dataSetSize = dataSet.shape[0]
    diffMat = tile(inX,(dataSetSize,1)) - dataSet   # add one row
    sqDiffMAt = diffMat ** 2
    sqDistance = sqDiffMAt.sum(axis=1)
    distance = sqDistance ** 0.5
    sortedDistIndicies = distance.argsort()
    classCount={}
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
    sortedClassCount = sorted(classCount.iteritems(),
     key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

  检验代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import KNN_1
import matplotlib
from numpy import *
import matplotlib.pyplot as plt

group,labers=KNN_1.creatDataSet()
test = array([0.8,0.5])
aimLaber=KNN_1.classify(test,group,labers,3)

print aimLaber
plt.plot(group[:,0],group[:,1],'ro')
plt.plot(test[0],test[1],'bo')
plt.axis([0, 2, 0, 2])
plt.show()

得到输出标签为A，显示图像如下：
images

算法应用

  在应用KNN时，由于数据的各维度之间的取值范围有一定的差别，如果直接使用，则可能可能出现某些属性对于距离计算有很大的影响，从而使得预测结果不准确，为了防止此类问题的发生，应该对于各属性进行离散化处理之后在进行合适距离的计算。
  《Machine Learning in Action》中对于KNN的进阶算法是利用其进行手写识别，实现方法是将3232的图像转化为11024的向量进行计算，书中样例的错误率为1.2%.但是同时说明，实现此算法的执行效率并不高，因为数据属性的维度高达1024，并且需要较大的储存空间储存样本。

算法小结

  KNN是分类数据最简单最有效的算法，是基于实例的学习，使用是必须有接近实际数据的训练样本数据。此外必须对数据集中的每个数据计算距离值，如果样本属性的维度本来就很高，则会非常耗时；其另一个缺陷是无法给出任何数据的基础结构信息，因此我们也无法知道平均实例样本和典型实例样本具有的特征。