Najmniej skorelowany podzbiór zmiennych losowych z macierzy korelacji

Mam macierz korelacji , którą uzyskałem za pomocą współczynnika korelacji liniowej Pearsona za pomocą corrcoef Matlaba () . Macierz korelacji o wymiarze 100x100, tj. Obliczyłem macierz korelacji na 100 zmiennych losowych.$A$

Spośród tych 100 zmiennych losowych chciałbym znaleźć 10 zmiennych losowych, których macierz korelacji zawiera możliwie „małą korelację” (patrz Obliczanie, ile „więcej korelacji” zawiera matryca korelacji A w porównaniu do macierzy korelacji B w odniesieniu do metryk do pomiaru ogólna korelacja w macierzy korelacji). Dbam tylko o korelację par.

Czy istnieją dobre metody znalezienia tych 10 zmiennych losowych w rozsądnym czasie (np. Nie chcę próbować )? Algorytmy aproksymacyjne są OK.$\binom{100}{10}$

Rozważmy sumę bezwzględnych korelacji par jako naszą miarę wyboru. Szukamy zatem wektora przy który zminimalizuje gdzie.$v\in\{0,1\}^N$$l_1(v)=n$$v'Qv$$Q_{ij}=|A_{ij}|$

Załóżmy, że Q jest również pozytywnie określone jako A, problem sprowadza się do rozwiązania ograniczonego kwadratowego problemu optymalizacji:

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

To sugeruje następujący relaks:

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

które można łatwo rozwiązać za pomocą gotowych rozwiązań; wynik jest podawany przez największe składników w .$n$$v^*$

Przykładowy kod 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)

Może to być gorsze niż hierarchiczna idea klastrowania @ ttnphns. Ale: Właśnie natrafiłem na artykuł, który używa jako rosnącej funkcji celu podmodularnego:$\log \det(I + A)$

Vanchinathan, Marfurt, Robelin, Kossman i Krause. Odkrywanie cennych przedmiotów z ogromnych danych . KDD 2015. ( doi , arXiv )

Jeśli uważasz, że jest to rozsądna miara „najmniej skorelowanej”, możesz uzyskać współczynnik optymalnego zestawu, po prostu iteracyjnie wybierając punkt, który ją maksymalizuje. Można to skutecznie zrobić z dekompozycją bloku LU , gdzie jest wektorem korelacji z wpisami już w macierzy:$1-1/e$$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*}$$

i oczywiście powinieneś obliczyć , gdzie jest Choleskiego na i za pomocą solwera trójkątnego czyli . Cały ten proces powinien więc zająć aby wybrać spośród elementów, zakładając, że macierz korelacji jest już obliczona .$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$

Nie jestem do końca pewien, co rozumiesz przez „dbam tylko o korelację par” , ale oto coś, co może pomóc: użyj odwrócenia macierzy korelacji. Termin wynosi , w którym jest x matryca zbudowana z gdzie kolumna i wiersz zostały usunięte.$A^{-1}_{ii}$$det(A_{0_i}) / det(A)$$A_{0_i}$$(n-1)$$(n-1)$$A$$i$

Uzyskanie indeksu minimalnego współczynnika przekątnej w mówi zatem, który punkt ma najniższą korelację z resztą zbioru.$A^{-1}$

W zależności od tego, co faktycznie chcesz zrobić, możesz wziąć 10 najniższych wartości na przekątnej inwertora lub uzyskać pierwszą, a następnie obliczyć inwertę z usuniętym punktem i tak dalej.

Jeśli nie jest to potrzebne, czuję, że ta sztuczka może być nadal pomocna, ale nie jestem pewien, jak to zrobić.

Znajdź z elementów z najmniejszej korelacji parami: Ponieważ korelacja Say wyjaśnia relacji między dwoma serii większy sens, aby zminimalizować sumę kwadratów korelacji dla docelowego przedmiotów. Oto moje proste rozwiązanie.$k$$n$$0.6$$0.36$$k$

Przepisz swoją macierz korelacji do macierzy kwadratów korelacji. Zsumuj kwadraty każdej kolumny. Wyeliminuj kolumnę i odpowiadający jej wiersz o największej sumie. Masz teraz macierz . Powtarzaj, aż uzyskasz macierz . Możesz także zachować kolumny i odpowiadające im wiersze z najmniejszymi sumami. Porównując metody, znalazłem w macierzy i że tylko dwa elementy o bliskich sumach były różnie przechowywane i eliminowane.$n \times n$$(n−1)\times (n−1)$$k\times k$$k$$n=43$$k=20$