KNN 算法基本原理

kNN 算法的核心思想是用距离最近的 k 个样本数据的分类来代表目标数据的分类。 用俗话来说就是 “近朱者赤，近墨者黑”，采用距离最近的 k 个样本中占比最高的类别来代表测试数据的类别。

注意 KNN 算法仍然是有监督学习算法的一种

KNN 算法的特点

  • 优点：
    1. 监督学习：可以看到，kNN 算法首先需要一个训练样本集，这个集合中含有分类信息，因此它属于监督学习。
    2. 通过计算距离来衡量样本之间相似度，算法简单，易于理解和实现。
    3. 对异常值不敏感
  • 缺点：
    1. 需要设定 k 值，结果会受到 k 值的影响，不同的 k 值，最后得到的分类结果不尽相同。k 一般不超过 20。
    2. 计算量大，需要计算样本集中每个样本的距离，才能得到 k 个最近的数据样本。
    3. 训练样本集不平衡导致结果不准确问题。当样本集中主要是某个分类，该分类数量太大，导致近邻的 k 个样本总是该类，而不接近目标分类。

KNN 算法的流程

一般情况下，kNN 有如下流程：

  1. 收集数据：确定训练样本集合测试数据；
  2. 计算测试数据和训练样本集中每个样本数据的距离；
  • 常用的距离计算公式：

欧式距离计算公式：
曼哈顿距离公式：

  1. 按照距离递增的顺序排序；
  2. 选取距离最近的 k 个点(这个 k 一般小于等于 20)；
  3. 确定这 k 个点中分类信息的频率；
  4. 返回前 k 个点中出现频率最高的分类，作为当前测试数据的分类。

python 算法实现

开发的基本流程如下：

  • 收集数据: 提供文本文件
  • 准备数据: 使用 Python 解析文本文件
  • 分析数据: 使用 Matplotlib 画二维散点图
  • 训练算法: 此步骤不适用于 k-近邻算法
  • 测试算法: 使用海伦提供的部分数据作为测试样本。

测试样本和非测试样本的区别在于:
测试样本是已经完成分类的数据，如果预测分类与实际类别不同，则标记为一个错误。

  • 使用算法: 产生简单的命令行程序，然后海伦可以输入一些特征数据以判断对方是否为自己喜欢的类型。
  1. KNN 算法分类器函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 定义KNN算法分类器函数
# 函数参数包括: (测试数据, 训练数据, 分类, k值)
def classify(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]  # 读取矩阵有几层数据
    diffMat = tile(inX, (dataSetSize, 1)) - dataSet  # 将测试数据转化为数值相同的行向量,再与训练集作差
    sqDiffMat = diffMat ** 2
    sqDistances = sqDiffMat.sum(axis=1)  # axis=1 按行相加;axis=0 按列相加
    distances = sqDistances ** 0.5  # 计算欧式距离
    sortedDistIndicies = distances.argsort()  # 排序并返回index,注意此处返回的是索引而不是具体值!
    # 选择距离最近的k个值
    classCount = {}
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1  # get()相当于将其赴初值0然后加1
    # 排序
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True) # items()返回一个元组,operator.itemgetter()按照value排序
    return sortedClassCount[0][0] #返回标签
  1. 定义生成训练样本集的函数
1
2
3
4
def createDataSet():
    group = array([[1, 1.1], [1, 1], [0, 0], [0, 0.1]])
    labels = ['A', 'A', 'B', 'B']
    return group, labels
  1. 定义主函数运行代码
1
2
3
4
5
6
7
def main():
    group, labels = createDataSet()
    print(classify([0, 0], group, labels, 3))


if __name__ == '__main__':
    main()

完整源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#!/user/bin/env python3
# -*- coding: utf-8 -*-

from numpy import *
import operator


# 定义KNN算法分类器函数
# 函数参数包括: (测试数据, 训练数据, 分类, k值)
def classify(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]  # 读取矩阵有几层数据
    diffMat = tile(inX, (dataSetSize, 1)) - dataSet  # 将测试数据转化为数值相同的行向量,再与训练集作差
    sqDiffMat = diffMat ** 2
    sqDistances = sqDiffMat.sum(axis=1)  # axis=1 按行相加;axis=0 按列相加
    distances = sqDistances ** 0.5  # 计算欧式距离
    sortedDistIndicies = distances.argsort()  # 排序并返回index,注意此处返回的是索引而不是具体值!
    # 选择距离最近的k个值
    classCount = {}
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1  # get()相当于将其赴初值0然后加1
    # 排序
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True) # items()返回一个元组,operator.itemgetter()按照value排序
    return sortedClassCount[0][0] #返回标签


# 定义一个生成"训练样本集"的函数,包含特征和分类信息
def createDataSet():
    group = array([[1, 1.1], [1, 1], [0, 0], [0, 0.1]])
    labels = ['A', 'A', 'B', 'B']
    return group, labels


def main():
    group, labels = createDataSet()
    print(classify([0, 0], group, labels, 3))


if __name__ == '__main__':
    main()

本文参考自 机器学习之 k-近邻（kNN）算法与 Python 实现