Pemahaman k-NN

Zainul Arifin
Nov 1 · 4 min read

1. Apa yang dimaksud k-NN ?

k-NN adalah singkatan dari k-Nearest Neighbour yang merupakan algoritma klasifikasi non-parametik yang tidak menggunakan training data dan tidak menggunakan asumsi atau model awal pada proses perhitungan. Termasuk dalam supervised learning, yang dimana hasil query instance yang baru diklasifikasikan berdasarkan mayoritas kedekatan jarak dari kategori yang ada dalam k-NN.

Kualitas hasil klasifikasi algoritma k-Nearest Neighbor sangat bergantung pada jarak kedekatan antar objek dan nilai dari k yang ditetapkan, maka pemilihan metode untuk perhitungan jarak sangat menentukan hasil pengelompokkan.

2. Tahapan Langkah Algoritma K-NN

Tahapan dalam k-NN meliputi :

  1. Menentukan parameter nilai k (berdasarkan jumlah tetangga paling dekat).
  2. Menghitung kuadrat jarak eucliden objek terhadap data training yang diberikan.
  3. Mengurutkan hasil no 2 secara ascending (pengurutan berdasarkan dari nilai tinggi ke rendah).
  4. Mengumpulkan kategori Y (Klasifikasi nearest neighbor berdasarkan nilai k).
  5. Dengan menggunakan kategori nearest neighbor yang paling mayoritas maka dapat dipredisikan kategori objek.

3. Kelebihan dan Kekurangan dari Algoritma K-NN

Kelebihan :

1. Sangat nonlinear :

k-NN merupakan salah satu algoritma pembelajaran mesin yang bersifat nonparametrik. Model nonparametrik merupakan model yang biasanya lebih sulit diinterpretasikan, tetapi kelebihannya adalah garis keputusan kelas yang dihasilkannya memungkinkan jadi hasil yang sangat fleksibel dan nonlinear.

2. Mudah dipahami dan diimplementasikan :

Untuk mengklasifikasi instance x menggunakan kNN, kita cukup mendefinisikan fungsi untuk menghitung jarak antar-instance, menghitung jarak x dengan semua instance lainnya berdasarkan fungsi tersebut, dan menentukan kelas x sebagai kelas yang paling banyak muncul dalam k instance terdekat.

Kekurangan :

1. Perlu menunjukkan parameter K.

2. Tidak menangani nilai hilang (missing value) secara implisit :

Jika pada suatu perhitungan terdapat missing value pada suatu instance, maka perhitungan jarak instance dengan instance lainnya akan tidak terdefinisi.

3. Sensitif terhadap data outlier :

Diperlukannya pemilihan nilai K yang tepat untuk mengurangi dampak data pencilai (outlier) dalam k-NN.

4. Rentan terhadap variabel yang non-informatif.

k-NN merupakan algoritma yang tidak dapat mengetahui variabel mana yang signifikan pada klasifikasi dan mana yang tidak.

Variabel yang kita tahu noninformatif kita beri bobot yang kecil, misalnya :

4. Algoritma k-NN

  1. Menentukan k bilangan bulat positif berdasarkan data.
  2. Memilih tetangga terdekat dari data baru sebanyak K.
  3. Menentukan klasifikasi yang paling umum pada langkah ke-2 dengan menggunakan frekuensi terbanyak.
  4. Pengeluaran klasifikasi dari data sampel baru.

5. Cara Kerja Algoritma k-NN

Algoritma k-NN melakukan klasifikasi dengan memproyeksikan data pembelajaran pada ruang yang berdimensi banyak. Ruang ini akan dibagi menjadi bagian-bagian yang merepresentasikan kriteria data pembelajaran. k-NN juga mempunyai formula yang digunakan dalam algoritmanya.

1. Euclidean Distance

Euclidean distance adalah metode mengukur jarak yang bersifat ordinary (garis lurus) antar dua titik di euclidean space. Jarak Euclidean antara titik p dan q adalah panjang segmen garis yang menghubungkan antara p ke q. Jarak Euclidean menghitung akar dari kuadrat perbedaan masing-masing dimensi dari dua titik, jika dituliskan sebagai rumus adalah sebagai berikut.

2. Manhattan Distance

Manhattan distance dikenal juga sebagai city block distance, rectilinear distance, atau taxicab metric yang didefinisikan sebagai jumlah dari panjang proyeksi dari segmen garis antar titik-titik ke sumbu koordinat.

Perbedaan Manhattan distance dan Euclidean distance

Jika dianalogikan pada sebuah papan catur, maka jarak antar kotak bidak catur adalah hasil pengukuran dengan metode manhattan distance. Rumus perhitungan Manhattan distance dapat ditulis sebagai berikut.

3. Tchebychev Distance

Tchebychev distance Juga dikenal sebagai Maximum value distance atau Chessboard distance. Ini adalah matriks yang didefinisikan pada ruang vektor dimana jarak antar dua vektor merupakan jarak terbesar (maksimum) dari kedua vektor tersebut. Secara matematis dapat ditulis sebagai berikut.

4. Cosine Distance

Cosine distance adalah metode yang digunakan untuk mengukur jarak similiraty (kedekatan) antar dua objek yang didasarkan pada vector space similarity measure. Metode cosine similarity ini menghitung kesamaan antara dua buah objek (misalkan D1 dan D2) yang dinyatakan dalam dua buah vector dengan menggunakan kata kunci dari sebuah dokumen sebagai ukuran. Adapun rumus menghitung jarak dengan cosine similarity adalah sebagai berikut.

Penulis : Zainul Arifin(4817071342)

Anggota Kelompok :

  1. Alviana Vinda
  2. Farhan Yusuf Jano Putra
  3. Fazel Junio
  4. Ita Tarigan
  5. Muhammad Arijal
  6. Zulian Zamzam
Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade