Как найти максимально возможную ковариационную матрицу или самый большой набор столбцов с не пропущенной попарной ковариацией

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

К сожалению, этот вопрос равняется нахождению максимальной клики , что является известной трудной проблемой.Стандартные алгоритмы для этой задачи будут работать лучше, если вы предварительно обработаете график сопоставимости путем объединения наборов узлов с точно такой же моделью наблюдения.Возможно, есть другие эвристики, которые могли бы работать для вашего графика.

Чтобы пойти другим путем, возможно, вы могли бы применить алгоритм SVD, который обрабатывает недостающие данные.