Bagaimana cara memahami kelemahan Hierarchical Clustering?

19

Adakah yang bisa menjelaskan pro dan kontra Hierarchical Clustering?

  1. Apakah Hierarchical Clustering memiliki kelemahan yang sama dengan K means?
  2. Apa keuntungan dari Hierarchical Clustering over K means?
  3. Kapan kita harus menggunakan K means lebih dari Hierarchical Clustering & sebaliknya?

Jawaban untuk posting ini menjelaskan kelemahan k sangat baik. Bagaimana memahami kelemahan K-means

GeorgeOfTheRF
sumber
2
Dalam jawaban ini saya menyentuh beberapa aspek yang berpotensi bermasalah dari analisis klaster aglomerasi hirarkis. "Kelemahan utama" adalah tidak serakah, algoritma serakah single-pass. Dengan algoritma serakah, Anda mengoptimalkan tugas langkah saat ini, yang - untuk sebagian besar metode HC - tidak selalu menjamin partisi terbaik pada langkah masa depan yang jauh. Keuntungan utama HC adalah fleksibel sehubungan dengan pilihan ukuran kedekatan yang akan digunakan. @Mic telah memberikan jawaban yang bagus di bawah ini, jadi saya hanya menggema.
ttnphns

Jawaban:

13

Sedangkan k berarti mencoba untuk mengoptimalkan tujuan global (varians dari kluster) dan mencapai optimal, pengelompokan hierarkis aglomeratif lokal bertujuan menemukan langkah terbaik pada setiap fusi klaster (algoritma serakah) yang dilakukan persis tetapi menghasilkan solusi yang berpotensi suboptimal .

Seseorang harus menggunakan pengelompokan hierarkis ketika data yang mendasarinya memiliki struktur hierarkis (seperti korelasi di pasar keuangan) dan Anda ingin memulihkan hierarki. Anda masih dapat menerapkan k berarti untuk melakukan itu, tetapi Anda mungkin berakhir dengan partisi (dari yang paling kasar (semua titik data dalam sebuah cluster) ke yang terbaik (setiap titik data adalah sebuah cluster)) yang tidak bersarang dan dengan demikian bukan hierarki yang tepat.

Jika Anda ingin menggali sifat-sifat yang lebih baik dari pengelompokan, Anda mungkin tidak ingin menentang pengelompokan datar seperti artinya ke pengelompokan hierarki seperti Hubungan Tunggal, Rata-Rata, dan Tautan Lengkap. Misalnya, semua pengelompokan ini menghemat ruang, yaitu ketika Anda membangun kluster Anda tidak mendistorsi ruang, sedangkan pengelompokan hierarkis seperti Ward tidak konservasi ruang, yaitu pada setiap langkah penggabungan akan mendistorsi ruang metrik.k

Untuk menyimpulkan, kelemahan dari algoritma pengelompokan hierarkis bisa sangat berbeda satu sama lain. Beberapa mungkin berbagi properti yang mirip dengan berarti: Ward bertujuan untuk mengoptimalkan varians, tetapi Single Linkage tidak. Tetapi mereka juga dapat memiliki sifat yang berbeda: Ward adalah pelebaran ruang, sedangkan Single Linkage menghemat ruang seperti k- berarti.kk

- Edit untuk presisi properti pelestarian-ruang dan pelebaran-ruang

D i j C i C j d

Dij[minxCi,yCjd(x,y),maxxCi,yCjd(x,y)]
DijCiCjd

ruang: yaitu dengan menggabungkan dan algoritma akan mendorong lebih jauh cluster .

D(CiCj,Ck)max(Dik,Djk),
CiCjCk
mik
sumber
Bisakah Anda memberi beberapa contoh lagi data yang memiliki struktur hierarkis? Tidak mengikuti contoh pasar keuangan.
GeorgeOfTheRF
Tentu. lih. arxiv.org/pdf/cond-mat/9802256.pdf atau secara sederhana Gambar 7 di arxiv.org/pdf/1506.00976.pdf yang menggambarkan matriks korelasi yang memiliki struktur blok korelasi hierarkis (berisik): Anda dapat melihat blok pada gambar utama diagonal, yang dibagi menjadi lebih banyak blok, masing-masing dibagi menjadi lebih banyak blok. Secara kasar sesuai dengan subdivisi di daerah (Eropa, AS, Asia ex-Jepang, Jepang), maka masing-masing daerah dibagi dengan kualitas aset (katakanlah kualitas tinggi vs sampah), kemudian dibagi oleh sektor industri besar (ritel, industri, media), lebih lanjut subdiv ke (aerospace, auto ...)
mic
3
+1. Namun, belum should use hierarchical clustering when underlying data has a hierarchical structure... and you want to recover the hierarchytentu. Dalam kebanyakan kasus, justru sebaliknya. Hirarki HC bukan cerita tentang algo daripada struktur data . Namun, pertanyaan ini pada akhirnya bersifat filosofis / logis, tidak begitu statistik.
ttnphns
Ward is not space-conserving, i.e. at each merging step it will distort the metric space. Bisakah Anda menulis lebih banyak tentang itu? Ini tidak terlalu jelas.
ttnphns
Ward is space-dilating, whereas Single Linkage is space-conserving like k-means. Apakah Anda ingin mengatakan ruang-kontrak untuk hubungan tunggal?
ttnphns
13

Skalabilitas

k berarti adalah pemenang yang jelas di sini. jauh lebih baik daripada skalabilitas (dalam beberapa kasus ) skalabilitas pengelompokan hierarkis karena biasanya dan dan kecil (sayangnya, cenderung tumbuh dengan , sehingga tidak tidak biasanya ditahan). Juga, konsumsi memori adalah linier, tidak seperti kuadrat (biasanya, kasus khusus linear ada).O(nkdi)O(n3d)O(n2d)kidinO(n)

Fleksibilitas

k -berarti sangat terbatas dalam penerapan. Ini pada dasarnya terbatas pada jarak Euclidean (termasuk Euclidean di ruang kernel, dan divergensi Bregman, tetapi ini sangat eksotis dan tidak ada yang benar-benar menggunakannya dengan berarti). Lebih buruk lagi, berarti hanya bekerja pada data numerik (yang seharusnya benar-benar berkelanjutan dan padat agar cocok untuk berarti).kkk

Hierarchical clustering adalah pemenang yang jelas di sini. Bahkan tidak memerlukan jarak - ukuran apa pun dapat digunakan, termasuk fungsi kesamaan hanya dengan memilih nilai tinggi ke nilai rendah. Data kategori? tentu saja gunakan misalnya Jaccard. String? Coba jarak Levenshtein. Seri waktu? Tentu. Jenis data campuran? Jarak Gower. Ada jutaan set data di mana Anda bisa menggunakan pengelompokan hierarkis, tetapi di mana Anda tidak bisa menggunakan berarti.k

Model

Tidak ada pemenang di sini. -berarti skor tinggi karena menghasilkan pengurangan data yang bagus. Centroid mudah dipahami dan digunakan. Di sisi lain, pengelompokan hierarki menghasilkan dendrogram. Dendrogram juga dapat sangat berguna dalam memahami kumpulan data Anda.k

Anony-Mousse -Reinstate Monica
sumber
Apakah Hierarchical gagal seperti k berarti ketika cluster adalah 1) non spherical 2) memiliki radius yang berbeda 3) memiliki kepadatan yang berbeda?
GeorgeOfTheRF
2
Keduanya bisa bekerja, dan keduanya bisa gagal. Itulah sebabnya hal-hal seperti dendrogram berguna. Jangan pernah mempercayai hasil pengelompokan sebagai "benar", selamanya.
Anony-Mousse -Reinstate Monica
Hierarchical clustering dapat memberikan cluster yang dioptimalkan secara lokal karena didasarkan pada pendekatan serakah tetapi K means memberikan cluster yang dioptimalkan secara global. Saya juga pernah mengalami bahwa penjelasan tentang pengelompokan hierarkis relatif mudah bagi pebisnis dibandingkan dengan K means.
Arpit Sisodia
7

Saya hanya ingin menambahkan ke jawaban lain sedikit tentang bagaimana, dalam arti tertentu, ada alasan teoritis yang kuat untuk lebih memilih metode pengelompokan hierarkis tertentu.

Asumsi umum dalam analisis cluster adalah bahwa data sampel dari beberapa mendasari kepadatan probabilitas bahwa kita tidak memiliki akses ke. Tapi misalkan kita punya akses ke sana. Bagaimana kita akan menentukan cluster dari f ?ff

Pendekatan yang sangat alami dan intuitif adalah untuk mengatakan bahwa cluster adalah daerah dengan kepadatan tinggi. Sebagai contoh, perhatikan kepadatan dua puncak di bawah ini:f

enter image description here

Dengan menggambar garis melintasi grafik kami menginduksi satu set cluster. Sebagai contoh, jika kita menggambar garis pada , kita mendapatkan dua kelompok yang ditunjukkan. Tetapi jika kita menggambar garis pada λ 3 , kita mendapatkan satu cluster.λ1λ3

Untuk membuatnya lebih tepat, anggap kita memiliki berubah-ubah . Apa cluster dari f pada level λ ? Mereka adalah komponen yang terhubung dari set superlevel { x : f ( x ) λ } .λ>0fλ{x:f(x)λ}

Sekarang alih-alih memilih berubah-ubah, kita dapat mempertimbangkan semua λ , sehingga himpunan kluster "benar" dari f adalah semua komponen yang terhubung dari himpunan superlevel f . Kuncinya adalah bahwa kumpulan cluster ini memiliki struktur hierarkis .λ λff

Biarkan saya membuatnya lebih tepat. Misalkan didukung pada X . Sekarang, biarkan C 1 menjadi komponen terhubung dari { x : f ( x ) λ 1 } , dan C 2 menjadi komponen yang terhubung dari { x : f ( x ) λ 2 } . Dengan kata lain, C 1 adalah sebuah cluster di level λ 1 , dan C 2 adalah sebuah cluster di level λ 2 . Lalu jikafXC1{x:f(x)λ1}C2{x:f(x)λ2}C1λ1C2λ2 , maka C 1C 2 , atau C 1C 2 = . Hubungan bersarang ini berlaku untuk setiap kelompok dalam koleksi kami, jadi yang kami miliki sebenarnya adalahhierarkikelompok. Kami menyebutnyapohon gugus.λ2<λ1C1C2C1C2=

Jadi sekarang saya memiliki beberapa data sampel dari kepadatan. Bisakah saya mengelompokkan data ini dengan cara yang memulihkan pohon cluster? Secara khusus, kami ingin metode konsisten dalam arti bahwa ketika kami mengumpulkan lebih banyak data, perkiraan empiris kami tentang pohon tandan tumbuh semakin dekat dan lebih dekat ke pohon tandan yang sebenarnya.

Hartigan adalah orang pertama yang mengajukan pertanyaan seperti itu, dan dengan melakukan itu ia mendefinisikan dengan tepat apa artinya bagi metode pengelompokan hierarki untuk secara konsisten memperkirakan pohon klaster. Definisinya adalah sebagai berikut: Misalkan dan B benar-benar merupakan cluster terpisah dari f sebagaimana didefinisikan di atas - yaitu, mereka adalah komponen yang terhubung dari beberapa set superlevel. Sekarang gambar satu set sampel n iid dari f , dan panggil set ini X n . Kami menerapkan metode pengelompokan hierarkis ke data X n , dan kami mendapatkan kembali kumpulan cluster empiris . Biarkan A n menjadi yang terkecilABfnfXnXnAncluster empiris yang mengandung semua , dan misalkan B n adalah yang terkecil yang mengandung semua B X n . Maka metode pengelompokan kami dikatakan Hartigan konsisten jika Pr ( A nB n ) = 1 sebagai n untuk setiap pasangan cluster menguraikan A dan B .AXnBnBXnPr(AnBn)=1nAB

Pada dasarnya, konsistensi Hartigan mengatakan bahwa metode pengelompokan kami harus memisahkan daerah dengan kepadatan tinggi. Hartigan menyelidiki apakah pengelompokan hubungan tunggal mungkin konsisten, dan menemukan bahwa itu tidak konsisten dalam dimensi> 1. Masalah menemukan metode umum, konsisten untuk memperkirakan pohon klaster terbuka sampai beberapa tahun yang lalu, ketika Chaudhuri dan Dasgupta memperkenalkan hubungan tunggal yang kuat , yang terbukti konsisten. Saya sarankan membaca tentang metode mereka, karena cukup elegan, menurut saya.

Jadi, untuk menjawab pertanyaan Anda, ada perasaan di mana hierarki klaster adalah hal yang "benar" untuk dilakukan ketika mencoba memulihkan struktur kepadatan. Namun, perhatikan tanda kutip di sekitar "benar" ... Pada akhirnya metode pengelompokan berbasis kepadatan cenderung berkinerja buruk dalam dimensi tinggi karena kutukan dimensi, dan meskipun definisi pengelompokan berdasarkan pada cluster adalah wilayah dengan probabilitas tinggi. cukup bersih dan intuitif, sering diabaikan demi metode yang berkinerja lebih baik dalam praktik. Itu tidak berarti hubungan tunggal yang kuat tidak praktis - itu benar-benar bekerja dengan baik pada masalah dalam dimensi yang lebih rendah.

Terakhir, saya akan mengatakan bahwa konsistensi Hartigan dalam beberapa hal tidak sesuai dengan intuisi konvergensi kita. Masalahnya adalah bahwa konsistensi Hartigan memungkinkan metode pengelompokan untuk sangat -segmen segmen sehingga suatu algoritma mungkin konsisten Hartigan, namun menghasilkan pengelompokan yang sangat berbeda dari pohon kluster yang benar. Kami telah menghasilkan karya tahun ini pada gagasan alternatif konvergensi yang membahas masalah ini. Pekerjaan muncul di "Beyond Hartigan Consistency: Gabungkan metrik distorsi untuk pengelompokan hierarkis" di COLT 2015.

jme
sumber
Ini adalah cara berpikir yang menarik tentang pengelompokan hierarkis. Saya merasa sangat mengingatkan clustering dengan estimasi nonparametrik density ( pdf ), yang diimplementasikan dalam Rdi pdfCluster paket. (Saya bahas di sini .)
gung - Reinstate Monica
HDBSCAN * menggunakan pendekatan serupa.
Anony-Mousse -Reinstate Monica
3

Keuntungan praktis tambahan dalam pengelompokan hierarkis adalah kemungkinan memvisualisasikan hasil menggunakan dendrogram. Jika sebelumnya Anda tidak tahu jumlah cluster yang Anda cari (seperti yang sering terjadi ...), Anda dapat plot dendrogram dapat membantu Anda memilih tanpa perlu membuat clustering terpisah. Dedrogram juga dapat memberikan wawasan yang hebat tentang struktur data, membantu mengidentifikasi outlier, dll. Hierarchical clustering juga deterministik, sedangkan k-means dengan inisialisasi acak dapat memberikan Anda hasil yang berbeda ketika dijalankan beberapa kali pada data yang sama. Dalam k-means, Anda juga dapat memilih metode yang berbeda untuk memperbarui cara klaster (walaupun pendekatan Hartigan-Wong sejauh ini adalah yang paling umum), yang tidak ada masalah dengan metode hierarkis.k

EDIT terima kasih kepada ttnphns: Salah satu fitur yang dibagi hierarkis dengan banyak algoritma lainnya adalah kebutuhan untuk memilih ukuran jarak. Ini seringkali sangat tergantung pada aplikasi dan tujuan tertentu. Ini mungkin dilihat sebagai komplikasi tambahan (parameter lain untuk memilih ...), tetapi juga sebagai aset - lebih banyak kemungkinan. Sebaliknya, algoritma K-means klasik secara khusus menggunakan jarak Euclidean.

Jacek Podlewski
sumber
3
Saya kira "masalah" dalam paragraf terakhir Anda akan dilihat secara positif sebagai aset. K-means, bagaimanapun, didasarkan secara implisit pada jarak euclidean saja .
ttnphns
Banyak pilihan yang mungkin bisa menjadi masalah sekaligus aset, memang :) Terima kasih atas komentarnya pada k-means, saya akan memperbaiki paragraf itu.
Jacek Podlewski
kk
Saya percaya pertanyaan awal dibuat berkenaan dengan "K-means 'klasik dan tidak sedikit pun niat untuk mempelajari perbedaan Bregman. Namun, komentar yang bagus, saya akan memeriksa makalah ini lebih teliti dengan pasti.
Jacek Podlewski
@mic tidak ada yang menggunakan divergensi Bregman melampaui variasi jarak Euclidean ... itu adalah kelas kecil yang sangat kecil saja. Tetapi orang-orang ingin menggunakan jarak Manhattan misalnya, Gower dll yang bukan divergensi Bregman untuk semua yang saya tahu.
Anony-Mousse -Reinstate Monica