简介
KNN（K-Nearest Neighbors）算法是当前主流的分类算法之一，最初有Cover和Hart于1968年提出。
基本思想
有那么一堆已经知道类别的数据，当有一个新数据进入时，依次计算这个数据和每个训练数据的距离，然后挑出离这个数据最近的K个点，看看这个K个点属于什么类型，然后用少数服从多数的原则，给新数据归类。
算法实现
实现步骤
- 构建训练数据集(数据标准化)；
- 计算训练数据集中的点与当前点的距离；
- 按照距离递增排序；
- 选取距离与当前距离最小的K个点；
- 确定前K个点中所在类别的出现概率；
- 返回前K个点中出现概率最高的类别作为当前点的分类。
Python代码实现：
import numpy as np
import operator
def createDataSet():
"""
构造训练数据，产生4条训练样本，group为样本属性，labels为分类标签
"""
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(inX, dataSet, labels, k):
"""
简单KNN分类
:param inX: 待分类向量
:param dataSet: 训练样本集
:param labels: 训练样本标签
:param k: K值
:return:
"""
dataSetSize = dataSet.shape[0] # 训练样本个数
diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet # 计算训练样本和待分类样本的数值差值
sqDiffMat = diffMat ** 2 # 差值的平方
sqDistances = sqDiffMat.sum(axis=1) # 平方和
distances = sqDistances ** 0.5 # 平方和开方
sortedDistIndicies = distances.argsort() # 返回升序排列后的索引
classCount = {}
# 统计前K个样本中各标签出现次数
for i in range(k):
voteIlabel = labels[sortedDistIndicies[i]]
classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
print(sortedClassCount)
# 按标签次数排序，返回次数最多的标签
return sortedClassCount[0][0]
if __name__ == '__main__':
group, labels = createDataSet()
print(classify([0.9, 0.9], group, labels, 2))
# 最终输出类别为A
优缺点
优点
- KNN算法思想简单，非常人容易实现；
- 有新样本要加入训练集时，无需重新训练；
缺点
- 分类速度慢，因为每次分类新样本时，都要和所有的训练样本进行计算比较，时间复杂度和储存空间会随着训练集规模和特征维数的增大而增加。
- 各属性权重相同，当样本分布不均匀时，会影响准确率；
- K值不好确定