流数据的聚类方法研究

流数据的聚类方法研究报告人：导师：Email:[e-mail]2007.4.14介绍提纲◆选题依据◆国内外研究动态◆课题研究目标◆课题的主要关键技术和研究方法◆计划安排选题依据流数据流数据的定义及其特点数据流的三种模型构造概要数据结构的方法聚类聚类定义传统的聚类方法数据流聚类的特点流数据流数据是一种大量的连续到达、时间有序、快速变化、潜在无限的数据。流数据的特点是：※数据量十分庞大，这些数据随着时间的增长数量急剧上升※流数据均按照时间顺序连续到达。※相比于有限的内存，不可能存储整个数据集，只能存储数据的汇总信息。※大多数流数据本质上是多维，多层的数据，需要多维多层次的处理。数据流的三种模型按照数据流上各个元素重要程度的不同可以将其分为三种子模型：界标模型，滑动窗口模型和衰减窗口模型。界标模型：考虑从某一个特定的时间点s开始到当前时间点N之间的所有数据，查询范围是[s…N]。滑动窗口模型：仅考虑最近的w个元素。衰减窗口模型：数据流算法的范围从初始时间点到当前时间点，查询范围是[0…N]。但各个元素的重要程度是不同的。新到达的元素，重要程度较高，旧的元素，重要程度较低。构造概要数据结构的方法直方图技术(histograms）:等宽直方图、v-优化直方图随机采样（randomsampling）:常用的方法:水库抽样小波方法（wavelet）梗概（sketches）基于滑动窗口模型的方法●指数直方图(exponentialhistogram)按照元素的到达次序购建桶。桶的容量按照不同级别而指数递增。●基本窗口（basicwindow）将大小为W的窗口按照时间次序划分成k个等宽的子窗口，成为基本窗口，每个基本窗口包含W/k个元素聚类聚类问题将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程称为聚类。这些对象与同一簇中的对象彼此相似，与其他簇中的对象相异。传统聚类方法：基于划分：k-meansk-mediods基于层次：BIRCH基于密度:DBScan基于网格：STING基于模型：COBWEB算法性能比较国内外研究动态数据流聚类问题是近些年数据挖掘理论研究和应用领域中的热点问题。研究的主要方向有单层数据流的聚类、双层数据流聚类、高维数据流聚类、基于密度的数据流聚类、多数据流聚类等。◇2000年,Guha提出针对数据流聚类的LOCALSEARCH算法。基于分治的思想使用一个不断的迭代过程实现有限空间对数据流进行k-means聚类.。◇2002年，O’Callaghan提出了STREAM，是单层数据流聚类算法的经典之作。◇2003年，AGGARWALC等人设计了一种更加行之有效的算法框架CluStream。双层数据流聚类框架应运而生。◇2003年,Barbard总结了数据流聚类算法的要求，并对一些可能适用于数据流的聚类算法做了一次总结。◇2004年，AGGARWALC提出了一种高维，投影数据流聚类算法HPstream。◇2006年，ZHUWei-Heng等人详细分析了数据流聚类算法CluStream的不足之处，提出了一种采用空间分割、组合以及按密度聚类的算法ACluStream。国内外研究动态◇多数据流的实时聚类◇满足用户需求的多数据流聚类◇基于相位差的数据流的聚类◇高维流数据的降维的聚类◇基于密度的流数据的聚类本课题研究的主要内容有：1.多数据流的实时聚类（1）问题描述及研究背景设在时间t有条数据流，其中。对多条数据流在时间t、跨度L上的聚类,就是要将流数据分为类：使得目标函数最大。（2）已有的研究工作YangJiong用带权重的快照差的和作为流数据间距离的度量,不能反映流数据间趋势变化的相似度。Beringer等人通过对流数据标准化等预处理后用离散傅立叶变换减少噪声,用增量在线的k-means算法进行聚类。算法质量和执行效率都依赖于DFT系数个数,难以在效率和质量间达到平衡。12{,}nXXX12(,)iiiitXxxx12(),(),...,()kCLCLCLG1.多数据流的实时聚类(3)我们的研究思路我们针对多数据流的实时聚类问题，提出了一种基于相关系数的聚类算法CORREL-cluster。◇相关系数（优于欧氏距离）：◇衰减系数（如取=0.99）：突出新数据比旧数据在聚类结构中有更大的重要性◇更新时间片段：将长度为的时间片里的数据分为段,每段长为个单位时间。在任意时刻,算法保存个数据段。xyLlmm算法CORREL-cluster对不断到达的流数据实时形成其统计信息，并按一定的时间段进行保存。在一定的时间间隔以后,算法根据统计信息进行聚类。提出一种动态的k-means的聚类算法。该算法首先用k-means方法产生初始聚类。在以后的各次聚类操作中,由于流数据的变化是逐渐的,相邻两次的聚类结果之间有大部分是重叠的。因而每次聚类时,仅需在前一次聚类的基础上,用少量的几次k-means迭代就可以得到结果。使用聚类调整算法adjust进行聚类调整,更新k的值。1.多数据流的实时聚类对世界气象数据集的实验1(a)世界各个城市的天气数据1(b)所得第一类：亚洲城市数据1(c)所得第二类：欧洲城市数据1(d)所得第三类：大洋洲城市数据1(e)所得第四类：非洲城市数据1(f)所得第四类：南美洲城市数据实验分析0.80.820.840.860.880.946816numberofsegmentsclusteringqualityCORREL-clusterDFT-cluster实验表明：CORREL-cluster算法在各种片段数下的正确率均比DFT-cluster（30个DFTcoefficient)算法高。实验表明：聚类个数的变化表明了CORREL-cluster算法具有随着数据流适时调整聚类的能力。算法有较好的稳定性。图2聚类质量的比较图3不同初始聚类个数下聚类数的变化2.满足用户需求的多数据流聚类（1）问题描述及研究背景为了支持灵活的聚类要求，满足用户对多数据流不同长度的聚类要求。需要设计一种框架，满足流数据环境中对空间和时间的要求。（2）已有的研究工作Bi-RuDai等人提出了一种自适应的聚类多条流数据的算法ADAPTIVE-cluster，在线阶段使用一种分层机制保存概要信息，提出了两种汇总方法，基于小波和回归的分析。离线阶段设计了一种自适应聚类算法，能够根据流数据的变化在小波模型或回归模型间选择。但算法的在线部分保存信息的时间较长。(3)我们的研究思路我们针对用户的不同需求，设计了一种COR算法框架。该框架包含两个部分：前台信息存储层和后台聚类层。前台信息存储层：保存多条数据流的汇总信息，设计了一种保存信息的机制。将数据流片段按指数递增的形式划分：从小到大分别是：1，2，4，8，…每个级别的片段的个数不能大于一个预定义的门槛值。如果某个级别片段的个数大于门槛值，则合并本级别最早生成的片段，创建一个更高级别的片段。合并操作会导致更高级别片段的连锁合并操作。2.满足用户需求的多数据流聚类由以下公式确定各片段数的分配情况。按这种方法可使得用户的查询长度和所能的到的聚类长度的误差最小。后台聚类层根据用户提交的查询长度，从片段表中截取相应长度的信息，然后使用k-Medoids算法聚类。22(4)liiCli'argmax()1iikmC（1）（2）2.满足用户需求的多数据流聚类实验分析0.950.960.970.980.991101520253035404550NumberofsegmentsClusteringqualityDatasetADatasetB图4前台保存信息阶段扩展性能比较图5不同片段数下的聚类质量实验表明：COR算法比ADAPTIVE-cluster算法效率更高。这是因为ADAPTIVE-cluster算法要花费时间选择一种保存信息的模型。实验表明：COR算法的聚类质量较高。且划分的片段数越大，对汇总信息的聚类越接近于对原始数据的聚类。3.基于相位差的流数据的聚类（1）问题描述及研究背景多条数据流之间很可能会存在某种调控关系。通常有两种类型的调控关系：正向和反向。例如，若数据流a影响b,则a值上升，那么经过一定的时间延迟后，b的值上升（正向调控作用），或下降（反向调控作用）。图6具有调控关系的两条数据流（2）已有的研究工作已有学者提出若干种方法提取数据流之间的调控信息，包括简单的相关性分析、边检测方法、贝叶斯网络模型。这些方法都没有考虑到数据流之间的时间延迟。HongYan提出了一种基于谱分析的方法，但是该方法考虑的是整条数据流，没有考虑流数据的动态性。(3)我们的研究思路针对这一问题，我们使用基于自回归模型（autoregressivemodeling）的方法来度量序列之间的相关度。将序列分解成谱参数成员之和，再根据谱参数计算相关系数。3.基于相位差的流数据的聚类3.基于相位差的流数据的聚类具体为：每个谱成分由四个参数来表示：振幅（amplitude）、相位（phase）、衰减速率（dampingrate）、频率（frequency）。我们将相位设为0来计算相关系数，从而有效的解决了相位偏差的问题。谱成分之间的相关系数定义为：（3）（4）最终，两个序列之间的相关系数由公式（5）确定。3.基于相位差的流数据的聚类（5）4.高维流数据的降维的聚类（1）问题描述及研究背景聚类算法不仅要擅长处理低维的数据集，还应能处理高维数据，对高维流数据聚类是当前流聚类的研究热点，高维数据可能是非常稀疏且高度偏斜的数据集．因而设计一种有效的距离度量标准是一个亟待解决的问题。（2）已有的研究工作AGGARWALC提出了一种高维，投影数据流聚类算法HPstream。将类定义在部分联系密切的维上，在子维上聚类，取得了较好的聚类效果，但是每一数据到达后，要重新计算子维使得算法的执行效率不高。(3)我们的研究思路我们把高维流数据的每一属性看成一条数据流，因而一条高维数据流可以看成是多条单属性的数据流。将每一属性标准化后，首先用标准的k-means方法聚类，得到初始的几个类，再根据一定的标准，在每个类中，选择一个有代表性的属性来代表整个类，再参加下一次的聚类，得到最终的结果。4.高维流数据的降维的聚类5.基于密度的流数据的聚类（1）问题描述及研究背景在传统的聚类分析中，k-means和k-median是最经典的算法。同样，在流数据聚类中，它们也发挥着巨大的作用。许多流聚类思想都是以k-means和k-median的聚类思想为基础，并在此基础上进行改进，以适应流数据的特点。但基于划分的方法决定了它们有一个共同的缺点，那就是聚类个数k的确定。另外，它们采用的都是基于距离的度量方法，不能发现任意形状的类。能否设计一种流数据聚类算法，能够在数据流中发现任意形状、个数不定的聚类呢？（2）我们的研究思路我们提出了一种基于密度的数据流实时聚类算法RTCS，可以很好挖掘任意形状的数据。＊算法引入数据点的蜕化系数概念，对多维数据和空间单元格动态计算密度。＊算法采用了在线/离线双层框架，它在前台在线层快速实时地将到达的数据点放入相应的单元格，在后台离线层形成初始聚类，并不断地更新单元格的密度来自适应地调整聚类。＊算法提出了对孤立点的处理策略，能够根据密度的动态变化区分出真正的孤立点并剔除之，而这种剔除对后面的聚类结果没有影响。由于算法无需计算和比较距离，大大提高了执行效率。5.基于密度的流数据的聚类图785000个数据点的随机分布图8t1时刻的聚类结果图9t2时刻的聚类结果图10t3时刻的聚类结果实验表明：图8显示了RTCS算法首先在t1时刻发现了类1，并去除了大量的孤立点。图9显示在t2时刻类1消失，算法去除了所有的孤立点，并产生了类2和类3两个新类，且该时刻类2处于渐渐消退中。图10显示了在t3时刻数据流全部流结束时刻的聚类结果，可以看出类3处于渐渐消退过程中，且类4产生。到此，数据集中所有的类均及时地被RTCS算法发现，且有效地去除了所有孤立点。实验分析论文实施计划2006.6-2007