数据流聚类算法CluStream介绍优秀PPT.ppt

《数据流聚类算法CluStream介绍优秀PPT.ppt》由会员分享，可在线阅读，更多相关《数据流聚类算法CluStream介绍优秀PPT.ppt（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、背景随着计算机软硬件的不断升级，人们获得数据实力越来越高。在电信、金融、天气预报、网络入侵检测、传感器网络等领域出现了一种不同于传统静态数据的流数据。这种数据流有自己的特点。数据流特点1、数据实时达到2、数据到达次序独立，不受系统限制3、数据量是巨大的，不能预知其大小4、单次扫描，数据一经处理，除非特意保存，否则不能再次被处理数据流聚类聚类是数据挖掘中一类重要的问题，在很多领域有其应用之处。聚类定义：给定一个有很多数据元素组成的集合，我们将其分为不同的组（类、簇），使得组内的元素尽可能的相像，不同组之间的元素尽可能的不同。由于数据流的特点，对它的聚类算法提出了新的要求。数据流聚类算法要求1、压

2、缩的表达（概要数据）2、快速、增量地处理新到达的数据3、快速、清晰地识别离群点CluStream概要C.C.Aggarwal等人在2003年提出了该著名的经典数据流聚类框架。它引入了簇和时间帧结构两个主要的概念，将数据流聚类过程分为在线部分（微聚类）和离线部分（宏聚类）。在线部分实时处理新到达的数据，并周期性的存储统计结果；离线部分就利用这些统计结果结合用户输入得到聚类结果。CluStream的影响CluStream两阶段框架是一个著名的框架，后续有很多算法在其基础上进行各方面的改进。它的在线部分可以实时处理较快速度的流数据，并得到统计结果。离线部分结合用户输入的参数可以近似得到过去某些时候的

3、聚类结果。CLuStream算法的核心概念微簇（Micro-clusters）时间衰减结构（Pyramidal Time Frame）数据流一种形式化描述数据流计算模型界标模型滑动窗口模型衰减模型微簇（Micro-clusters）CluStream以微簇的形式维护关于数据位置的统计信息。这些微簇被定义成簇特征向量在时间上的扩展。这些微簇额外增加的时间属性很自然将其应用于解决数据流问题。在上述数据流定义下，微簇是一个2d+3（d是数据维度）的元组时间帧结构（Pyramidal Time Frame）上述微簇须要在某些时刻维护和存储到磁盘以供离线阶段查询。由于数据量巨大，不行能将全部时刻的微簇信

4、息都存储到磁盘（这部分信息叫做快照），因此引入时间帧结构。它将时间轴划分成不同粒度的时刻，结果是离现在的越近粒度越细，反之越粗。T=55的时间轴划分这种时间帧结构的一些好处。1.能满足用户对最近数据感爱好的需求；2.运行100年的数据流仅仅须要存储或许95个快照，这能满足有限内存的需求。在线部分（微簇维护）初始化簇 首先在磁盘上存储最初始的initNumber个数据点，然后接受标准的k-means算法形成q个微簇：M1、M2Mq。在线处理对于以后达到的每一个数据点Xik，要么被上述的某个微簇吸取，要么放进它自己的簇中。首先计算Xik与q个微簇中的每一个的距离（事实上是其中心）。将其放到离它最近

5、的那个簇Mp中。特殊状况 1.Xik虽然离Mp最近，但是Xik却在Mp的边界外；2.由于数据流的演化，Xik可能是一个新簇的开端。处理方法 为落在边界外的数据点创建一个带独有标记id的新簇，这须要削减一个其他已经存在的簇。这可以通过删除一个最早的簇或者合并两个最早的簇来实现。如何平安删除？估计每一个簇中最终m个达到的数据点的平均时间戳，然后删除带有最小时间戳的值（时间越早值越小且小于用户定义的阈值）的那个簇。这种方法只增加了存储每个簇中最终m个点的数据的信息（时间戳）。何时合并？有些状况下，不能合并任何两个微簇。这种状况是发生在当全部上述计算的时间值都大于那个阈值，此时须要合并某两个靠的最近的

6、微簇。此时用它们原来的id一起标记这个新的微簇。同时，须要存储金字塔时间结构对应时刻的微簇（事实上指的是微簇的特征向量值）到磁盘。离线部分（宏簇创建）用户在该部分可以在不同时间幅度内发觉簇。这部分所用的数据是在线部分形成的统计信息，这可以满足内存有限的需求。用户供应两个参数h和k，h是时间幅度，k是预定义的须要形成的簇的数目。k-means 算法基本步骤1.从 n个数据对象随意选择 k 个对象作为初始聚类中心；2.依据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并依据最小距离重新对相应对象进行划分；3.重新计算每个（有变更）聚类的均值（中心对象）；4.计算标准测度函数，当

7、满足确定条件，如函数收敛时，则算法终止；假如条件不满足则回到步骤2。离线部分算法该部分接受改进的k-means算法（1）初始阶段不在随机的选取种子，而是选择可能被划分到给定簇的种子，这些种子其实是对应微簇的中心。（2）划分阶段一个种子到一个“伪数据点”（也就是微簇）的距离就等于它到“伪数据点”中心的距离。（3）调整阶段一个给定划分的新种子被定义成那个划分中带权重的微簇中心。簇演化分析CluStream可以进行演化分析演化分析就是分析数据流在过去一段时间内潜在的一些变更。比如在入侵检测系统检测到在某一时间段收到某种类型的攻击。试验评估一、数据集合选择二、评估手段数据集人工数据集和真实数据集。由人

8、工数据集相关属性简洁被限制，用它来评估算法在不同纬度和不同聚类数目上的性能。用真实数据集来评估算法的有效性以及在评估其是否能发觉数据流潜在的演化特性。评估手段SSQ:评估聚类质量运行时间：评估算法效率灵敏度：对参数的敏感程度CluStream算法优缺点优点：提出了两阶段聚类框架，算法能适应数据流快速、有序无限、单遍扫描的特点。能够发掘数据流潜在的演化特性。缺点：1、不能发觉随意形态的簇；2、不能很好地识别离群点；3、对高维数据聚类质量下降；后续探讨基于两层次的数据路聚类解决高维问题的数据流聚类（HPStream）基于滑动窗口的数据流聚类（Clu-Win）基于密度的数据流聚类（ACluStream、DenStream及改进）基于网格的数据流聚类（D-Stream及改进）接受树索引的网格数据流聚类（CD-Stream、TDCA）基于分形维度的数据路聚类（FCluStream）