数字聚类/划分算法

Question

我有一个有序的一维数字数组。数组长度和数组中数字的值都是任意的。我想根据数值将数组划分为 k 个分区，例如，假设我想要 4 个分区，分布为 30% / 30% / 20% / 20%，即首先​​是前 30% 的值，接下来的 30%之后，等等。我可以选择 k 和分布的百分比。此外，如果相同的数字在数组中出现多次，则不应将其包含在两个不同的分区中。这意味着上面的分配百分比并不严格，而是“目标”或“起点”（如果您愿意）。

例如，假设我的数组是 ar = [1, 5, 5, 6, 7, 8, 8, 8, 8, 8]。

我选择 k = 4，数字应按百分比 pA = pB = pC = pD = 25% 分配到分区 A、B、C 和 D。

鉴于我上面给出的约束，生成的分区应该是：

A = [1] B = [5, 5] C = [6, 7] D = [8, 8, 8, 8, 8]

结果（实现/修正）百分比pcA = 10%，pcB = 20%，pcC = 20%，pcD = 50%

在我看来，我需要一个修改后的 k 均值算法，因为标准算法不能保证遵守我的百分比和/或相同值不能出现在多个集群/分区中的要求。

那么，有没有一种算法可以实现这种聚类呢？

Answer 1

聚类算法用于多维数据。对于一维数据，您应该简单地使用排序算法。

对数据进行排序。然后按照您的示例，从数组底部到顶部对数据集进行线性分区。

Answer 2

这是一个动态规划解决方案，它找到一个分区，使零件尺寸误差的平方和最小。因此，在 [1, 5, 5, 6, 7, 8, 8, 8, 8, 8] 的示例中，您需要大小为 (2.5, 2.5, 2.5, 2.5) 的部分，并且此代码给出的结果是 ( 9.0, (1, 2, 2, 5))。这意味着选择的分区大小为 1、2、2 和 5，总误差为 9 = (2.5-1)^2 + (2.5-2)^2 + (2.5-2)^2 + (2.5- 5)^2。

def partitions(a, i, sizes, cache):
    """Find a least-cost partition of a[i:].

    The ideal sizes of the partitions are stored in the tuple 'sizes'
    and cache is used to memoize previously calculated results.
    """
    key = (i, sizes)
    if key in cache: return cache[key]
    if len(sizes) == 1:
        segment = len(a) - i
        result = (segment - sizes[0]) ** 2, (segment,)
        cache[key] = result
        return result
    best_cost, best_partition = None, None
    for j in xrange(len(a) - i + 1):
        if 0 < j < len(a) - i and a[i + j - 1] == a[i + j]:
            # Avoid breaking a run of one number.
            continue
        bc, bp = partitions(a, i + j, sizes[1:], cache)
        c = (j - sizes[0]) ** 2 + bc
        if best_cost is None or c < best_cost:
            best_cost = c
            best_partition = (j,) + bp
    cache[key] = (best_cost, best_partition)
    return cache[key]


ar = [1, 5, 5, 6, 7, 8, 8, 8, 8, 8]
sizes = (len(ar) * 0.25,) * 4
print partitions(ar, 0, (2.5, 2.5, 2.5, 2.5), {})

Answer 3

简单的方法是这样的：

假设 p1...pk 是分区的百分比 (p1+...+pk = 1)

假设数组中有 N 个元素

初始边界（其中有 k+1 个，包括数组结束，因为你有 k 个分区）是：
0、p1*N、(p1+p2)*N、...、N（需要进行一些舍入操作）。

为了移动边界，您可以查看边界两侧的两个数组元素（对于可以移动的 k-1 个边界）。如果两个元素相等，则需要移动到边界（左侧或右侧），至少直到满足约束为止。一种简单的方法是从左侧开始并进行最小的调整（只需将约束调整到导致移动最少的一侧，并且不要进一步移动边界）。

但该算法并未覆盖整个分区空间。它只是给你一种解决方案。为了找到最佳解决方案，您需要对整个分区空间进行强力搜索，并进行某种修剪（例如动态编程，您可以记住初始数组的子数组的最佳分区）。