有效的动态聚类

Question

我有一组来自单位间隔的数据点（即具有数值值的一维数据集）。我在线收到一些其他数据点，此外，某些数据点的值可能会动态变化。我正在寻找一种理想的聚类算法，可以有效地处理这些问题。

我知道 顺序K-均值聚类 应对新实例的添加，我想通过次要修改，它可以与动态实例值一起使用（即首先从相应的群集中获取修改后的实例，然后更新集群的平均值，最后给出修改后的实例作为输入该算法是添加了看不见的实例）。

我关注的是使用K-均值算法的是，需要提供集群数量作为输入。我知道他们在时间和空间复杂性中击败了其他聚类算法（气体，MST，分层方法等）。老实说，我不确定，但是也许我可以摆脱上述算法之一。即使是我的数据集相对较大，单个维度的存在也使我感到奇怪。

更具体地说，我的典型测试案例将包含约10K-200K 1维数据点。我想最好在一秒钟以下完成聚类。假定值的动态变化是平滑的，即相对较小。因此，能够使用现有的解决方案（即在更改值或添加新值时能够继续在现有的解决方案上进行聚类）是高度首选的。

总而言之：

您能想到一种算法，该算法将在计算效率和簇WRT的准确性之间提供甜蜜的位置。上面定义的问题？

K均值算法是否有一些不错的启发式方法可以自动计算事先计算K的值？

Answer 1

我认为在您的情况下（具有单一维度），层次聚类将更加有效。根据您的任务，您可以实施这样的事情：

具有n个数据点d_一世 具有其1维值x_一世:

1. 根据其x对数据点进行排序_一世 价值。
2. 计算相邻数据点（N-1距离）之间的距离。每个距离必须分配一对原始数据点（D_一世, ，d_j).
3. 按降序排序以生成数据点对列表（D_一世, ，d_j），从最接近的开始。
4. 迭代统一数据点（D_一世, ，d_j）进入簇，从列表的开始（最接近的对）开始。 （取决于D的当前状态_一世 和d_j, ，将它们团结起来的意思是：（a）为两个未簇的数据点创建新群集，（b）在现有群集中添加一个数据标记，以及（c）团结两个簇。
5. 如果距离超过一定的阈值，请停止团结。
6. 为未进入簇的数据点创建单例群集。

该算法实现 单个链接 聚类。可以轻松地调谐以实现平均链接。 完整的链接 效率较低，但也许更容易的人会根据您的数据和任务提供良好的结果。

我相信，对于200k数据点，如果您使用适当的数据结构进行上述操作，则必须在第二以下。

Answer 2

尝试使用HDBSCAN，即使它是一种层次结构方法，也可能会更有效。我在多维数据集上运行它，比200k稍长一点，并且运行不到一分钟。警告是它可能产生的簇数。如果它们太多，您可能想坚持使用分区方法。