社区首页 >专栏 >KNN除了可以做分类和预测，还知道它可以识别异常值吗？

KNN除了可以做分类和预测，还知道它可以识别异常值吗？

1480

发布于 2019-08-08 07:48:10

2.6K00

代码可运行

文章被收录于专栏：数据分析1480数据分析1480

运行总次数：0

代码可运行

前言

首先跟各位读者朋友道个歉，这篇文章来的较晚，距离上一篇有关数据分析中异常值的判断已超过3个月。在《Python数据清洗--异常值识别与处理01》文中，介绍了两种单变量的异常识别方法，分别是分位数法（即借助于箱线图的策略）和Sigma法（即借助于正态分布的假设）。

然而这两种方法，并不能从全局的角度识别出数据中可能存在的异常点。为解决这个问题，本文将借助于KNN模型的思想，从多变量的角度，判断全局数据中的异常点。本文中所涉及的代码和数据源均可从文末的链接中下载。

KNN算法介绍

KNN模型属于有监督的学习算法，它的中文名称为K最近邻算法，该模型是通过搜寻最近的k个已知类别样本对未知类别样本进行预判，当然也可以对连续的Y变量做预测。关于“最近”的度量就是应用点之间的距离（如计算欧氏距离、曼哈顿距离、余弦相似度等），如果距离越小，说明它们之间越近。为了使读者能够理解KNN模型的思想，简单绘制了如下的示意图。

如上图所示，假设数据集中一共含有两种类别，分别用五角星和三角形表示，待预测样本为各圆的圆心。如果以近邻个数k=5为例，就可以通过投票方式快速得到未知样本所属的类别。该算法的背后是如何实现上面分类的呢？它的具体步骤可以描述为：

确定未知样本近邻的个数k值。
根据某种度量样本间相似度的指标（如欧氏距离）将每一个未知类别样本的最近k个已知样本搜寻出来，形成一个个簇。
对搜寻出来的已知样本进行投票，将各簇下类别最多的分类用作未知样本点的预测。

异常点识别原理

异常点是指远离大部分正常点的样本点，再直白点说，异常点一定是跟大部分的样本点都隔得很远。基于这个思想，我们只需要依次计算每个样本点与它最近的K个样本的平均距离。再利用计算的距离与阈值进行比较，如果大于阈值，则认为是异常点。同样，为了帮助读者理解如何利用KNN思想，实现异常值的识别，我手工画了一张图。

如上图所示，一共包含16个样本点，每一个样本点都可以跟剩余的15个样本点算欧式距离，再从15个距离中找出最小的K个距离，并计算平均距离，用于衡量该样本点与其它样本的相似度。

不妨以最近的5个近邻为例，目测图中的五角星应该就是异常点，因为它到最近5个样本点的平均距离，一定超过其他点的最近5个邻居的平均距离。

理论、思想说了那么多，下面我们就直接开干，为了方便后续的分析和可视化，我们选取了中国统计局公布的2018年各省常住人口量与GDP数据。希望从该数据中，寻找到可能存在异常点。

案例实战

首先，基于该数据，绘制各省常住人口量与GDP的散点图，让大家对数据有一个直观的认识。

# 导入后文即将用到的第三方模块
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
from sklearn.preprocessing import scale

# 导入数据
datas = pd.read_excel('economics.xlsx')
# 绘制2018年我国各省人口量与GDP之间的散点图
plt.scatter(datas.Population, datas.GDP)
plt.xlabel('Population')
plt.ylabel('GDP')
plt.show()

如上图所示，直觉上图中右上角的三个点可能是异常点，因为它们与大部分的数据点距离都比较远。为了验证我们的直觉，接下来通过构造自定义函数，计算每个点与剩余点的距离，并基于最近5个样本点算平均距离，寻找是否超过阈值的异常点（阈值的计算是《Python数据清洗--异常值识别与处理01》为中介绍的分位数法）。下方代码可能有点长，但仔细阅读并查看对应的注释内容，相信你一定能够理解代码的思想。

# 借助于K近邻算法，寻找数据中可能存在的异常点
def knn_outliner(data, K):
    # 数据的标准处理
    std_data = scale(data)
    # 重新转换为数据框
    std_data = pd.DataFrame(std_data)

    # 构造空列表，用于存储每个样本点的K近邻平均距离
    all_dist = []
    for i in range(std_data.shape[0]):
        # 计算第i个数据样本点与其他样本点的距离
        diff_i = np.array(std_data.loc[std_data.index != i, :]) \
                 - np.array(std_data.loc[std_data.index == i, :])
        dist_i = np.sum(np.square(diff_i), axis=1)
        # 从中寻找最近的K个邻居，并计算近邻的平均距离
        avg_dist_i = np.mean(np.sort(dist_i)[:K])
        # 记录每一个样本点距离其他样本点的平均距离
        all_dist.append(avg_dist_i)

    # 根据分位数法，寻找判断异常的阈值
    Q1 = pd.Series(all_dist).quantile(0.25)
    Q3 = pd.Series(all_dist).quantile(0.75)
    thread = Q3 + 3 * (Q3 - Q1)
    is_outline = pd.Series(all_dist) > thread

    # 合并数据（原始数据、近邻的平均距离和是否异常）
    final_res = pd.concat([data, pd.Series(all_dist, name='Dist'), pd.Series(is_outline, name='IsOutline')], axis=1)
    # 返回数据结果
    return final_res

# 调用函数，返回异常检测的结果
res = knn_outliner(datas[['Population', 'GDP']], K=5)

# 绘图
sns.lmplot(x="Population", y="GDP", hue='IsOutline', data=res,
           fit_reg=False, legend=False)
plt.legend(loc='best')
plt.show()

如上图所示，基于5个近邻的KNN思想，寻找到了4个异常点，与之前我们的直觉判断还是非常吻合的。读者也可以尝试其他几种可能的K值，并对比每一种K值所得到的异常点是否存在较大的差异。

KNN的短板

从思想、理论到实战，大家一定会发现，基于KNN模型寻找异常点，所要经过的运算次数还是非常多的（例如针对100个样本点寻找可能的异常，需迭代计算100×99次的运算）。所以，基于KNN模型寻找异常点是不适合于高维数据和大批量数据的；而且距离的计算采用的是欧式距离公式，只能针对球形簇的样本数据寻找异常，对于非球形簇则无法很好的搜寻异常。