0

我需要从输入的整数数组中导出整数簇，以使簇内的变化最小化。（数组中的整数或数据值对应城市间行驶的16辆汽车的油耗，最后我会根据数据值的聚类，从这16辆汽车中推导出4个聚类。）

约束：元素的数量总是16，没有。簇的数量为 4，簇的大小为 4。

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

但是，我卡住的地方如下：数组中的数据随时间变化。基本上，我需要每 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)
4

1 回答 1

2

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

您是否知道大多数 QuickSort 实现回退到小数组的插入排序？因为它对小型阵列做得相当好，而且开销很小。

所有的复杂性讨论都只针对非常大的数据集。事实上，它们仅适用于无限大小的数据。在达到无穷大之前，复杂度更高的简单算法可能仍然表现更好。对于 n < 10，二次插入排序通常优于 O(n log n) 排序。

但是，k-means 对您帮助不大。

  1. 您的数据是一维的。甚至不要费心去看多维方法，它们的性能会比适当的一维方法差（可以利用数据可以排序）
  2. 如果您想要保证运行时间，那么可能有很多迭代的 k-means 是完全不受控制的。
  3. 您不能轻松地将诸如 4-cars 规则之类的约束添加到 k-means

我相信您的任务的解决方案（因为数据是一维的并且您添加的约束）是：

Sort the integers
Divide the sorted list into k even-sized groups
于 2012-07-16T05:59:43.070 回答