K-近邻算法

1.算法概述——人以群分、物以类聚：

k近邻算法（k-Nearest Neighbor，即kNN）是监督学习方法的一种，是1967年由Cover T和Hart P提出的一种基本分类与回归方法，是根据计算的不同特征值之间的某种距离（常用的距离计算方法有：欧氏距离、余弦距离、汉明距离、曼哈顿距离等等）度量进行预测。

对于给定的带有标签的训练数据集，因此我们知道训练数据集中每一个样本的数据与所属的分类的对应关系。然后输入测试样本，将新数据的与训练数据集中的样本数据进行比较，基于某种距离度量找出训练集中与其最近的k个“邻居”，然后基于这k个“邻居”的标签进行预测，这就是kNN算法中k的出处，通常k是不大于20的整数。

在做预测时，通常，在分类任务中使用“投票法”，即选择k个样本中出现最多的标签作为预测结果；在回归任务中使用“平均法”，即将k个样本的平均值作为输出结果；另外，还可基于距离远近进行加权投票或者加权平均（当预测样本的类别大小方面存在较大不同，即数据类别不平衡，这种情况下那些数据较小类别的数据点可能会被来自更大类别的数据所掩盖，预测错误的风险也就更大，为了提高准确率，可以采用加权法处理）。

如上图所示，有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是待分类的数据。

• 如果K=3，绿色圆点的最近的3个邻居是2个红色小三角形和1个蓝色小正方形，少数从属于多数，判定绿色的这个待分类点属于红色的三角形一类。
• 如果K=5，绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，判定绿色的这个待分类点属于蓝色的正方形一类。

由此可以看出，k值是该算法中重要的参数，k值的选取对预测的准确率起着至关重要的作用：

• k值太小的话，只会与最近的“邻居”匹配，并且随机噪声所产生的误差也会被放大；
• k值太大的话，会与距离更远的“邻居”匹配，因为kNN算法是利用数据中的隐含模型进行预测的，这样的话数据中隐含的模型会被忽略掉；
• 因此只有找到最合适的k值，得到最合适数量的“邻居”，才会使得误差相互抵消，有利于揭示数据中隐含的模式。
• k值的确定可以采用交叉验证的方法来确定。

2.算法优缺点：

2.1 优点

• 简单，易于理解，易于实现，无需参数估计，无需训练;
• 精度高、对异常值不敏感、无数据输入假定；
• 训练时间开销为零：kNN算法是“懒惰学习（lazy learning）”的著名代表，其没有显式的训练过程，在训练阶段仅仅是把样本数据保存起来，待收到测试样本时再进行处理。
• 适合于多分类问题(multi-modal,对象具有多个类别标签)，KNN要比SVM表现要好;

2.2 缺点

• 可解释性差，无法告诉你哪个变量更重要，无法给出决策树那样的规则;
• 计算复杂度高、空间复杂度高；
• 当预测变量过多时，在多个维度上进行处理会导致计算量大增，而且有些预测变量可能是多余的，对提高预测准确率没有什么帮助，此时可以采用裇降维技巧，只抽取最具影响力的变量用于分析。

3.实战代码：

import numpy as np
# 导入运算符模块
import operator

def creatDataset():
	"""
	创建数据集和标签
	"""
	group = np.array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
	labels = ['A', 'A', 'B', 'B']
	return group, labels

def classify(pre_data, sam_datas, sam_labels, k):
	"""
	K-近邻算法实现
	Parameters，参数说明:
	pre_data - 测试机数据
	sam_datas - 训练集样本数据集
	sam_labels - 训练集样本标签
	k - kNN算法参数
	"""
	# 取得训练样本数据集的行数
	sam_datas_size = sam_datas.shape[0]
	# 在列向量方向上重复pre_data共1次(横向)，行向量方向上重复inX共sam_datas_size次(纵向)
	# [0,0]经过np.tile([0,0],(4,1))方法得到如下数据：
	# array([[0, 0],
	#        [0, 0],
	#        [0, 0],
	#        [0, 0]])
	pre_data_process = np.tile(pre_data, (sam_datas_size, 1))
	# 计算距离,这里为欧氏距离(相减后再平方再求和再开方)
	diffMat = pre_data_process - sam_datas
	sqDiffMat = diffMat ** 2
	sqDistances = sqDiffMat.sum(axis=1)
	distances = sqDistances ** 0.5
	# 返回distances中元素从小到大排序后的索引值
	sortedDistIndicies = distances.argsort()
	classCount = {}
	for i in range(k):
		vote_label = sam_labels[sortedDistIndicies[i]]
		classCount[vote_label] = classCount.get(vote_label, 0) + 1
	# 使用sorted方法降序排序字典
	sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
	# 返回次数最多的类别,即所要分类的类别
	return sortedClassCount[0][0]

def main():
	group, labels = creatDataset()
	# 测试样本数据
	pre_data = [0,0]
	print(classify(pre_data, group, labels, 3))

if __name__ == '__main__':
	main()

输出结果为：

B

References：

• Numsense! Data Science for the Layman: No Math Added[M]
• 周志华-机器学习[M]
• 李航-统计学习方法[M]
• Machine Learning in Action[M]