Agrupación de una matriz de correlación

Question

Tengo una matriz de correlación que indica cómo se correlaciona cada elemento con el otro. Por lo tanto, para N elementos, ya tengo una matriz de correlación N*N. Utilizando esta matriz de correlaciones, ¿cómo puedo agrupar los N elementos en M contenedores para poder decir que los Nk elementos del kº contenedor se comportan igual? Por favor, ayúdeme. Todos los valores de los ítems son categóricos.

Gracias. Hazme saber si necesitas más información. Necesito una solución en Python, pero cualquier ayuda que me empuje hacia los requisitos será de gran ayuda.

Answer 1

Parece un trabajo para el modelado de bloques. Busca en Google "modelado de bloques" y los primeros resultados son útiles.

Digamos que tenemos una matriz de covarianza en la que N=100 y en realidad hay 5 clusters:

Lo que trata de hacer la modelización por bloques es encontrar una ordenación de las filas, de modo que los grupos se manifiesten como "bloques":

A continuación se muestra un ejemplo de código que realiza una búsqueda codiciosa básica para lograr esto. Probablemente sea demasiado lento para tus 250-300 variables, pero es un comienzo. Mira si puedes seguir con los comentarios:

import numpy as np
from matplotlib import pyplot as plt

# This generates 100 variables that could possibly be assigned to 5 clusters
n_variables = 100
n_clusters = 5
n_samples = 1000

# To keep this example simple, each cluster will have a fixed size
cluster_size = n_variables // n_clusters

# Assign each variable to a cluster
belongs_to_cluster = np.repeat(range(n_clusters), cluster_size)
np.random.shuffle(belongs_to_cluster)

# This latent data is used to make variables that belong
# to the same cluster correlated.
latent = np.random.randn(n_clusters, n_samples)

variables = []
for i in range(n_variables):
    variables.append(
        np.random.randn(n_samples) + latent[belongs_to_cluster[i], :]
    )

variables = np.array(variables)

C = np.cov(variables)

def score(C):
    '''
    Function to assign a score to an ordered covariance matrix.
    High correlations within a cluster improve the score.
    High correlations between clusters decease the score.
    '''
    score = 0
    for cluster in range(n_clusters):
        inside_cluster = np.arange(cluster_size) + cluster * cluster_size
        outside_cluster = np.setdiff1d(range(n_variables), inside_cluster)

        # Belonging to the same cluster
        score += np.sum(C[inside_cluster, :][:, inside_cluster])

        # Belonging to different clusters
        score -= np.sum(C[inside_cluster, :][:, outside_cluster])
        score -= np.sum(C[outside_cluster, :][:, inside_cluster])

    return score

initial_C = C
initial_score = score(C)
initial_ordering = np.arange(n_variables)

plt.figure()
plt.imshow(C, interpolation='nearest')
plt.title('Initial C')
print 'Initial ordering:', initial_ordering
print 'Initial covariance matrix score:', initial_score

# Pretty dumb greedy optimization algorithm that continuously
# swaps rows to improve the score
def swap_rows(C, var1, var2):
    '''
    Function to swap two rows in a covariance matrix,
    updating the appropriate columns as well.
    '''
    D = C.copy()
    D[var2, :] = C[var1, :]
    D[var1, :] = C[var2, :]

    E = D.copy()
    E[:, var2] = D[:, var1]
    E[:, var1] = D[:, var2]

    return E

current_C = C
current_ordering = initial_ordering
current_score = initial_score

max_iter = 1000
for i in range(max_iter):
    # Find the best row swap to make
    best_C = current_C
    best_ordering = current_ordering
    best_score = current_score
    for row1 in range(n_variables):
        for row2 in range(n_variables):
            if row1 == row2:
                continue
            option_ordering = best_ordering.copy()
            option_ordering[row1] = best_ordering[row2]
            option_ordering[row2] = best_ordering[row1]
            option_C = swap_rows(best_C, row1, row2)
            option_score = score(option_C)

            if option_score > best_score:
                best_C = option_C
                best_ordering = option_ordering
                best_score = option_score

    if best_score > current_score:
        # Perform the best row swap
        current_C = best_C
        current_ordering = best_ordering
        current_score = best_score
    else:
        # No row swap found that improves the solution, we're done
        break

# Output the result
plt.figure()
plt.imshow(current_C, interpolation='nearest')
plt.title('Best C')
print 'Best ordering:', current_ordering
print 'Best score:', current_score
print
print 'Cluster     [variables assigned to this cluster]'
print '------------------------------------------------'
for cluster in range(n_clusters):
    print 'Cluster %02d  %s' % (cluster + 1, current_ordering[cluster*cluster_size:(cluster+1)*cluster_size])

Answer 2

¿Ha mirado la agrupación jerárquica? Puede trabajar con similitudes, no sólo con distancias. Puedes cortar el dendrograma a una altura en la que se divide en k clusters, pero normalmente es mejor inspeccionar visualmente el dendrograma y decidir la altura a cortar.

La agrupación jerárquica también se utiliza a menudo para producir una reordenación inteligente para la visualización de una matriz de similitud, como se ve en la otra respuesta: coloca las entradas más similares una al lado de la otra. Esto también puede servir como herramienta de validación para el usuario.

Answer 3

¿Has mirado en agrupación de correlación ? Este algoritmo de agrupación utiliza la información de correlación positiva/negativa por pares para automáticamente proponer el número óptimo de conglomerados con un funcional bien definido y un riguroso interpretación probabilística generativa .

Answer 4

Yo filtraría en algún umbral significativo (de significación estadística) y luego utilizaría la descomposición dulmage-mendelsohn para obtener los componentes conectados. Tal vez antes de intentar eliminar algún problema como las correlaciones transitivas (A altamente correlacionado con B, B con C, C con D, por lo que hay un componente que los contiene a todos, pero en realidad D con A es bajo). se puede utilizar algún algoritmo basado en la interrelación. No es un problema de biclustering como alguien sugirió, ya que la matriz de correlación es simétrica y por lo tanto no hay biclustering.