K-Nearest Neighbor (K-NN) adalah suatu metode yang menggunakan algoritma supervised dimana hasil dari sampel uji yang baru diklasifikasikan berdasarkan mayoritas dari kategori pada K-NN. Tujuan dari algoritma ini adalah mengklasifikasi objek baru berdasakan atribut dan sampel latih. pengklasifikasian tidak menggunakan model apapun untuk dicocokkan dan hanya berdasarkan pada memori. Diberikan titik uji, akan ditemukan sejumlah K objek (titik training) yang paling dekat dengan titik uji. Klasifikasi menggunakan voting terbanyak di antara klasifikasi dari K objek. Algoritma K-NN menggunakan klasifikasi ketetanggaan sebagai nilai prediksi dari sample uji yang baru. Dekat atau jauhnya tetangga biasanya dihitung berdasarkan jarak Eucledian.
Algoritma metode KNN sangatlah sederhana, bekerja dengan berdasarkan pada jarak terpendek dari sample uji ke sample latih untuk menentukan KNN nya. Setelah mengumpulkan KNN, kemudian diambil mayoritas dari KNN untuk dijadikan prediksi dari sample uji.
Data untuk algoritma KNN terdiri dari beberapa atribut multi-variate Xi yang akan digunakan untuk mengklasifikasikan Y. Data dari KNN dapat dalam skala ukuran apapun, dari ordinal ke nominal.
KNN memiliki beberapa kelebihan yaitu bahwa dia tangguh terhadap training data yang noisy dan efektif apabila data latih nya besar. Sedangkan kelemahan dari KNN adalah KNN perlu menentukan nilai dari parameter K (jumlah dari tetangga terdekat), pembelajaran berdasarkan jarak tidak jelas mengenai jenis jarak apa yang harus digunakan dan atribut mana yang harus digunakan untuk mendapatkan hasil yang terbaik, dan biaya komputasi cukup tinggi karena diperlukan perhitungan jarak dari tiap sample uji pada keseluruhan sample latih

Algoritma Nearest Neighbor

Klasifikasi adalah proses untuk menemukan model atau fungsi yang menjelaskan atau membedakan konsep atau kelas data, dengan tujuan untuk dapat mem[erkirakan kelas dari suatu objek yang labelnya belum diketahui. Model itu sendiri dapat berupa aturan “jika-maka”, berupa decision tree, formula matematis atau neural network. Salah satu metode klasifikasi yaitu Nearest Neighbor.
Nearest Neighbor merupakan metode untuk mengklasifikasikan suatu data baru berdasarkan similaritas atau kemiripan dengan labeled data. Similaritas menggunakan metrik jarak dengan satuan Euclidian. Macam-macam algoritma  Nearest Neighbor yaitu:
  1. Algoritma 1-NN
Pengklasifikasian dilakukan terhadap 1 labeled data terdekat. Berikut ini adalah ilustrasi algoritma 1-NN:
Pada ilustrasi diatas, data baru (node warna biru) akan diklasifikasikan ke dalam kelompok hipertensi dan tidak hipertensi. Dari kelima data yang tersebar dalam kelompok hipertensi dan tidak hipertensi, data input (node biru) lebih dekat dengan salah satu pada kelompok hipertensi. Dengan demikian, dapat disimpulkan bahwa data baru tersebut termasuk ke dalam kelompok hipertensi.
Rumus euclide distance yang digunakan dalam metode 1-NN untuk mengambil keputusan dengan menghitung jarak terpendek antara input dengan masing-masing data yang penentuan bobot atau label dilakukan secara acak atau random yaitu:
  1. Algoritma K-NN
Pengklasifikasian dilakukan terhadap k labeled data terdekat. Dimana k>1. Berikut ini adalah ilustrasi algoritma K-NN:
 
Langkah-langkah dalam metode K-NN adalah sebagai berikut:
  1. Tentukan k.
  2. Hitung jarak antara data baru ke setiap labeled data.
  3. Tentukan k labeled data yang mempunyai jarak yang paling minimal.
  4. Klasifikasikan data baru ke dalam labeled data yang mayoritas.
Kelemahan Algoritma k-Nearest Neighbors
Pada algoritma k-NN proses kategorisasi dilakukan dengan menggunakan k-values yang sama pada semua kategori, tanpa memperhitungkan jumlah dokumen latih yang dimiliki oleh tiap-tiap kategori. Sedangkan distribusi dokumen latih dalam training set tidak sama, yaitu terdapat beberapa kategori yang memiliki jumlah dokumen latih yang lebih banyak daripada kategori yang lain.
Ketika k-values yang ditetapkan terlalu kecil, maka akan menghasilkan akurasi yang rendah, karenakan hasil kategori akan lebih terpengaruh dengan noise(Chairina., Rizal., dan Agung. 2008). Sedangkan menurut Baoli., Shiwen., dan Qin (2003) apabila k-values yang ditetapkan terlalu tinggi memang akan mengurangi efek noise tetapi juga membuat akurasi menjadi rendah karena hasil kategori dokumen uji lebih terpengaruh pada kategori yang memiliki jumlah dokumen latih yang lebih besar.
Kelemahan ini dapat diatasi dengan melakukan analisa dari hasil percobaan dengan berbagai variasi k-values (cross-validation). Namun metode ini memiliki running time dan computation cost sangat tinggi.

Algoritma Improved k-Nearest Neighbors  
Algoritma Improved k-Nearest Neighbors melakukan modifikasi dalam penentuan k-values. Dimana penetapan k-values tetap dilakukan, hanya saja tiap-tiap kategori memiliki k-values yang berbeda. Perbedaan k-values yang dimiliki pada tiap-tiap kategori disesuaikan dengan besar-kecilnya jumlah dokumen latih yang dimiliki kategori tersebut. Sehingga ketika k-values semakin tinggi, hasil kategori tidak terpengaruh pada kategori yang memiliki jumlah dokumen latih yang lebih besar.
Perhitungan penetapan k-values pada algoritma Improved k-Nearest Neighborsdilakukan menggunakan persamaan (2.3) dengan terlebih dahulu mengurutkan secara menurun hasil dari persamaan (2.2) pada tiap-tiap kategori.