基于图的情境离群点检测方法

李涛，张芸，黄志宏

(华南农业大学 现代教育技术中心，广东 ，广州 510640)



基于图的情境离群点检测方法

李涛，张芸，黄志宏

(华南农业大学 现代教育技术中心，广东 ，广州 510640)

针对异常模式挖掘中的情境离群点检测问题，提出一种基于图的检测方法.首先对数据实例构建一个实例图，然后采用一个滑动窗口穿越数据实例，对处于滑动窗口内的数据实例，计算结点之间的闵可夫斯基距离作为边权值，然后采用最小生成树聚类算法对实例图进行聚类，再采用第二个滑动窗口穿越数据实例，根据窗口内的数据实例是否属于主趋势聚类赋予不同的离群值评分，不属于主趋势聚类的数据实例被认为是潜在的离群点.仿真实验和实际数据分析表明该方法在一元序列数据检测中是切实可行的，该方法具有较好的适用性和扩展性.

数据挖掘；离群点检测；图；聚类

近年来，异常模式挖掘又称离群点检测得到数据挖掘研究社区的重视.情境离群点是一类特殊的异常模式，又称条件离群点，因为它们条件的依赖于选定的情境.情境离群点检测中，数据对象的属性划分为两组：情境属性和行为属性.情境离群点是局部离群点的推广.全局离群点检测可以看做情境离群点检测的特例，其中情境属性集为空.与全局离群点检测不同，在情境离群点检测中，一个对象是否是离群点不仅仅依赖于行为属性，而且还依赖情境属性.情境通过情境属性来定义，通常由用户提供.情境属性可以包括空间属性、时间、网络位置和复杂结构的属性.与一般的离群点检测不同，识别情境离群点需要分析对应的情境信息.

尽管目前开发了很多技术探测离群点，但其中支持情境离群点的方法并不多.目前有两种一般方法被用来解决情境离群点检测问题.第一种是把情境离群点检测转换成传统的点离群点检测.第二种方法是利用利用情境对正常行为建模，数据的结构信息抽取情境离群点.以往挖掘情境离群点的时间序列模型方法通常依赖数据中必须存在周期性规律，这二种方法在面对不存在周期性模式的数据时，一般很难处理.通常情况下，需要一定数量的训练数据实例来构建分类模型.近年来代表性的情境离群点检测方法包括：文献[1]提出利用空间拓扑关系进行条件离群点检测，对空间数据的实验证明效果较好.文献[2]提出了一种条件离群点检测算法，作者改进了基于近邻的情境离群点检测算法，通过去掉比较难设置的参数变量，提高了之前近邻情境离群点检测算法的适用性.文献[3]基于随机游走，提出利用概率方法进行情境离群点检测，通过稳态期望的方式进行离群值评分.

本文方法比起以上文献，原理比较容易理解，具有可扩展性可以扩展到更复杂的数据集.采用基于图的有关算法，包括基于图的最小生成树的聚类算法和滑动窗口技术.该方法可以在不同类型的序列数据中检测离群点，在不存在周期性规律的数据中也同样适用.

1 检测原理与方法

定义1 序列数据：设I={I1，I2，…，Ip}是所有项的集合.项集是项的非空集合.序列是事件的有序列表.序列s记作〈e1e2e3…el〉，其中事件e1出现在e2之间，e2出现在e3之间，事件ej也称为s的元素.

定义2 滑动窗口：给定一个长度m的序列数据集D，和一个用户预先定义的子序列长度α，通过使用一个长度α的滑动窗口穿越D，能够抽取所有长度α的子序列.

本文有关情境离群点检测问题的有关正式定义如下：

输入：一个序列数据实例的集合D，其中包含n个数据实例{d1，d2，…，dn}.其中每个数据实例是情境属性和行为属性的组合，可以定义为一个二元组di=〈xi，yi〉，其中xi为情境属性，yi为行为属性.

输出：离群点实例的集合O；它们的行为属性与它们在数据集中的邻居数据实例存在明显不同.

为简化问题的研究，预先设定：① 所有实例{d1，d2，…，dn}都仅有一个情境属性xi；这对于序列数据和时间序列数据都成立.这类数据集仅有一个情境属性就是时间或者数据实例在数据集中的索引值.但是在空间和时空数据中，情境属性的数量超过一个，通过使用更复杂的滑动窗口技术，本文的算法可以推广到存在多个情境属性的数据集中.② 只有一个行为属性yi;所有实例都有同样数量的行为属性；对于一般同质的数据集这个设定都是成立的，对于异构混杂的数据，每个被检测的数据实例并不是包含同样数量的行为属性，这种情况称为包含分类属性，通过采用其他更复杂的距离测量标准，本文的方法也可以推广到异构混合分类数据集中.③ 所有行为属性都是连续的；这个设定对于日常生活中的序列数据集都是成立的.图1给出了算法流程图.

1.1 构建实例图

设集合D={d1，d2，…，dn}，di=〈xi，yi〉是数据实例对象的集合.首先按照数据集的情境属性对D中数据实例进行排序.再为每个数据实例构建一个结点，生成一个带权图G=(V，E，L，λ，ω)，其中V是图的结点集合，E是边的集合，L是标号集合，λ:V→L，λ是一个标号函数用来给结点分配标号，ω:E→R+是一个权值函数用来对每条边(u，v)∈E分派一个实数w>0作为权值.λ是一个单射函数，G中不存在重复标号.

1.2 生成实例图的边

采用第一个滑动窗口WIN1从左到右扫描穿越数据集.对于数据对象di，dj，如果存在|xi-xj|≤α1，就计算di，dj之间的闵可夫斯基距离：

(1)

闵可夫斯基距离又称为Lp范数，文中取p=3.

然后在实例图G中，与di，dj对应的结点vi，vj之间连通一条边e(vi，vj)∈E，边的权值：

ω(vi，vj)=Dist(di，dj)；

在这一步，滑动窗口的大小参数α1对算法的精确度和效率起到关键作用.对于每个数据实例，要比较的数据实例的个数是2(α1-1).因此这步的运行时间是O(|D|α1)，其中|D|是数据实例的个数.如果α1的值太低，会导致实例图G中连接邻居结点的边太少，图会变的很稀疏，也会导致极差的聚类质量.如果α1的值太大，也会导致图中太多边，严重影响算法的运行时间.α1的最优值取决于被挖掘数据的种类和用户的操作经验，通常α1被设置为轻微大过离群点边界的尺寸.方法如下：如果离群点的集合是O={d1，d2，…，dn}，计算任意两个离群点的情境属性之间的索引距离：dinx(i，j)=|xi-xj|，i，j∈[1，n]，α1的值可以设置为所有索引距离的最大值，这个最大值就是离群点边界的尺寸：

(2)

这样设置α1的值，算法可以在最短的计算时间内取得最大精确度.在运算结束之前通常并不知道这个值的大小，也可以先抽取少量数据作为训练集，来计算出大概的α1的大小，不过这会增加算法的运行时间.

1.3 裁剪实例图G中的边

因为构建实例图G的目的是在下一步中发现一个最小生成树聚类，如果图G中边太多，会导致算法运行时间太长，所以可以在这一步中裁剪某些不必要的边，这对于快速创建最小生成树聚类有好处.因为对于单变量数据每个数据实例都仅有一个行为属性，可以发现一个最小生成树，其中有|D|条边的权值是一样的.尽管下面提出这个裁剪方法并不能帮助改进第一步的运行时间，但是在输入数据是单变量时，它可以减少下一步发现最小生成树算法的运行时间.本文采取的裁剪方法就是选择性地创建连通边，就是在第二步移动第一个滑动窗口WIN1时，并不是把所有处于窗口内的结点都创建边连通，而是选择性的只选择一些有代表性的结点创建边连通.创建的规则如下：

对于数据集D中的某个数据对象di，在图G中对应的结点是vi，在所有与vi处于同一个滑动窗口的所有结点集合Dwin中，根据有关图理论，设定vi只与下面6种结点连通(分别是左边3个和右边3个)：

①vl-:vl-∈Dwin，vj∈Dwin，λ(vj)<λ(vi)，存在λ(vl-)≤λ(vj)&&dl-(y)>di(y)；

②vl：vl∈Dwin，vj∈Dwin，λ(vj)<λ(vi)，存在dl(y)>di(y);

③vl+:vl+∈Dwin，vj∈Dwin，λ(vj)<λ(vi)，存在λ(vl+)≥λ(vj)&&dl+(y)

④vr-:vr-∈Dwin，vj∈Dwin，λ(vj)>λ(vi)，存在λ(vr-)≤λ(vj)&&dr-(y)>di(y);

⑤vr:vr∈Dwin，vj∈Dwin，λ(vj)>λ(vi)，存在dr(y)=di(y);

⑥vr+:vr+∈Dwin，vj∈Dwin，λ(vj)>λ(vi)，存在λ(vr+)≥λ(vj)&&dr+(y)>di(y).

如果图中还存在其他边和这6条边一样的权值，就一起删除.图2解释了实际效果，点划线框代表滑动窗口WIN1，跟当前结点vi落入同一个滑动窗口的结点都列入被考虑连通的范围，按照上面的规则，只连通左边的3个结点和右边的3个结点，如图中粗实线所示，而同一个滑动窗口中其他虚线连通结点都实际上不与vi连通.对于单变量数据集，如果每个实例vi都被链接到这样的左边3个和右边3个的实例，而不是链接到和vi处在同一个窗口中的所有右边和左边的实例，实例图G的最小生成树的权值和不会增长[4].

1.4 聚类实例图G的结点

在这一步，采用基于最小生成树的聚类算法[5]来对输入数据产生的示例图G的结点进行聚类.算法步骤如下：

步骤1 在无环带权图G=(V，E，L，λ，ω)上构建最小生成树：

m(MST)=min{m(tree)|tree=(V，E)};

步骤2 按照MST的边的权值重新对边进行排序；

步骤3 从MST删除权值最大的边，形成D上的森林，则

步骤4 在第三步删除边后寻找连通子图；获得森林F中的所有树

则

(3)

步骤5 把其中每棵树(Vi，Ei)作为一个单独的聚类Ci=Vi.根据聚类质量的评估标准，来决定聚类效果是否可以接受；

步骤6 如果聚类达到效果，返回连通子图作为聚类组份，否则返回步骤3继续执行.

为了识别在步骤5当前聚类是否达到可以接受的效果，本文采用两个判断标准：

① 第一个是边的权值阈值min_w.如果下一步要删除的边的权值小于一个预定义的边权阈值min_w，算法就退出循环，否则回到步骤3继续执行，重新从MST中删除边.在某些情况下，在MST中不一致边和正常边的权值之间存在明显的边界.此时可以发现这个边界并且设置好边权阈值min_w.如果并没有检测到不一致边和正常边的权值之间的边界，也可以继续删除边直到接近图中的平均边权值.

② 第2个停止删除边的判断准则是对删除边前后引发的聚类变化进行测量，称为聚类变化度量系数μ，计算方式如下：

(4)

式中:X1，X2，…，Xn为n个数据实例；Xnd表示实例Xn的第d个行为属性的值；Fkd为在聚类k中的所有实例的第d个行为属性的值总和；Zk为聚类k中数据实例的数量.

然后采用一个标准化因子μN来除上述公式进行标准化从而获得一个标准化的μ测量值.对于一个给定数据集，标准化因子μN就是μ的最大可能值，就是当所有实例都存在于同一个聚类内部时可以达到的μ值，此时聚类变化度量μ定义为

(5)

式中分母就是μN，其中Fd是聚类中所有实例的第d个行为属性值的总和.

为了评价采用标准化μ评价聚类效果的可接受性，定义一个μ的阈值μT，凡是计算聚类变化系数μ低于阈值μT的聚类都认为是可以接受的.在本文的方法中，不断删除边，从而生成新的聚类，直到μ达到稳定状态，也就是删除一条边前计算得到的μ值和删除一条边后计算获得的μ值并没有发生什么改变.正确的算法停止准则对于算法的性能很关键，最优的停止准则还取决于输入数据的统计属性.本文中同时考虑两个准则，如果两个标准中的一个得到满足，算法就可以结束循环.

1.5 检测离群点

在这一步，上一步的聚类结果被用来识别情境离群点.采用第二个滑动窗口WIN2对聚类后的数据进行第二次扫描，这一步的滑动窗口的长度通过投票窗尺寸α2决定.算法步骤描述如下：

步骤1 从拥有最小情境属性值的数据实例开始进行扫描，用数据实例填满滑动窗口WIN2；

步骤2 计算当前滑动窗口WIN2中属于每个聚类的实例的数量；

步骤3 在当前滑动窗口中，拥有最多数据实例数量的聚类被认为是当前滑动窗口中的数据主趋势；

步骤4 对于不属于当前滑动窗口主趋势的数据实例，增加它们的离群值评分，而对于属于主趋势的数据实例，减少它们的离群值评分；

步骤5 如果滑动窗口WIN2还没有到达数据的末端，就向右边移动一个数据实例的位置，然后转向步骤2继续执行，如果已经到了数据末端，就转到步骤6；

步骤6 对拥有最高可能离群值评分的实例进行标注，标记为情境离群点.

按照这种方式每次移动滑动窗口，就可以识别在滑动窗口中占优势的聚类，属于少数派聚类的数据实例就增加它们的离群值评分.因此在这一步的运行时间在最坏情况下是O(|D|α2).

因为滑动窗口每次是向右移动一个位置，可能会出现当前主趋势聚类的结点移动到窗口边缘时，变成不占主趋势的结点，该结点的离群值评分也会增加，可能会被误判为离群点.所以在步骤4分配离群值评分的时候，本文采取双向评分的方式：

在当前滑动窗口WIN2内，假设有若干个聚类C1，C2，…，Cn，按照如下机制计算离群值评分：

主趋势聚类

对于主趋势聚类的数据结点di：

Score(di)=-|CM|，di∈CM.

对于其他结点dj：

Score(dj)=|Cj|，dj∉CM.

α1和α2这两个参数的重要功能是可以控制情境属性覆盖的规模，从而控制在每一步算法覆盖到的数据实例的数量.如果这两个参数设置值太低，就变成检测局部离群点，如果值太高，就变成检测全局离群点.在极端的情况下，如果这两个参数设置成整个数据集的规模|D|，算法就会返回针对整个数据集的离群点.此时情境属性就对离群点检测过程没有任何影响力，输出的离群点是纯粹的全局离群点.

2 实验分析

实验环境酷睿i3-2100 3.10 GHz双核CPU，12 G内存，Win7系统，Java开发环境.在真实数据集上进行测试，采用的数据集是海洋温度数据SST，来自于NCDC网站[6].采集的数据是南太平洋区域，从东经150°，到西经70°，纬度是南纬20°，温度计数是每隔0.25°一个计数，时间是2011年10月1日，整个下载的数据集包含559个数据实例.每个数据实例拥有一个经度索引坐标和一个温度值，在本文中，经度坐标是情境属性，而温度值是行为属性.

本文设置第一个滑动窗口尺寸α1=20，这样设置的效果是每个数据实例可以和它左边东经5°和右边的西经5°的数据进行比较，按照每0.25°一个数据实例，刚好20个数据实例处于一个滑动窗口内.因为在实际温度中10个经度区域范围内温差一般存在明显变化，所以不大可能存在某个离群点组成的聚类区域跨越10个经度，α1=20刚好足够达到离群点区域的最大边界.根据数据D创建对应的实例图G后，因为图中边较多，生成最小生成树常用的克鲁斯卡尔算法不实用，本文运行普里姆算法生成MST.

为了生成聚类，必须从MST中删除不一致的边.首先对边进行排序，图3表示了对边排序的效果.较大的权值的边都是不一致边，可以看出这些不一致边的权值几乎都大于0.1，因此设置边权阈值min_w为0.1.

从原始数据集中选出包含20个实例的一部分数据作为训练集得出评价聚类质量的阈值μT，对训练集运用基于MST的聚类生成算法，图4显示了μ与聚类数量的比较关系，从图中可以看出，当聚类数量达到4时，μ的值基本稳定下来，因此对于这个训练集最合适的就是4个聚类，此时对应的μ值大概是0.1，因此本文设置聚类系数阈值μT为0.1.

在创建完成聚类后，就可以进行离群点检测步骤.在这里设置第2个滑动窗口WIN2尺寸α2=80，这样可以确保规模最大的离群点聚类区域在滑动窗口内仍然可能属于少数派，从而可以把规模最大的离群点区域识别为离群点.图5展示了实际的实验效果，一共识别出15个数据实例或者区域属于离群点.

其中B，C，D，G，I，J区域的温度与邻居的温度值明显不同，被正确识别为离群点.区域M和N也被识别为离群点，是因为这两个区域的数据呈现局部剧烈的变化.在图中可以看出在这些区域中，实例的行为属性值呈现过于陡峭的下降趋势，在这些区域中每个实例与它的邻居实例比较都有完全不同的行为属性值，所以在这些区域中存在很多情境离群点.J和O可以看做是全局离群点，因为因为它们的值相对于全局都是比较极端.另外可以看出，在最后的3个区域M，N，O中，都是小规模的离群点聚类区域，每个区域都是由单独的小规模聚类组成.该数据集如果采用前面文献提到的两种普通情境离群点检测算法，检测到的离群点数量会少一些，M和N区域都识别不到.

3 结 论

本文中提出一种针对单变量数据的情境离群点检测方法.采用了挖掘序列数据的滑动窗口计数，有效利用了闵可夫斯基距离作为测量标准，采用了基于图理论的最小生成树聚类算法，并且提出了聚类评价标准函数.对天气数据的实验结果表明该方法可以识别其他局部离群点检测算法识别不了的周边数据实例差异较大的某些实例和区域作为情境离群点.该方法比较简单容易实现，具有较好的适用性.下一步的工作包括采用更复杂的滑动窗口技术把本文的方法推广到存在多个情境属性的数据集中，还要尝试采用其他距离测量标准推广到包含多个行为属性的分类数据集中[7].

[1] 顾珊,吉根林.一种基于包含关系的空间面对象条件离群检测算法[J].山东大学学报：工学版,2011,41(2):91-95.

Gu Shan, Ji Genlin.An algorithm for detecting conditional outlier polygons based on inclusion relations[J].Journal of Shandong University: Engineering Science, 2011,41(2):91-95.(in Chinese)

[2] 杨茂林.离群检测算法研究[D].武汉：华中科技大学,2012.

Yang Maolin.Research on algorithms for outlier detection[D].Wuhan: Huazhong University of Science &Technology, 2012.(in Chinese)

[3] Wang X, Davidson I.Discovering contexts and contextual outliers using random walks in graphs;proceedings of the data mining[C]∥Proceedings of 2009 ICDM’09 Ninth IEEE International Conference on.[S.l.]: IEEE, 2009.

[4] Bollob S B, Kun G, Leader I.Cops and robbers in a random graph [J].Journal of Combinatorial Theory, Series B, 2013, 103(2): 226-236.

[5] 王小乐,刘青宝,陆昌辉,等.一种最小生成树聚类算法[J].小型微型计算机系统,2009,30(5):876-881.

Wang Xiaole, Liu Qingbao, Lu Changhui, et al.Minimum spanning tree clustering algorithm[J].Journal of Chinese Computer Systems, 2009,30(5):876-881.(in Chinese)

[6] Tang G, Bailey J, Pei J, et al.Mining multidimensional contextual outliers from categorical relational data[C]∥Proceedings of the 25th International Conference on Scientific and Statistical Database Management.[S.l.]: ACM, 2013.

(责任编辑：刘芳)

An Approach for Contextual Outlier Detection Based on Graph

LI Tao，ZHANG Yun，HUANG Zhi-hong

(Modern Education Technology Center，South China Agricultural University，Guangzhou 510640，Guangdong，China)

Aiming at the contextual outlier detection problem in abnormal pattern mining, a graph-based detection method was presented, first a graph was built to represent the data instances, then a sliding window was used across the data instance, the Minkowski distance was calculated between nodes for the data instances in the sliding window, the Minkowski distance was adopted as the edges weight.Then the minimum spanning tree clustering algorithm was adopted to cluster the instances graph, finally the second sliding window was adopted cross the data instance, different outlier score was given to the data instance according to the data instance belonged to the main trends clustering or not.The data instances which did not belong to the main trends within the window clustering were considered potential outliers.Simulation experiments and real data analysis show that this algorithm is feasible in binary sequence data； and this method has good applicability and scalability.

data mining;outlier detection;graph;clustering

2014-11-15

国家教育部人文社会科学研究青年基金项目(15YJC880037)

李涛(1978—)，男，博士生，E-mail:verrazano@126.com.

TP 391

A

1001-0645(2016)03-0302-06

10.15918/j.tbit1001-0645.2016.03.015