1.传统的数据聚类算法

传统静态的数据聚类算法对于后期流式数据聚类算法的进一步研究具有相当重要的现实意义，很多流式数据聚类算法都是一些常见的经典聚类算法的变形。聚类算法一般可以分为三类，分别是基于划分的方法、基于层次的方法和基于密度的方法。

基于划分的方法主要有K-means、K-medions、PAM等聚类算法；基于层次的方法主要有CURE、ROCK和BIRCH；基于密度的方法主要有DBSCAN和STDBSCAN；基于网格的方法主要有STING、CLIQUE等。相关对比见表4.1。

表4.1　聚类算法比较

2.流式数据聚类算法

在流式数据模型提出后，流式数据挖掘便成为热点研究内容。在流式数据挖掘中，算法短时间内需要处理大量数据，同时，随着时间的推移，流式数据是不断演化的，因此传统数据挖掘聚类算法先存储后计算的方式并不适合流式数据聚类算法。

流式数据聚类算法有以下两个特点。

（1）从流式数据中数据到达速度的角度来看，流式数据聚类算法计算速度很快，对时间复杂度要求较高，以至于会实时得到计算结果。

（2）从流式数据中数据数量角度来看，持续、无限的流式数据中数据量巨大，对于容量有限的存储设备，流式数据聚类算法会进行抽样或者概要处理，而不是对数据进行持久化的存储，相应地，数据也只被算法处理一次。

与传统的静态数据聚类算法相比，流式数据聚类算法有很大的不同。首先，类簇的个数会随着流式数据的演化而变化，因此流式数据聚类算法无法提前假设类簇数量。其次，流式数据中的数据分布通常是随机、无规则的，相应地，类簇的形状也是不规则的，因此流式数据算法要具有能够挖掘任意形状的聚类能力。最后，在实际生产生活当中，受相关因素影响，比如通信故障、电池电量不足、信号屏蔽等，流式数据中不可避免地会夹杂一些随机的噪声数据，这就要求流式数据聚类算法可以分辨、处理流式数据中的噪声数据。

尽管与传统聚类算法存在很大不同，但流式数据聚类算法确实是在传统数据聚类算法基础上演化发展而来的，常见的流式数据聚类算法与其相对应的传统聚类算法如图4.2所示。

图4.2　流式数据的算法的演化与发展

由于流式数据具有海量、高维、实时等特点，流式数据聚类算法比传统的聚类算法要复杂许多。目前影响比较大的流式数据聚类算法有以下几种。

1）Stream算法

Stream算法近似聚类算法，是一种单遍扫描同时基于k中位数的流式数据聚类算法，是以k中位数问题开发的。k中位数问题的解决目标是使数据集合中的点与它相应的类簇的中心点之间距离误差平方和最小。由于每个桶较小，Stream在工作时把处理的m个桶中的流式数据，都放在内存中。对于每个桶，Stream把每个桶的点分成k个簇。然后，仅通过保留k个中心信息来汇总桶的信息。一旦收集到足够的中心，加权中心将再次聚类，以产生另外o（k）个簇中心集合。如此重复，以便在每个层最多保留m个点。Stream算法源于k中位数聚类，使用有限时间和空间可得到不错的聚类效果。然而它没有考虑数据的演变和时间粒度的变化。聚类可能受控于旧的、过期的流式数据，不能反映流式数据的动态性，与实际应用中流式数据应该是随时间而变化的特点不符。(www.daowen.com)

2）CluStream流式数据聚类算法

CluStream是一种经典的流式数据聚类框架，它的相关思想被许多算法学习和借鉴。该算法提出了微簇（Micro-clusters）和金字塔时间结构（Pyramidal Time Frame）两个全新概念，采取与传统聚类算法不同的思想将聚类过程分为在线和离线两个部分。当流式数据到达时，在线部分（即微聚类）根据当前采集的数据信息实时更新微簇中的由系统持续维护的概要信息，同时根据金字塔时间结构定义的时间粒度保存相应时刻全部微簇的概要信息；由于在线部分保存了不同时间范围和时间粒度的微簇信息，因此离线部分根据用户输入的参数，可以使用在线部分保存的概要信息对任意时间范围内的数据进行聚类计算，从而实现对流式数据演化过程进行聚类分析。CluStream计算框架如图4.3所示。

图4.3　CluStream计算框架

3）HPStream流式数据聚类算法

传统聚类算法解决高维数据问题时通常使用投影技术，HPStream流式数据聚类算法正是采用投影技术来解决高维流式数据聚类问题的。和传统聚类算法相似，该算法将流式数据中的高维数据对不同维度进行投影实现数据的增量更新，提高了高维流式数据的聚类质量。同时针对历史数据，该算法使用了指数衰减的方式为响应的数据指定一个权重，流式数据中越早到达的数据其权重越小，将历史数据将聚类结果的影响控制在合理的范围。同时，该算法也存在着相应参数较难确定、无法对任意形状类簇进行聚类的缺点。

4）DenStream流式数据聚类算法

DenStream流式数据聚类算法从基于密度的DBSCAN数据聚类算法的思想上发展而来，同时借鉴了CluStream算法中提出的两阶段计算框架的思想，提出了核心微聚类簇、微聚类簇和潜在微聚类簇的概念，将流式数据聚类分为在线和离线两个过程，可以较好地识别处理离群点，发现流式数据中任意形状的类簇。针对算法空间复杂度问题，该算法设计了良好的删除策略，降低了内存使用量；在算法的时间复杂度上，由于该算法对时间特性统计和密度计算的依赖，其时间复杂度较高，同时该算法对密度参数较为敏感也影响了聚类质量。

5）D-Stream流式数据聚类算法

D-Stream流式数据聚类算法从网格密度聚类算法发展而来，因此可以较好地识别任意形状的类簇。与CluStream两阶段计算框架相似，该算法在线部分将到达的数据元素映射到划分好的某一网格单元中，离线部分对网格中数据元素密度进行计算得到相应的类簇。针对流式数据动态变化的特点，D-Stream算法使用密度衰减技术实时、灵活、高效地调整簇，从而使流式数据的高速变化也可以被算法实时捕获。通过合理地移除稀疏网格，提高了算法的计算效率，降低了资源使用率。和其他算法不同，D-Stream算法在效率、实时性以及提高高速流式数据聚类质量方面有着较大优势。

6）流式数据聚类算法对比

流式数据聚类算法由传统数据聚类算法演化而来，主要流式数据聚类算法对比如表4.2所示。

表4.2　流式数据聚类算法对比

续表