在 R/python 中将向量分割成 n 个“相似”段

Question

如果我有一个由 m 实数组成的向量，如何将向量分成 n 段，使得每个段都包含“相似”值，并且所有值都在原始向量中具有相邻位置？

这里的“相似”可以指最小化每个分段中数字的变异性。所以，例如如果我有向量：

[4, 4.2, 4, 18, 1, 2, 0.98, 15, 17]

，并且我想将其分成 4 个（为了示例而随机选择）段，我最终会得到这些段：

{[4, 4.2, 4], [18], [1, 2, 0.98],[15, 17]}

。

值得注意的是，相似性不必定义为最小变异性，但这对我来说才有意义。

所以我的问题是：

1. 有没有一种算法，给定一个大小为 m 的向量，以及将该向量分割成的段数 n（其中 n ≤ m），可以找到最佳的 m 段，使得每个段部分包含“相似”数字？这里的目标可能是最小化每个分段的方差之和。
2. 是否有一种算法可以执行上述操作，但不将段数作为参数，而是可以找到最佳段数及其定位？ （在我看来，最佳的段数就是 m 个段，因为每个段的可变性为 0，因此必须有某种与添加新段相关的成本函数）。

我理想地希望得到 R 或 python 中的答案，但是，我主要只对此类算法的逻辑/名称感兴趣。

Answer 1

套餐{反色欲}

将元素池划分为簇（或反簇），目标是实现簇间的高相似性和簇内的高异质性。

...并提供方差作为相似性度量之一。

在您的示例中，您可以：

创建您的矢量

v

...

v <- c(4, 4.2, 4, 18, 1, 2, 0.98, 15, 17)

...并检索组索引，例如4 组相似方差：

library(anticlust)
group <- anticlustering(v, K = 4, objective = 'variance')

结果，整理一些数据：

library(dplyr)
data.frame(v, group) |>
  mutate(var = var(v), .by = group) |>
  arrange(group)

      v group      var
1  4.00     1  76.0000
2 18.00     1  76.0000
3  2.00     1  76.0000
4  4.20     2   0.0200
5  4.00     2   0.0200
6  1.00     3  98.0000
7 15.00     3  98.0000
8  0.98     4 128.3202
9 17.00     4 128.3202

组（段）2 仍然与其他组有很大偏差；我想这已经是最好的了，因为整体简历很大，而且只有九个元素需要移动。