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)
Manfaat Clustering
1.
Clustering merupakan metode
segmentasi data yang sangat berguna dalam prediksi dan analisa masalah bisnis
tertentu. Misalnya Segmentasi pasar, marketing dan pemetaan zonasi wilayah.
2.
Identifikasi
obyek dalam bidang berbagai bidang seperti computer vision dan image
processing.
Syarat Clustering
Menurut Han dan
Kamber, 2012, syarat sekaligus tantangan yang harus dipenuhi oleh suatu
algoritma clustering adalah:
1.
Skalabilitas
Suatu metode clustering
harus mampu menangani data dalam jumlah yang besar. Saat ini data dalam jumlah
besar sudah sangat umum digunakan dalam berbagai bidang misalnya saja suatu
database. Tidak hanya berisi ratusan objek, suatu database dengan ukuran besar
bahkan berisi lebih dari jutaan objek.
2.
Kemampuan
analisa beragam bentukdata
Algortima
klasteriasi harus mampu dimplementasikan pada berbagai macam bentuk data
seperti data nominal, ordinal maupun gabungannya.
3.
Menemukan
cluster dengan bentuk yang tidak terduga
Banyak algoritma clustering
yang menggunakan metode Euclidean atau Manhattan yang
hasilnya berbentuk bulat. Padahal hasil clustering dapat berbentuk
aneh dan tidak sama antara satu dengan yang lain. Karenanya dibutuhkan
kemampuan untuk menganalisa cluster dengan bentuk apapun pada suatu
algoritma clustering.
3.
Kemampuan
untuk dapat menangani noise
Data tidak selalu
dalam keadaan baik. Ada kalanya terdapat data yang rusak, tidak dimengerti atau
hilang. Karena system inilah, suatu algortima clustering dituntut
untuk mampu menangani data yang rusak.
4.
Sensitifitas
terhadap perubahan input
Perubahan atau
penambahan data pada input dapat menyebabkan terjadi perubahan pada cluster
yang telah ada bahkan bisa menyebabkan perubahan yang mencolok apabila
menggunakan algoritma clustering yang memiliki tingkat sensitifitas
rendah.
5.
Mampu
melakukan clustering untuk data dimensi tinggi
Suatu kelompok
data dapat berisi banyak dimensi ataupun atribut. Untuk itu diperlukan
algoritma clustering yang mampu menangani data dengan dimensi yang
jumlahnya tidak sedikit.
6.
Interpresasi
dan kegunaan
Hasil dari clustering
harus dapat diinterpretasikan dan berguna.
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.
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.
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
Komentar
Posting Komentar