什么是STREAM？

STREAM 是一种针对 k-均值问题的单遍常数因子近似算法。k-均值问题是将 N 个数据点聚类成 k 个簇或组，使得点与其所属簇中心之间的平方误差和 (SSQ) 最小化。其思想是将相似的点分配到同一个簇中，而这些点与其他簇中的点不同。

在流数据模型中，数据点只能查看一次，并且内存和时间有限。它可以实现高质量的聚类，STREAM 算法以 m 个点的桶（或批次）处理数据流，每个桶都适合主内存。

对于每个桶 b_i，STREAM 将桶中的点聚类成 k 个簇。然后，它通过仅保留关于 k 个中心的信息来总结桶信息，每个簇中心都按分配给其簇的点数加权。

然后，STREAM 丢弃点，只保留中心信息。由于已经收集了足够的中心，因此对加权中心进行聚类以生成另一组 O(k) 个簇中心。重复此过程，以便在每一层最多保留 m 个点。这种方法产生了一种单遍、O(kN) 时间、O(N^ε) 空间（对于某个常数 ε < 1）的常数因子近似算法，用于数据流 k-均值。

STREAM 改变了具有确定区域和时间的质量 k-均值聚类。但是，它既没有处理记录的演变也没有处理时间粒度。聚类可能会被流中较旧、过时的数据所支配。簇的特征会随着评估它们的时刻和测量它们的时间范围而变化。

例如，用户可能需要测试上周、上个月或去年出现的集群。这些可能是不同的。因此，数据流聚类算法还必须支持以交互方式计算用户定义时间段内集群的灵活性。

CluStream 是一种基于用户指定的在线聚类查询的演变数据流聚类算法。它将聚类过程分为在线和离线组件。

在线组件使用微簇计算并存储关于数据流的汇总统计信息，并执行微簇的增量在线计算和维护。离线组件进行宏观聚类，并使用保存的汇总统计信息解决多个用户问题，这取决于倾斜时间框架模型。

基于历史和当前流数据信息对簇演变数据流进行聚类，采用倾斜时间框架模型（如渐进对数模型），根据数据的近期性存储不同粒度级别的一组微簇的快照。

Ginni

更新于：2022年2月17日

328 次浏览

启动您的职业生涯

完成课程获得认证

开始学习