algorithm - 数聚类/划分算法

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-means 算法，因为标准算法不能保证尊重我的百分比和/或相同值不能出现在多个集群/分区中的要求。

那么，这种聚类有算法吗？

Answer 1

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

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