Clustering - Skripsi Teknik Informatika

Clustering

Suatu cluster merupakan sekelompok entitas yang memiliki kesamaan dan memiliki perbedaan  dengan entitas dari kelompok lain(Everitt,1980).
Algoritma Clustering bekerja dengan mengelompokkan obyek-obyek data (pola, entitas, kejadian, unit,hasil observasi) ke dalam sejumlah cluster tertentu (Xu and Wunsch,2009).

Dengan kata lain algoritma Clustering melakukan pemisahan/ pemecahan/ segmentasi data ke dalam sejumlah kelompok (cluster) menurut karakteristik tertentu


Aplikasi Clustering

1.  Teknik
Digunakan dalam bidang biometric recognition & speech recognition, analisa sinyal radar, Information Compression,dan noise removal

2. Ilmu Komputer
Web mining,analisa database spatial,information retrieval,textual document collection,dan image segmentation

3. Medis
Digunakan dalam mendefinisikan taxonomi dalam bidang biologi, identifikasi fungsi protein dan gen, diagnosa penyakit dan penanganannya

4. Astronomy
Digunakan untuk mengelompokkan bintang dan planet, menginvestigasi formasi tanah, mengelompokkan wilayah /kota, digunakan dalam studi tentang sistem pada sungai dan gunung.

5. Sosial
Digunakan pada analisa pola perilaku,identifikasi hubungan diantara budaya yang berbeda, pembentukan sejarah evolusi bahasa, dan studi psikologi criminal

6. Ekonomi
Penerapan pada pengenalan pola pembelian& karakteristik  konsumen, pengelompokan perusahaan, analisa trend stok


Tujuan clustering
Tujuan clustering (pengelompokan) data dapat dibedakan menjadi dua, yaitu pengelompokan untuk pemahaman dan clustering untuk penggunaan (Prasetyo,2012)


1. clustering untuk pemahaman

Proses pengelompokan untuk tujuan pemahaman hanya sebagai proses awal untuk kemudian dilanjutkan dengan pekerjaan seperti summarization(rata-rata,standar deviasi), pelabelan kelas untuk setiap kelompok sehingga dapat digunakan sebagai data training dalam klasifikasi supervised.


2. clustering untuk penggunaan
Sementara jika untuk penggunaan, tujuan utama clustering biasanya adalah mencari prototipe kelompok yang paling representatif terhadap data, memberikan abstraksi dari setiap obyek data dalam kelompok dimana sebuah data terletak didalamnya.


Jenis-jenis Clustering

• Clustering dapat dibedakan menurut struktur kelompok ,keanggotaan data dalam kelompok, dan kekompakan data dalam kelompok.
• Menurut struktur kelompok clustering dibagi menjadi dua yaitu hierarchical dan partitioning.

Hierarchical clustering

• adalah metode clustering yang mengelompokkan data dengan urutan partisi berkalang, metode ini dikelompokkan menjadi dua metode yaitu agglomerative  dan divisive.
• keduanya mengorganisasi data ke dalam struktur hirarki berbasis matrix proximity, hasil dari Hierarcichal Clustering digambarkan dalam bentuk binary tree ataupun dendogram, root merupakan keseluruhan dataset dan tiap cabang merupakan data point, clustering akhir dapat diperoleh dari pemotongan dendogram pada level-level yang sesuai

Hierarchical clustering - agglomerative

metode agglomerative berawal dari obyek-obyek individual dimana pada awalnya banyaknya cluster sama dengan banyaknya obyek. Pertama-tama obyek-obyek yang paling mirip dikelompokkan, dan kelompok-kelompok awal ini digabungkan sesuai dengan kemiripannya. Akhirnya sewaktu kemiripan berkurang, semua subkelompok digabungkan menjadi satu cluster tunggal.

Hierarchical - divisive

Metode Hierarchical divisive merupakan proses kebalikan dari agglomerative.

Partitional clustering

Mengelompokkan datapoint kedalam k klaster tanpa struktur hirarki( Xu & Wunsch, 2009), metode ini membagi set data ke dalam sejumlah kelompok yang tidak saling overlap antara satu kelompok dengan kelompok lainnya, artinya setiap data hanya menjadi satu kelompok, termasuk dalam metode ini adalah K-Means dan DBSCAN

Keanggotaan data dalam kelompok

• Menurut keanggotaan data dalam kelompok, pengelompokan dibagi menjadi dua yaitu ekslusif dan overlap/tumpang tindih. 
• Dalam kategori ekslusif sebuah data hanya menjadi anggota satu kelompok saja dan tidak bisa menjadi anggota kelompok lainnya. Metode yang termasuk kategori ini adalah K-Means dan DBSCAN,
• Sedangkan yang masuk kategori overlap adalah metode clustering yang membolehkan sebuah data menjadi anggota di lebih dari satu kelompok, misalnya Fuzzy C-Means.

K-Means
Dalam machine-learning dan statistic K-Means merupakan metode analisis kelompok yang mengarah pada pembagian N obyek pengamatan ke dalam K kelompok (cluster), dimana setiap obyek dimiliki oleh sebuah kelompok dengan mean (rata-rata) dan metode ini mencoba untuk menemukan pusat dari kelompok (centroid) dalam data sebanyak iterasi perbaikan yang dilakukan.


Algoritma K-Means

• Tentukan jumlah cluster
• Alokasikan data ke dalam kelompok secara acak
• Hitung pusat cluster (centroid) menggunakan mean utk masing-masing kelompok
• Alokasikan masing-masing data ke centroid terdekat
• Kembali ke langkah 3, jika masih ada data yang berpindah cluster atau jika nilai centroid diatas nilai ambang, atau jika nilai pada fungsi obyektif yang digunakan masih diatas ambang

   Tabel Data nasabah

• Nasabah yang memiliki jumlah rumah dan mobil hampir sama akan berada pada kelompok nasabah yang sama.
• Nasabah yang memiliki jumlah rumah dan mobil yang berbeda akan berada pada kelompok nasabah yang berbeda

Iterasi 1

Langkah 1: Tentukan jumlah cluster yang diinginkan (misl:k=3)
Langkah 2: Pilih centroid awal secara acak : Pada langkah ini secara acak akan dipilih 3 buah data sebagai centroid,
misalnya:
data {B,E,F}
M1=(3,3) ,M2=(1,2),M3=(4,2)

Pada langkah ini setiap data akan ditentukan centroid terdekatnya, dan data tersebut akan ditetapkan sebagai anggota kelompok yang terdekat dengan centroid.
Data: (1,3) , centroid M1: (3,3), centroid M2: (1,2), centroid M3: (4,2)

Langkah 3: Tabel hasil perhitungan jarak

Dari tabel diatas didapatkan keanggotaan nasabah sbb:
Cluster 1 = {B},cluster 2 ={A,E,G,H},cluster 3= {C,D,F}


Menghitung BCV (Between Cluster Variation)

Pada langkah ini dihitung pula rasio antara besaran BCV (Between Cluster Variation) dengan WCV (Within Cluster Variation) :
         M1=(3,3) ,M2=(1,2),M3=(4,2)

BCV=d(m1,m2)+d(m1,m3)+d(m2,m3)
                      = 2.236+1.414+3
                      = 6,650
Dalam hal ini d(mi,mj) menyatakan jarak Euclidean dari mi ke mj


WCV (Within Cluster Variation)
memilih jarak terkecil antara data dengan centroid pada masing-masing cluster

WCV=12+02+12+1. 4142+02+02+12+1.4142=7
Sehingga Besar Rasio = BCV/WCV =  6.650 / 7 = 0.950
Karena langkah ini merupakan iterasi 1 maka lanjutkan ke langkah berikutnya


Langkah 4:

Pembaruan centroid dengan menghitung rata-rata nilai pada masing-masing cluster
     Cluster 1 = {B},cluster 2 ={A,E,G,H},cluster 3= {C,D,F}

Sehingga didapatkan centroid baru yaitu : m1=(3,3),m2=(1.25,1.75),m3=(4.33,2.67)

Kembali Langkah 3: 

jika masih ada data yang berpindah cluster
atau jika nilai centroid diatas nilai ambang,
atau jika nilai pada fungsi obyektif yang digunakan masih diatas ambang (Rasio BCV/WCV lebih > dari Rasio Iterasi sebelumnya).
Selanjutnya pada langkah ini dilakukan penempatan lagi data dalam centroid terdekat sama seperti yang dilakukan dilangkah-3


State of the art Clustering

• Algoritma K-Means merupakan bagian dari algoritma partitioning clustering, algoritma partitional clustering yang lain diantaranya: Mixture-Based Density,Graph Theory-Based Clustering,Fuzzy Clustering. 
• Sementara Metode Clustering yang lain selain partitional diantaranya: Hierarchical Clustering, Neural Network-Based Clustering, Kernel-based Clustering, dan Sequential Data Clustering (Xu and Wunsch,2009).