一个在线数据聚类实例

Question

我需要从输入的整数数组中导出整数簇，使集群中的变化最小化。(数组中的整数或数据值对应于16辆在城市之间行驶的汽车的气体使用量。最后，我将根据数据值的聚类，从16辆汽车派生出4个集群。)

约束:元素的数量总是16，否。集群的大小是4，集群的大小是4。

我计划做的一个简单方法是对输入数组进行排序，然后将它们分成4个组，如下所示。我认为我也可以使用k-均值聚类。

但是，我坚持的地方如下:数组中的数据随着时间的推移而变化。基本上，我需要每1秒对数组进行监视，并对它们进行重新组合/重新聚类，以便将集群中的变化最小化。此外，我需要满足上述约束。为此，我得到的一个想法是根据两个组的均值和变化选择两个组，并在组间移动数据值，以最小化组内的变化。但是，我不知道如何选择要在组之间移动的数据值，也不知道如何选择这些组。我不能在每一秒内对数组进行排序，因为我不能为每一秒提供NlogN。如果你能指导我想出一个简单的解决方案，那就太好了。

sorted `input array: (12 14 16 16 18 19 20 21 24 26 27 29 29 30 31 32)`

cluster-1: (12  14 16 16)
cluster-2: (18 19 20 21)
cluster-3: (24 26 27 29)
cluster-4:  (29 30 31 32) 

Answer 1

让我首先指出，对少数对象进行排序是非常快的。特别是当它们之前被排序时，“邪恶”气泡排序或插入排序通常是线性的。考虑到有多少地方的订单可能发生了变化！当数据适合CPU第一级缓存时，所有经典的复杂性讨论都不适用。

您知道大多数QuickSort实现都回到了插入排序的小数组中吗？因为它对小型数组做得相当好，而且开销也很小。

所有的复杂性讨论都是针对大型数据集的。事实上，它们只被证明是非常小的数据。在达到无穷大之前，一个复杂度较高的简单算法可能仍然会执行得更好。对于n< 10，二次插入排序往往优于O(n log )排序。

但这对你没有多大帮助。

1. 你的数据是一维的。不要费心去看多维方法，它们的性能会比正确的一维方法(这种方法可以利用数据可以被排序)更糟糕。
2. 如果您想要保证运行时，k-意指可能有许多迭代是完全不受控制的。
3. 您很难将约束(如4-car规则)添加到k-方法中。

我相信您的任务的解决方案(因为数据是一维的和您添加的约束)是：

Sort the integers
Divide the sorted list into k even-sized groups