1.理论知识
KNN（K-Nearest Neighbor）算法是机器学习算法中最基础、最简单的算法之一。它既能用于分类，也能用于回归。KNN通过测量不同特征值之间的距离来进行分类。
KNN算法的思想：
对于任意n维输入向量，分别对应于特征空间中的一个点，输出为该特征向量所对应的类别标签或预测值。
KNN算法是一种非常特别的机器学习算法，因为它没有一般意义上的学习过程。它的工作原理是利用训练数据对特征向量空间进行划分，并将划分结果作为最终算法模型。存在一个样本数据集合，也称作训练样本集，并且样本集中的每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的数据后，将这个没有标签的数据的每个特征与样本集中的数据对应的特征进行比较，然后提取样本中特征最相近的数据（最近邻）的分类标签。
图2.1 KNN算法示意图
其中常用的距离量度方式包括：
- 闵可夫斯基距离
- 欧氏距离
- 曼哈顿距离
- 切比雪夫距离
- 余弦距离
2.算法流程图
3.关键代码
from numpy import *
import operator
# k近邻分类算法
def classify0(inX, dataSet, labels, k):
# 欧式距离计算
dataSetSize = dataSet.shape[0]
diffMat = tile(inX, (dataSetSize, 1)) - dataSet
sqDiffMat = diffMat ** 2
sqDistinces = sqDiffMat.sum(axis=1) # 行方向求和
distances = sqDistinces ** 0.5
# 将距离值进行排序，并返回索引值
sortedDistIndicies = distances.argsort()
# 选择距离最小的k个点，并统计k个点中各个类别的数目
classCount = {}
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)
return sortedClassCount[0][0]
# 归一化数值
def autoNorm(dataSet):
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
ranges = maxVals - minVals
normDataSet = zeros(shape(dataSet))
m = dataSet.shape[0] # 获取数据行数
normDataSet = dataSet - tile(minVals, (m, 1))
normDataSet = normDataSet / tile(ranges, (m, 1))
return normDataSet, ranges, minVals
if __name__ == '__main__':
dataSet = [[3, 104], [2, 100], [1, 81], [101, 10], [99, 5], [98, 2]]
labels = ['类别1', '类别1', '类别1', '类别2', '类别2', '类别2']
test = [100, 90] # 未知电影的接吻镜头次数、打斗镜头次数
normMat, ranges, minVals = autoNorm(array(dataSet)) # 归一化处理
k = 3
classifierResult = classify0(test, normMat, labels, k)
print("输入的k:\n ", k)
print('------------------------------------------------------')
print("数据为:\n ", dataSet)
print('------------------------------------------------------')
print("对应标签为:\n ", labels)
print('------------------------------------------------------')
print("输入数据为:\n ", test)
print('------------------------------------------------------')
print("预测的标签：\n", classifierResult)
4.实验结果
测试数据
表2.1 输入的数据集(输入k=3)
数据 |
3, 104 |
2, 100 |
1, 81 |
101, 10 |
99, 5 |
98, 2 |
类别 |
类别1 |
类别1 |
类别1 |
类别2 |
类别2 |
类别2 |
*其中3,104代表属性1为3, 属性2为104.
实验结果与分析
图2.2 实验结果
算法特点
优点：
- 简单易用。相比其他算法，KNN 算法比较简洁明。
- 模型训练时间快，上面说到 KNN 算法是惰性的。
- 预测效果好。
- 对异常值不敏感。
缺点：
- 对内存要求较高，因为该算法存储了所有训练数据。
- 预测阶段可能很慢。
- 对不相关的功能和数据规模敏感。