数据流聚类算法介绍优秀课件

时间帧结构（Pyramidal Time Frame）
• 上述微簇需要在某些时刻维护和存储到磁盘以供离线阶段 查询。由于数据量巨大，不可能将所有时刻的微簇信息都 存储到磁盘（这部分信息叫做快照），因此引入时间帧结 构。它将时间轴划分成不同粒度的时刻，结果是离现在的 越近粒度越细，反之越粗。
T=55的时间轴划分
数据流一种形式化描述
数据流计算模型
• 界标模型 • 滑动窗口模型 • 衰减模型
微簇（Micro-clusters）
• CluStream以微簇的形式维护关于数据位置的统计信 息。这些微簇被定义成簇特征向量在时间上的扩展 。这些微簇额外增加的时间属性很自然将其应用于 解决数据流问题。
• 在上述数据流定义下，微簇是一个2d+3（d是数据 维度）的元组
CluStream概要
• C. C. Aggarwal等人在2003年提出了该著名的经典数据流聚 类框架。它引入了簇和时间帧结构两个主要的概念，将数 据流聚类过程分为在线部分（微聚类）和离线部分（宏聚 类）。在线部分实时处理新到达的数据，并周期性的存储 统计结果；离线部分就利用这些统计结果结合用户输入得 到聚类结果。
• 缺点： 1、不能发现任意形状的簇； 2、不能很好地识别离群点； 3、对高维数据聚类质量下降；
离线部分算法
• 该部分采用改进的k-means算法 （1）初始阶段
不在随机的选取种子，而是选择可能被划分到给定簇的种 子，这些种子其实是对应微簇的中心。 （2）划分阶段 一个种子到一个“伪数据点”（也就是微簇）的距离就等 于它到“伪数据点”中心的距离。 （3）调整阶段 一个给定划分的新种子被定义成那个划分中带权重的微簇 中心。
• 这种时间帧结构的一些好处。
1.能满足用户对最近数据感兴趣的需求；
2.运行100年的数据流仅仅需要存储大概95个快照，这能 满足有限内存的需求。
在线部分（微簇维护）
初始化簇
首先在磁盘上存储最初始的initNumber个数据点，然后采用标准的kmeans算法形成q个微簇：M1、M2…Mq。
在线处理
为落在边界外的数据点创建一个带独有标志id的新簇，这需要减少一 个其他已经存在的簇。这可以通过删除一个最早的簇或者合并两个最 早的簇来实现。
• 如何安全删除？
估计每一个簇中最后m个达到的数据点的平均时间戳，然 后删除带有最小时间戳的值（时间越早值越小且小于用户 定义的阈值）的那个簇。这种方法只增加了存储每个簇中 最后m个点的数据的信息（时间戳）。
k-means 算法
• 基本步骤 1 .从 n个数据对象任意选择 k 个对象作为初始聚类中心； 2 .根据每个聚类对象的均值（中心对象），计算每个对象与
这些中心对象的距离；并根据最小距离重新对相应对象进 行划分； 3.重新计算每个（有变化）聚类的均值（中心对象）； 4.计算标准测度函数，当满足一定条件，如函数收敛时，则 算法终止；如果条件不满足则回到步骤2。
对于以后达到的每一个数据点Xik，要么被上述的某个微簇吸收，要么 放进它自己的簇中。首先计算Xik与q个微簇中的每一个的距离（实际 上是其中心）。将其放到离它最近的那个簇Mp中。
特殊情况
1.Xik虽然离Mp最近，但是Xik却在Mp的边界外； 2.由于数据流的演化，Xik可能是一个新簇的开端。
处理方法
数据流聚类算法介绍
背景
• 随着计算机软硬件的不断升级，人们获取数据能力越来越 高。在电信、金融、天气预报、网络入侵检测、传感器网 络等领域出现了一种不同于传统静态数据的流数据。这种 数据流有自己的特点。
数据流特点
• 1、数据实时达到 • 2、数据到达次序独立，不受系统控制 • 3、数据量是巨大的，不能预知其大小 • 4、单次扫描，数据一经处理，除非特意保存，否则不能
再次被处理
数据流聚类
• 聚类是数据挖掘中一类重要的问题，在许多领域有其应用 之处。
• 聚类定义：给定一个有许多数据元素组成的集合，我们将 其分为不同的组（类、簇），使得组内的元素尽可能的相 似，不同组之间的元素尽可能的不同。
• 由于数据流的特点，对它的聚类算法提出了新的要求。
数据流聚类算法要求
• 1、压缩的表达（概要数据） • 2、迅速、增量地处理新到达的数据 • 3、快速、清晰地识别离群点
• 何时合并？
有些情况下，不能合并任何两个微簇。这种情况是发生在 当所有上述计算的时间值都大于那个阈值，此时需要合并 某两个靠的最近的微簇。此时用它们原来的id一起标志这 个新的微簇。
同时，需要存储金字塔时间结构对应时刻的微簇（实际上 指的是微簇的特征向量值）到磁盘。
离线部分（宏簇创建）
• 用户在该部分可以在不同时间幅度内发现簇。这部分所用 的数据是在线部分形成的统计信息，这可以满足内存有限 的需求。用户提供两个参数h和k，h是时间幅度，k是预定 义的需要形成的簇的数目。
CluStream的影响
• CluStream两阶段框架是一个著名的框架，后续有许多算法 在其基础上进行各方面的改进。它的在线部分可以实时处 理较快速度的流数据，并得到统计结果。离线部分结合用 户输入的参数可以近似得到过去某些时候的聚类结果。
CLuStream算法的核心概念
• 微簇（Micro-clusters） • 时间衰减结构（Pyramidal Time Frame）
簇演化分析
• CluStream可以进行演化分析 • 演化分析就是分析数据流在过去一段时间内潜在的一些变
化。比如在入侵检测系统检测到在某一时间段收到某种类 型的攻击。
实验评估
• 一、数据集合选择 • 二、评估手段
数据集
• 人工数据集和真实数据集。 • 由人工数据集相关属性容易被控制，用它来评估算法在不
同纬度和不同聚类数目上的性能。 • 用真实数据集来评估算法的有效性以及在评估其是否能发
现数据流潜在的演化特性。
评估手段Hale Waihona Puke Baidu
• SSQ:评估聚类质量 • 运行时间：评估算法效率 • 灵敏度：对参数的敏感程度
CluStream算法优缺点
• 优点： 提出了两阶段聚类框架，算法能适应数据流快速、有序无 限、单遍扫描的特点。能够发掘数据流潜在的演化特性。