流数据的聚类方法研究课件.ppt

1、流数据的聚类方法研究 报告人：导 师：Email: 2007.4.14介绍提纲 选题依据 国内外研究动态 课题研究目标 课题的主要关键技术和研究方法选题依据选题依据 流数据 流数据的定义及其特点 数据流的三种模型 构造概要数据结构的方法 聚类 聚类定义 传统的聚类方法 数据流聚类的特点流数据 流数据是一种大量的连续到达、时间有序、快速变化、潜在无限的数据。流数据的特点是：数据量十分庞大，这些数据随着时间的增长数量急剧上升 流数据均按照时间顺序连续到达。相比于有限的内存，不可能存储整个数据集，只能存储数据的汇总信息。大多数流数据本质上是多维，多层的数据，需要多维多层次的处理。数据流的三种模型 按

2、照数据流上各个元素重要程度的不同可以将其分为三种子模型：界标模型，滑动窗口模型和衰减窗口模型。界标模型界标模型：考虑从某一个特定的时间点s开始到当前时间点N之间的所有 数据，查询范围是sN。滑动窗口模型滑动窗口模型：仅考虑最近的w个元素。衰减窗口模型衰减窗口模型：数据流算法的范围从初始时间点到当前时间点，查询范 围是0N。但各个元素的重要程度是不同的。新到达的元素，重要程度较高，旧的元素，重要程度较低。构造概要数据结构的方法 直方图技术(histograms）:等宽直方图、v-优化直方图 随机采样（random sampling）:常用的方法:水库抽样 小波方法（wavelet）梗概（sket

3、ches）基于滑动窗口模型的方法 指数直方图(exponential histogram)按照元素的到达次序购建桶。桶的容量按照不同级别而指数递增。基本窗口（basic window）将大小为W的窗口按照时间次序划分成k个等宽的子窗口，成为基本窗口，每个基本窗口包含W/k个元素 聚类聚类 o 聚类问题 将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程称为聚类。这些对象与同一簇中的对象彼此相似，与其他簇中的对象相异。o 传统聚类方法：基于划分：k-means k-mediods 基于层次：BIRCH 基于密度:DBScan 基于网格：STING 基于模型：COBWEB算法性能比较国内

4、外研究动态国内外研究动态 数据流聚类问题是近些年数据挖掘理论研究和应用领域中的热点问题。研究的主要方向有单层数据流的聚类、双层数据流聚类、高维数据流聚类、基于密度的数据流聚类、多数据流聚类等。2000年,Guha 提出针对数据流聚类的LOCALSEARCH算法。基于分治的思想使用一个不断的迭代过程实现有限空间对数据流进行k-means 聚类.。2002年，OCallaghan提出了STREAM，是单层数据流聚类算法的经典之作。2003年，AGGARWAL C等人设计了一种更加行之有效的算法框架CluStream。双层数据流聚类框架应运而生。2003年,Barbard 总结了数据流聚类算法的要求

5、，并对一些可能适用于数据流的聚类算法做了一次总结。2004年，AGGARWAL C提出了一种高维，投影数据流聚类算法HPstream。2006年，ZHU Wei-Heng等人详细分析了数据流聚类算法CluStream 的不足之处，提出了一种采用空间分割、组合以及按密度聚类的算法ACluStream。国内外研究动态国内外研究动态 多数据流的实时聚类多数据流的实时聚类满足用户需求的多数据流聚类满足用户需求的多数据流聚类 基于相位差的数据流的聚类基于相位差的数据流的聚类高维流数据的降维的聚类高维流数据的降维的聚类基于密度的流数据的聚类基于密度的流数据的聚类本课题研究的主要内容有本课题研究的主要内容有

6、：1.多数据流的实时聚类多数据流的实时聚类 （1）问题描述及研究背景 设在时间t有条数据流 ，其中 。对多条数据流在时间t、跨度L上的聚类,就是要将流数据分为类：使得目标函数 最大。（2）已有的研究工作 Yang Jiong用带权重的快照差的和作为流数据间距离的度量,不能反映流数据间趋势变化的相似度。Beringer等人通过对流数据标准化等预处理后用离散傅立叶变换减少噪声,用增量在线的k-means算法进行聚类。算法质量和执行效率都依赖于DFT系数个数,难以在效率和质量间达到平衡。12,nX XX12(,)iiiitXx xx12(),(),.,()kCL CLCLG1.多数据流的实时聚类多数

7、据流的实时聚类 (3)我们的研究思路 我们针对多数据流的实时聚类问题，提出了一种基于相关系数的聚类算法CORREL-cluster。相关系数 （优于欧氏距离）：衰减系数 （如取 =0.99）：突出新数据比旧数据在聚类结构中有更大的重要性 更新时间片段：将长度为 的时间片里的数据分为 段,每段长为个 单位时间。在任意时刻,算法保存 个数据段。xyLlmmo算法CORREL-cluster对不断到达的流数据实时形成其统计信息，并按一定的时间段进行保存。在一定的时间间隔以后,算法根据统计信息进行聚类。o提出一种动态的k-means的聚类算法。该算法首先用k-means方法产生初始聚类。在以后的各次聚

8、类操作中,由于流数据的变化是逐渐的,相邻两次的聚类结果之间有大部分是重叠的。因而每次聚类时,仅需在前一次聚类的基础上,用少量的几次k-means迭代就可以得到结果。o使用聚类调整算法adjustadjust进行聚类调整,更新k的值。1.多数据流的实时聚类多数据流的实时聚类对世界气象数据集的实验1(a)世界各个城市的天气数据 1(b)所得第一类：亚洲城市数据 1(c)所得第二类：欧洲城市数据 1(d)所得第三类：大洋洲城市数据 1(e)所得第四类：非洲城市数据 1(f)所得第四类：南美洲城市数据 实验分析实验表明：CORREL-cluster算法在各种片段数下的正确率均比DFT-cluster（

9、30个DFT coefficient)算法高。实验表明：聚类个数的变化表明了CORREL-cluster算法具有随着数据流适时调整聚类的能力。算法有较好的稳定性。图2聚类质量的比较图3不同初始聚类个数下聚类数的变化 2.满足用户需求的多数据流聚类满足用户需求的多数据流聚类（1）问题描述及研究背景 为了支持灵活的聚类要求，满足用户对多数据流不同长度的聚类要求。需要设计一种框架，满足流数据环境中对空间和时间的要求。（2）已有的研究工作 Bi-Ru Dai等人提出了一种自适应的聚类多条流数据的算法ADAPTIVE-cluster，在线阶段使用一种分层机制保存概要信息，提出了两种汇总方法，基于小波和回

10、归的分析。离线阶段设计了一种自适应聚类算法，能够根据流数据的变化在小波模型或回归模型间选择。但算法的在线部分保存信息的时间较长。(3)我们的研究思路 我们针对用户的不同需求，设计了一种COR算法框架。该框架包含两个部分：前台信息存储层和后台聚类层。前台信息存储层：保存多条数据流的汇总信息，设计了一种保 存信息的机制。将数据流片段按指数递增的形式划分：从小到大分别是：1，2，4，8，每个级别的片段的个数不能大于一个预定义的门槛值。如果某个级别片段的个数大于门槛值，则合并本级别最早生成的片段，创建一个更高级别的片段。合并操作会导致更高级别片段的连锁合并操作。2.满足用户需求的多数据流聚类满足用户需

11、求的多数据流聚类 由以下公式确定各片段数的分配情况。按这种方法可使得用户的查询长度和所能的到的聚类长度的误差最小。后台聚类层 根据用户提交的查询长度，从片段表中截取相应长度的信息，然后使用k-Medoids算法聚类。22(4)l iiCli argmax()1iikmC（1）（2）2.满足用户需求的多数据流聚类满足用户需求的多数据流聚类 实验分析图4 前台保存信息阶段扩展性能比较 图5不同片段数下的聚类质量 实验表明：COR算法比ADAPTIVE-cluster算法效率更高。这是因为ADAPTIVE-cluster算法要花费时间选择一种保存信息的模型。实验表明：COR 算法的聚类质量较高。且划

12、分的片段数越大，对汇总信息的聚类越接近于对原始数据的聚类。3.基于相位差的流数据的聚类基于相位差的流数据的聚类（1）问题描述及研究背景 多条数据流之间很可能会存在某种调控关系。通常有两种类型的调控关系：正向和反向。例如，若数据流a影响b,则a值上升，那么经过一定的时间延迟后，b的值上升（正向调控作用），或下降（反向调控作用）。图6具有调控关系的两条数据流（2）已有的研究工作 已有学者提出若干种方法提取数据流之间的调控信息，包括简单的相关性分析、边检测方法、贝叶斯网络模型。这些方法都没有考虑到数据流之间的时间延迟。Hong Yan提出了一种基于谱分析的方法，但是该方法考虑的是整条数据流，没有考虑

13、流数据的动态性。(3)我们的研究思路 针对这一问题，我们使用基于自回归模型（autoregressive modeling）的方法来度量序列之间的相关度。将序列分解成谱参数成员之和，再根据谱参数计算相关系数。3.基于相位差的流数据的聚类基于相位差的流数据的聚类3.基于相位差的流数据的聚类基于相位差的流数据的聚类 具体为：每个谱成分由四个参数来表示：振幅（amplitude）、相位（phase）、衰减速率（damping rate）、频率（frequency）。我们将相位设为0来计算相关系数，从而有效的解决了相位偏差的问题。谱成分之间的相关系数定义为：（3）（4）最终，两个序列之间的相关系数由公

14、式（5）确定。3.基于相位差的流数据的聚类基于相位差的流数据的聚类（5）4.高维流数据的降维的聚类高维流数据的降维的聚类（1）问题描述及研究背景 聚类算法不仅要擅长处理低维的数据集，还应能处理高维数据，对高维流数据聚类是当前流聚类的研究热点，高维数据可能是非常稀疏且高度偏斜的数据集因而设计一种有效的距离度量标准是一个亟待解决的问题。（2）已有的研究工作 AGGARWAL C提出了一种高维，投影数据流聚类算法HPstream。将类定义在部分联系密切的维上，在子维上聚类，取得了较好的聚类效果，但是每一数据到达后，要重新计算子维使得算法的执行效率不高。(3)我们的研究思路 我们把高维流数据的每一属性

15、看成一条数据流，因而一条高维数据流可以看成是多条单属性的数据流。将每一属性标准化后，首先用标准的k-means方法聚类，得到初始的几个类，再根据一定的标准，在每个类中，选择一个有代表性的属性来代表整个类，再参加下一次的聚类，得到最终的结果。4.高维流数据的降维的聚类高维流数据的降维的聚类5.基于密度的流数据的聚类基于密度的流数据的聚类（1）问题描述及研究背景 在传统的聚类分析中，k-means 和k-median是最经典的算法。同样，在流数据聚类中，它们也发挥着巨大的作用。许多流聚类思想都是以k-means 和k-median的聚类思想为基础，并在此基础上进行改进，以适应流数据的特点。但基于划

16、分的方法决定了它们有一个共同的缺点，那就是聚类个数k的确定。另外，它们采用的都是基于距离的度量方法，不能发现任意形状的类。能否设计一种流数据聚类算法，能够在数据流中发现任意形状、个数不定的聚类呢？（2）我们的研究思路 我们提出了一种基于密度的数据流实时聚类算法RTCS，可以很好挖掘任意形状的数据。算法引入数据点的蜕化系数概念，对多维数据和空间单元格动态计算密度。算法采用了在线/离线双层框架，它在前台在线层快速实时地将到达的数据点放入相应的单元格，在后台离线层形成初始聚类，并不断地更新单元格的密度来自适应地调整聚类。算法提出了对孤立点的处理策略，能够根据密度的动态变化区分出真正的孤立点并剔除之，

17、而这种剔除对后面的聚类结果没有影响。由于算法无需计算和比较距离，大大提高了执行效率。5.基于密度的流数据的聚类基于密度的流数据的聚类图 7 85000个数据点的随机分布 图8 t1时刻的聚类结果 图 9 t2时刻的聚类结果 图 10 t3时刻的聚类结果 实验表明：图8显示了RTCS算法首先在t1时刻发现了类1，并去除了大量的孤立点。图9显示在t2时刻类1消失，算法去除了所有的孤立点，并产生了类2和类3两个新类，且该时刻类2处于渐渐消退中。图10显示了在t3时刻数据流全部流结束时刻的聚类结果，可以看出类3处于渐渐消退过程中，且类4产生。到此，数据集中所有的类均及时地被RTCS算法发现，且有效地去

18、除了所有孤立点。实验分析论文实施计划 2006.6-2007.2 广泛阅读有关文献，深入掌握该领域的研究的理论知识。并关注国内外对流数据聚类最新的动态和进展。2007.3-2007.5 编程实现课题的一、二项内容。并给出理论分析和实验结果分析。2007.6-2008.1 编程实现课题的三、四、五项内容。并给出理论分析和实验结果分析。2008.2-2008.3 提交论文初稿。2008.4-2008.5 论文修改、答辩。科研项目情况参与科研项目:1.国家自然科学基金项目，“xxxxxx”，批准号：xxxxxxx，200520062.国家科技攻关计划项目子课题，“xxxxxx”，题号：xxxxxxxx，2004.42005.103.江苏省自然科学基金项目“xxxxxxxx”,项目批准号：xxxxxxxx4.南京大学国家软件新技术重点实验室基金项目，xxxxxxxxx。20052007发表论文情况 多数据流的实时聚类算法。计算机应用（已录用）谢谢各位评审老师！