Clustering

Clustering adalah metode penganalisaan data, yang sering dimasukkan sebagai salah satu metode Data Mining, yang tujuannya adalah untuk mengelompokkan data dengan karakteristik yang sama ke suatu ‘wilayah’ yang sama dan data dengan karakteristik yang berbeda ke ‘wilayah’ yang lain.

Ada beberapa pendekatan yang digunakan dalam mengembangkan metode clustering. Dua pendekatan utama adalah clustering dengan pendekatan partisi dan clustering dengan pendekatan hirarki. Clustering dengan pendekatan partisi atau sering disebut dengan partition-based clustering mengelompokkan data dengan memilah-milah data yang dianalisa ke dalam cluster-cluster yang ada. Clustering dengan pendekatan hirarki atau sering disebut dengan hierarchical clustering mengelompokkan data dengan membuat suatu hirarki berupa dendogram dimana data yang mirip akan ditempatkan pada hirarki yang berdekatan dan yang tidak pada hirarki yang berjauhan. Di samping kedua pendekatan tersebut, ada juga clustering dengan pendekatan automatic mapping (Self-Organising Map/SOM)

Clustering Dengan Pendekatan Partisi

K-Means

Salah satu metode yang banyak digunakan dalam melakukan clustering dengan partisi ini adalah metode k-means. Secara umum metode k-means ini melakukan proses pengelompokan dengan prosedur sebagai berikut:

• Tentukan jumlah cluster
• Alokasikan data secara random ke cluster yang ada
• Hitung rata-rata setiap cluster dari data yang tergabung di dalamnya
• Alokasikan kembali semua data ke cluster terdekat
• Ulang proses nomor 3, sampai tidak ada perubahan atau perubahan yang terjadi masih sudah di bawah treshold

Prosedur dasar ini bisa berubah mengikuti pendekatan pengalokasian data yang diterapkan, apakah crisp atau fuzzy. Setelah meneliti clustering dari sudut yang lain, saya menemukan bahwa k-means clustering mempunyai beberapa kelemahan.
Hal-hal terkait dengan metode k-means saya rangkum dalam tulisan saya yang dapat di-download di sini (k-means – penerapan, permasalahan dan metode terkait).

Penjelasan lengkap tentang k-means dapat juga dilihat pada Yudi Agusta’s K-Means Page.

Mixture Modelling (Mixture Modeling)

Mixture modelling (mixture modeling) merupakan metode pengelompokan data yang mirip dengan k-means dengan kelebihan penggunaan distribusi statistik dalam mendefinisikan setiap cluster yang ditemukan. Dibandingkan dengan k-means yang hanya menggunakan cluster center, penggunaan distribusi statistik ini mengijinkan kita untuk:

• Memodel data yang kita miliki dengan setting karakteristik yang berbeda-beda
• Jumlah cluster yang sesuai dengan keadaan data bisa ditemukan seiring dengan proses pemodelan karakteristik dari masing-masing cluster
• Hasil pemodelan clustering yang dilaksanakan bisa diuji tingkat keakuratannya

Distribusi statistik yang digunakan bisa bermacam-macam mulai dari yang digunakan untuk data categorical sampai yang continuous, termasuk di antaranya distribusi binomial, multinomial, normal dan lain-lain. Beberapa distribusi yang bersifat tidak normal seperti distribusi Poisson, von-Mises, Gamma dan Student t, juga diterapkan untuk bisa mengakomodasi berbagai keadaan data yang ada di lapangan. Beberapa pendekatan multivariate juga banyak diterapkan untuk memperhitungkan tingkat keterkaitan antara variabel data yang satu dengan yang lainnya.

Klik Yudi Agusta’s Mixture Modelling Page untuk penjelasan lebih rinci.

Clustering dengan Pendekatan Hirarki

Clustering dengan pendekatan hirarki mengelompokkan data yang mirip dalam hirarki yang sama dan yang tidak mirip di hirarki yang agak jauh. Ada dua metode yang sering diterapkan yaitu agglomerative hieararchical clustering dan divisive hierarchical clustering. Agglomerative melakukan proses clustering dari N cluster menjadi satu kesatuan cluster, dimana N adalah jumlah data, sedangkan divisive melakukan proses clustering yang sebaliknya yaitu dari satu cluster menjadi N cluster.

Beberapa metode hierarchical clustering yang sering digunakan dibedakan menurut cara mereka untuk menghitung tingkat kemiripan. Ada yang menggunakan Single Linkage, Complete Linkage, Average Linkage, Average Group Linkage dan lain-lainnya. Seperti juga halnya dengan partition-based clustering, kita juga bisa memilih jenis jarak yang digunakan untuk menghitung tingkat kemiripan antar data.

Salah satu cara untuk mempermudah pengembangan dendogram untuk hierarchical clustering ini adalah dengan membuat similarity matrix yang memuat tingkat kemiripan antar data yang dikelompokkan. Tingkat kemiripan bisa dihitung dengan berbagai macam cara seperti dengan Euclidean Distance Space. Berangkat dari similarity matrix ini, kita bisa memilih lingkage jenis mana yang akan digunakan untuk mengelompokkan data yang dianalisa.

Clustering Dengan Pendekatan Automatic Mapping

Self-Organising Map (SOM)

Self-Organising Map (SOM) merupakan suatu tipe Artificial Neural Networks yang di-training secara unsupervised. SOM menghasilkan map yang terdiri dari output dalam dimensi yang rendah (2 atau 3 dimensi). Map ini berusaha mencari property dari input data. Komposisi input dan output dalam SOM mirip dengan komposisi dari proses feature scaling (multidimensional scaling).

Walaupun proses learning yang dilakukan mirip dengan Artificial Neural Networks, tetapi proses untuk meng-assign input data ke map, lebih mirip dengan K-Means dan kNN Algorithm. Adapun prosedur yang ditempuh dalam melakukan clustering dengan SOM adalah sebagai berikut:

• Tentukan weight dari input data secara random
• Pilih salah satu input data
• Hitung tingkat kesamaan (dengan Eucledian) antara input data dan weight dari input data tersebut dan pilih input data yang memiliki kesamaan dengan weight yang ada (data ini disebut dengan Best Matching Unit (BMU))
• Perbaharui weight dari input data dengan mendekatkan weight tersebut ke BMU dengan rumus:

  Wv(t+1) = Wv(t) + Theta(v, t) x Alpha(t) x (D(t) – Wv(t))

  Dimana:

  • Wv(t): Weight pada saat ke-t
  • Theta (v, t): Fungsi neighbourhood yang tergantung pada Lattice distance antara BMU dengan neuron v. Umumnya bernilai 1 untuk neuron yang cukup dekat dengan BMU, dan 0 untuk yang sebaliknya. Penggunaan fungsi Gaussian juga memungkinkan.
  • Alpha (t): Learning Coefficient yang berkurang secara monotonic
  • D(t): Input data
• Tambah nilai t, sampai t < Lambda, dimana Lambda adalah jumlah iterasi

Variasi Metode Clustering

• Quality Threshold Clustering Method
• Locality Sensitive Hashing
• Algoritma Rock
• Hierarchical Frequent Term-Base Clustering
• Suffix Tree Clustering
• Single Pass Clustering
• Neighborhood Clustering
• Sequence Clustering
• Spectral Clustering
• Clustering on Frequent Tree
• Latent Class Cluster Analysis a.k.a. Latent Profile Analysis a.k.a. Mixture Model for Continuous Variabel
• Latent Class Analysis a.k.a. Mixture Model for Categorical Variable

Hal-hal Terkait Dengan Clustering

• Analisa Faktor
• Singular Value Decomposition
• Eigen Value and Eigen Vector
• Similarity Measure
• Feature Discretisation
• Feature Selection
• Feature Scaling
• Indexing Method For Searching

Clustering Implementation

• Document Clustering Algorithm, Document Feature Extraction
• Image Clustering

Corat-coret Saya Mengenai Clustering

K-Means – Penerapan, Permasalahan dan Metode Terkait; Akurasi Hasil Pemodelan K-Means

Links Tentang Clustering

Under Construction. Sorry!Co