数据流聚类算法D-Stream

Density-BasedClusteringforReal-TimeStreamData基于密度的实时数据流聚类(D-Stream)翻译bymuyefeiE-mail:[e-mail]注释：版权归作者所有，文档仅用于交流学习，可以用大纲视图查看文档结构摘要：现有的聚类算法比如CluStream是基于k-means算法的。这些算法不能够发现任意形状的簇以及不能处理离群点。而且，它需要预先知道k值和用户指定的时间窗口。为了解决上述问题，本文提出了D-Stream算法，它是基于密度的算法。这个算法用一个在线部分将数据映射到一个网格，在离线部分计算网格的密度然后基于密度形成簇。算法采用了密度衰减技术来捕获数据流的动态变化。为了探索衰减因子、数据密度以及簇结构之间的关系，我们的算法能够有效的并且有效率地实时调整簇。而且，我们用理论证明了移除那些属于离群点的稀疏网格是合理的，从而提高了系统的时间和空间效率。该技术能聚类高速的数据流而不损失聚类质量。实验结果表明我们的算法在聚类质量和效率是有独特的优势，并且能够发现任意形状的簇，以及能准确地识别实时数据流的演化行为。关键词流数据挖掘基于密度的聚类D-Stream分散的网格1介绍实时聚类高维数据流是困难的但很重要。因为它在各个领域应用到。比如...聚类是一项关键的数据挖掘任务。挖掘数据流有几项关键的挑战：（1）单遍扫描（2）将数据流视为数据一个很长的向量在很多应用中捉襟见肘，用户更加关注簇的演化行为。近来，出现了许多数据流聚类方法。比如STREAM、CluStream以及扩展（在多数据流，分布式数据流，并行数据流上的扩展）等。CluStream以及扩展的算法有以下一些缺陷：1、只能发现球形簇，不能发现任意形状的簇。2、不能够识别噪声和离群点。3、基于k-means的算法需要多次扫描数据（其实CluStream利用两阶段方法和微簇解决了该问题）。基于密度的聚类算法介绍。基于密度的方法可以发现任意形状的簇，可以处理噪声，对原始数据集只需一次扫描。而且，它不需要像k-means算法那样预先设定k值。文本提出了D-Stream,一种基于密度的数据流聚类框架。它不是简单用基于密度的算法替代k-means的数据流算法。它有两项主要的技术挑战：首先，我们不大愿意将数据流视为静态数据很长的一个序列，因为我们对数据流演化的时间特征更加感兴趣。为了捕获簇的动态变化，我们提出了一个新颖的方案，它可以将衰减因子与每个数据点的密度联系起来。与CluStream算法要求用户输入聚类目标的持续时间不同，衰减因子为系统提供一种新颖的机制，可以通过将最近的数据赋予更高的权重而不是完全丢弃历史信息，从而动态地、自动地形成簇。另外，D-Stream不需要用户输入簇的数目k。因此，D-Stream特别适合于那些对应用程序数据具有少量领域知识的用户。其次，由于数据流的数据是海量的，不大可能保留每个数据记录的密度信息。因此我们提出将数据空间划分成一个个离散的网格，然后将新来的数据映射到对应的网格。这样，我们不需要保留原始数据，仅仅需要操纵这些网格。然而，对于高维数据，这些网格的数目是海量的。因此如何处理高维数据来提高伸缩性是一个关键的问题。幸运的是，实际上大部分网格是空的或者只包含少量的记录，我们在D-Stream中开发了一种内存有效的技术来管理这些松散的网格。与CluStream算法比起来，D-Stream在聚类质量和效率方面更有优势，而且针对海量高维的流数据具有更好的伸缩性。本文的剩余部分是这样组织的：部分2是D-Stream算法的概述；部分3提出了关于密度网格和衰减因子的一些概念和理论；部分4给出了算法的细节和理论分析；部分5是实验，在人工和真实数据集上与CluStream算法做了比较。部分6是论文总结。2算法概述D-Stream算法对一个数据流，在每一个时刻，D-Stream算法的在线部分连续第读入一个新的记录，将多维的数据放置到对应多维空间中的离散密度网格,然后更新密度网格的特征向量（5-8行）。关于密度网格和特征向量在部分3详细介绍。离线部分在每隔gap（一个时间整数参数）时间动态地调整簇。在第一个gap时间内产生了初始簇（9-11行）。然后，算法周期性地移除松散的网格以及调整簇（12-15行）。3密度网格由于不可能保留原始数据，D-Stream将多维数据空间分为许多密度网格然后由这些网格形成簇。如下图所示：3.1基础定义文本中，假设输入的数据有d维。并且在以下的数据空间中定义：在D-Stream中，我们将d维的空间S划分成密度网格。假设对于每一维，它的空间是Si，i=1,...,d被分为pi个部分。这样数据空间S被分成了个密度网格。每个密度网格g是由组成，我们将它表示为：一个数据记录可以映射到下面一个密度网格g(x):对于每个记录x,我们分给它一个密度系数，它随着时间递减。实际上，如果x在tc时刻到达，我们将它的时间戳定义成：T(x)=tc，这样它在时刻t的密度系数D(x,t)就是：任何网格的密度是经常变动的。然而，我们发现没有必要在每一个时刻去更新所有数据记录的密度值，而是，只有当一个数据点映射到那个网格时，我们去更新网格的密度。对于每个网格，当一个新的数据记录到达某个网格，且接收到需要记录的最后的数据记录时，我们才根据下面的结论去更新网格的密度。命题3.1假设一个网格g在时刻tn接收到一个新的数据记录，假设g接收到最后的数据记录是在时刻tl(tntl)，那么g的密度可以按下面的方式更新：证明略。命题3.1节省了大量的计算时间。原本在每个时间间隔更新所有网格需要计算时间。相反的是，利用命题3.1我们只用的运行时间就可以更新一个网格。这种效率的增加是非常明显的，因为网格数目N的数目是巨大的。而且，命题3.1节省了内存空间。我们发现在一个网格中，我们没有必要去保存时间戳和密度值。相反的，对于每个网格，按一下定义的方式存储一个特征向量。稍后解释该向量中的每一项。命题3.2（特征向量）一个网格g的特征向量是一个五元组：其中，tg是g更新的最后时间，tm是g作为松散（稀疏）网格从grid_list中移除的最后时间，D是网格最后更新后的密度，label是网格的类（簇）标签，status={SPORADIC,NORMAL}是一个用来移除松散网格的标签，3.2基于密度的网格簇我们现在需要决定如何基于密度信息得到簇。我们的方法是基于以下的观察：命题3.2.让从时刻0到时刻t到达的所有数据记录成为一个集合。我们有：证明略。命题3.2表明系统中所有数据记录密度的总和永远不会超过。由于存在个网格，因此每个网格的平均密度不会超过。有这个观察得到以下的定义：在时刻t，对一个网格g，如果有我们称它为稠密网格。其中，Cm1是一个控制阈值的参数。比如，我们设定Cm=3。我们要求NCm，因为D(g,t)不能超过。在时刻t，对一个网格g，如果有我们称它为稀疏网格。其中，0Cl1。比如，我们设定Cl=0.8。在时刻t，对一个网格g，如果有我们称它为过渡网格。在多维空间，为了形成簇，我们考虑连接各个邻接的网格，我们按以下定义：定义3.3（邻接网格）考虑两个稠密网格和，如果存在，使得：那么在第k维空间，g1和g2就是邻接网格。表示为：g1~g2。定义3.4（网格组）如果对于任何两个网格G，存在一系列网格使得，那么密度网格的一个集合就是一个网格组。定义3.5（内部网格和外部网格）考虑到一个网格组G以及一个网格，假如，如果g在每一个维度存在邻接网格。那么g就是G中的一个内部网格。否则g就是G中的一个外部网格。现在我们准备定义如何基于网格的密度形成簇。定义3.6（网格簇）如果G内部每一个网格都是稠密网格而每个外部网格或者是一个稠密网格或者是一个过渡网格，那么G就是一个网格簇。直观地，一个网格簇就是一个连接的网格组，它比它周围的网格密度要大。注意到我们总是尝试在任何可能的时候合并簇，因此这样会导致簇被松散的网格所包围。4D-Stream算法的组成我们将在图1描述了算法D-Stream的主要部分。对于每一个新的数据记录x，我们将它映射到一个网格g，然后利用（5）来更新g的密度（图1中5-8行）。然后，我们周期性的（每隔gap时间）形成簇以及移除稀疏网格。下面我们描述确定gap的策略，管理活动网格的列表（list）以及产生簇。4.1网格检测以及时间间隔gap为了挖掘数据流的动态特征，我们在部分3开发的密度网格方案会逐渐地使得每个数据记录和网格的密度变小。如果一个稠密网格长期不接收一个新的数据，它可能会降级成为一个过渡网格或者一个稀疏网格。另一方面，如果一个稀疏网格接受一些新的数据记录，它可以升级成为一个过渡网格或者稠密网格。因此，经过一个时间周期后，每个网格的密度应该被重新检查，簇也要调整。一个关键的决定是确定检查网格的时间间隔的长度。我们发现这个时间间隔gap不能太大也不能太小。如果gap太大，数据流的动态变化不能够被很好地识别出来。如果gap太小，会导致在离线部分频繁地计算从而增加了负载。当这种计算负载过重，离线部分的处理速度可能不能匹配数据流输入的速度。我们提出以下的策略来确定gap值的合适大小。我们认为使一个稠密网格降级成为稀疏网格所需的的最少时间与使一个稀疏网格成为一个稠密网格所需的时间差不多。为了确保检查除足够频繁地去监测任何网格的密度变化，我们将gap设定为这些最小时间的中的最小值。命题4.1对任何稠密网格g，从稠密网格成为一个稀疏网格所需的最少时间是：证明略。命题4.2对任何稀疏网格g，从稀疏网格成为一个稠密网格所需的最少时间是：证明略。基于以上两个命题，我们选择足够小的gap，这样可以识别一个网格从稠密变为稀疏的任何变化，或者从稀疏变为稠密（的任何变化）。因此，在D-Stream中我们设定：4.2检测以及移除稀疏网格针对基于密度的方案一个严重挑战是大量的网格，尤其是高维数据。比如，如果每一个维度被分为20个部分，那么将有20^d（指数级）个可能的网格。一个关键的观察是空间中的大部分网格是空的或者只接收数据不是很频繁。在我们的实现方法中，我们只为那些非空的网格分配内存用来存储特征向量，这可以形成一个非常小的网格子空间。不幸的是，实际上，由于在数据错误中形成的离群点数据，导致在聚类过程中不断地增加处理非空网格的时间，这个方法的效率不是足够高。由于这些网格包含非常少的数据，我们称它为稀疏网格。由于大量的数据流高速地到达而且运行很长时间，这样使得稀疏网格不断累积，它们的数目会变得非常巨大，最终导致系统运行越来越慢。因此我们有必要周期性地检测和移除这样的稀疏网格。这在图1中的D-Stream算法中的13行描述。那些的网格代表稀疏网格。然而，有两种原因会导致一个网格的密度会小于Dl。第一个原因是它接收到非常少的数据，第二个原因是那个网格虽然在过去时间接收到许多数据但是由于受衰减因子的影响它的密度不断变小。只有前面那个原因导致的稀疏网格才是真的，需要移除。有后者原因导致的稀疏网格不应该被移除，因为它包含了许多数据，而且它经常升级，可能会成为过渡网格或者稠密网格。通过大量的实验，我们发现由于后者原因从而导致错误地移除这些网格会严重地恶化聚类的质量。我们定义了一个密度阈值函数来区分这两种不同类别的稀疏网格。定义4.1（密度阈值函数）假设一个网格g最后的更新时间是tg，那么在时刻t（ttg），密度阈值函数是：命题4.3函数具有以下一些性质：证明略。我们从所有稀疏网格中用检测出松散的网格。在图1中13行的周期性检测中，在时刻t，如果满足以下条件，我们判断那个稀疏网格是一个松散网格。注意tm和tg在是特征向量中存储。在D-Stream中，我们维护一个grid_list，它包括那些考虑用来作聚类分析的网格。grid_list使用可以解决冲突的双链表结构的哈希表实现。哈希表运行检索、更新以及删除。当将每一个网格联系到一个特征向量的入口，哈希表的关键词就相当于一个网格。我们使用下面的规则从grid_list删除松散网格。(D1)在图1中的13行