Finden Sie k von n Elementen mit den geringsten paarweisen Korrelationen

9

Ich habe eine Matrix paarweiser Korrelationen zwischen n Elementen. Jetzt möchte ich eine Teilmenge von k Elementen mit der geringsten Korrelation finden. Somit gibt es zwei Fragen:

  1. Welches ist das geeignete Maß für die Korrelation innerhalb dieser Gruppe?
  2. Wie finde ich die Gruppe mit der geringsten Korrelation?

Dieses Problem erscheint mir wie eine Art inverse Faktoranalyse, und ich bin mir ziemlich sicher, dass es eine einfache Lösung gibt.

Ich denke, dieses Problem entspricht tatsächlich dem Problem, (nk) Knoten aus einem vollständigen Diagramm zu entfernen, sodass die verbleibenden Knoten mit minimalen Kantengewichten verbunden sind. Was denken Sie?

Vielen Dank für Ihre Vorschläge im Voraus!

Chris
quelle
Diese Seite könnte helfen: stackoverflow.com/questions/6782070/…
Timothée HENRY
Das sieht jetzt eher nach einer Graphentheorie als nach einer statistischen Frage aus (weil Korrelationen nicht mehr als voneinander abhängig angesehen werden). Vielleicht kann StackOverflow bessere Antworten liefern. Eine Art eingeschränkter minimaler Spannbaum ...
ttnphns
@ttnphs: Ein minimaler Spanning Tree ist genau das, was ich nicht möchte, da paarweise Korrelationen ein vollständiges Diagramm implizieren. Trotzdem haben Sie Recht, dass diese Frage besser zur Mathematik-Site passt. Vielen Dank!
Chris
Mir ist nicht klar, was Sie wollen. Wenn Sie alle Teilmengen überprüfen würden, würden Sie die Teilmenge mit der kleinsten Summe der quadratischen Korrelationen auswählen, wobei die Summe über den -Korrelationen innerhalb der Teilmenge liegt? Sind die -Korrelationen mit den verbleibenden Elementen von Bedeutung? (nk)k(k1)/2k(nk)nk
Ray Koopman
Ich habe eine ungefähre Lösung angegeben, die in der verknüpften Frage vorgeschlagen wird .
Uri Cohen

Antworten:

5

[Vorwarnung: Diese Antwort erschien, bevor das OP beschloss, die Frage neu zu formulieren, sodass sie möglicherweise an Relevanz verloren hat. Ursprünglich ging es um How to rank items according to their pairwise correlations]

Da die Matrix paarweiser Korrelationen kein eindimensionales Array ist, ist nicht ganz klar, wie "Ranking" aussehen kann. Vor allem, solange Sie Ihre Idee nicht im Detail ausgearbeitet haben, wie es scheint. Aber Sie haben PCA als für Sie geeignet erwähnt, und das hat mich sofort dazu gebracht, Cholesky-Wurzel als potenziell noch geeignetere Alternative zu betrachten.

Die Cholesky-Wurzel ist wie eine Matrix von Ladungen, die von PCA hinterlassen werden, nur ist sie dreieckig. Ich werde beides anhand eines Beispiels erklären.

R, correlation matrix
         V1       V2       V3       V4
V1   1.0000   -.5255   -.1487   -.2790
V2   -.5255   1.0000    .2134    .2624
V3   -.1487    .2134   1.0000    .1254
V4   -.2790    .2624    .1254   1.0000

A, PCA full loading matrix
          I       II      III       IV
V1   -.7933    .2385    .2944    .4767
V2    .8071   -.0971   -.3198    .4867
V3    .4413    .8918    .0721   -.0683
V4    .5916   -.2130    .7771    .0261

B, Cholesky root matrix
          I       II      III       IV
V1   1.0000    .0000    .0000    .0000
V2   -.5255    .8508    .0000    .0000
V3   -.1487    .1589    .9760    .0000
V4   -.2790    .1361    .0638    .9485

A*A' or B*B': both restore R
         V1       V2       V3       V4
V1   1.0000   -.5255   -.1487   -.2790
V2   -.5255   1.0000    .2134    .2624
V3   -.1487    .2134   1.0000    .1254
V4   -.2790    .2624    .1254   1.0000

Die PCA-Ladematrix A ist die Korrelationsmatrix zwischen den Variablen und den Hauptkomponenten. Wir können es sagen, weil die Zeilensummen der Quadrate alle 1 sind (die Diagonale von R), während die Matrixsumme der Quadrate die Gesamtvarianz ist (Spur von R). Die Elemente von Cholesky-Wurzel von B sind ebenfalls Korrelationen, da diese Matrix auch diese beiden Eigenschaften hat. Spalten von B sind keine Hauptkomponenten von A, obwohl sie in gewissem Sinne "Komponenten" sind.

Sowohl A als auch B können R wiederherstellen und somit beide R als seine Darstellung ersetzen. B ist dreieckig, was deutlich zeigt, dass es die paarweisen Korrelationen von R nacheinander oder hierarhisch erfasst. Choleskys Komponente Ikorreliert mit allen Variablen und ist das lineare Bild der ersten von ihnen V1. Komponente IInicht mehr mit, V1sondern korreliert mit den letzten drei ... Schließlich IVist nur mit den letzten korreliert , V4. Ich dachte, eine solche Art von "Ranking" ist vielleicht das, wonach Sie suchen ?

Das Problem bei der Cholesky-Zerlegung ist jedoch, dass sie - im Gegensatz zu PCA - von der Reihenfolge der Elemente in der Matrix R abhängt. Nun, Sie können die Elemente in absteigender oder aufsteigender Reihenfolge der Summe der quadratischen Elemente sortieren (oder, wenn Sie möchten , Summe der absoluten Elemente oder in der Reihenfolge des Mehrfachkorrelationskoeffizienten - siehe unten). Diese Reihenfolge gibt an, wie stark ein Artikel brutto korreliert.

R, rearranged
         V2       V1       V4       V3 
V2   1.0000   -.5255    .2624    .2134 
V1   -.5255   1.0000   -.2790   -.1487 
V4    .2624   -.2790   1.0000    .1254 
V3    .2134   -.1487    .1254   1.0000 

Column sum of squares (descending)
     1.3906   1.3761   1.1624   1.0833 

B 
          I       II      III       IV 
V2   1.0000    .0000    .0000    .0000 
V1   -.5255    .8508    .0000    .0000 
V4    .2624   -.1658    .9506    .0000 
V3    .2134   -.0430    .0655    .9738

Aus der letzten B-Matrix sehen wir, dass der V2am stärksten korrelierte Gegenstand alle seine Korrelationen in verpfändet I. Der nächste grob korrelierte Gegenstand V1verpfändet seine gesamte Korrelation, außer der mit V2, in II; und so weiter.


Eine andere Entscheidung könnte darin bestehen, den Mehrfachkorrelationskoeffizienten für jedes Element und jede Rangfolge basierend auf seiner Größe zu berechnen . Die Mehrfachkorrelation zwischen einem Element und allen anderen Elementen wächst, wenn das Element mehr mit allen korreliert, sie jedoch weniger miteinander korrelieren. Die quadratischen Mehrfachkorrelationskoeffizienten bilden die Diagonale der sogenannten Bildkovarianzmatrix, die , wobei die Diagonalmatrix der Kehrwerte der Diagonalen von .SR1S2S+RSR1

ttnphns
quelle
Vielen Dank für diese ausführliche Antwort, aber ich befürchte, dass ich mein Problem falsch angegeben habe. Ich bin mir sehr sicher, dass Ihr Beitrag für andere von Nutzen ist und stimme daher ab! Vielen Dank!
Chris
1
@ Ray, danke, dass du aufmerksam bist, um einen Fehler zu erkennen.
ttnphns
3

Hier ist meine Lösung für das Problem. Ich berechne alle möglichen Kombinationen von k von n Elementen und berechne ihre gegenseitigen Abhängigkeiten, indem ich das Problem in ein graphentheoretisches transformiere: Welches ist das vollständige Diagramm, das alle k Knoten mit der kleinsten Kantensumme (Abhängigkeiten) enthält? Hier ist ein Python-Skript, das die networkx-Bibliothek und eine mögliche Ausgabe verwendet. Bitte entschuldigen Sie etwaige Unklarheiten in meiner Frage!

Code:

import networkx as nx
import itertools
import os

#Create new graph
G=nx.Graph()

#Each node represents a dimension
G.add_nodes_from([1,2,3,4,5,6,7,8,9,10,11])

#For each dimension add edges and correlations as weights
G.add_weighted_edges_from([(3,1,0.563),(3,2,0.25)])
G.add_weighted_edges_from([(4,1,0.688),(4,3,0.438)])
G.add_weighted_edges_from([(5,1,0.25),(5,2,0.063),(5,3,0.063),(5,4,0.063)])
G.add_weighted_edges_from([(6,1,0.063),(6,2,0.25),(6,3,0.063),(6,4,0.063),(6,5,0.063)])
G.add_weighted_edges_from([(7,2,0.25),(7,3,0.063),(7,5,0.125),(7,6,0.063)])
G.add_weighted_edges_from([(8,1,0.125),(8,2,0.125),(8,3,0.5625),(8,5,0.25),(8,6,0.188),(8,7,0.125)])
G.add_weighted_edges_from([(9,1,0.063),(9,2,0.063),(9,3,0.25),(9,6,0.438),(9,7,0.063),(9,8,0.063)])
G.add_weighted_edges_from([(10,1,0.25),(10,2,0.25),(10,3,0.563),(10,4,0.125),(10,5,0.125),(10,6,0.125),(10,7,0.125),(10,8,0.375),(10,9,0.125)])
G.add_weighted_edges_from([(11,1,0.125),(11,2,0.063),(11,3,0.438),(11,5,0.063),(11,6,0.1875),(11,7,0.125),(11,8,0.563),(11,9,0.125),(11,9,0.188)])

nodes = set(G.nodes())
combs = set(itertools.combinations(nodes,6))
sumList = []
for comb in combs:
    S=G.subgraph(list(comb))
    sum=0
    for edge in S.edges(data=True):
        sum+=edge[2]['weight']
    sumList.append((sum,comb))

sorted = sorted(sumList, key=lambda tup: tup[0])    

fo = open("dependency_ranking.txt","wb")

for i in range(0,len(sorted)):
    totalWeight = sorted[i][0]
    nodes = list(sorted[i][1])
    nodes.sort()
    out = str(i)+": "+str(totalWeight)+","+str(nodes)
    fo.write(out.encode())
    fo.write("\n".encode())

fo.close()

S=G.subgraph([1,2,3,4,6,7])
sum = 0
for edge in S.edges(data=True):
        sum+=edge[2]['weight']
print(sum)

Beispielausgabe:

0: 1.0659999999999998,[2, 4, 5, 7, 9, 11]
1: 1.127,[4, 5, 7, 9, 10, 11]
2: 1.128,[2, 4, 5, 9, 10, 11]
3: 1.19,[2, 4, 5, 7, 8, 9]
4: 1.2525,[4, 5, 6, 7, 10, 11]
5: 1.377,[2, 4, 5, 7, 9, 10]
6: 1.377,[2, 4, 7, 9, 10, 11]
7: 1.377,[2, 4, 5, 7, 10, 11]

Eingabediagramm: Geben Sie hier die Bildbeschreibung ein

Lösungsdiagramm: Geben Sie hier die Bildbeschreibung ein

Für ein Spielzeugbeispiel ist k = 4, n = 6: Eingabediagramm: Geben Sie hier die Bildbeschreibung ein

Lösungsdiagramm: Geben Sie hier die Bildbeschreibung ein

Beste,

Christian

Chris
quelle
1
Dies könnte eine gute Lösung sein. Aber um es zu schätzen, möchte man das Diagramm (die Matrix) selbst und die Lösung als Diagramm sehen. Nicht nur der Code und und die Ausgabe.
ttnphns
@ttnphns: Ich habe Diagramme der resultierenden Diagramme und ein Spielzeugbeispiel hinzugefügt.
Chris
@ Chris Danke, dass Sie Ihre Lösung dokumentiert haben. Könnten Sie ein oder zwei Sätze darüber hinzufügen, wie lange dies gedauert hat und wie es mit der Anzahl der Knoten / Dimensionen skaliert?
Casimir
@Casimir: Ich entschuldige mich dafür, dass ich diese Informationen nicht im Voraus aufgenommen habe. Zu diesem Zeitpunkt ist dieser Beitrag jedoch> 5 Jahre alt und ich habe die Informationen nicht mehr zur Hand. Bitte zögern Sie nicht, den Code zu kopieren und einzufügen und angewandte oder theoretische Laufzeitschätzungen vorzunehmen - ich würde mich über die Ergänzung des Beitrags freuen.
Chris
1
Es könnte daher erwähnenswert sein, dass in Fällen, in denen die Anzahl der Dimensionen bei Hunderten oder sogar Tausenden liegt, dieser Ansatz nicht durchführbar ist. Aber immer noch eine coole Möglichkeit, dies für kleine Problemgrößen zu lösen!
Casimir
2

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.n 0,6 0,36 kkn0.60.36k

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 ) k × k k n = 43 k = 20n×n(n1)×(n1)k×kkn=43k=20

Jon Arts
quelle
1
Ich habe diese Methode ausprobiert und mit der Diagrammmethode verglichen, bei der jeder Untergraph nachgeschlagen wurde. Obwohl diese Methode nicht die optimalste Antwort lieferte, lieferte sie eine der 5 besten Kombinationen und ist natürlich viel schneller.
SamFisher83