什么是CluStream？

CluStream是一种基于用户指定的在线聚类查询对不断发展的数据流进行聚类的算法。它将聚类过程分为在线和离线两个部分。

在线组件使用微集群计算和存储关于数据流的汇总统计信息，并执行微集群的增量在线计算和维护。离线组件进行宏观聚类，并使用基于倾斜时间框架模型的存储汇总统计信息来回答各种用户问题。

该集群基于历史和当前流数据信息不断发展的数据流，采用倾斜时间框架模型（例如渐进对数模型），根据近期情况存储不同粒度级别的一组微集群的快照。

这里的直觉是，与较旧的事件相比，需要更多信息来处理较新的事件。存储的信息可用于处理与历史相关的、特定于用户的聚类查询。CluStream中的微集群定义为聚类特征。

CluStream扩展了在BIRCH中开发的聚类特征的概念，以包含时间域。作为聚类特征的时间扩展，对于一组d维点X₁, ..., X_n，带有时间戳T₁,...,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₁, ..., M_q，其中q通常远大于自然集群的数量，并由可用内存量决定。

在第二阶段，更新微集群。每个新的数据点都被添加到现有的集群或新的集群中。它可以决定是否需要一个新的集群，为每个集群定义一个最大边界。

Ginni

更新于：2021年11月25日

769 次浏览

开启您的职业生涯

完成课程获得认证

开始学习