Metode pengelompokan yang tidak memerlukan pra-penetapan jumlah cluster

17

Adakah metode pengelompokan "non-parametrik" yang tidak perlu kita tentukan jumlah clusternya? Dan parameter lain seperti jumlah titik per cluster, dll.

clustering Learn_and_Share
sumber

Jawaban:

22

Algoritma pengelompokan yang mengharuskan Anda untuk menentukan sebelumnya jumlah cluster adalah minoritas kecil. Ada sejumlah besar algoritma yang tidak. Mereka sulit diringkas; ini seperti meminta deskripsi tentang organisme apa pun yang bukan kucing.

Algoritma pengelompokan sering dikategorikan ke dalam kerajaan luas:

  1. Algoritma pemartisian (seperti k-means dan keturunannya)
  2. Pengelompokan hierarki (seperti yang dijelaskan oleh @Tim )
  3. Clustering berbasis kepadatan (seperti DBSCAN )
  4. Pengelompokan berbasis model (misalnya, model campuran Gaussian terbatas , atau Analisis Kelas Laten )

Mungkin ada kategori tambahan, dan orang-orang bisa tidak setuju dengan kategori ini dan algoritma mana yang masuk dalam kategori mana, karena ini heuristik. Namun demikian, skema seperti ini biasa terjadi. Bekerja dari ini, terutama hanya metode partisi (1) yang memerlukan pra-spesifikasi jumlah cluster untuk menemukan. Apa informasi lain yang perlu ditentukan sebelumnya (misalnya, jumlah titik per kluster), dan apakah masuk akal untuk menyebut berbagai algoritma 'nonparametrik', juga sangat bervariasi dan sulit untuk diringkas.

Hierarchical clustering tidak mengharuskan Anda untuk menentukan sebelumnya jumlah cluster, seperti yang dilakukan k-means, tetapi Anda memang memilih sejumlah cluster dari output Anda. Di sisi lain, DBSCAN tidak memerlukan salah satu (tapi itu membutuhkan spesifikasi dari jumlah minimum poin untuk 'lingkungan' - meskipun ada default, jadi dalam beberapa hal Anda bisa melewatkan menentukan itu - yang menempatkan lantai pada jumlah pola dalam sebuah cluster). GMM bahkan tidak memerlukan ketiganya, tetapi memang membutuhkan asumsi parametrik tentang proses menghasilkan data. Sejauh yang saya tahu, tidak ada algoritma pengelompokan yang tidak pernah mengharuskan Anda untuk menentukan sejumlah cluster, jumlah minimum data per cluster, atau pola / pengaturan data dalam cluster. Saya tidak melihat bagaimana mungkin ada.

Mungkin membantu Anda membaca ikhtisar berbagai jenis algoritma pengelompokan. Berikut ini mungkin tempat untuk memulai:

  • Berkhin, P. "Survei Teknik Penambangan Data Clustering" ( pdf )
gung - Pasang kembali Monica
sumber
Saya bingung dengan nomor 4 Anda: Saya pikir jika seseorang mencocokkan model campuran Gaussian dengan data maka orang perlu memilih jumlah Gaussians yang cocok, yaitu jumlah cluster harus ditentukan terlebih dahulu. Jika demikian, mengapa Anda mengatakan bahwa "terutama hanya" # 1 membutuhkan ini?
Amuba kata Reinstate Monica
@amoeba, itu tergantung pada metode berbasis model & bagaimana penerapannya. GMM sering cocok untuk meminimalkan beberapa kriteria (seperti, misalnya, regresi OLS, lihat di sini ). Jika demikian, Anda tidak menentukan sebelumnya jumlah cluster. Bahkan jika Anda melakukannya sesuai dengan beberapa implementasi lain, itu bukan fitur khas untuk metode berbasis model.
gung - Reinstate Monica
k=3k
Saya tidak benar-benar mengikuti argumen Anda di sini, @amoeba. Ketika Anda cocok dengan model regresi sederhana dengan algoritma OLS, apakah Anda akan mengatakan bahwa Anda telah menentukan sebelumnya kemiringan & penyadapan, atau bahwa algoritma menentukannya dengan mengoptimalkan kriteria? Jika yang terakhir, saya tidak melihat apa yang berbeda di sini. Memang benar bahwa Anda dapat membuat meta-algoritma baru yang menggunakan k-means sebagai salah satu langkahnya untuk menemukan partisi tanpa pra-spesifikasi k, tetapi meta-algoritma tidak akan menjadi k-means.
gung - Reinstate Monica
1
@amoeba, ini tampaknya menjadi masalah semantik, tetapi algoritma standar yang digunakan untuk menyesuaikan GMM biasanya mengoptimalkan kriteria. Misalnya, salah satu Mclustpenggunaan dirancang untuk mengoptimalkan BIC, tetapi AIC dapat digunakan atau serangkaian tes rasio kemungkinan. Saya kira Anda bisa menyebutnya meta-algoritma, b / c memiliki langkah konstituen (misalnya, EM), tetapi itu adalah algoritma yang Anda gunakan, & bagaimanapun itu tidak mengharuskan Anda untuk menentukan sebelumnya k. Anda dapat dengan jelas melihat dalam contoh tertaut saya bahwa saya tidak menentukan sebelumnya k di sana.
gung - Reinstate Monica
13

Contoh paling sederhana adalah pengelompokan hierarkis , di mana Anda membandingkan setiap titik dengan masing-masing titik lainnya menggunakan ukuran jarak , dan kemudian bergabung bersama pasangan yang memiliki jarak terkecil untuk membuat titik pseudo bergabung (misalnya b dan c membuat bc seperti pada gambar di bawah). Selanjutnya Anda ulangi prosedur dengan menggabungkan titik, dan titik semu, berdasarkan jarak berpasangan mereka sampai masing-masing titik digabungkan dengan grafik.

Ilustrasi Wikipedia

(sumber: https://en.wikipedia.org/wiki/Hierarchical_clustering )

Prosedur ini non-parametrik dan satu-satunya hal yang Anda butuhkan adalah ukuran jarak. Pada akhirnya Anda perlu memutuskan bagaimana memangkas grafik pohon yang dibuat menggunakan prosedur ini, sehingga keputusan tentang jumlah cluster yang diharapkan perlu dibuat.

Tim
sumber
Bukankah memangkas berarti Anda memutuskan nomor cluster?
Learn_and_Share
1
@MedNait itu yang saya katakan. Dalam analisis kluster Anda selalu harus membuat keputusan seperti itu, satu-satunya pertanyaan adalah bagaimana hal itu dibuat - misalnya itu bisa sewenang-wenang, atau bisa didasarkan pada beberapa kriteria yang masuk akal seperti model sesuai kemungkinan-kecocokan dll.
Tim
1
Itu tergantung pada apa yang Anda cari, @MedNait. Hierarchical clustering tidak mengharuskan Anda untuk menentukan sebelumnya jumlah cluster, seperti yang dilakukan k-means, tetapi Anda memilih sejumlah cluster dari output Anda. Di sisi lain, DBSCAN juga tidak memerlukan (tetapi memang membutuhkan spesifikasi jumlah minimum poin untuk 'lingkungan' - meskipun ada default - yang menempatkan jumlah pola pada sebuah cluster) . GMM bahkan tidak mengharuskan itu, tetapi memang membutuhkan asumsi parametrik tentang proses menghasilkan data. Dll
gung - Reinstate Monica
10

Parameternya bagus!

Metode "bebas parameter" berarti Anda hanya mendapatkan satu bidikan (kecuali untuk keacakan), tanpa kemungkinan penyesuaian .

Sekarang pengelompokan adalah teknik eksplorasi . Anda tidak boleh berasumsi bahwa ada satu pengelompokan "benar" . Anda sebaiknya lebih tertarik mengeksplorasi berbagai pengelompokan data yang sama untuk mempelajari lebih lanjut tentang itu. Memperlakukan pengelompokan sebagai kotak hitam tidak pernah bekerja dengan baik.

Misalnya, Anda ingin dapat menyesuaikan fungsi jarak yang digunakan tergantung pada data Anda (ini juga merupakan parameter!) Jika hasilnya terlalu kasar, Anda ingin bisa mendapatkan hasil yang lebih baik, atau jika terlalu halus , dapatkan versi yang lebih kasar.

Metode terbaik seringkali adalah metode yang memungkinkan Anda menavigasi hasil dengan baik, seperti dendrogram dalam pengelompokan hierarkis. Anda kemudian dapat menjelajahi substruktur dengan mudah.

Memiliki QUIT - Anony-Mousse
sumber
0

Lihatlah model campuran Dirichlet . Mereka menyediakan cara yang baik untuk memahami data jika Anda tidak tahu jumlah cluster sebelumnya. Namun, mereka membuat asumsi tentang bentuk cluster, yang mungkin dilanggar oleh data Anda.

Zeke
sumber