Cara Kerja Algoritma K-Nearest Neighbor (KNN) untuk Data Mining

Pengertian Algoritma K-Nearest Neighbor (KNN)

Algoritma k-nearest neighbor (k-NN atau KNN) adalah metode yang digunakan untuk melakukan klasifikasi terhadap objek berdasarkan data pembelajaran yang jaraknya paling dekat dengan objek tersebut. K-Nearest Neighbor berdasarkan konsep ‘learning by analogy’.

Data learning dideskripsikan dengan atribut numerik n-dimensi. Tiap data learning merepresentasikan sebuah titik, yang ditandai dengan c, dalam ruang n-dimensi. Jika sebuah data query yang labelnya tidak diketahui diinputkan, maka K-Nearest Neighbor akan mencari k buah data learning yang jaraknya paling dekat dengan data query dalam ruang n-dimensi.

Cara Kerja Algoritma K-Nearest Neighbor (KNN)

Jarak antara data query dengan data learning dihitung dengan cara mengukur jarak antara titik yang merepresentasikan data query dengan semua titik yang merepresentasikan data learning dengan rumus Euclidean Distance.

Pada fase klasifikasi, tweet sama dihitung untuk testing data (klasifikasinya belum diketahui). Jarak dari vektor yang baru ini terhadap seluruh vektor training sample dihitung, dan sejumlah k buah yang paling dekat diambil.

Titik yang baru klasifikasinya diprediksikan termasuk pada klasifikasi terbanyak dari titik – titik tersebut. Nilai k yang terbaik untuk algoritma ini tergantung pada data; secara umumnya, nilai k yang tinggi akan mengurangi efek noise pada klasifikasi, tetapi membuat batasan antara setiap klasifikasi menjadi lebih kabur. Nilai k yang bagus dapat dipilih dengan optimasi parameter, misalnya dengan menggunakan cross-validation.

Langkah-Langkah dalam Metode K-Nearest Neighbor

Langkah-langkah yang dilakukan dalam metode K-Nearest Neighbor adalah sebagai berikut:

1. Menentukan Parameter K (jumlah tetangga terdekat)

2. Menghitung kuadrat jarak euclidean (query instance) masing-masing objek terhadap data sampel.

3. Mengurutkan jarak tersebut ke dalam kelompok yang mempunyai euclid terkecil (secara ascending).

4. Mengumpulkan kategori Y (Klasifikasi Nearest Neighbor) berdasasrkan nilai K. Dengan menggunakan kategori yang paling banyak muncul maka akan menghasilkan kelas pada data baru.

Kelebihan Algoritma K-Nearest Neighbor

1. Simpel

2. Efektif jika data besar

3. Performa cukup baik

4. Tahan terhadap data latih yang noisy

Kelemahan Algoritma K-Nearest Neighbor

1. Waktu komputasi tinggi jika data latih besar. Disebabkan oleh semua data diukur jaraknya untuk setiap data uji.

2. Sangat sensitive dengan ciri yang redundan atau tidak relevan. Ditanggulangi dengan seleksi ciri atau pembobotan ciri.

3. Tidak diketahui perhitungan jarak apa yang paling sesuai untuk dataset tertentu.