BAB II TINJAUAN PUSTAKA 2.1 Tinjauan Empiris Pada penelitian ini, peneliti menggunakan beberapa penelitian yang pernah dilakukan sebelumnya sebagai tinjauan studi. Berikut ialah tinjauan empiris yang digunakan: 1. A Modification on K-Nearest Neighbor Classifier (Parvin 2010) Pada penelitian ini diperkenalkan modifikasi metode KNN yang diberi nama Modified K-Nearest Neighbor. Modifikasi yang dilakukan pada algoritma KNN bertujuan untuk meningkatkan kinerja algoritma KNN salah satunya mengatasi masalah tingkat akurasi yang rendah pada algoritma
KNN.
Modifikasi
algoritma
KNN
dilakukan
dengan
menambahkan proses validasi dataset dan pembobotan dataset untuk menentukan kelas dari sebuah objek baru. Metode ini di evaluasi pada 9 data set yakni Wine, Isodata, Iris, Bupa, Inospehre dan 3 data set Monk’s Problem. Hasil evaluasi yang diperoleh metode MKNN yang diusulkan lebih baik dari algoritma tradisional KNN terutama dari segi ketahanan dan akurasi. Metode MKNN lebih baik untuk data set yang memiliki noise dan juga dalam kasus outlier. 2. Penerapan Algoritma K-Nearest Neighbor untuk Penentuan Resiko Kredit Kepemilikan Kendaraan Bemotor (Leidiyana, 2013). Pada penelitian tersebut dilakukan proses klasifikasi pada data konsumen yang menggunakan jasa keuangan kredit kendaraan bermotor untuk mengevaluasi resiko kredit. Untuk mengukur performa algoritma KNN dalam klasifikasi resiko kredit kepemilikan kendaraan bermotor dilakukan pengujian menggunakan metode cross validation, confusion matrix dan kurva ROC. Hasil pengujian mendapatkan tingkat akurasi sebesar 81,46% dan nilai AUC sebesar 0.98. Hal ini menunjukan bahwa algoritma KNN termasuk dalam kategori yang sangat baik untuk melakukan klasifikasi. 22
23
3. Perbandingan Algortima Backpropagation dan K-Nearest Neighbor (K-NN) untuk Identifikasi Penyakit (Redjeki, 2013) Pada penelitian ini dilakukan perbandingan terhadap dua algoritma klasifikasi yang bersifat supervised learning (pembelajaran terawasi). Objek penelitian yang digunakan adalah 10 jenis penyakit dengan gejala awal demam dan 38 gejala lainnya, sehingga total 39 gejala untuk setiap penyakit. Data penelitian yang digunakan berjumlah 82 data yang dibagi menjadi 2 bagian yaikni 72 data testing dan 10 dataset. Hasil pengujian untuk performa kedua metode mendapatkan tingkat akurasi 90% untuk metode Back Propagation dan 100% untuk metode K-NN.
Hal ini
menunjukan bahwa algoritma K-NN memiliki nilai akurasi yang lebih baik dibandingkan dengan algoritma Back Propagation dalam melakukan identifikasi penyakit. 2.2 Tinjauan Teoritis 2.2.1
Klasifikasi Klasifikasi adalah pekerjaan menilai objek data untuk memasukkannya ke
dalam kelas tertentu dari sejumlah kelas yang tersedia. Dengan proses klasifikasi kita dapat menemukan model (fungsi) yang menjelaskan dan membedakan kelaskelas atau konsep. Dalam klasifikasi ada dua pekerjaan utama yang dilakukan yaitu pembangunan model sebagai prototipe untuk disimpan sebagai memori dan penggunaan model tersebut untuk melakukan klasifikasi pada suatu objek data lain agar diketahui kelas dari data objek tersebut dalam model yang telah disimpan. Klasifikasi bertujuan untuk memprediksikan objek yang tidak memiliki kelas menggunakan model yang telah ditemukan. Model yang digunakan didasarkan pada analisis dari dataset. (Prasetyo: 2012) 2.2.2
Metode Perhitungan Jarak Jarak dalam metode Intansce-Based Classifier adalah fungsi yang
digunakan untuk menentukan seberapa dekat vektor inputan baru y dengan setiap
24
data sampel dan menggunakan kelas data sampel terdekat untuk memprediksi output kelas y. Terdapat banyak fungsi perhitungan jarak yang digunakan untuk memilih data sampel terdekat dengan vaktor inputan baru, diantaranya ialah sebagai berikut: 1. City Blok Dinstance Pada Manhattan atau City Block jarak antara dua titik dihitung dengan menggunakan rumus sebagai berikut: (
)
∑
|
| ........................................................................(2.1)
Dimana n adalah dimensi data. 2. Euclidean Distance Untuk Euclidean distance, jarak antara dua titik dihitung menggunakan rumus sebagai berikut: (
)
√∑
(
) ..................................................................(2.2)
Dimana n adalah dimensi data. 3. Minskowsky Distance Untuk Minkowsky distance space, jarak antara dua titik dihitung menggunakan rumus sebagai berikut: (
)
√∑
|
| ...................................................................(2.3)
Dimana n adalah dimensi data dan Minkowsky. Secara umum
adalah parameter jarak
merupakan parameter karakteristik jarak. Jika
, maka jaraknya sama dengan Manhattan. Jika
, maka ruang
jaraknya sama dengan Euclidean. 4. Tchebychev Distance Tchebychev Distance disebut juga dengan jarak nilai maksimum. Tchebychev Distance adalah peringkat mutlak maksimum.
25
√∑
|
|
|
| ..............(2.4)
5. Cosine Distance Cosine distance memberikan jarak sudut antara cosinus, jarak kosinus ditulis sebagai berikut:
(
∑
)
√∑
√∑
...................................................(2.5)
6. Correlation Distance Korelasi jarak dua variabel acak diperoleh dengan membagi kovarians jarak mereka dengan produk jarak deviasi standar mereka. Perhitungan korelasi jarak dituliskan sebagai berikut: (
)
.................................................................................(2.6)
di mana c adalah koefisien korelasi Pearson. Dari berbagai metode perhitungan jarak diatas, metode perhitungan jarak yang paling sering digunakan adalah euclidean distance. Metode perhitungan jarak diatas bekerja dengan baik untuk mendefinisikan jarak pada data dengan atribut numerik, tetapi memiliki kelemahan yakni tidak tepat diaplikasikan untuk mengukur jarak antar data dengan atribut nominal atau kategorikal. (Wilson : 1997) 2.2.2.1 Value Difference Metric Value Difference Metric (VDM) diperkenalkan oleh Stanfill dan Waltz pada tahun 1986 untuk memberikan fungsi perhitungan jarak yang tepat untuk data dengan atribut kategorikal. VDM mendefinisikan jarak antara dua value x dan y dari atribut sebagai berikut: ∑ Dimana
:
|
| ................................................................(2.7)
26
: Jumlah instance dalam dataset yang memiliki value x untuk atribut a : Jumlah instance dalam dataset yang memiliki value x untuk atribut a dan kelas c : jumlah kelas q
: konstanta, bernilai 1 atau 2
Dengan menggunakan metode perhitungan jarak VDM jarak antara dua value (x,y) dianggap lebih dekat jika memiliki tingkat kesamaan (similarity) klasifikasi yang lebih tinggi. Kelemahan dari metode perhitungan jarak VDM ini ialah jarak antara dua value akan dianggap 0 ketika value yang muncul dalam vektor inputan baru tidak terdapat pada training set. Jika value x tidak pernah muncul dalam atribut, maka nilai
untuk setiap C (kelas) akan 0 dan
juga akan bernilai 0. Fungsi jarak VDM ini tidak tepat digunakan langsung pada data dengan atribut kontinue. Jika metode VDM digunakan langsung pada atribut kontinue, semua value dapat bernilai unik. Nilai dan
dapat bernlai 1 untuk semua value x
dapat bernilai 1 untuk kelas 1 (C=1) dan bernilai 0 untuk kelas lainnya.
Vektor inputan baru cenderung memiliki value yang unik, sehingga perhitungan jarak dapat menghasilkan nilai 0 dan nilai yang dihasilkan menjadi tidak berguna, maka dari itu metode perhitungan jarak ini tidak tepat diaplikasikan untuk mengukur jarak antar data dengan atribut kontinue. (Wilson : 1997) 2.2.2.2 Heterogeneous Value Difference Metric (HVDM) Heterogeneous
Value
Difference
Metric
(HVDM)
ialah
metode
perhitungan jarak yang diusulkan oleh Wilson dan Martinez pada tahun 1997. Metode ini diusulkan untuk menghitung jarak pada data dengan atribut yang heterogen yakni atribut kontinue dan nominal (kategorikal). Metode ini menjawab kelemahan dari metode perhitungan jarak Euclidean Distance yang tidak tepat diaplikasikan untuk data dengan atribut nominal dan menjawab kelemahan metode VDM (Value Difference Metric) yang tidak dapat menangani atribut
27
kontinue ataupun numerik. Metode perhitungan jarak HVDM didefinisikan sebagai berikut: √∑
..................................................................(2.8)
dimana m merupakan jumlah atribut. Fungsi
mengembalikan
jarak antara dua nilai x dan y dan didefinisikan sebagai: {
................(2.9)
Fungsi normalized_diff didefinisikan sebagai: |
dimana
|
....................................................................(2.10)
merupakan standari deviasi dari value numerik untuk atribut a. Terdapat tiga fungsi normalized_vdm yang dapat digunakan dalam metode
perhitungan jarak heterogen. Tiga fungsi tersebut diberi label N1, N2, N3 dan berikut ini ialah definisi dari ketiga fungsi tersebut: ∑
√∑
√
|
| .................................(2.11)
|
∑
| ............................(2.12)
|
| ......................(2.13)
Fungsi N1 merupakan fungsi pada persamaan 7 dengan nilai q=1. Fungsi N2 menggunakan nilai q=2 dan mengkuadratkan hasil perhitungan jarak. Fungsi N3 adalah fungsi yang digunakan dalam Heterogeneous Radial Basis Function Networks dimana HVDM pertama kali diperkenalkan. (Wilson : 1997)
28
Pengujian terhadap ketiga fungsi normalisasi diatas telah dilakukan oleh Wilson dan Martinez untuk mengetahui fungsi normalisasi yang paling baik. Pengujian dilakukan pada 15 basisdata dari database repository Univerity of California dengan mengimplementasikan metode K-Nearest Neighbor dengan K=1 dan ten-fold cross validation. Hasil pengujian menunjukan bahwa fungsi normalisasi N2 mencapai akurasi general yang lebih tinggi dibandingkan dengan fungsi normalisasi N1 maupun N3, maka dari itu fungsi normalisasi N2 akan digunakan sebagai skema normalisasi untuk metode perhitungan jarak HVDM. 2.2.3
K-Nearest Neighbor (KNN) K-Nearest Neighbor (KNN) merupakan salah satu algoritma klasifikasi
yang melakukan klasifikasi berdasarkan kedekatan jarak suatu data dengan data yang lain. Pada algoritma KNN data berdimensi q, jarak dari data tersebut ke data yang lain dapat dihitung. Nilai jarak digunakan sebagai nilai kedekatan atau kemiripan antara data testing dengan dataset. Nilai K pada algoritma KNN merupakan jumlah data yang terdekat dari data testing. Jika K bernilai 1, maka kelas dari suatu data testing adalah kelas dari tetangga yang terdekat. Jika k bernilai 2, akan diambil 2 tetangga terdekat dari dataset. Apabila dalam Ktetangga terdapat dua kelas yang berbeda, maka kelas untuk data traning akan ditentukan berdasarkan jumlah data terbanyak (voting mayoritas). (Prasetyo:2012) KNN merupakan salah satu algoritma yang paling banyak digunakan dalam machine learning. KNN adalah metode pembelajaran yang berbasis pada pada kasus dan tidak diperlukan fase pembelajaran (training). Model yang dikembangkan dalam algoritma KNN adalah sampel pelatihan berkaitan dengan fungsi jarak dan fungsi pilihan kelas berdasarkan kelas tetangga terdekat. Berfungsinya metode tergantung pada pilihan beberapa jumlah parameter seperti parameter K yang mewakili jumlah tetangga yang dipilih untuk menetapkan kelas data baru dan metode perhitungan jarak yang digunakan. (Medjahed : 2013) 2.2.3.1 Algoritma K-Nearest Neighbor (KNN) Klasifikasi menggunakan metode KNN ini secara umum dilakukan dengan algoritma dasar sebagai berikut :
29
Input
Output
:
:
K
: nilai untuk parameter K
D
: dataset yang berjumlah N dengan setiap kelasnya
Y
: data objek baru
c
: kelas dari data objek baru
1.
Hitung jarak data objek baru dengan seluruh dataset
2.
Urutkan data berdasarkan data yang memiliki jarak terkecil.
3.
Tentukan label kelas c berdasarkan kelas mayoritas.
2.2.3.2 Kelebihan dan Kelemahan Algoritma K-Nearest Neighbor (KNN) (Yan : 2013) Algoritma KNN memiliki beberapa kelebihan diantaranya algoritma KNN adalah algoritma klasifikasi yang sederhana, ketahahanan dari gangguan pada dataset, dan efektivitas dalam dataset yang memadai. Namun, algoritma KNN juga memiliki kekurangan diantaranya: 1. Algortima KNN memiliki kompleksitas perhitungan yang tinggi. Untuk mengetahui k-tetangga terdekat dari sebuah data testing, semua kesamaan antara data testing dan dataset harus dihitung. Ketika jumlah dataset kurang algoritma KNN tidak akan berjalan secara optimal, namun ketika dataset berjumlah besar maka algoritma KNN akan membutuhkan lebih banyak waktu untuk menghitung kesamaan. 2. Algoritma KNN memeliki ketergantungan pada dataset. Klasifikasi yang dihasilkan hanya berdasarkan sampel dataset dan tidak menggunakan data tambahan. Hal ini membuat algoritma KNN sangat bergantung pada dataset. 3. Algoritma KNN mengangap semua dataset sama. Pada algoritma KNN tidak ada pembobotan untuk setiap dataset. Seluruh dataset diperlakukan sama, tidak ada perbedaan antar sampel. 4. Algoritma KNN juga memiliki kelemahan dari segi akurasi yang rendah dalam data set multidimensi, parameter K, dan metode perhitungan jarak.
30
2.2.4
Modified K-Nearest Neighbor (KNN) Algoritma Modified K-Nearest Neighbor (MKNN) ialah pengembangan dari
metode KNN yang diusulkan oleh Parvin dkk yang sebagian bertujuan untuk mengatasi masalah tingkat akurasi yang rendah pada algoritma KNN. Pengembangan dilakukan dengan melakukan modifikasi pada algoritma KNN yang bertujuan untuk meningkatkan kinerja algortima KNN. Ide utama dari pengembangan algoritma KNN yang dilakukan adalah untuk menggunakan tetangga yang kuat dalam dataset. Metode MKNN menambahkan proses validasi pada setiap dataset. Selanjutnya proses klasifikasi dijalankan dengan melakukan pembobotan pada dataset dengan menggunakan nilai validasi sebagai faktor perkalian. (Parvin : 2010) 2.2.4.1 Validasi Dataset Dalam algoritma Modified K-Nearest Neighbor setiap dataset akan melalui tahap validasi terlebih dahulu. Validasi setiap titik dihitung sesuai dengan tetangganya dan dilakukan hanya satu kali. Nilai validasi setiap dataset kemudian akan digunakan untuk melakukan pembobotan pada dataset yang akan digunakan untuk menentukan kelas suatu data testing. Untuk memvalidasi sebuah dataset, harus ditentukan terlebih dahulu parameter H yang akan digunakan. Parameter H ini merupakan sebuah nilai yang merepresentasikan jumlah tetangga yang digunakan untuk melakukan proses validasi. Diantara H tetangga terdekat dari dataset x, nilai validasi validity(x) setiap dataset dilakukan dengan menghitung jumlah data yang memiliki label yang sama dengan label x. Berikut ialah rumus untuk menghitung nilai validasi setiap dataset: ∑
(
) ....................................(2.14)
Dimana H adalah jumlah tetangga yang digunakan, yakni bernilai 10% dari jumlah dataset. lbl(x) merupakan label dari dari dataset, dan
label dari
tetangga terdekat dengan i = 1,2,3... H. Fungsi S memperhitungkan kesamaan antara satu dataset dan dataset lainnya. Berikut ialah definisi dari fungsi S:
31
{
...........................................................(2.15)
2.2.4.2 Pembobotan Dataset Pembobotan dataset dalam KNN merupakan salah satu dari variasi metode KNN. Variasi metode KNN ini melakukan penentuan kelas dari data objek baru tidak dengan cara melakukan voting mayoritas kelas pada K tetangga terdekat, melainkan dengan cara melakukan voting berdasarkan bobot pada dataset. Setiap dataset akan diberikan bobot dengan melalukan perhitungan. Misalnya, bobot setiap dataset dihitung menggunakan persamaan: .............................................................................................(2.16) Dimana w merupakan bobot, dan
merupakan jarak euclidean. Bobot ini
kemudian akan dijumlahkan untuk setiap kelas dan kelas dengan bobot tertinggi akan dipilih untuk menentukan kelas dari data objek baru. Dalam metode Modified K-Nearest Neighbor bobot masing-masing tetangga dilakukan dengan perhitungan sebagai berikut: ..............................................................................................(2.17) Dimana
merupakan sebuah konstanta yang disebut sebagai smoothing
regulator. Kemudian nilai yang peroleh dari perhitungan diatas akan dikalikan dengan nilai validasi untuk mendapatkan nilai bobot akhir. Berikut ialah perhitungan bobot akhir: ..................................................................(2.18) Dimana W(i) dan validity(i) merupakan bobot dan nilai validasi dari i tetangga terdekat antara dataset dan data testing. Teknik pembobotan diatas akan memberikan nilai yang tinggi untuk dataset yang memiliki nilai validasi yang besar dan kesamaan yang tinggi dengan data testing. (Parvin : 2010)
32
2.2.4.3 Algoritma Modified K-Nearest Neighbor Berikut ini ialah tahapan proses klasifikasi menggunakan algoritma Modified K-Nearest Neighbor: Input
:
Output 1.
:
K
: nilai untuk parameter K
a
: nilai untuk alfa (smoothing regulator)
D
: dataset yang berjumlah N dengan setiap kelasnya
Y
: data objek baru
c
: kelas dari data objek baru
For i = 1 to training_size a.
Hitung nilai validasi setiap dataset
b.
Hitung jarak antara data objek baru dan dataset
c.
Hitung bobot setiap dataset
2.
Jumlahkan nilai bobot untuk setiap kelas
3.
Label kelas c = kelas data yang memiliki bobot tertinggi.
