Pertemuan 8 : ALGORITMA KKN (K-Nearest Neighbor)

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.

 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 euclideanBerikut beberapa formula yang digunakan dalam algoritma knn.

  • Euclidean Distance

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

  • 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.

Contoh soal Perhitungan KNN

Diberikan data Training berua dua atribut Bad dan Good untuk mengklasiikasikan sebuah data apakah tergolong Bad atau Good , berikut ini adalah contoh datanya :

Contoh data training
Contoh data training

Langkah penyelesaian 

Kita tentukan parameter K. Misalnya kita buat jumlah tertangga terdekat K = 3.

 1 kita hitung jarak antara data baru dengan semua data training. Kita menggunakan Euclidean Distance. Kita hitung seperti pada table berikut :

Perhitungan jarak dengan euclidean distance

 2 kita urutkan jarak dari data baru dengan data training dan menentukan tetangga terdekat berdasarkan jarak minimum K.

pengurutan jarak terdekat data baru dengan data training

3 Dari kolom 4 (urutan jarak) kita mengurutkan dari yang terdekat ke terjauh antara jarak data baru dengan data training. ada 2 jarak yang sama (yaitu 4) pada data baris 2 dan baris 6, sehingga memiliki urutan yang sama. Pada kolom 5 (Apakah termasuk 3-NN?) maksudnya adalah K-NN menjadi 3-NN , karena nilai K ditentukan sama dengan 3.

4 tentukan kategori dari tetangga terdekat. Kita perhatikan baris 3, 4, dan 5 pada gambar sebelumnya (diatas). Kategori Ya diambil jika nilai K<=3. Jadi baris 3, 4, dan 5 termasuk kategori Ya dan sisanya Tidak.

penentuan kategori yang termasuk K=3

Kategori ya untuk K-NN pada kolom 6, mencakup baris 3,4, dan 5. Kita berikan kategori berdasarkan tabel awal. baris 3 memiliki kategori Bad, dan 4,5 memiliki kategori Good.

5 Gunakan kategori mayoritas yang sederhana dari tetangga yang terdekat tersebut sebagai nilai prediksi data yang baru.

Data yang kita miliki pada baris 3, 4 dan 5 kita punya 2 kategori Good dan 1 kategori Bad. Dari jumlah mayoritas (Good > Bad) tersebut kita simpulkan bahwa data baru (X=3 dan Y=5) termasuk dalam kategori Good.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout /  Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout /  Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout /  Ubah )

Connecting to %s