KLASTERISASI DATA DISKRET MENGGUNAKAN ALGORITMA MULTINOMIAL GENERALIZED DIRICHLET MIXTURE PADA CITRA

Seminar Nasional Teknologi Informasi dan Komunikasi 2012 (SENTIKA 2012) Yogyakarta, 10 Maret 2012

ISSN: 2089-9815

KLASTERISASI DATA DISKRET MENGGUNAKAN ALGORITMA MULTINOMIAL GENERALIZED DIRICHLET MIXTURE PADA CITRA Ahmad Saikhu1, Hanny Saputro2 Jurusan Teknik Informatika, Fakultas Teknologi Informasi Institut Teknologi Sepuluh Nopember, Surabaya Email: [email protected], [email protected] ABSTRAKS Klasterisasi adalah salah satu metode data mining yang digunakan untuk mempartisi data dengan karakteristik yang sama ke suatu kelas yang sama dan data dengan karakter yang berbeda ke kelas yang lain. KMeans melakukannya dengan menentukan jumlah cluster, mempartisi data ke dalam kelas secara random, dan menghitung centroid masing-masing kelas. Partisi data ke dalam kelas berdasarkan jarak minimum data ke centroid. Metode Kmeans mempunyai kelemahan pada hasil yang mengarah pada lokal optima, dan data yang seringkali mengalami overlapping. N. Bouguila dan W. ElGuebaly memperkenalkan sebuah algoritma baru sebagai alternatif yaitu, Multinomial Generalized Dirichlet Mixture. Beberapa kelebihan MGDM dari metode Kmeans adalah kemampuan untuk mendeteksi keberadaan data yang mengalami overlapping. Multinomial Generalized Dirichlet Mixture mempunyai dua algoritma utama yaitu, Spherical K-Means dengan optimasinya menggunakan PSO (Particle Swarm Optimization) dan Expectation Maximation (EM). Uji coba dilakukan terhadap tiga dataset image yang berbeda (masing-masing dataset terdapat 1000 data) dengan beberapa variasi jumlah data yang digunakan dalam proses training yaitu 500, 625, 750, dan 875. Berdasarkan hasil uji coba, semakin besar jumlah data training nilai akurasi yang didapat cenderung menurun sebaliknya nilai presisi cenderung meningkat. Kata Kunci: Cluster, Data Diskret, MGDM, hybrid PSO, Spherical K-Means, Expectation Maximation Tujuan dari pengerjaan peneletian ini adalah mengimplementasikan algoritma MGDM dengan mengujikannya pada tiga buah dataset image dengan pengambilan histogram sebagai fiturnya. Dataset yang diambil bersifat supervised dengan masing-masing dataset terdapat 1000 data yang terbagi dalam 25 kelas. Uji coba dilakukan dengan pengambilan beberapa variasi jumlah data yang digunakan pada proses training diantaranya 500, 625, 750, dan 875. Berdasarkan hasil uji coba didapatkan bahwa jumlah data yang digunakan dalam proses training menggunakan algoritma MGDM berpengaruh terhadap nilai akurasi missclassified image (sebuah image yang seharusnya berada pada kelas i, tetapi akhirnya menempati kelas j setelah dilakukan training, dimana i ≠ j) dari tiap-tiap dataset. Penurunan nilai akurasi tersebut tidak selalu menyebabkan berkurangnya persentase presisi saat dilakukan proses testing.

1.

PENDAHULUAN Klasterisasi adalah salah satu metode data mining yang digunakan untuk mengelompokkan data dengan karakteristik yang sama ke suatu wilayah yang sama dan data dengan karakteristik yang berbeda ke wilayah yang lain. K-Means (KM) adalah salah satu algoritma paling populer yang digunakan untuk proses partisi karena efisiensinya pada saat menangani data yang banyak. KM tergolong mudah untuk diimplementasikan dan dapat mancapai titik konvergen secara cepat. Namun terkadang hasilnya mengarah pada lokal optima[Ciu, 2005]. Permasalahan lain yang juga muncul pada saat menggunakan KM untuk melakukan clustering adalah overlapping data. Untuk mengatasi hal tersebut [Bougila, 2008] mengusulkan sebuah algoritma baru yang diberi nama Multinomial Generalized Dirichlet Mixture (MGDM). Tujuan dari algoritma ini adalah melakukan maksimasi terhadap KM dengan memperkenalkan Spherical K-Means (SPKMeans) dan optimasi dengan menggunakan Expectation Maximation (EM). Beberapa kelebihan Mixture Modelling dari metode sebelumnya adalah terdapatnya kemampuan untuk mendeteksi keberadaan suatu cluster yang overlap dengan cluster yang lain. Mixture Modelling telah digunakan dalam berbagai bidang seperti computer vision, image processing dan pattern recognition yang sebagian besar data bersifat diskret. Penulis juga melakukan eksplorasi terhadap algoritma hybrid PSO untuk membantu SPKMeans terlepas dari lokal optima.

2.

SPHERICAL K-MEANS Algoritma K-Means yang standar mempunyai rumus objective function untuk meminimalisasi error sebagai berikut: ∑ || || (1) yaitu dimana k(x) = ,…, min index dari centroid dengan jarak terdekat ke x, N adalah jumlah total data vektor. Spherical K-Means muncul dengan menggunakan konsep maksimasi nya serta untuk mengatasi data dengan jumlah dan dimensi yang besar. SPKMeans mempunyai cara perhitungan 98

Seminar Nasional Teknologi Informasi dan Komunikasi 2012 (SENTIKA 2012) Yogyakarta, 10 Maret 2012

cosine similarity yang berbeda dengan KM dan setiap data pada SPKMeans dinormalisasi menjadi unit vektor nya 1 . Sehingga menjadi set dari unit vektor , ,…, centroid. ∑ (2) . Perbedaan dimana arg mendasar dari standar k-means adalah estimasi mean vektor perlu untuk dinormalisasikan menjadi unit-length nya. (3)

ISSN: 2089-9815

(6) Variabel i merupakan partikel ke-i dalam kawanan, t merupakan jumlah iterasi, Vi adalah kecepatan partikel ke-i, Xi adalah variabel partikel vektor (contohnya posisi vektor) dari partikel ke-i. R1 dan R2 merupakan bilangan acak antara 0 dan 1, ω adalah beban partikel disebut sebagai innertia weight, C1 dan C2 adalah dua konstanta bilangan, sering disebut sebagai cognitive confidence coefficent. Dalam paper ini, setiap partikel di dalam PSO merepresentasikan k centroid dari sebuah dataset. Partikel terbaik akan digunakan sebagai inisialisasi centroid pada algoritma SPKMeans [Cui, 2005]. Fitness Function yang digunakan pada PSO ini adalah:

Algorithm: spherical k-means (SPKMeans) Input: sebuah set unit-length vektor X = {X1,…,XN} sebanyak N, total cluster K dan centroid awal μ. Output: sebuah partisi vektor data yang diberikan oleh cluster vektor Y = {y1,…,yN}, yn {1,…,K} dan μ = {μ1, μ2,...,μk}. Steps: 1. Initialization: inisialisasi unit-length vektor ; sebagai cluster centroid , ,…, 2. Penetapan kelas: untuk setiap vektor data , tentukan arg max ; 3. Estimasi centroid; untuk tiap cluster k, misalkan | , estimasikan centroid sebagai ∑

∑

∑

,

(7) adalah vektor data ke j yang ada pada dimana cluster i, adalah centroid cluster i, adalah total adalah total cluster, data yang ada pada cluster i, , adalah jarak antara vektor data ke j dan yang ada pada cluster i dengan centroid cluster i. Jarak dua vektor dihitung dengan persamaan (8) berikut:

∑

∑

,

4. Stop jika y tidak mengalami perubahan; sebaliknya pergi ke Step 2. Gambar 1. Algoritma Spherical K-means

(8)

dan adalah dua vektor data, dimana adalah dimensi data, dan adalah nilai dari dimensi ke k pada vektor dan . Algoritma Hybrid PSO dapat dilihat pada Gambar 2.

Sebuah penelitian menarik bahwa ketika X dan μ keduanya berupa unit vektor, Euclidean distance dari KM setara dengan cosine similarity dari SPKMeans untuk proses pengelompokan data ke dalam cluster similarnya [Zhong, 2005]. 2 2 2 (4)

4.

EXPECTATION MAXIMATION Expectation Maximation (EM) merupakan salah satu metode untuk menemukan estimasi maximum likelihood dari sebuah dataset dengan distribusi tertentu. Langkah-langkah algoritma EM dapat dibagi menjadi tiga bagian besar yaitu dua langkah untuk Expectation dan Maximation serta satu langkah untuk Optimization. a. E-STEP (Expectation Step) Di dalam langkah ini, secara singkat menggunakan rumus sebagai berikut:

3.

HYBRID PARTICLE SWARM OPTIMIZATION Metode PSO dikembangkan oleh Ebenhart dan Kennedy (1995) yang terinspirasi oleh tingkah laku burung flock. PSO menggunakan sekumpulan partikel yang saling bekerjasama. Setiap partikel mempunyai kemampuan untuk mengevaluasi kemampuannya dan kemampuan partikel lain di sekitarnya. Setiap partikel menyimpan solusi yang kemungkinan merupakan solusi terbaik untuk semua partikel yang ada. PSO diinisialisasi dengan pembuatan matriks secara acak. Matriks yang mengandung nilai variabel tersebut selanjutnya disebut dengan partikel. Masing-masing partikel akan berpindah berdasarkan jarak dan kecepatan. Partikel akan memperbaharui kecepatan sesuai dengan persamaan (5) dan posisinya diukur dari solusi terbaik lokal dan global dengan persamaan (6).

| ,

|

∑

(9)

dimana didapat dari perhitungan dengan distribusi gaussian dengan parameter mean dan kovarian. b. M-STEP (Maximation Step) Di dalam tahap ini, merupakan bagian untuk mencari nilai alpha / prior, mu, dan sigma baru yang didapat secara berturut-turut dengan menggunakan rumus ∑ | , (10) ∑ ∑

(5) 99

| , ,

(11)

Seminar Nasional Teknologi Informasi dan Komunikasi 2012 (SENTIKA 2012) Yogyakarta, 10 Maret 2012

Σ

∑

,

∑

| ,

ISSN: 2089-9815

mendapatkan elemen masing-masing vektor. Algoritma ditunjukkan pada Gambar 3.  e. Menerapkan Method of Moment (MM) berdasarkan persamaan (16) untuk masingmasing komponen kelas. ∏ (16)

(12)

Pada rumus tersebut masing-masing merupakan nilai optimal dengan asumsi sudah didapatkan nilai parameter, Θ, yang sudah optimal atau maksimal juga, dengan menggunakan rumus , (13)

f. Menentukan keanggotaan setiap data ke dalam masing-masing kelas, dan asumsikan bahwa model ini adalah benar. g. Jika model sebelumnya dan model baru yang diperoleh adalah sama satu sama lain, selesai, jika tidak kembali ke step d.

c. Q-Function Dengan asumsi sudah ditentukan sebelumnya nilai threshold atau batas, fungsi Q ini digunakan untuk optimasi komputasi pada program. Disebut optimasi, karena di dalam tahapan ini dilakukan pengecekan apakah selisih antara nilai Qi dengan Qi-1 sudah tidak lebih dari threshold atau belum. Ketika sudah mencapai batas yang ditentukan maka komputasi akan dihentikan. Fungsi Q sendiri digunakan dengan rumus sebagai berikut | , ∑ ∑ log | , (14) 5.

ALGORITMA MGDM Tahap inisialisasi menjadi sangat penting ketika sebuah mixture model berhadapan dengan data baik kontinyu maupun diskret. Pada umumnya metode yang efektif sebagai algoritma inisialisasi seperti KMeans dan Fuzzy K-Means adalah diperuntukkan untuk data yang sifatnya kontinyu dan tidak bisa diaplikasikan untuk data diskret. Sebagai contoh, algoritma K-Means klasik menggunakan Euclidean Distance yang mana tidak tepat untuk mengcluster data diskret dan memberikan hasil yang kurang baik. Dengan tujuan untuk membuat sebuah estimasi algoritma menjadi sedikit menyentuh lokal optima, digunakan sebuah skema inisialisasi menggunakan algoritma hybrid PSO - Spherical KMeans (PSOSPKMeans) dan method of moment (MM). Untuk mengaplikasikan algoritma ini, digunakan frekuensi vektor yang dihitung untuk tiap-tiap vektor data , 1, … , . Kemudian dilakukan tahap preprosesing yang disebut juga dengan normalisasi skema frekuensi supaya membentuk vektor baru yang ,…, akan digunakan sebagai input untuk algoritma PSOSPKMeans. Normalisasi skema frekuensi dilakukan berdasarkan persamaan (15) berikut ⁄ ∑ (15)

Gambar 2. Algoritma Hybrid PSO Algoritma utuh a. Algoritma Inisialisasi b. E-Step. c. M-Step d. Q-Function e. Lakukan pengecekan terhadap nilai Q, apabila memenuhi threshold, selesai, jika tidak kembali ke step 2.

Detail algoritma multinomial generalized dirichlet mixture adalah sebagai berikut: Algoritma Inisialisasi 1, … , , a. Input data berupa vektor diskret , V, dan total cluster K. b. Menghitung frekuensi vektor , 1, … , ,…, c. Melakukan normalisasi skema frekuensi menggunakan persamaan (15), 1, … , , 1, … , . d. Menerapkan algoritma PSOSPKMeans untuk

Perhitungan akurasi Ada tiga point yang dihitung untuk melakukan uji performa algoritma ini yaitu: a. Misslassified Image Adalah sebuah image yang seharusnya berada pada kelas i, tetapi akhirnya menempati kelas j setelah dilakukan training, dimana b. Precision Adalah proporsi dari suatu set yang diperoleh 100

Seminar Nasional Teknologi Informasi dan Komunikasi 2012 (SENTIKA 2012) Yogyakarta, 10 Maret 2012

ISSN: 2089-9815

Tabel 2. Tabel karakteristik dataset masukan Jumlah Nama Jumlah Jumlah Jumlah data dataset kelas data fitur tiap (dimensi) kelas Dataset1 25 40 256 1000 Dataset2 25 40 256 1000 Dataset3 25 40 256 1000

dari proses retrieve yang relevan dengan data asli. | | | | (17) c. Recall Adalah semua data yang relevan di koleksi termasuk data yang diperoleh. | | | | (18)

Tabel 2 menjelaskan bahwa tiap dataset memiliki 1000 data dengan jumlah kelas yang sama sebanyak 25 kelas, serta tiap-tiap kelas mempunyai 40 variasi data dimana masing-masing data mempunyai dimensi sebesar 256 yang merepresentasikan jumlah frekuensi dari tiap-tiap pixelnya (histogram). Untuk lebih jelasnya mengenai image apa saja yang ada pada tiap-tiap dataset dapat dilihat pada Tabel 3. Tabel 3. Tabel Dataset 1

Dataset1 Nama lukisan kartu

2

celengan

3

buku tebal

korek api

4

tas jinjing

5

koin perak

buah jeruk dompet warna hitam guci dan colokan

Kelas

6 7

6.

UJI COBA Uji coba yang dilakukan diantaranya adalah dengan membuat dataset image sebanyak 3 jenis yang masing-masing berjumlah 1000 data dan 25 kelas. Karakteristik untuk tiap image yang ada pada dataset dituangkan dalam tabel 1.

101

gantungan kunci buku KBBI binder kunci

korek api

kamus jerman - indonesia

9

alat pijat

minyak wangi

10

boneka bebek komporkomporan

HP SE K700i boneka warna merah sendok dan garpu piringpiringan

12

kepingan CD

13

bedak

14

mouse

buah-buahan

15 16

piala topi pramuka saputangan + gelang buku problem solving

flashdisk remote sepatu kecil warna merah

18

pin doraemon

sisir

jam beker

17

Tabel 1. Tabel karakteristik image Property Value Width 600 pixels Height 800 pixels Horizontal Resolution 300 dpi Vertical Resolution 300 dpi Bit Depth 24 Frame Count 1 Color Representation sRGB Ekstensi *.jpg (JPEG Image)

Dataset3 Nama pensil warna

stempel

8

11

Gambar 3. Algoritma PSOSPKMeans

tempat kacamata dompet warna merah jambu

Dataset2 Nama panci kecil senter warna biru

recorder

19

telur

20

alat cukur

21

mainan piano

rantang plastik warna orange sarung tangan motor cobek

22

meteran

celengan

23

cetakan roti

buah tomat

cetakan roti warna kuning bedak putih kaca biru kalkulator buah tomat telepon warna biru sandal sehat blender radio lampu senter bohlam sepatu kecil warna kuning ulek-ulek keping CD driver kotak pensil warna

Seminar Nasional Teknologi Informasi dan Komunikasi 2012 (SENTIKA 2012) Yogyakarta, 10 Maret 2012

24 25

HP Nokia 2100 kipas kayu

gelas warna putih pin doraemon

ISSN: 2089-9815

Nilai parameter tersebut dipilih berdasarkan penelitian seleksi parameter PSO yang dilakukan oleh Shi dan Eberhart [4]. Tabel 5 di bawah ini menjelaskan bahwa terdapat pengaruh antara jumlah data yang digunakan dalam proses training terhadap nilai akurasi missclassified image dan pengaruh itu dibuktikan secara kuat bahwa dalam jumlah iterasi yang berbeda-beda dihasilkan kecenderungan perubahan rata-rata nilai missclassified image yang sama pada tiap dataset.

panci kecil sepatu coklat

Skenario Uji coba dilakukan terhadap masingmasing dataset dengan rincian sebagai berikut: a. Uji coba dengan jumlah data training sebesar 500 dan data testing 500 b. Uji coba dengan jumlah data training sebesar 625 dan data testing 325 c. Uji coba dengan jumlah data training sebesar 750 dan data testing 250 d. Uji coba dengan jumlah data training sebesar 875 dan data testing 125.

Tabel 5. Rata-rata Uji Coba dari tiap iterasi, dataset, dan jumlah data training Rata-rata Uji Coba dari tiap iterasi, dataset, dan jumlah data training

Masing-masing skenario dilakukan dengan iterasi 5, 10, dan 15. Kemudian untuk masingmasing skenario juga dilakukan perhitungan terhadap nilai missclassified image, precision, recall dan running time. Pemilihan skenario di atas dimaksudkan untuk mengetahui pengaruh jumlah data tersebut terhadap akurasi yang diperoleh. Perbedaan jumlah iterasi dimaksudkan untuk mengetahui tingkat kestabilan nilai akurasi dari tiap dataset. Parameter masukan pada proses PSOSPKMeans dituangkan pada tabel 4.

Iter asi

dat ase t

1

5

2

3

 

 

 

 

 

 

 

 

1

10

2

3

 

 

 

  1

 

 

 

 

 

 

 

 

15

2

3

Gambar 4. Image yang mewakili setiap kelas yang ada pada salah satu dataset. 7.

nTrai ning 500 625 750 875 500 625 750 875 500 625 750 875 500 625 750 875 500 625 750 875 500 625 750 875 500 625 750 875 500 625 750 875 500 625 750 875

Traini ng Accur acy (%) 80 81 78 79 61 63 61 60 80 82 80 79 80 79 79 79 62 61 60 61 79 79 80 80 80 79 79 79 62 62 61 60 80 79 80 79

Precis ion

Recall

0.80 0.79 0.78 0.82 0.59 0.59 0.59 0.60 0.81 0.81 0.81 0.81 0.77 0.78 0.77 0.79 0.60 0.61 0.60 0.61 0.80 0.80 0.81 0.80 0.80 0.78 0.80 0.80 0.60 0.61 0.59 0.60 0.80 0.80 0.81 0.81

0.79 0.77 0.76 0.74 0.54 0.58 0.57 0.56 0.76 0.77 0.77 0.77 0.76 0.77 0.76 0.77 0.56 0.58 0.57 0.58 0.76 0.77 0.77 0.77 0.77 0.76 0.78 0.76 0.56 0.58 0.57 0.57 0.77 0.77 0.77 0.77

Running Time (second) 188.33 205.74 278.83 298.44 166.45 224.89 331.49 361.76 162.15 243.06 375.15 433.94 173.15 203.45 286.09 281.27 140.14 213.14 255.19 414.67 156.23 225.22 302.69 411.52 161.17 216.74 275.00 356.01 143.15 211.66 284.09 318.03 158.42 200.84 346.66 402.79

KESIMPULAN Kesimpulan yang diperoleh berdasarkan uji coba dan evaluasi terhadap algoritma Multinomial Generalized Dirichlet Mixture (MGDM) yang telah dilakukan adalah sebagai berikut: a. MGDM terbukti mampu menjadi classifier, dan mampu untuk mengklaster sampel baru suatu dataset. b. Semakin besar jumlah data yang digunakan

Tabel 4. Tabel parameter masukan PSOSPKMeans Parameter Nilai nPartikel 20 nKelas 25 Inertia 0.72 c1 1.49 c2 1.49 102

Seminar Nasional Teknologi Informasi dan Komunikasi 2012 (SENTIKA 2012) Yogyakarta, 10 Maret 2012

dalam proses training menggunakan algoritma MGDM cenderung menyebabkan menurunnya nilai akurasi dari tiap-tiap dataset. c. Penurunan nilai akurasi algoritma MGDM cenderung menyebabkan naiknya presisi pada tahap testing.

PUSTAKA A.

Yudi. (2007). K-Means – Penerapan, Permasalahan dan Metode Terkait. Jurnal Sistem dan Informatika. Cui, X., & Potok, T. E. (2005). Document Clustering Analysis Based on Hybrid PSO+Kmeans Algorithm. I.S. Dhillon, D.S. Modha, Concept decompositions for large sparse text data using clustering. Jeff A, Bimes. (1998). A Gentle Tutorial of EM Algorithm and its Application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models. Berkeley CA, 94704.  N. Bouguila, W. ElGuebaly. (2008). Discrete data clustering using finite mixture models. S. Zhong (2005). Efficient Online Spherical KMeans Clustering. Department of Computer Science and Engineering, Florida Atlantic University, Boca Raton, FL 33431. Shi, Y. H., Eberhart, R. C., (1998). Parameter Selection in Particle Swarm Optimization, The 7th Annual Conference on Evolutionary Programming, San Diego, CA.

103

ISSN: 2089-9815