考虑一个相关矩阵 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
此外，每个变量都有一个特定的“分数”。对于变量 1 到 10，我们分配分数 1:10。
score <- 1:10
我想选择一个 n 变量的子集，这些变量的相关性绝对值不大于 thr(忽略对角线)。根据 n 的不同，可能会有很多这样的子集。我想确定最小化总和“分数”的子集。
手动做这件事很痛苦，考虑到所有子集对于大矩阵是不可行的，除非 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
最佳答案
如果你能有效地解决这个问题，我想你可以解决https://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29#Finding_maximum_independent_sets通过创建反射(reflect)图中边是否存在的相关矩阵，可以有效地实现。我假设如果您对非零相关使用非常小的数字，您将生成一个可能实际发生的相关矩阵。如果是这种情况，那么您的问题是最坏情况下的困难，因为最大独立集是最坏情况下的困难，尽管该链接周围提到的特殊情况有一些希望。不幸的是，一般近似似乎也是最坏的情况。
你能决定你真的想要一些可以转化为更简单的图形问题的东西吗，比如找出哪些点直接或间接地相互连接，你可以通过 https://en.wikipedia.org/wiki/Disjoint-set_data_structure 找到它？
关于r - 选择一个不相关的子集，受约束，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34667549/