算法简介
KNN（k-NearestNeighbor ）算法是数据挖掘算法中最简单的算法之一，K代表最邻近的邻居，一个样本的列表可以根据最邻近的K个邻居的分类决定。KNN的核心思想就是一个样本在特征向量空间中k个最相邻的样本中大多数属于哪个类别，那我们就说这个样本属于哪个类别。
算法优点
1.简单，易于理解，易于实现，无需估计参数，无需训练；
- 适合对稀有事件进行分类；
3.特别适合于多分类问题(multi-modal,对象具有多个类别标签)， kNN比SVM的表现要好。
算法缺点
1.当样本数量不平衡时，一个类的样本容量特别大，其他类的样本容量特别小，影响分类效果。
2.计算量大，需要计算待分类样本与全部已知的所有分类样本的距离，才能得到与待分类样本最近的K个样本。
3.可理解性查。
算法改进
kNN计算量大，非常占用内存的问题，对于大规模的数据，效率惨不忍睹。
就样本数据本身来改进，由于kNN善于处理稀有事件和多类别问题（MLkNN）所以适合类域的交叉或重叠较多的。样本容量比较大的数据集。另外可以考虑压缩训练样本量，像浓缩技术(condensing)和编辑技术(editing)等都能大幅减少训练样本量，同时又能很好的保持分类精度。
4.算法实现：
from numpy import *
import operator
import KNN
def createDataSet():
# 创建训练集
group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
labels = ['A', 'A', 'B', 'B']
return group, labels
def classify0(inX, dataSet, labels, k):
dataSetSize = dataSet.shape[0]
print("dataSetSize=",dataSetSize)
# 根据欧式距离计算训练集中每个样本到测试点的距离
# Numpy的 tile() 函数，就是将原矩阵横向、纵向地复制
diffMat = tile(inX, (dataSetSize, 1)) - dataSet
sqDiffMat = diffMat ** 2
sqDistances = sqDiffMat.sum(axis=1)#按行求和
print("sqDistances=",sqDistances)
distances = sqDistances ** 0.5#再开方
print("distances=",distances)
# 计算完所有点的距离后，对数据按照从小到大的次序排序 argsort返回的是索引值
sortedDistIndicies = distances.argsort()
print("sortedDistIndicies=",sortedDistIndicies)
# 确定前k个距离最小的元素所在的主要分类，最后返回发生频率最高的元素类别
classCount = {}
for i in range(k):
voteIlabel = labels[sortedDistIndicies[i]]
classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
# operator.itemgetter(1)根据数据的第1维排序，第1维的为分类出现的次数
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
if __name__ == '__main__':
group,labes = KNN.createDataSet()
print("group=",group)
print("labels",labes)
print(KNN.classify0([0,0],group,labes,3))
输出：
group=
[[1. 1.1]
[1. 1. ]
[0. 0. ]
[0. 0.1]]
labels ['A', 'A', 'B', 'B']
dataSetSize= 4
sqDistances= [2.21 2. 0. 0.01]
distances= [1.48660687 1.41421356 0. 0.1 ]
sortedDistIndicies= [2 3 1 0]
B
