ISBN : 978-602-50006-0-7
Pembentukan Prototype Data Dengan Metode K-Means Untuk Klasifikasi dalam Metode KNearest Neighbor (K-NN) Khairul Umam Syaliman Magister Teknik Informatika Fasilkom - TI USU
[email protected]
Adli Abdillah Nababan Magister Teknik Informatika Fasilkom - TI USU
[email protected]
Nadia Widari Nasution Magister Teknik Informatika Fasilkom - TI USU
[email protected]
Abstrak Metode K-Nearest Neighbor (K-NN) adalah metode klasifikasi yang sederhana. K-NN menentukan kelas suatu data berdasarkan mayoritas label dari K tetangga terdekat untuk mengklasifikasikan data tersebut. Permasalahan yang sering terjadi dalam metode ini adalah menentukan nilai K yang paling baik untuk digunakan dalam klasifikasi. Selain nilai K, model jarak yang digunakan untuk menghitung kedekatan data juga menjadi hal yang penting untuk diperhatikan. Karena termasuk dalam lazy learner, dalam mengklasifikasikan data yang baru K-NN akan menghitung kemiripan data baru keseluruh basis pengetahuna yang mengakibatkan proses klasifikasi menjadi lama. Untuk mengatasi permasalah tersebut, dalam penelitian ini penulis menciptakan prototype data dari setiap class data dengan menggunakan algoritma K-Means. Model jarak yang digunakan adalah Euclidean dengan nilai lamda 3. Penelitian ini berfokus pada pembentukan prototype data berdasarkan banyaknya data yang dapat diklasifikasikan. Kata kunci : klasifikasi, K-Means, K-Nearest Neighbor, prototype data, Euclidean
I. LATAR BELAKANG K-Nearest Neighbor adalah metode untuk melakukan klasifikasi objek berdasarkan data pembelajaran yang terletak paling dekat dengan objek[1]. K-NN diperkenalkan pertama kali pada awal tahun 1950-an[2].
Meski K-NN tergolong metode yang sederhana dan mudah, K-NN tetap termasuk salah satu dalam top 10 algorithm[3]. Meskipun begitu K-NN juga memiliki masalah yang menarik untuk didiskusikan, antara lain adalah pemilihan K yang paling sesuai untuk mengklassifikasikan suatu data. Hal ini dikarenakan metode ini hanya
173
ISBN : 978-602-50006-0-7
mengandalkan label mayoritas dari K tetangga terdekat. Dalam mencari tetangga terdekat K-NN menggunakan model jarak, ada beberapa model jarak yang sering digunakan, antara lain manhattan, euclidean, dan lain-lain. Dari beberapa model jarak yang dapat digunakan, model jarak euclidean menjadi model jarak yang paling sering digunakan, karena model jarak euclidean cocok untuk menentukan jarak terdekat (lurus) antara dua data[1]. Dalam penelitian kali ini akan dilakukan perhitungan dengan model jarak Euclidean. Selain model jarak, pemilihan jumlah K juga menjadi permasalahan dalam algoritma ini. Maka dari itu, untuk mempermudah dan memfokuskan tujuan penelitian ini jumlah K yang akan digunakan untuk melakukan pengujian dimulai dari K=1 sampai K=10. Pemilihan nilai K yang besar dapat mengakibatkan distorsi data yang besar pula, hal ini disebabkan karena setiap tetangga memiliki bobot yang sama terhadap data uji, sedangkan nilai K yang terlalu kecil bisa menyebabkan algoritma terlalu sensitive terhadap noise. Karena termasuk kedalam Algoritma lazy learner, K-NN dalam pengklasifikasiannya akan menghitung jarak data baru ke seluruh data latih, yang mengakibatkan proses klasifikasi menjadi relative lebih lama. Mengatasi kekurangan tersebut penelitian kali ini mencoba melakukan modifikasi sebelum melakukan klasifikasi dalam metode K-NN dengan menggunakan metode clustering K-Means yang bertujuan untuk menciptakan prototype data yang diharapkan dapat mewakali data dari setiap class data. Dimana gabungan dari dua algoritma ini selanjutnya disebut dengan K-MeansNN.
II. TINJAUAN PUSTAKA a. Klasifikasi Secara harfiah, klasifikasi adalah pembagian sesuatu menurut kelas-kelas. Menurut Sulistyo Basuki, klasifikasi adalah proses pengelompokan/ pengumpulan benda atau entitas yang sama, serta memisahkan benda atas entitas yang tidak sama. Proses klasifikasi menggunakan metode KNearest Neighbor (K-NN) dan K-Means untuk clustering.
b. K-Nearest Neighbor K-Nearest Neighbor (K-NN) merupakan sebuah metode untuk melakukan klasifikasi terhadap objek berdasarkan data pembelajaran yang jaraknya paling dekat dengan objek tersebut. K-NN termasuk algoritma supervised learning dimana hasil dari query instance yang baru diklasifikan berdasarkan mayoritas dari kategori pada K-NN. Kelas yang paling banyak muncul itu yang akan menjadi kelas hasil klasifikasi. Tujuan dari algoritma ini adalah mengklasifikasikan objek baru berdasarkan atribut dan training sample. Algoritma KNearest Neighbor menggunakan klasifikasi ketetanggaan (neighbor) sebagai nilai prediksi dari query instance yang baru. Algoritma ini sederhana, bekerja berdasarkan jarak terpendek dari query instance ke training sample untuk menentukan ketetanggaannya [4]. Langkah-langkah untuk menghitung metode KNearest Neighbor antara lain: 1. Menentukan parameter k 2. Menghitung jarak antara data yang akan dievaluasi dengan semua pelatihan 3. Mengurutkan jarak yang terbentuk 4. Menentukan jarak terdekat sampai urutan k 5. Memasangkan kelas yang bersesuaian 6. Mencari jumlah kelas dari tetangga yang terdekat dan tetapkan kelas tersebut sebagai kelas data yang akan dievaluasi p
∑ (x
di =
2i
− x1i ) 2
i =1
Keterangan: x1 = Sampel data x2 = Data uji atau data testing i = Variabel data d = Jarak p = Dimensi data c. K-Means K-means untuk clustering menggunakan metrik jarak untuk menemukan yang tetangga terdekat dan sebagian besar jarak Euclidean telah digunakan. Fungsi objektif K-Means dapat direpresentasikan sebagai berikut: k
n
J = ∑∑ xij − c j
2
j =1 i =1
174
ISBN : 978-602-50006-0-7
Algoritma K-Means 1. Tetapkan jumlah awal centroid secara acak atau berurutan 2. Hitung jarak antara setiap titik data dan cluster pusat 3. Ulangi: Tetapkan titik data jarak minimum ke cluster pusat yang jaraknya minimum untuk titik itu. 4. Hitung ulang cluster center dengan menggunakan:
ci =
1 mi
∑
mi
x(i); mi mewakili jumlah data
j =1
poin dalam (i) cluster 5. Menghitung ulang jarak antara setiap titik data dan pusat cluster yang baru didapat sampai: Tidak ada titik data yang ditugaskan kembali. d. Model Jarak Model Jarak digunakan untuk menghitung jumlah kemiripan atau kedekatan suatu data. Umam dan Labellapansa melakukan analisis terhadap model jarak Minkowski untuk menentukan jurusan yang tepat pada sekolah tinggi dengan nilai lamda 1, 2 dan 3. Jumlah data yand digunakan adalah 500 data dengan nilai lamda yang paling akurat adalah lamda 1[8]. Ause Labellapansa dkk melakukan penelitian untuk menentukan penyakit Schizophrenia dengan menggunakan model jarak minkowski dengan nilai lamda 1, 2, dan 3. Hasil yang didapati dari penelitian ini adalah saat lamda bernilai 3 hasil prediksi lebih akurat dari lamda yang bernilai 1 dan 2 [9]. Ada banyak model pengukuran jarak, dan yang paling sering digunkan antara lain model jarak Euclidea, Manhattan, Chebyshev, dan Minkowsky[1]. Pengukuran jarak pada ruang jarak Euclidean menggunakan formula : D ,
||
||
|
|
Pengukuran jarak pada ruang jarak Manhattan menggunakan formula : D ,
||
||
|
|
Pengukuran jarak pada ruang jarak Chebyshev menggunakan formula : D ,
||
||
lim →
∑
|
|
Pengukuran jarak pada ruang jarak Minkowsky menggunakan formula : D ,
||
||
|
|
D adalah jarak antara data x dan y, N adalah jumlah fitur (dimensi) data. adalah parameter jarak Minkowsky, secara umum Minkowsky adalah generalisasi dari Euclidean dan Manhattan. merupakan parameter penentu, jika nilai λ = 1 maka ruang jarak Minkowsky sama dengan Manhattan, dan jika λ = 2 ruang jaraknya sama dengan Euclidean[6] dan jika λ= ∞ sama dengan ruang jarak Chebyshev[7]. III.HASIL DAN PEMBAHASAN a. Data Yang Digunakan Dalam penelitian ini menggunakan dua data set yang diunduh dari UCI Repository Data Set. Data yang pertama adalah berupa data iris dan data yang kedua berupa data wine. Setiap data dibagi menjadi dua, yaitu data latih sebesar 80% dan data uji sebesar 20%. Data tersebut akan digunakan untuk menguji gabungan metode K-means dan K-NN. Jumlah masing-masing data subset dapat dilihat pada table dibawah ini : Tabel 1. Jumlah Setiap Data Subset
Data Subset Iris Wine
Latih
Uji
Total
120 142
30 36
150 178
Tabel 2. Detail Sebaran Data Latih Iris Setiap Class
IrisSetosa 40
IrisVersicolor 40
Virginica
Total
40
120
Tabel 3. Detail Sebaran Data Latih Wine Setiap Class
Class 1 42
Class 2 58
Class 3 42
Total 142
175
ISBN : 978-602-50006-0-7
Adapun sebaran data untuk setiap data latih pada setiap data set dapat dilihat pada gambar dibawah ini :
Langkah 2 :
Langkah 3 : Langkah 4 : Langkah 5 : Langkah 6 :
Gambar 1. Sebaran Data Iris
Gambar 2. Sebaran Data Wine
b. Proses K-MeansNN Untuk melihat apakah pembentukan prototype ini berhasil atau tidak, maka akan dilihat berdasarkan perbandingan hasil klasifikasi yang dilakukan algoritma K-NN berdasarkan nilai centroid akhir yang didapati dari algoritma KMeans sebagai prototype data dengan algoritma KNN konvensional. Tahapan proses K-MeansNN dapat dilakukan dengan mengikuti langkah-langkah sebagai berikut. • Pembentukan prototype data : Langkah 1 : Tentukan banyak cluster (K)
Untuk setiap kelompok data (Ci) tentukan titik pusat cluster sebanyak K Hitung jarak antara setiap data ke pusat cluster dengan menggunakan model jarak euclidean Kelompokkan data ke cluster terdekat Hitung pusat cluster baru Lakukan Langkah 3 sampai Langkah 6 hingga konvergen
• Klasifikasi data uji : Langkah 7 : Hitung jarak antara data baru ke setiap pusat cluster pada setiap kelompok data (Ci) menggunakan model jarak Euclidean Langkah 8 : Urutkan data dari pusat cluster berdasarkan jarak terdekat Langkah 9 : Jadikan kelompok mayoritas menjadi kelompok untuk data baru Langkah 10 : Lakukan langkah 7 sampai 9 untuk seluruh data uji Secara sederhana, apabila dibandingkan antara algoritma K-MeansNN dan K-NN konvensional terletak pada pembelajaran dan klasifikasinya. Pada K-NN konvensional, algoritma tersebut tidak melakukan pembelajaran sama sekali. Sedangkan K-MeansNN akan melakukan pembelajaran sehingga membentuk prototype data, dimana prototype data tersebut didapati dari pusat cluster pada setiap kelompok data. Perbedaan dalam melakukan klasifikasinya, KMeansNN hanya akan menghitung jarak sebanyak Ci x K untuk setiap data yang akan diklasifikasi. Sedangkan K-NN akan menghitung keseluruh data latih untuk setiap data baru. Dalam penelitian ini, penulis menggunakan nilai K=1 sampai K=10 dengan model jarak euclidean. Dengan mengikuti langkah-langkah pada bagian III (B), maka perbandingan akurasi pada kedua algoritma dapat dilihat pada tabel dibawah ini : Tabel 4. Perbandingan Akurasi Pada data Uji Iris
Jumlah K 1 2
K-MeansNN
K-NN
96.67%
93.33%
93.33%
93.33%
Algoritma Terbaik KMeansNN KMeansNN,
176
ISBN : 978-602-50006-0-7
3
96.67%
93.33%
4
96.67%
93.33%
5
93.33%
93.33%
6
93.33%
93.33%
7
93.33%
93.33%
8
93.33%
93.33%
9
93.33%
93.33%
10
93.33%
93.33%
Total
943.33%
933.33%
Ratarata
94.33%
93.33%
K-NN KMeansNN KMeansNN KMeansNN, K-NN KMeansNN, K-NN KMeansNN, K-NN KMeansNN, K-NN KMeansNN, K-NN KMeansNN, K-NN KMeansNN KMeansNN
Tabel 5. Perbandingan Akurasi Pada data Uji Wine
Jumlah K 1 2 3
K-MeansNN
K-NN
75.00% 66.67% 77.78%
80.56% 80.56% 72.22%
4 5
69.44% 80.56%
72.22% 72.22%
6
75.00%
69.44%
7
77.78%
69.44%
8
72.22%
69.44%
9
77.78%
69.44%
10
80.56%
72.22%
Total
752.78
727.78
Ratarata
75.28%
72.78%
Algoritma Terbaik K-NN K-NN KMeansNN K-NN KMeansNN KMeansNN KMeansNN KMeansNN KMeansNN KMeansNN KMeansNN KMeansNN
Grafik perbandingan akurasi pada data uji wine dapat dilihat pada gambar berikut :
Grafik perbandingan akurasi pada data uji iris dapat dilihat pada gambar berikut:
Gambar 4. Akurasi K-MeansNN dan K-NN
Gambar 3. Akurasi K-MeansNN dan K-NN
Perbandingan akurasi untuk data uji wine dapat dilihat pada tabel dibawah ini :
IV. KESIMPULAN Berdasarkan hasil penelitian dapat dilihat dari tabel dan gambar grafik akurasi yang telah dipaparkan maka dapat disimpulkan bahwa algoritma K-Means dapat digunakan sebagai suatu cara untuk menciptakan prototype data yang pada akhirnya prototype data tersebut dapat digunakan
177
ISBN : 978-602-50006-0-7
untuk melakukan klasifikasi dalam algoritma KNN. Pengujian dengan menggunakan data subset iris, diperoleh bahwa K-MeansNN berhasil mendapati nilai akurasi lebih tinggi saat nilai K=1 dengan nilai akurasi 96.67%, K=3 dengan nilai akurasi 96.67%, dan K=4 dengan nilai akurasi 96.67%, selebihnya nilai akurasi yang didapati oleh kedua algoritma adalah sama, sebesar 93.33%. Sedangkan pengujian dengan menggunakan data subser wine, diperoleh bahwa K-NN memiliki nilai akurasi yang tinggi saat nilai K=1 dengan nilai akurasi 80.56%, K=2 dengan nilai akurasi 80.56% dan K=4 dengan nilai akurasi 72.22%, selebihnya K-MeansNN mendapati nilai akurasi yang lebih tinggi. DAFTAR PUSTAKA [1]
Prasetyo, Eko. 2012. DATA MINING- Konsep dan Apliksai Menggunakan MATLAB. Andi Offset: Yogyakarta.
[2]
Han, Jiawei ; Kamber, Micheline. 2007. Data Mining: Concepts and Techniques. Elsevier.
[3]
Xindong, Wu., Vipin Kumar. 2009. The Top Ten Algorithms in Data Mining. Taylor & Francis Group. United States of America.
[4]
Rizal Yepriyanto, dkk. Sistem Diagnosa Kesuburan Sperma Dengan Metode K-Nearest Neighbor (K-NN). Jurnal Ilmiah SINUS ISSN : 1693 – 1173
[5]
Zhang, H and Guan, X. 2017. Iris Recognition Based on Grouping KNN and Rectangle Conversion. International Journal of IEEE Xplorer.
[6]
Mergio, J.M., dan Casanovas, M., 2008, The Induced Minkowski Ordered Weighted Averaging Distance Operator, ESTYLF08, Cuencas Mineras (MieresLangreo), Congreso Espanol sobre Tecnologiasy Logica Fuzzy, pp 35-41.
[7]
Rao, M.K., Swamy, K.V., seetha, K.A., dan Mohan, B.C., 2012, Face Recognition Using Different Local Feature with Different Distance Techniques, International Journal of Computer Science, Engineering and Information Technology (IJCSEIT), Vol.2, No.1, pp 67-74, DOI: 10.5121/ijcseit.2012.2107
[8]
Bin Lukman, Khairul Umam Syaliman, and Ause Labellapansa. "Analisa Nilai Lamda Model Jarak Minkowsky Untuk Penentuan Jurusan SMA (Studi Kasus di SMA Negeri 2 Tualang)." Jurnal Teknik Informatika dan Sistem Informasi 1.2 (2015).
[9]
Ause Labellapansa etc., 2016, Lambda Value Analysis on Weighted Minkowski Distance Model in CBR of Schizophrenia Type Diagnosis, Fourth International Conference on Information and Communication Technologies (ICoICT)
178
