Mengelompokkan matriks korelasi

20

Saya memiliki matriks korelasi yang menyatakan bagaimana setiap item berkorelasi dengan item lainnya. Karenanya untuk item N, saya sudah memiliki matriks korelasi N * N. Dengan menggunakan matriks korelasi ini, bagaimana cara mengelompokkan item N dalam M bin sehingga saya dapat mengatakan bahwa Item Nk di kth bin berperilaku sama. Mohon bantu saya. Semua nilai item bersifat kategoris.

Terima kasih. Beri tahu saya jika Anda memerlukan informasi lebih lanjut. Saya membutuhkan solusi dengan Python tetapi bantuan dalam mendorong saya ke arah persyaratan akan sangat membantu.

Abhishek093
sumber
seberapa besar biasanya N?
Rodin
1
Saya tidak memerlukan pengelompokan hierarkis untuk masalah saya. Hanya perlu memberi tahu item mana yang berperilaku juga.
Abhishek093
N biasanya 250 - 300.
Abhishek093
3
FYI, masalah ini disebut bi-clustering. Demo itu dapat ditemukan di scikit-learn.org/stable/auto_examples/bicluster/…
chanp

Jawaban:

15

Sepertinya pekerjaan untuk pemodelan blok. Google untuk "blokir pemodelan" dan beberapa hit pertama sangat membantu.

Katakanlah kita memiliki matriks kovarians di mana N = 100 dan sebenarnya ada 5 klaster: Matriks kovarians awal

Apa yang coba dilakukan pemodelan blok adalah menemukan urutan baris, sehingga cluster menjadi jelas sebagai 'blok': Urutan matriks kovarians yang dioptimalkan

Di bawah ini adalah contoh kode yang melakukan pencarian serakah dasar untuk mencapai ini. Mungkin terlalu lambat untuk variabel 250-300 Anda, tapi ini awal. Lihat apakah Anda dapat mengikuti dengan komentar:

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
sumber
Bukankah itu teknik yang digunakan untuk pengelompokan Jejaring Sosial? Apakah itu relevan di sini? Apakah masuk akal untuk menggunakan matriks korelasi sebagai matriks jarak?
Abhishek093
1) Ya, 2) Saya kira begitu, 3) Ya (nilai-nilai yang sangat berkorelasi dekat)
Rodin
Baik. Saya melihat melalui beberapa tautan pertama. Saya masih tidak tahu bagaimana ini akan membantu saya memecahkan masalah saya.
Abhishek093
Saya sudah mengedit jawaban saya. Semoga bermanfaat bagi Anda.
Rodin
Saya akan memeriksanya sekarang. Saya akan memberi tahu Anda jika itu sesuai dengan masalah saya. Terima kasih banyak.
Abhishek093
6

Sudahkah Anda melihat pengelompokan hierarkis? Ia dapat bekerja dengan kesamaan, tidak hanya jarak. Anda dapat memotong dendrogram pada ketinggian di mana ia terbagi menjadi beberapa k, tetapi biasanya lebih baik untuk memeriksa dendrogram secara visual dan memutuskan ketinggian yang akan dipotong.

Hierarchical clustering juga sering digunakan untuk menghasilkan penataan ulang yang cerdas untuk vidualisasi matriks kesamaan seperti yang terlihat pada jawaban lain: ia menempatkan entri yang lebih mirip di sebelah satu sama lain. Ini juga bisa berfungsi sebagai alat validasi bagi pengguna!

Anony-Mousse -Reinstate Monica
sumber
2

Sudahkah Anda melihat pengelompokan korelasi ? Algoritma pengelompokan ini menggunakan informasi korelasi positif / negatif pasangan-bijaksana untuk secara otomatis mengusulkan jumlah cluster optimal dengan fungsional yang baik dan interpretasi probabilistik generatif yang ketat .

Shai
sumber
Artikel Wikipedia yang dipromosikan: Correlation clustering provides a method for clustering a set of objects into the optimum number of clusters without specifying that number in advance. Apakah itu definisi metode? Jika ya itu aneh karena ada metode lain untuk secara otomatis menyarankan jumlah cluster, dan juga, mengapa kemudian disebut "korelasi".
ttnphns
@ttnphns (1) itu disebut "clustering korelasi" karena diharapkan sebagai input matriks korelasi pasangan-bijaksana (lihat karya mani Bansal, N.; Blum, A.; Chawla, S. (2004). "Correlation Clustering ". Pembelajaran Mesin. 56: 89).
Shai
@ttnphns mengenai "jumlah cluster optimal": Anda benar tentang fakta bahwa "optimal" adalah ambigu, "optimal" di bawah ukuran apa? Adapun pengelompokan korelasi, jika Anda menerima model generatif yang diusulkan dalam Bagon & Galun "Clustering Korelasi Skala Besar" , maka metode ini menghasilkan angka yang optimal.
Shai
Shai, tampaknya Anda adalah salah satu penemu metode ini. Saya akan mendorong Anda untuk memberikan jawaban yang lebih terbuka dan menyajikannya - jika Anda punya waktu dan keinginan. Secara khusus, seseorang ingin tahu bagaimana metode ini ditempatkan di antara beberapa metode yang sudah mapan, seperti k-means atau hierarkis. Perhatikan juga korelasi mudah dikonversi ke jarak euclidean (dengan metode pengelompokan standar yang berlaku setelah itu), - mengetahui fakta / trik, lalu hal-hal apa yang memungkinkan metode Anda yang mana "trik" tidak memungkinkan? Tulis tentang itu. (Terima kasih sebelumnya!)
ttnphns
1
Saya harap ini mencakup. Saya hanya ingin mengatakan bahwa itu selalu merupakan ide yang baik untuk memberikan sedikit lebih banyak rincian dalam jawaban yang diposting di situs ini, terutama ketika suatu metode agak baru dan ketika ada yang tahu harus berkata apa, menjadi seorang penemu. :-) Tidak, tidak "terlalu luas".
ttnphns
-1

Saya akan menyaring pada beberapa ambang batas yang bermakna (signifikansi statistik) dan kemudian menggunakan dekomposisi dulmage-mendelsohn untuk mendapatkan komponen yang terhubung. Mungkin sebelum Anda dapat mencoba untuk menghapus beberapa masalah seperti korelasi transitif (A sangat berkorelasi dengan B, B ke C, C ke D, jadi ada komponen yang mengandung semuanya, tetapi pada kenyataannya D ke A rendah). Anda dapat menggunakan beberapa algoritma berbasis antar Ini bukan masalah biklustering seperti yang disarankan seseorang, karena matriks korelasi simetris dan karenanya tidak ada bi-sesuatu.

pengguna2843263
sumber
Jawaban ini tidak cukup menjelaskan bagaimana mengatur ambang yang disarankan, yang IMO tampaknya sewenang-wenang. Selain itu, karena pertanyaan ini berumur dua tahun, dan jawaban dengan beberapa peningkatan telah diterima, Anda mungkin ingin menguraikan informasi yang sudah ada.
IWS