基于MARS和概率规划的离群值检测算法

王瑞豪，童英华，2+，冯忠岭

(1.青海师范大学 计算机学院，青海 西宁 810008；2.青海师范大学 省部共建藏语智能信息处理及应用国家重点实验室，青海 西宁 810008；3.青海师范大学 物理与电子信息学院，青海 西宁 810008)

0 引 言

物联网(internet of things，IoT)是将分散在世界各地的数百万个对象、传感器节点进行连接、通信和数据交换，并使用其传感器生成大量数据的网络[1]。IoT已经影响人们日常生活中的许多领域，如城市、家庭、健康部门等[2]，并将对社会产生重大影响。此外，随着技术的进步，嵌入式传感器设备的数据收集能力也逐步提高，从而增加了来自物理世界的数据和更多连续的数据流。数据代表了连接网络世界和物理世界的桥梁[3]。物理世界到数字世界的数据流动将扩展计算机对周围环境的认识，从而人类将获得无处不在的服务。新产品和服务的质量很大程度上依赖于物联网设备所收集的数据质量。

文献[4-6]表明了数据质量(data quality，DQ)对数据挖掘过程的重要性，以及低DQ对这些过程结果有效性的影响，从而得出应确保DQ和准确性的结论。文献[7，8]提出了物联网的许多因素包括部署规模、资源有限和连接中断正在危及生产数据的质量。DQ中这些偏差的一个主要表现是数据离群值[9-11]。为了避免低DQ所带来的后果，需要对数据离群值进行处理，以提高数据的质量。

本文提出了一种结合多元回归MARS模型和概率规划的多元离群点检测方法。本方法使用一个多变量自适应回归样条曲线MARS模型来拟合具有单一因变量的多个预测因子变量，然后MARS模型的残差被用作可推广的、完全贝叶斯概率模型的输入，以检测离群值。最后，将该算法成功应用于物联网数据的离群值分析。

1 相关工作

基于回归模型与离群值检测已经有很多研究，主要集中在如何检测和处理离群值。文献[12]提出了一种贝叶斯方法，使用回归模型中的残差来检测离群值，利用线性回归模型中的标准化残差评估离群值，并利用离群值概率的后验分布假设非先验信息。这些后验概率被建模为学生t分布，以便更好地捕捉分布尾部的外围值。文献[13-16]使用离群值检测方法改进线性回归模型。本文关注的不是离群值如何影响回归模型，而是如何基于回归模型的输出来检测离群值。学生化残差和马氏距离等技术可用于评估回归模型数据输出中可能的离群值。文献[17]使用几种常用技术，如学习残差来检测离群值以改进回归模型，文章采用检测方法自动发现仪器浮标记录中可能存在的离群值，如飓风，以保护分析结果不受这些罕见事件的影响，即删除或记录这些事件，以创建干净的基线数据集进行分析。结果表明，贝叶斯方法与其它方法如标准化残差和预测不一致性诊断的结果相似。

2 多元变量离群值检测方法

离群值是位于主要数据分组之外的某个值，或者不适合某个正常模型的数据点[12]，其中模型可以基于距离、密度、回归等。检测和标记离群值的一种简单方法是提供一个上限或下限阈值，但前提是要了解整个数据集。

在许多情况下，例如检测欺诈，使用多个变量可以在检测和调查可能的离群值时提供有价值的信息。与单变量方法相比，使用多变量输入数据检测离群值的技术研究较少。研究多元离群值、回归模型和单变量的一个原因是，在多元回归的背景下，单变量离群值可能不是极端的，并且在双变量或单变量分析中，多元离群值可能无法检测到。在本节中将简要讨论两种常用的多变量离群值检测方法，用于发现潜在的外围数据点。

2.1 马氏距离

马氏距离(Mahalanobis distance)考虑了多元分布的数据规模，这些分布表示观察的概率。马氏距离与欧几里德距离相似，只是它沿着不相关的方向标准化了数据[18]。马氏距离给出了从一个错误值到预测变量(自变量)所有观测值的质心的距离。一个大的距离表示一个观测值是由预测值定义的空间中的一个离群值。式(1)定义了马氏距离

(1)

2.2 K-均值聚类

数据空间的划分有不同的方法，其中一种方法是K-均值聚类[19]。K-均值聚类的目标是最小化数据点到聚类的距离，或者减少聚类内的方差，通过最小化平方误差函数来实现，如式(2)所示

(2)

式中：J是目标函数，k是簇的数目，n是观测数据点的数目，xi是i的观测，cj是簇j的质心。因为K-均值聚类试图最小化簇内平方和，所以它总是给较大的簇赋予更多的权重。此外，K-均值聚类对数据进行了一些假设，包括以下内容：每个变量分布的方差都是球形的，或者聚类的分布是相似的，每个星团的观测数量大致相等。如果这些假设中的任何一个不成立，K-均值聚类将不会按预期运行，产生误导性或不正确的结果。

总之，在上述各种研究离群点检测方法时都有规范性假设，另一个重要因素是数据分布的形状。一般来说，大多数常见的离群点检测技术在正态分布数据上都有很好的表现。铰链函数同样对数据应用变换函数有助于创建多元正态分布，但变换并不总是有效的，任何结果都必须转换回原始空间。这些方法的这一弱点可能导致检测出不正确的离群值，特别是在非正态分布的数据集中。

3 基于MARS回归模型和概率规划的多元离群点检测算法

本节详细介绍提出的基于MARS回归模型和概率规划的多元离群点检测方法的两个必要组成部分，即MARS回归模型和概率模型。3.1节利用MARS模型计算出学生化残差，以便概率模型使用这些残差来检测离群值；3.2节通过贝叶斯推理得出概率规划的可信区间；3.3节概率模型的实现。

3.1 MARS回归模型

MARS是一个非参数回归模型，它解释了变量之间的非线性及其相互作用[20]。MARS利用铰链函数作为分段线性函数(拟合数据)，并通过组合铰链函数的变量关系而形成的非线性函数。MARS的优点是有利于创建多变量模型，包括铰链函数能够自动划分输入数据，在某种程度上包含输入数据中离群值的影响和快速预测。此外，自动特征选择选出最相关的特征，从而在使用模型检测具有多个变量的离群值时减少噪声和可能的离群值。MARS执行自动变量选择，适用于大型数据集，比传统线性模型更灵活。式(3)描述了使用MARS构建的模型

(3)

式中：ci为常数系数，基函数Bi(x) 可取值为1，也可取值为铰链函数max(0，x-ci) 或max(0，ci-x)。

H=X(XTX)-1XT

(4)

(5)

(6)

其中，H是hat矩阵，它是设计矩阵X在列空间上的正交投影，ε是绝对残差，σ2是残差的方差，hii是hat矩阵对角线上的值，t是学生化残差。本模型利用多变量MARS模型残差结果来实现数据可能存在的离群值概率。

3.2 概率规划与贝叶斯推理

概率规划利用高级语言来创建概率模型并自动求解，本模型结合了概率规划，用于检测物联网数据中的离群值，并实现完整的贝叶斯推理。贝叶斯推理提供了一种将新的证据与先前的信念或假设相结合的方法，通过应用贝叶斯规则来实现，贝叶斯公式如式(7)所示

(7)

在贝叶斯规则中，P(A) 是事件A的先验概率，P(X) 是X的先验概率，P(X|A) 是给定事件A的X的相似性，P(A|X) 是后验概率。

概率规划作为一种通用的推理技术，能够建立某一事件或特征的模型，如异常点的检测，并对预测进行概率推理，从过去的事件中推断原因，从过去的经验中学习以改进预测。概率规划的核心是概率推理，概率模型是用编程语言来实现的。这在一定程度上是因为概率程序被解释为一种分布，人们可以从中使用工具来询问有关分布的问题。此外，这些建模语言将随机事件作为原语合并，如前所述，它们是基于运行环境处理推理。还有其它可用的表示类型语言，如贝叶斯信念网络和隐马尔可夫模型。然而，这些方法只是简单的模拟，而不是机器学习。概率程序类似于可以运行和分析的模拟。

贝叶斯技术为本模型中的不同参数提供了可信区间。可信区间表明，某个值或参数在区间带内的概率为80%或95%。这比传统的置信区间更容易解释，因为传统的置信区间表明，如果一个实验重复多次，那么80%或95%的时间值都在这个区间内。此外，与其它评估结果可信度的方法一样，如果模型是真实的，那么结果周围的可信区间是可靠的。

3.3 概率模型

为了创建离群点检测概率模型，从MARS回归模型残差中检测离群值，作为双重方法的一部分，本文使用了Stan概率编程语言[21]。在Stan上，后验分布是每个未知参数的充分条件。这是用Hamiltonian Monte Carlo(HMC)和No-U-Turn采样器(NUTS)完成的，这两个采样器都是在Stan中实现的，用于执行统计推断。模型拟合是通过指定全似然函数和所有未知参数的先验分布来完成的。下面将详细介绍所提出的概率模型算法。

算法：概率模型算法

输入：长度为N的向量y

输出：最终离群值概率

(1)intN1;

vector[N1] y;

IntN2;

vector[N2]y2; //数据的输入

(2)real mu;

realsigma; 平均分布

realnu;//模型所需要的参数, 模型的设计参数的输入

(3)mu～normal(100,100)//mu平均分布

(4)sigma～normal(100,100)//sigma 标准差分布

(5)nu～cauchy(7,5);

for(i in 1:N1){

y[i]～student_t(nu, mu, sigma);

}//离群值的学生t分布

(6)vector[N2] cdf_prob;//概率累计的数据

(7)vector[N2] ccdf_prob;//数据的逆

(8)vector[N2] prob;

for(i in 1:N2){

cdf_prob[i] = student_t_cdf(y2[i], nu, mu, sigma);

ccdf_prob[i] = 1 - cdf_prob[i];

prob[i] = 2*(cdf_prob[i]*ccdf_prob[i]);

}//生成最终的离群值概率

首先声明了3个与实际输入相对应的输入变量，包括用于评估离群值的总体(或样本)向量、用于查找离群值的检查值以及每个向量的长度。Stan要估计的未知模型参数是样本空间与要检查的输入值(从中检测离群值)的平均值和标准偏差，以及学生t分布的自由度。对于离群值的检测，假设学生t分布的概率，使用均值、标准差和式(8)中定义的自由度，式(8)显示概率密度函数

(8)

t分布是对称的钟形分布[22]，类似于正态分布，峰值为零。不同的是，数据的扩散比标准正态分布的扩散要大。因此，t分布可以更好地捕捉数据集中更宽的尾部，以便更好地描述离群值分布。

在使用Stan概率编程语言时，概率语句用标准符号表示，如y～Normal(μ，σ)。 这意味着变量y模型数据被声明为具有给定均值和标准差的正态分布，用这个符号来表示本文的概率模型。

对于最终结果，本文计算了相对于大多数观测值，观测到更极端值的概率，该概率存储在离群值概率模型变量prob中，离群值概率的阈值与数据有关。

4 实验设计与分析

4.1 实验设计

本文提出的方法包含两部分，以检测离群值和可能的异常行为。MARS模型和相应的残差是物联网数据中离群值处理的第一步，它解决了数据集的多变量性质。在为每个专业创建了多元回归模型后，第二步就涉及到使用生成的学生t分布模型残差来检测离群值。模型是通过物联网数据集和特定的数据种类来建立的。

本研究使用R编程语言和MARS的earth包实现来创建和验证每个模型。分类和回归训练CARET包用于创建最终的MARS模型，并选择10倍交叉验证来减少训练模型的过度拟合。在进行10倍交叉验证中，将90%的数据集用于模型训练，10%用于测试，从而能够使用所有的可用数据来密切估计最终模型的预测性能。为了创建完全贝叶斯异常检测概率模型，本文使用了Stan概率编程语言的rstan。

4.2 实验结果及讨论

本文提出了完整的多变量离群值检测方法，在本节中将该方法与马氏距离、K-均值聚类方法进行比较。实验数据选择了基于物联网的雾霾部分数据进行离群值检测。该实验数据来源于某地区区委大楼2016年5月3日0点到5月7日下午5点空气中PM2.5的观测值，以小时为单位，共计114条数据。

在运行Mahalanobis 距离时，需要确定阈值或距离，将超过阈值或距离的值视为离群值。在比较中，采用降序对数据值相隔距离进行排序。此外，距离的确定是根据数据的种类而确定的，在某种程度上是任意的。计算出的距离在本质上，并不能决定大于该距离的值一定为离群值。可以通过几种不同的方式使用Mahalanobis距离检测离群值。其中一种方法使用平均马氏距离的1.5或3.0倍的值来创建阈值与每个距离进行比较，高于阈值的值被视为离群值。

对于K-均值聚类，关键因素是决定数据值聚类的数量。在本文的分析中，使用了肘部方法，它能直观地描绘集群内方差与集群数量的关系。当方差达到稳定点时，选择最佳聚类数。

4.2.1 MARS模型分析

图1给出了MARS模型选出离群值的分析过程。在图1中，首先通过模型选择器对数据量进行量化分析，然后计算出数据的累积分布率，通过累积分布率得到了数据值的集群分布图。经过MARS回归模型的演算，被标记为27、34、41的数据可能为离群值。MARS模型通过计算出的残差去检测离群值，而本文提出的算法可以通过MARS模型计算出的残差得出数据为离群值的概率。

图1 MARS模型的分析过程

4.2.2 多变量离群值检测方法比较

下面将本文提出的概率模型与Mahalanobis距离、K-均值聚类的离群值检测效果进行比较，结果如图2所示。

图2 多变量离群值检测效果

由图2可知，K-均值聚类选出的离群值过多并且分散，主要是由于数据值并不是过于的聚集，导致选出的离群值过多，可能存在误判。本文提出的算法选出的全部离群值与Mahalanobis 距离选出的部分离群值重叠，而K-均值聚类和Mahalanobis 距离选出的离群值只有3个重叠。主要是由于本方法首先通过MARS模型计算出数据的残差，然后将残差作为输入，进而得出数据异常的概率，因此能更准确选出离群值。

4.2.3 可信区间分析

图3显示了基于物联网的雾霾实验数据中PM2.5的可信区间，在该图中，黑点表示平均概率，较粗的水平线是80%区间的可信水平，细水平线是95%区间的外部水平。数据的平均概率表明有多大的概率观察到比该数据值更极端的数据值，概率越低表明很小的概率观察到比该值更极端的值，则该数据可能为离群值，概率越高，则表示很大概率观察到比该值更极端的值，更极端的值过多，表明该值也有可能为离群值。所以概率为40%到60%的数据值，处于钟形分布的中间部分，不太可能为离群值。可信区间的这种分布有助于确定某个值是否为离群值。

图3 物联网雾霾数据中PM2.5可信区间

由图3可知，当间隔位于1%概率阈值左侧或右侧的值可以被明确地标记为正常值；如果区间超过1%阈值，则该点可视为离群值，反之亦然。例如，被标记为27的数据，该数据与前后数据的间隔过大，超过了1%，并且该数据的较粗水平线过小，可信区间小，所以该值为离群值。具体取决于平均概率与阈值的关系。该信息捕获了固有的不确定性，可用于帮助创建更好的指标，以了解在给定更多可变数据集的情况下标记离群值，或者相反，在使用可变性较小的数据集标记离群值时设定更严格的界限。

5 结束语

提出了一种基于MARS模型和概率规划的离群值检测方法，并将该方法应用于物联网数据的离群值检测。与其它多变量离群值检测方法Mahalanobis距离和K-均值聚类相比，本模型返回值是数据为离群值的概率分布，能更准确选出离群值。因此，在给定某些特定数据集时，作为离群值的平均概率可用于确定离群值所需的适当概率阈值。同时，本方法不依赖于设置的距离值阈值，也不需要参数来指定邻居或集群的数量。此外，本算法对数据分布的影响更加稳健。