《一种基于势能模型的数据流聚类算法》由会员分享，可在线阅读，更多相关《一种基于势能模型的数据流聚类算法（21页珍藏版）》请在金锄头文库上搜索。
1、 一种基于势能模型的数据流聚类算法 舒 越 解 庆 刘永坚 唐伶俐(武汉理工大学计算机科学与技术学院 湖北 武汉 430070)0 引 言随着信息技术不断发展，信息的传播效率不断提高，各种信息充斥着整个世界，各种高效的智能化数据采集技术投入市场应用，使信息数据的处理能力不断增强，而如何更加精准地从大量信息中挖掘出有价值的信息，是近些年学者们关注的重点之一1。随着数据流的爆发增长，比如金融数据、Web日志数据和视频监控数据等，数据流挖掘引起了学者们的关注2。数据流3是一个连续不断的数字信号序列，具有以下三个特性4。(1) 无限性：因为数据流持续不断地产生，因而数据点的数量是无限的，不能直接将其全
2、部存储到内存中。(2) 动态演变性：数据分布和特征随时间推移而不断变化。(3) 实时性：数据流实时产生，需要被实时处理。这些特点给数据流处理带来了不小的挑战5-6:由于数据流无法全部存储在内存中，对数据流只能扫描一次；由于数据流的动态演变性，随着时间的推移，数据可能发生变化，即“概念漂移”问题；需要具有处理离群点的能力。很多旨在解决数据流聚类问题的算法已经被提出，其中大部分是基于传统聚类算法扩展而来，如：K-means算法、DBSCAN算法和Affinity Propagation Clustering算法等，将这些传统聚类算法改进适用于数据流聚类。除此之外，很多数据流聚类算法沿用在线/离线两
3、阶段数据流聚类框架7，在线阶段旨在构建概要数据结构，离线阶段根据这些概要数据结构使用聚类算法得到最终聚类结果。由于大部分数据流聚类算法以距离作为相似度度量标准，这造成对噪点敏感的问题，聚类效果不理想。针对这个问题，本文提出一种基于势能模型的层次聚类算法PHAStream，该算法结合在线/离线两阶段数据流聚类框架7和基于势能模型的层次聚类算法PHA8，在线阶段采用融合势能和距离的相似度度量标准更新微簇，判断新到达数据点是否合并进现有微簇或新建微簇，并每隔一定时间采取剪枝策略删除过期的微簇，调整所有微簇的类型；离线阶段计算所有正常微簇的势能，构建边缘加权树和树状图，得到最终聚类结果。本文的主要贡献
4、包括：(1) 使用一种新的概要数据结构，它不仅记录数据点属性的统计信息、权重信息和时间戳信息，还有微簇之间的距离信息。它可以快速构建距离矩阵，方便计算微簇的势能，为后续基于势能和距离的相似度度量标准和微簇聚类提供基础。(2) 以势能和距离为相似度度量标准，在线阶段判断新到达数据点可能合并的微簇，然后根据势能判断是否合并进该微簇或新建微簇。传统以距离为相似度度量标准的方法中，新到达数据点是否合并进微簇会受到噪点的干扰，以势能和距离为相似度度量标准，可以减少噪点的干扰。(3) 将基于势能的层次聚类算法PHA改进适用于数据流聚类，可以减少噪点对聚类的影响，提高聚类效果。1 相关工作目前学术界对数据流
5、聚类算法的研究已经取得不少成果，主要分为基于划分的方法、基于层次的方法、基于密度的方法、基于网格的方法和基于模型的方法五种。第一种是基于划分的数据流聚类方法，实践操作较为简单，但必须在操作之前对聚类簇的数量进行设置，数据流的分布形态在初期阶段很难明确，聚类簇的数量很难得到准确的评估和预测。比如，Youn等9提出使用滑动窗口的基于划分的数据流聚类算法，该算法为每个窗口移动生成集群，由于在所有更改的窗口上重复进行聚类，会造成内存和计算时间方面的低效，所以此算法仅考虑窗口的插入和删除元组。第二种是基于层次的数据流聚类方法，在数据的划分方面以微簇为主。如CluStream算法7，该算法提出了在线/离线
6、两阶段数据流聚类框架，在线阶段以增量的方式更新微簇，离线阶段根据用户要求，使用K-means算法对微簇进行聚类。该算法操作简单，但是基于距离的相似度度量使得其对噪点较为敏感。第三种是基于密度的数据流聚类方法，能够实现对任意形状的数据流进行划分，但是在计算过程中需要设置大量初始参数。如DenStream算法10，该算法沿用在线/离线两阶段数据流聚类框架，在线阶段将新到达的数据点分配给距离它最近的微簇，进行微聚类，同时提出了核心微簇、潜在核心微簇和噪点微簇来区分正常微簇数据、可能成为正常簇的微簇数据和噪点数据；离线阶段使用DBSCAN算法来聚类。第四种是基于网格的数据流聚类方法，对聚类数据的形状没
7、有约束限制，但是网格粒度的大小对聚类的质量有较大影响。D-Stream算法11是基于网格的数据流聚类算法之一，该算法沿用在线/离线两阶段数据流聚类框架，在线阶段将每个输入的数据点映射到网格中，离线阶段对这些密度网格进行聚类，并且取出稀疏的网格。张冬月等12提出基于网格耦合的数据流聚类算法，该算法在聚类过程中，不再片面地单独处理网格，而是将每个网格之间的耦合关系纳入考虑的范围内，网格之间的耦合关系可以更加精准地表现数据点之间的相似度，从而提升聚类质量。第五种是基于模型的数据流聚类方法，需要大量的学科领域知识作为辅助，在使用中需要假设模型的支持。例如，朱颖雯等13提出的基于欧拉核的数据流聚类算法，
8、该算法首先采用欧拉核的方式，显式地将数据点映射到同一维度的复数特征空间，接着在这个特征空间中使用GNG(Growing Neural Gas)模型进行聚类。2 势能模型假设无穷远处的势能为0，那么数据点xi来自数据点xj的势能为：(2)在势能模型中，只需要关注势能的相对值，万有引力常数并没有影响，所以为了方便计算，将G设置为1，并假设每个数据点的质量为1，于是式(2)可改写为：数据点xi的势能，表示为来自其他所有数据点对它产生的势能：(4)式中：N就是所有数据点的个数。距离阈值的选取需要考虑数据点的分布，可以通过距离矩阵来进行计算：=mean(MinDi)/S(6)式中：MinDi表示数据点x
9、i和其他数据点之间的最短距离;S为比例因子。由文献14可知，取S=10时，模型可以达到较好的平衡状态。在势能模型中，通常相似的数据点之间势能的差值也比较小，距离也更近，基于势能和距离的聚类方法以该规律为基础进行设计。3 基于势能模型的数据流聚类算法本节详细介绍基于势能模型的数据流聚类算法PHAStream，该算法结合在线/离线两阶段数据流聚类框架和基于势能模型的层次聚类算法PHA，算法的流程如图1所示。图1 PHAStream算法流程3.1 PHAStream算法初始化阶段数据流是一段连续不断的序列点X=X0,X1,Xn,，每个数据点到达的时间分别为T=t0,t1, ,tn,，每个数据点在数据
10、空间中是一个d维向量。考虑不同到达时间的数据点的重要性，对每个数据点加权，利用一个衰减系数来确定权重与时间的关系。使用式(7)来作为衰减函数，其中0，并且t表示当前时间戳tcurrent和该点到达的时间戳tarrival的差值，即t=tcurrent-tarrival。w(t)=2-t(7)在初始化阶段，模型初始化参数并把时间戳t设置为0，对初始长度的数据点使用PHA进行聚类，得到首批微簇。对于每个微簇，模型定义聚类特征向量来记录微簇的统计信息。借鉴StrDip算法15的聚类特征向量，本文提出一种改进的聚类特征向量，主要由带权重的微簇统计信息、微簇的权重和微簇之间的距离信息组成。距离信息可以快
11、速构建距离矩阵，进而快速计算势能。聚类特征向量以这种形式定义: (CFx1,tl,weight,n,t0,dist_arr)。(2)tl: 微簇中最后到达点的时间戳。(4)n:微簇中所有数据点的个数。(5)t0：微簇被创建的时间戳。(6)dist_arr：当前微簇中心点和所有微簇中心点(包括自己)的距离组成的数组。基于聚类特征向量，每个微簇的中心可以通过式(8)计算。3.2 PHAStream算法在线阶段在线阶段，对于每个新到达的数据点，寻找其可能合并的微簇，并判断是否合并进该微簇或者新建微簇，并更新聚类特征向量，每隔固定时间采用剪枝操作，删除过期的微簇并调整所有微簇的类型。(1) 寻找目标微
12、簇。当模型接收到一个新数据点的时候，需要在现有微簇中找到与之最相似的微簇，即其最可能合并进的目标微簇。由文献8，16可知，在势能场中，距离矩阵和势能分别反映了数据点的局部和全局分布，同时可以发现同一个簇中的数据点，势能差值小且相互距离更近，所以这里提出一个新的相似判断标准pd值，如式(9)所示，来找到新数据点的“目标微簇”。pdi=abs(c-i)distci(9)式中：c表示新到达数据点的势能；i表示微簇i的势能；distci表示新到达数据点和微簇i的距离，pdi则表示新到达数据点跟微簇i的势能差绝对值和距离的乘积，因为同一个类中的数据点，势能差值小且相互距离越近，所以取pdi最小值时，微簇
13、i是新到达数据点的“目标微簇”。(2) 微簇的合并准则。当找到目标微簇之后，模型需要判断新到达点需要合并到目标微簇中，还是新建一个微簇。为此，需要设计一个合并准则来进行判断。由文献17可知，一般情况下，由于数据集中噪点的数量是远小于正常数据点的数量，同时噪点的分布也相对稀疏，从数据点的概率分布特点和势能大小分析可知，噪点的势能相对正常数据点更大，从势能角度，这一特点正是区别正常数据点和噪点的关键。如图2所示17，是一个带有噪点的数据集，将每个数据点的势能按从小到大排序，如图3所示17，会出现一个“拐点”C，这个C点被称为“势能拐点”，“势能拐点”之后的数据点被认为是噪点。图2 含有噪点的数据集
14、图3 势能递增图将“势能拐点”作为一个新的合并准则，来判断新到达数据点是否合并进“目标微簇”。根据上述内容，由于此时已经可以求出每个微簇的势能，将新到达的数据点构成的微簇和其他所有微簇的势能按从小到大的顺序排列，构成势能递增图，根据式(10)找到当前势能场下的“势能拐点”。如果新到达数据点微簇的势能和“目标微簇”的势能均在“势能拐点”之前，那么在当前势能场下，新到达数据点微簇和 “目标微簇”均属于正常数据点，所以将新到达数据点合并进“目标微簇”中。否则，以新到达的数据点新建一个微簇。(i-i+1)(i+1-i+2)0(10)(3) 更新微簇与新建微簇。根据微簇的合并准则，当新到达数据点和其目标
15、微簇的势能都在“势能拐点”之前时，那么就将新到达的数据点合并进目标微簇中；否则，以新到达数据点单独成为一个微簇，构建CF向量。假设直到tc才有数据点x被吸收进微簇i，并且i接收上一个点的时间戳为tl，那么带有权重的微簇统计信息将以下列方式更新15:weight=weight2-(tc-tl)+1(11)CFx1=CFx12-(tc-tl)+x(12)通过式(11)和式(12)，可以快速地更新一个微簇新的权重weight和CFx1。CF向量中的dist_arr属性，记录着当前微簇和其他微簇之间的距离信息，虽然不是以增量的方式更新，但是更新的代价并不大，因为在新的数据点到达时，要么将新到达数据点合并进某个微簇，要么以新到达的数据点新增一个微簇，如果处于检查周期，那么就删除过期微簇，期间这三种操作涉及个别微簇，或者只需要更新每个微簇dist_arr属性中个别距离值。dist_arr属性可以大大提高离线阶段进行聚类的效率。(4) 删除微簇与调整微簇类型。微簇随着时间推移，会根据衰退函数改变权重，微簇的权重大于等于预设的权重阈值，则为正常微簇，反之，则为噪点微簇。随着时间的推移，数据流的分布可能发生变化，一些“正常微簇”可能很长时间没有接收新的数据点，变为“噪点微簇”，这个现象我们称为“概念漂移”。所以需要每隔固定时间来检查
