Prosiding Prosiding Seminar Nasional Efisiensi Energi Encrgi untuk Peningkatan Peningkatan Daya Saing Industri Manufaklur & Efisiensi Industri Manufaktur & Otomotif Nasional Otomolif Nasional
27 September 2012
IMPLEMENTASI TEKNIK DATA MINING DENGAN ALGORITMA KMEANS DAN FUNGSI KERNEL POLYNOMIAL UNTUK KLASTERISASI OBJEK DATA Sudirman1.2, Nur Ani' Ani I Sudirman1,2, IDepartement Information Science, Faculty of Computer Science 1Departemcnt of Information Science and Information University Mercu Mereu Buana, Jakarta, Indonesia Technology, University 2Departement of Information Science, Faculty of Computer Science and Information Infonnation Science,
Technology, MaJaya. Kuala Lumpur, Malaysia Technology. University of Malaya, sdr23Q868@yahoo,coml ,l,
[email protected]' nurani @gmail.com1
[email protected]''2.
Abstrak— Abstrak·· Penelitian ini membahas modiflkasi modifikasi
dala serta memilah-milah memilah-milah data data mengelompollin data mengelompokkan
algoritma K-Means K·Means dalam dnlam klasterisasi suatu sDatu objek data. Tujuan dari modifikasi ini adalah aclalah untuk uDtuk meningkatkan kinerja algoritma aJgoritma tersebut, karena seringkali algoritma K-Means K·Means terjebak dalam lokal lokaJ optima ketika menghadapi data yang tidak tidak linier. Data nata test yang digunakan untuk menguji cfektifitas untnk meDguji e(ektifitas modiflkasi modifikasi algoritma menggunakan menggunakaD set data data Iris. Iris. Modifikasi algoritma dilakukan dengan deDgan menambahkan meoambahkan fungsi kernel kemcl polynomial. Fungsi kernel akan alean membawa data dari space space lama ke ke space baru barn sehingga sehingg. dimungkinkan untuk untuk dipisah dipisah secara secara linier. Hasil Hasil penelitian penelitian ini ini mengkonflrmasikan mengkonfirmasikan bahwa babwa nilai nilal (1p antara a ntara 0.09 0.09 sampai sampal 11 pada fungsi fungsl kernel polynomial memberikan tingkat memberikan tingkat kernel polynomial missclass missdass terendah lcrtndah sebesar sebesar 2% 2 % pada pada klasterisasi klasterisasi data data Iris. Iris.
ke dalam klaster-klaster k1asler-k1aster yang ada. yang dianalisa kedalam Salah satu metode melode klastering klaslering yang umum digunakan di bidang bidanS data data mining adalah adalah metode K-
Kala KJJJa kunci: kunci " Data nata Mining, Mining, Kernel Kernel Polynomial, Polynomial, Klasterisasi, Klasterisasi, K-Means, K.Means, Set Set Data nata Iris Iris
LL
PENDAHULUAN PENDAIIULUAN
Metode Metode pengelompokkan pengelompokkan data data dalam dalam data data mining di kenal dengan istilah Mastering. kenai deogan klnstering. Klastering merupakan usaha mengelompokkan mengelompokkan data kedalam beberapa klaster k1aster atau kelas berdasarakan tingkat tingkat kemiripannya, semakin semakin mirip nilai dari suatu suatu titik tilik data data maka maka akan akan menempati menempali kelas kelas yang yang sama. kl nslering ini ini menggunakan menggunakan dua dua sarna. Metode Mctode klastering pendekatan berdasarakan herarki herarki dan dan pendekatan utama utama yaitu yaitu berdasarakan partisi. partisi. Metode Metode klastering klastering dengan de ngan pendekatan peodekatan herarki dilakukan dilak ukan dengan membuat membual suatu hirarki, hirarki, biasanya berupa berupa dendrogram dengan dengan menempatkan menempatkan data data yang yang memiliki memiliki tingkat kemiripan kemiripan sama sarna pada pada satu 8atu hirarki hirarki akibatnya akibalnya data data yang memiliki mcmiliki tingkat {ingkal kemiripan rendah hirarki yang yang rcndah akan akan menempati mcnempati hirarki berjauhan. Klaslering dengan dengan pendekatan pende kalan partisi partisi berjauhan. Klastering (partition-based clustering) clustuing) dilakukan dilakukan dengan dcngan
Meansclustering. Meansclusuring. K-Means X·Mums adalah suatu metode
penganalisaan data dala dalam data dala mining dengan melakukan proses pemodelan tanpa lanpa supervisi {unsupervised} dan merupakan salah satu metode (unsupervised) melakukan pengelompokan data dengan dengail yang melakukan
sistem sislem partisi (Agusta, (Agusta. 2007). Metode tersebut lersebut Ice d ilakukan dengan mengelompokkan obyek ke dilakukan dalam k klaster kJasler atau alau kelas. kelas. Untuk Untuk melakukan dalam klastering nilai k hams harns ditentukan ditenlukan terlebih terlebih klaslering ini, nilai usu atau pemakai sudah sOOah dahulu. Biasanya user infonnasi awal tentang tenlang obyek yang memiliki informasi k1aster yang dipelajari. termasuk lermas uk berapa jumlah klaster dipelajari, 2(07). Tujuan dari dari lepat (Santosa, 2007). paling tepat klasterisasi klaslcrisasi data data menjadi kk kelas adalah adalah meminimalisasi variasi variasi di di dalam dalam suatu kelas kelas dan dan meminimalisasi me maksimalkan variasi variasi antar anlar kelas. memaksimalkan Usaha untuk meningkatkan kinerja K-Means dalam mcngklasterkan algoritma K-Means mengklasterkan terus dilakukan. dilakukan. Zhang et, all.(1999) all.( 1999) kumpulan data terus K Harmonic Hal7Mn;c Means Means dalam algoritma KKmengusul K Means untuk unluk mengatasi mengalasi terjadinya lokal lok.al optima kelika inisialisasi inisialisasi pusat pusal klaster. klasler. Penelitian Penelitian tersebut tersebul ketika disempurnakan lagi lagi oleh Zhang et, all.(2009) 811.(2009) disempurnakan Bet: de ngan diusulkannya penggunaan algoritma Bee dengan unluk inisialisasi pusat pusal klaster. klaster. Pada Colony untuk akan digunakan digu nakan fungsi kernel kernel penelilian ini akan penelitian Polynomial untuk unluk menghindar mcnghindar dari dan terjadinya lokal lok81 Polynomial inisialisasi pusat pusal klaster. klasler. Hal H81 tersebut tersebul optima pada inisialisasi space lama dengan memetakan memelakan data dari dari space dilakukan dengan spau yang baru sehingga sehingga data dala bisa biss dipisahkan d ipisahkan ke space ke secara seeara linier. linier.
BB -49 - 49
Prosiding Seminar Nasional i 27 September 2012
Efisiensi Energi untuk Peningkatan Daya Saing Industri Manufaktur &Otomotif Nasional I
dimana parameter tersebut akan berfungsi sebagai banyaknya klaster yang dikehendaki. Data yang ada sebanyak n data atau obyek akan di klaster ke
dalam k klaster tadi sehingga diharapkan menghasilkan similarity intra klaster tinggi namun similarity antar klaster rendah. Untuk mengukur kemiripan bisa dipakai cosinus, kovarian, dan korelasi, sedangkan untuk mengukur ketidakmiripan bisa digunakan jarak (Santosa,
LANDASAN TEORI
II.
Data Mining Secara sederhana data mining adalah ekstraksi informasi atau pola yang penting atau menarik dari data yang ada di basisdata yang besar. Data mining juga dikenal dengan nama KDD (Konowledge Discovery in Database)[2]. Data mining menggunakan pendekatan discovery-based dimana pencocokan pola (patternmatching) dan algoritma-algoritma yang lain II.l
digunakan untuk menentukan relasi-relasi kunci di dalam data yang dieksplorasi. Data mining (penambangan data), sesuai dengan namanya, berkonotasi sebagai pencarian informasi bisnis yang berharga dari basis data yang sangat besar. Dengan tersedianya basis data dalam kualitas dan ukuran yang memadai, teknologi data mining memiliki kemampuan-kemampuan sebagai berikut a.
Mengotomatisasi prediksi trend an sifat-sifat bisnis. Data mining mengotomatisasi proses pencarian informasi di dalam basis data yang besar.
b.
Mengotomatisasi penemuan pola-pola yang tidak
diketahui
sebelumnya.
Tools
data
mining "menyapu" basis data, kemudian mengidentifikasi pola-pola yang sebelumnya tersembunyi dalam satu sapuan. Contoh dari penemuan pola ini adalah analisis pada data penjualan ritel untuk mengidentifikasi produk-produk yang kelihatannya tidak berkaitan, yang seringkali dibeli secara
2007). Ketidakmiripan dapat diterjemahkan dalam konsep jarak, semakin dekat jaraknya berarti
semakin tinggi kemiripannya, dan sebaliknya (Santosa, 2007). Pada penelitian ini akan digunakan konsep perhitungan jarak eucledian. Jarak euclidean (L -norm) jarak dua titik x dan y menuruteuclidean dirumuskan sebagai:
d(x>y) =|x-y||2=r(x-y )2 Algoritma K-Means secara sederhana menurut Han & Kamber (2006) adalah:
1. Definisikan secara random jumlah klaster (k) yang akan digunakan sebagai pusat klaster awal.
2. Untuk semuaobyek data, tempatkan pada klaster yang paling mirip, berdasarkan pada jarak
antara obyek dengan pusat klaster awal. 3. Tentukan nilai mean dari klaster-klaster yang terbentuk, sebagai pusat klaster baru. Proses ini berlangsung iteratif.
4. Lakukan lagi langkah 2 dan 3 sampai fungsi kriteria konvergen. Umumnya, kriteria yang digunakan adalah square-error yang dirumuskan sebagai berikut:
E=I ||(j>-m) 2
bersamaan oleh customer.
II.2
Classification
Classification
adalah
proses
untuk
menemukan model atau fungsi yang menjelaskan atau membedakan konsep atau kelas data, dengan tujuan untuk dapat memperkirakan kelas dari satu objek yang labelnya tidak diketahui [3]. Masukkan data untuk klasifikasi adalah
dimana E adalah sum of square error untuk semua obyek dalam data set, p adalah koordinattiap titik yang mewakili obyek yang ada, dan m adalah mean dari klaster C (p dan m adalah '
/
i
multidimensional). Fungsi kriteria ini mencoba
menghasilkan k klaster yang padat dan terpisah sebaik mungkin. Secara ringkas, metode K-Means dapat dilihat pada Gambar 1.1.
kumpulan record. Setiap record dikenal sebagai instance atau contoh yang ditandai oleh tuple (x,y),
Thtt mini ptitiomng ilpfttiun.
dimana x adalah attribut dan y adalah attribute khusus yang menunjukkan label kelas (disebut juga kategori atau atribut target).
in.
METODOLOGI
Langkah pertama dari algoritma K-Means
adalah dengan menentukan parameter input, k.
ChuKrinfof • miM|Nk bmtdm takmmm Mia* (tlx MM irfwdi duM h nurt*ib)ri"*\)
B -50
Prosiding Seminar Nasional Efisien
27 September 2012
gi untuk Peningkatan Daya Saing IndustriManufaktur & OtomotifNasional '•
—
hasil klaster. Didalam kernel K-Means diharapkan data bisa dipisahkan dengan lebih baik karena data yang overlap atau nonlinier bisa menjadi linier di
ruang dimensi baru. Fungsi kernel yang digunakan adalah fungsi polynomial. Nilai p pada persamaan kernel polynomial berperan sebagai derajat dan akan ditentukan melalui serangkaian ujicoba. Nilai y terbaik akan memberikan tingkat missclass terendah.
K=(x.x'+l)P Kernel
K-Means
adalah
pegembangan
Alur kiustci isasi algoritma K-Means dengan fungsi kernel dapat dilihat pada gambar dibawah.
dari
algoritma K-Means dengan cara memetakan data ke space baru menggunakan metode kernel. Hal tersebut dilakukan untuk meningkatkan akurasi Data set Iris
Pengurutan atribut / varlabel
1 Membentuk Matrik Kernel dengan
Tentukan Jumlah Klaster/Kelas ang dikehendaki
I Inisialisasi Pusat Klaster
i Tempatkan Setiap Objek Data ke Pusat KlasterTerdekat Berdasarkan Jaraknva
Hitung Jarak Rata-Rata Anggota Klaster dengan Pusat Klaster
i Tugaskan Lagi Setiap Obyek ke Pusat Klaster Baru, Sampai Pusat Klaster Tidak Berwhah
Gambar 1. Alur Algoritma Kernel K-Means
B
-51
Prosiding Seminar Nasional I 27 September 2012 Efisiensi Energi untuk Peningkatan Daya Saing Industri Manufaktur &Otomotif Nasional I dimana n dan n masing-masing adalah banyaknya data dalam set A dan B. 4. Centroid linkage
Jarak antara dua klaster didefinisikan sebagai d(A,B) = ()yxs, dimana:
LS=AxAxnx,1 !E=BxBynyl
5. Ward linkage Jarak antara dua klaster didefinisikan sebagai
Untuk menentukan tingkat keberhasilan dalam melakukan proses klastering ada beberapa ukuran yang bisa dipakai. Menurut Santosa (2007), untuk menentukan jarak antara dua klaster A dan B dapat digunakan salah satu dari beberapa ukuran:
d (A,B) = , BAABBAnnsnn+2 dimana adalah jarak antara klaster A dan B
menggunakan centroid linkage. 2Abs
1. Complete linkage clustering (jarak maksimum antara elemen dalam klaster)
Jarak antara dua klaster didefinisikan sebagai:
d(A,B)= max{Sxy} dimana S adalah jarak dua data x dan y VI
masing-masing dari klaster A dan B. 2. Single linkage clustering (jarak minimum antara elemen dari setiap klaster) Jarak antara dua klaster didefinisikan sebagai
d(A,B) = min{Sxy} 3. Average linkage clustering (rata-rata jarak antara elemen dari setiap klaster) Jarak antara dua klaster didefinisikan sebagai
d (A,B) = S S{s,y}
IV.
PEMBAHASAN
Untuk melihat efektifitas algoritma ini dalam melakukan klasterisasi data, akan digunakan data test. Data test yang digunakan adalah data set iris yang bisa diambil dari UCI Machine Learning Repository (ftp://ftp.ics.uci.edu./pub/machinelearning-database/). Jumlah total data iris ini sebanyak 150 data terdiri dari empat fitur, dan tiga kelas. Dalam penelitian ini, 40% data akan digunakan sebagai data training dan sisanya digunakan sebagai data testing. Salah satu parameter yang akan di buat berubah-ubah guna mendapatkan hasil klaster terbaik adalah nilai p pada fungsi kernelnya. Jumlah iterasi ditentukan sebesar 1000 didapatkan hasil sebagai berikut:
Tabel 1. Hasil Missclass Klasterisasi Data Iris Menggunakan Algoritma Kernel K-Means
No
P
Missclass
1
2
14.67%
2
1.9
14.67%
3
1.8
14%
4
1.6
12.67%
5
1.4
12%
6
1.2
11.3%
7
1
11.3%
8
0.8
10%
9
0.6
6%
10
0.4
4%
11
0.2
2.6%
12
0.1
2%
13
0.09
2%
14
0.07
2.6%
15
0.05
2.6%
16
0.03
2.6%
B -52
Prosiding Seminar Nasional
27 September 2012
Efisiensi Energi untuk Peningkatan Daya Saing Industri Manufaktur &Otomotif Nasional
Nilai P terbaik yang mampu memberikan
tingkat missclass terendah bcrada pada kisaran 0.09 sampai 1 dengan prosentase missclass 2%. Nilai missclass sebesar 2% ini menunjukkan algoritma Kernel K-Means kurang tepat dalam menentukan kelas dari 3 titik data dari 150 titik data.
Han, J. dan Kamber, M. (2006), Data mining: Concepts and Techniques (2nded,), Elsevier Inc.
Note: Sudirman, S, Kom, MM, M. Kom
KESIMPULAN
V.
Phd Student, Data Mining, Univ of Malaya /
Hasil komputasi dari Algoritma Kernel KMeans menunjukkan bahwa fungsi Kernel
Bea Siswa Dikti
Polynomial dengan tingkat degree pada kisaran 0.09 sampai 0.1 mampu mengklasterkan data Irish dengan tingkat kesalahan 2%. Dengan demikian dapat disimpulkan bahwa penambahan fungsi kernel polynomial mampu meningkatkan kinerja algoritma K-Means. Untuk penelitian selanjutnya bisa diuji cobakan fungsi-fungsi kernel lainnya sehingga bisa di lihat pengaruhnya terhadap kinerja algoritma K-Means dalam usaha klasterisasi objek
Univ of Mercubuana, Jakarta, Indonesia Staf IT.KBRI-KL,Malayasia Nur Ani, S. KomJvTMSI
Ketua Program Studi Sistem Informasi Universitas Mercu Buana Jakarta
data.
DAFTARPUSTAKA
Zhang C, Ouyang, D., dan Ning, J. (2009), An Artificial Bee Colony Approach for Clustering, Expert Systems with Applications, Vol. 37, hal 4761-4767.
Agusta,
Y.
(2007),
K-means,
Penerapan,
Permasalahan dan Metode Terkait, Jurnal Sistem
dan Informatika, Vol, 3 (Pebruari 2007), 47-60. Santosa,
B. (2007),
Data
Mining
Teknik
Pemanfaatan Data untuk Keperluan Bisnis, Graha Ilmu, Jakarta
Zhang, B., Hsu, M., dan Dayal, U. (1999), KHarmonic Means-A Data Clustering Algorithm,
Technical Report HPL-1999-124, Hewlett-Packard Laboratories
lya, M. (2010), Klastering Menggunakan Modifikasi MeansBerbasis
Varietas Padi Metode K-
OWAfOriented
Weighted
Averaging), Thesis Jurusan Teknik Industri, Institut Teknologi Sepuluh Nopember, Surabaya.
B -53
