Regroupement d'une matrice de corrélation

20

J'ai une matrice de corrélation qui indique comment chaque élément est corrélé à l'autre élément. Donc pour un N items, j'ai déjà une matrice de corrélation N * N. En utilisant cette matrice de corrélation, comment puis-je regrouper les N éléments dans M bacs afin que je puisse dire que les Nk éléments dans le kième bac se comportent de la même manière. Veuillez m'aider. Toutes les valeurs des éléments sont catégoriques.

Merci. Faites-moi savoir si vous avez besoin de plus d'informations. J'ai besoin d'une solution en Python mais toute aide pour me pousser vers les exigences sera d'une grande aide.

Abhishek093
la source
quelle est la taille de N en général?
Rodin
1
Je n'ai pas besoin d'un clustering hiérarchique pour mon problème. Il suffit de dire quels éléments se comportent de la même manière.
Abhishek093
N est généralement de 250 à 300.
Abhishek093
3
Pour info, ce problème est appelé bi-clustering. Une démo peut être trouvée sur scikit-learn.org/stable/auto_examples/bicluster/…
chanp

Réponses:

15

Ressemble à un travail de modélisation de blocs. Google pour la "modélisation de blocs" et les premiers hits sont utiles.

Disons que nous avons une matrice de covariance où N = 100 et il y a en fait 5 grappes: Matrice de covariance initiale

Ce que la modélisation de blocs essaie de faire est de trouver un ordre des lignes, de sorte que les clusters deviennent apparents comme des «blocs»: Ordre de matrice de covariance optimisé

Voici un exemple de code qui effectue une recherche gourmande de base pour y parvenir. C'est probablement trop lent pour vos variables 250-300, mais c'est un début. Voyez si vous pouvez suivre les commentaires:

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])
Rodin
la source
Cette technique n'est-elle pas utilisée pour le clustering des réseaux sociaux? Est-ce que cela sera pertinent ici? Est-il judicieux d'utiliser cette matrice de corrélation comme matrice de distance?
Abhishek093
1) Oui, 2) Je pense que oui, 3) Oui (les valeurs qui sont fortement corrélées sont proches)
Rodin
D'accord. J'ai vu à travers les premiers liens. Je ne sais toujours pas comment cela va m'aider à résoudre mon problème.
Abhishek093
J'ai édité ma réponse. J'espère que cela vous sera utile.
Rodin
Je vais le vérifier maintenant. Je vous ferai savoir si cela correspond à mon problème. Merci beaucoup.
Abhishek093
6

Avez-vous envisagé le clustering hiérarchique? Il peut fonctionner avec des similitudes, pas seulement des distances. Vous pouvez couper le dendrogramme à une hauteur où il se divise en k grappes, mais il est généralement préférable d'inspecter visuellement le dendrogramme et de décider d'une hauteur à couper.

Le clustering hiérarchique est également souvent utilisé pour produire un réordonnancement intelligent pour une visualisation de matrice de similitude, comme indiqué dans l'autre réponse: il place plus d'entrées similaires les unes à côté des autres. Cela peut également servir d'outil de validation pour l'utilisateur!

Anony-Mousse -Reinstate Monica
la source
2

Avez-vous étudié le clustering de corrélation ? Cet algorithme de clustering utilise les informations de corrélation positive / négative par paire pour proposer automatiquement le nombre optimal de clusters avec une fonctionnalité bien définie et une interprétation probabiliste générative rigoureuse .

Shai
la source
Le promu article de Wikipédia: Correlation clustering provides a method for clustering a set of objects into the optimum number of clusters without specifying that number in advance. Est-ce une définition de la méthode? Si oui c'est étrange car il existe d'autres méthodes pour suggérer automatiquement le nombre de clusters, et aussi, pourquoi alors cela s'appelle-t-il "corrélation".
ttnphns
@ttnphns (1), il est appelé "cluster de corrélation" car il attend en entrée une matrice de corrélation par paire (voir le travail séminal de Bansal, N .; Blum, A .; Chawla, S. (2004). "Correlation Clustering ". Apprentissage automatique. 56: 89).
Shai
@ttnphns concernant le "nombre optimal de clusters": vous avez raison sur le fait que "optimal" est ambigu, "optimal" dans quelle mesure? En ce qui concerne le clustering de corrélation, si vous acceptez le modèle génératif proposé dans Bagon & Galun "Clustering de corrélation à grande échelle" , alors la méthode génère le nombre optimal.
Shai
Shai, il semble que vous soyez l'un des inventeurs de la méthode. Je vous encourage à donner une réponse plus simple en la présentant - si vous avez le temps et le désir. Plus précisément, on veut savoir comment la méthode est placée parmi certaines bien établies, telles que k-means ou hiérarchique. Notez également que la corrélation est facilement convertible en distance euclidienne (avec toute méthode de clustering standard applicable par la suite), - sachant ce fait / astuce, quelles sont les choses que votre méthode autorise alors que cette "astuce" ne permet pas? Écrire à ce sujet. (Merci d'avance!)
ttnphns
1
J'espère que ça couvre. Je voulais juste dire que c'est toujours une bonne idée de donner un peu plus de détails dans une réponse postée sur ce site, surtout quand une méthode est plutôt nouvelle et quand on sait quoi dire, être inventeur. :-) Non, ce n'est pas "trop ​​large".
ttnphns
-1

Je filtrerais à un seuil significatif (signification statistique), puis utiliserais la décomposition dulmage-mendelsohn pour obtenir les composants connectés. Peut-être avant de pouvoir essayer de supprimer certains problèmes comme les corrélations transitives (A fortement corrélé à B, B à C, C à D, il existe donc un composant les contenant tous, mais en fait D à A est faible). vous pouvez utiliser un algorithme basé sur l'interdépendance. Ce n'est pas un problème de biclustering comme quelqu'un l'a suggéré, car la matrice de corrélation est symétrique et donc il n'y a pas de bi-quelque chose.

user2843263
la source
Cette réponse n'explique pas tout à fait comment fixer les seuils suggérés, ce que l'OMI semble arbitraire. De plus, comme cette question a deux ans et qu'une réponse avec quelques votes positifs a déjà été acceptée, vous voudrez peut-être développer les informations déjà existantes.
IWS