Наименее коррелированное подмножество случайных величин из корреляционной матрицы

У меня есть корреляционная матрица $A$ , которую я получил, используя коэффициент линейной корреляции Пирсона через функцию Matlab corrcoef () . Корреляционная матрица размерности 100x100, т.е. я вычислил корреляционную матрицу на 100 случайных величин.

Среди этих 100 случайных величин я хотел бы найти 10 случайных величин, чья матрица корреляции содержит как можно меньшую «корреляцию» (см. Количественную оценку того, насколько «больше корреляции» содержит матрица корреляции A по сравнению с матрицей B корреляции для измерения метрик общая корреляция в корреляционной матрице). Я забочусь только о парной корреляции.

Существуют ли хорошие методы, чтобы найти эти 10 случайных величин за разумное время (например, я не хочу пробовать комбинации )? Алгоритмы аппроксимации в порядке.$\binom{100}{10}$

Давайте рассмотрим сумму абсолютных парных корреляций в качестве нашей меры выбора. Таким образом, мы ищем вектор с l 1 ( v ) = n, который минимизирует v ′ Q v, где Q i j = | A i j | ,$v\in\{0,1\}^N$$l_1(v)=n$$v'Qv$$Q_{ij}=|A_{ij}|$

Предположим, что Q также положительно определен как A, задача сводится к решению ограниченной задачи квадратичной оптимизации:

$$v^*=\min\ v'Qv\ s.t.\ l_1(v)=n,\ v_i\in\{0,1\}$$

Это предполагает следующее расслабление:

$$v^*=\min\ v'Qv\ s.t.\ l_1(v)=n,\ v_i\in[0,1]$$

которая может быть легко решена с помощью готовых решателей; тогда результат дается наибольшими компонентами в v ∗ .$n$$v^*$

Пример кода Matlab:

N=100;
n=10;
% Generate random data
A=rand(N,1000);
C=corrcoef(A');
Q=abs((C+C')/2); % make sure it is symmetric
x = cplexqp(Q,zeros(1,N),[],[], ones(1, N),n, zeros(N,1), ones(N,1));
% If you don't use CPLEX, use matlab's default
% x = quadprog(Q,zeros(1,N),[],[], ones(1, N),n, zeros(N,1), ones(N,1));
assert(abs(sum(x)-n)<1e-10);
% Find the n largest values
I=sort(x); 
v=zeros(size(x)); v(x>I(N-n))=1; 
assert(abs(sum(v)-n)<1e-10);
% Make sure we do better than 10K random trials
for i=1:10000
   vc=zeros(size(x)); vc(randperm(N,n))=1;
   assert(sum(vc)==n, 'Wrong l0 norm');
   assert(vc'*Q*vc>v'*Q*v, 'Improves result');
end
% Show results
J=find(v==1);
fprintf('The optimal solution total off-diagonal correlations are %1.3f\n', v'*Q*v-n);
fprintf('The matrix:\n');
C(J,J)

Это может быть хуже, чем идея иерархической кластеризации @ ttnphns. Но: я только что натолкнулся на статью, в которой $\log \det(I + A)$ в качестве растущей субмодульной целевой функции:

Ванчинатан, Марфурт, Робелин, Коссман и Краузе. Обнаружение ценных предметов из массивных данных . KDD 2015. ( doi , arXiv )

Если вы считаете, что это разумная мера «наименее коррелированной», вы можете получить коэффициент $1-1/e$ оптимального набора, просто итеративно выбирая точку, которая максимизирует это. Это может быть эффективно выполнено с помощью блока разложения LU , где $v$ - вектор корреляций с записями, уже находящимися в матрице:

$$\begin{align*} \det \begin{bmatrix} I+A & v \\ v^T & 2 \end{bmatrix} &= \det \left( \begin{bmatrix} I & 0 \\ v^T (I+A)^{-1} & 1 \end{bmatrix} \begin{bmatrix} I+A & 0 \\ 0 & 2 - v^T (I+A)^{-1} v \end{bmatrix} \begin{bmatrix} I & (I+A)^{-1} v \\ 0 & 1 \end{bmatrix} \right) \\&= \det \begin{bmatrix} I & 0 \\ v^T (I+A)^{-1} & 1 \end{bmatrix} \det \begin{bmatrix} I+A & 0 \\ 0 & 2 - v^T (I+A)^{-1} v \end{bmatrix} \det \begin{bmatrix} I & (I+A)^{-1} v \\ 0 & 1 \end{bmatrix} \\&= (2 - v^T (I+A)^{-1} v) \det (I+A) \end{align*}$$

и, конечно, вы должны вычислить $v^T (I+A)^{-1} v = \lVert L^{-1} v \rVert^2$ , где$L$ - факторизация Холецкого для$I + A$ и используя треугольный решатель, который равен$O(n^2)$ . Так что весь этот процесс должен занять$O( \sum_{k=1}^n N k^2 + k^3) = O( N n^3 )$ время выбрать$n$ из$N$ элементов, предполагая, что корреляционная матрица уже вычислена.

Я не совсем понимаю, что вы подразумеваете под «меня волнует только парная корреляция» , но вот что может помочь: используйте инверсию вашей корреляционной матрицы. - 1 я я член равен д е т ($A^{-1}_{ii}$$det(A_{0_i}) / det(A)$ , где 0 я является ( п - 1 )$A_{0_i}$$(n-1)$ х $(n-1)$ матрица построена из $A$ , где $i$столбец и строка были удалены.

Таким образом, получение индекса минимального диагонального коэффициента в $A^{-1}$ говорит вам, какая точка имеет наименьшую корреляцию с остальной частью набора.

В зависимости от того, что вы действительно хотите сделать, вы можете либо взять 10 самых низких значений по диагонали инвертирования, либо получить первое, затем вычислить инвертирование с удаленной точкой и так далее.

Если это не то, что вам нужно, я чувствую, что этот трюк может быть полезен, но я не уверен, как, хотя.

Найдите из n элементов с наименьшей попарной корреляцией: поскольку, скажем, корреляция 0,6 объясняет 0,36 отношения между двумя рядами, имеет больше смысла минимизировать сумму квадратов корреляций для ваших целевых k элементов. Вот мое простое решение.$k$$n$$0.6$$0.36$$k$

Перепишите свою матрицу корреляций в матрицу квадратов корреляций. Суммируйте квадраты каждого столбца. Удалите столбец и соответствующую строку с наибольшей суммой. Теперь у вас есть ( n - 1 ) × ( n - 1 ) матрица. Повторяйте, пока не получите матрицу k × k . Вы также можете просто сохранить столбцы и соответствующие строки с k наименьшими суммами. Сравнивая методы, я нашел в матрице с n = 43 и k = $n \times n$$(n−1)\times (n−1)$$k\times k$$k$$n=43$$k=20$ что только два предмета с близкими суммами были по-разному сохранены и исключены.