K近邻算法概述

K近邻(KNN)算法是一种简单的监督学习方法，该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。

KNN 算法本身简单有效，它是一种 lazy-learning 算法，分类器不需要使用训练集进行训练，训练时间复杂度为0。KNN 分类的计算复杂度和训练集中的文档数目成正比，也就是说，如果训练集中文档总数为 n，那么 KNN 的分类时间复杂度为O(n)。

K近邻算法基本要素

K 值的选择，距离度量和分类决策规则是该算法的三个基本要素：

1. K 值的选择会对算法的结果产生重大影响。K值较小意味着只有与输入实例较近的训练实例才会对预测结果起作用，但容易发生过拟合；如果 K 值较大，优点是可以减少学习的估计误差，但缺点是学习的近似误差增大，这时与输入实例较远的训练实例也会对预测起作用，使预测发生错误。在实际应用中，K 值一般选择一个较小的数值，通常采用交叉验证的方法来选择最优的 K 值。随着训练实例数目趋向于无穷和 K=1 时，误差率不会超过贝叶斯误差率的2倍，如果K也趋向于无穷，则误差率趋向于贝叶斯误差率。通常情况下，K是不大于20的整数。
2. 该算法中的分类决策规则往往是多数表决，即由输入实例的 K 个最临近的训练实例中的多数类决定输入实例的类别
3. 距离度量一般采用 Lp 距离，当p=2时，即为欧氏距离，在度量之前，应该将每个属性的值规范化，这样有助于防止具有较大初始值域的属性比具有较小初始值域的属性的权重过大。

K近邻算法基本步骤

1. 收集样本数据集合，这些样本都是分过类的。
2. 确定样本集中各个样本对象用于分类的特征，输入一个待分类对象时，将待分类对象的对应特征与样本集中的样本特征进行比较，计算待分类样本与样本集中每个样本的距离。
3. 确定K之后，根据与待分类样本特征相似度前K个样本集中样本大部分属于哪个类别，来判断待分类样本属于哪个类别。

其中需要注意的是，样本集中样本用于分类的特征都需要设置权重来确定该特征对于分类的影响，同时还需要对特征值进行归一化，防止某个属性值过大过小对于距离的影响。

归一化的计算方式如下,下面的公式可以将任意取值范围的特征值转化为0到1区间内的值:

newValue=(oldValue – min)/(max – min)

K近邻算法使用示例

下面就通过一个简单的例子来使用K近邻算法进行分类。 在此使用python来进行分类。 首先创建一个knn.py文件来定义样本集的具体数据以及样本集中数据的分类情况。

from numpy import *
import operator

def createDateSet():
	group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
	labels = ['A','A','B','B']
	return group, labels

这样就定义了一个有A，B两个类别的样本集。 然后创建一个分类的函数，具体的功能就是使用K近邻算法将待分类对象划分到某个类别中，实现思路如下： 对未知类别属性的数据集中的每个点依次执行如下操作：

1. 计算已知类别样本集中的样本特征向量与当前待分类对象的特征向量之间的距离，在此使用欧氏距离。
2. 按照距离递增次序进行排序。
3. 选取与当前待分类对象的距离最小的k个样本集中的样本。
4. 确定这K个样本在各个类别中的出现频率。
5. 返回这K个样本出现频率最高的类别作为待分类对象的预测分类。 具体代码如下

   def classify0(inX,dataSet,labels,k):
   	dataSetSize = dataSet.shape[0]
   	diffMat = tile(inX,(dataSetSize,1)) - dataSet
   	sqDiffMat = diffMat**2
   	sqDistances = sqDiffMat.sum(axis=1)
   	distances = sqDistances**0.5
   	sortedDistIndicies = distances.argsort()
   	classCount={}
   	for i in range(k):
   		votelabel = labels[sortedDistIndicies[i]]
   		classCount[votelabel] = classCount.get(votelabel,0)+1
   	sortedClassCount = sorted(classCount.iteritems,
   	key=operator.itemgetter(1),reverse=True)
   	return sortedClassCount[0][0]​

   为了预测指定对象[0,0]的类别情况，在python提示符中输入以下命令

   knn.classify0([0,0],group,labels,3)​

   输出结果为B，则该对象被预测为B类。