K-Nearest Neighbor merupakan salah satu metode yang digunakan dalam klasifikasi. Prinsip kerja KNN adalah dengan mengelompokkan data baru berdasarkan jarak ke beberapa data k tetangga terdekat (neighbor) dalam data pelatihan. Nilai k yang terbaik untuk algoritma ini tergantung pada data, secara umum nilai k yang tinggi akan mengurangi efek noise pada klasifikasi, tetapi membuat batasan antara setiap klasifikasi menjadi lebih kabur. Teknik cross validasi digunakan untuk mencari nilai k yang optimal dalam mencari parameter terbaik dalam sebuah model. Jarak Euclidean menurut McAndrew (2004) digunakan untuk menghitung jarak antara dua vektor yang berfungsi menguji ukuran yang bisa digunakan sebagai interpretasi kedekatan jarak antara dua obyek yang direpresentasikan dalam persamaan.
Klasifikasi dengan K-Nearest Neighbor Classifier
K-Nearest Neighbor adalah supervised learning algorithm dimana sebuah objek diklasifikasikan berdasarkan kelas mayoritas dari k buah tetangga terdekatnya. Klasifikasi memanfaatkan mekanisme voting dari k buah objek terdekat dan bila hasil voting seri, maka label untuk objek akan dipilih secara acak.
K-Nearest Neighbor berdasarkan konsep ‘learning by analogy’. Data learning dideskripsikan dengan atribut numerik n-dimensi. Tiap data learning merepresentasikan sebuah titik dalam ruang n-dimensi. Jika sebuah data query yang labelnya tidak diketahui diinputkan, maka K-Nearest Neighbor akan mencari k buah data learning yang jaraknya paling dekat dengan data query dalam ruang n-dimensi. Jarak antara data query dengan data learning dihitung dengan cara mengukur jarak antara titik yang merepresentasikan data query dengan semua titik yang merepresentasikan data learning dengan rumus Euclidean Distance.
Diberikan 2 buah titik P dan Q dalam sebuah ruang vektor n-dimensi dengan P(p1, p2,…, pn) dan Q(q1, q2,…,qn), maka jarak antara P dan Q dapat diukur dengan menggunakan persamaan Euclidean Distance sebagai berikut:
dimana P dan Q adalah titik pada ruang vektor n dimensi sedangkan pi dan qi adalah besaran skalar untuk dimensi ke i dalam ruang vektor n dimensi.
K buah data learning terdekat akan melakukan voting untuk menentukan label mayoritas. Label data query akan ditentukan berdasarkan label mayoritas dan jika ada lebih dari satu label mayoritas maka label data query dapat dipilih secara acak di antara label-label mayoritas yang ada.
ECatatan 