一种分布式高维类别属性数据流离群点检测算法

发布于:2021-10-24 20:29:36

http://www.paper.edu.cn

一种分布式高维类别属性数据流离群点检测算法1
孙志挥,周晓云,倪巍伟
东南大学计算机科学与工程系,南京 (210096) E-mail:wni@seu.edu.cn 摘 要:基于数据流数据的挖掘算法研究受到了越来越多的重视,而高维数据流离群点检测算 法的研究则刚刚起步. 本文针对分布式数据流环境,提出了基于时间相关滑动窗口和 WFPOF 的高维分布式数据流离群点检测算法.该算法将不同站点的数据流放在同等地位,将它们作为 全局数据流的子集,在每个分布站点上维护本地数据流的频繁模式,并在此基础上由中心站点 生成全局频繁模式,而各分布站点利用全局频繁模式计算 WFPOF 值,检测本地的离群点.算法 对分布环境下站点间的协调通信以及局部频繁模式和全局频繁模式的维护等问题进行了详 细的讨论,并通过实验验证了算法的可行性和有效性。 关键词:分布式数据流,离群点检测,频繁模式,高维 中图分类号:TP311

1. 引 言
随着计算机技术的广泛应用,数据流(Data Streams)作为一类重要的数据来源,受到越来越 多的关注,基于数据流模型的管理系统及其知识发现算法等已成为重要的研究课题[1-3].网络 事件日志、电话呼叫纪录、信用卡交易流、传感器网络等均可以看作基于数据流模型的数据 集.它们具有数据量大、潜在无限、到达速率不确定等特点,同时这些特点也对数据挖掘算法 提出了更高的要求. 同时在现实世界中存在着大量高维甚至是超高维数据.在高维空间中,数据分布稀疏,数 据之间的距离尺度及区域密度不再具有直观的意义.从一个数据点来看,其他点到它的距离之 差落在一个很小的区间内,很难给出一个合适的*似度阈值,来确定哪些点是与它相似的,而 其他哪些点不是,即无法判断高维空间中所存在的离群点. “维数灾难”[4][5]以及数据流数据本 身所固有的特性,使得高维数据流数据挖掘算法的研究更是具有其特别的难度和深度. 离群点检测问题是数据挖掘技术的重要研究领域之一,它被广泛应用于网络入侵抵御、 信用卡恶意透支检测等风险控制领域.离群点检测技术由于其独特的知识发现功能而得到较 深入的研究.到目前为止,离群点还没有一个正式的、 为人们普遍认同的定义. Hawkins 的定义
[6]

揭示了离群点的本质:“如果一个数据样本与其他样本之间存在足以引起怀疑的差异,则称 对于数据流的离群点检测问题,文献[7]中首次提出了针对大规模数据流的异常检测算法,

其为离群点.” 该算法引用文献[8]中提出的异常(Deviant)作为离群点的概念,解决 Time Series 这一特殊数据 流模型上的离群点检测问题.文献[9]中提出了基于动态网格的数据流离群点检测算法 FODDS 及其快速版本 FODDS-S 算法,算法采用一种快速直接、时间相关的网格动态划分方 法,将空间中密度稀疏和稠密的区域分开,根据局部空间的离群度检测数据流中可能出现的离 群点区域,从而得到候选离群点集合,但是其不足仍然是只能处理低维数据流.文献[10]采用加 权频繁模式离群因子(WFPOF)作为离群点度量并提出了 FODFP-Stream 算法,能够有效的处 理高维类别属性数据流的离群点检测问题. 对于分布式数据流中的离群点检测问题,文献[11]提出了一个分布式环境下信号网络中

1

本课题得到教育部高等学校博士学科点科研基金资助(No.20040286009)。 -1-

http://www.paper.edu.cn

异常检测的框架,着重从总体角度讨论了该问题,并指出了其中需要进一步解决的问题,但是 没有涉及具体实现方面.文献[12]提出了一种通过允许各个不同的组织相互协作产生更好的 整个网络的行为模式以提高入侵检测精度的网络检测技术.在无线网络领域,也提出了许多基 于分布协作的网络入侵检测方法[13-15].但是,这些方法仅仅用于网络入侵检测,不能应用于一 般目的的离群点检测.文献[16]对分布式环境下的离群点检测问题进行了进一步的研究,提出 了基于核密度估计的分布式数据流离群点检测算法 FindOutStreams.该算法将不同节点的数 据流放在同等的地位上,并将它们作为全局数据的子集,着重讨论全局环境下的离群点检测问 题.同时针对分布式环境下节点间的协调通信、统计信息维护以及离群点检测等问题进行了 详细的讨论.但上述这些算法都只能处理低维数据流,对分布高维数据流的离群点检测问题尚 未见报道. 本文采用类似文献[16]的分布数据流结构,将不同节点的数据流放在同等的地位上,着重 讨论了分布情况下的高维类别属性数据流的离群点检测问题,并在文献[10]的基础上提出了 分布高维类别属性数据流离群点检测算法 FOD-Dstream.,算法重点解决了数据的高维性和 分布环境下各站点的通信协调以及局部频繁模式和全局频繁模式的维护等问题,最后通过实 验验证了算法的可行性.

2. 问题描述与相关概念
设 D={D1, D2, …, Dk}是一个有序集合, A j
= {a (j1) , a (j2 ) ,..., a j
(n j )

} 是类别属性

Dj 上的值的集合,

其中 nj 表示类别属性 Dj 的可取值的个数,相应有 k 维类别属性空间 S = D1 × D2 × ... × Dk .设
v X v =< x1v , x 2 ,..., xtv > 是站点

v 上的数据流 DSv 在时刻 t 时的数据集,其中 xiv

=< xi1 , xi 2 ,..., xik > , xij ∈ A j

.

本文所研究的分布式数据流结构如图 1 所示.
CSite

Site1 DS1

Site2 DS2

Sited DSd

图 1 分布式数据流的结构 Fig.1 The Structure of Distributed Data Stream

本文对所研究的分布式高维类别属性数据流中离群点检测问题描述为:在一定内存、 时间 限制下,在各个分布站点 Site1 , Site2 ,..., Sited 检测相对于当前时间相关滑动窗口内所有站点数据 流分布的离群点集合 Outlier1 , Outlier2 ,..., Outlierd . 文献[10]提出了加权频繁模式离群因子(WFPOF)的概念,并在其基础上给出了一种新的 离群点定义.它的主要思想是,频繁模式可以认为是通常模式,一个数据包含的频繁模式越多, 其成为离群点的可能性越小,反之具有较小 WFPOF 的数据成为离群点的可能性越大. WFPOF 能够有效度量高维数据的离群度,而且计算所需的时空复杂度较低,有利于应用于高 维数据流环境,同时将模式长度与数据流空间维数的比值作为权重,更能体现不同长度频繁模 式对离群度的贡献大小,使得离群点的度量更准确.

-2-

http://www.paper.edu.cn

定义 1(加权频繁模式离群因子). 对于 k 维类别属性数据流 DS 上的任意数据点 x,其加权 频繁模式离群因子(WFPOF)为
WFPOF ( x) =
p ? x , p∈FPS ( DS ,minsup )

∑ Sup( p) × (| p | k )

|| FPS ( DS , minsup ) ||

其中 | p | 为模式 p 的长度,k 为数据空间的维数, FPS ( DS , mins up ) = { p | Sup ( p ) ≥ mins up } ,
Sup ( p ) 为模式

p 的支持度.

数据流具有潜在无限的特点,并且最新的数据往往具有更高的重要性,因此 FOD-Dstream 算法采用在滑动窗口上发现和维护频繁模式.滑动窗口通常分为基于计数(Count-based)和基 于时间(Time-based)的滑动窗口两类.由于在各个站点的数据流流量存在差异,即使同一个站 点在不同时刻数据流流量也会发生变化,因此对各站点采用相同的数据量作为窗口宽度,或对 某站点始终采用恒定的数据量作为窗口宽度都是不合适的.因此 FOD-Dstream 算法采用时间 相关滑动窗口(Time-sensitivy Sliding Windows)的概念. 定义 2(时间相关基本窗口).给定一时刻点 t 和时间跨度 p ,在 (t ? p, t ] 时间段内到达的数据 流数据组成一个时间相关基本窗口 BW ,记 bwi 为数据流的第 i 个时间相关基本窗口,基本窗口 大小 bwi .size =| bwi | ,时间跨度 bwi .span = p . 显然,时间相关基本窗口大小是不定的,而时间跨度是固定的. 定义 3 (时间相关滑动窗口). 一个连续的时间相关基本窗口序列构成一个时间相关滑动 窗口 SLW ,记 slwi = bwi?q+1 , bwi?q+2 ,..., bwi 为第 i 个基本窗口到达后的时间相关滑动窗口,其中 q 表 示 一 个 滑 动 窗 口 容 纳 基 本 窗 口 的 数 目 . 滑 动 窗 口 大 小 slwi .size = ∑ j =1 bwi? j +1.size , 时 间 跨 度
q

slwi .span = q × p .

FOD-Dstream 算法的主要思路是将不同节点的数据流放在同等地位,采用 WFPOF 来度 量高维数据的离群度,利用时间相关滑动窗口进行各个分布站点和中心站点的交互.各个分布 站点维护局部频繁模式,并与中心站点交互获得全局频繁模式,计算基于全局数据的 WFPOF 来检测离群点.

3. FOD-Dstream 算法及其构造
3. 1 分布站点上的局部频繁模式发现与维护
在分布站点 v(1 ≤ v ≤ d ) 上保存站点 v 的基本窗口数据结构 BW _ DSS v 和全局频繁模式,包 含低维模式估计 BW _ BFS v ,高维候选频繁模式集 BW _ HCFPSETS v 和频繁模式集 BW _ FPSETS v . 其 中 BW _ FPSETS v = Υk=1 BW _ FPr S v , BW _ FPr S v 表 示 站 点 v 上 r (1 ≤ r ≤ k ) 维 频 繁 模 式 r 集. BW _ BFS v 保存的元组结构为 (id , count ) , BW _ HCFPSETS v 和 BW _ FPSETS v 保存的元组结构为
(item _ id , count , level ) , item _ id 为 模 式 的 编 码 , level 为 模 式 的 长 度 , count 为 模 式 的 支 持

度. BW _ BFS v 用 Bloom Filter[17,18]方法保存,同时采用 TreeHash[19]对所有元组进行存储,搜索和 更新操作. 为了尽可能地减少网络通讯量,站点 v 仅向中心站点传送当前的基本窗口信息 BW _ DSSv . 离群点检测是基于大规模数据上的统计信息,因此离群点检测可以在整个滑动窗口建立后开 始.分布站点 v 的 BW _ DSSv 更新算法具体描述如下:

-3-

http://www.paper.edu.cn
算法 1. BW _ DSS v 更新算法 输入 : 站点 v 上 k 维数据流 DS v 的第 i 的基本窗口 bwiv ; 维数阈值 l ; 哈希函数 h1 , h2 ,..., hg ; 最小支持度

minsup.
输出: BW _ DSS v (1 ≤ v ≤ d ) ,第 i 个基本窗口的数据量 N iv . 步骤:

Let BW _ DSS v be empty;

N iv = 0 ;
For each datum x arrived in bwiv {

N iv = N iv + 1; For all f-itemset ( 1 ≤ f ≤ l ) s of

x

{

id=convert(s, DS v ,l); /*convert(s, DS v ,l)将 s 转换成[1…M]之间的整数*/ For ( i = 1; i ≤ g ; i + + ) VB[ hi (id )].count = VB[hi (id )].count + 1; /* VB[i] 表示获得 BW _ BFS v 第 i 个位置上的元组*/ If (s not in BW _ FPf S v ) { If (all VB[ hi (id )].count ≥ minsup × N iv ) { insert s into BW _ FPf S v ; FPB[ s ].count = min(VB[hi (id )].count ); }/* FPB[s ] 表示获得 s 在 BW _ FPSETS v 中的元组*/ } Else if (all VB[ hi (id )].count ≥ minsup × N iv ) FPB[ s ].count = FPB[ s ].count + 1;
Else delete s and all superset(s) from BW _ FPSETS v ;

/* superset(s)表示 s 的所有超集*/ } j = l +1 ; While ( BW _ FPj S v ≠ φ ) and ( j ≤ k ) do { For all j-itemset s of x { If (s in BW _ HCFPSETS v ) {

CFPB[ s].count = CFPB[ s].count + 1 ; } /* CFPB[S ] 表示获得 s 在 BW _ HCFPSETS v 中的元组*/ Else if all (j-1)-itemset of s in BW _ HCFPSETS v { insert s into BW _ HCFPSETS v ; CFPB[ s].count = 1 ;} If (s not in BW _ FPf S v ) { If ( CFPB[ s].count ≥ minsup × N ip ) { insert s into BW _ FPf S v ;
FPB[ s ].count = CFPB[ s ].count ;

} } Else If ( CFPB[ s].count ≥ minsup × N ip ){ FPB[ s ].count = FPB[ s ] + 1 ; }

-4-

http://www.paper.edu.cn Else delete s and all superset(s) from BW _ FPSETS v ; } j=j+1; } }

3. 2 中心站点上的全局频繁模式发现与维护
为了得到基于所有分布站点的全局频繁模式,必须将各分布站点的信息传送给中心站点, 在得到全局频繁模式后再分发到各个分布站点. 在 中 心 站 点 将 保 存 中 心 站 点 基 本 窗 口 数 据 结 构 BW _ DSC 和 滑 动 窗 口 数 据 结 构
SLW _ DSC . BW _ DSC 结构与 BW _ DSS v 类似,而 SLW _ DSC 包含低维模式估计 SLW _ BFC ,高维

候 选 频 繁 模 式 集 SLW _ HCFPSETC 和 频 繁 模 式 集 SLW _ FPSETC . 其 中
SLW _ FPSETC = Υr =1 SLW _ FPr C , SLW _ FPr C 表示全局 r (1 ≤ r ≤ k ) 维频繁模式集. SLW _ BFC 同样
k

用 Bloom Filter 方法保存,同时采用 TreeHash 对所有元组进行存储,搜索和更新操作.中心站点 基本窗口 BW _ DSC 更新具体描述如下:
算法 2. BW _ DSC 更新算法 输入: BW _ DSS v (1 ≤ v ≤ d ) 输出: BW _ DSC 步骤:

For ( i = 0; i < m; i + + ) For ( v = 1; v ≤ d ; v + + ) VB[i ] = VB[i ] + VB v [i ] ; /* VB[i] , VB v [i ] 分别表示获得 BW _ BFC 和 BW _ BFS v 的第 i 个位置上的值 */ For ( v = 1; v ≤ d ; v + + ) For every s in BW _ HCFPSETS v If s not in BW _ HCFPSETC { Insert s into SLW _ HCFPSETC ; CFPB[ s ] = CFPB v [ s] ;} /* CFPB[i ] , CFPB v [i] 分别表示获得 s 在 BW _ HCFPSETC 和 BW _ HCFPSETS v 中的元组*/ Else CFPB[ s] = CFPB[ s] + CFPB v [ s] ; For ( v = 1; v ≤ d ; v + + ) For every s in BW _ FPSETS v If s not in BW _ FPSETC { Insert s into BW _ FPSETC ; FPB[ s] = FPB v [ s] ;} /* FPB[i ] , FPB v [i ] 分别表示获得 s 在 BW _ FPSETC 和 BW _ FPSETS v 中的元组*/

Else FPB[ s] = FPB[ s] + FPB v [ s] . 更新中心站点基本窗口后,可以进一步更新中心站点的 SLW _ DSC ,具体算法描述如下:
算法 3. SLW _ DSC 更新算法 输入: 维数阈值 l ;哈希函数 h1 , h2 ,..., hg ;最小支持度 minsup; BW _ DSC ; SLW _ DSC ,滑动窗口容纳基本 窗口的数目 q ,第 i 个基本窗口的数据量 N i = ∑v =1 N i .
d

输出: SLW _ DSC .

-5-

http://www.paper.edu.cn
步骤:

Let SLW _ DSC be empty; For each BW _ DSCi has arrived CSite{ If ( i = 1 ) { For ( j = 0; j < m; j + + ) VS[ j ] = VB[ j ] ; /* VS[ j ] 表示获得 SLW _ BFC 第 j 个位置上的元组*/ For every s in BW _ HCFPSETCi { Insert s into SLW _ HCFPSETC ;
CFPS[ s ] = CFPBi [ s ] ;}

/* CFPS[S ] 表示获得 s 在 SLW _ HCFPSETC 中的元组*/ For every s in BW _ FPSETCi { Insert s into SLW _ FPSETC ;
FPS [ s ] = FPBi [ s ] ;}/* FPS[s ] 表示获得 s 在 SLW _ FPSETC 中的元组*/

} If ( i ≤ q ) { SLW _ DS _ Maintenace ; } Else { For ( j = 0; j < m; j + + ) VS[ j ] = VS[ j ] ? VBi ?q [ j ] ; For every s in BW _ HCFPSETCi ?q { CFPS[ s] = CFPS[ s ] ? CFPBi ? q [ s] ; If ( CFPS[ s] = 0 ) delete s from SLW _ HCFPSETC ;} For every s in BW _ FPSETCi ?q { FPS[ s] = FPS[ s ] ? FPBi ?q [ s ] ; If ( FPS[ s] < minsup × ∑ j =2 N i ? j +1 ) delete s from SLW _ FPSETC ;}
q

SLW _ DS _ Maintenace ;

} }
SLW _ DS _ Maintenace 具体描述如下:

算法 4. SLW _ DS _ Maintenace 算法 输入: 维数阈值 l ;哈希函数 h1 , h2 ,..., hg ;最小支持度 minsup; BW _ DSC ; SLW _ DSC . 输出: SLW _ DSC . 步骤:

For ( j = 0; j < m; j + + ) VS [ j ] = VS [ j ] + VBi [ j ] ; For every s in BW _ HCDSETCi { If s not in SLW _ HCFPSETC { Insert s into SLW _ HCFPSETC ;
CFPS[ s ] = CFPBi [ s ] ;}

Else CFPS[ s ] = CFPS [ s ] + CFPBi [ s ] ; } For all s( dim(s) ≤ l ) in ( SLW _ FPSETC ∪ BW _ FPSETCi ) { id=convert(s,DS,l); If (all VS[hi (id )].count ≥ minsup × ∑ j =1 N i ? j +1 ) {
q

If s not in SLW _ FPSETC { insert s into SLW _ FPSETC ;

-6-

http://www.paper.edu.cn
FPS [ s ].count = min (VS [ hi (id )].count ) ;}

Else FPS[s].count = min(VS[hi (id )].count) ; } Else { If s in SLW _ FPSETC delete s and superunit(s) from SLW _ FPSETC ;} } For all s( dim(s ) > l ) in ( SLW _ FPSETC ∪ BW _ FPSETCi ){ If ( CFPS[ s ] ≥ minsup × ∑ j =1 N i ? j +1 ){
q

If s not in SLW _ FPSETC { insert s into SLW _ FPSETC ; FPS [ s ].count = CFPS [ s ].count ;} Else FPS[s].count = CFPS[s].count ; } Else { If (s in SLW _ FPSETC ) delete s and superunit(s) from SLW _ FPSETC ;}

}

3. 3 离群点检测
各个分布站点获得基于当前滑动窗口的全局频繁模式,计算 WFPOF 值,检测离群点.具体 描述如下:
算法 5. Outlier _ d etection 算法 输入: 站点 v 的 k 维数据流 DS v ;全局频繁模式集 SLW _ FPSETC ;偏差阈值 ? ;当前中心站点滑动窗口 数据总量 N 输出: 离群点集合 Outlier. 步骤:

For each datum x arrived in DS v (1 ≤ v ≤ d ) { Support=0;FPS=0;
j=1;

While ( SLW _ FPj C ≠ φ ) and ( j ≤ k ) do { For all j-itemset s of x { If (s in SLW _ FPj C ) {
Support = Support + (( j k ) × FPS[ s ].count ) N ;

/* FPS[s] 表示获得 s 在 SLW _ FPSETC 中的元组*/ FPS=FPS+1;} } j=j+1; }
WFPOF ( x ) = Support ; FPS

If ( WFPOF (x) ≤ ? ) Output datum x which is in current sliding window as outlier; }

3. 4 分布站点与中心站点的交互
与文献[16]类似, FOD-Dstream 算法也定义了被动与主动两种交互方式,但具体实现有较 大的不同.在被动方式下,每个分布站点向中心站点传送信息的周期为一个基本窗口时间跨度
p .中心站点可以以广播的形式向各个分布站点发送 p 值,用以指定发送周期,该方法简单精

-7-

http://www.paper.edu.cn

确. 在主动方式下,每个站点可以根据本站点的数据流变化情况,主动向中心站点请求更新. 设站点 v 上一个基本窗口的频繁模式集为 FPSET1 ,当前基本窗口到目前为止的频繁模式集为
FPSET2 ,可以将 FPSET1 ∪ FPSET2 的频繁模式集分为以下三类.

(1) 存 在 于 FPSET1 而 不 存 在 于 FPSET2 的 频 繁 模 式 集 , 即 为 消 失 的 频 繁 模 式 集 , 记 为
delete( FPSET1 , FPSET2 ) , delete( FPSET1 , FPSET2 ) = FPSET1 ? ( FPSET1 ∩ FPSET2 ) ;

(2) 不 存 在 于 FPSET1 而 存 在 于 FPSET2 的 频 繁 模 式 集 , 即 为 出 现 的 频 繁 模 式 集 , 记 为
add ( FPSET1 , FPSET2 ) , add ( FPSET1 , FPSET2 ) = FPSET2 ? ( FPSET1 ∩ FPSET2 ) ;

(3) 存 在 于 FPSET1 且 存 在 于 FPSET2 的 频 繁 模 式 集 , 即 为 保 持 的 频 繁 模 式 集 , 记 为
retain( FPSET1 , FPSET2 ) , retain( FPSET1 , FPSET2 ) = FPSET1 ∩ FPSET2 .

定义 4 频繁模式集变化率定义为
v ariation = || FPSET1 ∩ FPSET2 || || FPSET1 ||

其中 || ? ? ? || 表示集合所含元素的个数. 给定变化率阈值 θ ,当 v ariation ≤ θ 时,认为站点 v 的数据分布情况已经发生显著变化,这时 站点 v 主动向中心站点发送信息.

4. 算法性能分析与实验结果
4. 1 复杂度分析
下面对 FOD-Dstream 的空间与时间效率进行分析. 在算法中每个分布站点 v 需要维护 2 个基本窗口数据结构 BW _ DSS v 和一个全局频繁模 式集 SLW _ FPSETC , BW _ DSS v 空间复杂度包括三个部分: BW _ BFS v 所需内存空间 O(m) ,高维 (维数大于 l )候选频繁模式集元所需内存 O(| BW _ HCFPSETS v |) 和频繁模式集所需存储空间
O(| BW _ FPSETS v |) .在类 Apriori 算法中,低维候选频繁模式需要大量的存储空间,随着维数的

增加,高维候选频繁模式显著减少. FOD-Dstream 用 O(m)空间对低维候选频繁模式进行估计, 并且用户可以根据内存大小和精度需要设定维数阈值参数 l,因此 O(m+ | BW _ HCFPSETS v |) 可 控制在有限的内存范围内,从而 O(2 | BW _ DSS v | + | SLW _ FPSETC |) 可控制在有限的内存范围 内. 在中心站点需要维护 q + 1 个基本窗口数据结构 BW _ DSC 和一个滑动窗口数据结构
SLW _ DSC ,显然 O(∑i =1 | BW _ DSC |i + | SLW _ DSC |) 也可控制在有限的内存范围内.
q +1

网络传输的数据大小为 O(| BW _ DSS v |) 和 O(| SLW _ FPSETC |) ,这样的数据规模在一般的网 络环境下均可实现较快的传输,相对于分布站点上对于新到数据的计算时间,其可以忽略. 在最坏情况下,在每个分布站点,对每个新到数据,维护基本窗口的时间复杂度为 O(2 k ) ,计 算其 WFPOF 值的时间复杂度为 O(2 k ) ,所以分布站点上的时间复杂度为 O(2 k +1 ) .在中心站点维 护基本窗口和维护滑动窗口的时间复杂度也为 O(2 k +1 ) .因此算法对数据流总量具有线性复杂 度. 在实际情况下,高维频繁模式数量很少,并且存在的频繁模式的最高维数远小于 k.因此 FOD-Dstream 算法的计算量远小于最坏情况的时间估计.

-8-

http://www.paper.edu.cn

4. 2 实验结果
本节对算法 FOD-Dstream 进行实验测试,实验在 4 台 Intel 1.8G/512MB 的 PC 机上进行, 其中一台作为中心站点,另外三台作为分布站点.算法由 Visual C++(6.0)实现.利用数据产生器 产生仿真数据,并将其每一维*均分割成 10 个区间,每个区间作为该维上的一个类别属性值. 数据以文本文件形式保存在分布站点上,并采用 I/O 读取的方式模拟数据流的产生.实验中各 分布站点采用相同的数据流速. 为了测试算法 FOD-Dstream 对于全局离群点检测的有效性,采用如下指标评价算法的精 确度
[16]

:
P recision = | O1 ∪ O2 ∪ ? ? ? ∪ Od | Oc

其 中 O1 ∪ O2 ∪ ? ? ? ∪ Od 通 过 FOD-Dstream 得 到 , 而 Oc 通 过 在 测 试 数 据 集 的 并 集 上 运 行 FOD-Dstream 算法得到.进行如下的三个实验. (1)在 3 个分布站点分别生成 30 维相同分布的仿真数据,大小为 300K,均包含相同的两个 主 要 聚 类 , 同 时 加 入 均 匀 分 布 的 离 群 点 , 滑 动 窗 口 为 t slw = 50s , 基 本 窗 口 为 tbw = 5s , minsup=0.2%,l=10.对比 100s, 150s, 200s, 250s 时的 4 个滑动窗口中的检测结果,如图 2 所示. 可以看到,在各分布站点数据分布相同的情况下,采用 FOD-Dstream 算法的精度较高,即在分 布站点进行检测和在全局数据集上进行检测的结果大致相同.
100 98 Precision(%) 96 94 92 90 1 2 Window 3 4
Precision

图 2 算法精度比较-1 (流速 1000 元组/s)

Fig.2 Precision of Algorithm-1 (stream_speed=1000)

(2)在 3 个分布站点分别生成 30 维不同分布的仿真数据集,大小为 300K.每个数据集中分 别包含两个不同的主要聚类和均匀分布的离群点,滑动窗口为 t slw = 50s ,基本窗口为 tbw = 5s , minsup=0.2%,l=10.仍然考察 100s, 150s, 200s, 250s 时的 4 个滑动窗口中的检测结果.试验分为 Test1:在各个分布站点上运行算法,但是不进行与中心站点的交互,得到 O1 ∪ O2 ∪ ? ? ? ∪ Od ;Test2: 采用 FOD-Dstream 挖掘全局离群点.同时在 3 组数据的并集上得到全局离群点集合 Oc .两次实 验的精度如图 3 所示.可以看到,在 Test1 不进行交互的情况下,由于各数据集存在不同的聚类, 造成了各数据集的离群点分布也有较大的差异,某个数据集中检测出来的离群点往往是其他 数据集聚类中的点.因此精度大大降低.而在 Test2 中,由于中心站点能够维护全局相关的数据 分布信息,精度较高.

-9-

http://www.paper.edu.cn
100 90 Precision(%) 80 70 60 50 40 1 2 Window Test1 Test2 3 4

图 3 算法精度比较-2 (流速 1000 元组/s)

Fig.3 Precision of Algorithm-2 (stream_speed=1000)

(3)测试主动请求更新对于精确度的影响.在 3 个分布站点分别生成 30 维不同分布的仿真 数据集,每组数据包含 3 各主要聚类,大小为 400K,这里没有对生成的数据进行随机化,而是按 照生成聚类的顺序进行排列,并随机插入均匀分布的离群点.在这种情况下,各组数据存在从 一 个 聚 类 到 另 外 一 个 聚 类 的 概 念 转 移 现 象 . 滑 动 窗 口 为 t slw = 60s , 基 本 窗 口 为 tbw = 15s , minsup=0.2%, l=10.考察 120s, 180s, 240s, 300s 时的 4 个滑动窗口中的检测结果.实验分为 Test1:不采用主动请求更新,即各站点在经过一个基本窗口时间周期更新信息;Test2:采用主动 4 更新请求,设 v ariation = 0.5 .两次实验结果如图 4 所示,在第 2、 时间窗口中,由于各组数据的不 同聚类数据混合,在不能立刻更新全局信息的情况下,检测精度都显著下降.在采用了主动更 新以后,各分布站点提前进行了信息的交互,因此精度下降程度较小.
100 90 Precision(%) 80 70 60 50 40 1 2 Window 3 4

Test1

Test2

图 4 算法精度比较-3 (流速 1000 元组/s)

Fig.4 Precision of Algorithm-3 (stream_speed=1000)

为了测试算法 FOD-Dstream 的内存使用情况,分别生成 10、15、20、25 和 30 维仿真数 据集,大小为 300K,滑动窗口为 t slw = 20s ,基本窗口为 tbw = 5s ,l=8.算法运行稳定时,分布站点和 中心站点使用的内存情况如图 5、图 6 所示,算法使用的内存可保持在一个较小的范围内.
350 300 Memory(KB) 250 200 150 100 50 0 10 15 20 Number of Dimensions 25 30 minsup=0.4% minsup=0.8%

图 5 FOD-DStream 分布站点使用内存

Fig.5 Distrubuted Site Memory Used by FOD-DStream - 10 -

http://www.paper.edu.cn

900 800 700 Memory(KB) 600 500 400 300 200 100 0 10 15 20 25 30 minsup=0.4% minsup=0.8%

Number of dimensions

图 6 FOD-DStream 中心站点使用内存

Fig.6 Central Site Memory Used by FOD-DStream

为了测试算法 FOD-DStream 的执行速度,在分布站点分别生成大小 500K,维数为 30 的仿 真数据集,并观察在某个分布站点上的执行效率.执行时间如图 7 所示.可以看到, FOD-Dstream 算法执行时间与数据流规模成线性关系
120 Running Time(s) 100 80 60 40 20 0 100 200 300 Dataset Size(K) 400 500
Running Time

图 7 FOD-DStream 的执行时间

Fig.7 Running Time of FOD-DStream

5. 结论
本文针对分布式环境下的高维类别属性数据流离群点检测进行了研究,在已有工作的基 础上提出了 FOD-Dstream 算法.该算法采用 WFPOF 来度量高维数据的离群度,利用时间相关 滑动窗口进行各个分布站点和中心站点的交互.各个分布站点维护局部频繁模式,并与中心站 点 交 互 获 得 全 局 频 繁 模 式 , 计 算 基 于 全 局 数 据 的 WFPOF 来 检 测 离 群 点 . 实 验 结 果 表 明,FOD-Dstream 是可行有效的.进一步提高算法的实现效率,对数据流变化的自适应性,解决 分布式环境下数据挖掘的隐私保护问题等是下一步的研究内容.

- 11 -

http://www.paper.edu.cn

参考文献
[1] B. Babcock, S. Babu, M. Datar, R. Motawani, and J. Widom. Models and Issues in Data Stream Systems. In: Proceedings of the 21st ACM Symposium on Principles of Database Systems. 2002. 1-16. [2] S. Muthukrishnan. Data streams: Algorithms and applications. In: Proceedings of the 14th annual ACM-SIAM symposium on Discrete algorithms. Philadelphia: Society for Industrial and Applied Mathematics, 2003. 413-413. [3] 金澈清, 钱卫宁, 周傲英. 流数据分析与管理综述. 软件学报, 2004, Vol.15(8): 1172-1181 [4] Hinneburg A, Keim D. Optimal Grid-Clustering: Towards Breaking the Curse of Dimensionality in High-Dimensional Clustering[C]. In: Proceedings of the 25th International Conference on Very Large Data Base, 1999, 506-519. [5] Parsons L, Haque E, Liu H. Subspace Clustering for High Dimensional Data: A Review[C]. In: Proceedings of 2004 ACM-SIGMOD International Conference on Knowledge Discovery and Data Mining. [6] 李存华, 孙志挥. GridOF: 面向大规模数据集的高效离群点检测算法. 计算机研究与发展, 2003, Vol.40, No.11:1586-1592. [7] Muthukrishnan S, Shah R, Vitter J. Mining Deviants in Time Series Data Streams[C]. In: Proceedings of the 16th International Conference on Scientific and Statistical Database Management. Los Alamitos, CA:IEEE Computer Society Press, 2004. 41-50. [8] Jagadish H V, Koudas N, Muthukrishnan S. Mining Deviants in a Time Series Database[C]. In: Proceedings of the 25th International Conference on Very Large Data Bases. Edinburgh: Morgan Kaufmann Publishers Inc., 1999. 102-113. [9] 杨宜东 , 孙志挥 , 朱玉全 , 杨明 , 张柏礼 . 基于动态网格的数据流离群点快速检测算法 [J]. 软件学报 , 2006,17(8): 1796-1803. [10] 周 晓 云 , 孙 志 挥 , 张 柏 礼 , 杨 宜 东 . 高 维 类 别 属 性 数 据 流 离 群 点 快 速 检 测 算 法 [J]. 软 件 学 报 , 2007,18(4):933-942. [11] Palpanas T, Papadopoulos D, Kalogeraki V, Gunopulos D. Distributed Deviation Detection in Sensor Networks [J]. SIGMOD Record, vol.32(4), 2003:77-82. [12] Locasto M E, Parekh J J, Stolfo S J, Keromytis A D, Malkin T, Misra V. Collaborative Distributed Intrusion Detecion (Technical Report CUCS-012-04). Department of Computer Scientce, Columbia University in the City of New York, 2004. [13] Zhang Y, Lee W. Intrusion Detection in Wireless Ad-hoc Network.[J] Mobile Computing and Networking, 2000, 275-283. [14] Zhang Y, Lee W, Huang Y-A. Intrusion Detection Techniques for Mobile Wireless Networks[J]. Wireless Networks, 2003, 9, 545-556. [15] Huang Y-A, Lee W. A Cooperative Intrusion Detection System for Ad-hoc Networks[C]. In: Proceedings of the ACM Workshop on Security of Ad-hoc and Sensor Networks, 2003, ACM Press:135-147. [16] 杨宜东, 孙志挥, 张净. 基于核密度估计的分布数据流离群点检测[J]. 计算机研究与发展. Vol.42, May, 2005: 289-294. [17] Bloom B. Space/Time Trade-offs in Hash Coding with Allowable Errors[J]. Communications of the ACM, 1970, 13(7): 422-426. [18] Cohen S, Matias Y. Spectral Bloom Filters[C]. In: Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data. San Diego: ACM Press, 2003, 241-252. [19] R. Jin, G. Agrawal. An Algorithm for In-Core Frequent Itemset Mining on Streaming Data. In: Proceedings of the 5th IEEE International Conference on Data Mining. IEEE Computer Society, 2005, 210-217.

- 12 -

http://www.paper.edu.cn

Outlier Detection of Distributed High Dimensional Categorical Data Streams
Sun Zhihui,Zhou Xiaoyun,Ni Weiwei
College of Computer Science and Technology,Nanjing Jiangsu(210096) Abstract Data mining in data stream, such as clustering, classifying, etc, becomes a hot research field, but the research on outlier detection of high dimensional data stream just begin. In this paper, we introduce an algorithm for outlier detection in distributed high dimensional categorical data streams based on time sensitive sliding window and WFPOF. Our method looks every local stream as a subset of the global stream union and finds outliers at every distributed site by global frequent pattern. For reducing network traffic between sites, every distributed site maintains the local frequent pattern of local data stream, and sends it to central site. Then the global frequent pattern can be computed and send back to distributed sites. Detailed solutions for many problems, such as communication and maintenance of frequent pattern, are also presented. Keywords:distributed data streams,outlier detection,frequent pattern,high dimension

作者简介:孙志挥,男,1941 年生,教授,博士生导师,主要研究方向数据库知识发现, 复杂信息系统应用。

- 13 -


相关推荐

最新更新

猜你喜欢