k-Nearest Neighbor

Bismillahirrahmanirrahim.

Setelah sekian lama vakum, saya kembali lagi menulis. Semoga di pertengahan Ramadhan ini, kita semua selalu dinaungi rahmat-Nya. Aamiin.

Kali ini saya akan mencoba menuliskan kembali salah satu algoritma yang saya gunakan dalam pengerjaan skripsi saya, cukup familiar dan saya rasa Anda sudah pernah mendengarnya. Ya, algoritma ini cukup terkenal dalam bidang data mining, yaitu k-Nearest Neigbor.

Sebelumnya, apa sih data mining itu? Data mining adalah kegiatan mengekstraksi atau menambang pengetahuan dari data yang berukuran/berjumlah besar, informasi inilah yang nantinya sangat berguna untuk pengembangan.[1]

K-NN adalah algoritma instance-based learning yang didasarkan pada fungsi jarak untuk beberapa pasang pengamatan, seperti jarak Euclidean dan Manhattan. Dalam paradigma klasifikasi ini, k tetangga terdekat dari sampel tes yang diambil pertama kali. Kesamaan antara sampel uji dan k tetangga terdekat dikumpulkan menurut kelas tetangga, dan pengujian sampel ditugaskan untuk kelas paling mirip. Kasus khusus dimana kelas yang diperkirakan masuk dalam kelas sampel pelatihan terdekat (k = 1) disebut algoritma nearest neighbor.[2]

Ilustrasi k-NN

K-NN dari node i bisa diperoleh dengan menarik sebuah lingkaran dengan berpusat pada node i sampai diperoleh k node lain yang berada dalam lingkaran. Pada gambar di atas, 3-ketetanggaan terdekat dari node A adalah tiga node, yaitu node B, C, dan D. 7-ketetanggaan terdekat dari simpul A diperoleh dengan memperpanjang jari-jari lingkaran sampai diperoleh 7 node yang berada dalam lingkaran, yaitu simpul B, C, D, E, F, G, dan H. Dua node (I dan J) bukan anggota dari 7-ketetanggaan terdekat dari node A, karena berada diluar lingkaran. [3]

Dekat jauhnya tetangga dapat dihitung berdasarkan Euclidean Distance :

dimana matriks D (a,b) adalah jarak skalar dari kedua vektor a dan b dari matriks dengan ukuran d dimensi.

[1] Fadli, Ari Konsep Data Mining. http://ilmukomputer.org/wp-content/uploads/2011/03/Ari_Fadli_Konsep_Data_Mining.pdf

[2] Liu, Tie-Yan. 2011. Learning to Rank for Information Retrieval. Springer.

[3] Abidin, Zainal, dan Agus Zainal Arifin. 2010. Membatasi K-Ketenggaan Simpul Dalam Pembangkitan Random Graph Metode Erdos Royi untuk Meningkatkan Kinerja Komputasi. Jurnal CAUCHY.

Semoga ulasan singkat ini bisa membantu. Saran dan kritik bisa disampaikan pada kolom komentar.
Terima kasih.

Alhamdulillahirabbil'alamin.