Clustering einer Korrelationsmatrix

20

Ich habe eine Korrelationsmatrix, die angibt, wie jedes Objekt mit dem anderen Objekt korreliert ist. Daher habe ich für N Elemente bereits eine N * N Korrelationsmatrix. Wie gruppiere ich mit dieser Korrelationsmatrix die N Elemente in M ​​Fächern, damit ich sagen kann, dass sich die Nk Elemente im k-ten Fach gleich verhalten. Bitte hilf mir raus. Alle Artikelwerte sind kategorisch.

Vielen Dank. Lassen Sie mich wissen, wenn Sie weitere Informationen benötigen. Ich brauche eine Lösung in Python, aber jede Hilfe, um mich an die Anforderungen heranzuführen, wird eine große Hilfe sein.

Abhishek093
quelle
Wie groß ist N normalerweise?
Rodin
1
Ich brauche kein hierarchisches Clustering für mein Problem. Ich muss nur sagen, welche Elemente sich ebenfalls verhalten.
Abhishek093
N ist in der Regel 250 - 300.
Abhishek093
3
Zu Ihrer Information wird dieses Problem als Bi-Clustering bezeichnet. Eine Demo davon finden Sie unter scikit-learn.org/stable/auto_examples/bicluster/…
chanp

Antworten:

15

Sieht aus wie ein Job für die Blockmodellierung. Google für "Blockmodellierung" und die ersten Treffer sind hilfreich.

Nehmen wir an, wir haben eine Kovarianzmatrix mit N = 100 und es gibt tatsächlich 5 Cluster: Anfängliche Kovarianzmatrix

Bei der Blockmodellierung wird versucht, eine Reihenfolge der Zeilen zu finden, sodass die Cluster als "Blöcke" sichtbar werden: Optimierte Kovarianzmatrixreihenfolge

Unten finden Sie ein Codebeispiel, mit dem eine einfache Suche durchgeführt wird, um dies zu erreichen. Es ist wahrscheinlich zu langsam für Ihre 250-300 Variablen, aber es ist ein Anfang. Sehen Sie, ob Sie den Kommentaren folgen können:

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
quelle
Wird diese Technik nicht für das Clustering sozialer Netzwerke verwendet? Wird das hier relevant sein? Ist es sinnvoll, diese Korrelationsmatrix als Distanzmatrix zu verwenden?
Abhishek093
1) Ja, 2) Ich denke schon, 3) Ja (Werte, die stark korrelieren, sind eng)
Rodin
Okay. Ich habe die ersten Links durchgesehen. Ich weiß immer noch nicht, wie ich mein Problem lösen kann.
Abhishek093
Ich habe meine Antwort bearbeitet. Ich hoffe, es ist nützlich für Sie.
Rodin
Ich werde es jetzt überprüfen. Ich werde Sie wissen lassen, ob es zu meinem Problem passt. Ich danke dir sehr.
Abhishek093
6

Haben Sie sich mit hierarchischem Clustering befasst? Es kann mit Ähnlichkeiten arbeiten, nicht nur mit Entfernungen. Sie können das Dendrogramm in einer Höhe schneiden, in der es sich in k Cluster aufteilt. In der Regel ist es jedoch besser, das Dendrogramm visuell zu überprüfen und eine Schnitthöhe festzulegen.

Hierarchisches Clustering wird auch häufig verwendet, um eine geschickte Neuordnung für eine Ähnlichkeitsmatrix-Visualisierung zu erzeugen, wie in der anderen Antwort zu sehen ist: Es platziert mehr ähnliche Einträge nebeneinander. Dies kann auch dem Benutzer als Validierungswerkzeug dienen!

Anony-Mousse
quelle
2

Haben Sie sich mit Korrelationsclustern befasst ? Dieser Cluster-Algorithmus verwendet die paarweise positive / negative Korrelationsinformation, um automatisch die optimale Anzahl von Clustern mit einer genau definierten funktionalen und einer strengen generativen probabilistischen Interpretation vorzuschlagen .

Shai
quelle
Der geförderte Wikipedia - Artikel: Correlation clustering provides a method for clustering a set of objects into the optimum number of clusters without specifying that number in advance. Ist das eine Definition der Methode? Wenn ja, ist es seltsam, weil es andere Methoden gibt, um die Anzahl der Cluster automatisch vorzuschlagen, und auch, warum heißt es dann "Korrelation".
TTNPHNS
@ttnphns (1) wird "Korrelationsclustering" genannt, weil es als Eingabe eine paarweise Korrelationsmatrix erwartet (siehe die wegweisende Arbeit von Bansal, N.; Blum, A.; Chawla, S. (2004). "Korrelationsclustering ". Maschinelles Lernen. 56: 89).
Shai
@ttnphns zur "optimalen Anzahl von Clustern": Sie haben Recht damit, dass "optimal" mehrdeutig ist, "optimal" in welchem ​​Maße? Wenn Sie für das Korrelationsclustering das in Bagon & Galun vorgeschlagene generative Modell "Large Scale Correlation Clustering" akzeptieren , gibt die Methode die optimale Zahl aus.
Shai
Shai, Sie scheinen einer der Erfinder der Methode zu sein. Ich würde Sie ermutigen, eine unverpackte Antwort zu geben, wenn Sie Zeit und Lust haben. Insbesondere möchte man wissen, wie die Methode unter einigen gut etablierten Methoden wie k-means oder hierarhical zu finden ist. Beachten Sie auch, dass die Korrelation leicht in eine euklidische Distanz konvertierbar ist (mit jeder danach anwendbaren Standard-Clustering-Methode). - Wenn Sie diese Tatsache / diesen Trick kennen, welche Dinge erlaubt Ihre Methode dann, was dieser "Trick" nicht erlaubt? Schreibe darüber. (Danke im Voraus!)
TTNPHNS
1
Ich hoffe es deckt. Ich wollte nur sagen, dass es immer eine gute Idee ist, in einer Antwort auf dieser Website ein bisschen mehr Details zu nennen, besonders wenn eine Methode ziemlich neu ist und man weiß, was man sagen soll, wenn man ein Erfinder ist. :-) Nein, ist nicht "zu breit".
TTNPHNS
-1

Ich würde bei einer sinnvollen (statistischen Signifikanz) Schwelle filtern und dann die Hackfleisch-Mendelsohn-Zerlegung verwenden, um die verbundenen Komponenten zu erhalten. Vielleicht, bevor Sie versuchen können, ein Problem wie die transitiven Korrelationen zu beseitigen (A korreliert stark mit B, B mit C, C mit D, es gibt also eine Komponente, die alle enthält, aber tatsächlich ist D mit A niedrig). Sie können einen Algorithmus auf der Basis von Zwischenwissen verwenden. Es ist kein Biclustering-Problem, wie von jemandem vorgeschlagen, da die Korrelationsmatrix symmetrisch ist und es daher kein Bi-Etwas gibt.

user2843263
quelle
Diese Antwort erklärt nicht ganz, wie die vorgeschlagenen Schwellenwerte festgelegt werden sollen, was IMO willkürlich erscheint. Da diese Frage zwei Jahre alt ist und eine Antwort mit einigen positiven Stimmen bereits akzeptiert wurde, möchten Sie möglicherweise die bereits vorhandenen Informationen näher erläutern.
IWS