Pengertian dan Cara Kerja Algoritma K-Nearest Neighbors (KNN)

67

K-nearest neighbors atau knn adalah algoritma yang berfungsi untuk melakukan klasifikasi suatu data berdasarkan data pembelajaran (train data sets), yang diambil dari k tetangga terdekatnya (nearest neighbors). Dengan k merupakan banyaknya tetangga terdekat.

A. Cara Kerja Algoritma K-Nearest Neighbors (KNN)

K-nearest neighbors melakukan klasifikasi dengan proyeksi data pembelajaran pada ruang berdimensi banyak. Ruang ini dibagi menjadi bagian-bagian yang merepresentasikan kriteria data pembelajaran. Setiap data pembelajaran direpresentasikan menjadi titik-titik c pada ruang dimensi banyak.

Klasifikasi Terdekat (Nearest Neighbor Classification)

Data baru yang diklasifikasi selanjutnya diproyeksikan pada ruang dimensi banyak yang telah memuat titik-titik c data pembelajaran. Proses klasifikasi dilakukan dengan mencari titik c terdekat dari c-baru (nearest neighbor). Teknik pencarian tetangga terdekat yang umum dilakukan dengan menggunakan formula jarak euclidean. Berikut beberapa formula yang digunakan dalam algoritma knn.

  • Euclidean Distance

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

    euclidean

  • Hamming Distance

    Jarak Hamming adalah cara mencari jarak antar 2 titik yang dihitung dengan panjang vektor biner yang dibentuk oleh dua titik tersebut dalam block kode biner.

  • Manhattan Distance

    Manhattan Distance atau Taxicab Geometri adalah formula untuk mencari jarak d antar 2 vektor p,q pada ruang dimensi n.

  • Minkowski Distance

    Minkowski distance adalah formula pengukuran antar 2 titik pada ruang vektor normal yang merupakan hibridisasi yang mengeneralisasi euclidean distance dan mahattan distance.

Teknik pencarian tetangga terdekat disesuaikan dengan dimensi data, proyeksi, dan kemudahan implementasi oleh pengguna.


Banyaknya k Tetangga Terdekat

Untuk menggunakan algoritma k nearest neighbors, perlu ditentukan banyaknya k tetangga terdekat yang digunakan untuk melakukan klasifikasi data baru. Banyaknya k, sebaiknya merupakan angka ganjil, misalnya k = 1, 2, 3, dan seterusnya. Penentuan nilai k dipertimbangkan berdasarkan banyaknya data yang ada dan ukuran dimensi yang dibentuk oleh data. Semakin banyak data yang ada, angka k yang dipilih sebaiknya semakin rendah. Namun, semakin besar ukuran dimensi data, angka k yang dipilih sebaiknya semakin tinggi.


Algoritma K-Nearest Neighbors
  1. Tentukan k bilangan bulat positif berdasarkan ketersediaan data pembelajaran.
  2. Pilih tetangga terdekat dari data baru sebanyak k.
  3. Tentukan klasifikasi paling umum pada langkah (ii), dengan menggunakan frekuensi terbanyak.
  4. Keluaran klasifikasi dari data sampel baru.

B. Contoh Aplikasi K Nearest Neighbors

Contoh berikut diambil dari buku "Data Science Algorithms in a Week" yang ditulis oleh  Dávid Natingga.

Pada contoh ini, dilakukan klasifikasi suhu udara berdasarkan persepsi seseorang yang bernama Marry. Adapun klasifikasi suhu udara terdiri dari 2 persepsi yaitu Panas dan Dingin. Persepsi ini dapat diukur berdasarkan 2 variabel yaitu temperatur dalam derajat celcius dan kecepatan angin dalam km/h. Diperoleh data berikut,

Temperatur Udara (ºC) Kecepatan Angin (km/jam) Klasifikasi atau Persepsi Marry
10 0 Dingin
25 0 Panas
15 5 Dingin
20 3 Panas
18 7 Dingin
20 10 Dingin
22 5 Panas
24 6 Panas

Untuk contoh ini terbentuk ruang dimensi 2, yang berisi 2 kriteria yaitu temperatur udara dan kecepatan angin.

Proyeksi dimensi banyak

Pada proyeksi di atas sumbu vertikal adalah kecepatan angin, sumbu horizontal adalah temperatur suhu, warna biru adalah dingin, dan warna merah adalah panas.

Dari proyeksi di atas, dapat dilakukan klasifikasi data baru. Misalnya, Bagaimana persepsi Marry saat temperatur udara 16°C dan kecepatan angin 3 km/jam.

klasifikasi dengan knn

Proses pencarian tetangga terdekat

Menghitung jarak terdekat antar titik

Dapat diketahui tetangga terdekatnya adalah titik c dingin dengan temperatur 15°C dan kecepatan angin 5 km/jam. Jadi berdasarkan pemilihan k = 1, klasifikasinya adalah dingin.

Dengan melakukan proses di atas terhadap semua titik, diperoleh proyeksi klasifikasi berikut.

proyeksi klasifikasi

Catatan: Untuk pemilihan k lainnya, hasil klasifikasi ditentukan dengan frekuensi terbanyak. Misalnya k = 3, dengan titik terdekat dingin, panas, dingin. Hasil klasifikasi data baru tersebut adalah dingin.

Baca juga tutorial lainnya: Daftar Isi Machine Learning


Sekian artikel Pengertian dan Cara Kerja Algoritma K-Nearest Neighbors (KNN). Nantikan artikel menarik lainnya dan mohon kesediaannya untuk share dan juga menyukai halaman Advernesia. Terima kasih…

67 KOMENTAR

  1. Selamat malem kak. Metode wknn itu kan pengembangan dari metode KNN. Misalnya kita mempunyai nilai 683 dan kita menghilangkan 5 data menggunakan k tetangga terdekat 3, 5, 7, 9, 11 itu alasannya kenapa ya kak? Minta tolong butuh jawaban alasannya kak🙇

    • Hai kak Watsiqatut Dianah
      Saya baru pertama dengan metode WKNN, untuk algoritma KNN penggunaan k-tetangga terdakat dimaksud untuk menyeleksi data yang mempunyai karakteristik yang hampir sama dengan data yang diujikan. Sehingga selanjutnya dapat ditentukan karakteristik data yang diuji berdasarkan frekuensi terbanyak dari data-data yang hampir sama tersebut.

      Semoga bermanfaat 🙂

  2. kak mau tanya lagi gimana caranya menentukan k-tetangga terdekat jika ada data sebanyak 683 dan apakah ada rumusnya untuk menentukan k ? butuh bantuan jawaban

    • Hai kak Watsiqatut Dianah, untuk penentuan k tetangga terdekat dapat menggunakan "algoritma optimasi". Hal ini dilakukan karena setiap data yang diproses oleh KNN mempunyai spesifikasi k optimal yang berbeda-beda.

      Misalnya, Kakak dapat menggunakan k-fold cross validation untuk melihat performa nilai k dalam interval tertentu. Penentuan bisa dilihat dari representasi grafik yang dihasilkan bisa dilihat dari titik minimum error atau pun konvergensi error yang dihasilkan.

      Semoga membantu 🙂

  3. assalamu'alaikum kk mau tanya lagi, bagaimana caranya menghitung nilai KNN jika terdapat 2 nilai kosong pada satu baris/atribut ?

    • Jika data yang diproses merupakan data train dan data nya berjumlah ratusan, secara sederhana ke-dua data dapat dihilangkan. Dengan asumsi, data yang tidak lengkap adalah data yang tidak valid.

      Semoga bermanfaat 🙂

    • assalamu’alaikum kk, sebaiknya gunakan k dalam interval 3-50, lalu lakukan tuning menggunakan k-fold cross validation

      Semoga membantu 🙂

    • saya ambil judul skripsi data mining menggunakan metode kkn tentang nilai hasil belajar santri nah itu bisa gak yah kak?

    • Bisa kak Achmadsainur, tapi menurut saya hasil belajar itu lebih baik dimodelkan dalam bentuk fungsi linier, karena variabelnya jelas dan dapat diukur secara langsung.
      Semoga bermanfaat 🙂

    • untuk alur sistemnya Itu kira" bagusnya gmana ya kak, gw sih pake data santri pesantren nah, untuk bagusnya gmna ya kak? mohon bimbingannya dong kak,

    • Jika kakak menggunakan KNN, secara fundamental ini merupakan algoritma klasifikasi. Sehingga harus ditentukan output data merupakan nilai diskrit yang telah ada pada data, misalnya A, B, C, D, E (Data harus memuat output tersebut). Nah langkah selanjutnya susun data menjadi state space matriks output = kkn(input). Proses pembelajaran akan disesuaikan dengan model KKN yang dibuat sehingga dapat menghasilkan output yang diharapkan.
      Semoga bermanfaat 🙂

  4. Kak saya punya judul..
    Implementasi alghoritma knn pada pengukuran tingkat kemagangan biji kopi arabika.
    Pertanyaanya apa bisa menggunakan metode knn?
    Apa aja aplikasi yang di butuhkan untuk melakukan pengolah datanya?
    Menrut kaka apa tujuan dengan judul di atas?

    • Hai kak Ilzam Munasa, menurut saya kasus kematangan kopi tersebut sangat cocok dengan metode knn.
      Untuk pengolahan datanya mungkin dapat menggunakan image processing(warna, bentuk), atau variabel lain misalnya ukuran buah, umur buah.
      Semoga bermanfaat 🙂

  5. Kak saya mau bertanya, untuk klasifikasi dengan banyak kelas apakah bisa menggunakan knn? contohnya seperti terdapat 5 kelas dan 450 data dan 24 fitur kak. itu cara nya bagaimana ya kak jika terdapat banyak kelas? minta tolong kak bantu jawabannya .

    • Hai, kak karin
      Menurut saya itu bisa dilakukan, knn akan mengolah data dalam ruang R^24. Fitur itu Variabel kan?

    • Jumlah kelas ditentukan oleh data train dibagian outputnya, nanti data train jika divisualisasikan akan kelihatan kelas yang dibentuknya.
      Semoga bermanfaat 🙂

  6. kak mau tanya , kenapa Banyaknya k itu sebaiknya merupakan angka ganjil? tidak menggunakan angka genap ?Minta tolong butuh jawaban alasannya kak🙇

    • Hai Lala,
      Tidak harus ganjil, lebih tepatnya k sebaiknya bernilai 3, 4, 5, dst, angka 2 mempunyai peluang besar mendapatkan frekuensi sama, misal k =2 (misal A,B), knn harus meningkatkan nilai k menjadi k = 3 (misal A,B,A), diperoleh output A,
      Jika set 4, peluang frekuensi sama lebih rendah dari 2, tapi masih cukup tinggi, misal k = 4 {AABB,ABAB,BABA},maka nilai k harus ditingkatkan lagi
      Semoga bermanfaat 🙂

    • "Untuk menghindari frekuensi data kembar, yang secara langsung meningkatkan efisiensi".
      Semoga membantu 🙂

1 2

AYO BERKOMENTAR

Tulis komentar
Masukkan nama Anda