Two-Stage Outlier Detection Algorithm Based on Markov Random Walk

doi:10.3778/j.issn.1002-8331.2012-0352

Abstract

Abstract: In the neighborhood-based outlier detection algorithm, the selection and determination of parameters is an important issue. Unreasonable parameter selection leads to a significant decrease in the performance of the algorithm. In order to reduce the influence of parameters on outlier detection, a two-stage outlier detection algorithm based on Markov random wandering is proposed, which can effectively reduce the influence of parameters on detection results without affecting the efficiency of the algorithm. The algorithm firstly conducts a uniform sampling strategy to generate a series of triangulation graphs, and the removal rules are introduced to get the topology structure of the node, so that the algorithm obtains a transition probability matrix defined by the node connectivity, which reduces the computational complexity and running time of the algorithm. Secondly, the weighted voting principle is used to redefine the restart vector, and the average deviation of the smoothly distributed vector on different graphs is used as the outlier score, which effectively improves the accuracy of the algorithm. Finally, the synthetic data set and UCI data set are used to verify that the algorithm has a higher accuracy rate than the existing algorithm.

Key words: outlier detection, DLS-delaunary, Markov random walk

摘要： 基于邻域的离群点检测算法中，参数的选择与确定是一个重要的问题，不合理的参数选择导致算法的性能显著下降。为减少参数对于离群点检测的影响，提出了一种基于马尔科夫随机游走的两阶段离群检测算法，可以在不影响算法效率的基础上，有效降低参数对检测结果的影响。该算法采用均匀采样策略生成一系列三角剖分图，并引入移除规则得到节点的拓扑结构，从而获得由节点连通性定义的转移概率矩阵，有效减少了算法的计算量和运行时间；其采用加权投票原则重新定义重启向量，并将不同图上得到的平稳分布向量的平均偏差值作为离群点分数，有效地提高了算法的准确性。采用合成数据集以及UCI数据集，验证了该算法与现有的算法相比有更高的准确率。

关键词: 离群点检测, DLS-三角剖分, 马尔科夫随机游走

XI Tingting, ZHAO Xujun, SU Jianhua. Two-Stage Outlier Detection Algorithm Based on Markov Random Walk[J]. Computer Engineering and Applications, 2022, 58(1): 89-98.

席婷婷, 赵旭俊, 苏建花. 基于马尔科夫随机游走的两阶段离群检测算法[J]. 计算机工程与应用, 2022, 58(1): 89-98.

References

[1] CHEN Y，MIAO D，ZHANG H.Neighborhood outlier detection[J].Expert Systems with Applications，2010，37（12）：8745-8749.
[2] BREUNIG M M，KRIEGEL H P，NG R T，et al.LOF：Identifying density-based local outliers[J].ACM Sigmod Record，2000，29（2）：427-438.
[3] TANG B，HE H.A local density-based approach for outlier detection[J].Neurocomputing，2017，241：171-180.
[4] WANG C，GAO H，ZHEN L，et al.A new outlier detection model using random walk on local information Graph[J].IEEE Access，2018，6：75531-75544.
[5] ZHU Q，FENG J，HUANG J.Natural neighbor：A self-adaptive neighborhood method without parameter K[J].Pattern Recognition Letters，2016，80：30-36.
[6] CAMPOS G O，ZIMEK A，SANDER J，et al.On the evaluation of unsupervised outlier detection：Measures，datasets，and an empirical study[J].Data Mining & Knowledge Discovery，2016，30（4）：891-927.
[7] LONG S，ZHU W.Outlier detection for learning-based optimizing compiler[C]//Proceedings of the 5th International Conference on Frontier of Computer Science & Technology，2010：570-575
[8] WANG X，WANG X L，MA Y，et al.A fast MST-inspired kNN-based outlier detection method[J].Information Systems，2014，48：89-112.
[9] 石鸿雁，马晓娟.改进的DBSCAN聚类和LAOF两阶段混合数据离群点检测方法[J].小型微型计算机系统，2018，39（1）：74-77
SHI H Y，MA X J.Two-stage outlier detection method based on DBSCAN clustering and LAOF of hybrid data[J].Journal of Chinese Computer Systems，2018，39（1）：74-77.
[10] AKOGLU L，TONG H，KOUTRA D.Graph-based anomaly detection and description：A survey[J].Data Mining & Knowledge Discovery，2015，29（3）：626-688.
[11] RANSHOUS S，SHEN S，KOUTRA D，et al.Anomaly detection in dynamic networks：A survey[J].Wiley Interdiplinary Reviews Computational Stats，2015，7（3）：223-247.
[12] MOONESINGHE H D K，TAN P N.OutRank：A graph-based outlier detection framework using random walk[J].International Journal on Artificial Intelligence Tools，2008，17（1）：19-36.
[13] HAUTAMAKI V，KARKKAINEN I，FRANTI P.Outlier detection using k-Nearest Neighbour graph[C]//Proceedings of the 17th International Conference on Pattern Recognition，2004：430-433.
[14] 朱利，邱媛媛，于帅，等.一种基于快速k-近邻的最小生成树离群检测方法[J].计算机学报，2017，40（12）：224-238.
ZHU L，QIU Y Y，YU S，et al.A fast kNN-based MST outlier detection method[J].Chinese Journal of Computers，2017，40（12）：224-238.
[15] WANG C，LIU Z，GAO H，et al.VOS：A new outlier detection model using virtual graph[J].Knowledge-Based Systems，2019，185：1-12.
[16] MOONESIGNHE H D K，TAN P N.Outlier detection using random walks[C]//Proceedings of the IEEE International Conference on Tools with Artificial Intelligence，2006：532-539.
[17] GCAMPOS G O，ZIMEK A，SANDER J，et al.On the evaluation of unsupervised outlier detection：Measures，datasets，and an empirical study[J].Data Mining & Knowledge Discovery，2016，30（4）：891-927.