Apakah ada kasus di mana tidak ada k optimal dalam k-means?

11

Ini sudah ada dalam pikiran saya selama setidaknya beberapa jam. Saya mencoba menemukan k yang optimal untuk output dari algoritma k-means (dengan metrik kesamaan cosine ) jadi saya akhirnya merencanakan distorsi sebagai fungsi dari jumlah cluster. Dataset saya adalah kumpulan 800 dokumen dalam ruang 600 dimensi.

Dari apa yang saya mengerti, menemukan titik lutut atau titik siku pada kurva ini harus memberi tahu saya setidaknya tentang jumlah cluster yang saya butuhkan untuk memasukkan data saya. Saya meletakkan grafik di bawah ini. Titik di mana garis merah vertikal ditarik diperoleh dengan menggunakan tes turunan maksimum kedua . Setelah melakukan semua ini, saya terjebak pada sesuatu yang lebih sederhana: apa yang diceritakan grafik ini tentang dataset?

Apakah ini memberitahu saya bahwa itu tidak layak untuk dikelompokkan dan dokumen saya tidak memiliki struktur atau saya perlu menetapkan k yang sangat tinggi? Satu hal yang aneh adalah bahwa meskipun dengan k rendah, saya melihat dokumen serupa dikelompokkan jadi saya tidak yakin mengapa saya mendapatkan kurva ini. Adakah pikiran?

masukkan deskripsi gambar di sini

machine-learning clustering k-means Legenda
sumber
2
Apa yang saya benar-benar tidak mengerti adalah bagaimana Anda bisa menggunakan pengelompokan k-means dengan input matriks kedekatan (dan yang menjadi cosinus!). K-means clustering membutuhkan input data mentah (objek X variabel) dan beroperasi secara internal pada jarak euclidean.
ttnphns
2
@ttnphns: Saya harap saya mengerti maksud Anda tetapi sejauh yang saya ketahui, kita bisa menggunakan metrik jarak dengan k-means bukan? Saya melakukan ini dengan Python tetapi sepertinya bahkan ada perpustakaan yang tersedia untuk R: cran.r-project.org/web/packages/skmeans/index.html Inputnya bukan matriks kedekatan, melainkan terms x documentdiperoleh setelah melakukan vektor tunggal penguraian. Harap perbaiki saya jika saya salah.
Legenda
Klaster k-means bulat , berdasarkan ukuran cosinus, adalah hal baru bagi saya, harus saya akui. Saya berharap untuk membaca lebih banyak tentang itu suatu hari nanti.
ttnphns
@ttnphns: Terima kasih telah kembali. Hanya ingin memastikan saya tidak menggunakan apel dan jeruk bersama-sama :)
Legenda
Lp

Jawaban:

12

Dalam kebanyakan situasi, saya akan berpikir bahwa dsuch plot pada dasarnya berarti bahwa tidak ada struktur cluster dalam data. Namun, pengelompokan dalam dimensi yang sangat tinggi seperti ini rumit karena untuk metrik jarak Euclidean semua jarak cenderung sama dengan jumlah dimensi meningkat. Lihat halaman Wikipedia ini untuk referensi ke beberapa makalah tentang topik ini. Singkatnya, itu mungkin hanya dimensi tinggi dari dataset yang menjadi masalah.

Ini pada dasarnya adalah "kutukan dimensi", lihat halaman Wikipedia ini juga.

Sebuah makalah yang mungkin menarik adalah Sanguinetti, G., "Pengurangan dimensi datset berkerumun", Transaksi IEEE pada Analisis Pola dan Kecerdasan Mesin, vol. 30 no. 3, hlm. 535-540, Maret 2008 ( www ). Yang agak mirip versi LDA tanpa pengawasan yang mencari ruang dimensi rendah yang menekankan struktur cluster. Mungkin Anda bisa menggunakannya sebagai metode ekstraksi fitur sebelum melakukan k-means?

Dikran Marsupial
sumber
Ups maaf. Saya seharusnya menyebutkan bahwa saya menggunakan kesamaan cosinus.
Legenda
Saya pikir kemungkinan kutukan dimensionalitas juga berlaku pada persamaan cosinus. Pada dasarnya dikatakan bahwa Anda perlu (kasus terburuk) secara eksponensial lebih banyak pola untuk mendefinisikan distribusi ketika jumlah dimensi meningkat. Dalam pengelompokan apa yang Anda lakukan secara efektif adalah mengidentifikasi distribusi yang mewakili sub-populasi, jadi pengelompokan dalam dimensi tinggi cenderung secara inheren rumit.
Dikran Marsupial
+1 Terima kasih atas tautannya. Saya akan melewatinya dan kembali. Saya menerapkan SVD pada matriks asli saya sebelum menerapkan k-means untuk mengurangi jumlah dimensi.
Legenda
3

Bagaimana tepatnya Anda menggunakan kesamaan cosinus? Apakah ini yang disebut sebagai K-means bola? Kumpulan data Anda cukup kecil, jadi saya akan mencoba memvisualisasikannya sebagai jaringan. Untuk ini wajar untuk menggunakan kesamaan (memang, misalnya kesamaan cosinus atau korelasi Pearson), menerapkan cut-off (hanya mempertimbangkan hubungan di atas kesamaan tertentu), dan melihat hasilnya sebagai jaringan dalam misalnya Cytoscape atau BioLayout . Ini bisa sangat membantu untuk merasakan data. Kedua, saya akan menghitung nilai singular untuk matriks data Anda, atau nilai eigen dari matriks yang ditransformasikan dan dinormalisasi secara tepat (matriks dokumen-dokumen yang diperoleh dalam beberapa bentuk). Struktur cluster harus (lagi) muncul sebagai lompatan dalam daftar nilai eigen atau nilai singular yang diurutkan.

micans
sumber
+1 Terima kasih atas petunjuknya. Saya tidak mengetahui tentang Cytoscape. Saya akan mencobanya. Dan ya, sepertinya k-means dengan persamaan cosinus disebut sebagai k-means Spherical. Saya menerapkan k-means ini setelah menerapkan SVD dan mengurangi jumlah dimensi. Cara saya mengurangi jumlah dimensi adalah dengan menggunakan aturan varians (pilih nilai singular yang berkontribusi 95% dari varians dalam data asli).
Legenda
Jika Anda tidak keberatan, dapatkah Anda mengarahkan ke tutorial yang menjelaskan cara melakukan ini (atau setidaknya sesuatu seperti ini). Setelah saya menghasilkan matriks, apakah saya hanya mengekspornya dan kemudian mengimpornya ke Cytoscape dan melakukan apa yang Anda sarankan? Yang saya ingin tahu adalah apakah Cytoscape memiliki metode bawaan untuk kesamaan cosinus atau apakah saya harus melakukan precompute terhadap beberapa format data dan memberikannya sebagai input?
Legenda
Ketika saya bekerja dengan program-program itu, saya menghitung semua kesamaan berpasangan secara eksternal, memfilter menurut ambang, dan menghasilkan file dengan format <label1> <label2> <similarity>. Entah harus dapat membaca input itu. Dalam BioLayout, saya harus memiliki akhiran .txt; di CytoScape gunakan 'impor dari tabel'.
micans
Dimengerti Saya akan melakukan itu dan segera kembali. Terima kasih sekali lagi.
Legenda
Maaf untuk pertanyaan bodoh tapi saya memformat data saya sebagai <label1> <label2> <similarity> tetapi saya tidak dapat menemukan cara mengimpornya dengan tepat. Saya melakukan File-> Impor-> Jaringan dari Tabel dan memilih sumber dan kolom target saya. Saya meninggalkan interaksi sebagai default. Tapi bagaimana saya bisa mengimpor bobot tepi bersama dengan tepi? Apakah Anda punya saran?
Legenda
2

Secara umum ya, k-means mungkin bertemu dengan solusi yang sangat berbeda yang mungkin dinilai tidak cocok. Ini terjadi khususnya untuk cluster dengan bentuk tidak beraturan.

Agar mendapatkan lebih banyak intuisi, Anda juga dapat mencoba pendekatan visualisasi lain: Untuk k-means Anda dapat memvisualisasikan beberapa proses dengan k-means menggunakan Graphgrams (lihat paket WEKA graphgram - terbaik diperoleh oleh manajer paket atau di sini . Pengantar dan contoh juga bisa berupa ditemukan di sini .

Johannes Schneider
sumber
1

Jika saya memahami grafik dengan benar itu adalah plot dari jumlah cluster, K pada sumbu x dan jarak cluster dalam pada sumbu y?

Karena fungsi objektif K-means Anda adalah untuk meminimalkan WCSS, plot ini harus selalu berkurang secara monoton. Saat Anda menambahkan lebih banyak cluster, jarak antara titik-titik di cluster akan selalu berkurang. Ini adalah masalah mendasar pemilihan model, jadi Anda harus menggunakan sedikit kecanggihan.

Mungkin coba statistik Gap: www-stat.stanford.edu/~tibs/ftp/gap.ps atau yang lain menyukainya.

Selain itu, Anda mungkin menemukan bahwa K-means bukan alat yang tepat untuk pekerjaan itu. Berapa banyak cluster yang Anda harapkan? Menggunakan aturan varians untuk pengurangan dimensi untuk pengelompokan tidak tepat. Lihat makalah ini ketika memproyeksikan ke PC K-1 pertama adalah langkah preprocessing yang tepat: http://people.csail.mit.edu/gjw/papers/jcss.ps

Anda dapat dengan cepat melihat apakah ini hal yang benar untuk dilakukan dengan memplot proyeksi ke dua komponen utama pertama. Jika ada pemisahan yang jelas maka K-means harus baik-baik saja, jika tidak Anda perlu melihat ke hal lain. Mungkin K-subruang atau metode pengelompokan subruang lainnya. Ingat metode ini berlaku untuk jarak Euclidean. Saya tidak yakin bagaimana ini berubah untuk cosinus.

bmc
sumber