基于马尔科夫随机游走的两阶段离群检测算法

席婷婷，赵旭俊，苏建花

太原科技大学计算机科学与技术学院，太原 030024

目前，在已有的无监督离群点检测方法中，已经验证了基于邻域的方案[1]对于离群点检测是非常有效的，并被广泛地应用于各个方面。此类算法从局部出发，通过每个对象的邻域来看其孤立情况，既可以检测各种形状的簇，同时也适合于全局情况，该方法从预定义的邻域大小推导出距离或密度来衡量每个对象的异常值得分。

然而，这类算法也存在很多问题。第一，如何选择合适的邻域大小，即参数的选择问题。几乎所有的异常点检测算法都要求一个或多个参数的输入，参数k的值的选择影响着相关算法的性能。以LOF[2]算法以及其改进算法RDOS[3]为例，参数k的值的选择在很大程度上取决于数据集的先验知识，即使是有经验的用户要选择一个适当的k值也不是一件容易的事。第二，如何测量对象偏离其相应正常数据点的程度。大部分的离群点检测算法定义了各种计算离群分数的函数，目的是为每个对象分配一个离群点分数，以此将真实的离群点与正常点区分，然而每个点的计算均需要从全局出发，使得算法效率大大降低。第三，Wang 等人[4]将马尔科夫随机游走应用到离群点检测中，将平稳分布向量作为离群点分数，其算法效率和精度大大提升。然而这类算法在随机游走的过程中极有可能访问不到处于边缘的孤立节点，产生悬挂链路问题，使得随机游走在达到平衡之前提前终止。针对该问题现有的解决方案是给离群点赋予更多的权重，使其有更多的机会被访问，但并未充分考虑该节点周围的局部信息。

本文提出了一种基于马尔科夫随机游走的两阶段离群点检测算法，该算法第一阶段根据均匀采样策略生成一系列的DLS-delaunary 图，在不依赖用户指定参数的情况下，为下一步马尔科夫随机游走提供每个数据对象的链路结构，减少参数对算法精度的影响。第二阶段利用节点的连通性，得到转移概率矩阵，引入并重新定义重启向量，将本节点及其相邻节点的连通性考虑在内，确保DLS-delaunary 图中的每个节点都有机会被重新选中，以此解决悬挂链路问题，从而确定马尔科夫随机游走的方式，该图强大的连通性也保证了随机游走过程能够得到唯一的平稳分布向量。由于离群点对象的数量比正常点对象的数量要少得多，则导致离群点在不同图上的偏差值会远远大于正常点的偏差值，因此，访问概率发生巨大的变化的点就是要找的离群点。

1 相关工作

近年来，基于邻域离群点挖掘的研究取得了一定的进展，研究者们已经提出的一些相关检测算法并得到一定程度的应用。本章主要研究两种类型的孤立点检测：基于邻域信息的方法和基于图形的方法。

1.1 基于邻域的离群点检测方法

在这类算法中，邻域的定义起着重要的作用，合理的邻域的定义可以有效地提高算法的性能[5]。Campos等人[6]在各种数据集的基础上，提供了基于局部信息的孤立点检测方法的全面的比较。KNN是最著名的分类算法之一，将对象与其第k个最近邻的距离视为异常值得分，以适应离群点检测的问题。该方法简单且有效，可在均匀分布的数据集中找到异常值，但是不能找到适当的k值来捕获具有不同密度的数据集的异常值。为了降低人为因素对实验结果的影响，其改进算法RKNN算法[7]在不需要提前指定参数k的情况下，可自适应的选择近邻来确定k值。Wang 等人[8]提出了一种有效的基于MST 的kNN 的离群点检测方法，它可以同时检测全局和局部离群点，但因为在现实中，通常很难检测到所有符合用户直觉的异常值，因此可将其作为一个组件纳入当前的离群点检测框架可能是有意义的。石鸿雁等人[9]也为降低人为因素做出了贡献，但是实验结果仍然摆脱不了参数的选取。LOF 通过引入一个局部可达距离来估计每个数据对象的局部密度来解决这个问题，离群点分数被定义为k-邻域内的平均局部密度与物体的局部密度之比。

由以上可知，基于邻域的算法对于离群点检测是有效的，然而还存在两方面的问题：一是对用于确定邻域的大小的参数是敏感的；二是当待观察值具有多样性时，性能会比较差。因此，本文考虑遵循上述研究的理念，并尝试依据所建的图形来捕获每个数据对象周围的邻域关系。

1.2 基于图形的离群点检测算法

近年来，由于基于图形或网格的离群点检测方法具有鲁棒性，在数据集中捕捉远距离关联性的能力非凡以及能够有效地捕获数据集中隐含的潜在连接等优点，引起了越来越多学者的兴趣。Akoglu 等人[10]和Randshus等人[11]提供了基于图的离群点检测方法以及由动态网格表示的数据的全面调查。但是，基于图的离群点检测算法强调了数据集的整体结构，但很少注意每个节点周围的局部信息，从而导致了高假阳性。OutRank 算法[12]首先提出利用随机游走过程的平稳分布来表示每个数据的离群程度，该方法从原始数据构造一个完全连通的无向图，然后应用马尔可夫随机游走过程计算离群点分数。ODIN 算法[13]是基于索引数的孤立点检测算法，通过数据的局部信息构造有向无权图，然后利用图结构信息来定义离群点的得分，该算法的核心思想是：在有向的k近邻图中，离群点的索引数明显小于正常点的数量。该方法只考虑了图的静态结构信息，而忽略了可能隐藏在图中的相关性。FKMOD算法[14]通过构造剪枝的k-近邻最小生成树来确定全局离群点，但是算法在进行剪枝确定聚类时仍需要参数设定。RDOS 算法用共享邻居扩展了邻域定义以确定给定对象的局部信息，并且还采用核密度估计来估计局部密度。VOS 算法[15]与以前的研究相比，特别设计了一种利用每个对象的top-k相似邻域构造了一个加权有向的虚拟图，这一机制确保了所提出的虚拟图能够发挥有效作用。但该算法还有其无法改进的问题，比如算法中k值仍然是人为定义以及关于虚拟点的存在虽然可以将全局信息考虑在内，但该点的位置却会影响每个点的访问概率。

2 基于马尔科夫随机游走的离群点检测

现有的基于马尔科夫随机游走的离群点检测，存在两个关键性的问题：第一，如何适当的构造邻域图进行数据点的相似性度量；第二，如何在随机游走达到平稳状态时，使离群点的访问概率明显区别于正常点。针对上述问题，本文提出了基于马尔科夫随机游走的两阶段离群点检测算法，首先，利用数据集的几何关系构造适合马尔科夫随机游走的DLS-delaunay图；然后根据潜在异常值应该具有较低的访问概率的假设，采用重新定义的重启向量来解决孤立节点引起的悬挂链路问题；最后采用迭代方法，在随机过程达到平衡后，将平稳分布的平均偏差值作为每个对象的离群分数。

2.1 构建DLS-delaunary图

针对现有的基于马尔科夫随机游走的算法，邻域图的构建都仅仅依赖于用户给定的固定参数，而未考虑每个点周围的实际情况。本文提出使用DLS-delaunary图的几何关系来确定每个数据对象的邻域，图中每个数据对象与该点空间上相邻的点都存在边直接相连，从而形成一种有效的邻域关系。

定义1 Delaunay三角剖分。对给定n×n的空间数据集D=(X1,X2,…,Xn)进行三角网划分，其中当划分成的三角网满足以下两个特性即为delaunay 三角剖分图G(V,E)：

（1）空球准则，单个三角形或不规则的四面体的外接圆或外接球内部不包含除顶点外的其他点。

（2）最大-最小角准则，每个三角的角度都满足是所有可能三角形中最小的。

定义2 DLS-delaunary 图。设有无向图G(V,E)为delaunary 三角剖分图，其中V表示三角剖分图中各个三角形顶点集，E表示三角剖分图中各个三角形的边的集合，图中数据点pi与pj相连的边为edge(pi,pj)，若两点pi到pj间的欧氏距离dist(pi,pj)足以下公式：

则将该图定义为DLS-delaunary三角剖分F(S,T)，即为图G(V,E)的子图，其中F⊂G，S=V，T⊂E，ω为选定侯选边的距离阈值。

定义3 空间邻域。对于任意∀pi,pj∈D，若在定义2 的DLS-delaunary 图中有边edge(pi,pj) 相连，那么pi和pi即为空间相邻点，而数据点pi所有的空间相邻点的集合称为的pi空间邻域DN(Pi)。

由以上定义得出的DLS-delaunary 图为无向图，只将邻域限制在一组具有高相似度的节点上，该方法根据不同数据点周围的具体情况，对数据对象间的相互关系有不同的描述，其中每个节点代表一个数据对象，每条边表示两个节点之间的相似性，据此图即可得出有关整个数据集中每个数据对象的相似性信息。以下为构建DLS-delaunary图的详细步骤。

步骤1 计算数据集D的样本期望。

假设有数据对象pi,pj∈D()i,j=1,2,…,n，点之间的邻域关系用边edge(pi,pj)表示，构造delaunay三角剖分，用N(Pi)表示pi的所有邻居，由于在delaunay 三角剖分图中，所有边的概率均为1n，即样本的期望可简化为样本均值mean(p)的计算，如下：

其中，Sdist(pi,pj)是pi和pj之间的欧式距离，也就是三角剖分图edge(pi,pj)的长度。

步骤2 计算数据集D的标准偏差.以贝塞尔公式来计算求得delaunay三角剖分图与pi相关的所有边的标准差ST_dev(pi)，如公式（2）所示：

通过循环迭代公式（2）即可得到delaunay图所有边的标准差。由于聚类边界中的点倾向于具有比簇内的点拥有更长的delaunay 边edge(pi,pj)，在现实世界中，由长边连接的簇间点不能定义为相邻点。

步骤3 建立DLS-delaunary图，制定边的移除规则。

对于图G(V,E)上任意一点p，设p与点相连点的集合为U，若U′是包含所有到p点的欧氏距离小于等于ω的边的集和合，则：

以p点为起点当点v与p点距离小于预设值的侯选边edge(v,p)会被加入候选集合U′中，组成每个点的新的邻域。对于每个数据对象v，如果其邻居v∈N(v)满足公式（3），则加入到候选集合U′，将不符合条件的边移除即移除edge(v,p) ，并将边edge(v,p) 从v的邻域N(v)中删除，再从p的邻域N(pi)中删除点v。对于delaunary 三角剖分图中所有的点p连接的边均用公式（3）鉴别，将不符合条件的边舍弃，重复循环迭代直至所有的边均在给定范围内。由上述步骤可知，DLSdelaunary 图阈值的选择只取决于数据集D，即相应数据集的均值和标准差，并且可以在不依赖用户的情况下自动导出，由此得到自动阈值的离群点检测算法。

2.2 基于DLS-delaunary图邻域相似性

由于马尔科夫随机游走的方式是由DLS-delaunary图节点的链路结构来确定的，因此，若一个数据对象与图中其他对象的连通性较低，那么该点更有可能是一个离群点。而一个节点的连通性是根据图中相关节点给出的加权投票来确定的，加权投票法的规则为高连接性节点比低连通性的节点投票的权重更大，来自任意节点投票的权重大小按与源节点相邻的节点的数量来缩放。本文算法通过考虑节点的连通性和邻居节点的分布来决定一个节点的权值，因此某一节点的连通性是由本节点的连通性和相邻节点的连通性来表示的，正如公式（4）所示：

对于n个节点p1,p2,…,pn，可以任意分配每个节点的初始连接性值（例如Cpi=1/n,1 ≤i≤n）并递归地进行计算，以细化每次迭代中每个节点的连通性的值，这种迭代过程称为幂方法，常用于求矩阵的主导特征向量，通过将该场景建模为马尔可夫链来细化每个节点的连通性。

定义4 数据对象的相似性simpi,pj：

其中distpi,pj表示pi和pj之间的边的距离，其中若pi和pj之间的不存在边，则认为distpi,pj=∞。注意，对象与自身的相似性设置为零，以避免底层图形表示中的自循环，这样的循环应该被忽略，因为这对每个节点都是存在且常见的，因此对于区分正常对象和异常值并不是很有用。

数据集D中所有对象之间的关系用n×n的矩阵sim(pi,pj)表示，其中n是D中数据点的个数，矩阵中的每个条目(simpi,pj)对应于上面定义的对象i和对象j之间的相似性，将此相似矩阵作为图的邻接矩阵。如果两个节点的相似性度量大于零，则两个节点X和Y通过边连接，并且将simpi,pj作为该边的权值如公式（5）：

2.3 基于马尔科夫随机游走的离群点度量

由于W矩阵中除了对角线外，还有可能存在一些零项的行或者列，将会导致随机游走没有机会到达该点，也就是说使用DLS-delaunary 图可能导致三角剖分图被分割成几个孤立的子图，产生悬挂链路问题。针对该问题，本文算法引入并重新定义重启向量，使得邻接矩阵中每个条目都大于零，使得每个节点都有被选择的机会，这将确保本地信息图中的每个节点都有机会被重新选中，同时还避免引入新的孤立节点。

定义5 定义重启向量

m=(sim(n1),sim(n2),…,sim(nn))

这种归一化确保了转换矩阵的每一行的元素和为1，这是马尔可夫链的一个基本性质。在利用公式（6）计算完转移概率矩阵S(i,j)，需要使其既不可约又非周期，才能收敛到唯一的平稳分布。在过去这个问题已经由文献[16]解决了，在他们的迭代过程计算中，保留一个低概率值来重新启动随机游走：

其中S是行归一化过渡矩阵，d称为阻尼因子，I是单位列向量(1,…,1)T。直观地说，可以看作是允许随机步行者以概率d传输到图中的任何节点，即使这些节点不与当前访问的节点相邻。利用迭代方法，可以计算邻域图上马尔科夫随机游动过程的平稳分布。迭代过程的形式为公式（7）：

达到平衡后节点的访问概率。本文算法为了提高效率，本算法采用自动生成一系列DLS-delaunary 图的方法，针对其每个Gα(0<α

根据上述定义，对象的离群点分数为其访问概率在各个Gα图上平稳向量的平均偏差值，在这种情况下，由于离群点对象的数量比正常点对象的数量少得多，则导致异常点在不同图上的偏差值会远远大于正常值，也就是说异常点的离群点分数会比正常点对象的离群点分数大得多。因此，具有较大离群点分数的对象表示其在不同图上的访问概率发生了巨大的变化，这表明它有更高的机会成为一个离群点。

3 基于马尔科夫随机游走的两阶段离群点检测算法

本文算法基本过程分为两个阶段：第一阶段，根据数据集以及公式（1）（2）（3）对三角剖分图进行调整，删除对表达相似性无效的边，构建DLS-delaunary图，并得到每个点的拓扑结构；第二步，建立相似矩阵S与转移概率P，对该图进行马尔科夫随机游走，计算各个图平稳分布的平均偏差值，从中选取分数最高的前n个对象作为离群点。由于用到了DLS-delaunary是本算法的特色，因此将该算法简称为DLS算法描述如下：

算法基于马尔科夫随机游走的的两阶段离群点检测算法

现有的利用马尔科夫随机游走的算法，例如VOS算法[15]，该算法添加一个虚拟节点和2n条虚拟边来构造强连通图，然后在该图上执行量身定做的马尔科夫随机游走来衡量每个数据对象的离群程度。该方法主要存在两方面的问题：第一，利用虚拟节点和虚拟边构造强连通图是极容易受到虚拟节点位置的影响，而且有可能引入新的孤立节点，从而影响算法的精确度。第二，马尔科夫随机游走的过程是由虚拟边的权值决定的，为了使其不直接移动到虚拟点，该算法给定数据点到虚拟点间的权值较小，这一过程并未将数据对象周围的实际情况考虑进来。本文所提出的两阶段离群点检测算法，在第一阶段，利用算法步骤1 到步骤6 构造DLS-delaunary图，避免了引入新的孤立节点，将空间上相邻的点都赋予边直接相连，在用户不用输入任何参数的情况下，为下一步的马尔科夫随机游走提供每个节点的链路结构。在第二阶段，也就是算法的步骤10到步骤15，为了使得每个数据点均有机会被访问，在此阶段引入并重新定义了重启向量，即使出现数据对象较为稀疏的情况，仍然可以得到平稳分布向量；在本阶段马尔科夫随机游走的方式是转移概率矩阵决定的，而转移概率矩阵将节点的连通性考虑在内，使得随机游走的方式和数据点的真实分布直接相关，以此提高算法的准确性。

4 实验分析

为了验证基于马尔科夫随机游走的两阶段离群点检测算法的有效性，4.1 节首先选取了两个不同形状的合成数据集，计算结果表明，本文算法可以适应于不同的分布数据集。此外，4.2 节简要介绍了选定的10 个UCI数据集的预处理过程以及对比算法，并利用ROC曲线、AUC以及精确度来测试算法的性能。

4.1 人工合成数据集

由于利用邻域信息计算离群点分数的离群点检测方法容易受到数据集分布的影响，为了测量所提出的算法在不同分布的数据集上的适应性，构造了两个不同形状的人工合成数据集如图1 所示。其中图（a）和（d）的横纵坐标均为数据点的横纵坐标。第一个数据集如图1（a）所示，包含一个环状簇750 个点和随机生成的35 个离群点，其中远离环状区域的点称之为离群点。第二个数据集如图1（d）所示，是一条余弦波曲线，由501 个点作为正常点和从高斯分布中随机采样的42个点作为离群点组成。

首先对两个人工合成数据分别建立DLS-delaunay三角剖分图，结果如图1（b）和（e）所示，其中连接点之间的灰色线条代表DLS-delaunay 图得到的数据点间的拓扑关系，然后依据该图进行马尔科夫随机

游走计算了上述两个数据集中每个对象的离群点分数，依照Top-n以区分正常点与离群点，结果如图1（c）和（f）所示，其中黑色和橙色分别表示正常点和离群点。由图1可知，本文算法可为之字形数据集Zigzag和环状数据集Ring 检测出真正的离群点，并为孤立点对象分配了相对较小的分数，并且将人工数据集Ring 和Zigzag 应用到经典算法VOS、OutRannk 以及RDOS 上，如表1 所示，可以看到DLS 算法性能优于其余3 个算法。主要原因是在获得DLS-delaunary图的基础上得到了每个数据点的邻接关系，并不需要人为设定参数，依此得到的相似矩阵更能代表数据点之间的关系，使得算法有了良好的基础；此外，再利用连通性构造的重启向量，进行马尔科夫随机游走，使得算法的准确率大大提高，表明了所提出的算法对于不同的数据分布具有较强的适应性。

图1 Ring 和Zigzag数据集的DLS算法的执行过程Fig.1 Execution process of DLS algorithm for Ring and Zigzag datasets

表1 Ring和Zigzag不同算法的AUC值Table 1 AUC values of Ring and Zigzag algorithms

4.2 真实数据集

4.2.1 数据集和评价标准

在本文研究中采用了Emmott方法构造了来自UCI数据存储库10 个真实世界数据集，详细的预处理过程参照文献[17]，数据集的详细信息在表2。在每个数据集中，来自小类（ES）的样本被视为异常值，使用归一化过程将每个属性值缩放到一个[0，1]范围内，同时将重复的样本和那些包含缺失值的样本丢弃，其中数据的孤立点标签信息不是用来提高算法的性能，而是仅仅用来评估结果。

表2 10个真实数据集的特征Table 2 Features of 10 real datasets

由于异常值检测邻域有一项具有挑战性的任务是严格的类不平衡，也就是离群点对象的数量要远远小于正常点对象的数量，因此在离群点检测邻域，很少有研究直接使用传统的度量方式。本文通过评估所有可能的决策阈值，可以得到ROC曲线，这表明正确分类的阳性样本（离群点）的数量，称为为真阳性，错误分类的阴性样本（正常样本）的数量称为假阳性，并且该曲线越接近于左上角证明模型效果越好。AUC即为计算ROC曲线下的面积，其值从0到1不等，越接近于1，证明算法模型效果越好。设n是用户期望从离群点检测算法中得到的离群点对象的数量，TP和FP分别表示真实离群点的数量和被错误标记的正常点的个数，FN 为被错误标记的真实离群点的个数。TPR（true positive rate）、FPR（flase positive rate）和精度的计算如下：

特别是，一个完美的模型将得到一个接近1的AUC的分数，而随机模型的分数将等于0.5。当模型被分配到相对较大的AUC 分数时，模型更可取。在下面的部分中，本文使用ROC 和AUC 将所提出的算法与其他3种方法进行比较。

4.2.2 真实数据集不同算法比较结果

为了验证本文提出的基于马尔科夫随机游走的两阶段式离群点检测算法优于传统的离群点检测算法，将所提出的算法与其他3 种使用局部信息或随机游走过程来决定离群点分数的算法进行了比较。将DLS、VOS、OutRannk 以及RDOS 算法在10 个真实的数据集上进行测试，并使用相同的实验环境，实验结果如表3所示。

表3 在10个数据集上最好的AUC和Precision score结果Table 3 Best AUC and Precision score results on 10 datasets

为了更直观地证明本文算法的性能，进一步采用ROC曲线来评估检测结果，其中本文画出了4个数据集的ROC 曲线，如图2 所示，图中右下角的area 值代表ROC 曲线下的面积，由4.2.1 小节可知area 值越接近于1，代表算法性能越好，因此DLS算法在这4个数据集上是优于其余算法的。而对于Synthetic-control 和Arrhythmia 数据集出现折线主要是因为数据量较小而且数据间的差距较小，导致最终计算的假阳性即FPR值有重复，为了使图像呈现结果更接近真实性，没有对折线进行平滑处理。

图2 不同算法在4个数据集上的ROC AUC分数Fig 2 ROC AUC scores of different algorithms on four datasets

为了验证本文提出的根据三角剖分图自动确定阈值的方法优于传统的基于k值确定邻域信息的方法，本节通过将k的值从2调整到100来对每个数据集进行附加实验，如图3。对于VOS 和RDOS，实验结果将随着邻域大小k的变化而急剧变化，而DLS和OutRank不需要一个参数来指示邻域大小，将实验结果应用于所有k设置的值，实验结果如图3 所示。现将表2 中性能较为优越的两个数据集glass和Breast-cancer--wisc-diag进行不同k值的分析，由图3可以看到在这两个数据集上本文所提出的算法不论其他3 种算法取何k值都会有较高的AUC 值。在k值较小的时候，DLS 算法可自动为每个数据点分配合适的邻域，并使用平稳分布向量的平均偏差值可以有效的区分正常点和离群点，从而提高算法的性能，而图中OutRank 和RDOS 的效果性能比较差，主要是因为从正常点到离群点的边会大幅度减少，可能会导致降低随机步行者从正常点跳到离群点的概率，使目标离群点很难得到所需的分数。另一方面，从图中我们也可以观察到，当k较大时，DLS 算法是基于节点的连通性来确定马尔科夫随机游走的转移概率矩阵和重启向量，可得到唯一的平稳分布向量，这也就使算法的准确性仍然高于其余算法，其中VOS 算法和OutRank 算法的AUC 值会比较接近本算法，其原因是，即使在离群点对象之间形成簇时，k设置为一个较大的值，仍然存在连接正常点和离群点的边缘，并确保随机步行者可以从正常节点跳到离群点，但是往往需要较大k值才能有较高准确率，因此k值的选择仍然不可避免的影响算法的准确性。

图3 不同k 值的不同算法的ROC AUC分数比较Fig 3 Comparison of ROCAUC scores of different algorithms using different k values

本文算法中，为了提高效率选择自动生成一系列的邻域图，而为了验证生成邻域图的数目对实验的结果的影响，选择4个数据集在不同邻域图数量的前提下进行实验，邻域图的数量分别为7，80，100，180，260，320，360，440，520，600，实验结果如图4 所示。从图4所示的结果可以看出，随着图数的增加，算法的性能开始增加。当该值达到65左右时，性能趋于稳定，具体针对每个数据集有不同的值，主要是因为每个数据集有不同的维度。此外，这一趋势几乎适用于所有的测试数据集，这也就意味着我们提出的DLS 算法对图的数量并不敏感。

图4 图的数量对AUC值得影响Fig.4 Influence of AUC values under number of graphs

在证明了本文算法的有效性之后，使用真实数据集Waveform-noise 和Arrhythmia 对算法的性能进行实验测试，将本文算法在最优状态下的时间与VOS、Out-Rank、RDOS 算法的时间相比较，实验结果如图5 所示。该图显示，本文所提出的算法，无论在哪个数据集上，其运行时间都比较短，充分说明本文提出的算法相比于对比算法有更高的效率。其主要原因一是本文算法采用均匀采样策略，在不影响算法效率的前提下，尽可能的将算法效率优化；二是当建立完成DLS-delaunary图后，即可得到每个点的近邻，也就是说本文算法在寻找每个点近邻时不用从全局出发，也就是说避免了每次都将全部点遍历一遍，有效的降低了时间复杂度。

图5 不同算法效率对比Fig.5 Efficiency comparison of different algorithms

5 结束语

在分析了基于随机游走的图模型的特点后，提出了一种新的离群点检测算法：基于马尔科夫随机游走的两阶段离群点检测算法。该算法从DLS-delaunary图中推导出转移概率矩阵，由于其并不依赖于特定的阈值，因此即可确保对不同应用场景的适应性；为了解决悬挂链路问题，本文提出了基于相邻节点的重启向量，然后利用马尔科夫随机游走过程得到平稳分布向量，而平均偏差值可以有效地区分正常点和潜在的离群点对象。最后对人工数据集和UCI数据集进行了广泛实验，结果表明，该方法在10 个真实世界的数据集中优于一组基于局部信息的算法以及基于马尔科夫随机游走的算法。

此外借助三角剖分图计算节点间的拓扑结构和计算随机游走的平稳分布也是耗时的过程，也限制了本文算法在大规模和流数据中的应用。因此，如何克服这一特殊问题，开发出新的算法，既可以加快过程，同时又能保持算法性能，也是未来研究的方向。