Question

就餐饮企业而言，经常会碰到如下问题。

1）如何根据客户的消费记录检测是否为异常刷卡消费？

2）如何检测是否有异常订单？

这一类异常问题可以通过离群点检测来解决。

离群点检测是数据挖掘中重要的一部分，它的任务是发现与大部分其他对象显著不同的对象。大部分数据挖掘方法都将这种差异信息视为噪声而丢弃，然而在一些应用中，罕见的数据可能蕴含着更大的研究价值。

在数据的散布图中，图5-24所示离群点远离其他数据点。因为离群点的属性值明显偏离期望的或常见的属性值，所以离群点检测也称偏差检测。

图5-24　离群点检测示意图

离群点检测已经被广泛应用于电信和信用卡的诈骗检测、贷款审批、电子商务、网络入侵和天气预报等领域。例如，可以利用离群点检测分析运动员的统计数据，以发现异常的运动员。

（1）离群点的成因

离群点的主要成因有：数据来源于不同的类、自然变异、数据测量和收集误差。

（2）离群点的类型

对离群点的大致分类见表5-31。

表5-31　离群点的大致分类

图5-25　全局离群点和局部离群点

5.5.1　离群点检测方法

常用离群点检测方法^[14]见表5-32。

表5-32　常用离群点检测方法

基于统计模型的离群点检测方法需要满足统计学原理，如果分布已知，则检验可能非常有效。基于邻近度的离群点检测方法比统计学方法更一般、更容易使用，因为确定数据集有意义的邻近度量比确定它的统计分布更容易。基于密度的离群点检测与基于邻近度的离群点检测密切相关，因为密度常用邻近度定义：一种是定义密度为到K个最邻近的平均距离的倒数，如果该距离小，则密度高；另一种是使用DBSCAN聚类算法，一个对象周围的密度等于该对象指定距离d内对象的个数。

下面重点介绍基于统计模型和聚类的离群点检测方法。

5.5.2　基于模型的离群点检测方法

通过估计概率分布的参数来建立一个数据模型。如果一个数据对象不能很好地同该模型拟合，即如果它很可能不服从该分布，则它是一个离群点。

（1）一元正态分布中的的离群点检测

正态分布是统计学中最常用的分布之一。

若随机变量x的密度函数，则称x服从正态分布，简称x服从正态分布N（μ，σ），其中参数μ和σ分别为均值和标准差。

图5-26显示N（0，1）的密度函数。

图5-26　N（0，1）的概率密度函数

N（0，1）的数据对象出现在该分布的两边尾部的机会很小，因此可以用它作为检测数据对象是否是离群点的基础。数据对象落在3倍标准差中心区域之外的概率仅有0.0027。

（2）混合模型的离群点检测^[14]

这里先介绍一下混合模型。混合模型是一种特殊的统计模型，它使用若干统计分布对数据建模。每一个分布对应一个簇，而每个分布的参数提供对应簇的描述，通常用中心和发散描述。

混合模型将数据看作从不同的概率分布得到的观测值的集合。概率分布可以是任何分布，但是通常是多元正态的，因为这种类型的分布不难理解，容易从数学上进行处理，并且已经证明在许多情况下都能产生好的结果。这种类型的分布可以对椭圆簇建模。

总的来说，混合模型数据产生过程为：给定几个类型相同但参数不同的分布，随机地选取一个分布并由它产生一个对象。重复该过程m次，其中m是对象的个数。

具体地讲，假定有K个分布和m个对象χ＝{x₁，x₂，…，x_m}。设第j个分布的参数为α_j，并设A是所有参数的集合，即A＝{α₁，α₂，…，α_K}。则P（x_i|α_j）是第i个对象来自第j个分布的概率。选取第j个分布产生一个对象的概率由权值w_j（1≤j≤K）给定，其中权值（概率）受限于其和为1的约束，即。于是，对象x的概率由以下公式给出：

如果对象以独立的方式产生，则整个对象集的概率是每个个体对象x_i的概率的乘积，公式如下。

对于混合模型，每个分布描述一个不同的组，即一个不同的簇。通过使用统计方法，可以由数据估计这些分布的参数，从而描述这些分布（簇）。也可以识别哪个对象属于哪个簇。然而，混合模型只是给出具体对象属于特定簇的概率。

聚类时，混合模型方法假定数据来自混合概率分布，并且每个簇可以用这些分布之一识别。同样，对于离群点检测，用两个分布的混合模型建模，一个分布为正常数据，而另一个为离群点。

聚类和离群点检测的目标都是估计分布的参数，以最大化数据的总似然。

我们提供一种离群点检测常用的简单的方法：先将所有数据对象放入正常数据集，这时离群点集为空集；再用一个迭代过程将数据对象从正常数据集转移到离群点集，该转移能提高数据的总似然。

具体操作如下。

假设数据集U包含来自两个概率分布的数据对象：M是大多数（正常）数据对象的分布，而N是离群点对象的分布。数据的总概率分布可以记作：

U（x）=（1-λ）M（x）+λN（x）其中，x是一个数据对象；λ∈[0，1]，给出离群点的期望比例。分布M由数据估计得到，而分布N通常取均匀分布。设M_t和N_t分别为时刻t正常数据和离群点对象的集合。初始t=0，M₀=D，而N₀≠。

根据公式混合模型中公式推导，在整个数据集的似然和对数似然可分别由下面两式给出。

其中P_D、分别是D、M_t、N_t的概率分布函数。

因为正常数据对象的数量比离群点对象的数量大很多，因此当一个数据对象移动到离群点集后，正常数据对象的分布变化不大。在这种情况下，每个正常数据对象的总似然的贡献保持不变。此外，如果假定离群点服从均匀分布，则移动到离群点集的每一个数据对象对离群点的似然贡献一个固定的量。这样，当一个数据对象移动到离群点集时，数据总似然的改变粗略地等于该数据对象在均匀分布下的概率（用λ加权）减去该数据对象在正常数据点的分布下的概率（用1-λ加权）。从而，离群点由这样一些数据对象组成。这样，数据对象在均匀分布下的概率比正常数据对象分布下的概率高。

在某些情况下是很难建立模型的。例如，因为数据的统计分布未知或没有训练数据可用。在这种情况下，可以考虑其他不需要建立模型的检测方法。

5.5.3　基于聚类的离群点检测方法

聚类分析用于发现局部强相关的对象组，而异常检测用来发现不与其他对象强相关的对象。因此，聚类分析非常自然地可以用于离群点检测。本节主要介绍两种基于聚类的离群点检测方法。

（1）丢弃远离其他簇的小簇

一种利用聚类检测离群点的方法是丢弃远离其他簇的小簇。通常，该过程可以简化为丢弃小于某个最小阈值的所有簇。

这个方法可以和其他任何聚类技术一起使用，但是需要最小簇大小和小簇与其他簇之间距离的阈值。而且这种方案对簇个数的选择高度敏感，使用这个方案很难将离群点得分附加到对象上。

在图5-27中，聚类簇数K＝2，可以直观地看出其中一个包含5个对象的小簇远离大部分对象，可以视为离群点。

图5-27　K-Means算法的聚类图

（2）基于原型的聚类

基于原型的聚类是另一种更系统的方法。首先聚类所有对象，然后评估对象属于簇的程度（离群点得分）。在这种方法中，可以用对象到它的簇中心的距离来度量属于簇的程度。特别地，如果删除一个对象导致该目标的显著改进，则可将该对象视为离群点。例如，在K均值算法中，删除远离其相关簇中心的对象能够显著地改进该簇的误差平方和（SSE）。

对于基于原型的聚类，主要有两种方法评估对象属于簇的程度（离群点得分）：一是度量对象到簇原型的距离，并用它作为该对象的离群点得分；二是考虑到簇具有不同的密度，可以度量簇到原型的相对距离，相对距离是点到质心的距离与簇中所有点到质心的距离的中位数之比。

如图5-28所示，如果选择聚类簇数K＝3，则对象A、B、C应分别属于距离它们最近的簇，但相对于簇内的其他对象，这3个点又分别远离各自的簇，所以有理由怀疑对象A、B、C是离群点。

图5-28　基于距离的离群点检测

诊断步骤如下。

1）进行聚类。选择聚类算法（如K-Means算法），将样本集聚为K簇，并找到各簇的质心。

2）计算各对象到它的最近质心的距离。

3）计算各对象到它的最近质心的相对距离。

4）与给定的阈值作比较。

如果某对象距离大于该阈值，就认为该对象是离群点。

基于聚类的离群点检测的改进如下。

1）离群点对初始聚类的影响：通过聚类检测离群点时，离群点会影响聚类结果。为了处理该问题，可以使用方法：对象聚类，删除离群点，对象再次聚类（这个不能保证产生最优结果）。

2）还有一种更复杂的方法：取一组不能很好地拟合任何簇的特殊对象，这组对象代表潜在的离群点。随着聚类过程的进展，簇在变化。不再强属于任何簇的对象被添加到潜在的离群点集合；测试当前在该集合中的对象，如果它现在强属于一个簇，就可以将它从潜在的离群点集合中移除。聚类过程结束时还留在该集合中的点被分类为离群点（这种方法也不能保证产生最优解，甚至不比前面的简单算法好，在使用相对距离计算离群点得分时，这个问题特别严重）。

对象是否被认为是离群点可能依赖于簇的个数（如k很大时的噪声簇）。该问题也没有简单的答案。一种策略是对于不同的簇个数重复该分析。另一种方法是找出大量小簇，其想法如下。

1）较小的簇倾向于更加凝聚；

2）如果存在大量小簇时，一个对象是离群点，则它多半是一个真正的离群点。

不利的一面是一组离群点可能形成小簇从而逃避检测。

利用表5-14的数据进行聚类分析，并计算各个样本到各自聚类中心的距离，分析离群样本，得到如图5-29所示的距离误差图。

图5-29　离散点检测距离误差图

分析图5-29可以得到，如果距离阈值设置为2，那么所给的数据中有8个离散点，在聚类的时候这些数据应该剔除。

其Python代码如代码清单5-8所示。

代码清单5-8　离散点检测

#-*- coding: utf-8 -*-
#使用K-Means算法聚类消费行为特征数据
import numpy as np
import pandas as pd
#参数初始化
inputfile = '../data/consumption_data.xls' #销量及其他属性数据
k = 3 #聚类的类别
threshold = 2 #离散点阈值
iteration = 500 #聚类最大循环次数
data = pd.read_excel(inputfile, index_col = 'Id') #读取数据
data_zs = 1.0*(data - data.mean())/data.std() #数据标准化
from sklearn.cluster import KMeans
model = KMeans(n_clusters = k, n_jobs = 4, max_iter = iteration) #分为k类，并发数4
model.fit(data_zs) #开始聚类
#标准化数据及其类别
r = pd.concat([data_zs, pd.Series(model.labels_, index = data.index)], axis = 1)  
#每个样本对应的类别
    r.columns = list(data.columns) + [u'聚类类别'] #重命名表头
norm = []
for i in range(k): #逐一处理
  norm_tmp = r[['R', 'F', 'M']][r[u'聚类类别'] == i]-model.cluster_centers_[i]
  norm_tmp = norm_tmp.apply(np.linalg.norm, axis = 1) #求出绝对距离
  norm.append(norm_tmp/norm_tmp.median()) #求相对距离并添加
norm = pd.concat(norm) #合并
import matplotlib.pyplot as plt
plt.rcParams['font.sans-serif'] = ['SimHei'] #用来正常显示中文标签
plt.rcParams['axes.unicode_minus'] = False #用来正常显示负号
norm[norm <= threshold].plot(style = 'go') #正常点
discrete_points = norm[norm > threshold] #离群点
discrete_points.plot(style = 'ro')
for i in range(len(discrete_points)): #离群点做标记
  id = discrete_points.index[i]
  n = discrete_points.iloc[i]
  plt.annotate('(%s, %0.2f)'%(id, n), xy = (id, n), xytext = (id, n))
plt.xlabel(u'编号')
plt.ylabel(u'相对距离')
plt.show()

代码详见：示例程序/code/discrete_point_test.py