Metode clustering adalah tugas untuk mengelompokkan sekumpulan objek sedemikian rupa sehingga mereka dalam kelompok yang sama lebih mirip satu sama lain daripada objek di industri lain. Ini adalah tugas utama penambangan data dan teknik analisis statistik umum yang digunakan di banyak bidang, termasuk pembelajaran mesin, pengenalan pola, pengenalan gambar, pengambilan informasi, kompresi data, dan grafik komputer.
Masalah optimasi
Metode pengelompokan itu sendiri bukanlah satu algoritme khusus, tetapi merupakan tugas umum yang perlu diselesaikan. Hal ini dapat dicapai dengan berbagai algoritma yang berbeda secara signifikan dalam memahami apa yang merupakan kelompok dan bagaimana menemukannya secara efisien. Penggunaan metode clustering untuk pembentukan metasubyek meliputi penggunaan grup denganjarak kecil antara anggota, daerah padat ruang, interval, atau distribusi statistik tertentu. Oleh karena itu, pengelompokan dapat dirumuskan sebagai masalah optimasi multi-tujuan.
Metode dan pengaturan parameter yang sesuai (termasuk item seperti fungsi jarak yang digunakan, ambang kepadatan, atau jumlah cluster yang diharapkan) bergantung pada kumpulan data individual dan tujuan penggunaan hasil. Analisis seperti itu bukanlah tugas otomatis, tetapi proses berulang dari penemuan pengetahuan atau optimasi multi-tujuan interaktif. Metode pengelompokan ini mencakup upaya coba-coba. Seringkali diperlukan untuk memodifikasi prapemrosesan data dan parameter model hingga hasilnya mencapai properti yang diinginkan.
Selain istilah "pengelompokan", ada beberapa kata yang memiliki kesamaan arti, antara lain klasifikasi otomatis, taksonomi numerik, keduanya, dan analisis tipologi. Perbedaan halus sering terletak pada penggunaan metode clustering untuk membentuk hubungan metasubjek. Sementara dalam ekstraksi data, kelompok yang dihasilkan menarik, dalam klasifikasi otomatis sudah ada kekuatan diskriminatif yang melakukan fungsi-fungsi ini.
Analisis klaster didasarkan pada banyak karya Kroeber pada tahun 1932. Itu diperkenalkan ke dalam psikologi oleh Zubin pada tahun 1938 dan oleh Robert Tryon pada tahun 1939. Dan karya-karya ini telah digunakan oleh Cattell sejak tahun 1943 untuk menunjukkan klasifikasi metode pengelompokan secara teori.
Istilah
Konsep "cluster" tidak dapat didefinisikan dengan tepat. Ini adalah salah satu alasan mengapa ada begitu banyak metode pengelompokan. Ada penyebut yang sama: sekelompok objek data. Namun, peneliti yang berbeda menggunakan model yang berbeda. Dan masing-masing penggunaan metode clustering ini melibatkan data yang berbeda. Konsep yang ditemukan oleh berbagai algoritma berbeda secara signifikan dalam sifat-sifatnya.
Menggunakan metode pengelompokan adalah kunci untuk memahami perbedaan antara instruksi. Pola klaster tipikal meliputi:
- Centroid s. Ini, misalnya, ketika pengelompokan k-means mewakili setiap cluster dengan satu vektor rata-rata.
- Model konektivitas s. Ini, misalnya, pengelompokan hierarkis, yang membangun model berdasarkan konektivitas jarak.
- Model distribusi s. Dalam hal ini, cluster dimodelkan menggunakan metode clustering untuk membentuk distribusi statistik metasubject. Seperti pemisahan normal multivariat, yang dapat diterapkan pada algoritma maksimalisasi ekspektasi.
- Model kepadatan s. Ini adalah, misalnya, DBSCAN (Spatial Clustering Algorithm with Noise) dan OPTICS (Order Points for Structure Detection), yang mendefinisikan cluster sebagai daerah padat yang terhubung dalam ruang data.
- Model subruang c. Dalam biclustering (juga dikenal sebagai co-clustering atau dua mode), grup dimodelkan dengan kedua elemen dan dengan atribut yang sesuai.
- Model s. Beberapa algoritma tidakhubungan yang disempurnakan untuk metode pengelompokan mereka untuk menghasilkan hasil meta-subjek dan hanya memberikan pengelompokan informasi.
- Model berdasarkan graf s. Sebuah klik, yaitu subset dari node, sehingga setiap dua koneksi di bagian tepi dapat dianggap sebagai prototipe bentuk cluster. Melemahnya total permintaan dikenal sebagai quasi-cliques. Nama yang sama persis ditampilkan dalam algoritma pengelompokan HCS.
- Model saraf s. Jaringan tanpa pengawasan yang paling terkenal adalah peta yang mengatur dirinya sendiri. Dan model-model inilah yang biasanya dapat dicirikan mirip dengan satu atau lebih metode pengelompokan di atas untuk pembentukan hasil meta-subjek. Ini mencakup sistem subruang ketika jaringan saraf mengimplementasikan bentuk analisis komponen utama atau independen yang diperlukan.
Istilah ini, pada kenyataannya, adalah sekumpulan grup seperti itu, yang biasanya berisi semua objek dalam kumpulan metode pengelompokan data. Selain itu, dapat menunjukkan hubungan cluster satu sama lain, seperti hierarki sistem yang dibangun satu sama lain. Pengelompokan dapat dibagi menjadi beberapa aspek berikut:
- Metode pengelompokan centroid keras. Di sini, setiap objek milik grup atau di luarnya.
- Sistem lunak atau kabur. Pada titik ini, setiap objek sudah menjadi bagian dari cluster manapun. Ini juga disebut metode clustering fuzzy c-means.
Dan perbedaan yang lebih halus juga mungkin terjadi. Misalnya:
- Pengelompokan partisi yang ketat. Di Sinisetiap objek milik tepat satu grup.
- Pengelompokan partisi yang ketat dengan outlier. Dalam hal ini, objek mungkin juga bukan milik cluster mana pun dan dianggap tidak perlu.
- Pengelompokan yang tumpang tindih (juga alternatif, dengan banyak tampilan). Di sini, objek dapat dimiliki lebih dari satu cabang. Biasanya melibatkan cluster padat.
- Metode pengelompokan hierarkis. Objek yang termasuk dalam grup anak juga termasuk dalam subsistem induk.
- Pembentukan subruang. Meskipun mirip dengan cluster yang tumpang tindih, dalam sistem yang didefinisikan secara unik, grup bersama tidak boleh tumpang tindih.
Petunjuk
Seperti yang dinyatakan di atas, algoritma clustering dapat diklasifikasikan berdasarkan model clusternya. Tinjauan berikut hanya akan mencantumkan contoh paling menonjol dari instruksi ini. Karena mungkin ada lebih dari 100 algoritme yang diterbitkan, tidak semua menyediakan model untuk klasternya dan oleh karena itu tidak dapat dengan mudah diklasifikasikan.
Tidak ada algoritma pengelompokan yang benar secara objektif. Tetapi, seperti disebutkan di atas, instruksi selalu berada di bidang pandang pengamat. Algoritma pengelompokan yang paling cocok untuk masalah tertentu sering kali harus dipilih secara eksperimental, kecuali ada alasan matematis untuk lebih memilih satu model daripada yang lain. Perlu dicatat bahwa algoritma yang dirancang untuk satu tipe biasanya tidak bekerja dengankumpulan data yang berisi subjek yang sangat berbeda. Misalnya, k-means tidak dapat menemukan grup non-cembung.
Pengelompokan berbasis koneksi
Kesatuan ini juga dikenal dengan namanya, model hierarkis. Ini didasarkan pada gagasan khas bahwa objek lebih terhubung ke bagian tetangga daripada yang lebih jauh. Algoritma ini menghubungkan objek, membentuk cluster yang berbeda, tergantung pada jaraknya. Sebuah grup dapat digambarkan terutama dengan jarak maksimum yang diperlukan untuk menghubungkan bagian-bagian yang berbeda dari cluster. Pada semua jarak yang memungkinkan, kelompok lain akan terbentuk, yang dapat direpresentasikan menggunakan dendrogram. Ini menjelaskan dari mana nama umum "pengelompokan hierarkis" berasal. Artinya, algoritme ini tidak menyediakan satu partisi dari kumpulan data, melainkan memberikan urutan otoritas yang luas. Berkat dia ada saluran pembuangan satu sama lain pada jarak tertentu. Dalam dendrogram, sumbu y menunjukkan jarak di mana cluster datang bersama-sama. Dan benda-benda tersebut disusun sepanjang garis X agar kelompoknya tidak bercampur.
Pengelompokan berbasis koneksi adalah seluruh keluarga metode yang berbeda dalam cara menghitung jarak. Selain pilihan fungsi jarak yang biasa, pengguna juga perlu memutuskan kriteria koneksi. Karena sebuah cluster terdiri dari beberapa objek, ada banyak pilihan untuk menghitungnya. Pilihan populer dikenal sebagai pengelompokan tuas tunggal, ini adalah metodenyatautan lengkap, yang berisi UPGMA atau WPGMA (ansambel pasangan tidak berbobot atau berbobot dengan rata-rata aritmatika, juga dikenal sebagai pengelompokan tautan rata-rata). Selain itu, sistem hierarki dapat bersifat aglomerasi (dimulai dengan elemen individu dan menggabungkannya ke dalam kelompok) atau membagi (dimulai dengan kumpulan data lengkap dan memecahnya menjadi beberapa bagian).
Pengelompokan terdistribusi
Model ini paling erat hubungannya dengan statistik yang didasarkan pada pemisahan. Cluster dapat dengan mudah didefinisikan sebagai objek yang kemungkinan besar termasuk dalam distribusi yang sama. Fitur praktis dari pendekatan ini adalah sangat mirip dengan cara kumpulan data buatan dibuat. Dengan mengambil sampel objek acak dari suatu distribusi.
Meskipun dasar teoretis dari metode ini sangat baik, mereka mengalami satu masalah utama, yang dikenal sebagai overfitting, kecuali jika batasan dikenakan pada kompleksitas model. Asosiasi yang lebih besar biasanya akan menjelaskan data dengan lebih baik, sehingga sulit untuk memilih metode yang tepat.
Model campuran Gaussian
Metode ini menggunakan semua jenis algoritma maksimalisasi ekspektasi. Di sini, dataset biasanya dimodelkan dengan sejumlah distribusi Gaussian yang tetap (untuk menghindari overriding) yang diinisialisasi secara acak dan parameternya dioptimalkan secara iteratif agar lebih sesuai dengan dataset. Sistem ini akan konvergen ke optimum lokal. Itulah mengapa beberapa lari bisa memberihasil yang berbeda. Untuk mendapatkan pengelompokan yang paling ketat, fitur sering ditugaskan ke distribusi Gaussian yang kemungkinan besar menjadi miliknya. Dan untuk grup yang lebih lembut, ini tidak perlu.
Pengelompokan berbasis distribusi menciptakan model kompleks yang pada akhirnya dapat menangkap korelasi dan ketergantungan antar atribut. Namun, algoritma ini memberikan beban tambahan pada pengguna. Untuk banyak kumpulan data dunia nyata, mungkin tidak ada model matematika yang didefinisikan secara ringkas (misalnya, dengan asumsi distribusi Gaussian adalah asumsi yang cukup kuat).
Pengelompokan berdasarkan kepadatan
Dalam contoh ini, grup pada dasarnya didefinisikan sebagai area dengan impermeabilitas yang lebih tinggi daripada kumpulan data lainnya. Objek di bagian langka ini, yang diperlukan untuk memisahkan semua komponen, biasanya dianggap sebagai noise dan titik tepi.
Metode clustering berbasis kepadatan yang paling populer adalah DBSCAN (Spatial Noise Clustering Algorithm). Tidak seperti banyak metode yang lebih baru, ia memiliki komponen cluster yang terdefinisi dengan baik yang disebut "keterjangkauan kepadatan". Mirip dengan pengelompokan berbasis tautan, ini didasarkan pada titik koneksi dalam ambang jarak tertentu. Namun, metode ini hanya mengumpulkan item yang memenuhi kriteria kepadatan. Dalam versi aslinya, didefinisikan sebagai jumlah minimum objek lain dalam radius ini, cluster terdiri dari semuaitem terkait kepadatan (yang dapat membentuk grup bentuk bebas, tidak seperti banyak metode lain), dan semua objek yang berada dalam rentang yang diizinkan.
Properti lain yang menarik dari DBSCAN adalah kompleksitasnya yang cukup rendah - ini membutuhkan sejumlah kueri rentang linier terhadap database. Dan yang juga tidak biasa adalah bahwa pada dasarnya akan menemukan hasil yang sama (ini deterministik untuk titik inti dan kebisingan, tetapi tidak untuk elemen batas) di setiap proses. Oleh karena itu, tidak perlu menjalankannya berkali-kali.
Kelemahan utama DBSCAN dan OPTICS adalah mereka mengharapkan penurunan kepadatan untuk mendeteksi batas cluster. Misalnya, dalam kumpulan data dengan distribusi Gaussian yang tumpang tindih-kasus penggunaan umum untuk objek buatan-batas klaster yang dihasilkan oleh algoritme ini sering kali tampak arbitrer. Hal ini terjadi karena kepadatan kelompok terus berkurang. Dan dalam kumpulan data campuran Gaussian, algoritme ini hampir selalu mengungguli metode seperti pengelompokan EM, yang mampu memodelkan jenis sistem ini secara akurat.
Perpindahan rata-rata adalah pendekatan pengelompokan di mana setiap objek bergerak ke area terpadat di lingkungan tersebut berdasarkan perkiraan seluruh kernel. Pada akhirnya, objek menyatu ke maxima imperabilitas lokal. Mirip dengan pengelompokan k-means, "penarik kepadatan" ini dapat berfungsi sebagai perwakilan untuk kumpulan data. Tapi pergeseran rata-ratadapat mendeteksi cluster berbentuk arbitrer mirip dengan DBSCAN. Karena prosedur iteratif yang mahal dan estimasi densitas, perpindahan rata-rata biasanya lebih lambat dari DBSCAN atau k-Means. Selain itu, penerapan algoritma shift tipikal untuk data berdimensi tinggi sulit karena perilaku estimasi kepadatan kernel yang tidak seragam, yang mengarah pada fragmentasi berlebihan dari ekor cluster.
Peringkat
Memverifikasi hasil pengelompokan sama sulitnya dengan pengelompokan itu sendiri. Pendekatan populer termasuk penilaian "internal" (di mana sistem direduksi menjadi ukuran kualitas tunggal) dan, tentu saja, penilaian "eksternal" (di mana pengelompokan dibandingkan dengan klasifikasi "kebenaran dasar" yang ada). Dan skor manual ahli manusia dan skor tidak langsung ditemukan dengan memeriksa kegunaan clustering dalam aplikasi yang dimaksud.
Ukuran flag internal mengalami masalah karena mewakili fitur yang dapat dianggap sebagai target pengelompokan. Misalnya, dimungkinkan untuk mengelompokkan data yang diberikan oleh koefisien Silhouette, kecuali bahwa tidak ada algoritme efisien yang diketahui untuk melakukannya. Menggunakan ukuran internal untuk evaluasi, lebih baik untuk membandingkan kesamaan masalah optimasi.
Tanda luar memiliki masalah yang sama. Jika ada label "kebenaran dasar" seperti itu, maka tidak perlu mengelompok. Dan dalam aplikasi praktis, biasanya tidak ada konsep seperti itu. Di sisi lain, label hanya mencerminkan satu kemungkinan partisi dari kumpulan data, yang tidak berartibahwa tidak ada pengelompokan lain (bahkan mungkin lebih baik).
Jadi tidak satu pun dari pendekatan ini yang pada akhirnya dapat menilai kualitas sebenarnya. Tapi ini membutuhkan evaluasi manusia, yang sangat subjektif. Namun demikian, statistik tersebut dapat informatif dalam mengidentifikasi cluster yang buruk. Tetapi seseorang tidak boleh mengabaikan penilaian subjektif seseorang.
Tanda dalam
Bila hasil pengelompokan dievaluasi berdasarkan data yang telah dikelompokan itu sendiri, ini disebut istilah ini. Metode ini umumnya memberikan hasil terbaik untuk algoritma yang membuat grup dengan kesamaan tinggi di dalam dan rendah di antara grup. Salah satu kelemahan menggunakan kriteria internal dalam evaluasi cluster adalah bahwa skor tinggi tidak selalu mengarah pada aplikasi pencarian informasi yang efektif. Juga, skor ini bias terhadap algoritma yang menggunakan model yang sama. Misalnya, pengelompokan k-means secara alami mengoptimalkan jarak fitur, dan kriteria internal yang didasarkan padanya cenderung melebih-lebihkan pengelompokan yang dihasilkan.
Oleh karena itu, langkah-langkah evaluasi ini paling cocok untuk mendapatkan gambaran tentang situasi di mana satu algoritma berkinerja lebih baik daripada yang lain. Tetapi ini tidak berarti bahwa setiap informasi memberikan hasil yang lebih andal daripada yang lain. Periode validitas yang diukur dengan indeks semacam itu bergantung pada pernyataan bahwa struktur tersebut ada dalam kumpulan data. Suatu algoritma yang dikembangkan untuk beberapa tipe tidak memiliki peluang jika himpunan berisi radikalkomposisi yang berbeda atau jika penilaian mengukur kriteria yang berbeda. Misalnya, pengelompokan k-means hanya dapat menemukan cluster cembung, dan banyak indeks skor mengasumsikan format yang sama. Dalam dataset dengan model non-cembung, tidak tepat menggunakan k-means dan kriteria evaluasi tipikal.
Evaluasi eksternal
Dengan jenis balling ini, hasil clustering dievaluasi berdasarkan data yang tidak digunakan untuk grouping. Yaitu, seperti label kelas yang dikenal dan tes eksternal. Pertanyaan tersebut terdiri dari satu set item pra-klasifikasi dan sering dibuat oleh para ahli (manusia). Dengan demikian, kit referensi dapat dilihat sebagai standar emas untuk evaluasi. Jenis metode penilaian ini mengukur seberapa dekat pengelompokan dengan kelas referensi yang diberikan. Namun, baru-baru ini telah dibahas apakah ini memadai untuk data nyata atau hanya untuk himpunan sintetik dengan kebenaran dasar aktual. Karena kelas mungkin berisi struktur internal, dan atribut yang ada mungkin tidak mengizinkan pemisahan cluster. Juga, dari sudut pandang penemuan pengetahuan, mereproduksi fakta yang diketahui belum tentu menghasilkan hasil yang diharapkan. Dalam skenario pengelompokan terbatas khusus di mana meta-informasi (seperti label kelas) sudah digunakan dalam proses pengelompokan, tidak mudah untuk menyimpan semua informasi untuk tujuan evaluasi.
Sekarang jelas apa yang tidak berlaku untuk metode pengelompokan, dan model apa yang digunakan untuk tujuan ini.
