Encuentre k de n elementos con las correlaciones de menor par

9

Tengo una matriz de correlaciones por pares entre n elementos. Ahora quiero encontrar un subconjunto de k elementos con la menor correlación. Por lo tanto, hay dos preguntas:

  1. ¿Cuál es la medida adecuada para la correlación dentro de ese grupo?
  2. ¿Cómo encontrar el grupo con la menor correlación?

Este problema me parece una especie de análisis factorial inverso y estoy bastante seguro de que hay una solución directa.

Creo que este problema en realidad es igual al problema de eliminar (nk) nodos de un gráfico completo para que los nodos restantes estén conectados con pesos de borde mínimos. ¿Qué piensas?

Gracias por sus sugerencias de antemano!

Chris
fuente
Esta página podría ayudar: stackoverflow.com/questions/6782070/…
Timothée HENRY
Eso ahora parece más una teoría gráfica que una pregunta estadística (porque las correlaciones ya no se consideran interdependientes). Quizás StackOverflow pueda dar mejores respuestas. Algún tipo de árbol de expansión mínimo restringido ...
ttnphns
@ttnphs: un árbol de expansión mínimo es justo lo que no quiero, ya que las correlaciones por pares implican un gráfico completo. Sin embargo, tiene razón en que esta pregunta podría encajar mejor en el sitio de matemáticas. ¡Gracias!
Chris
No tengo claro lo que quieres. Si tuviera que verificar todos los subconjuntos , ¿elegiría el subconjunto con la suma más pequeña de correlaciones al cuadrado, donde la suma está por encima de las correlaciones dentro del subconjunto? ¿ correlaciones con los elementos restantes ? (nk)k(k1)/2k(nk)nk
Ray Koopman
He dado una solución aproximada que se sugiere en la pregunta vinculada .
Uri Cohen

Respuestas:

5

[Advertencia: esta respuesta apareció antes de que el OP decidiera reformular la pregunta, por lo que puede haber perdido relevancia. Originalmente la pregunta era sobre How to rank items according to their pairwise correlations]

Debido a que la matriz de correlaciones por pares no es una matriz unidimensional, no está muy claro cómo podría ser la "clasificación". Especialmente siempre que no haya elaborado su idea en detalle, como parece. Pero mencionó PCA como adecuado para usted, y eso inmediatamente me hizo pensar en la raíz de Cholesky como una alternativa potencialmente aún más adecuada.

La raíz de Cholesky es como una matriz de cargas dejadas por PCA, solo que es triangular. Explicaré ambos con un ejemplo.

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

La matriz de carga A de PCA es la matriz de correlaciones entre las variables y los componentes principales. Podemos decirlo porque las sumas de cuadrados de las filas son todas 1 (la diagonal de R) mientras que la suma de cuadrados de la matriz es la varianza general (rastro de R). Los elementos de la raíz de Cholesky de B también son correlaciones, porque esa matriz también tiene estas dos propiedades. Las columnas de B no son componentes principales de A, aunque son "componentes", en cierto sentido.

Tanto A como B pueden restaurar R y, por lo tanto, ambos pueden reemplazar a R, como su representación. B es triangular, lo que muestra claramente el hecho de que captura las correlaciones por pares de R de forma secuencial o jerárquica. El componente de Cholesky se Icorrelaciona con todas las variables y es la imagen lineal de la primera de ellas V1. El componente IIno comparte más con, V1pero se correlaciona con los últimos tres ... Finalmente, IVse correlaciona solo con el último V4,. Pensé que ese tipo de "clasificación" es quizás lo que buscas ?

Sin embargo, el problema con la descomposición de Cholesky es que, a diferencia de PCA, depende del orden de los elementos en la matriz R. Bueno, puede ordenar los elementos en orden descendente o ascendente de la suma de elementos al cuadrado (o, si lo desea , suma de elementos absolutos, o en orden de coeficiente de correlación múltiple (ver más abajo). Este orden refleja cuánto correlaciona bruto un artículo.

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

De la última matriz B vemos que V2, el ítem más correlacionado, empeña todas sus correlaciones I. El siguiente elemento extremadamente correlacionado V1empeña toda su correlación, excepto que con V2, en II; y así.


Otra decisión podría ser calcular el coeficiente de correlación múltiple para cada elemento y clasificación según su magnitud. La correlación múltiple entre un elemento y todos los demás elementos crece a medida que el elemento se correlaciona más con todos ellos, pero se correlacionan menos entre sí. Los coeficientes de correlación múltiple al cuadrado forman la diagonal de la llamada matriz de covarianza de imagen que es , donde es la matriz diagonal de los recíprocos de las diagonales de .SR1S2S+RSR1

ttnphns
fuente
Muchas gracias por esta elaborada respuesta, pero me temo que he declarado mal mi problema. Estoy muy seguro de que tu publicación es útil para otros y, por lo tanto, ¡vota! ¡Gracias!
Chris
1
@ Ray, gracias por estar atento para detectar un lapso.
ttnphns
3

Aquí está mi solución al problema. Calculo todas las combinaciones posibles de k de n elementos y calculo sus dependencias mutuas transformando el problema en un gráfico teórico: ¿Cuál es el gráfico completo que contiene todos los k nodos con la suma de bordes más pequeña (dependencias)? Aquí hay un script de Python que usa la biblioteca networkx y una salida posible. ¡Por favor, discúlpese por cualquier ambigüedad en mi pregunta!

Código:

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)

Salida de muestra:

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]

Gráfico de entrada: ingrese la descripción de la imagen aquí

Gráfico de solución: ingrese la descripción de la imagen aquí

Para un ejemplo de juguete, k = 4, n = 6: Gráfico de entrada: ingrese la descripción de la imagen aquí

Gráfico de solución: ingrese la descripción de la imagen aquí

Mejor,

cristiano

Chris
fuente
1
Esta podría ser una buena solución. Pero para apreciarlo, a uno le gustaría ver el gráfico (la matriz) en sí y la solución como gráfico. No solo el código y la salida.
ttnphns
@ttnphns: agregué gráficos de los gráficos resultantes y un ejemplo de juguete.
Chris
@ Chris Gracias por documentar su solución. ¿Podría agregar una o dos oraciones sobre cuánto tiempo tardó en ejecutarse y cómo se escala con el número de nodos / dimensiones?
Casimir
@Casimir: mis disculpas por no incluir esta información por adelantado. Sin embargo, en este punto, esta publicación tiene más de 5 años y ya no tengo la información a la mano. Siéntase libre de copiar y pegar el código y hacer estimaciones de tiempo de ejecución aplicadas o teóricas. Agradecería la adición a la publicación.
Chris
1
Por lo tanto, vale la pena mencionar que en los casos en que el número de dimensiones es de cientos o incluso miles, este enfoque no es factible. ¡Pero sigue siendo una forma genial de resolver esto para problemas pequeños!
Casimir
2

Encuentre de elementos con la menor correlación por pares: dado que una correlación de digamos explica de la relación entre dos series, tiene más sentido minimizar la suma de los cuadrados de correlaciones para sus elementos objetivo . Aquí está mi solución simple.kn0.60.36k

Reescribe tu matriz de correlaciones en una matriz de cuadrados de correlaciones. Suma los cuadrados de cada columna. Eliminar la columna y la fila correspondiente con la mayor suma. Ahora tiene una matriz . Repita hasta que tenga una matriz . También podría mantener las columnas y las filas correspondientes con las sumas más pequeñas. Al comparar los métodos, encontré en una matriz con y que solo dos elementos con sumas cercanas se mantuvieron y eliminaron de manera diferente.n×n(n1)×(n1)k×kkn=43k=20

Jon Arts
fuente
1
Probé este método y lo comparé con el método gráfico de buscar cada subgrafo y aunque este método no proporcionó la respuesta más óptima, proporcionó una de las 5 mejores combinaciones y, por supuesto, es mucho más rápido.
SamFisher83