CluStream 是一种基于用户指定的在线聚类查询对不断发展的数据流进行聚类的算法。它将聚类过程分为在线和离线组件。
在线组件使用微集群对数据流的汇总统计进行计算和存储，并对微集群进行增量在线计算和维护。离线组件使用基于倾斜时间框架模型的存储的汇总统计数据进行宏观聚类并回答各种用户问题。
集群演化数据流基于历史和当前流数据信息，采用倾斜时间框架模型（如渐进对数模型），根据新近度以不同的粒度级别存储一组微集群的快照。
这里的直觉是，与较早的事件相比，较新的事件将需要更多信息。存储的信息可用于处理与历史相关的、特定于用户的聚类查询。CluStream 中的微集群被定义为集群特征。
CluStream 扩展了 BIRCH 中开发的聚类特征的概念，以包括时间域。作为聚类特征的时间扩展，一组 d 维点的微聚类，X 1 , . . . , X n , 带有时间戳, T 1 ,...,T n , 被定义为 (2d +3) 元组 (CF2 x ,CF1 x ,CF2 t , CF1 t , n)，其中 CF2 x和 CF1 x是d 维向量，而 CF2 t、CF1 t和 n 是标量。CF2 x维护每维数据值的平方和，即$\sum_{i=1}^{n}{X_{i}}^{2}$
类似地，对于每个维度，数据值的总和保存在 CF1 x 中。从统计的角度来看，CF2 x和CF1 x 分别代表数据的二阶矩和一阶矩。时间戳的平方和保存在 CF2 t 中。时间戳的总和保存在 CF1 t 中。最后，微集群中的数据点数量保持在 n 中。
聚类特征具有加法和减法特性，这使得它们对数据流聚类分析非常有用。例如，可以通过添加各自的聚类特征来合并两个微聚类。此外，可以在不使用大量内存的情况下维护大量微集群。这些微集群的快照根据倾斜的时间框架存储在关键时间点。
在线微集群处理分为统计数据收集和微集群更新两个阶段。在第一阶段，总共维护了 q 个微集群，M 1 ,..., M q，其中 q 通常显着大于自然集群的数量，并由可用内存量决定。
在第二阶段，更新微集群。每个新数据点都会添加到现有集群或新集群中。它可以决定是否需要一个新的集群，定义每个集群的最大边界。