张东月,周丽华,吴湘云,赵丽红

1(云南大学 信息学院,云南 昆明 650000)

2(丽江师范高等专科学校,云南 丽江 674199)

数据流是一种随着时间增加而顺序、快速、大量、连续到达的数据序列.近年来,随着软硬件的发展,大量的数据流不断产生,如金融数据、视频监控数据、传感数据和网络流量数据等.这些数据流大部分是无标签的,所以实时聚类数据流并从中提取有价值的信息,成为了数据挖掘领域的重要问题之一[1-4].然而,由于数据流的连续性、无限性、演变性等特点,要求数据流聚类算法只能在资源约束的条件下单次扫描数据流,并能够随时间的变化追踪簇的形状和位置的变化[5,6].除此之外,提高数据流聚类算法的精度和效率,也是一直存在的重要挑战.

现有的数据流聚类算法大多采用经典的在线/离线框架[7]来处理数据流.在线阶段将到达的数据对象映射到一组支持快速查找的网格结构中,以此汇总数据流并提取数据流的摘要信息.每个网格都类似于一组数据对象的集合,是在单次扫描数据流的环境下创建的.离线阶段,根据用户或应用程序的需要,使用传统的(或改进的)聚类算法将网格结构合并,生成最终聚类[8-10].采用在线/离线框架的数据流聚类算法通过网格提取数据流的概要信息,能够较快地处理数据流并支持实时聚类,但是这些聚类算法在将数据对象映射到网格并增量更新网格时,通常假设网格之间彼此独立,忽略了网格之间的相互影响,使得提取的数据流概要信息不够精确,从而影响了聚类精度.

为了提高聚类精度,MR-Stream[11]映射数据时使用了尺寸更加精细的网格;DBSTREAM[12]引入共享密度来检测微簇内数据的分布状态,避免了两个微簇相交区域密度较低却仍然将他们聚为一类的现象,提高了聚类质量.但是网格的精细化既增大了内存占用又降低了算法效率;而共享密度不仅需要计算微簇之间关系,还要计算数据对象与微簇的关系,这样才能捕捉到两个微簇相交区域的数据量,同样降低了算法效率.本文提出了一种基于网格耦合的数据流聚类算法,称为 GCStream.首先,基于网格内的数据对象定义网格权重,并在聚类过程中不再独立处理网格,而是基于网格内数据对象的分布状态考虑网格之间权重的相互影响,即,一个网格权重的变化会使相邻网格的权重增加或减小,网格的耦合更加准确地表达了数据之间的相关性,从而提高聚类精度.其次,基于网格内数据的分布,通过搜索密度相连的网格完成聚类,并根据高密度网格的变化捕捉簇的演化.

本文的主要贡献包括:

(1) 聚类过程中不再独立处理网格,而是考虑了网格之间的耦合关系,从而更加准确地表达了数据之间的相关性;

(2) 提出了一种基于网格耦合的数据流聚类算法,该算法不需要指定簇的数目,只需通过搜索密度相连的网格完成聚类,并根据高密度网格的变化捕捉簇的演化;

(3) 在人工和真实数据流上进行了实验验证,通过实验对比了所提算法的性能.

本文第1节介绍数据流聚类的典型算法.第2节介绍网格耦合的相关概念和定义.第3节给出GCStream的算法流程并分析算法的时间复杂度.第4节给出在合成和真实数据集上的对比实验.最后,总结论文工作.

1 相关工作

现有的数据流聚类算法可以分为基于划分的、基于层次的以及基于密度的方法[13].前两种方法主要基于对象之间的距离进行聚类,比如STREAM[14]算法采用类似批处理的方式将数据流分块,将每一批数据分为k个簇,通过保留k个簇的中心点汇总每一批数据.STREAM算法无法在任意时刻给出当前数据流的聚类结果,并且也没有考虑数据流的演变性.CluStream[7]算法提出了在线/离线两阶段处理框架:在线阶段通过微簇结构以增量方式维护数据流的概要信息,离线阶段基于概要信息和用户输入产生聚类结果,克服了STREAM算法不能实时产生聚类结果的问题.但是 CluStream 算法没有体现近期数据与历史数据对聚类结果的不同影响,并且在高维数据流的聚类上表现不佳.HPStream算法[15]通过投影技术和衰减簇结构对CluStream算法进行了改进,能够集成当前数据和历史数据,更好地聚类高维数据流.但是,HPStream 算法仍然不能聚类任意形状的数据流,并对噪声敏感.

基于密度的方法通过查找被低密度区域包围的高密度区域来进行聚类,能够发现任意形状的簇并且可以去除噪声.DenStream 算法[16]、D-Stream 算法[8]、MuDi-Stream 算法[9]、MR-Stream[11]和 DBSTREAM 算法[12]都继承了CluStream的在线/离线框架.DenStream算法的在线阶段通过将数据点分配给离它最近的微簇来进行微聚类,并且提出了核心微簇、潜在核心微簇和离群微簇的概念来区分正常簇的数据、可能发展为正常簇的数据和噪声数据;离线阶段通过 DBSCAN算法进行宏聚类,所以它能发现任意形状的簇.D-Stream算法的在线阶段将数据流映射到相应的网格,并通过网格密度对网格进行分类;离线阶段通过合并相邻网格产生聚类结果.MuDi-Stream 算法的在线阶段计算数据点与网格中心的距离,并将数据点分配给距离其最短的网格;离线阶段通过改进的DBSCAN算法生成聚类结果,在多密度数据流上表现较好.MR-Stream算法使用网格树结构来存储网格,树中每个节点代表一个网格,并且存有其父和子节点的概要信息.MR-Stream 算法的在线阶段将当前数据映射到网格树的相应叶子节点,离线阶段在不同网格树高度上通过合并相邻网格进行聚类.该方法本质上是通过将大的网格细分为多个小网格来提高聚类质量,但是网格细分导致内存占用成倍地增加,降低了聚类效率.DBSTREAM 算法通过共享密度对数据流进行聚类,其在线阶段通过微簇来维护数据流的概要信息,并且通过计算微簇与微簇、数据对象与微簇之间的关系来捕捉两个微簇之间共同拥有的数据,即共享密度;离线阶段在进行宏聚类时不仅考虑微簇之间的距离关系,同时还考虑不同微簇共同拥有的数据量.这种通过引入共享密度来检测微簇内数据的分布状态的方法,避免了两个微簇相交区域密度较低却仍然将它们聚为一类的现象,提高了聚类质量.但是DBSTREAM算法需要的计算量较大,降低了聚类效率,这一点在高维数据流上尤为突出.

除了聚类效率,上述算法在新数据到达而更新数据摘要时均独立处理摘要结果,忽略了概要之间的相互影响,从而影响了算法的聚类精度.

2 网格耦合的相关概念和定义

本节首先介绍网格耦合的相关概念,然后给出网格耦合的定义.

2.1 基本概念

假设S=s1×s2×…×sd是一个d维的空间,将空间si(i=1,2,…,d)均匀分为pi份,即,则空间S被划分为个网格.每一个网格g由组成,其中,ji=1,2,…,pi.g可以表示为g=(j1,j2,…,jd).如果网格在某一维度m(1≤m≤d)上满足并且,则称网格g1和g2在第m维相邻.两个网格只要在某一维度相邻,则称这两个网格为相邻网格.

设输入数据流中的每个数据对象X=(x1,x2,…,xd)是d维空间中的一个点,如果xi∈si,ji,则可以将数据对象X映射到空间S的网格g中,记为g(x)=(j1,j2,…,jd),xi∈si,ji.映射到同一网格中的数据对象距离相近,因此可以对各个网格内的数据进行汇总形成概要,从而聚类过程只针对概要进行处理,降低存储空间和计算成本.

数据流中的数据对象有不同的到达时间,对聚类的贡献也不同.为了区分历史数据和新数据,许多数据流聚类算法[1,7,8]为数据流中每个数据对象分配一个带有衰减因子的权重,使其重要性(新鲜度)随时间推移而下降.

定义2.1(数据权重).如果数据对象X在tp时刻到达,那么X在t时刻的权重W(X,t)定义为

其中,λ-a(0＜λ-a＜1)为衰减因子.参数λ和a控制衰减因子的衰减速度,a的绝对值越大,衰减速度越快.

由于数据对象被映射到网络中,因此可以基于数据对象的权重定义网格权重.

定义2.2(网格权重).设E(g,t)表示到时刻t为止,映射到网格g中的数据对象集合,则网格g在时刻t的权重定义为网格g内所有数据对象的权重之和,即:

网格权重的大小反映了网格内数据对象的数目和数据对象的新鲜程度.网格内数据的变化会引起网格权重的变化,即使没有新的数据对象映射到网格g,g的权重W(g,t)也会减小,因为g中数据对象的权重是随时间逐渐衰减的.Chen和Tu在文献[8]中指出,从0时刻开始到任意时刻读取到的数据流总权重不超过1/(1-λ-a).假设网格数量为N,那么每个网格权重为1/[N(1-λ-a)].

不同的网格包含的数据量不同,因此,不同的网格具有不同的权重.基于网格权重的大小,Chen和 Tu[8]还将网格分为稀疏网格和稠密网格:如果t时刻网格g的权重W(g,t)满足W(g,t)≤Cs/[N(1-λ-a)],则称网格g为稀疏网格;如果W(g,t)≥Cd/[N(1-λ-a)],则称网格g为稠密网格,其中,Cd(Cd＞1),(0＜Cs＜1)是阈值参数.

2.2 网格耦合

许多基于网格的聚类算法在聚类过程中独立处理网格,忽略了网格之间的相互影响,从而影响了聚类质量.如图1所示,图中显示了截止到tp时刻数据流映射到网格1～网格6的数据分布.网格6由于数据量太少,可能会被当成噪声网格,使得网格6中的数据不被聚类;网格3和网格4是相邻的非稀疏网格,因此网格3和网格4中的数据会聚在一个簇中.实际上,网格6中的数据应该与网格4和网格5中的点聚成一簇,网格3与网格4中的点应该分属不同的簇.针对这个问题,本文提出了一种基于网格耦合的数据流聚类方法.该方法在聚类过程中不再独立处理网格,而是基于网格内数据对象的分布状态考虑网格之间权重的相互影响,即,一个网格权重的变化会使相邻网格的权重增加或减小,比如图1中网格4权重的增大使得网格6权重增加、网格3权重减少,从而避免独立处理网格带来的问题.

Fig.1 Data distribution within the grid as the timetp图1 截止到tp时刻网格内的数据分布

为了表示网格内数据对象的分布状态,本文将网格内带权数据对象的中心定义为网格质心.由于数据流是动态的,因此网格质心也会随时间而变化.如果数据对象在网格内均匀分布,则网格质心位于网格中心;如果数据对象在网格内分布不均匀,则网格质心不在网格中心.如图1中,网格3和网格4的网格质心就不在网格中心.

定义2.3(网格质心).设E(g,t)为截止到t时刻映射在网格g中的数据对象集合,W(X,t)代表数据对象X在t时刻的权重,则网格g在t时刻的质心C(g,t)定义为网格g内带权数据对象的加权平均,即:

为了快速计算网格质心,定理2.1给出了基于tp时刻的网格质心C(g,tp)来计算t时刻网格质心C(g,t)的更新方式.

定理2.1.假设网格g在tp时刻的质心是C(g,tp),t时刻有新数据对象X′映射进来,则t时刻网格g的质心C(g,t)的计算公式为

其中,k是一个质心调节参数:如果0＜k＜1,则表示降低历史数据权重对网格质心的影响,提高网格质心的实时性;如果k＞1,则表示增加历史数据权重对网格质心的影响,降低网格质心的实时性.

证明:假设每一时刻数据流中只有一个数据对象到达,网格g在tp时刻的质心是C(g,tp).根据网格质心定义公式(3)、网格权重公式(2)可以得出t时刻质心公式:

因为t时刻网格权重可以根据tp时刻网格权重迭代得出,所以通过公式(5)可推得公式(6):

另一方面,根据将tp时刻的质心公式可得到公式(7):

将公式(7)带入公式(6),可得到网格质心迭代公式(8):

网格质心表示网格内数据的分布状态,为了度量两个网格内数据分布的距离,本文定义了网络间的质心距离. □

定义2.4(网格质心距离).设C(gi,t)={ci1,ci2,…,cid}和C(gj,t)={cj1,cj2,…,cjd}分别是两个相邻网格gi和gj的质心,则在t时刻,这两个相邻网格质心间的距离disC(gi,gj)定义为

为了减少计算量,本文只考虑相邻网格间的耦合,因此,两个不相邻网格间的质心距离定义为无穷大.

网格之间的相互影响与网格质心之间的距离有关:距离越近,影响越大;反之越小.实际上,质心距离越近的网格,网格内的数据点属于同一个簇的可能性越大;而距离较远的网格内的数据点属于不同簇的可能性大.属于同簇的网格,其权重的变化趋势应该相同;属于异簇的网格,其权重的变化趋势应该相反.为了区分网格之间的不同影响,本文定义了正影响和负影响的概念.设Dislen为影响区域阈值,如果disC(gi,gj)≤Dislen,则网格gi对网格gj产生正影响;反之产生负影响.正影响表明gi权重增加,gj权重随之增大;负影响则表示gi权重增加,gj权重随之减小.影响系数定量度量了网格间的影响强度.

定义2.5(影响系数(Ideg)).网格gi和gj之间的影响系数定义如下:

其中,MaxCdis为相邻网格质心距离的最大值(体对角上的两点间距离).假设网格空间为d维,网格边长为len,则MaxCdis定义为

如果网格gi对网格gj产生正影响,则Ideg(gi,gj)＞0;反之,Ideg(gi,gj)＜0.如图2中,两个星形符号分别表示网格3和网格6的质心.假设时刻t有一个数据映射到网格4中,则以网格4的质心为圆心、Dislen为半径,生成一个实线圆,圆内区域是网格4的正影响区域,圆外是网格4的负影响区域.由图可见:网格4权重的变化对网格6产生正影响,对网格3产生负影响,使网格6的权重有所增加,网格3的权重有所减少.网格间的耦合增大了网格4和网格6中数据聚到同一个簇的可能,减小了网格4和网格3中数据聚到同一个簇的可能,克服了独立处理网格带来的问题.

在基于网格的聚类算法中,每个簇都是由一组相连的网格组成,每个簇被稀疏网格包围.通常,处于簇中心的网格,其权重与相邻网格的权重之和较大;而位于簇边缘的网格,其权重与相邻网格的权重之和较小.为了区分这两种不同的状态,本文定义了核心网格的概念,并将簇定义为密度相连的网格内的数据集合.

定义2.6(核心网格).设L(g,t)是网格g在Dislen影响范围内的网格集合,如果L(g,t)内所有网格的权重之和大于阈值,即,则称网格g为核心网格.所有核心网格的集合表示为LD.由于核心网格很可能为簇中心网格,其权重与相邻网格权重之和大于簇边缘上的稀疏网格及其相邻网格权重之和,所以阈值ε≥Cd/[N(1-λ-a)].

定义2.7(密度相连).设网格gi是一个核心网格,如果gj是LD中离网格gi质心距离最近的网格,则称网格gj与gi密度相连,网格gj中的数据点被分配到gi中数据点所属的簇.核心网格gi及其密度相连的网格内数据对象构成的集合称为簇,记为Cgi.

设网格gi和gj密度相连,gk和gl密度相连,如果disC(gp,gq)＜Dislen(p=i,j;q=k,l),则gi,gj,gk和gl密度相连,即gi和gj构成的簇与gk和gl构成的簇合并.

Fig.2 Effect of mapping data objects in grid 4 on grid 3 and grid 6图2 网格4中映射数据对象对网格3和网格6的影响

3 GCStream算法

本文所提的GCStream算法也是基于在线/离线框架,如图3所示.

Fig.3 GCStream algorithm flow chart图3 GCStream算法流程图

在线阶段创建网格并将数据流中到达的数据对象映射到相应网格中,然后根据新到达的数据对象更新核心网格及网格的权重、质心等,并周期性检测及删除噪声网格.离线阶段主要基于更新的核心网格和网格的质心寻找密度相连的网格,从而完成聚类,追踪簇的变化.每个步骤详细介绍如下.

· 在线阶段

(1) 将数据映射到网格.

首先初始化一个红黑树用以存储网格列表,而每个网格由一个多元组(key,W,cvec,status,clusterid,tg,Ngkeys)组成.其中,key是由网格的位置信息生成的哈希码,W为网格的权重,cvec为网格的质心向量,status代表网格的稠密状态,clusterid为该网格所属的簇号,tg记录的为该网格上次的更新的时刻,Ngkeys为该网格的邻居列表.当数据对象到来时,根据该数据对象的属性向量为其寻找对应的网格进行映射.如果该网格在网格列表中不存在,则创建一个新的网格单元.

(2) 根据网格耦合思想更新网格.

当数据对象映射到网格之后,需要更新该网格的元组.值得注意的是,网格之间是相互影响的,所以本文在更新当前网格时,还通过网格质心距离捕捉该网格与周围网格的关系,以此来确定周围网格的更新.

(3) 更新核心网格.

当网格权重发生变化时,需要判断该网格是否满足核心网格条件.如果满足,则将该网格替换进核心网格列表中.

(4) 周期性检测及删除噪声网格.

噪声网格为一些由噪声生成的网格或一些由簇衰退形成的零星网格.在数据流不断到达的过程中,这些网格不断累积,会造成内存空间的浪费,所以需要定期地检测删除这些噪声网格.

本文根据噪声网格比较稀疏并不可能变为稠密网格的特性,将经过tu时间段还没由稀疏转为稠密的网格定义为噪声网格.定理3.1给出了一个稀疏网格转换为稠密网格所需时间的计算公式.

定理3.1.设网格g是一个稀疏网格,tu是g转换为稠密网格所需的时间,则:

证明:设网格g在t1时刻为稀疏网格,则:

设网格g在t2(t2＞t1)时刻转为稠密网格,则:

如果要求网格g能在最短的时间内由稀疏网格转为稠密网格,则需要时间段tu(tu=t2-t1)内到达的数据对象均映射在网格g内,因此,

其中,X∈(E(g,t2)-E(g,t1))表示时间段tu映射到网格g的数据对象集合.

由数据权重公式可得时间段tu映射到网格g的数据权重为.可以看到,该组数据权重满足等比公式,所以不等式(15)可变形为

联立不等式(14)和不等式(16)可以得到:

(5) 检测核心网格是否变动.

随着时间的推移,网格中历史数据的权重逐渐衰减,新映射进来的数据具有较大权重从而导致网格权重发生变化,进而引起网格类型发生变化:稠密网格与稀疏网格互换、核心网格与非核心网格互换.这些变化使得数据流中的簇也是不断变化的,有的簇会随着时间的流逝慢慢消失,有的簇会随着新数据点的映射而慢慢扩大.所以,本文根据核心网格是否变动来调用离线组件.

在线阶段的 5个步骤主要用于映射数据流以及收集数据流的概要信息.值得注意的是:在高维空间中数据是比较稀疏的,这有可能划分出许多空网格或数据对象数较少的网格.针对这个问题,本文在线阶段在生成网格时,根据当前到达数据样本的属性向量动态生成网格.即当数据流映射进来时,查找网格列表中是否有与其对应的网格:如果有,则将该数据对象映射到该网格并更新该网格的元组;否则,为该数据对象创建一个新网格单元.除此之外,在线阶段的周期性检测及删除噪声网格等步骤则能定期删除一些数据对象数较小的网格.通过以上两个策略,使得 GCStream 算法能够不生成空网格以及减少稀疏网格的数量,既降低了内存占用,也提高了算法的效率.

· 离线阶段

(1) 寻找与核心网格密度相连的网格生成簇.该阶段通过为每个核心网格寻找与其密度相连的网格来将网格进行划分,形成以核心网格为中心的簇;

(2) 合并簇.上述生成的以核心网格为中心的簇可能存在两个网格数据分布接近,使得两个簇相连,所以进一步判断是否存在能够合并的簇是有必要的.

基于核心网格的离线聚类时间复杂度分析.假设某一时刻网格列表中的总网格数为n,核心网格集合LD的大小为Ncg.首先执行算法2的第3步～第5步,生成簇.该过程将剩余网格分配给核心网格,所需要的时间复杂度为O(0.5×Ncg(n-Ncg));然后执行算法2的第6步～第10步,合并簇.在合并簇的时候,需要遍历每个网格的邻居.假设每个网格有Nng个邻居网格,则该阶段时间复杂度为O(Ncg×n).所以基于核心网格的离线聚类算法的时间复杂度为O(Ncg(n-Ncg)+Nng×n).

算法1.GCStream的在线阶段.

输出:网格列表.

步骤:

算法2.GCStream的离线阶段.

输入:网格列表信息;

输出:聚类结果.

步骤:

4 实验评估

本节对 GCStream算法适应和捕捉数据流演变的能力、去除噪声数据的能力、聚类质量以及聚类效率进行了实验评估.

4.1 实验准备

本文实验的操作系统为64位Windows 7旗舰版,硬件环境为Intel(R) Core(TM) i3-3240(3.40GHz),RAM为4GB.

· 测试数据集

本文实验总共用到5个数据集:两个人工数据集(MTD和MOAD)和3个UCI真实数据集(KDDCUP99[17],CoverType[18]和PAMAP2[19]).其中,人工数据集MTD使用MATLAB生成,包含两个凸型簇和两个非凸型簇并带有10%均匀分布的噪声.该数据集用以测试GCStream算法适应和捕捉簇演变的能力以及去除噪声数据的能力.MOAD使用MOA(massive online analysis)工具生成[20,21],该工具是一个处理演变数据流的框架,广泛用于数据流挖掘工作.MOAD数据集由12 072个数据对象组成,分属10个簇,每个数据对象包含1 000个属性,用以测试各算法在不同维度上的效率.KDDCUP99数据集是麻省理工学院林肯实验室收集的网络入侵检测数据集,包含494 020条TCP连接记录,分属于23种不同的网络连接类型.CoverType数据集是美国森林服务信息系统提供的数据集,包含581 012条记录,每条记录由一块30×30平方英尺上的 54个地理数据组成.PAMAP2数据集是Reiss和Strickere收集的身体活动监测数据,由9名佩戴3个惯性测量单位和心率监测仪的受试者进行18项不同的身体活动(如步行、骑自行车、踢足球等)产生的数据组成.本文通过将上述数据集中数据的输入顺序作为数据流的传输顺序,把所有数据集转为流.每个数据集的大小、维度、簇数以及簇之间的最小距离见表1.

Table 1 Dataset feature summary表1 数据集特征汇总

· 对比算法

本文使用 D-Stream[8],DenStream[16],DBSTREAM[12],GCStream-UC作为本文的对比算法.其中,GCStream-UC为在线阶段不考虑网格耦合的GCStream算法,即GCStream-UC算法只是更新映射了数据对象的网格的权重,相邻网格的权重不受新映射了数据对象的网格权重变化的影响.

· 聚类质量评估方法

本文中采用的聚类质量评价方法为Purity和CMM[22].Purity定义如下:

其中,K代表簇的数量,Ci代表簇i中数据对象总数,代表簇i中被正确划分的数据对象数目.Purity度量了各个簇中正确聚类的对象比例.

CMM(clustering mapping measure)是一种考虑了数据流中数据对象的权重(新鲜度)并可以反映簇生成、移动、分裂过程固有错误(比如簇的移动导致部分数据对象丢失;簇的合并和分裂产生重叠的簇,导致一些数据对象被错误划分)的评价指标.此外,CMM还能对数据流中的噪声情况进行度量.CMM定义如下:

其中,Cl={Cl1,…,Cll}是真实簇集合,C={C1,…,Ck,Cφ}是聚类结果,W(o)是数据对象o的权重,pen(o,C)是聚类过程中对遗漏数据对象、错分及噪声的惩罚,con(o,Cl(o))度量了数据对象o与其所属的簇Cl(o)之间的点连通度,F是错误划分的数据对象集合.CMM∈[0,1],CMM值越大,代表聚类质量越好.

4.2 算法参数选择

在进行对比实验之前,需要统一环境变量以及对算法参数进行调整.本文默认设置各数据流数据点到达速率为 1000pt/s,各算法中数据点的衰减速度一致.在 GCStream 中,设置λ=1.002,a=1;在 D-Stream 算法中,设置λ=0.998,a=-1;在 DenStream 和 DBSTREAM 中,设置λ=2,a=0.0028,使得权重衰减函数f=λ-a=0.998.对比算法的其他参数设置需参考其原始文献.由于GCStream算法主要受质心调节参数k,Dislen以及Ncg的影响,所以本节将通过实验探索这3个参数的选择.

4.2.1 质心调节参数k

质心调节参数k决定着历史数据权重对网格质心的影响程度,是网格质心实时性的调节因子.0＜k＜1表示提高网格质心的实时性,k＞1表示降低网格质心的实时性,k=1代表不考虑网格质心实时性,所以本文分别选择小于1、等于1以及大于1的k值进行对比实验.实验结果如图4所示:在KDDCUP99数据流上,k=1时效果最好,于是本文在此基础上进一步缩小参数k的调整幅度,最终确定了k=0.96;在CoverType数据流上,k=0.8和k=1时结果较好,本文在此范围内继续微调参数k,最终确定了k=0.97;在PAMAP2数据流上,聚类结果相差不大,于是本文最终选择了k=0.87.

Fig.4 CMM and Purity comparison of GCStream algorithm under differentk图4 GCStream算法在不同k值下的CMM和Purity对比

4.2.2 距离阈值Dislen

距离阈值Dislen为影响区域阈值,直接影响着网格之间的耦合以及簇的合并.本节实验通过对比GCStream算法在不同Dislen值下的CMM和Purity来探索Dislen的取值,实验结果如图5所示.

在KDDCUP99数据流上,当Dislen=70时,聚类结果的CMM值明显好于另外两个,并且Purity值也是比较高的,所以本文选择在Dislen=70的基础进一步微调参数.在CoverType数据流上,Dislen=80和Dislen=140时聚类结果的CMM值高于Dislen=300的CMM值.进一步观察发现,Dislen=140时聚类结果的Purity值高于Dislen=80时的Purity值,所以本文选择在Dislen=140附近继续寻找最优值.在PAMAP2数据流上,3个参数值的聚类结果相近,所以本文便选择了Dislen=5为本文实验的参数值.

Fig.5 CMM and Purity comparison of GCStream algorithm under different Dislen图5 GCStream算法在不同Dislen值下的CMM和Purity对比

4.2.3 核心网格集合LD大小Ncg

核心网格集合由大于阈值ε的网格组成.本节实验选用不同的Ncg值进行聚类结果的CMM和Purity对比,实验结果如图6所示.在KDDCUP99数据流上,Ncg=6,8时聚类结果的CMM值较高.进一步对比这两个不同Ncg值的聚类结果评价指标值发现,他们的CMM值相差不大,但是Ncg=6时,聚类结果的Purity值要高些,所以本文在KDDCUP99数据集上设置Ncg=6;在CoverType数据流上,当Ncg＞12时,算法聚类结果的 CMM指标值较小,当Ncg≤12时,聚类结果的两个评价指标相差不大,所以本文在CoverType数据流上设置Ncg=12;在PAMAP2数据流上,不同Ncg值得到的聚类结果CMM值相差不大,但是当Ncg=12时,Purity值要高些,所以本文在PAMAP2数据流上设置Ncg=12.

Fig.6 CMM and Purity comparison of GCStream algorithm under differentNcg图6 GCStream算法在不同Ncg值下的CMM和Purity对比

综上,本文后续实验在3个UCI真实数据集上,质心调节参数k分别设置为0.96,0.97,0.87;网格质心距离阈值Dislen分别设置为64,144,5;核心网格集合LD大小Ncg分别设置为6,12,12.

4.2.4 数据集处理

在实验进行之前,有时需要对数据集进行标准化处理.因为实验数据的不同维度代表不同含义,有时数据跨度差别非常大.这就需要对数据进行标准化处理以消除不同维度间的量纲差异,使数据具有可比性.但如果对数据跨度不大的数据集也进行处理,则可能会丢失数据集的真实性和原始性.为此,本文在3个UCI真实数据集(标准化和非标准化)上测试了GCStream算法和3种对比算法的聚类Purity值来决定是否对数据集进行标准化处理.实验结果见表2,可以看到各算法在 3个数据集标准化和非标准化下的聚类Purity值差异很小,所以本文选择不对数据集进行标准化处理.

Table 2 Purity comparison under standardized and non-standardized data sets表2 标准化和非标准化数据集下的Purity对比

4.3 聚类质量评价

4.3.1 UCI数据集的聚类结果

为了验证GCStream算法的聚类质量,本文在3个UCI数据集上运行了GCStream算法、GCStream-UC算法、D-Stream算法、DenStream算法和DBSTREAM算法,比较了这些算法的Purity和CMM指标.实验中,各个算法每隔25s对流数据进行一次聚类,图7比较了各种算法的平均Purity.

Fig.7 Purity comparison on UCI datasets图7 各算法在UCI数据集上的Purity对比

由图7可见,GCStream算法在3个数据流上的平均Purity值均大于其他算法的平均Purity值.D-Stream算法在PAMAP2数据流上的Purity值较小,这是因为PAMAP2数据流中同一时刻内生成的簇较多并且维度较高,D-Stream算法对这类数据流比较敏感.图8展示了各种算法在每次聚类时得到的CMM值,图9比较了各种算法的平均CMM.由图8可见:大多数时刻,GCStream算法的CMM值都是优于对比算法的,并且比较稳定.值得注意的是:GCStream算法的CMM值在3个数据流上的多个时刻均高于GCStream-UC,说明基于网格耦合思想更新网格结构能够提高算法聚类质量.图9表明,在3个数据集上,GCStream算法的CMM均值均大于其他算法的平均CMM.

Fig.8 CMM comparison of algorithms on UCI datasets图8 各算法在UCI数据集上的CMM对比

Fig.9 CMM mean comparison on UCI datasets图9 UCI数据集上的CMM均值对比

4.3.2 GCStream算法在不同数据流速度下的聚类质量

能够快速聚类数据流,是数据流聚类算法的一个重要特性.因此,本文在 KDDCUP99数据流上以不同的数据流速度(1k/s,2k/s,7k/s)验证本文算法聚类质量.聚类结果如图10所示.首先,本文算法能够在这3种速度下处理完数据流,说明 GCStream算法有能力处理速度较快的数据流.然后,分析聚类质量评价指标结果可以得出,随着数据流速度的上升,CMM指标值有所下降,但是下降幅度并不大;Purity指标值下降幅度比CMM值略大,但仍保持在较高的水平.说明GCStream算法在聚类高速数据流时依然可以保存较高的聚类质量.

Fig.10 Cluster quality comparison under different stream rate图10 不同数据流速度下的聚类质量对比

4.3.3 GCStream算法在不同网格边长下的聚类质量

本节实验主要测试不同网格边长对聚类质量的影响.以KDDCUP99为测试数据流,我们分别设置网格边长len=40,100,120,160,其中,len=100为本文整理数据集时发现的KDDCUP99数据集中簇之间的最小距离.聚类结果如图11所示.从图11可以看出,当网格边长大于100时,聚类结果的CMM值和Purity值随着网格边长的增加均有明显的下降.当网格边长小于 100时,聚类质量总体相对稳定.实验结果说明:本文实验设置的网格边长len=100是比较准确的,并且GCStream算法聚类质量随着网格边长的增加而有所下降.

Fig.11 Cluster quality comparison under different grid sides图11 不同网格边长下的聚类质量对比

4.3.4 GCStream算法捕捉簇的演变能力

数据聚类算法的一个重要特性是能够适应和捕捉簇的演变.为了验证GCStream算法的这两个特性,本文在人工数据集 MTD上对 GCStream 算法进行了评估.在这个测试中,本文设置数据流到达速度为 1000pt/s,整个MTD数据流在116s内处理完.该数据集的分布如图12所示.图12(a)～图12(c)分别显示了MTD数据集中簇的生成顺序.其中,簇1和簇2中的数据是交叉分布的,在同一时刻,既有簇1中的数据到达也有簇2中的数据到达,所以簇1和簇2能够同时生成.图13中显示了GCStream算法处理下的MTD数据分布.图13(a)～图13(d)分别显示了在t=5,t=54,t=84,t=116时刻生成的聚类结果.图中深颜色的区域代表当前时刻的生成的簇,浅蓝色的区域代表即将消失掉的簇.可以看出,GCStream能够发现4个不同形状的簇并且不受噪声影响.图14显示了MTD数据流中簇的演变时刻.不同颜色的线条表示不同的簇,线条的长度表示簇存在的时间段.可以看到,簇1和簇2在初始时刻产生,在 55时刻消失;簇 3在 54时刻产生,在 85时刻消失;簇 4在 84时刻产生.除此之外,本文测得GCStream算法在人工数据集MTD的上的Purity均值为0.983,CMM均值为1.说明GCStream算法具有较高的聚类质量.

Fig.12 MTD data distribution图12 MTD数据分布

Fig.13 Data distribution of MTD data set changes with time图13 MTD数据集的数据分布随时间的变化

Fig.14 Evolution of clusters in MTD datasets图14 MTD数据集中簇的演变

4.4 聚类效率评价

实时更新聚类结果对于数据流聚类算法至关重要.本文分别在多个数据集和不同维度上对各算法的效率进行了对比.

4.4.1 GCStream算法在不同数据集上的效率

本节在3个UCI数据流上测试了GCStream与对比算法的聚类效率.设置数据流到达速率为1000pt/s,并且每隔25s显示一次聚类结果.如果各算法能够在25s内处理完这段时间内到达的数据,则证明该算法能够正常运行;否则,说明该算法的效率不足以处理 1000pt/s的数据流.图15显示了 25s间隔内不同算法的响应时间对比.其中,DBSTREAM算法在3个数据流上只在开始时正常运行,随后便运行失败;DenStream和D-Stream算法在PAMAP2数据流上运行失败;而本文的GCStream算法能以1000pt/s的速度正常处理3个数据流并且所需时间最少,这说明GCStream算法效率比对比算法高.

Fig.15 Response time comparison on multiple datasets图15 多数据集上反映时间对比

4.4.2 网格边长与数据维度对GCStream算法效率的影响

本文在MOAD数据流上测试GCStream与对比算法在不同维度和不同网格边长上的聚类效率.图16(a)、图16(b)分别显示了网格边长len=6和len=12.4时,各算法在不同维度上平均效率.在不同大小的网格边长上比较可看出:随着网格边长的增加,GCStream,D-Stream以及DenStream算法效率都有所提升.在不同数据维度上的算法效率比较可以看到:在数据维度小于 100维时,GCStream算法的效率是最高的;当数据维度大于 100维时,GCStream算法的效率也是比较高的,基本处于各算法效率的第2位.

Fig.16 Response time comparisons in multiple dimensions and different grid lengths图16 不同网格边长和多维度上反映时间对比

5 结束语

本文针对现有数据流聚类算法在实时处理高速、大量的数据流时聚类效率和精度不高的问题,提出了一种基于网格耦合和核心网格的数据流聚类算法 GCStream.首先,通过网格耦合实现了对数据流更精确的汇总,提高算法聚类质量;其次,本文根据数据流中局部权重较高的网格相比于局部权重较低的网格更可能为簇中心的特点引入了核心网格,然后以核心网格为簇中心生成簇,并且根据核心网格集合的变化来捕捉簇的演变;最后,通过真实数据集上进行实验,对比了本文所提方法与其他方法的聚类效果和聚类效率.实验结果表明,本文所提算法的聚类效果和聚类效率都优于对比方法.

由于本文算法的实验都是在网格边长相等的基础上进行的,没有考虑不同维度上的数据分布差异.所以本文的未来研究工作将着重研究根据不同维度上的数据分布采用不同的网格边长来使网格划分更精确,以进一步提高聚类质量.