Encontre k de n itens com menos correlações aos pares

Eu tenho uma matriz de correlações aos pares entre n itens. Agora, quero encontrar um subconjunto de k itens com a menor correlação. Portanto, existem duas perguntas:

1. Qual é a medida apropriada para a correlação dentro desse grupo?
2. Como encontrar o grupo com a menor correlação?

Esse problema parece um tipo de análise fatorial inversa para mim e tenho certeza de que existe uma solução direta.

Eu acho que esse problema é igual ao problema de remover nós (nk) de um gráfico completo para que os nós restantes sejam conectados com pesos mínimos de borda. O que você acha?

Agradecemos desde já as suas sugestões!

[Aviso prévio: esta resposta apareceu antes do OP decidir reformular a pergunta, para que pudesse ter perdido relevância. Originalmente, a pergunta era sobre How to rank items according to their pairwise correlations]

Como a matriz de correlações aos pares não é uma matriz unidimensional, não está claro como pode ser a "classificação". Especialmente desde que você não tenha elaborado sua idéia em detalhes, ao que parece. Mas você mencionou o PCA como adequado para você, e isso imediatamente me fez pensar na raiz de Cholesky como uma alternativa potencialmente ainda mais adequada.

A raiz de Cholesky é como uma matriz de cargas deixadas pelo PCA, mas é triangular. Vou explicar os dois com um exemplo.

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

A matriz de carregamento A do PCA é a matriz de correlações entre as variáveis ​​e os principais componentes. Podemos dizer isso porque as somas de linhas dos quadrados são todas 1 (a diagonal de R), enquanto a soma dos quadrados da matriz é a variação geral (traço de R). Os elementos B da raiz de Cholesky também são correlações, porque essa matriz também possui essas duas propriedades. As colunas de B não são componentes principais de A, embora sejam "componentes", em certo sentido.

Ambos A e B podem restaurar R e, portanto, ambos podem substituir R, como sua representação. B é triangular, o que mostra claramente o fato de capturar as correlações aos pares de R sequencialmente ou hierarquicamente. O componente de Cholesky se Icorrelaciona com todas as variáveis ​​e é a imagem linear da primeira delas V1. O componente IInão compartilha mais com, V1mas se correlaciona com os três últimos ... Finalmente, IVé correlacionado apenas com o último V4,. Eu pensei que esse tipo de "ranking" é talvez o que você procura ?

O problema com a decomposição de Cholesky, porém, é que - diferentemente do PCA - depende da ordem dos itens na matriz R. Bem, você pode classificar os itens em ordem decrescente ou crescente da soma dos elementos ao quadrado (ou, se desejar , soma dos elementos absolutos ou na ordem do coeficiente de correlação múltipla - veja abaixo). Essa ordem reflete o quanto um item está correlacionado bruto.

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

Da última matriz B, vemos que V2, o item mais grosseiramente correlacionado, penhor todas as suas correlações em I. O próximo item grosseiramente correlacionado V1penhora toda a sua correlação, exceto com V2, in II; e assim por diante.

Outra decisão pode ser calcular o coeficiente de correlação múltipla para cada item e classificar com base em sua magnitude. A correlação múltipla entre um item e todos os outros itens aumenta à medida que o item se correlaciona mais com todos eles, mas eles se correlacionam menos entre si. Os coeficientes de correlação múltipla ao quadrado formam a diagonal da chamada matriz de covariância da imagem que é , onde é a matriz diagonal dos recíprocos das diagonais de .S R - $\bf S R^{-1} S - 2S + R$$\bf S$$\bf R^{-1}$

Aqui está a minha solução para o problema. Calculo todas as combinações possíveis de k de n itens e calculo suas dependências mútuas, transformando o problema em gráfico-teórico: Qual é o gráfico completo que contém todos os nós de k com a menor soma de arestas (dependências)? Aqui está um script python usando a biblioteca networkx e uma saída possível. Peço desculpas por qualquer ambiguidade na minha pergunta!

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)

Saída de amostra:

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:

Gráfico da solução:

Para um exemplo de brinquedo, k = 4, n = 6: Gráfico de entrada:

Gráfico da solução:

melhor,

cristão

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.n 0,6 0,36 $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 - 1 ) × ( n - 1 ) k × k k n = 43 k = $n \times n$$(n-1) \times (n-1)$$k \times k$$k$$n=43$$k=20$