Apa itu clustering atau pengelompokan?

Ada berbagai cara untuk menggunakan pengelompokan dalam machine learning, mulai 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 lebih besar yang perlu dipecah menjadi beberapa kumpulan data atau dikurangi menggunakan reduksi dimensi. Dalam semua kasus ini, pengelompokan dapat menjadi langkah dalam prapemrosesan.

Contoh klaster dapat mencakup genre musik, kelompok pengguna yang berbeda, segmen utama dari segmentasi pasar, jenis lalu lintas jaringan pada klaster server, grup teman di jejaring sosial, atau beragam jenis kategori lainnya. Proses pengelompokan dapat menggunakan satu fitur data atau semua fitur yang ada dalam data.

Akan sangat membantu jika kita menganggap pengelompokan sebagai upaya menemukan pengelompokan 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 algoritme pengelompokan yang digunakan, Anda mungkin dapat menghapus outlier dari data Anda atau memberi label sebagai outlier. Klastering juga dapat membantu dalam deteksi anomali dengan mendeteksi titik data apa yang tidak terkandung dalam sebuah klaster atau hanya berkaitan secara lemah dengan sebuah klaster dan dengan demikian dapat menjadi anomali dalam proses pembuatan data.

Klastering 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 klaster.

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

Ada banyak algoritme pengelompokan yang berbeda karena ada beberapa cara untuk mendefinisikan klaster. Pendekatan yang berbeda akan bekerja dengan baik untuk berbagai jenis model yang berbeda tergantung pada ukuran data input, dimensi data, kekakuan kategori, dan jumlah klaster dalam kumpulan data. Perlu diperhatikan bahwa satu algoritme 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 pengelompokan. Ada teknik lain seperti pengelompokan spektral atau pengelompokan 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 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:

Aglomerasi: Dalam pengelompokan aglomerasi, pendekatan bawah ke atas dimulai dengan satu titik data dan menggabungkan klaster secara berurutan 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 antara klaster yang rendah, algoritma akan beralih ke kumpulan klaster yang baru dibuat dan mengulangi proses ini hingga ada satu node akar di bagian atas grafik hierarki. Ada berbagai pilihan yang memungkinkan terkait bagaimana klaster ini harus digabungkan satu sama lain dengan menyeimbangkan antara kualitas dan efisiensi pengelompokan. Dalam pengelompokan satu tautan, jarak ter pendek antara pasangan titik data dalam dua klaster digunakan sebagai ukuran kemiripan. Pada tautan semua pasangan, rata-rata dari semua pasangan titik data digunakan, sedangkan pada tautan sampel, sampel dari titik data di dua klaster digunakan untuk menghitung jarak rata-rata. Dalam tautan centroid, jarak antara centroid yang digunakan. Salah satu tantangan dalam metode aglomerasi 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, sehingga terus semakin membesar dan menarik lebih banyak titik data ke dalam klaster mereka. Kerugian lainnya adalah bahwa metode aglomerasi mungkin jauh lebih lambat daripada metode divisif yang membangun hierarki.

Divisif: Dalam metode pengelompokan hierarkis divisif, pendekatan dari atas ke bawah secara berurutan membagi titik-titik data menjadi struktur seperti pohon. Langkah pertama adalah membagi kumpulan data menjadi klaster menggunakan metode pengelompokan datar seperti K-Mean. Klaster dengan Jumlah Kuadrat Kesalahan (SSE) terbesar kemudian dibagi lebih lanjut menggunakan metode pengelompokan datar. Algoritma berhenti saat mencapai tiap node atau SSE minimum. Partisi divisif memungkinkan fleksibilitas yang lebih besar baik dalam hal struktur pohon hierarkis maupun 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 adalah tepat dua. Hal ini memungkinkan pembuatan struktur pohon yang memungkinkan kompromi berbeda dalam menyeimbangkan kedalaman node dan bobot node (jumlah titik data dalam node). Pengelompokan hierarkis divisif bisa berlangsung lebih cepat daripada pengelompokan hierarkis aglomerasi, terutama ketika data tidak memerlukan pembuatan pohon hingga ke tiap titik data.

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 ulangi langkah Ekspektasi sampai persamaan tercapai 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 titik setidaknya dalam jumlah 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 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.

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

Pengukuran intrinsik adalah metrik evaluasi untuk analisis klaster 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 klasternya sendiri dan semua klaster lainnya. Nilai metrik berkisar dari -1 hingga +1. Nilai tinggi menunjukkan bahwa objek tersebut cocok dengan klasternya sendiri dan tidak cocok dengan klaster tetangga.

Indeks Davies-Bouldin: Metrik ini menghitung rasio jarak dalam klaster dengan jarak antara klaster. Semakin rendah skor indeks, semakin baik kinerja pengelompokan.

Indeks Calinski-Harabasz: Dikenal juga sebagai Kriteria Rasio Varians, indeks ini mengukur rasio varians antara klaster dan varians dalam klaster. Semakin tinggi rasio Calinski-Harabasz berarti semakin baik penetapan suatu klaster.

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

Pengukuran ekstrinsik menggunakan kebenaran dasar atau informasi eksternal untuk menilai validitas kinerja algoritme pengelompokan. 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 (disebut juga Ukuran F): Metrik ini menentukan keakuratan algoritma pengelompokan dengan melihat presisi dan recall ketika membandingkan pengelompokan yang diusulkan dengan kebenaran dasar. Dalam hal skor F, semakin tinggi semakin baik.

Kemurnian: Metrik ini mengukur fraksi titik data yang ditetapkan dengan benar ke kelas atau klaster yang sama di tempat titik berada. Dalam hal ukuran kemurnian, semakin tinggi semakin baik.

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

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

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, 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.