《数据流聚类算法》由会员分享，可在线阅读，更多相关《数据流聚类算法（16页珍藏版）》请在金锄头文库上搜索。
1、Density-Based Clustering for Real-Time Stream Data基于密度的实时数据流聚类(D-Stream)Yixin ChenLi TuDepartment of Computer Science andInstitute of Informatio n Science and Tech no logyEngineeringNanjing University of Aeronautics andWashington University in St. LouisAstronauticsSt. Louis, USAlitu che ncse.wustl.e
2、du翻译 by muyefeiE-mail: 注释：版权归作者所有，文档仅用于交流学习，可以用大纲视图查看文档结构摘要：现有的聚类算法比如CluStream是基于k-means算法的。这些算法不能够发现任 意形状的簇以及不能处理离群点。而且，它需要预先知道k值和用户指定的时间窗口。为了 解决上述问题，本文提出了 D-Stream算法，它是基于密度的算法。这个算法用一个在线部 分将数据映射到一个网格，在离线部分计算网格的密度然后基于密度形成簇。算法采用了密 度衰减技术来捕获数据流的动态变化。为了探索衰减因子、数据密度以及簇结构之间的关系， 我们的算法能够有效的并且有效率地实时调整簇。而且，我们用
3、理论证明了移除那些属于离 群点的稀疏网格是合理的，从而提高了系统的时间和空间效率。该技术能聚类高速的数据流 而不损失聚类质量。实验结果表明我们的算法在聚类质量和效率是有独特的优势，并且能够 发现任意形状的簇，以及能准确地识别实时数据流的演化行为。关键词流数据挖掘基于密度的聚类D-Stream分散的网格1介绍实时聚类高维数据流是困难的但很重要。因为它在各个领域应用到。比如聚类是一项关键的数据挖掘任务。挖掘数据流有几项关键的挑战：（1）单遍扫描（2）将数据流视为数据一个很长的向量在很多应用中捉襟见肘，用户更加关注簇的演 化行为。近来，出现了许多数据流聚类方法。比如STREAM、CluStream以
4、及扩展（在多数据流， 分布式数据流，并行数据流上的扩展）等。CluStream以及扩展的算法有以下一些缺陷：1、只能发现球形簇，不能发现任意形状的簇。2、不能够识别噪声和离群点。3、基于k-means的算法需要多次扫描数据（其实CluStream利用两阶段方法和微簇解决了 该问题）。基于密度的聚类算法介绍。基于密度的方法可以发现任意形状的簇，可以处理噪声，对 原始数据集只需一次扫描。而且，它不需要像k-means算法那样预先设定k值。文本提出了 D-Stream,一种基于密度的数据流聚类框架。它不是简单用基于密度的算法 替代k-means的数据流算法。它有两项主要的技术挑战：首先，我们不大愿意
5、将数据流视为静态数据很长的一个序列，因为我们对数据流演化的 时间特征更加感兴趣。为了捕获簇的动态变化，我们提出了一个新颖的方案，它可以将衰减因子与每个数据点的密度联系起来。与CluStream算法要求用户输入聚类目标的持续时间不 同，衰减因子为系统提供一种新颖的机制，可以通过将最近的数据赋予更高的权重而不是完 全丢弃历史信息，从而动态地、自动地形成簇。另外，D-Stream不需要用户输入簇的数目k。 因此，D-Stream特别适合于那些对应用程序数据具有少量领域知识的用户。其次，由于数据流的数据是海量的，不大可能保留每个数据记录的密度信息。因此我们 提出将数据空间划分成一个个离散的网格，然后将
6、新来的数据映射到对应的网格。这样，我 们不需要保留原始数据，仅仅需要操纵这些网格。然而，对于高维数据，这些网格的数目是 海量的。因此如何处理高维数据来提高伸缩性是一个关键的问题。幸运的是，实际上大部分 网格是空的或者只包含少量的记录，我们在D-Stream中开发了一种内存有效的技术来管理 这些松散的网格。与CluStream算法比起来，D-Stream在聚类质量和效率方面更有优势，而且针对海量高 维的流数据具有更好的伸缩性。本文的剩余部分是这样组织的：部分2是D-Stream算法的概述；部分3提出了关于密 度网格和衰减因子的一些概念和理论;部分4给出了算法的细节和理论分析;部分5是实验， 在人
7、工和真实数据集上与CluStream算法做了比较。部分6是论文总结。2算法概述D-Stream 算法1. procedure D-Stream2. tc 0;3. initialize an empty hash table gridj.ist4. while data stream is active do5. read record x （応:l,応2, ,d）:6. determine the density grid g that contains x:7. if（g liot in. griddist） insert g to gridJ.ist:8. update the char
8、acteristic vector of g9. if tc = gap then10. call initiaLclusteri:11.12.13.14.15.end ifect and remove sporadic grids from gridj.ist:call adjust.clusend ifif tc mod gap 0 then16. tc tc 1;17. end while18. end-procedureFigure 1: The overall process of D-Stream.对一个数据流，在每一个时刻，D-Stream算法的在线部分连续第读入一个新的记录，
9、将多维的数据放置到对应多维空间中的离散密度网格，然后更新密度网格的特征向量（5-8 行）。关于密度网格和特征向量在部分3详细介绍。离线部分在每隔gap （一个时间整数参 数）时间动态地调整簇。在第一个gap时间内产生了初始簇（9-11行）。然后，算法周期性 地移除松散的网格以及调整簇(12-15行)。3密度网格由于不可能保留原始数据，D-Stream将多维数据空间分为许多密度网格然后由这些网 格形成簇。如下图所示：OulineDensity Gridtl），那么g的密度可以按下面的方式更新：酩）=入血切曲）+ 1（5）证明略。JL命题3.1节省了大量的计算时间。原本在每个时间间隔更新所有网格需
10、要计算时间。相反的是，利用命题3.1我们只用宀-的运行时间就可以更新一个网格。这种效率的 增加是非常明显的，因为网格数目N的数目是巨大的。而且，命题3.1节省了内存空间。我们发现在一个网格中，我们没有必要去保存时间戳 和密度值。相反的，对于每个网格，按一下定义的方式存储一个特征向量。稍后解释该向量 中的每一项。命题32 （特征向量）一个网格g的特征向量是一个五元组：宀：九其中，tg是g更新的最后时间，tm是g作为松散（稀疏）网格 从gridist中移除的最后时间，D是网格最后更新后的密度，label是网格的类（簇）标签, status=SPORADIC,NORMAL是一个用来移除松散网格的标签
11、，32基于密度的网格簇我们现在需要决定如何基于密度信息得到簇。我们的方法是基于以下的观察： 命题3.2.让从时刻0到时刻t到达的所有数据记录成为一个集合。我们有：1）工皿口）土） 1是一个控制阈值的参数。比如，我们设定Cm=3。我们要求NCm，因为D（g,t）不能超过二7。在时刻t,对一个网格g,如果有我们称它为稀疏网格。其中，OvClvl。比如，我们设定Cl=0.8。在时刻t,对一个网格g,如果有,V（1 - A） - D t） S A（l-A）我们称它为过渡网格。在多维空间，为了形成簇，我们考虑连接各个邻接的网格，我们按以下定义： 定义3.3 （邻接网格）考虑两个稠密网格工二 d 儿：和
12、山二八，如果存在，使得：1）ji I* A: 1, fe + L d: and2）jk - 3k = 1?那么在第k维空间，gl和g2就是邻接网格。表示为：g1g20定义34 （网格组）如果对于任何两个网格加 A三G,存在一系列网格X 一，甘=就是一个网格组?不明白?相当于俩个端点，中间有很多近似的网格定义35 （内部网格和外部网格）考虑到一个网格组G以及一个网格三心，假如 总八，如果g在每一个维度 一 八存在邻接网格。那么g就是G中的一个内部网格。否则g就是G中的一个外部网格。现在我们准备定义如何基于网格的密度形成簇。定义36 （网格簇）如果G内部每一个网格都是稠密网格而每个外部网格或者是一个 稠密网格或者是一个过渡网格，那么G就是一个网格簇。直观地，一个网格簇就是一个连接的网格组，它比它周围的网格密度要大。注意到我们 总是尝试在任何可能的时候合并簇，因此这样会导致簇被松散的网格所包围。4 D-Stream算法的组成我们将在图1描述了算法D-Stream的主要部分。对于每一个新的数据记录x,我们将 它映射到一
