从数学的角度初步看离群点检测算法

◎王晨皓

从数学的角度初步看离群点检测算法

◎王晨皓

目前，大数据技术在全世界范围内迅猛发展，在金融、电信、交通、医疗等领域得到了广泛应用，全球包含个人电脑、平板电脑、智能手机、可穿戴终端及物联网终端等联网设备将超过500亿台，全年产生的数据总量是一个天文数字，如此数量、多样化的数据，对各行各业来说存在着巨大的潜在价值，然而由于大数据的4V特性（大体量、多样性、时效性和精确性）决定了大数据的处理和利用难度高，传统的数据分析技术无法满足应用需求，数据挖掘技术应运而生。

数据挖掘是从大量数据中提取出人们所关心的有价值的数据信息，是一门涵盖了统计学、机器学习、人工智能、图像处理、数据库等多门学科的交叉学科，其中数学理论是数据分析与研究的技术。离群点检测正是数据挖掘的重要任务之一，在完成离群点数据检测与分析的过程中，应用了大量的数学模型与数学方法，是数学方法针对数据时代新应用的特殊需求的一次新发展。

离群点检测

离群点数据是与大多数数据在某些特征空间上有所差异的数据，其产生途径大致有两种：一是人为误差或测量设备故障而产生导致的异常数据，会导致数据分析结果的错漏；二是由另外一种完全不同的机制产生的数据。第一类数据在数据分析中是没有意义的，它的存在反而会对数据分析的结果产生不良的影响，通过离群点检测技术剔除此类离群数据是进行数据挖掘的前提。第二类数据在数据分析中占有重要的意义，由于其产生机制的不同，在一些特殊的领域，如电子商务犯罪、疾病诊断、网络攻防等研究领域，离群点的存在往往蕴含一些特殊的信息，具有极高的研究意义。离群点检测和分析技术就是采用一定的方法对离群点数据进行查找并分析其成因与属性的技术。

离群点检测算法中的数学应用

数学理论是数据分析与预测的基础，在大数据相关技术中，无论是数据的采集、取样、存储，还是数据挖掘与处理，都离不开数学模型与数学理论的支持，在离群点检测算法中，更是应用了包括统计学、几何学在内的大量数学理论。

基于统计的离群点检测。基于统计的离群点检测算法是基于统计学知识，通过对事件发生的概率判别数据点是否为离群点。这类离群点检测算法须首先定义数据的概率分布或概率模型，然后将数据特征与概率模型进行一致性检验，不符合概率模型的数据为离群点。此算法是最经典的离群点检测算法，便于理解，实现简易。其难点在于概率模型的设定往往是根据数据集先验知识采样确定的，无法完全确定数据的概率分布，在选择不同的采集点时选出的离群点不同。另外，此种方法要求待分析数据必须满足某种已知的概率分布模型（如正态分布、拉普拉斯分布等），模型的参数（如均值、标准差等）难以确定且对分析结果影响较大。利用统计学方法进行离群点检测具有一定的局限性，比较适合挖掘单变量数值型数据，然而在大数据时代，大部分数据挖掘需求对多元化数据进行分析，发现多维数据的离群点，其概率分布难以符合目前已有的标准概率分布，基于统计的离群点检测算法难以按照需求发现所有离群点。

基于分形理论的离群点检测。基于分形理论的离群点检测算法是采用分形几何的相关概念，通过数据集的多维特征分进行分形，通过数据集的嵌入维和内在维判别数据点是否为离群点。此种离群点检测算法采用多维分形维数对多维空间中多样化的数据进行离群检测，以推广GP（Grassberger-Procaccia）算法计算多重分形广义维数谱，通过关联积分得出关联维数。在度量离群点时，首先计算包含离群点的数据集的离群度DIM（D,D）和剔除了目标数据p的数据集的离群度DIM（D-p,D），两结果相比即为数据p的离群度OD(p,D)，此数值越高，则p为离群点的概率越大。当超过事先设定的权值时，将p设定为离群点。基于分性理论的离群点检测算法在高维空间上的离群数据挖掘看做最优化分割问题进行处理，有效地解决了多样化、多特征数据的离群点检测，但是对每个数据点均需计算计算其离群度，算法时间复杂度高达O(n3)，效率较低。

基于距离的离群点检测。基于距离的离群点检测算法是应用空间几何模型，将数据看作高维空间中的点，每两个数据点之间的距离即为这两个数据的偏差值，离群点即为数据集中与大多数点距离大于规定阈值的点。这种方法通俗易懂，便于理解。通常情况下，数据集D中有不少于p个对象与对象o的距离大于dm，则称对象o为以参数p和距离dm为参数的离群点，写作D（p,dm）。在对数据进行离群点检测时，可以根据数据的规模和特性以及数据处理需要，定义参数p和dm，经过算法计算即可检测离群点。目前已经成熟的检测算法有三种：一是基于索引的算法，二是基于单元的算法，三是嵌套—循环算法。在理论上，这几种算法的时间复杂度最高为O(kn2)，效率较差，但可处理多维数据模型，这类算法的缺点是受阈值限制，且仅能检测全局离群点。

基于密度的局部离群点检测。基于密度的局部离群点检测算法结合多维几何理论，检测局部离群点的算法。这种方法将数据对象作为多维空间独立的点，这些点是有自己的集群的，即多个距离近的数据对象为一数据集。在计算时，通过数据对象周围单位空间内数据对象的个数（即密度）作为此数据对象是否为离群点的判断标准。由于取单位空间操作较难达成，在计算时，通常选取与目标对象距离最近的n个数据对象，并计算其与目标对象的距离之和，结果较大的密度低。它与其他离群点检测算法不同，不仅仅简单的判断数据对象是否为离群点，更建立了一种评估数据对象离群程度的标准，即局部离群因子（LOF）。数据对象P的局部离群因子的计算过程如下：（1）计算数据集中所有数据对象到P的距离，通常采用的计算方式有三种：欧几里得距离、曼哈顿距离和明考斯距离。（2）从上述结果中选出n个，选中其中最大的一个为P的n距离。（3）计算P的距离邻域，以及被选中的n个数据点的距离。（4）通过距离计算P的局部密度和局部离群因子。LOF算法的主要缺点在于计算复杂度较高，但是经过基于索引的方法优化后，计算复杂度为O(nlogn)，效率得到了较大提高。

基于聚类的离群点检测。聚类分析是将研究对象的集合按照既定规则分成多个类的过程，是一种将多种数学模型应用化的统计分析方法，现大规模应用于数据挖掘领域。聚类算法可以高效的将数据对象集划分成为具有多个具有相似特征的微聚类，在划分完成后，不属于任何聚类的数据对象即为离群点。基于聚类的离群点检测算法过程是首先利用聚类算法将给定的数据对象进行运算，得出离群数据对象和聚类，然后判断离群对象在各个一维子空间内对各个聚类投影的离群情况，得出离群对象的相关信息。这类方法基于线性和K均值（接近线性复杂度均值）的聚类技术可以高效的完成离群点的分类，并将具有相同离群属性的离群点划分到同一离群簇，便于分析其离群特性，但同样的，检测到的离群点往往非常依赖所用的簇的个数和数据中离群点的存在性，且产生的簇的质量对此类方法产生的离群点的质量影响较大。

离群点检测是数据挖掘的重要任务，随着大数据时代的到来，离群数据的检测与分析在防范网络犯罪、分析市场走向等方面发挥着愈来愈重要的作用。现有的离群点数据检测技术是基于包括统计学、几何学在内的大量数学知识和数学模型发展而来的。数学理论是离群点数据检测技术的基础，新的离群点数据检测技术的提出必然与提出新的数学模型息息相关，是当前研究人员的研究重点。

（作者单位：郑州市第四中学）