python - 如何找到最大可能的协方差矩阵，或具有非缺失成对协方差的最大列集

Question

我的数据经常缺少很多观察值。有时这意味着我有几对没有重叠观察值的列，因此我无法计算两者之间的协方差。

但我想知道最大的一组列，该集合中的所有列对都有重叠的观察值(至少 2 个，但你可以假设有一个就有很多)，这样我就可以计算一个没有缺失值的协方差矩阵(所有成对协方差)。

例如，考虑以下 python 代码。

>>> import pandas as pd
>>> import numpy as np
>>> n = np.nan
>>> d = pd.DataFrame(
np.array(
[[1, n, 2, 4, 2, n, 6, n, 1, 1],
 [2, n, 3, 4, 4, n, 5, 4, 2, n],
 [1, 3, 4, 2, n, 2, 4, 2, n, 1],
 [1, 3, 4, 1, n, 1, 2, 1, n, 1]]),
        columns=['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'])
>>> d
      a    b    c    d    e    f    g    h    i    j
0  1.0  NaN  2.0  4.0  2.0  NaN  6.0  NaN  1.0  1.0
1  2.0  NaN  3.0  4.0  4.0  NaN  5.0  4.0  2.0  NaN
2  1.0  3.0  4.0  2.0  NaN  2.0  4.0  2.0  NaN  1.0
3  1.0  3.0  4.0  1.0  NaN  1.0  2.0  1.0  NaN  1.0

我想创建一些函数来告诉我应该使用哪一组列来创建最大的协方差矩阵。我认为这种情况下的答案是 ['a', 'b', 'c', 'd', 'f', 'g', 'h', 'j']:

>>> d[['a', 'b', 'c', 'd', 'f', 'g', 'h', 'j']].cov() 
          a    b         c         d    f         g         h    j
a  0.250000  0.0 -0.083333  0.416667  0.0  0.250000  0.833333  0.0
b  0.000000  0.0  0.000000  0.000000  0.0  0.000000  0.000000  0.0
c -0.083333  0.0  0.916667 -1.250000  0.0 -1.416667 -0.833333  0.0
d  0.416667  0.0 -1.250000  2.250000  0.5  2.416667  2.333333  0.0
f  0.000000  0.0  0.000000  0.500000  0.5  1.000000  0.500000  0.0
g  0.250000  0.0 -1.416667  2.416667  1.0  2.916667  2.166667  0.0
h  0.833333  0.0 -0.833333  2.333333  0.5  2.166667  2.333333  0.0
j  0.000000  0.0  0.000000  0.000000  0.0  0.000000  0.000000  0.0

这只是一个玩具示例。实际上，数据集很大 n=1000 或 n=100000 或更多。并且列数 k=10 或 k=200。我认为对于大 k 这可能是一个非常困难的问题。似乎可能有更有效的动态编程解决方案，因为检查所有不同的列组合看起来令人望而却步。

Answer 1

不幸的是，这个问题相当于 finding a maximum clique ，这是一个已知的难题。如果您通过合并具有完全相同观察模式的节点集来预处理可比性图，那么该问题的标准算法会更好地工作。也许还有其他适用于您的图表的启发式方法。

要采取不同的策略，也许您可​​以应用 SVD 算法来处理缺失数据。