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

来源：爱够旅游网

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]提出了一个分布式环境下信号网络中

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

- 1 -

http://www.paper.edu.cn

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

本文采用类似文献[16]的分布数据流结构,将不同节点的数据流放在同等的地位上,着重讨论了分布情况下的高维类别属性数据流的离群点检测问题,并在文献[10]的基础上提出了分布高维类别属性数据流离群点检测算法FOD-Dstream.，算法重点解决了数据的高维性和分布环境下各站点的通信协调以及局部频繁模式和全局频繁模式的维护等问题,最后通过实验验证了算法的可行性.

2. 问题描述与相关概念

设D＝{D1, D2, …, Dk}是一个有序集合,Aj

={a(j1),a(j2),...,aj

(nj)

}是类别属性Dj上的值的集合,

其中nj表示类别属性Dj的可取值的个数,相应有k维类别属性空间S=D1×D2×...×Dk.设

Xv=是站点

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

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

CSiteSite1DS1Site2DS2

SitedDSd图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,minsup)={p|Sup(p)≥minsup},

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=1bwi−j+1.size,时间跨度slwi.span=q×p.

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

3. FOD-Dstream算法及其构造

3. 1 分布站点上的局部频繁模式发现与维护

在分布站点v(1≤v≤d)上保存站点v的基本窗口数据结构BW_DSSv和全局频繁模式,包含低维模式估计BW_BFSv,高维候选频繁模式集BW_HCFPSETSv和频繁模式集BW_FPSETSv.其中BW_FPSETSv=ΥkBW_FPrSv,BW_FPrSv表示站点v上r(1≤r≤k)维频繁模式r=1集.BW_BFSv保存的元组结构为(id,count),BW_HCFPSETSv和BW_FPSETSv保存的元组结构为

(item_id,count,level),item_id为模式的编码,level为模式的长度,count为模式的支持

度.BW_BFSv用Bloom Filter[17,18]方法保存,同时采用TreeHash[19]对所有元组进行存储,搜索和更新操作.

为了尽可能地减少网络通讯量,站点v仅向中心站点传送当前的基本窗口信息BW_DSSv.离群点检测是基于大规模数据上的统计信息,因此离群点检测可以在整个滑动窗口建立后开始.分布站点v的BW_DSSv更新算法具体描述如下:

- 3 -

http://www.paper.edu.cn

算法1. BW_DSSv更新算法

输入: 站点v上k维数据流DSv的第i的基本窗口bwiv;维数阈值l;哈希函数h1,h2,...,hg;最小支持度

minsup.

输出: )BW_DSSv(1≤v≤d,第i个基本窗口的数据量Niv. 步骤:

empty; Let BW_DSSv be

Niv=0;

For each datum x arrived in bwiv { Niv=Niv+1;

For all f-itemset (1≤f≤l) s of

x {

id=convert(s,DSv,l); /*convert(s,DSv,l)将s转换成[1…M]之间的整数*/ For (i=1;i≤g;i++) VB[hi(id)].count=VB[hi(id)].count+1;/*VB[i]表示获得BW_BFSv第i个位置上的元组*/ If (s not in BW_FPfSv) {

If (all VB[hi(id)].count≥minsup×Niv){

BW_FPfSv;FPB[s].count=min(VB[hi(id)].count);insert s into

}/*FPB[s]表示获得s在BW_FPSETSv中的元组*/ }

FPB[s].count=FPB[s].count+1; Else if (all VB[hi(id)].count≥minsup×Niv)

Else delete s and all superset(s) from BW_FPSETSv； /* superset(s)表示s的所有超集*/

} j=l+1;

While (BW_FPjSv≠φ) and (j≤k) do {

For all j-itemset s of x {

If (s in BW_HCFPSETSv){

CFPB[s].count=CFPB[s].count+1; }

/*CFPB[S]表示获得s在BW_HCFPSETSv中的元组*/

Else if all (j-1)-itemset of s in BW_HCFPSETSv{

insert s into BW_HCFPSETSv;

CFPB[s].count=1;} If (s not in BW_FPfSv) { If (CFPB[s].count≥minsup×Nip){insert s into BW_FPfSv; FPB[s].count=CFPB[s].count;

} }

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

}

- 4 -

http://www.paper.edu.cn

Else delete s and all superset(s) from BW_FPSETSv；

}

j=j+1;

} }

3. 2 中心站点上的全局频繁模式发现与维护

为了得到基于所有分布站点的全局频繁模式,必须将各分布站点的信息传送给中心站点,在得到全局频繁模式后再分发到各个分布站点.

在中心站点将保存中心站点基本窗口数据结构BW_DSC和滑动窗口数据结构

SLW_DSC.BW_DSC结构与BW_DSSv类似,而SLW_DSC包含低维模式估计SLW_BFC,高维

候选频繁模式集SLW_HCFPSETC和频繁模式集SLW_FPSETC.其中

SLW_FPSETC=Υr=1SLW_FPrC,SLW_FPrC表示全局r(1≤r≤k)维频繁模式集. SLW_BFC同样

用Bloom Filter方法保存,同时采用TreeHash对所有元组进行存储,搜索和更新操作.中心站点

更新具体描述如下: 基本窗口BW_DSC

算法2. BW_DSC更新算法输入: )BW_DSSv(1≤v≤d 输出: BW_DSC 步骤:

For (i=0;i/*VB[i],VBv[i]分别表示获得BW_BFC和BW_BFSv的第i个位置上的值 */ For (v=1;v≤d;v++)

For every s in BW_HCFPSETSv If s not in BW_HCFPSETC{ Insert s into SLW_HCFPSETC; CFPB[s]=CFPBv[s];}

/*CFPB[i],CFPBv[i]分别表示获得s在BW_HCFPSETC和BW_HCFPSETSv中的元组*/ Else CFPB[s]=CFPB[s]+CFPBv[s]; For (v=1;v≤d;v++)

For every s in BW_FPSETSv If s not in BW_FPSETC{ Insert s into BW_FPSETC; FPB[s]=FPBv[s];}

/*FPB[i],FPBv[i]分别表示获得s在BW_FPSETC和BW_FPSETSv中的元组*/

Else FPB[s]=FPB[s]+FPBv[s].

更新中心站点基本窗口后,可以进一步更新中心站点的SLW_DSC,具体算法描述如下:

算法3. SLW_DSC更新算法

输入: 维数阈值l;哈希函数h1,h2,...,hg;最小支持度minsup;BW_DSC;SLW_DSC,滑动窗口容纳基本窗口的数目q,第i个基本窗口的数据量Ni=∑v=1Ni.

输出: 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/*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;jIf (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]q

}

SLW_DS_Maintenace具体描述如下:

算法4. SLW_DS_Maintenace算法

输入: 维数阈值l;哈希函数h1,h2,...,hg;最小支持度minsup；BW_DSC;SLW_DSC. 输出: SLW_DSC. 步骤:

For (j=0;jIf 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=1Ni−j+1){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=1Ni−j+1){ 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_detection算法

输入: 站点v的k维数据流DSv;全局频繁模式集SLW_FPSETC;偏差阈值ϕ;当前中心站点滑动窗口数据总量N

输出: 离群点集合Outlier. 步骤:

For each datum x arrived in DSv(1≤v≤d) { Support=0;FPS＝0；

j=1;

While (SLW_FPjC≠φ) and (j≤k) do { For all j-itemset s of x {

If (s in SLW_FPjC) {

Support=Support+((jk)×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 频繁模式集变化率定义为

variation=

||FPSET1∩FPSET2||

||FPSET1||

其中||⋅⋅⋅||表示集合所含元素的个数.

给定变化率阈值θ,当variation≤θ时,认为站点v的数据分布情况已经发生显著变化,这时

站点v主动向中心站点发送信息.

4. 算法性能分析与实验结果

4. 1 复杂度分析

下面对FOD-Dstream的空间与时间效率进行分析.

在算法中每个分布站点v需要维护2个基本窗口数据结构BW_DSSv和一个全局频繁模式集SLW_FPSETC,BW_DSSv空间复杂度包括三个部分:BW_BFSv所需内存空间O(m),高维(维数大于l)候选频繁模式集元所需内存O(|BW_HCFPSETSv|)和频繁模式集所需存储空间

O(|BW_FPSETSv|).在类Apriori算法中,低维候选频繁模式需要大量的存储空间,随着维数的

在中心站点需要维护q+1个基本窗口数据结构BW_DSC和一个滑动窗口数据结构

q+1

SLW_DSC,显然O(∑i=1|BW_DSC|i+|SLW_DSC|)也可控制在有限的内存范围内.

网络传输的数据大小为O(|BW_DSSv|)和O(|SLW_FPSETC|),这样的数据规模在一般的网在最坏情况下,在每个分布站点,对每个新到数据,维护基本窗口的时间复杂度为O(2k),计

络环境下均可实现较快的传输,相对于分布站点上对于新到数据的计算时间,其可以忽略. 算其WFPOF值的时间复杂度为O(2k),所以分布站点上的时间复杂度为O(2k+1).在中心站点维护基本窗口和维护滑动窗口的时间复杂度也为O(2k+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对于全局离群点检测的有效性,采用如下指标评价算法的精

|O1∪O2∪⋅⋅⋅∪Od|

确度[16]:

Precision=

其中O1∪O2∪⋅⋅⋅∪Od通过FOD-Dstream得到,而Oc通过在测试数据集的并集上运行FOD-Dstream算法得到.进行如下的三个实验.

(1)在3个分布站点分别生成30维相同分布的仿真数据,大小为300K,均包含相同的两个主要聚类,同时加入均匀分布的离群点,滑动窗口为tslw=50s,基本窗口为tbw=5s, minsup=0.2%,l=10.对比100s, 150s, 200s, 250s时的4个滑动窗口中的检测结果,如图2所示.可以看到,在各分布站点数据分布相同的情况下,采用FOD-Dstream算法的精度较高,即在分布站点进行检测和在全局数据集上进行检测的结果大致相同.

10098Precision(%)9694929012Window34Precision

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

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

(2)在3个分布站点分别生成30维不同分布的仿真数据集,大小为300K.每个数据集中分别包含两个不同的主要聚类和均匀分布的离群点,滑动窗口为tslw=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

10090Precision(%)807060504012WindowTest1Test234

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

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

(3)测试主动请求更新对于精确度的影响.在3个分布站点分别生成30维不同分布的仿真数据集,每组数据包含3各主要聚类,大小为400K,这里没有对生成的数据进行随机化,而是按照生成聚类的顺序进行排列,并随机插入均匀分布的离群点.在这种情况下,各组数据存在从一个聚类到另外一个聚类的概念转移现象.滑动窗口为tslw=60s,基本窗口为tbw=15s, minsup=0.2%, l=10.考察120s, 180s, 240s, 300s时的4个滑动窗口中的检测结果.实验分为Test1:不采用主动请求更新,即各站点在经过一个基本窗口时间周期更新信息;Test2:采用主动4时间窗口中,由于各组数据的不更新请求,设variation=0.5.两次实验结果如图4所示,在第2、

同聚类数据混合,在不能立刻更新全局信息的情况下,检测精度都显著下降.在采用了主动更新以后,各分布站点提前进行了信息的交互,因此精度下降程度较小.

10090Precision(%)807060504012Window34Test1Test2

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

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

为了测试算法FOD-Dstream的内存使用情况,分别生成10、15、20、25和30维仿真数

据集,大小为300K,滑动窗口为tslw=20s,基本窗口为tbw=5s,l=8.算法运行稳定时,分布站点和中心站点使用的内存情况如图5、图6所示,算法使用的内存可保持在一个较小的范围内.

350300Memory(KB)250200150100500101520Number of Dimensions2530minsup=0.4%minsup=0.8%

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

Fig.5 Distrubuted Site Memory Used by FOD-DStream

- 10 -

http://www.paper.edu.cn

900800700Memory(KB)60050040030020010001015202530minsup=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算法执行时间与数据流规模成线性关系

120Running Time(s)100806040200100200300Dataset Size(K)400500Running 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, 5-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: 2-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 -

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文