Algoritma k-nearest
neighbor (k-NN atau KNN) adalah sebuah metode untuk melakukan klasifikasi terhadap objek berdasarkan data pembelajaran yang jaraknya paling
dekat dengan objek tersebut.
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,
algoritma 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 algoritma 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.
Kasus khusus di mana klasifikasi diprediksikan berdasarkan data pembelajaran
yang paling dekat (dengan kata lain, k = 1) disebut
algoritma nearest neighbor.
Ketepatan algoritma k-NN
ini sangat dipengaruhi oleh ada atau tidaknya fitur-fitur yang tidak relevan,
atau jika bobot fitur tersebut tidak setara dengan relevansinya terhadap
klasifikasi. Riset terhadap algoritma ini sebagian besar membahas bagaimana
memilih dan memberi bobot terhadap fitur, agar performa klasifikasi menjadi
lebih baik.
Terdapat beberapa jenis
algoritma pencarian tetangga terdekat, diantaranya:
·
Linear scan
·
Pohon kd
·
Pohon Balltree
·
Pohon metrik
·
Locally-sensitive hashing (LSH)
Algoritma k-NN ini memiliki
konsistensi yang kuat. Ketika jumlah data mendekati tak hingga, algoritma ini
menjamin error rate yang tidak lebih dari dua kali Bayes
error rate (error rate minimum untuk distribusi data
tertentu).
K-Nearest Neighbor (KNN) adalah suatu metode yang
menggunakan algoritma supervised dimana hasil dari query instance yang baru diklasifikan berdasarkan mayoritas dari kategori pada
KNN. Tujuan dari algoritma ini adalah mengklasifikasikan obyek baru bedasarkan
atribut dan training sample. Classifier tidak menggunakan model apapun untuk dicocokkan dan hanya
berdasarkan pada memori. Diberikan titik query, akan ditemukan sejumlah k obyek atau (titik training) yang paling dekat dengan titik query. Klasifikasi menggunakan voting terbanyak diantara klasifikasi dari k obyek.. algoritma KNN
menggunakan klasifikasi ketetanggaan sebagai nilai prediksi dari query instance yang baru.
Algoritma metode KNN sangatlah sederhana, bekerja berdasarkan jarak terpendek dari query instance ke training sample untuk menentukan KNN-nya. Training samplediproyeksikan ke ruang berdimensi banyak, dimana masing-masing dimensi merepresentasikan fitur dari data. Ruang ini dibagi menjadi bagian-bagian berdasarkan klasifikasi training sample. Sebuah titik pada ruang ini ditandai kelac c jika kelas cmerupakan klasifikasi yang paling banyak ditemui pada k buah tetangga terdekat dari titik tersebut. Dekat atau jauhnya tetangga biasanya dihitung berdasarkan Euclidean Distance yang direpresentasikan sebagai berikut :
dimana matriks D(a,b) adalah jarak skalar dari kedua vektor a dan b dari matriks dengan ukuran d dimensi.
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 (yang klasifikasinya tidak diketahui). Jarak dari vektor
baru yang 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.
Sebagai contoh, untuk mengestimasi p(x) dari n training sample dapat memusatkan pada sebuah sel disekitar x dan membiarkannya tumbuh hingga meliputi k samples. Samplestersebut adalah KNN dari x. Jika densitasnya tinggi di dekat x, maka sel akan berukuran relatif kecil yang berarti memiliki
resolusi yang baik. Jika densitas rendah, sel akan tumbuh lebih besar, tetapi
akan berhenti setelah memasuki wilayah yang memiliki densitas tinggi. Pada
Gambar 2.13 dan Gambar 2.14 ditampilkan estimasi densitas satu dimensi dan dua
dimensi dengan KNN .
Gambar 1. Delapan titik dalam satu dimensi dan estimasi densitas KNN
dengan k =3 dan k = 5
Gambar 1. KNN mengestimasi densitas Dua Dimensi dengan k = 5
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 semakin kabur. Nilai k yang bagus dapat dipilih dengan optimasi parameter, misalnya
dengan menggunakan cross-validation. Kasus khusus dimana klasifikasi diprediksikan berdasarkan training data yang paling dekat (dengan kata lain, k = 1) disebut algoritma nearest neighbor.
Ketepatan algoritma KNN sangat dipengaruhi oleh ada
atau tidaknya fitur-fitur yang tidak relevan atau jika bobot fitur tersebut
tidak setara dengan relevansinya terhadap klasifikasi. Riset terhadap algoritma
ini sebagian besar membahas bagaimana memilih dan memberi bobot terhadap fitur
agar performa klasifikasi menjadi lebih baik.
KNN memiliki beberapa kelebihan
yaitu ketangguhan terhadap training data yang memiliki banyak noise dan efektif apabila training data-nya besar. Sedangkan, kelemahan KNN adalah KNN perlu menentukan
nilai dari parameter k (jumlah dari tetangga terdekat), training berdasarkan jarak tidak jelas mengenai jenis jarak apa yang harus
digunakan dan atribut mana yang harus digunakan untuk mendapatkan hasil
terbaik, dan biaya komputasi cukup tinggi karena diperlukan perhitungan jarak
dari tiap query instance pada keseluruhan training sample.
