Metode-metode Dasar dalam Clustering

Menurut berbagai literatur, ada banyak algoritma clustering. Jadi agak sulit untuk memberikan pengkategorian yang pas untuk berbagai macam metode clustering karena akan menyebabkan overlap dalam kategori-kategori tersebut sehingga suatu metode mungkin saja memiliki ciri-ciri dari beberapa kategori. Namun, mungkin bermanfaat apabila disajikan gambaran yang relatif lebih terorganisir tentang metode-metode clustering. Secara umum, metode-metode utama dalam clustering yang mendasar bisa digolongkan menjadi kategori-kategori berikut dibawah ini. [Baca juga: Metode-metode dalam Data Mining]

Metode-metode partisi (partitioning methods): Misalkan, ditentukan satu set object sebanyak n, metode partisi akan membuat partisi data sebanyak k, dimana setiap partisi akan mewakili satu cluster dan k <= n. Artinya, metode ini akan membagi data menjadi kelompok/grup sebanyak k sedemikian rupa sehingga masing-masing kelompok/grup berisi minimal satu object. Dengan kata lain, metode partisi melakukan partisi satu-tingkat pada dataset. Metode-metode partisi dasar biasanya mengadopsi apa yang disebut dengan exclusive cluster separation (atau pemisahan cluster ekslusif). Artinya, masing-masing object harus tepat masuk dalam satu kelompok/grup. Syarat ini bisa dilonggarkan, misalnya, dalam berbagai teknik partisi samar (fuzzy).

Kebanyakan metode-metode partisi adalah berbasiskan jarak (distance-based). Misalnya, ditentukan k, yaitu jumlah partisi yang akan dibuat, metode partisi akan membuat partisi awal. Kemudian, metode ini menggunakan teknik pemindahan object secara iteratif untuk mencoba memperbaiki partisi dengan memindah-mindahkan object-object dari satu kelompok/grup ke kelompok/grup lainnya. Kriteria umum dari partisi yang baik adalah bahwa object-object dalam cluster yang sama adalah saling berdekatan atau terkait satu sama lain, tetapi object-object pada cluster yang berbeda tidaklah berdekatan atau jauh atau sangat berbeda. Ada beberapa macam kriteria lainnya untuk menilai kualitas partisi. Metode-metode partisi tradisional bisa diterapkan juga pada clustering dengan ruang data yang lebih kecil (subspace), dibandingkan dengan mencari ruang data yang utuh/full. Hal ini akan sangat berguna bila ada banyak atribut dan data yang bersifat tersebar. Usaha mendapatkan hasil yang optimal secara global dalam clustering berbasis partisi seringkali mahal secara komputasi, dan berpotensi memerlukan enumerasi yang lengkap dan menyeluruh dari semua kemungkinan partisi. Sebaliknya, kebanyakan aplikasi mengadopsi metode-metode heuristic yang sudah populer, seperti pendekatan 'greedy' seperti pada algoritma-algoritma k-means dan k-medoids, yang secara progresif meningkatkan kualitas clustering dan mendekati optimum secara lokal. Metode-metode clustering heuristic seperti ini akan berjalan dengan baik untuk menemukan cluster-cluster yang berbentuk bulat pada database yang kecil hingga sedang. Untuk mendapatkan cluster-cluster dengan bentuk-bentuk yang kompleks dan pada dataset yang sangat besar, metode-metode berbasis partisi perlu diperluas lagi. Metode-metode clustering berbasis partisi akan dibahas pada post artikel lainnya dengan lebih mendalam.

Metode-metode hirarki (hierarchical methods): Suatu metode hirarki membuat dekomposisi atau penguraian atau pemecahan object-object secara hirarki pada dataset object-object tertentu. Metode hirarki bisa digolongkan menjadi agglomerative maupun divisive, tergantung bagaimana dekomposisi atau penguraian atau pemecahan dijalankan. Pendekatan agglomerative, disebut juga dengan pendekatan bottom-up, dimulai dengan masing-masing object yang membentuk kelompok/grup terpisah. Kemudian secara berturut-turut menggabungkan object-object atau kelompok-kelompok yang berdekatan satu sama lain, hingga semua kelompok/grup tergabung menjadi satu (tingkat paling puncak/atas dari hirarki), atau bila ada suatu kondisi untuk berhenti sudah terpenuhi. Jadi untuk agglomerative adalah penggabungan object-object secara hirarki dan bukan penguraian atau pemecahan.

Metode-metode clustering hirarki bisa berbasis jarak (distance-based)  atau berbasis densitas (density-based)  dan berbasis kontinyuitas (continuity-based). Berbagai macam perluasan metode-metode hirarki mempertimbangkan clustering dalam subspace  juga (sub-ruang atau ruang data yang lebih kecil).

Metode-metode hirarki memiliki kelemahan yaitu bahwa sekali suatu langkah sudah dilakukan (baik penggabungan maupun pemisahan), langkah tersebut tidak bisa dibatalkan. Kekakuan ini membawa keuntungan tersendiri dalam arti bahwa hal tersebut membuat biaya komputasi semakin kecil karena tidak perlu mengkhawatirkan jumlah kombinasi terhadap berbagai pilihan yang berbeda-beda. Teknik-teknik seperti ini tidak bisa mengoreksi keputusan-keputusan yang salah; namun, metode-metode untuk meningkatkan kualitas cluastering hirarki sudah diusulkan oleh banyak ahli. Metode-metode clustering hirarki akan dibahas lebih mendalam pada post artikel lainnya.

Metode-metode berbasis densitas (density-based methods): Kebanyakan metode-metode partisi meng-cluster object-object berdasarkan jarak antar object. Metode-metode seperti ini bisa menghasilkan cluster-cluster yang hanya berbentuk bulat dan akan sulit menemukan cluster-cluster yang berbentuk sembarangan. Beberapa metode clustering lainnya sudah dikembangkan yaitu berbasis gagasan densitas. Gagasan umumnya adalah melanjutkan suatu cluster tertentu selama densitas-nya (jumlah object atau data point) dalam sekeliling (neighborhood) melebihi suatu ambang batas (treshold). Misalnya, untuk masing-masing titik data (data point) di dalam cluster tertentu, di sekelilingnya dengan radius tertentu harus berisi minimal jumlah tertentu titik data. Metode yang seperti ini bisa digunakan untuk memfilter 'noise' (data yang agak mengganggu) atau 'outlier' (pencilan) dan mendapatkan cluster-cluster dengan bentuk yang sembarangan.

Metode-metode berbasis densitas bisa membagi suatu set object menjadi beberapa cluster eksklusif, atau hirarki dari cluster-cluster. Pada umumnya, metode-metode berbasis densitas hanya mempertimbangkan cluster-cluster eksklusif, dan tidak mempertimbangkan cluster-cluster samar (fuzzy). Selain itu, metode-metode berbasis densitas bisa diperluas dari clustering yang full-space (ruang data yang utuh/full) ke clustering subspace (ruang data yang lebih kecil). Metode-metode clustering berbasis densitas akan dibahas pada post artikel lainnya dengan lebih mendalam.

Metode berbasis grid (grid-based methods): Metode-metode berbasis grid meng-kuantisasikan ruang object menjadi jumlah sel yang terbatas yang membentuk suatu struktur grid. Semua pengerjaan clustering dilakukan pada struktur grid (misanya, pada ruang yang sudah dikuantisasi). Keuntungan utama dari pendekatan ini adalah waktu pemrosesannya yang sangat cepat, yang biasanya tidak bergantung pada jumlah object data tetapi bergantung hanya pada jumlah sel pada setiap dimensi pada ruang yang sudah dikuantisasi. Dengan menggunakan grid seringkali menjadi sangat efisien bagi problem-problem pada berbagai penambangan data spasial (spatial data mining) termasuk clustering. Karena itu, metode-metode berbasis grid bisa diintegrasikan dengan metode-metode clustering lainnya seperti metode-metode berbasis densitas dan metode-metode hirarki. Clustering berbasis grid akan dibahas lebih dalam pada post artikel lainnya.

Metode-metode di atas diringkas dalam tabel dibawah ini.

Gambaran sekilas yang relatif terorganisir metode-metode dasar
dalam clustering dan ciri-cirinya

Perlu dicatat bahwa beberapa algoritma clustering mengintegrasikan lebih dari satu metode clustering, sehingga terkadang sangat sulit untuk menggolongkan suatu algoritma tertentu sebagai suatu metode yang unik milik satu golongan kategori metode clustering tertentu. Selain itu, beberapa aplikasi mungkin telah memiliki kriteria clustering yang memerlukan integrasi dari beberapa teknik clustering.

Artikel terkait clustering:

• Pengertian Clustering atau Analisa Cluster
• Metode-metode Dasar dalam Clustering
• Penjelasan Cara Kerja Algoritma k-Means: Suatu Teknik Clustering Partisi Berbasis Centroid
• Contoh Ilustrasi Clustering Dengan Menggunakan k-Means dan Variannya: k-Modes
• Kelemahan k-Means dan Contohnya
• Penjelasan k-Medoids, Algoritma, dan Contohnya
• k-Means vs k-Medoids, Kelemahan k-Medoids dan Solusinya: CLARA