Algoritma K-Nearest Neighbor (KNN)

Algoritma K-Nearest Neighbor (KNN) adalah sebuah metode untuk melakukan klasifikasi terhadap objek berdasarkan data pembelajaran yang jaraknya paling dekat dengan objek tersebut.Data pembelajaran diproyeksikan k ruang berdimensi banyak, dimana masing – masing dimensi merepresentasikan fitur dari data. Ruang ini dibagi menjadi bagian – bagian berdasarkan klasifikasi data pembelajaran. Sebuah titik pada ruangan ini ditandai dengan kelas c, jika kelas c merupakan klasifikasi yang paling banyak ditemui pada k buah tetangga terdekat titik tersebut.

K-Nearest Neighbor merupakan metode yang bersifat supervised, dimana hasil dari query instance yang baru diklasifikasikan berdasarkan mayoritas kategori pada KNN.  

Pada fase training, algoritma ini hanya melakukan penyimpanan vektor – vektor fitur dan klasifikasi data training sample. Pada fase klasifikasi, fitur – fitur yang sama dihitung untuk testing data (klasifikasinya belum diketahui). Jarak dari vektor yang baru ini terhadap seluruh vektor training sample dihitung, dan sejumlah k buah yang paling dekat diambil. Titik yang baru klasifikasinya diprediksikan termasuk pada klasifikasi terbanyak dari titik – titik tersebut. 

Ketepatan algoritma KNN oleh ada atau tidak adanya fitur – fitur yang tidak relevan, atau jika bobot fitur tersebut setara dengan relevansinya terhadap klasifikasi. Algoritma K Nearest Neighbor memiliki kelebihan yaitu dapat menghasilkan data yang kuat atau jelas dan efektif jika digunakan pada data yang besar. Dari beberapa kelebihan tersebut,  K-Nearest Neighbor juga memiliki kekurangan yaitu membutuhkan nilai K sebagai parameter, jarak dari data percobaan tidak dapat jelas dengan tipe jarak yang digunakan dan dengan atribut yang digunakan untuk memperoleh hasil yang terbaik, maka harus menggunakan semua atribut atau hanya satu atribut yang telah pasti, dan perhitungan harga sangat tinggi karena percobaan ini membutuhkan perhitungan jarak dari beberapa query untuk semua data percobaan.

Adapun algoritma dari KNN ditunjukan pada flowchart berikut :

Flowchart KNN