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

Question

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

\n

这里的“相似”可以指最大限度地减少每个部分中数字的变异性。因此，例如，如果我有向量：[4, 4.2, 4, 18, 1, 2, 0.98, 15, 17]，并且我想将其分成 4 个（为了示例而随机选择）段，我最终会得到段：{[4, 4.2, 4], [18], [1, 2, 0.98],[15, 17]}。

\n

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

\n

所以我的问题是：

\n

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

\n

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

\n

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 组（段）仍然与其他组有很大偏差；我想这对于整体简历来说已经是最好的了，而且只有九个元素需要移动。

编辑

为了最大限度地减少组内方差，您可以使用Ward 方法进行聚类（v如上所述）：

data.frame(value = v,
           group = v |>
             dist() |>
             hclust(method = 'ward.D') |>
             cutree(4)
           ) |> 
  mutate(var = var(value), .by = group) |>
  arrange(group)

  value group        var
1  4.00     1 0.01333333
2  4.20     1 0.01333333
3  4.00     1 0.01333333
4 18.00     2 0.50000000
5 17.00     2 0.50000000
6  1.00     3 0.34013333
7  2.00     3 0.34013333
8  0.98     3 0.34013333
9 15.00     4         NA