Am wenigsten korrelierte Teilmenge von Zufallsvariablen aus einer Korrelationsmatrix

Ich habe eine Korrelationsmatrix , die ich unter Verwendung des linearen Korrelationskoeffizienten nach Pearson durch Matlab's corrcoef () erhalten habe . Die Korrelationsmatrix der Dimension 100x100, dh ich habe die Korrelationsmatrix für 100 Zufallsvariablen berechnet.$A$

Unter diesen 100 Zufallsvariablen möchte ich die 10 Zufallsvariablen finden, deren Korrelationsmatrix so wenig Korrelation wie möglich enthält (siehe Quantifizieren, wie viel "mehr Korrelation" eine Korrelationsmatrix A im Vergleich zu einer Korrelationsmatrix B in Bezug auf zu messende Metriken enthält die Gesamtkorrelation in einer Korrelationsmatrix). Ich kümmere mich nur um paarweise Korrelation.

Gibt es gute Methoden, um diese 10 Zufallsvariablen in angemessener Zeit zu finden (z. B. möchte ich keine $\binom{100}{10}$ -Kombinationen ausprobieren )? Approximationsalgorithmen sind in Ordnung.

Betrachten wir die Summe der absoluten paarweisen Korrelationen als unser Maß für die Wahl. Damit haben wir einen Vektor suchen mit denen minimieren wo.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}|$

Angenommen, Q ist auch als A eindeutig positiv, dann wird das Problem auf die Lösung des eingeschränkten quadratischen Optimierungsproblems reduziert:

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

Dies deutet auf folgende Entspannung hin:

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

die mit handelsüblichen Lösern leicht gelöst werden kann; dann ist das Ergebnis durch die größten Komponenten in .v $n$$v^*$

Beispiel für einen Matlab-Code:

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)

Dies ist möglicherweise schlimmer als die hierarchische Clustering-Idee von @ ttnphns. Aber: Ich bin gerade auf ein Papier gestoßen , das als zunehmende submodulare Zielfunktion verwendet:$\log \det(I + A)$

Vanchinathan, Marfurt, Robelin, Kossman und Krause. Erkennen wertvoller Gegenstände aus massiven Daten . KDD 2015. ( doi , arXiv )

Wenn Sie der Meinung sind, dass dies ein vernünftiges Maß für "am wenigsten korreliert" ist, können Sie einen Faktor der optimalen Menge erreichen, indem Sie einfach iterativ den Punkt auswählen, der dies maximiert. Dies kann effizient mit der Block-LU-Zerlegung durchgeführt werden , wobei der Korrelationsvektor zu Einträgen ist, die sich bereits in der Matrix befinden:$1-1/e$v$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*}$$

und natürlich sollten Sie berechnen , wobei die Cholesky-Faktorisierung von und einen Dreieckslöser verwendet das ist . Dieser gesamte Prozess sollte also Zeit benötigen, um aus Elementen auszuwählen , vorausgesetzt, die Korrelationsmatrix ist bereits berechnet .$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$

Ich bin mir nicht sicher, ob Sie vollständig verstehen, was Sie unter "Ich kümmere mich nur um die paarweise Korrelation" verstehen , aber hier ist etwas, das helfen kann: Verwenden Sie die Invertierung Ihrer Korrelationsmatrix. Die Term ist gleich , wo ist die x Matrix von eingebauten wo die te Spalte und Zeile entfernt wurden.$A^{-1}_{ii}$$det(A_{0_i}) / det(A)$$A_{0_i}$$(n-1)$$(n-1)$$A$$i$

Wenn Sie den Index des minimalen Diagonalkoeffizienten in erfahren Sie, welcher Punkt die niedrigste Korrelation zum Rest der Menge aufweist.$A^{-1}$

Je nachdem, was Sie tatsächlich tun möchten, können Sie entweder die 10 niedrigsten Werte auf der Diagonale der Invertierung verwenden oder den ersten erhalten und dann die Invertierung mit dem gelöschten Punkt berechnen und so weiter.

Wenn dies nicht das ist, was Sie brauchen, könnte dieser Trick immer noch hilfreich sein, aber ich bin mir nicht sicher, wie.

Finden von Elementen mit der geringsten paarweise Korrelation: Da eine Korrelation von etwa erklärt der Beziehung zwischen zwei Serien es mehr Sinn macht , die Summe der Quadrate der Korrelationen für Ihr Ziel zu minimieren Elemente. Hier ist meine einfache Lösung.$k$$n$$0.6$$0.36$$k$

Schreiben Sie Ihre Korrelationsmatrix in eine Matrix von Korrelationsquadraten um. Summiere die Quadrate jeder Spalte. Beseitigen Sie die Spalte und die entsprechende Zeile mit der größten Summe. Sie haben jetzt eine Matrix. Wiederholen Sie diesen Vorgang, bis Sie eine Matrix haben. Sie können auch einfach die Spalten und entsprechenden Zeilen mit den kleinsten Summen behalten . Beim Vergleich der Methoden stellte ich in einer Matrix mit und dass nur zwei Elemente mit engen Summen unterschiedlich aufbewahrt und eliminiert wurden.( n - 1 ) × ( n - 1 $n \times n$$(n−1)\times (n−1)$k n = 43 k = $k\times k$$k$$n=43$$k=20$