Select 一个不相关的子集，受约束

Question

考虑一个相关矩阵 r，表示变量 1 到 10 之间的相关性：

r <- matrix(c(1, 0.61, 0.67, -0.14, 0.93, 0.77, 0.42, 0.61, 0.49, 0.97, 0.61, 
              1, 0.91, 0.26, 0.81, 0, 0.91, 0.67, -0.25, 0.66, 0.67, 0.91, 
              1, -0.15, 0.76, 0.24, 0.66, 0.78, -0.14, 0.63, -0.14, 0.26, -0.15, 
              1, 0.16, -0.56, 0.63, -0.31, -0.25, 0.11, 0.93, 0.81, 0.76, 0.16, 
              1, 0.51, 0.72, 0.61, 0.28, 0.97, 0.77, 0, 0.24, -0.56, 0.51, 
              1, -0.24, 0.34, 0.78, 0.65, 0.42, 0.91, 0.66, 0.63, 0.72, -0.24, 
              1, 0.41, -0.32, 0.57, 0.61, 0.67, 0.78, -0.31, 0.61, 0.34, 0.41, 
              1, -0.09, 0.53, 0.49, -0.25, -0.14, -0.25, 0.28, 0.78, -0.32, 
              -0.09, 1, 0.45, 0.97, 0.66, 0.63, 0.11, 0.97, 0.65, 0.57, 0.53, 
              0.45, 1), 10)

r 看起来像这样：

##        [,1]  [,2]  [,3]  [,4] [,5]  [,6]  [,7]  [,8]  [,9] [,10]
##  [1,]  1.00  0.61  0.67 -0.14 0.93  0.77  0.42  0.61  0.49  0.97
##  [2,]  0.61  1.00  0.91  0.26 0.81  0.00  0.91  0.67 -0.25  0.66
##  [3,]  0.67  0.91  1.00 -0.15 0.76  0.24  0.66  0.78 -0.14  0.63
##  [4,] -0.14  0.26 -0.15  1.00 0.16 -0.56  0.63 -0.31 -0.25  0.11
##  [5,]  0.93  0.81  0.76  0.16 1.00  0.51  0.72  0.61  0.28  0.97
##  [6,]  0.77  0.00  0.24 -0.56 0.51  1.00 -0.24  0.34  0.78  0.65
##  [7,]  0.42  0.91  0.66  0.63 0.72 -0.24  1.00  0.41 -0.32  0.57
##  [8,]  0.61  0.67  0.78 -0.31 0.61  0.34  0.41  1.00 -0.09  0.53
##  [9,]  0.49 -0.25 -0.14 -0.25 0.28  0.78 -0.32 -0.09  1.00  0.45
## [10,]  0.97  0.66  0.63  0.11 0.97  0.65  0.57  0.53  0.45  1.00

此外，每个变量都有一个特定的 "score"。对于变量 1 到 10，让我们分配分数 1:10.

score <- 1:10

我想要 select n 变量的子集，这些变量的相关性绝对值不大于 thr（忽略对角线）。根据 n 的不同，可能会有很多这样的子集。我想确定最小化求和 "score".

的子集

手动操作很痛苦，考虑到所有子集对于大矩阵是不可行的，除非 n 相当接近候选变量的数量，或者接近 1。有没有有效的方法使程序自动化？

FWIW，这是全子集解决方案的样子：

thr <- 0.8 # I use the term uncorrelated loosely in the title ;)
n <- 4
combos <- combn(ncol(r), n)
summed_score <- apply(combos, 2, function(x) {
  z <- abs(r[x, x])
  if(any(z[lower.tri(z)] > thr)) NA else sum(score[x])
})

min(summed_score, na.rm=T)
## [1] 13

which.min(summed_score)
## [1] 9

以上表明以下变量组合使总分最小化，同时与绝对值大于 0.8 的相关性无关。

combos[, 9]
## [1] 1 2 4 6

r[combos[, 9], combos[, 9]]

##       [,1] [,2]  [,3]  [,4]
## [1,]  1.00 0.61 -0.14  0.77
## [2,]  0.61 1.00  0.26  0.00
## [3,] -0.14 0.26  1.00 -0.56
## [4,]  0.77 0.00 -0.56  1.00

Answer 1

我认为你应该订购 combos 这样你就可以按这个顺序尝试

combos[,order(apply(combos,2,sum))]

那么如果它通过约束（即没有任何高于阈值的相关性），那将是最好的解决方案，您可以停止搜索。

jbaums的代码见评论：

combos <- combos[, order(apply(combos, 2, function(x) sum(score[x])))];
for(i in seq_len(ncol(combos))) {
    z <- abs(r[combos[, i], combos[, i]]); 
    if(!any(z[lower.tri(z)] > thr)) break()
}

> combos[, i]
[1] 1 2 4 6

Answer 2

如果你能有效地解决这个问题，我认为你可以通过创建一个反映图中边是否存在的相关矩阵来有效地解决 https://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29#Finding_maximum_independent_sets。我假设如果您对 non-zero 相关性使用非常小的数字，您将生成一个可能实际发生的相关矩阵。如果是这种情况，那么您的问题 worst-case 很难，因为最大独立集是最坏的情况，尽管在 link 周围提到的特殊情况有一些希望。不幸的是，一般近似值似乎也是最坏的情况。

你能决定你真的想要一些可以转化为更简单的图形问题的东西吗，比如找出哪些点直接或间接地相互连接，你可以通过 https://en.wikipedia.org/wiki/Disjoint-set_data_structure 找到？

Select 一个不相关的子集，受约束

Select an uncorrelated subset, subject to a constraint

algorithm

performance

r

subset

correlation