进击数据挖掘十大算法(二):KNN

一、概述

k-近邻算法（k-Nearest Neighbour algorithm），又称为KNN算法，是数据挖掘技术中原理最简单的算法。KNN 的工作原理：给定一个已知标签类别的训练数据集，输入没有标签的新数据后，在训练数据集中找到与新数据最邻近的k个实例，如果这k个实例的多数属于某个类别，那么新数据就属于这个类别。可以简单理解为：由那些离X最近的k个点来投票决定X归为哪一类。

GitHub源码：QzmVc1/Data-Mining/KNN/

参考链接：
【智源学院】30分钟KNN算法-有意思专题系列(K-Nearest Neighbor, KNN)
【菊安酱的机器学习】第1期 k-近邻算法

---

二、KNN算法的简单理解

图中有红色三角和蓝色方块两种类别，我们现在需要判断绿色圆点属于哪种类别。
当k=3时，绿色圆点属于红色三角这种类别；
当k=5时，绿色圆点属于蓝色方块这种类别。

举个简单的例子，可以用k-近邻算法分类一个电影是爱情片还是动作片。（打斗镜头和接吻镜头数量为虚构）

上表就是我们已有的数据集合，也就是训练样本集。这个数据集有两个特征——打斗镜头数和接吻镜头数。除此之外，我们也知道每部电影的所属类型，即分类标签。粗略看来，接吻镜头多的就是爱情片，打斗镜头多的就是动作片。以我们多年的经验来看，这个分类还算合理。如果现在给我一部新的电影，告诉我电影中的打斗镜头和接吻镜头分别是多少，那么我可以根据你给出的信息进行判断，这部电影是属于爱情片还是动作片。

而k-近邻算法也可以像我们人一样做到这一点。但是，这仅仅是两个特征，如果把特征扩大到N个呢？我们人类还能凭经验“一眼看出”电影的所属类别吗？想想就知道这是一个非常困难的事情，但算法可以，这就是算法的魅力所在。

我们已经知道k-近邻算法的工作原理，根据特征比较，然后提取样本集中特征最相似数据（最近邻）的分类标签。 那么如何进行比较呢？比如表1中新出的电影，我们该如何判断他所属的电影类别呢？如下图所示:

我们可以从散点图中大致推断，这个未知电影有可能是爱情片，因为看起来距离已知的三个爱情片更近一点。k-近邻算法是用什么方法进行判断呢？没错，就是距离度量。这个电影分类例子中有两个特征，也就是在二维平面中计算两点之间的距离，就可以用我们高中学过的距离计算公式：

如果是多个特征扩展到N维空间，怎么计算？没错，我们可以使用欧氏距离（也称欧几里得度量），如下所示：

通过计算可以得到训练集中所有电影与未知电影的距离，如下表所示：

通过表2的计算结果，我们可以知道绿点标记的电影到爱情片《后来的我们》距离最近，为29.1。如果仅仅根据这个结果，判定绿点电影的类别为爱情片，这个算法叫做最近邻算法，而非k-近邻算法。k-近邻算法步骤如下：

(1) 计算已知类别数据集中的点与当前点之间的距离；
(2) 按照距离递增次序排序；
(3) 选取与当前点距离最小的k个点；
(4) 确定前k个点所在类别的出现频率；
(5) 返回前k个点出现频率最高的类别作为当前点的预测类别。

比如，现在K=4，那么在这个电影例子中，把距离按照升序排列，距离绿点电影最近的前4个的电影分别是《后来的我们》、《前任3》、《无问西东》和《红海行动》，这四部电影的类别统计为爱情片:动作片=3:1，出现频率最
高的类别为爱情片，所以在k=4时，绿点电影的类别为爱情片。这个判别过程就是k-近邻算法。

---

三、KNN算法的Python实现

3.1 Python代码

import csv
import random
# 读取数据集
with open('iris.csv','r') as fp:
    reader = csv.DictReader(fp)
    datas = [row for row in reader]

# 对数据分成训练集和测试集
random.shuffle(datas)
n = len(datas) // 3
test_set = datas[0:n]
train_set = datas[n:]

# 计算欧几里得距离
def distance(d1,d2):
    res = 0
    for key in ("Sepal.Length","Sepal.Width","Petal.Length","Petal.Width"):
        res += (float(d1[key])-float(d2[key]))**2
    return res**0.5

K = 3
def KNN(data):
    # 1.计算距离
    res = [
        {'result':train['Species'],'distance':distance(data,train)}
        for train in train_set
    ]

    # 2.升序排序
    res = sorted(res,key=lambda item:item['distance'])

    # 3.取前K个数据
    res2 = res[0:K]

    # 4.加权平均
    result = {'versicolor':0,'setosa':0}
    sum = 0
    for r in res2:
        sum += r['distance']
    for r in res2:
        result[r['result']] += 1-r['distance']/sum

    if result['versicolor'] > result['setosa']:
        return 'versicolor'
    else:
        return 'setosa'


# 测试阶段
correct = 0
for test in test_set:
    result1 = test['Species']
    result2 = KNN(test)
    if result1 == result2:
        correct += 1

print("{:.2f}%".format(correct*100/len(test_set)))

3.2 数据集

ID	Sepal.Length	Sepal.Width	Petal.Length	Petal.Width	 Species
1	      5.1	          3.5	        1.4	          0.2	     setosa
2	      4.9	          3	          1.4	          0.2	     setosa
3	      4.7	          3.2	        1.3	          0.2	     setosa
4	      4.6	          3.1	        1.5	          0.2	     setosa
5	      5	            3.6	        1.4	          0.2	     setosa
6	      5.4	          3.9	        1.7	          0.4	     setosa
...     ...           ...         ...           ...      ...

---

四、算法总结

KNN
算法功能	分类（核心），回归
算法类型	有监督学习 - 惰性学习，距离类模型
数据输入	包含数据标签y，且特征空间中至少包含k个训练样本（k>=1) 特征空间中各个特征的量纲需统一，若不统一则需要进行归一化处理自定义的超参数k (k>=1)
模型输出	包含数据标签y，且特征空间中至少包含k个训练样本（k>=1) 特征空间中各个特征的量纲需统一，若不统一则需要进行归一化处理自定义的超参数k (k>=1)

4.1 优点

• 简单好用，容易理解，精度高，理论成熟，既可以用来做分类也可以用来做回归
• 可用于数值型数据和离散型数据
• 无数据输入假定
• 适合对稀有事件进行分类

4.2 缺点

• 计算复杂性高；空间复杂性高；
• 计算量太大，所以一般数值很大的时候不用这个，但是单个样本又不能太少，否则容易发生误分。
• 样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）
• 可理解性比较差，无法给出数据的内在含义

---