Pengelompokan berbasis centroid adalah jenis metode pengelompokan yang mempartisi atau membagi kumpulan data ke dalam kelompok yang serupa berdasarkan jarak antara centroid mereka. Centroid atau pusat dari setiap klaster adalah rata-rata atau median dari semua titik dalam klaster, tergantung pada data.

Salah satu teknik pengelompokan berbasis centroid yang paling umum digunakan adalah algoritme pengelompokan k rata-rata. K rata-rata mengasumsikan bahwa pusat dari setiap klaster mendefinisikan klaster menggunakan ukuran jarak, biasanya jarak Euclidean, ke pusat klaster. Untuk menginisialisasi pengelompokan, Anda memberikan sejumlah klaster yang diharapkan, yang mewakili 'K' dalam K rata-rata, dan algoritme mencoba menemukan klaster yang masuk akal di seluruh data yang sesuai dengan jumlah tersebut. Klaster k optimal dalam kumpulan data yang diberikan diidentifikasi dengan meminimalkan jarak total antara setiap titik dan pusat klaster yang telah ditentukan secara berulang-ulang.

K rata-rata adalah pendekatan pengelompokan keras, yang berarti setiap titik data ditugaskan ke klaster terpisah dan tidak ada probabilitas yang berkaitan dengan keanggotaan klaster. K rata-rata bekerja dengan baik ketika klaster memiliki ukuran yang kurang lebih setara, dan tidak ada outlier atau perubahan yang signifikan dalam kepadatan di seluruh data. K rata-rata sering berkinerja buruk ketika data berdimensi tinggi atau ketika klaster memiliki ukuran atau kepadatan yang sangat berbeda. K rata-rata juga sangat sensitif terhadap outlier karena berusaha menetapkan centroid berdasarkan nilai rata-rata dari semua nilai dalam klaster dan dengan demikian memasukkan outlier tersebut akan rentan terhadap overfitting.

Pendekatan berbasis centroid lain untuk K rata-rata adalah K-medoid. Medoid adalah objek representatif dari kumpulan data atau klaster dalam kumpulan data yang jumlah jaraknya ke objek lain dalam klaster tersebut minimal. Alih-alih menggunakan centroid sembarang sebagai pusat grafik, algoritme ini membuat klaster dengan menggunakan titik data individual sebagai median atau pusat klaster. Karena algoritme K-medoid menggunakan titik data yang masih ada dan bukan titik tengah sembarang, algoritme ini tidak terlalu sensitif terhadap outlier.

Pengelompokan hierarkis, terkadang disebut pengelompokan berbasis konektivitas, mengelompokkan titik data bersama-sama berdasarkan kedekatan dan konektivitas atributnya. Metode ini menentukan klaster berdasarkan seberapa dekat titik data dengan satu sama lain di semua dimensi. Prinsipnya adalah bahwa objek yang lebih dekat lebih terkait erat daripada objek yang jauh satu sama lain. Tidak seperti k rata-rata, tidak perlu menentukan jumlah klaster sebelumnya. Sebaliknya, algoritme pengelompokan menciptakan jaringan grafik klaster di setiap tingkat hierarkis. Jaringan ini bersifat hierarkis, artinya bahwa setiap node tertentu di dalamnya hanya memiliki satu node induk tetapi mungkin memiliki beberapa node turunan. Kelompok hierarkis dapat digambarkan dengan dendrogram untuk membantu meringkas dan mengatur kelompok yang ditemukan secara visual dan hierarki yang mungkin dimilikinya.

Ada dua pendekatan untuk melakukan analisis klaster hierarkis:

Aglomeratif: Dalam pengelompokan aglomeratif, pendekatan bottom-up dimulai dengan titik data individual dan secara berturut-turut menggabungkan klaster dengan menghitung matriks kedekatan semua klaster pada tingkat hierarki saat ini untuk membuat struktur seperti pohon. Setelah satu tingkat klaster dibuat di mana semua klaster tidak memiliki atau memiliki kemiripan antarklaster yang rendah, algoritme akan berpindah ke kumpulan klaster yang baru dibuat dan mengulangi prosesnya hingga ada satu node akar di bagian atas grafik hierarki. Ada berbagai pilihan yang memungkinkan dalam hal bagaimana klaster-klaster ini harus digabungkan satu sama lain dengan mengorbankan kualitas dan efisiensi pengelompokan. Dalam pengelompokan tautan tunggal, jarak terpendek antara pasangan titik data dalam dua klaster digunakan sebagai ukuran kemiripan. Pada semua pasangan, rata-rata dari semua pasangan titik data digunakan, sedangkan pada sampel, sampel dari titik data di dua klaster digunakan untuk menghitung jarak rata-rata. Dalam hubungan centroid, jarak antara centroid digunakan. Salah satu tantangan dalam metode aglomeratif adalah metode ini dapat menunjukkan rantai, di mana klaster yang lebih besar secara alami memiliki bias untuk memiliki jarak yang lebih dekat ke titik lain dan terus menjadi lebih besar dan lebih besar dan menarik lebih banyak titik data ke dalam klaster mereka. Kerugian lainnya adalah metode aglomeratif mungkin jauh lebih lambat daripada metode pembagian dalam membangun hierarki.

Terbagi: Dalam metode pengelompokan hierarkis terbagi, pendekatan top-down secara berurutan mempartisi titik-titik data ke dalam struktur seperti pohon. Langkah pertama adalah membagi kumpulan data menjadi klaster menggunakan metode pengelompokan datar seperti K Rata-rata. Klaster dengan Sum of Squared Errors (SSE) terbesar kemudian dipartisi lebih lanjut dengan menggunakan metode pengelompokan datar. Algoritme berhenti baik saat mencapai node individu atau beberapa SSE minimum. Partisi yang terbagi memungkinkan fleksibilitas yang lebih besar dalam hal struktur pohon hierarkis dan tingkat keseimbangan dalam klaster yang berbeda. Tidak perlu memiliki pohon yang seimbang sempurna dalam hal kedalaman node yang berbeda atau pohon di mana derajat setiap cabang tepat dua. Hal ini memungkinkan pembuatan struktur pohon yang memungkinkan berbagai pertukaran dalam menyeimbangkan kedalaman node dan bobot node (jumlah titik data dalam node). Pengelompokan hierarkis yang terbagi atau memecah belah bisa lebih cepat daripada pengelompokan hierarkis aglomeratif, terutama ketika data tidak memerlukan pembuatan pohon hingga ke titik data individu.

Pengelompokan berbasis distribusi, terkadang disebut pengelompokan probabilistik, mengelompokkan titik-titik data berdasarkan distribusi probabilitasnya. Pendekatan ini mengasumsikan adanya proses yang menghasilkan distribusi normal untuk setiap dimensi data yang membentuk pusat klaster. Ini berbeda dari pengelompokan berbasis centroid karena tidak menggunakan metrik jarak seperti jarak Euclidean atau Manhattan. Sebaliknya, pendekatan berbasis distribusi mencari distribusi yang terdefinisi dengan baik yang muncul di setiap dimensi. Rata-rata klaster merupakan rata-rata distribusi Gaussian pada setiap dimensi. Pengelompokan berbasis distribusi merupakan pendekatan pengelompokan berbasis model karena pendekatan ini memerlukan penyesuaian distribusi beberapa kali pada setiap dimensi guna menemukan klaster. Artinya, proses komputasinya dapat memakan banyak biaya jika menangani kumpulan data besar.

Salah satu pendekatan yang umum digunakan untuk pengelompokan berbasis distribusi adalah membuat Model Campuran Gaussian (GMM) melalui Ekspektasi-Maksimisasi). Dinamakan GMM karena asumsi bahwa setiap klaster ditentukan oleh Distribusi Gaussian, yang sering disebut distribusi normal.

Pertimbangkan sebuah kumpulan data dengan dua kelompok yang berbeda, A dan B, yang keduanya ditentukan oleh dua distribusi normal yang berbeda: satu di sepanjang sumbu x dan satu di sepanjang sumbu y. Ekspektasi-Maksimisasi memulai tebakan acak untuk dua distribusi di sepanjang setiap sumbu dan kemudian melanjutkan untuk meningkatkan secara berulang dengan mengganti dua langkah:

Ekspektasi: Menetapkan setiap titik data ke setiap klaster dan menghitung probabilitas bahwa titik data tersebut berasal dari Klaster A dan Klaster B.

Maksimisasi: Memperbarui parameter yang menentukan setiap klaster, lokasi rata-rata tertimbang dan matriks varians-kovarians, berdasarkan kemungkinan setiap titik data berada dalam klaster. Kemudian langkah Ekspektasi diulangi sampai persamaan menyatu pada distribusi yang diamati untuk setiap klaster.

Setiap titik data diberi probabilitas terkait dengan klaster. Ini artinya pengelompokan melalui Ekspektasi-Maksimisasi adalah pendekatan pengelompokan yang lunak dan bahwa titik yang ditentukan mungkin secara probabilistik berkaitan dengan lebih dari satu klaster. Hal ini masuk akal dalam beberapa skenario, misalnya sebuah lagu mungkin memiliki genre sedikit folk dan sedikit rock atau pengguna mungkin lebih menyukai acara televisi dalam bahasa Spanyol, tetapi terkadang juga menonton acara dalam bahasa Inggris.

Pengelompokan berbasis densitas bekerja dengan mendeteksi area di mana titik-titik terkonsentrasi dan lokasi titik dipisahkan oleh area yang kosong atau tersebar. Tidak seperti pendekatan berbasis centroid, seperti K rata-rata, atau pendekatan berbasis distribusi, seperti Ekspektasi-Maksimisasi, pengelompokan berbasis densitas dapat mendeteksi klaster dengan bentuk yang berubah-ubah. Ini bisa sangat membantu ketika klaster tidak ditetapkan di sekitar lokasi atau distribusi tertentu. Tidak seperti algoritme pengelompokan lainnya, seperti K rata-rata dan pengelompokan hierarkis, algoritme berbasis densitas dapat menemukan kelompok dalam berbagai bentuk, ukuran, atau kepadatan dalam data Anda. Pengelompokan berbasis densitas juga dapat membedakan antara titik data yang merupakan bagian dari sebuah klaster dan titik data yang harus diberi label sebagai noise. Pengelompokan berbasis densitas sangat berguna ketika bekerja dengan kumpulan data dengan noise atau outlier atau ketika kita tidak memiliki pengetahuan sebelumnya tentang jumlah klaster dalam data.

DBSCAN adalah contoh algoritme pengelompokan yang mengambil pendekatan berbasis densitas untuk pengelompokan. Pendekatan ini menggunakan pendekatan pengelompokan spasial berbasis densitas untuk membuat klaster dengan densitas yang diberikan oleh pengguna yang berpusat di sekitar pusat spasial. Area di sekitar centroid disebut sebagai lingkungan dan DBSCAN mencoba untuk menentukan lingkungan klaster yang memiliki densitas tertentu. Untuk setiap klaster, DBSCAN akan menentukan tiga jenis titik data:

Titik Inti: Sebuah titik data adalah titik inti jika lingkungan di sekitar titik data tersebut berisi setidaknya sebanyak jumlah titik yang ditentukan pengguna.

Titik Batas: Sebuah titik data adalah titik perbatasan jika lingkungan di sekitar titik data tersebut berisi kurang dari jumlah minimum titik data, tetapi lingkungan di sekitar titik tersebut berisi titik inti.

Outlier: Sebuah titik data disebut outlier jika titik tersebut bukan merupakan titik inti atau titik batas. Pada dasarnya, ini adalah kelas “lain”.

DBSCAN adalah varian DBSCAN yang tidak memerlukan parameter apa pun untuk ditetapkan; hal ini dapat membuatnya lebih fleksibel daripada yang asli. HDBSCAN kurang sensitif terhadap noise dan outlier dalam data. Selain itu, DBSCAN terkadang kesulitan dalam mengidentifikasi klaster dengan densitas yang tidak seragam. Ini adalah dorongan utama untuk HDBSCAN sehingga menangani klaster dengan densitas yang bervariasi jauh lebih efektif.

Algoritme pengelompokan berbasis kisi tidak digunakan sesering empat pendekatan sebelumnya, tetapi dapat membantu dalam pengelompokan dimensi tinggi di mana algoritme pengelompokan lain mungkin tidak memiliki kinerja yang baik. Dalam pendekatan ini, algoritme mempartisi kumpulan data dimensi tinggi ke dalam sel. Setiap sel diberi pengenal unik yang disebut ID sel, dan semua titik data yang berada di dalam sel dianggap sebagai bagian dari klaster yang sama.

Pengelompokan berbasis kisi adalah algoritme yang efisien untuk menganalisis kumpulan data multidimensi yang besar karena mengurangi waktu yang dibutuhkan untuk mencari tetangga terdekat, yang merupakan langkah umum dalam banyak metode pengelompokan.

Salah satu algoritme pengelompokan berbasis kisi yang populer disebut STING, yang merupakan singkatan dari Statistical INformation Grid. Dalam STING, area spasial dibagi ke dalam sel persegi panjang dan beberapa tingkat sel pada tingkat resolusi yang berbeda-beda. Sel tingkat tinggi dibagi menjadi beberapa sel tingkat rendah. STING dapat sangat efisien dalam komputasi klaster pada skenario big data di mana kumpulan data berukuran sangat besar karena STING hanya mempartisi kumpulan data secara berulang ke dalam kisi-kisi yang lebih kecil dan mengevaluasi jumlah titik di dalam kisi-kisi tersebut. Kelemahan dari STING adalah batas-batas klaster harus ditentukan secara horizontal atau vertikal, algoritme ini tidak dapat mendeteksi batas-batas klaster yang tidak berbentuk persegi panjang.

Algoritme berbasis kisi lainnya yang sangat kuat dengan data berdimensi tinggi adalah algoritme Clustering In Quest atau CLIQUE. CLIQUE menggabungkan pendekatan berbasis kisi dan berbasis densitas untuk pengelompokan. Dalam algoritme ini, ruang data dibagi menjadi kisi-kisi dan densitas relatif titik-titik di dalam sel kisi-kisi dibandingkan dan sub-ruang yang memiliki densitas yang sama digabungkan. Pendekatan ini menemukan unit-unit yang padat di semua sub-ruang yang diminati dan kemudian mengukur apakah klaster yang serupa harus dihubungkan bersama. Ini artinya, CLIQUE dapat mendeteksi klaster bentuk sembarang dalam data dimensi tinggi.

Pengelompokan dapat membantu mengungkap anomali dengan mengukur titik data mana yang tidak termasuk dalam struktur pengelompokan yang ditentukan oleh analisis klaster. Titik data yang termasuk dalam klaster kecil atau sangat jarang atau yang jauh dari klaster yang ditetapkan dapat dianggap sebagai anomali. Metode berbasis densitas seperti Ekspektasi Maksimisasi digunakan untuk mengidentifikasi titik data di wilayah padat sebagai normal dan titik data di wilayah dengan densitas rendah sebagai anomali.

Ketika mencoba memahami persona pelanggan atau subset pasar yang mungkin ada, pengelompokan dapat menjadi alat yang ampuh untuk membantu melakukan segmentasi pelanggan. Anda mungkin dapat menggabungkan data demografis dengan data perilaku pelanggan untuk menemukan jenis karakteristik dan pola pembelian yang paling sering berkorelasi.

Gambar dapat dikelompokkan pikselnya dalam berbagai cara yang dapat membantu memotong gambar menjadi beberapa bagian yang berbeda untuk memisahkan latar depan dari latar belakang, mendeteksi objek dengan menggunakan kemiripan warna dan kecerahan, atau membagi gambar ke dalam area yang diminati untuk diproses lebih lanjut. Dengan gambar, metode pengelompokan memproses piksel dalam gambar dan menentukan area dalam gambar yang mewakili klaster.

Analisis pengelompokan dapat membantu dalam memproses dokumen dengan berbagai cara. Dokumen dapat dikelompokkan berdasarkan kesamaan untuk menunjukkan dokumen mana yang paling mirip satu sama lain. Hal ini dapat didasarkan pada panjang dokumen, distribusi frekuensi kata, atau berbagai cara lain untuk mengukur karakteristik penting terkait dokumen. Contoh penggunaan umum lainnya adalah untuk menganalisis kelompok bagian dokumen berdasarkan frekuensi kata kunci, panjang kalimat, atau distribusi istilah. Hal ini dapat membantu dalam meringkas dokumen atau memecah dokumen yang lebih besar menjadi kumpulan data yang lebih kecil untuk analisis lebih lanjut.