Klasifikasi Menggunakan K-Nearest Neighbor

Assalamualaikum sobat-sobatku..

Di kesempatan kali ini, aku mau sharing sebuah metode untuk melakukan klasifikasi terhadap objek berdasarkan data pembelajaran yang jaraknya paling dekat dengan objek tersebut. Metode tersebut dikenal dengan nama K-Nearest Neighbor atau biasa disingkat jadi KNN.

source : https://informatikalogi.com/algoritma-k-nn-k-nearest-neighbor/

Data pembelajaran diproyeksikan ke ruang berdimensi banyak, dimana masing-masing dimensi merepresentasikan fitur dari data. Ruang ini dibagi menjadi bagian-bagian berdasarkan klasifikasi data pembelajaran. Sebuah titik pada ruang ini ditandai kelas c jika kelas c merupakan klasifikasi yang paling banyak ditemui pada k buah tetangga terdekat titk tersebut. Dekat atau jauhnya tetangga biasanya dihitung berdasarkan jarak Euclidean.

Pada fase pembelajaran, algoritme ini hanya melakukan penyimpanan vektor-vektor fitur dan klasifikasi dari data pembelajaran. Pada fase klasifikasi, fitur-fitur yang sama dihitung untuk data test (yang klasifikasinya tidak diketahui). Jarak dari vektor yang baru ini terhadap seluruh vektor data pembelajaran dihitung, dan sejumlah k buah yang paling dekat diambil. Titik yang baru klasifikasinya diprediksikan termasuk pada klasifikasi terbanyak dari titik-titik tersebut.

Nilai k yang terbaik untuk algoritme ini tergantung pada data; secara umumnya, nilai k yang tinggi akan mengurangi efek noise pada klasifikasi, tetapi membuat batasan antara setiap klasifikasi menjadi lebih kabur. Nilai k yang bagus dapat dipilih dengan optimasi parameter, misalnya dengan menggunakan cross-validation.

Nah, langsung saja yuk kita eksekusi dengan R hehehehe.. Siapkan dulu library yang akan digunakan yaaa

library(class)
library(dbscan)

Data yang kita gunakan nanti cukup sederhana, misalkan ada 8 orang yang memiliki data mengenai tinggi badan, berat badan dan ukuran baju sebagai berikut.

Nah kita ingin mengetahui size baju yang cocok untuk seseorang bernama Ryan yang memiliki tinggi badan 173 cm dan berat badan 69 kg. Pertama-tama, kita definisikan variabel terlebih dahulu.

tinggi<-c(175, 165, 166, 178,174, 169, 168, 170)
berat<-c(75, 60, 77, 73, 62, 68, 64, 70)
size<-factor(c("L","M", "L","L","M","M","M","L"))
orang<-cbind(tinggi, berat)
rownames(orang)<-c("Richard","Deby","Mike","Tom","Bella","John","Ann","Jack")
orang

Maka akan muncul tampilan berikut

Selanjutnya, kita akan membuat plot untuk data tersebut. Gunakan perintah berikut.

plot(orang, col=ifelse(size=="L","red","blue"),cex=0.3,lwd=0.2, asp=1)
text(orang, labels=row.names(orang),cex=2)

Lalu akan muncul plot seperti ini

Kemudian, kita akan menambahkan data Ryan pada data orang tersebut.

orangbaru<-cbind(173,69)
points(orangbaru,cex=2,lwd=4)
rownames(orangbaru)<-c("Ryan")

Nantinya akan muncul satu titik dalam grafik yang merupakan letak data Ryan

Selanjutnya, kita ingin mencari tau ukuran baju untuk Ryan menggunakan syntax berikut ini.

kl3<-knn(orang,orangbaru,size, k=3,prob=TRUE)
kl3

Kemudian, akan muncul output berikut

Untuk perbandingan kita juga bisa menggunakan nilai k = 5

kl5<-knn(orang,orangbaru,size, k=5,prob=TRUE)
kl5

Maka output nya seperti berikut

Kita bisa melihat perbedaan antara hasil klasifikasi antara k=3 dan k=5. Dimana dengan nilai k=3, ukuran baju Ryan adalah L. Sedangkan untuk k=5, ukuran baju Ryan masuk kategori M. Disarankan menggunakan k yang ganjil agar ada dominasi yang berbeda, karena jika genap hasilnya dapat menjadi 50:50 dan menghasilkan target yang sama sehingga menyebabkan kesulitan dalam mengambil keputusan.

Berikutnya, kita ingin mengetahui persekitaran terdekat dari Ryan. Kita kumpulkan data semua orang terlebih dahulu, lalu kita bisa melihat tetangga terdekatnya.

semuaorang<-rbind(orang,orangbaru)
tetangga<-kNN(semuaorang,k=3)
i<-9
tetangga$id[i,]

Nantinya akan muncul output berikut

Dapat kita lihat, dari output tersebut diketahui bahwa tetangga terdekat Ryan adalah objek ke-8, objek ke-6 dan objek pertama. Lalu, kita akan membuat plot untuk melihat tetangga terdekatnya.

plot(semuaorang, col=ifelse(1:nrow(semuaorang)%in% tetangga$id[i,],"red","black"),cex=2, lwd=2, asp=1)
text(semuaorang,labels = row.names(semuaorang),cex=2)

Maka, akan muncul tampilan berikut

Kita bisa melihat bahwa tetangga terdekatnya memiliki lingkaran berwarna merah, jadi tetangga terdekat Ryan yaitu Jack, John dan Richard.

Kita bisa melihat lebih dekat lagi persekitaran tersebut dengan membuat sebuah lingkaran dengan diameter yaitu jarak terjauh dari tiga tetangga terdekat Ryan.

dist(rbind(semuaorang[9,],semuaorang[1,]),method = "euclidian")
circle<-function(x,y,rad=1,nvert=500, ...){
  rads<-seq(0,2*pi,length.out = nvert)
  xcoords<-cos(rads)*rad +x
  ycoords<-sin(rads)*rad +y
  polygon(xcoords, ycoords, ...)
}
circle(173,69,6.324555)

Nantinya akan muncul lingkaran seperti ini

Didapatkan bahwa dua dari tiga tetangga terdekat Ryan memiliki size baju berukuran L sehingga kita bisa mengatakan ukuran baju yang sesuai untuk Ryan yaitu L. Selanjutnya jika ingin mengetahui k mana yang terbaik, kita bisa menggunakan tabel klasifikasi, tapi kita harus menambahkan ukuran baju Ryan terlebih dahulu.

sizetambahan<-factor(c("L"))
size<-unlist(list(size, sizetambahan))
klasifikasi3<-knn(semuaorang,semuaorang,size,k=3,prob = TRUE)
100*sum(size==klasifikasi3)/100
table(klasifikasi3,size)
klasifikasi5<-knn(semuaorang,semuaorang,size,k=5,prob = TRUE)
100*sum(size==klasifikasi5)/100
table(klasifikasi5,size)

Maka akan ada dua output seperti ini

Dari output tersebut, kita bisa mengetahui jika tabel klasifikasi untuk k=3 memiliki satu misklasifikasi yaitu yang seharusnya berukuran M tetapi malah masuk ukuran L. Sedangkan pada tabel klasifikasi untuk k=5, didapatkan klasifikasi yang telah tepat. Sehingga kita bisa tau bahwa dalam kasus ini k=5 merupakan k terbaik.

Itu tadi langkah-langkah melakukan klasifikasi menggunakan KNN dengan data yang sederhana. Semoga bermanfaat sobat.

Terimakasih ^_^

Wassalamualaikum Wr. Wb.

Referensi :

1. https://id.wikipedia.org/wiki/KNN