加速大规模数据集的离群点检测

1、加速大规模数据集的离群点检测这两个算法请详细一下，是指Orca和iDOoR算法吗？离群点；聚类；索引；分布式；优化策略；剪枝规则0引言过去的几年中，大数据集中基于距离的离群点检测在数据挖掘领域引起了广泛的关注。与传统的基于统计的离群点检测相比，基于距离的离群点显得更灵活更容易计算。目前基于距离的离群点检测存在的一个主要瓶颈是要为数据集中的每一个数据对象查找最近邻。因此，像嵌套循环1这样直接实现的方法需要计算所有数据对之间的距离，导致了O(N2)的复杂度，在处理大数据时效率也比较低。近几年，数据挖掘工作者在Knorr等1所提方法基础上提出了一些用于提高基于距离的离群点检测效率的方法2-11。文献

2、2根据预聚类阶段的结果，通过移除那些不可能包含离群点的簇来提高离群点的检测效率。文献3通过维护一个当前第n个最大离群点得分并用它作为截断阈值，当某个点到目前找到的第k个最近邻的距离小于这个阈值时，该点就可以立即被剪枝；其中使得这个思想能够充分发挥作用的关键是能够以一种让离群点尽可能早地得到处理的顺序来处理数据。Bhaduri等4提出了一种基于索引的Orca3算法即(indexedOrca，iOrca)，该算法能够以一种尽可能早地处理离群点的顺序处理数据，但是该方法构建的索引是以随机选择的参考点建立的，具有一定程度的不稳定性，并且对具有不同密度数据的情况效果也不是很好，因为它们的索引是建立在全局

3、数据基础上的。Lozano等5提出了文献3的并行处理版本；但是该方法并没有解决文献3集中化版本中对数据的处理顺序和数据集的分布敏感等缺点。Bhaduri等4提出了基于索引的分布式离群点检测算法iDOoR(indexedDOoR)。但是该分布式算法与集中化方法相比，在初始阶段有明显的加速，而对后续阶段的加速则不明显，其主要原因是要把每个未被剪枝的测试数据在所有节点之间进行传递并在所经节点处进行测试。而后一阶段中需要测试的点大都是正常点，因此该算法做了大量不必要的工作，既增大了通信消耗又增加了计算时间。针对上述存在的问题，提出了一种基于聚类和索引的分布式离群点检测(DistributedOutli

4、erDetectionbasedonClusteringandIndexing,DODCD算法及两个优化策略和两条剪枝规则来加速大规模数据集中离群点的检测。该方法通过聚类将相似的点划分到同一个簇中以便于最近邻的查找，同时为了进一步提高剪枝的效率本文借鉴Bhaduri等4所提的索引思想，但不同于他们的方法，本文的索引是基于划分的簇并以簇质心为参考点来构建的，该方法能够克服Bhaduri等4所提方法不稳定的缺点。最后本文采用并行方法在所有簇中同时构建索引，并在并行计算的过程中结合两个优化策略和两条剪枝规则来缩小搜索空间和减少节点之间的通信消耗进而提高离群点的检测速度。1 问题描述与相关定义对于d维

5、空间中的数据点p=(pl,p2,，pd)和q=(q1,q2,，qd),通常采用欧几里得距离度量它们之间的相似度，即：dist(p,q)=Edi=1(pi-qi)2本文采用如下的离群点定义：定义1到其第k个最近邻的距离最大的n个数据点为离群点2 2。本文采用该定义是因为它较为直观，并且不用花费太多计算时间，下面给出离群得分的定义。定义2点的离群得分。对于数据集D,给定参数k(最近邻个数)和pD,则点p的离群得分Dk(p)定义为：Dk(p)=dist(p，Nk(p)其中Nk(p)表示p在数据集D中的第k个最近邻。Dk(p)越大，p成为离群点的可能性越大。并由定义2给出topn离群点定义。定义3to

6、pnDkOutlier。数据集D中那些到其第k个最近邻的距离Dk最大的前n个点就是离群点，即topnDkOutlier12。要得到topn个离群点，需要计算每个点的离群得分D(kp)，相应地需要计算每个点与数据集中其他点之间的距离以搜索该点的k个最近邻，导致O(N2)的时间复杂度。因此提高算法效率的关键在于减少k近邻搜索时数据点之间距离计算的次数，这也正是本文要解决的其中一个问题。2DODC算法该算法的配置由一个主节点和若干工作节点组成。其主要思想为：首先在主节点处采用某种聚类方法将原始数据集划分成簇。然后由主节点将划分的簇分别发送给各个节点，各个节点读取相应簇中的数据并在簇的范围内构建索引。

7、该索引能够使算法以一种尽可能早处理离群点的顺序进行检测，这样在初始阶段就可以使截断阈值获得一个较大的值，进而可以提高剪枝效率。最后以一种“推拉”循环模式进行并行计算并在该计算过程中结合两个优化策略和两条剪枝策略来提高离群点的检测速度。下面给出该算法的详细步骤。2.1 聚类阶段该阶段的目的是对数据集进行较快的大致聚类，算法的效率是关键。由于数据量比较大，为了提高算法的时间效率，本文在主节点处采用聚类中具有较低时间复杂度的利用分层的平衡迭代规约及聚类(BalancedIterativeReducingandClusteringUsingHierarchies，BIRCH)13算法。该算法适用于大数

8、据集，能够在有限的计算机资源和可接受的时间内对不断产生的数据进行动态的增量式聚类。该算法的I/O消耗是线性的，对数据集一遍扫描就能产生高质量的聚类结果，其中聚类特征(ClusteringFeature,CF)和CF树13是BIRCH算法的关键。本文采用BIRCH聚类算法单遍扫描数据集进行聚类，其主要步骤如下：步骤1扫描数据库，动态地建立一棵存放在内存的CF树；步骤2对叶节点进一步利用一个全局性的聚类算法，改进聚类质量。具体建树的步骤如下：步骤1给定一个初始阈值T并初始化一棵CF树t;步骤2扫描数据点并插入到t中；步骤3此时已经扫描完所有的数据点，将存储在磁盘中的潜在异常点吸收到t中，结束建树。

9、聚类后以每个叶节点中包含的所有子聚类为一个簇，如果有m个叶节点，即得到m个簇。并且根据CF13中包含的信息，可以计算簇质心：X0=(ENi=1Xi)/N。假设两个簇的质心分别是X01和X02,如果用簇质心之间的距离来度量簇之间的距离，那么很容易计算出任意两个簇之间的欧氏距离：D0=(X01-X02)212。对每个簇Ci，为其构建一个列表Ldi，其形式如下：这里假设C1,C2,，Cm-1是按照它们到簇Ci距离的升序排列的。基于该排序给出优化策略1。优化策略1在离群点检测过程中，对任意聚类Ci中的任一点来说，其k个最近邻很可能出现在Ci和与Ci相近的几个簇中，因此，只需优先在最近的几个簇中搜索就很

10、有可能找到点的最近邻，而不需在整个数据集中搜索。2.2 索引构建阶段为了能够以一种尽可能早处理离群点的顺序来处理数据集中的点，以使阈值在初始阶段获得一个较高的值进而来提高剪枝效率，本文在各个节点处的簇中并行构建索引。该算法以每个簇的质心为参考点，按照簇内其他点到簇质心的距离的降序构建一个索引列表记为L，其形式为：其中nc是簇中包含的数据点数，点pl,p2,，pnc是按照它们到簇质心Xi距离的降序排列的。由于离簇质心较远的点很可能是离群点，如果先处理那些点，离群点就有可能先被处理，进而可以使阈值在初始阶段得到一个较高的值，那么在后续的处理过程中就可以剪枝掉大量的点。图片图1基于参考点构建索引为了

11、详细阐述上述思想，下面以图1中的一个小数据集来说明。假设数据集D=p1，p2，p3，p4，p5，p0，以p0为参考点，按照上述方法构造一个索引序列，如图1右半部分所示。基于离参考点越远的点就越有可能是离群点这一思想，需要按照p3fp2fplfp5fp4的顺序来处理上述数据集中的点。这样处理的结果是p3,p2优先处理，假设参数k=2,n=2,那么此时的阈值c=Dk(p2),按照这个顺序获得该阈值只需检测两个点就可以了，如果以随机的顺序检测很可能需要检测许多不必要的点后才可以获得此阈值。按照这个顺序处理还可以得到一个新的停止规则，如下所示。定理1停止规则。Li为簇Ci构建的索引，Xi是用于构建索引

12、时的参考点(即Ci的质心)。pt是当前被处理的任意测试点。如果IIpt-XiII+11Xi-pn-k+1|算法1在各工作节点处的分布式计算。输入：k，Ci。步骤1在接收到的簇中构建索引L。步骤2对Ci中的每个点初始化其CNk和r。步骤3对索引序列L上的每个点p，如果满足定理1则终止算法；否则转步骤4。步骤4在Ci中查找点p的k最近邻，如果|CNk(p)|minDk(q,D):qGOk,那么替换掉具有最小Dk(y)的那个点，其中yGOk将p添加到Ok中；转步骤3。分布式算法的关键部分是终止标准。本文算法采用如下方法：每个节点Pi记录它剪枝掉的点的数目m,主节点记录它接收到的潜在离群点的数目p;主节点定期地查看工作节点