近年来，关于流式数据的聚类分析和规律发现研究已经成为一个新的研究热点。本节将从不同的角度对流式数据的聚类现状进行综述。

如图1.2 所示，传统的静态数据库的聚类算法可以划分为：划分方法、层次方法、基于密度的方法、基于网格的方法、基于概率模型的聚类、聚类高维数据、聚类图和网络数据、基于约束的聚类等。本书将从单流式数据聚类、多流式数据相关性分析、高维数据聚类、图聚类等方面进行归纳。

（1）单流式数据聚类

单流式数据聚类以单一数据统计点的流式数据对研究对象，只考虑该条流式数据的变化规律及特点。

图1.2　流式数据聚类算法发展

考虑到流式数据的时间特性，流式数据环境中的聚类算法又可分为单遍扫描的聚类算法和基于时间演化的进化聚类算法。Guha 等［88］提出利用k 中值算法进行流式数据聚类的严格的一次访问算法。Charikar等［89］提出了一种空间复杂度为O（kpoly log N）的流式数据k 中值算法，改进了由于层次增多而导致的近似性下降问题。O’Challaghan 等［90］提出了STREAM 算法以及LOCALSEARCH 子处理过程进行高性能流式数据聚类。

假设数据流的底层模型不断变化，进化数据流的聚类分析方法是将流式数据的行为看作动态变化的过程，在不同的窗口内抽取出不同的聚类模型，以适应随时间不断变化的流式数据的聚类需求。为了能在任意时刻给出当前流式数据的聚类结果，Aggarwal 等［91］提出了CluStream 算法，解决了STREAM 算法没有考虑流式数据演变的因素。CluStream 算法采用金字塔时间框架，包含在线微聚类和离线宏聚类两部分。针对高维连续属性流式数据，Aggarwal 等［92］提出了基于投影的流式数据聚类算法HPStream。Cao 等［93］提出了基于密度的方式发现进化流式数据中簇结构的DenStream 算法。DenStream 算法将具有遗忘特性的微聚类与经典的DBSCAN 算法［94］相结合，采用了CluStream 的两阶段处理框架，把聚类分析的过程分为联机和脱机两部分。Lühr 等［95］提出了基于稀疏图的RepStream 算法，其思想是采用代表性聚类点来增量地处理新增数据。

与流式数据聚类相近的另一概念进化聚类是由Chakrabarti 等［96］提出，该算法的目标是使得第t 步数据上的聚类与第t－1 步数据上的聚类尽量相似，并给出了基于k 均值和层次聚类的进化聚类版本。Chi 等［97］利用类似文献［96］的思想，对谱聚类进行扩展，提出了两种进化谱聚类算法。Tang 等［98］沿用演化谱聚类的思想，将其推广到多关系数据聚类的问题，以处理动态网络中的社团发现等问题。Wang 等［99］提出了聚类进化数据的ECKF 框架，该框架基于低秩矩阵逼近的方法［100⁃101］来处理随时间不断演化的数据的聚类问题。将t 时刻样本的聚类指示矩阵作用于t－1 时刻，逼近t－1 时刻数据矩阵的误差作为时间损失项。关于进化聚类算法的研究重点是相邻时间段聚类过渡的平滑性［102⁃105］，其主要应用于社会网络中的社团发现及其演化分析。

（2）多流式数据相关性分析

随着信息技术的广泛，将流式数据作为聚类对象，研究多流式数据环境中不同流式数据之间可能存在的某种耦合关系已经广泛展开。多流式数据聚类以多个数据统计点的流式数据为研究对象，同时考虑两个或者两个以上流式数据之间的相似程度。

针对实际应用中巨大的流式数据数量，StatStream［106］算法利用滑动窗口模型，将每一个滑动窗口分为若干基本窗口，通过离散傅里叶变换将基本窗口内的原始流序列进行约减。

SPIRIT 算法［107］可在多个流式数据中发现相关性并探测隐藏变量，每一个隐藏变量都代表多条流式数据的某种趋势。对每个变量均赋予一定的权重，作为对整个流式数据的贡献大小，通过PCA（Principle Component Analysis，PCA）方法动态地更新隐藏变量并计算其权重，进而基于流式数据的相关性分析进行预测。

Yang 等［108］将多流式数据间的聚类问题定义为维度随时间不断增长数据点的聚类问题，提出了一种增量聚类算法用于将多条流式数据聚类为多个不同的簇。

根据用户的要求，Dai 等［109］提出了一个多数据流的进化聚类框架COD。COD 中以动态地对多条流式数据进行聚类，并可支持多种数据处理的请求，包括在线概要维护与离线生成聚类结果部分，对多条流式数据同时进行单遍扫描提取统计信息，基于小波和回归分析的概要统计结构为多窗口的聚类挖掘请求提供支持。

Beringer 等［110］将每个流式数据的一个一定长度的滑动窗口中的数据保存下来，采用离散傅里叶变换（Discrete Fourier Transform，DFT）的方法对流式数据进行压缩。Yeh 等［111］提出了基于多流式数据关联关系的多进化流式数据聚类框架COMET⁃CORE。该框架采用分段线性近似（Piecewise Linear Approximation，PLA）对流式数据进行压缩，并以此计算流式数据之间的相关系数，进而度量流式数据相互之间的相似性。

（3）高维数据聚类(www.daowen.com)

针对流式数据环境中的高维数据聚类问题，基于投影聚类的思想，Aggarwal 等［92］提出了应用于高维流式数据聚类的HPStream 算法。Agrawal 等［112］使用DFT 将原始时间序列转换为少数几个离散傅里叶系数，在维数约简的基础上使用欧氏距离进行序列的聚类研究。与此类似，通过离散小波变换进行约简之后聚类［113］。

（4）图聚类

在实际应用中，如蛋白质网络、Internet 的物理层网络、交通物理网络等是相对静态的网络。例如，交通网络、社交网络等网络的拓扑结构随着时间不断变化。自2005 年起，对网络的社团结构发现的研究成为研究者们关注的热点问题［114⁃118］。

为分析不同时刻网络的演化情况，可将动态网络社团发现的方法分为两类：增量聚类和进化聚类。

1）增量聚类

增量聚类［95，104］的思想是基于相邻时刻动态网络变化不大的特点，对相邻时刻网络进行比较，在上一时刻网络社团聚类结果的基础上计算当前时刻网络社团结构，有效降低算法的时间复杂度，且保证相邻时刻网络社团结构具有较好一致性，在多个时间点上进行增量式分析。

根据时间尺度的不同，增量聚类可分为在一个时间点的聚类分析和在多个时间点的聚类分析两类。在一个时间点与流式数据聚类类似，为了在有限的存储空间上实现对快速产生的流式数据的有效聚类，只对聚类数据顺序考察一遍。鉴于单个时间点聚类的局限性，为能够更准确地反映实际情况，需要对某一个对象在多个时间点上进行聚类分析。

受启发于牛顿万有引力的思想，Yang 等［118］在复杂网络中定义了节点间的排斥力和吸引力。采用近似迭代方法计算复杂网络中节点间相互作用力［118］，通过多次迭代，使得社团内部节点之间的引力越来越大，社团间的节点将凝聚成不同的斥力极性。当某条处于社团间边的斥力经过多次迭代后超过某个阈值，社团间的边将会断裂，分裂为两个社团。

为了对动态图进行分割，Sun 等［119］基于信息理论的方法提出GraphScope 框架。该框架使用二分图对整个网络流式数据划分成S 个片段，使得每个划分片段中的图具有更多的相似性，不同划分片段中的图具有更大的差异性。GraphScope 框架将每个片段内的所有图结构及其社团结构进行编码，应用局部搜索的方法，求得近似最优解。

Ning 等［104］提出了一种增量谱聚类的动态网络社团结构发现方法，通过增量的方式迭代更新网络的谱系统，从而获取变化后的社团结构。考虑到网络的随机性和突发性，Tong 等［120］提出了Colibri 方法来处理静态和动态的网络分析。

2）进化聚类

依据动态网络变化缓慢的基本特性Chakrabarti 等［96］提出了进化聚类的概念，该算法的目标是使得每个时刻最优的聚类结果使快照质量最大、历史开销最小。利用快照质量衡量当前聚类结果Ct在当前网络拓扑Gt下的聚类质量，利用历史开销衡量当前时刻聚类结果Ct与前一时刻聚类结果Ct－1的差异性［96］。框架的具体描述为

Chi 等［97］提出了基于谱聚类的保持聚类质量（Preserving Cluster Quality，PCQ）和保持聚类成员（Preserving Clustering Membership，PCM）的框架。其中，PCQ 算法将历史数据和历史的聚类结果应用于当前时刻的聚类中，如式（1.1）所示。

针对同一个网络中存在异构结点，并且异构结点之间可能存在某种联系等问题，Tang 等［121］提出基于谱聚类的进化聚类框架。为了降低噪声数据对结果的影响，提高算法稳定性，Lin 等［103］应用贝叶斯统计学中的方法提出FacetNet 框架。与一般的进化聚类算法的不同在于：FacetNet框架中不仅使得社团进化，同时利用社团的进化反过来调整网络社团的结构。

本书的后续工作将通过基于CPS 的交通流式数据的特点，结合流式数据聚类分析的研究现状，研究适合于交通流式数据的聚类分析和演化趋势发现方法。