Belajar Algoritma K-Nearest Neighbor (Metode KNN)

Algoritma K-Nearest Neighbor adalah salah satu algoritma yang dapat digunakan untuk klasifikasi, K-Nearest Neighbor termasuk algoritma machine learning pada kategori supervised learning. KNN merupakan algoritma machine learning sederhana dan mudah diterapkan yang dapat digunakan untuk menyelesaikan masalah klasifikasi dan regresi.

KNN menggunakan sejumlah parameter yang fleksibel, dan jumlah parameter seringkali bertambah seiring data yang semakin banyak. Algoritma non-parametric secara komputasi lebih lambat, tetapi membuat lebih sedikit asumsi tentang data. Algoritma KNN juga bersifat lazy learning, yang artinya tidak menggunakan titik data training untuk membuat model. Singkatnya pada algoritma KNN tidak ada fase training, kalaupun ada juga sangat minim.

Semua data training digunakan pada tahap testing. Hal ini membuat proses training lebih cepat dan tahap testing lebih lambat. Dalam kasus terburuk, KNN membutuhkan lebih banyak waktu untuk memindai semua titik data. Proses ini juga akan membutuhkan lebih banyak memori untuk menyimpan data training.

K-Nearest Neighbor termasuk salah satu algoritma paling sederhana yang digunakan dalam machine learning untuk regresi dan klasifikasi. KNN mengikuti strategi “bird of a feather” dalam menentukan di mana data baru sebaiknya ditempatkan. Algoritma KNN mengasumsikan bahwa sesuatu yang mirip akan ada dalam jarak yang berdekatan atau bertetangga. Artinya data-data yang cenderung serupa akan dekat satu sama lain. KNN menggunakan semua data yang tersedia dan mengklasifikasikan data atau kasus baru berdasarkan ukuran kesamaan atau fungsi jarak. Data baru kemudian ditugaskan ke kelas tempat sebagian besar data tetangga berada.

Kelebihan

Algoritma K-Nearest Neighbor memiliki beberapa kelebihan, berikut beberapa keuntungan menggunakan Algoritma K-Nearest Neighbor:

  1. Simple dan Intuitive, algoritma KNN adalah algoritma yang mudah untuk dipahami oleh banyak orang serta mudah untuk diimplementasikan. Terbukti dengan banyaknya perusahaan yang mengimplementasikan algoritma ini.
  2. Memory Based Approach, algoritma KNN ini mudah beradaptasi dengan training data yang baru. Ini merupakan keunggulan algoritma knn dengan yang lain karena setiap algoritma pastinya memerlukan training data. Dengan mudahnya algoritma ini beradaptasi, maka akan memudahkan developer untuk mengimplementasikan training data yang baru.
  3. Variety Of Distance Matrics, adanya fleksibilitas dari user untuk menggunakan beberapa metode yang paling cocok untuk aplikasi mereka. Ada beberapa contoh metode yang paling umum digunakan, yaitu euclideanminkowskimanhattan dan masih banyak lagi.

Kekurangan

Selain kelebihan, tentunya ada juga kekurangan dari metode ini, yaitu:

  1. Tidak berfungsi dengan baik pada dataset berukuran besar
    Untuk dataset berukuran besar, cost untuk menghitung jarak antara titik baru dan setiap titik yang ada sangat besar dan cenderung menurunkan kinerja algoritma.

  2. Kurang cocok untuk dimensi tinggi
    Algoritma KNN tidak bekerja dengan baik pada data berdimensi tinggi karena dengan jumlah dimensi yang besar, menjadi sulit bagi algoritma untuk menghitung jarak di setiap dimensi.
  3. Perlu penskalaan fitur
    Kita perlu melakukan penskalaan fitur (standarisasi dan normalisasi) sebelum menerapkan algoritma KNN ke kumpulan data apa pun. Jika kita tidak melakukannya, KNN dapat menghasilkan prediksi yang salah.

  4. Sensitif terhadap noise data, missing values dan outliers
    KNN sensitif terhadap noise dalam dataset. Kita perlu secara manual memasukkan nilai yang hilang dan menghapus outlier. 

Cara Kerja Algoritma K-Nearest Neighbor

KNN bekerja berdasarkan prinsip bahwa setiap titik data yang berdekatan satu sama lain akan berada di kelas yang sama. Dengan kata lain, KNN mengklasifikasikan titik data baru berdasarkan kemiripan antara data testing dengan data yang ada pada data training.

  1. Langkah-1: Tentukan nilai K (Banyaknya tetangga)
  2. Langkah-2: Hitung jarak dari data testing ke setiap data training (untuk menghitung jarak dapat menggunakan salah satu metrik jarak, misalnya Euclidean distance)
  3. Langkah-3: Urutkan data dari jarak terdekat ke terjauh, ambil data sejumlah tetangga K (dari jarak terdekat)
  4. Langkah-4: Di antara tetangga K ini, hitung jumlah titik data di setiap Kelas (Kategori).
  5. Langkah-5: Tetapkan titik data baru ke Kelas (Kategori) yang jumlah tetangganya paling banyak.
  6. Langkah-6: Hasil Kelas (Kategori) dari data training merupakan Kelas (Kategori) dari titik hasil pada langkah-5.

 

Anda dapat melihat contoh aplikasi Algoritma KNN disini Aplikasi Metode K-Nearest Neighbor (KNN)