Kapan kita menggabungkan reduksi dimensi dengan pengelompokan?

16

Saya mencoba melakukan pengelompokan tingkat dokumen. Saya membangun matriks frekuensi istilah-dokumen dan saya mencoba mengelompokkan vektor-vektor dimensi tinggi ini menggunakan k-means. Alih-alih langsung mengelompokkan, apa yang saya lakukan adalah pertama-tama menerapkan dekomposisi vektor singular LSA (Latent Semantic Analysis) untuk mendapatkan matriks U, S, Vt, memilih ambang yang sesuai menggunakan plot scree dan pengelompokan yang diterapkan pada matriks yang dikurangi (khususnya Vt karena itu memberi saya informasi konsep-dokumen) yang sepertinya memberi saya hasil yang baik.

Saya pernah mendengar beberapa orang mengatakan SVD (dekomposisi vektor singular) adalah pengelompokan (dengan menggunakan ukuran kesamaan cosinus, dll.) Dan tidak yakin apakah saya dapat menerapkan k-means pada output SVD. Saya pikir itu secara logis benar karena SVD adalah teknik pengurangan dimensionalitas, memberi saya banyak vektor baru. k-means, di sisi lain, akan mengambil jumlah cluster sebagai input dan membagi vektor-vektor ini ke dalam jumlah cluster yang ditentukan. Apakah prosedur ini cacat atau adakah cara agar hal ini dapat diperbaiki? Ada saran?

Legenda
sumber
Pertanyaan bagus. secara pribadi saya telah memikirkan hal-hal ini. tetapi tidak memiliki jawaban yang bagus.
suncoolsu
1
Ada metode yang secara bersamaan melakukan reduksi dimensi dan pengelompokan. Metode-metode ini mencari representasi dimensi rendah yang dipilih secara optimal sehingga memudahkan identifikasi cluster. Sebagai contoh, lihat paket clustrd di R dan referensi terkait.
Nat

Jawaban:

6

Ini sama sekali bukan jawaban yang lengkap, pertanyaan yang harus Anda tanyakan adalah "jarak seperti apa yang dipertahankan ketika melakukan pengurangan dimensionalitas?". Karena algoritma pengelompokan seperti K-means hanya beroperasi pada jarak, metrik jarak yang tepat untuk digunakan (secara teoritis) adalah metrik jarak yang dipertahankan oleh reduksi dimensi. Dengan cara ini, langkah reduksi dimensi dapat dilihat sebagai jalan pintas komputasi untuk mengelompokkan data dalam ruang dimensi yang lebih rendah. (juga untuk menghindari minimum lokal, dll)

Ada banyak seluk-beluk di sini yang saya tidak akan berpura-pura mengerti, (jarak lokal vs jarak global, bagaimana jarak relatif terdistorsi, dll) tapi saya pikir ini adalah arah yang tepat untuk memikirkan hal-hal ini secara teoritis.

gabgoh
sumber
+1 Itu pertanyaan yang sangat menarik. Dalam hal itu, dapatkah Euclidean dianggap sebagai satu metrik seperti itu? Ketika dimensi berkurang, titik-titik diproyeksikan ke ruang dimensi yang lebih rendah tetapi itu bisa berarti gagasan jarak dapat hilang. Saya mengalami kesulitan untuk melihat bagaimana jarak dapat dipertahankan saat menggunakan reduksi seperti ini.
Legenda
1
Saya pikir jawaban ini pada dasarnya benar. Anda ingin menemukan beberapa penyematan dalam ruang yang lebih kecil yang menjaga jarak (untuk beberapa gagasan jarak). Dua algoritma yang baik untuk dicoba adalah Isomap dan Locally-Linear Embedding . "Pelestarian lingkungan" tampaknya merupakan pendekatan yang baik jika tujuan Anda mengelompok.
Stumpy Joe Pete
5

Sebagai balasan untuk judul Anda "Kapan kita menggabungkan pengurangan dimensi dengan pengelompokan?" alih-alih pertanyaan lengkap. Salah satu alasan yang mungkin jelas: ketika kita ingin mengamankan outlier agais. K-means algo, jika tanpa petunjuk pusat awal, mengambil k poin paling terpisah di cloud sebagai pusat awal, dan benar ini cenderung outlier. Beraksi dengan PCA menetralkan outliers yang terletak di sepanjang komponen junior - dengan memproyeksikannya ke beberapa komponen senior yang disimpan dalam PCA.

ttnphns
sumber