数据流聚类算法CluStream介绍

经典数据流聚类算法CluStream概要,报告人：高贺庆时间：2012-9-23,背景,随着计算机软硬件的不断升级，人们获取数据能力越来越高。在电信、金融、天气预报、网络入侵检测、传感器网络等领域出现了一种不同于传统静态数据的流数据。这种数据流有自己的特点。,数据流特点,1、数据实时达到2、数据到达次序独立，不受系统控制3、数据量是巨大的，不能预知其大小4、单次扫描，数据一经处理，除非特意保存，否则不能再次被处理,数据流聚类,聚类是数据挖掘中一类重要的问题，在许多领域有其应用之处。聚类定义：给定一个有许多数据元素组成的集合，我们将其分为不同的组（类、簇），使得组内的元素尽可能的相似，不同组之间的元素尽可能的不同。由于数据流的特点，对它的聚类算法提出了新的要求。,数据流聚类算法要求,1、压缩的表达（概要数据）2、迅速、增量地处理新到达的数据3、快速、清晰地识别离群点,CluStream概要,C.C.Aggarwal等人在2003年提出了该著名的经典数据流聚类框架。它引入了簇和时间帧结构两个主要的概念，将数据流聚类过程分为在线部分（微聚类）和离线部分（宏聚类）。在线部分实时处理新到达的数据，并周期性的存储统计结果；离线部分就利用这些统计结果结合用户输入得到聚类结果。,CluStream的影响,CluStream两阶段框架是一个著名的框架，后续有许多算法在其基础上进行各方面的改进。它的在线部分可以实时处理较快速度的流数据，并得到统计结果。离线部分结合用户输入的参数可以近似得到过去某些时候的聚类结果。,CLuStream算法的核心概念,微簇（Micro-clusters）时间衰减结构（PyramidalTimeFrame）,数据流一种形式化描述,数据流计算模型,界标模型滑动窗口模型衰减模型,微簇（Micro-clusters）,CluStream以微簇的形式维护关于数据位置的统计信息。这些微簇被定义成簇特征向量在时间上的扩展。这些微簇额外增加的时间属性很自然将其应用于解决数据流问题。在上述数据流定义下，微簇是一个2d+3（d是数据维度）的元组,时间帧结构（PyramidalTimeFrame）,上述微簇需要在某些时刻维护和存储到磁盘以供离线阶段查询。由于数据量巨大，不可能将所有时刻的微簇信息都存储到磁盘（这部分信息叫做快照），因此引入时间帧结构。它将时间轴划分成不同粒度的时刻，结果是离现在的越近粒度越细，反之越粗。,T=55的时间轴划分,这种时间帧结构的一些好处。1.能满足用户对最近数据感兴趣的需求；2.运行100年的数据流仅仅需要存储大概95个快照，这能满足有限内存的需求。,在线部分（微簇维护）,初始化簇首先在磁盘上存储最初始的initNumber个数据点，然后采用标准的k-means算法形成q个微簇：M1、M2Mq。在线处理对于以后达到的每一个数据点Xik，要么被上述的某个微簇吸收，要么放进它自己的簇中。首先计算Xik与q个微簇中的每一个的距离（实际上是其中心）。将其放到离它最近的那个簇Mp中。,特殊情况1.Xik虽然离Mp最近，但是Xik却在Mp的边界外；2.由于数据流的演化，Xik可能是一个新簇的开端。处理方法为落在边界外的数据点创建一个带独有标志id的新簇，这需要减少一个其他已经存在的簇。这可以通过删除一个最早的簇或者合并两个最早的簇来实现。,如何安全删除？估计每一个簇中最后m个达到的数据点的平均时间戳，然后删除带有最小时间戳的值（时间越早值越小且小于用户定义的阈值）的那个簇。这种方法只增加了存储每个簇中最后m个点的数据的信息（时间戳）。,何时合并？有些情况下，不能合并任何两个微簇。这种情况是发生在当所有上述计算的时间值都大于那个阈值，此时需要合并某两个靠的最近的微簇。此时用它们原来的id一起标志这个新的微簇。同时，需要存储金字塔时间结构对应时刻的微簇（实际上指的是微簇的特征向量值）到磁盘。,离线部分（宏簇创建）,用户在该部分可以在不同时间幅度内发现簇。这部分所用的数据是在线部分形成的统计信息，这可以满足内存有限的需求。用户提供两个参数h和k，h是时间幅度，k是预定义的需要形成的簇的数目。,k-means算法,基本步骤1.从n个数据对象任意选择k个对象作为初始聚类中心；2.根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；3.重新计算每个（有变化）聚类的均值（中心对象）；4.计算标准测度函数，当满足一定条件，如函数收敛时，则算法终止；如果条件不满足则回到步骤2。,离线部分算法,该部分采用改进的k-means算法（1）初始阶段不在随机的选取种子，而是选择可能被划分到给定簇的种子，这些种子其实是对应微簇的中心。（2）划分阶段一个种子到一个“伪数据点”（也就是微簇）的距离就等于它到“伪数据点”中心的距离。（3）调整阶段一个给定划分的新种子被定义成那个划分中带权重的微簇中心。,簇演化分析,CluStream可以进行演化分析演化分析就是分析数据流在过去一段时间内潜在的一些变化。比如在入侵检测系统检测到在某一时间段收到某种类型的攻击。,实验评估,一、数据集合选择二、评估手段,数据集,人工数据集和真实数据集。由人工数据集相关属性容易被控制，用它来评估算法在不同纬度和不同聚类数目上的性能。用真实数据集来评估算法的有效性以及在评估其是否能发现数据流潜在的演化特性。,评估手段,SSQ:评估聚类质量运行时间：评估算法效率灵敏度：对参数的敏感程度,CluStream算法优缺点,优点：提出了两阶段聚类框架，算法能适应数据流快速、有序无限、单遍扫描的特点。能够发掘数据流潜在的演化特性。缺点：1、不能发现任意形状的簇；2、不能很好地识别离群点；3、对高维数据聚类质量下降；,后续研究,基于两层次的数据路聚类解决高维问题的数据流聚类（HPStream）基于滑动窗口的数据流聚类（Clu-Win）基于密度的数据流聚类（ACluStream、DenStream及改进）基于网格的数据流聚类（D-Stream及改进）采用树索引的网格数据流聚类（CD-Stream、TDCA）基于分形维度的数据路聚类（FCluStream）,参考文献,【1】B.Babcocketal.ModelsandIssuesinDataStreamSystems,ACMPODSConference,2002.【2】BarbarD.Requirementsforclusteringdatastreams.ACMSIGKDDExplorationsNewsletter,2003，3(2):23-27.【3】LiadanOCallaghanetal.Stream-DataAlgorithmsForHigh-QualityClustering,Proceedingsofthe18thInternationalConferenceonDataEngineering(ICDE02),2002.【4】C.C.Aggarwal,J.Han,J.Wang,P.Yu.AFrameworkforClusteringEvolvingDataStreams.VLDBConference,2003.【5】SunHL,YuG,BanYB,ZhaoFX,WangDL.CDS-Tree:Aneffectiveindexforclusteringarbitraryshapesindatastreams.In:Proc.ofthe15thIntlWorkshoponResearchIssuesinDataEngineering:StreamDataMiningandApplications(RIDESDMA2005).Washington:IEEEComputerSociety,2005.81-88.(孙焕良，赵法信，鲍玉斌等.CD_Stream种基于空间划分的流数据密度聚类算法.计算机研究与发展，2004,10.)【6】C.C.Aggarwal,HanJ,WangJ,eta1.AFrameworkforProjectedClusteringofHighDimensionalDataStreamsc.Procofthe30thVLDBConference，2004：852-863.【7】ZhuWei-Heng,YinJian,XieYi-Huang.Arbitraryshapeclusteralgorithmforclusteringdatastream.JournalofSoftware,2006,17(3):379-387.(朱蔚恒,印鉴,谢益煌.基于数据流的任意形状聚类算法.软件学报,2006,17(3):379-387.)【8】CaoFeng,EsteryM,QianWeining,eta1.Density-basedClusteringoveranEvolvingDataStreamwithNoiseC.Proc.ofthe2006SIAMConferenceonDataMining.Bethesda,USA:s.n.,2006.【9】ChenYixin,LiTu.Density-basedClusteringforReal-timeStreamDataC.Proc.ofthe2007KDDConferenceonDataMining.LasVegas,USA:s.n.,2007.【10】