基于图上随机游走的离群点检测算法

杜旭升 ，于 炯 ，*，叶乐乐 ，陈嘉颖

（1.新疆大学软件学院，乌鲁木齐830008； 2.新疆大学信息科学与工程学院，乌鲁木齐830046；3.西安交通大学软件学院，西安710049）

（∗通信作者电子邮箱yujiong@xju.edu.cn）

0 引言

离群点是指那些在数据集中偏离大多数对象，让人不得不怀疑它是由某种不同于其他大多数对象的机制所产生的数据对象［1］。换言之，数据集中的绝大多数对象都服从某种确定的模式P，而离群点是那些不服从模式P的数据对象［2］。离群点检测常用于如网络入侵检测、医疗辅助诊断、金融欺诈检测、交通流中异常行为检测、变质农畜产品检测等，在天文学中离群点检测也被用来发现新天体［3-7］。

传统的无监督离群点检测算法，如基于距离的LDOF（Local Distance-Based Outlier Factor）、CBOF（Cohesiveness-Based Outlier Factor）及基于密度的 LOF（Local Outlier Factor）算法在检测高维数据集和大规模数据集时，存在检测率低、算法执行时间长、对参数敏感等问题。针对上述问题，本文提出了一种基于图上随机游走（Based on Graph Random Walk，BGRW）的离群点检测算法。

基于图上随机游走的离群点检测算法，将待检测数据集中的数据对象建模为图中的顶点，图上各顶点相连边上的权重表示漫步者由某一顶点出发，一步移动到另一顶点的概率。BGRW算法通过计算数据集对象间的转移概率，并通过用户预设的迭代次数和阻尼因子，迭代计算出所有对象的离群值。在UCI（University of California，Irvine）真实数据集与合成数据集实验表明，BGRW算法与无监督检测算法相比，在检测率与执行时间和误报率等指标上效果具有明显的提升。

基于图上随机游走的BGRW离群点检测算法的主要创新之处在于：