一种两阶段异常检测方法

　第26卷第7期　　2005年7月

小型微型计算机系统M I N I -M I CRO SYST E M S V o l 126N o . 7　

　Ju ly 2005　　

一种两阶段异常检测方法

蒋盛益1, 2, 李庆华1, 赵延喜1

1(2(

华中科技大学计算机学院, 湖北武汉, 430074) 衡阳师范学院计算机系, 湖南衡阳, 421008)

E 2m ail :jiangshengyi @163. com .

摘　要:提出了一种新的距离和对象异常因子的定义, 在此基础上提出了一种两阶段异常检测方法TOD , 第一阶段利用一种新的聚类算法对数据进行聚类, 第二阶段利用对象的异常因子检测异常. TOD 的时间复杂度与数据集大小成线性关系, 与属性个数成近似线性关系, 算法具有好的扩展性, 适合于大规模数据集. 理论分析和实验结果表明TOD 具有稳健性和实用性. 关键词:聚类; 异常因子; 异常检测

中图分类号:T P 18　　　　　文献标识码:A 　　　　　　文章编号:100021220(2005) 0721237204

Two -Stage Outl ier D etection Approach

1, 211

J I AN G 　Sheng 2yi , L I 　Q ing 2hua , ZHAO 　Yan 2x i 1(2(

Co mp u ter S chool , H uaz hong U niversity of S cience &T echnology , W uhan 430074, Ch ina ) Co mp u ter D ep art m ent of H engy ang N or m al U niversity , H engy ang 421001, Ch ina )

Abstract :In th is paper , a new distance defin iti on and ou tlier facto r of ob ject are in troduced . O n the basis of these , a tw o 2stage ou tlier detecti on app roach , nam ed TOD , is p resen ted , the first stage clu ster data by a new clu stering m ethod , the second stage . T he ti iden tify ou tliers by the ou tlier facto r of ob jects m e comp lex ity of TOD is linear w ith the size of dataset and nearly linear w ith the num ber of attribu tes , w h ich resu lts in good scalab ility and adap ts to large dataset . T he theo retic analysis and the ex 2peri m en tal resu lts show that the TOD is robu st and p racticab le . Key words :clu stering ; ou tlier facto r ; ou tlier detecti on

1　引　言

异常数据是在数据集中偏离大部分数据的数据, 使人怀疑这些数据的偏离并非由随机因素产生, 而是产生于完全不同的机制. 异常检测在许多应用领域中正逐步成为一种有用的工具, 特别在医学检测, 金融领域中的欺诈检测, 气象预报中的灾害预报, 网络安全中的入侵检测等领域中正在得到越来越广泛的应用. 常用的异常检测方法有基于统计的方法、基

[1][2][3,4]

于距离的方法、基于密度的方法、基于聚类的方法及神经网络的方法[5]等. 本文主要针对现有异常检测算法不能直接应用于具有混合属性的数据集以及难以用于大规模数据集的问题, 提出一种两阶段异常检测方法, 其主要思想是基于下面的考虑:(1) 正常数据占绝大部分, 且异常数据与正常数据在某种特征空间会表现出明显不同, 或者说异常数据会偏离正常数据(也就是大部分数据) ; (2) 采用一种新的数据结构来对类进行有效的压缩表示; (3) 数据的属性可以分割为分类属性和数值属性两部分, 也就是可以将数据特征空间分割为两个子空间, 对象间的距离计算可分解为两个子空间上的距离计算; (4) 采用一种高效的聚类算法对数据进行划分; (5) 寻找一种能区分正常对象与异常对象的度量方法.

2　相关定义

为了后面描述的方便, 我们引入定义1, 并提出3个新的定义. 假设数据集D 有m C 个分类属性和m N 个数值属性, m =m C +m N , 不妨设分类属性位于数值属性之前, 用D i 表示第

. i 个属性取值的集合

定义1. 给定类C , a i ∈D i , a i 在C 中关于D i 的支持度定义为C 在D i 上的投影中包含a i 的次数:S up C D i (a i ) = {ob 2

ject object ∈C , object . D i =a i } .

定义2. 给定类C , C 的摘要信息CS I (C lu ster Summ ary Info rm ati on ) 定义为:

CS I ={n , C luster , S umm a ry },其中n 为类C 的大小, C luster 为类C 中对象标识的集合, S umm a ry 由分类属性中不同取值的频度信息和数值属性的质心两部分构成, 即:

〈S ta t i , Cen 〉 S ta t i ={(a j , S up C D i (a ) ) a j ∈S umm a ry ={

D i },1≤i , j ≤m C , Cen =(c m C +1, c m C +2, …, c m C +m N ) }

定义3. 给定D 的子类C , C 1及C 2, 对象p ={p i i ∈[1, m ]},q ={q i i ∈[1, m ]}.

(1) 对象p , q 在属性i 上的差异程度(或距离) d if (p i , q i ) 定义为:

　　收稿日期:2004205209　基金项目:国家自然科学基金项目(60273075) 资助　作者简介:蒋盛益, 男, 1963年生, 副教授, 博士研究生, 主要研究方向为数据挖掘、网络安全; 李庆华, 男, 1940年生, 教授, 博士生导师, 主要研究方向为并行计算、网格计算、网络安全; 赵延喜, 男, 1979年生, 硕士研究生, 主要研究方向为网络安全.

1238　　　　　　　　　小　型　微　型　计　算　机　系　统　　　　　　　2005年

　　对于分类属性或二值属性,

d if (p i , q i ) =

的异常检测方法TOD (Tw o 2stage O u tlier D efecti on ) , 该方法

0p i ≠q i

;

1p i =q i

1p i ≠q i 0p i =q i

由两个阶段构成, 第一阶段是利用3. 1的聚类算法对数据集进行聚类; 第二阶段利用对象的异常因子确定异常对象. 引理1. 如果随机变量Ν服从正态分布, Ν～N (Λ, Ρ2) , 则有:P r (Ν≥Λ+2・Ρ) =0. 023, P r (Ν≥Λ+1. 645・Ρ) =0. 05, ≥Λ+1. 285・Ρ) =0. 10, P r (Ν≥Λ+Ρ) =0. 16. P r (Ν

根据概率论中的中心极限定理可知, 由大量微小且独立的随机因素引起并积累而成的变量, 必服从正态分布. 在大样本情况下, 可以将O F (p ) 近似地看成服从正态分布, 再根据引理1, 提出如下异常检测策略:

第一步, 对数据集D 进行聚类, 得到聚类结果C ={C 1,

C 2, …, C k };

=1-

对于连续数值属性或顺序属性, d if (p i , q i ) = p i -q i ;

(2) 两个对象p , q 间的距离(或差异程度, 不相似程度) d (p , q ) 定义为每个属性上的差异程度的平均值, 即:

d if (p i , q i ) ∑m

m

　　d (p , q ) =

(3) 对象p 与类C 间的距离d (p , c ) 定义为p 与类C 的

摘要之间的距离d (p , C ) =(d C +d N ) m , 各部分的含义如下:

分类属性部分的距离d C 定义为p 与C 中每个对象在不同分类属性上距离平均值之和:

S up C D i (p i ) ∑m C

第二步, 计算数据集D 中所有对象p 的异常因子O F

(p ) , 及其平均值A ve _O F 和标准差D ev _O F , 满足条件:O F (p ) ≥A ve -O F +Β・D ev -O F (1≤Β≤2) 的对象判定为异常. 3. 3　时间复杂度分析

　　d C =m C -

; C

数值属性部分的距离d N 定义为p 与C 的质心间的M a 2

m C +m N

异常检测方法的两个阶段需要扫描数据集两趟和聚类结果一趟. 第一阶段, 即聚类算法的时间复杂度依赖于数据集的大小N , 属性的个数m , 产生CS I 的个数及每个CS I 的大小. 为简化分析, 假定最终产生的CS I 个数为k , 每个分类属性i 有n i 个不同的取值, 则在最坏情况下聚类算法时间复杂度为

O (N ・k (∑n i +m N ) ) . 正如文献[7]指出, 分类属性通常有较

i =1m C

hattan 距离:d N =

i =m C +1

∑ p i -c i .

定义4. 设C ={C 1, C 2, …, C k }是训练集D 的分解表示, 即D =∪C i (C i ∩C j =5, i ≠j ) , 对象p 的异常因子O F (p ) 定

i =1义为p 与所有类间距离的加权平均值:O F (p ) =∑・d

j =1 D

(p , C j ) .

O F (p ) 度量了对象p 偏离整个数据集的程度, 其值越大, 说明p 偏离整体越远.

k

k

小的域, 典型的分类属性通常包含小于100个属性值, 再者在聚类过程中, 生成的聚类个数是从1逐步扩大到k 的, 每个聚类中分类属性值的个数也是逐步增加的, 且属性取值个数往往小于总的取值个数. 因此, 在实际问题中, 聚类算法期望的时间复杂度为O (N ・k ・m ) . 检测方法的第二阶段, 计算所有对象的异常因子, 需要计算每个对象与任意类的距离, 其时间复杂度与第一阶段最坏情况相同, 为O (N ・k ・(∑n i +

i =1m C

3　两阶段异常检测方法T OD

3. 1　数据聚类算法

目前在文献中存在大量的聚类算法, 算法的选择取决于数据的类型、聚类的目的和应用. 本文采用新的数据表示和距离定义, 采用有关最小距离原则算法下:

(1) 初始时, 聚类集合为空, 读入一个新的对象; (2) 以这个对象构造一个新的类;

(3) 若已到数据库末尾, 则转(6) , 否则读入新对象, 利

[4,6]

的思想对数据进行聚

m N ) ) . 因此检测方法最坏情况下的时间复杂度为O (N ・k ・

类, 将数据集分割为半径几乎相同的超球体或类. 具体过程如

(∑n i +m N ) ) , 期望的时间复杂度为O (N ・k ・m ) .

i =1

m C

由此可见, 两阶段异常检测方法TOD 的每个阶段需要扫描数据集一趟, 时间复杂度与数据集大小成线性关系, 与属性个数以及最终的聚类个数成近似线性关系, 算法具有好的扩展性.

3. 4　对数据输入顺序和参数r 的敏感性

k

k

k

用给定的距离定义, 计算它与每个已有类间的距离, 并选择最小的距离;

(4) 若最小距离超过给定的半径阈值r , 转(2) ;

(5) 否则将该对象并入具有最小距离的类中并更新该类

引理2. 设x =∑w i x i (w i >0, ∑w i =1) , f (x ) =∑w i x

i =1

i =1

i =1

的各分类属性值的统计频度及数值属性的质心, 转(3) ;

(6) 结束. 3. 2　异常检测方法

-x i - x -x , 则

①x ≤m in {x i , 1≤i ≤n }=c 1或x ≥m ax {x i , 1≤i ≤n }=c 2

时, f (x ) ≡0;

异常数据是在数据集中偏离大部分数据的数据, 而对象的异常因子度量了一个对象偏离整个数据集的程度, 自然地

将异常因子大的对象看成异常. 由此我们提出一种基于聚类

②x x 时, f (x ) 单调递减, 0≤f (x ) ≤f (x ) ;

k C 2

(∑w i x i 2-x 2) =③f (x ) d x =

c 2-c 2C 1c 2-c 1i =1

7期　　　　　　　

k

w i (x i -x ) 2. ∑c 2-c 1i =1

蒋盛益等:一种两阶段异常检测方法　　1239

4　实验结果

检测率、误报率是度量异常检测方法性能的两个指标. 检

测率(D etecti on rate ) 表示被正确检测的异常记录数占整个异常记录数的比例; 误报率(False po sitive rate ) 表示正常记录被检测为异常的记录数占整个正常记录数的比例. 为了评估算法TOD 的性能, 我们在V C 6. 0环境中实现了算法, 并在

U C IM ach ine L earn ing R epo sito ry [8]提供的真实数据集上进

引理2说明, 对于一维数据, 一个点到一组给定点的加权平均距离可用该点到这一组点的质心间的距离很好地近似.

由定义3及定义4可得:

S up C j D (p i ) ∑(() +(p 与C j ・m C -j =1 D C j

质心间的M ahattan 距离) ) m ) =

O F (p ) =(∑

m C

k

m C

m

((m C -

∑i =1

S up C D (p i )

D

) +

・(p 与C j 质心间的∑j =1 D

k

行了测试. 实验结果表明, 尽管在有些数据集上聚类结果的质

量不理想(有些类包含的元素个数太少) , 但异常检测结果都比较理想, 对参数r 和数据输入顺序不敏感.

4. 1　淋巴系造影术数据集

M ahattan 距离) ) =

m

从上面的式子可见, 一个对象的异常因子O F (p ) 可分解为两部分, 其中O F C 对应于分类属性, O F N 对应于数值属性. O F C 与聚类结果没有关系, 而只与该对象在数据集D 中各个属性上的支持度有关, 因而这一部分就与参数r 及训练集中对象的排列顺序无关, 特别地, 对于纯分类属性的数据集来说, 每个对象的异常因子的计算与r 及数据输入顺序无关. O F N 与聚类结果C j 有关, 即与r 及数据输入顺序有关, 但由引理2及M an tattan 距离的特点可知, 其值接近于p 与整个数据集数值部分的质心间的距离, 而这一距离与r 及数据输入顺序无关. 这说明r 及数据输入顺序对数据集中对象的异常因子的计算影响不大, 是由数据的本质特征所决定的. 尽管数据输入顺序会影响聚类的结果, 因而可能进一步影响异常检测的结果, 但理论分析表明, 我们提出的两阶段异常检测方法TOD 对于阈值r 及数据输入顺序是稳健的、不敏感的, 实验结果有力地支持了这一结论. 3. 5　参数的选择3. 5. 1　参数r 的选择

从前面的分析可见, 检测结果对于参数r 是稳健的, 但聚类算法中参数r 将影响聚类的结果和算法的时间效率. r 越小得到的类数越多, 算法时间开销越大, 考虑到算法的效率以及聚类结果可以作为进一步分析使用, 需要选取合适的参数r . 从聚类的过程直观地可以理解, 参数r 实际应小于类间距离, 而大于类内距离, 因此, 有理由猜测, r 应在所有对象间的平均距离或稍大的范围内. 对于数据集很大的情况, 可以采用抽样的方法来处理. 具体方法如下:

(1) 取数据集D 的一个样本子集D 3; (2) 计算D 3中每对对象间的距离;

(3) 计算(2) 中距离的平均值EX 和标准差DX ; (4) 取r 在EX 与EX +0. 5DX 之间.

3

可以看出为了选取样本子集D , 需要扫描数据集一趟, 若D 3的大小为n 0, 则计算EX 和DX 的时间复杂度为O

(n 02) , 为使它不超过O (N ) , 应保证n 0

2N .

这个数据集包含148条记录, 每条记录包含18个分类属性. 所有记录划分为4类, 各类数据记录分布情况如下:类1含2记录, 类2含81记录, 类3含61记录, 类4含4记录. 类1与类4只占整个数据集的4. 05%, 其中元素可以看成稀有记录(异常记录) . 对于这个数据集, 有EX =0. 473, DX =0.

136, 理论分析与实验结果表明, 检测结果与r 及数据输入顺

序无关, 表1给出了实验结果.

表1　在淋巴系造影术数据集中检测稀有记录

21. 6451. 2851

2449

5566

1. 41%2. 82%2. 82%6. 34%

83. 33%83. 33%100%100%

表1中N 1表示检测到的伪异常记录数, N 2表示检测到的真正异常记录(稀有记录) 数.

仔细分析实验结果发现, 前5条记录均为稀有记录, 前

10条记录可检测出全部6条稀有记录. 而对应地, CB L O F [3]

和RN N

[5]

异常检测方法前7条记录分别能检测出4条和1

条稀有记录, 前30条记录分别才能检测出6条和2条稀有记录, 由此可见本文方法在L ymphography 数据集上明显优于

. CB L O F 和RN N 方法4. 2　乳房癌数据集

乳房癌数据集有699条记录, 其中良性的458记录, 恶性的241记录, 每条记录包含9个数值属性. 直观地判断, 恶性与良性记录应有明显区别. 因此, 选取不同比例的两种记录构造分布不平衡的测试集, 其中选取39(8%) 条恶性记录和

444(92%) 条良性记录[5], 期望能够将比例很小的那部分记

录从测试集中检测出来. 对于这个数据集有EX =0. 144, DX

=0. 171, 实验结果表明r 在EX 20. 5DX ～EX +DX 时, 检测

结果是稳健的, 表2给出r 在EX ～EX +0. 25DX 时的实验结果.

表2中N 1表示检测到的伪异常记录(即良性记录) 数,

N 2表示检测到的真正异常记录(即恶性记录) 数.

Β越小检测率可能越高, 但误报率也会越高, 通常取Β=1或1. 285.

进一步, 前48条记录可检测出38条恶性记录, 前52条记录可检测出全部39条恶性记录, 对应地, CB L O F [3]和

RN N

[5]

异常检测方法前56条记录才可分别检测出38条和

1240　　　　　　　　　小　型　微　型　计　算　机　系　统　　　　　　　2005年

28条恶性记录, 前64条记录才能分别检测出39条和28条

表2　在威斯康星州乳房癌数据集中检测恶性记录

21. 6451. 2851

25812

31353638

0. 45%1. 13%1. 80%2. 70%

79. 49%89. 74%92. 31%97. 44%

合, 而称S C ={C i b

异常检测策略二:

第一步, 对数据集D 进行聚类, 得到聚类结果C ={C 1, C 2, …, C k };

第二步, 对聚类进行排序, 使 C 1 ≥ C 2 …≥ C k , 确定小聚类集合S C ={C i b

第三步, 计算小聚类集合中所有对象p 的异常因子, 按照异常因子从大到小排列对象, 前若干个对象判定为异常.

参数Α影响检测效率, 也影响检测精度. Α越大效率越高, 但Α过大将使得检测精度降低, 通常可取Α在0. 8左右. 实验结果表明, 对于L ymphography 数据集, 0. 73≤Α≤0. 84时前8条记录可检测出全部6条稀有记录, 0. 85≤Α≤0. 87时前6条记录全为稀有记录. 对B reast cancer 数据集, Α≤0. 8时前53条记录可检测全部出39条恶性记录, 检测率为100◊, 误报率为2. 93◊, 0. 81

与前面的策略比较, 策略二效率要高, 但需要异常数据个数的先验知识, 且稳健性要差.

数值属性部分的距离改为用欧式距离计算, 检测效果没有太大变化.

References :

[1]Kno rr E M , N g R T . A lgo rithm s fo r m ining distance 2based out 2

liers in large datasets [C ]. In :P roc . 24th Int . Conf . O n V ery L arge D ata Bases , N ew Yo rk , N Y , 1998:3922403. [2]Shenyi 2Yi J iang , Q ing 2H ua L i , Ken 2L iL i , H uiW ang , Zhong 2L uo

M eng . GLO F :a new app roach fo r m ining local outlier [C ]. Int . Conf . M ach . L earn . Cybern , 2003, 11:1572162.

[3]H e Zeng 2you , Xu X iao 2fei , D eng Sheng 2chun . D iscovering clus 2

ter 2based local outliers [J ]. Pattern R ecogniti on L etters , 2003, 24(9210) :165121660.

[4]L eonid Po rtnoy , E leazar E sk in and Salvato re J . Sto lfo . Intrusi on

detecti on w ith unlabeled data using clustering [C ]. In :P roc of A CM CSS W o rk shop on D ata M ining A pp lied to Security (DM 2SA 22001) . Ph iladelph ia , PA , 2001.

[5]H ark ins S , H e H , W illam s G J , Baster R A . O utlier detecti on

using rep licato r neural netwo rk s [C]. In:P roc . of the 4th Int . Conf . on D ata W arehousing and Know ledge D iscovery , A ix 2en 2P rovence F rance , 2002:1702180.

[6]H e Zeng 2you , Xu X iao 2fei , D eng Sheng 2chun . Squeezer :an effi 2

cient algo rithm fo r clustering catego rical data [J ]. Journal of Computer Science and T echno logy , 2002, 17(5) :6112624. [7]Guha S , R astogi R , Sh i m K . ROCK :A robust clustering algo 2

rithm fo r catego rical attributes [C ]. In :P roc . of the 15th I CD E , Sydney A ustralia , 1999, 5122521.

[8]M erz C J , M erphy P . U C I repo sito ry of m ach ine learning

. edu databases [EB OL ]. U RL :h ttp : www . ics . uci m learn

M L RR epo sito ry . h tm l , 1996.

[9]E sk in E , A rno ld A , P rerau M , Po rtnoy L , Sto lfo S . A geom etric

fram ewo rk fo r unsupervised anom aly detecti on :detecting intru 2si ons in unlabeled data [C ]. In :In BarbaraD and Jaj odia S (edito rs ) , A pp licati ons of D ata M ining in Computer Securuty , K luw er , 2002.

恶性记录, 由此可见本文方法在乳房癌数据集优于CBLO F 和RNN 方法. 4. 3　K DDCUP 99

KDDCU P 99包含了约4900000条模拟网络攻击记录, 每条记录由7个分类属性和34个数值属性刻划. 整个数据集太大, 且正常记录仅占20%左右, 不符合异常检测方法的前提假设, 为检测我们的算法, 从中随机选取子集P 1, 其中P 1包含38841条正常记录和1618条攻击记录(占4%) . 对于数据集P 1, 经计算得EX =0. 086, DX =0. 068. 实验结果表明, r 在EX 2DX ～EX +DX 之间检测结果变化不大, 表3给出了r =

. EX 时的检测结果

表3　在KDDCU P 99数据子集P 1中检测攻击记录

2. 621. 6451. 2851

[***********]29

[***********]8

3. 86%5. 00%6. 77%6. 78%7. 80%

52. 41%98. 33%98. 33%98. 58%98. 76%

表3中N 1表示检测到的伪异常记录(即正常记录) 数, N 2表示检测到的真正异常记录(即攻击记录) 数.

表4给出了文献[4][9]在KDDCU P 99上的检测结果, 结果表明本文方法的检测精度优于文献中同类方法.

表4　不同方法在KDDCU P 99上的检测结果对比

文献[4]的结果文献[9]的结果本文方法的结果

检测率35. 7%288%28%293%52. 41%298. 76%

误报率1. 44%28. 14%0. 5%210%3. 8627. 80%

5　讨　论

在实验过程中我们对检测策略和距离计算方法进行了调整, 得到了一些有益的结果.

由于异常数据只占整个数据集很小的比例, 因此, 直观地看, 异常数据极可能包含在元素个数较少的类中(但并非总是如此) , 为提高检测效率, 只需对元素个数较少的类中对象计算其异常因子, 为此引入定义5并提出另外一种检测策略.

定义5. 设C ={C 1, C 2, …, C k }是聚类算法在数据集D 上的聚类结果, C 1 ≥ C 2 …≥ C k , 给定0～1之间的参数Α, b 是满足

C i ∑ D

b

≥Α的最小值, 则称L C ={C i i ≤b }为大聚类集