1
K-PROTOTYPE UNTUK PENGELOMPOKAN DATA CAMPURAN Rani Nooraeni*, Dr. Jadi Supriadi, DEA, Zulhanif, S.Si,M.Sc Jurusan statistika terapan, Fakultas MIPA UNPAD
[email protected]*
Abstrak.Membagi suatu data set berukuran besar ke dalam cluster yang sehomogen mungkin adalah tujuan dalam metode data mining. Metode cluster hirarki yang standar tidak dapat mengatasi masalah pada efisiensi penghitungannya.K-Means merupakan metode yang dapat diterapkan pada data berukuran besar. Tetapi metode K-Means lebih cocok untuk data bertipe numerik. Metode K-Prototype adalah metode pengclusteran yang berdasarkan pada metode K-Means tetapi dikembangkan dengan menambahkan ukuran jarak kemiripan untuk data tipe kategorikal. Sehingga K-Prototype dapat diterapkan pada data berukuran besar dan data bertipe numerik maupun kategorikal. Metode K-prototype dapat meningkatkan kehomogenan dalam cluster dan ketidakmiripan maksimal antar cluster. Keywords:clustering, K-prototype, data campuran, data besar.
1
Pendahuluan
Clustering merupakan salah satu metode dalam Data Mining. Metode cluster dalam data mining berbeda dengan metode konvensional yang biasa digunakan untuk pengelompokkan. Perbedaannya adalah data mining memiliki dimensi data yang tinggi yaitu bisa terdiri dari puluhan ribu atau jutaan record dengan puluhan ataupun ratusan atribut.Selain itu pada data mining data bisa terdiri dari tipe data campuran seperti data numerik dan kategorikal[1]. Metode cluster standar hierarki dapat menangani data bertipe campuran numerik dan kategorikal tetapi ketika data berukuran besar maka timbul masalah dalam hal efisiensi waktu penghitungan. K-Means dapat diterapkan pada data berukuran besar tetapi efisien untuk data bertipe numerik. Hal ini disebabkan pada K-means optimasi cost function menggunakan jarak euclidean yang mengukur jarak antara data poin dengan rata-rata cluster. Meminimalkan fungsi cost dengan menghitung rata-rata cocok digunakan untuk data numerik. Untuk mengetahui hasil cluster baik atau tidak dapat diukur dengan melihat nilai total cost function, semakin kecil total cost function maka semakin bagus clustering yang dihasilkan.
2
Rumus Matematika
Misalkan = { , , … , } adalah kumpulan n objek dan = [ , , … ,
] dimanam menunjukan atribut dan i menunjukkan kluster ke-i.
2.1
Ukuran Kesamaan (Similarity Measure)
Bentuk umum ukuran kesamaan dinyatakan sebagai berikut , = ∑ ( , )
( 1)
= [ , , … ,
] adalah prototype untuk cluster i. Ukuran kesamaan untuk atribut numerik dikenal dengan jarak euclidean ditunjukkan dalam persamaan (2) berikut ini
, = ∑ −
!
( 2)
adalah nilai pada atribut numeric l, adalah rata-rata atau prototype atribut numeric ke l cluster i. mr adalah jumlah atribut numerik. Sedangkan ukuran kesamaan untuk data kategorikal adalah
$ , = " ∑% # , #
Dimana simple matching similarity measure untuk data kategorikal adalah 0 # = # + # , # = & 1 # ≠ #
( 3)
( 4)
" adalah bobot untuk atribut kategori pada cluster i yang nilainya merupakan nilai standar deviasi untuk atribut numerik pada masing-masing cluster. Ketika # adalah nilai atribut kategorikal , # adalah modus atribut ke l cluster i. mc adalah jumlah atribut kategorikal. [3]He, memodifikasi simple matching similarity measure menjadi persamaan (5) untuk meningkatkan kemiripan objek dalam cluster dengan atribut kategorikal sehingga hasil pengclusteran menjadi lebih baik. # , # = &
1 − ,( # , -) # = # + 1 # ≠ #
,( # , -) adalah nilai penimbang untuk # dimana nilai ,( # , -) adalah
2
( 5)
./ $ |2
0 3 ,( # , -) = |2 |./ $ |4 3
( 6)
0
5 # |6 adalah frekuensi nilai # dalam kluster i, dan |6 | adalah jumlah objek dalam kluster i, dan 5( # |7) adalah frekuensi nilai # pada keseluruhan dataset. Pada paper ini matching similarity measure yang digunakan untuk data kategorikal menggunakan formula He. Berdasarkan persamaan (1)-(5), maka ukuran kesamaan untuk data yang memiliki atribut numerik dan atribut kategorikal adalah[2]
$ , = ∑ # , # − + " ∑%
2.2
1! 2
( 7)
Huang Cost Function
Huang menyatakan persamaan cost function untuk data campuran numerik dan kategorikal adalah
$ $ 6:;< = ∑> = ∑ = ∑ # , # − + " ∑
( 8)
6:;< = 6:;< + 6:;< #
Dimana 6:;< adalah biaya total untuk semua atribut numeric dari object dalam cluster i. 6:;< diminimalkan jika dihitung dengan persamaan (9) berikut ini.
= ∑ = 3
untuk l = 1, …., m
( 9)
Dimana ? = ∑ =-@ @A adalah jumlah object di dalam cluster i. Pada atribut kategorikal misalkan Cl adalah sekumpulan nilai unik yang terdapat dalam atribut kategorikal l dan p(cl∈Cl|i) adalah probabilitas dari kemunculan nilai cl di dalam cluster i. maka 6:;< # dalam persamaan (5) bias ditulis ulang menjadi
$ 6:;< # = " ∑ ? 1 − B(C # ∈ 6 |-)
( 10)
Dimana ? adalah jumlah object di dalam cluster i. Solusi untuk meminimalisasi 6:;< # dijelaskan dengan Lemma 1 berikut. Lemma 1: untuk sebuah cluster khusus l, 6:;< # diminimalisasi jika dan hanya jika B( # ∈ 6 |A) ≥ B(F ∈ 6 |-) untuk # ≠ F untuk semua atribut kategorikal. Akhirnya Cost bias dituliskan ulang dengan
3
6:;< = ∑> (6:;< + 6:;< # ) = ∑> 6:;< + ∑> 6:;< # = 6:;< + 6:;< #
( 11)
Persamaan (10) adalah cost function untuk Clustering dataset dengan atribut bernilai numeric dan kategorikal. Karena 6:;< dan 6:;< # adalah non-negatif, minimalisasi Cost bias dilakukan dengan meminimalkan 6:;< dan 6:;< # , total cost dari atribut numeric dan kategorikal untuk semua cluster.
3
Algoritma K-Prototype
Tahapan algoritma K-Prototypes Sebelum masuk proses algoritma K-Prototypes tentukan jumlah k yang akan dibentuk batasannya minimal 2 dan maksimal √n atau n/2 dimana n adalah jumlah data point atau obyek[4]. Tahap 1: Tentukan K dengan inisial kluster z1, z2, ...,zk secara acak dari n buah titik {x1, x2,...,xn} Tahap 2: Hitung jarak seluruh data point pada dataset terhadap inisial kluster awal, alokasikan data point ke dalam cluster yang memiliki jarak prototype terdekat dengan object yang diukur. Tahap 3:Hitung titik pusat cluster yang baru setelah semua objek dialokasikan. Lalu realokasikan semua datapoint pada dataset terhadap prototype yang baru Tahap 4: jika titik pusat cluster tidak berubah atau sudah konvergen maka proses algoritma berhenti tetapi jika titik pusat masih berubah-ubah secara signifikan maka proses kembali ke tahap 2 dan 3 hingga iterasi maksimum tercapai atau sudah tidak ada perpindahan objek.
4
Simulasi, Hasil dan Kesimpulan
Tujuan dari simulasi ini adalah mencoba menerapkan algoritma K-Prototype pada data campuran numerik dan kategorikal. Data yang digunakan adalah Dataset Podes 2011. Ukuran data yang digunakanpada simulasi ini sebanyak 77.961 objek atau desa dan 37 atribut yang terdiri dari 17 atribut numerik dan 20 atribut kategorikal. Pada tahap preparation diperlakukan terhadap data point numerik normalisasi terlebih dahulu. Jumlah kluster yang akan dibentuk adalah 10 cluster.
4
4.1
Hasil Tabel 4.1.1 Jumlah anggota per cluster Cluster i
Jumlah Anggota
Cluster 1 Cluster 2 Cluster 3 Cluster 4 Cluster 5 Cluster 6 Cluster 7 Cluster 8 Cluster 9 Cluster 10
380 1634 9090 10404 325 61 2383 16261 13596 23827
Secara keseluruhan algoritma K-Prototype memberikan hasil clustering yang lebih baik, dimana tingkat kesamaan ciri-ciri cluster menjadi lebih erat atau mirip. Ciri-ciri setiap cluster sebagai berikut 1) Cluster 1. Dengan total elemen sebanyak 380 desa dengan variabel dominan berturut turut adalah variabel 14,13,12,6, dengan nilai dominan yang muncul adalah 2, 2, 2,1 dengan total kemunculan sebanyak 328,324,315,310. Artinya pada cluster 1 memiliki ciri-ciri tidak ada bank, tidak ada minimarket, tidak ada pasar, jalan dapat dilalui kendaraan beroda empat atau lebih sepanjang tahun. 2) Cluster 5. Dengan total elemen sebanyak 325 desa dengan variabel dominan berturut turut adalah variabel 20,9,4,6, dengan nilai dominan yang muncul adalah 1,1,1,1 dengan total kemunculan sebanyak 322,320,316,311. Artinya pada cluster 5 memiliki ciri-ciri tempat buang air besar adalah jamban sendiri, warnet ada, penerangan jalan ada, jalan dapat dilalui kendaraan roda empat atau lebih sepanjang tahun. 3) Cluster 7. Dengan total elemen sebanyak 2323 desa dengan variabel dominan berturut turut adalah variabel 20,2,4,9, dengan nilai dominan yang muncul adalah 1,3,1,1 dengan total kemunculan sebanyak 2313,2290,2266,2239. Artinya pada cluster 7 memiliki ciri-ciri tempat buang air besar jamban sendiri, letak terhadap hutan berada di luar kawasan hutan, penerangan jalan ada, warnet ada. 4) Cluster 10. Dengan total elemen sebanyak 23.827 desa dengan variabel dominan berturut turut adalah variabel 17,10,3,13, dengan nilai dominan yang muncul adalah 1,2,1,2, dengan total kemunculan sebanyak 23.604, 23.274, 22.842, 22.934. Artinya pada cluster 10 memiliki ciri-ciri sumber penghasilan utama dari pertanian, tidak ada kantor pos, status pemerintahan desa, minimarket tidak ada.
5
Tabel 4.1.2 Perbandingan hasil Clustering menurut jumlah data point dan iterasi Time Max Iterasi Total Cost Computing Jumlah data point Jumlah kluster (second) 10 2.29e+06 1726.9 77.961 100 (30 stop) 20 2.08e+06 5125.1 77.961 100 (60 stop) Dari hasil simulasi semakin banyak jumlah kluster yang dibentuk totalcost semakin kecil dan waktu penghitungan semakin lama.
4.2
Kesimpulan
Berdasarkan hasil simulasi yang telahdilakukan maka dapat diambil kesimpulan bahwa secara umum algoritma K-Prototype dapat mempertahankan efisiensi algoritma Kmeans dalam menangani data berukuran besar tetapi menghilangkan keterbatasan penerapan hanya pada data numerik tetapi dapat juga diterapkan pada kategorikal. Sehingga K-Prototype memberikan hasil clustering yang lebih baik karena dapat memberikan ciri atau karakteristik yang lebih mirip dalam Cluster yang terbentuk.
References [1] Zhexue Huang, "Clustering Large Data Sets with Mixed Numeric and Categorical Values," 1997. [2] Zengyou He, Xaiofei Xu, and Shengchun Deng, "Attribute VAlue Weighting in KModes Clustering," Expert System With Application, pp. 15365-15369, 2011. [3] Amir Ahmad and Lipika Dey, "A k-mean clustering algoritm for mixed numeric and categorical data," DAta & Knowledge Engineering, vol. 63, pp. 503-527, 2007. [4] Hwei-Jen Lin, Fu-Wen Yang, and Yang-Ta Kao, "An Efficient GA-based Clustering Technique," TAmkang Journal of Science and Engineering, pp. 113-122, 2005. [5] Chung Chian Hsu and Yan Ping Huang, "Incremental Clustering of Mixed Data based on Distance Hierarchy," Expert System with Application, pp. 1177-1185, 2008. [6] Duc-Truong Pham, Maria M. Suarez-Alvarez, and Yuriy I. Prostov, "Random search with k-prototypes algorithm for clustering mixed datasets," Proceeding of The Royal Society, 2011. [7] LI Jie, GAO Xinbo, and JIAO Li-Cheng, "A GA-Based Clustering Algorithm for Large Data Sets With Mixed Numeric and Categorical Values," Computational Intelligence and Multimediaa Applications, pp. 102-107, 2003.
6
