Apa itu clustering atau pengelompokan?

Ada berbagai cara untuk menggunakan pengklusteran dalam machine learning, mulai dari eksplorasi awal kumpulan data hingga pemantauan proses yang sedang berlangsung. Anda dapat menggunakannya dalam analisis data eksplorasi dengan kumpulan data baru untuk memahami tren, pola, dan outlier yang mendasarinya. Atau, Anda mungkin memiliki kumpulan data yang lebih besar yang perlu dipecah menjadi beberapa kumpulan data atau diperkecil menggunakan reduksi dimensionalitas. Dalam kasus ini, pengelompokan dapat menjadi langkah dalam prapemrosesan.

Contoh kluster dapat mencakup genre musik, berbagai kelompok pengguna, segmen utama segmentasi pasar, jenis lalu lintas jaringan pada kluster server, kelompok teman dalam jaringan sosial, atau kategori lainnya. Proses pengklusteran dapat menggunakan satu fitur data saja atau dapat menggunakan semua fitur yang ada dalam data.

Akan sangat membantu jika kita menganggap pengelompokan sebagai upaya menemukan pengklusteran alami dalam data untuk melihat kategori apa yang mungkin ada dan apa yang mendefinisikan kategori tersebut. Klaster dapat membantu Anda menemukan hubungan yang mendasari titik data untuk melihat fitur atau karakteristik apa yang dibagikan di seluruh kategori. Bergantung pada algoritma pengklusteran yang digunakan, Anda mungkin dapat menghapus outlier dari data Anda atau memberi label sebagai outlier. Klustering juga dapat membantu dalam deteksi anomali dengan mendeteksi titik data apa yang tidak terkandung dalam sebuah kluster atau hanya berkaitan secara lemah dengan sebuah kluster dan dengan demikian dapat menjadi anomali dalam proses pembuatan data.

Pengklusteran juga dapat digunakan untuk mengurangi kompleksitas kumpulan data besar dengan mengurangi jumlah dimensi data. Jika Anda melihat bahwa kategori hanya ditentukan oleh dua atau tiga fitur, Anda mungkin dapat menghapus fitur yang tidak relevan atau menggunakan teknik pengurangan dimensi seperti PCA. Pengelompokan juga sangat berguna dalam membuat visualisasi kumpulan data untuk melihat sifat yang muncul dari data serta kepadatan dan hubungan antar kluster.

Algoritma pengklusteran terkadang dibedakan sebagai pengklusteran keras, di mana setiap titik data hanya termasuk dalam satu kluster dan memiliki nilai biner, yaitu berada di dalam atau tidak di dalam kluster, atau pengelompokan lunak di mana setiap titik data diberi probabilitas untuk berada di setiap kluster yang diidentifikasi. Tidak ada satu proses pengklusteran yang terbaik. Sebaiknya pilih pendekatan yang paling masuk akal untuk kebutuhan Anda dan data yang Anda gunakan.

Ada banyak algoritma pengelompokan yang berbeda karena ada beberapa cara untuk mendefinisikan kluster. Pendekatan yang berbeda akan bekerja dengan baik untuk berbagai jenis model yang berbeda tergantung pada ukuran data input, dimensi data, kekakuan kategori, dan jumlah kluster dalam kumpulan data. Perlu diperhatikan bahwa satu algoritma mungkin bekerja dengan sangat baik untuk satu kumpulan data dan sangat buruk pada kumpulan data lain. Bagian ini membahas lima pendekatan yang umum digunakan untuk pengklusteran. Ada teknik lain seperti pengklusteran spektral atau pengklusteran Mean-Shift yang berada di luar cakupan artikel ini.

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 kluster adalah rata-rata atau median dari semua titik dalam kluster, tergantung pada data.

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

K rata-rata adalah pendekatan pengklusteran keras, yang berarti setiap titik data ditugaskan ke kluster terpisah dan tidak ada probabilitas yang berkaitan dengan keanggotaan kluster. K rata-rata bekerja dengan baik ketika kluster 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 kluster 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 kluster dan hal tersebut rentan terhadap overfitting untuk menyertakan outlier tersebut.

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 pengklusteran berbasis konektivitas, mengelompokkan titik data bersama-sama berdasarkan kedekatan dan konektivitas atributnya. Metode ini menentukan kluster 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, jumlah kluster sebelumnya tidak perlu ditentukan. Sebaliknya, algoritma pengklusteran menciptakan jaringan grafik kluster 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 kluster hierarkis:

Aglomeratif: Dalam pengelompokan aglomeratif, pendekatan bottom-up dimulai dengan titik data individual dan secara berturut-turut menggabungkan kluster dengan menghitung matriks kedekatan semua kluster pada tingkat hierarki saat ini untuk membuat struktur seperti pohon. Setelah satu tingkat klaster dibuat di mana semua klaster tidak memiliki atau memiliki kemiripan antar kluster yang rendah, algoritma akan berpindah ke kumpulan kluster yang baru dibuat dan mengulangi prosesnya hingga ada satu node akar di bagian atas grafik hierarki. Ada berbagai pilihan yang memungkinkan dalam hal bagaimana kluster-kluster ini harus digabungkan satu sama lain dengan mengorbankan kualitas dan efisiensi pengelompokan. Dalam pengelompokan tautan tunggal, jarak terpendek antara pasangan titik data dalam dua kluster 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 kluster 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 kluster mereka. Kerugian lainnya adalah metode aglomeratif mungkin jauh lebih lambat daripada metode pembagian dalam membangun hierarki.

Terbagi: Dalam metode pengklusteran hierarkis terbagi, pendekatan top-down secara berurutan mempartisi titik-titik data ke dalam struktur seperti pohon. Langkah pertama adalah membagi kumpulan data menjadi kluster menggunakan metode pengklusteran datar seperti K Rata-rata. Klaster dengan Sum of Squared Errors (SSE) terbesar kemudian dipartisi lebih lanjut dengan menggunakan metode pengklusteran 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.

Pengklusteran berbasis distribusi, terkadang disebut pengklusteran probabilistik, mengelompokkan titik-titik data berdasarkan distribusi probabilitasnya. Pendekatan ini mengasumsikan adanya proses yang menghasilkan distribusi normal untuk setiap dimensi data yang membentuk pusat kluster. 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 kluster merupakan rata-rata distribusi Gaussian pada setiap dimensi. Pengklusteran berbasis distribusi merupakan pendekatan pengelompokan berbasis model karena pendekatan ini memerlukan penyesuaian distribusi beberapa kali pada setiap dimensi guna menemukan kluster. 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 kluster 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 Kluster A dan Kluster B.

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

Setiap titik data diberi probabilitas terkait dengan kluster. Ini artinya pengklusteran melalui Ekspektasi-Maksimisasi adalah pendekatan pengklusteran 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.

Pengklusteran 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, pengklusteran berbasis densitas dapat mendeteksi kluster dengan bentuk yang berubah-ubah. Ini bisa sangat membantu ketika kluster tidak ditetapkan di sekitar lokasi atau distribusi tertentu. Tidak seperti algoritme pengklusteran lainnya, seperti K rata-rata dan pengelompokan hierarkis, algoritme berbasis densitas dapat menemukan kluster dalam berbagai bentuk, ukuran, atau kepadatan dalam data Anda. Pengklusteran berbasis densitas juga dapat membedakan antara titik data yang merupakan bagian dari sebuah kluster dan yang harus diberi label sebagai kebisingan. Pengklusteran berbasis densitas sangat berguna ketika bekerja dengan kumpulan data dengan kebisingan atau outlier atau ketika kita tidak memiliki pengetahuan sebelumnya tentang jumlah kluster dalam data.

DBSCAN adalah contoh algoritme pengklusteran yang mengambil pendekatan berbasis densitas untuk pengklusteran. Pendekatan ini menggunakan pendekatan pengklusteran 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 kluster yang memiliki densitas tertentu. Untuk setiap kluster, 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 batas 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 kluster dengan densitas yang tidak seragam. Ini adalah dorongan utama untuk HDBSCAN sehingga menangani kluster 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 kluster 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 pengklusteran.

Salah satu algoritme pengklusteran 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 kluster 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 kluster harus ditentukan secara horizontal atau vertikal, algoritma ini tidak dapat mendeteksi batas-batas kluster 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 klustering. 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 kluster yang serupa harus dihubungkan bersama. Ini artinya, CLIQUE dapat mendeteksi kluster bentuk sembarang dalam data dimensi tinggi.

Ada beberapa metrik evaluasi untuk analisis kluster dan pemilihan metrik yang sesuai tergantung pada jenis algoritma pengklusteran dan kumpulan data yang sesuai. Metrik evaluasi umumnya dapat dibagi menjadi dua kategori utama: Ekstrinsik dan Intrinsik.

Pengukuran intrinsik adalah metrik evaluasi untuk analisis kluster yang hanya menggunakan informasi dalam kumpulan data. Ini dapat membantu saat Anda bekerja dengan data yang tidak berlabel. Kualitas analisis sepenuhnya didasarkan pada hubungan antara titik data. Ini dapat digunakan saat kita tidak memiliki pengetahuan sebelumnya atau label data. Pengukuran intrinsik umum meliputi:

Skor siluet: Metrik ini mengukur kemiripan dan ketidakmiripan setiap titik data sehubungan dengan klusternya sendiri dan semua kluster lainnya. Nilai metrik berkisar dari -1 hingga +1. Nilai tinggi menunjukkan bahwa objek tersebut cocok dengan klusternya sendiri dan kurang cocok dengan kluster tetangga.

Indeks Davies-Bouldin: Metrik ini menghitung rasio jarak dalam kluster dengan jarak antar kluster. Semakin rendah skor indeks, semakin baik kinerja pengklusteran.

Indeks Calinski-Harabasz: Juga dikenal sebagai Kriteria Rasio Varian, indeks ini mengukur rasio varian antarkluster dan varian dalam klaster. Semakin tinggi rasio Calinski-Harabasz, semakin terdefinisi dengan baik suatu kluster.

Metrik evaluasi ini dapat membantu kita membandingkan kinerja algoritma dan model pengklusteran yang berbeda, mengoptimalkan parameter pengklusteran, dan memvalidasi keakuratan dan kualitas hasil pengklusteran.

Pengukuran ekstrinsik menggunakan kebenaran dasar atau informasi eksternal untuk menilai validitas kinerja algoritma pengklusteran. Dibutuhkan beberapa bentuk data label yang mengonfirmasi kelas atau klaster tempat setiap titik data berada. Dalam hal ini, Anda dapat membandingkan akurasi analisis pengelompokan Anda dengan metrik yang sering digunakan dalam akurasi klasifikasi. Tindakan ekstrinsik yang umum meliputi:

Skor F (juga disebut Ukuran F): Metrik ini menentukan keakuratan algoritme pengelompokan dengan melihat presisi dan akurasi ketika membandingkan pengklusteran yang diusulkan dengan ground truth. Dalam kasus skor F, semakin tinggi semakin baik.

Kemurnian: Metrik ini mengukur fraksi titik data yang ditetapkan dengan benar ke kelas atau kluster yang sama. Dalam kasus ukuran kemurnian, semakin tinggi semakin baik.

Indeks Rand: Ini adalah ukuran kemiripan antara label yang sebenarnya dan label yang diprediksi dari algoritma pengklusteran, mulai dari 0 hingga 1. Nilai yang lebih tinggi menunjukkan kinerja pengklusteran yang lebih baik.

Variasi Informasi (juga disebut Jarak Informasi Bersama): Ini mengukur jumlah informasi yang hilang dan diperoleh antara dua pengklusteran. Hal ini dapat terjadi antara pengklusteran kebenaran dasar dan pengklusteran yang dihasilkan algoritme atau antara dua pengklusteran yang berbeda. Semakin rendah semakin baik, karena hal ini menunjukkan jarak yang lebih kecil antara dua hasil pengklusteran.

Ada banyak area aplikasi di mana pengelompokan merupakan alat yang berharga untuk penambangan data atau analisis data eksploratif, kami hanya dapat mencantumkan sebagian kecil contoh area aplikasi di sini untuk memberikan gambaran betapa pentingnya jenis analisis ini.

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, pengklusteran 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 pengklusteran memproses piksel dalam gambar dan menentukan area dalam gambar yang mewakili kluster.

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.