K-Nearest Neighbor

 Pengertian K-Nearest Neighbor

    Algoritma ini mengkelaskan data baru menggunakan kemiripan antara data baru dengan sejumlah data (k) pada lokasi yang terdekat yang telah tersedia. KNN merupakan algoritma non parametrik, yaitu tidak membuat asumsi apapun terhadap data.

    Algoritma KNN juga merupakan “lazy learner”, di mana KNN menerapkan “lazy learning” atau “instant based learning”. Artinya, algoritma tidak melakukan proses training dan membangun model. KNN menyimpan set data training dan “belajar” atau melakukan learning darinya hanya pada saat membuat prediksi secra real-time.

    Algoritma KNN dapat digunakan untuk kasus klasifikasi (classification) maupun regresi (regression). Meskipun demikian, KNN lebih sering digunakan dalam proses klasifikasi.

Cara Kerja KNN (step by step)

Metode KNN bekerja dengan berdasarkan langkah-langkah sebagai berikut:

Langkah-1: Tentukan jumlah tetangga terdekat (K) yang akan dipertimbangkan sebagai dasar klasifikasi.

Langkah-2: Hitung jarak antara data baru terhadap semua titik data dalam dataset.

Langkah 3: Urutkan jarak pada langkah 2 dari kecil ke besar, lalu ambil titik data dengan jarak terkecil sejumlah K titik.

Langkah-4: Hitung jumlah titik data K pada setiap kelas atau kategori.

Langkah-5: Masukkan data baru ke kelas dengan jumlah K terbanyak.

Untuk lebih memudahkan pemahaman, simak visualisasi di bawah ini:

Algoritma K-Nearest Neighbor untuk klasifikasi

    Perhitungan jarak ke tetangga terdekat (langkah 2) dapat dilakukan dengan menggunakan metode:

• Euclidean distance adalah formula untuk mencari jarak antara 2 titik dalam ruang dua dimensi.

• Manhattan distance atau Taxicab Geometri adalah formula untuk mencari jarak d antar 2 vektor p,q pada ruang dimensi n.
• Hamming distance adalah cara mencari jarak antar 2 titik yang dihitung dengan panjang vektor biner yang dibentuk oleh dua titik tersebut dalam block kode biner.
• Minkowski distance adalah formula pengukuran antar 2 titik pada ruang vektor normal yang merupakan hibridisasi yang menjeneralisasi euclidean distance dan mahattan distance.

Di antara keempat metode tersebut, euclidean distance merupakan metode yang paling sering digunakan.

Cara Menentukan Nilai K pada Algoritma K-NN

    Pada metode K Nearest Neighbor, nilai K adalah jumlah tetangga terdekat yang digunakan oleh algoritma dalam proses klasifikasi maupun regresi. Nilai K ditetapkan dengan nilai ganjil untuk menghindari adanya kesamaan jarak yang dapat muncul pada proses KNN dijalankan. Berikut ini adalah beberapa pertimbangan yang dapat digunakan untuk menentukan nilai K:

• Tidak ada cara khusus untuk benar-benar menentukan nilai terbaik untuk parameter K pada algoritma K-NN.
• Nilai K yang sangat kecil, misala K=2 atau K=3 akan memberikan hasil yang kurang akurat, terutama jika ada banyak outlier dalam data kita. Selain itu, penggunakan K kecil dapat mengarahkan kita pada model yang overfit.
• Nilai K yang terlalu besar dapat memberikan hasil yang lebih akurat dan batas yang lebih halus. JIka K terlalu besar, kelas dengan jumlah titik data yang kecil akan selalu “kalah jumlah” dalam proses klasifikasi. Selain itu, nilai K yang besar juga akan memakan waktu dan sumberdaya komputasi yang lebih tinggi. 
• Jika bekerja pada dua kelas/ kategori, gunakan nilai K ganjil untuk menghindari jumlah kelas yang sama pada saat perhitungan kelas K.
• Sebagai ancar-ancar atau rule of thumb, nilai K=5 merupakan nilai yang paling sering digunakan.

Kelebihan K-NEAREST NEIGHBOR

Berikut ini adalah kelebihan atau keunggulan dari algoritma K- Nearest Neighbor:

• Sangat sederhana dan mudah dipahami
• Sangat mudah diterapkan
• Dapat digunakan dalam proses klasifikasi maupun regresi.
• Dapat digunakan dalam jumlah kelas yang berbeda-beda
• Tidak memerlukan proses training dan proses pembangunan model, karena data baru langsung dikelaskan.
• Sangat mudah jika akan dilakukan penambahan data
• Parameter yang diperlukan sedikit, yaitu hanya jumlah tetangga yang dipertimbangkan (K), dan metode perhitungan jaraknya (distance metrik)
• Hasil pemodelan tidak linear, sehingga cocok untuk klasifikasi data yang batasannya tidak linear.

Kelemahan K-NEAREST NEIGHBOR

Sedangkan beberapa kelemahan atau kekurangan dari algoritma k-nearest neighbor antara lain:

• Perlu menentukan nilai K yang tepat.
• Computation cost yang tinggi
• Waktu pemrosesan yang lama jika datasetnya sangat besar.
• Tidak cukup bagus jika diterapkan pada high dimensional data
• Sangat sensitif pada data yang memiliki banyak noise (noisy data), banyak data yang hilang (missing data), dan pencilan (outliers).