Menos subconjunto correlacionado de variáveis ​​aleatórias de uma matriz de correlação

Eu tenho uma matriz de correlação$A$ , que eu obtive usando o coeficiente de correlação linear de Pearson através docorrcoefde Matlab(). A matriz de correlação da dimensão 100x100, ou seja, eu calculei a matriz de correlação em 100 variáveis ​​aleatórias.

Entre essas 100 variáveis ​​aleatórias, gostaria de encontrar as 10 variáveis ​​aleatórias cuja matriz de correlação contém o mínimo possível de correlação (consulte Quantificando quanto "mais correlação" uma matriz de correlação A contém em comparação com uma matriz de correlação B em relação às métricas a serem medidas a correlação geral em uma matriz de correlação). Eu só me preocupo com a correlação pareada.

Existem bons métodos para encontrar essas 10 variáveis ​​aleatórias em um período de tempo razoável (por exemplo, eu não quero tentar combinações $\binom{100}{10}$ )? Algoritmos de aproximação estão OK.

Vamos considerar a soma das correlações absolutas aos pares como nossa medida de escolha. Assim, buscamos um vetor com que minimizará onde.$v\in\{0,1\}^N$$l_1(v)=n$$v'Qv$$Q_{ij}=|A_{ij}|$

Suponha que Q também seja positivo definido como A, o problema é reduzido para resolver o problema de otimização quadrática restrita:

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

Isso sugere o seguinte relaxamento:

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

que pode ser facilmente resolvido usando solucionadores prontos para uso; então o resultado é dado pelos maiores componentes em .$n$$v^*$

Exemplo de código 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)

Isso pode ser pior do que a idéia de agrupamento hierárquico do @ ttnphns. Mas: acabei de encontrar um artigo que usa como uma função objetivo submodular crescente:$\log \det(I + A)$

Vanchinathan, Marfurt, Robelin, Kossman e Krause. Descobrindo itens valiosos de dados maciços . KDD 2015. ( doi , arXiv )

Se você acha que essa é uma medida razoável de "menos correlacionado", você pode obter um fator de do conjunto ideal, simplesmente escolhendo iterativamente o ponto que maximiza isso. Isso pode ser feito eficientemente com a decomposição da LU do bloco , em que é o vetor de correlações para entradas já na matriz:$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*}$$

e, é claro, você deve calcular , onde é a fatoração de Cholesky de e usando um solucionador triangular que é . Portanto, todo esse processo deve levar tempo para selecionar dentre elementos, assumindo que a matriz de correlação já esteja computada .$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$

Não tenho certeza de entender completamente o que você quer dizer com "Só me preocupo com a correlação por pares" , mas aqui está algo que pode ajudar: use o inverso da sua matriz de correlação. O termo é igual a , onde é a matriz x construída a partir de onde a ésima coluna e linha foram removidas.$A^{-1}_{ii}$$det(A_{0_i}) / det(A)$$A_{0_i}$$(n-1)$$(n-1)$$A$$i$

Obter o índice do coeficiente diagonal mínimo em indica o ponto que tem a menor correlação com o restante do conjunto.$A^{-1}$

Dependendo do que você realmente deseja fazer, você pode pegar os 10 valores mais baixos na diagonal do inversor ou obter o primeiro, depois calcular o inversor com o ponto excluído e assim por diante.

Se não é isso que você precisa, acho que esse truque ainda pode ser útil, mas não sei como.

Encontre de itens com a correlação menos pareada: Como uma correlação de explica da relação entre duas séries, faz mais sentido minimizar a soma dos quadrados das correlações dos itens de destino . Aqui está a minha solução simples.$k$$n$$0.6$$0.36$$k$

Reescreva sua matriz de correlações para uma matriz de quadrados de correlações. Soma os quadrados de cada coluna. Elimine a coluna e a linha correspondente com a maior soma. Agora você tem uma matriz . Repita até que você tenha uma matriz . Você também pode manter as colunas e as linhas correspondentes com as menores somas. Comparando os métodos, descobri em uma matriz com e que apenas dois itens com somas próximas foram mantidos e eliminados de maneira diferente.$n \times n$$(n−1)\times (n−1)$$k\times k$$k$$n=43$$k=20$