Mengenal K-Nearest Neighbor: Algoritma Populer untuk Machine Learning

K-nearest neighbor (KNN) merupakan salah satu algoritma yang digunakan dalam machine learning. Jika kamu ingin mempelajari machine learning, kamu perlu memahami bagaimana algoritma ini bekerja, berikut contoh aplikasi dan kelebihan dan kekurangannya.

K-nearest neighbor adalah salah satu algoritma machine learning dengan pendekatan supervised learning yang bekerja dengan mengkelaskan data baru menggunakan kemiripan antara data baru dengan sejumlah data (k) pada lokasi yang terdekat yang telah tersedia. Algoritma ini menerapkan lazy learning” atau “instant based learning” dan merupakan algoritma non parametrik. Algoritma KNN digunakan untuk klasifikasi dan regresi.

Sebelum melanjutkan membaca, artikel ini merupakan bagian dari seri artikel yang menjelaskan tentang Algoritma Machine Learning.

Jika kamu sedang belajar mengenai algoritma machine learning meliputi pengertian, jenis dan macamnya, bagaimana cara kerjanya, silahkan mulai dari artikel ini dan menelusuri tautan-tautan di dalamnya:

Algoritma Machine Learning: Jenis-jenis dan Contoh Algoritmanya.

Apa itu K-Nearest Neighbor?

K-nearest neighbor (KNN) merupakan salah satu algoritma machine learning dengan pendekatan supervised learning yang paling sederhana.

Algoritma ini mengkelaskan data baru menggunakan kemiripan antara data baru dengan sejumlah data (k) pada lokasi yang terdekat yang telah tersedia.

KNN merupakan algoritma non parametrik, yaitu tidak membuat asumsi apapun terhadap data.

Algoritma KNN juga merupakan “lazy learner”, di mana KNN menerapkan “lazy learning” atau “instant based learning”. Artinya, algoritma tidak melakukan proses training dan membangun model. KNN menyimpan set data training dan “belajar” atau melakukan learning darinya hanya pada saat membuat prediksi secra real-time.

Algoritma KNN dapat digunakan untuk kasus klasifikasi (classification) maupun regresi (regression). Meskipun demikian, KNN lebih sering digunakan dalam proses klasifikasi.

Seperti halnya K-means clustering, algoritma KNN merupakan salah satu algoritma machine learning yang paling populer.

Metode KNN banyak dipilih untuk digunakan dalam proses machine learning karena proses dan logika algoritma yang sederhana dan mudah dipahami, data label sebagai input tersedia, dan algoritma ini tidak melakukan pembangunan model.

Contoh aplikasi  K-NEAREST NEIGHBOR

Beberapa contoh dimana algoritma KNN dapat diaplikasikan antara lain:

• Sistem rekomendasi (amazon, Hulu, Netflix, dll) –
• Rasio diabetes
• Peramalan pasar saham: Prediksi harga saham berdasarkan kinerja perusahaan dan data-data ekonomi.
• Klasifikasi citra penginderaan jauh

Cara kerja KNN (step by step)

Metode KNN bekerja dengan berdasarkan langkah-langkah sebagai berikut:

1. Langkah-1: Tentukan jumlah tetangga terdekat (K) yang akan dipertimbangkan sebagai dasar klasifikasi.
2. Langkah-2: Hitung jarak antara data baru terhadap semua titik data dalam dataset.
3. Langkah 3: Urutkan jarak pada langkah 2 dari kecil ke besar, lalu ambil titik data dengan jarak terkecil sejumlah K titik.
4. Langkah-4: Hitung jumlah titik data K pada setiap kelas atau kategori.
5. Langkah-5: Masukkan data baru ke kelas dengan jumlah K terbanyak.

Untuk lebih memudahkan pemahaman, simak visualisasi di bawah ini:

Perhitungan jarak ke tetangga terdekat (langkah 2) dapat dilakukan dengan menggunakan metode:

• Euclidean distance
• Manhattan distance
• Hamming distance
• Minkowski distance

Di antara keempat metode tersebut, euclidean distance merupakan metode yang paling sering digunakan.

K-Nearest Neighbor regression

Proses kerja KNN untuk regresi hampir sama dengan proses kerja KNN untuk klasifikasi.

Perbedaannya terletak pada langkah terakhir.

Pada proses klasifikasi, langkah terakhir adalah menentukan data baru masuk kelas tertentu berdasarkan voting jumlah kelas yang dimiliki oleh K.

Pada KNN untuk regresi, langkah terakhir adalah mengambil semua nilai yang dimiliki tetangga terdekat yang ditentukan (K), lalu menghitung nilai rata-ratanya.

Nilai rata-rata ini kemudian menjadi nilai output untuk data baru yang kita masukkan dalam algoritma KNN.

Secara lengkap, proses kerja algoritma KNN untuk reresi dapat dituliskan sebagai berikut.

1. Langkah-1: Tentukan jumlah tetangga terdekat (K) yang akan dipertimbangkan sebagai dasar klasifikasi.
2. Langkah-2: Hitung jarak antara data baru terhadap semua titik data dalam dataset.
3. Langkah 3: Urutkan jarak pada langkah 2 dari kecil ke besar, lalu ambil titik data dengan jarak terkecil sejumlah K titik.
4. Langkah-4: Hitung rata-rata nilai variabel output dari tiap titik, bisa juga melibatkan pembobotan berdasarkan jarak dalam perhitungan rata-ratanya (Inverse Distance Weighting).
5. Langkah-5: Masukkan nilai rata-rata tersebut sebagai output prediksi.

Untuk lebih memudahkan pemahaman, simak visualisasi di bawah ini:

Cara menentukan nilai K pada algoritma K-NN

Pada metode K Nearest Neighbor, nilai K adalah jumlah tetangga terdekat yang digunakan oleh algoritma dalam proses klasifikasi maupun regresi.

Nilai K ditetapkan dengan nilai ganjil untuk menghindari adanya kesamaan jarak yang dapat muncul pada proses KNN dijalankan.

Berikut ini adalah beberapa pertimbangan yang dapat digunakan untuk menentukan nilai K:

• Tidak ada cara khusus untuk benar-benar menentukan nilai terbaik untuk parameter K pada algoritma K-NN.
• Nilai K yang sangat kecil, misala K=2 atau K=3 akan memberikan hasil yang kurang akurat, terutama jika ada banyak outlier dalam data kita. Selain itu, penggunakan K kecil dapat mengarahkan kita pada model yang overfit.
• Nilai K yang terlalu besar dapat memberikan hasil yang lebih akurat dan batas yang lebih halus. JIka K terlalu besar, kelas dengan jumlah titik data yang kecil akan selalu “kalah jumlah” dalam proses klasifikasi. Selain itu, nilai K yang besar juga akan memakan waktu dan sumberdaya komputasi yang lebih tinggi. 
• Jika bekerja pada dua kelas/ kategori, gunakan nilai K ganjil untuk menghindari jumlah kelas yang sama pada saat perhitungan kelas K.
• Sebagai ancar-ancar atau rule of thumb, nilai K=5 merupakan nilai yang paling sering digunakan.

Kapan menggunaan K-NN algorithm

Kita dapat menggunakan algoritma KNN jika kita dihadapkan pada kasus yang membutuhkan klasifikasi atau regresi dalam pemecahannya.

Itu artinya, kita telah memiliki label atau keterangan pada output di data kita, shingga kita dapat melakukan kleasifikasi atau regresi berdasarkan variabel output tersebut.

Kelebihan K-NEAREST NEIGHBOR

Berikut ini adalah kelebihan atau keunggulan dari algoritma K- Nearest Neighbor:

• Sangat sederhana dan mudah dipahami
• Sangat mudah diterapkan
• Dapat digunakan dalam proses klasifikasi maupun regresi.
• Dapat digunakan dalam jumlah kelas yang berbeda-beda
• Tidak memerlukan proses training dan proses pembangunan model, karena data baru langsung dikelaskan.
• Sangat mudah jika akan dilakukan penambahan data
• Parameter yang diperlukan sedikit, yaitu hanya jumlah tetangga yang dipertimbangkan (K), dan metode perhitungan jaraknya (distance metrik)
• Hasil pemodelan tidak linear, sehingga cocok untuk klasifikasi data yang batasannya tidak linear.

Kelemahan K-NEAREST NEIGHBOR

Sedangkan beberapa kelemahan atau kekurangan dari algoritma k-nearest neighbor antara lain:

• Perlu menentukan nilai K yang tepat.
• Computation cost yang tinggi
• Waktu pemrosesan yang lama jika datasetnya sangat besar.
• Tidak cukup bagus jika diterapkan pada high dimensional data
• Sangat sensitif pada data yang memiliki banyak noise (noisy data), banyak data yang hilang (missing data), dan pencilan (outliers).

Cara melakukan K-NEAREST NEIGHBOR (tutorial)

Salah satu kelebihan K-NN adalah ketersediaannya dalam berbagai software seperti SPSS, Matlab, R dan Python.

Untuk melakukan K-Nearest Neighbor di R, silahkan menggunakan tutorial pada tauatan ini: K-Nearest Neighbor in r.

Sedangkan untuk melakukan K-Nearest Neighbor di Python, silahkan menggunakan tutorial pada tautan ini: K-Nearest Neighbor in python

Kesimpulan

K nearest neighbor merupakan sebuah algoritma machine learning pendekatatan supervised learning sederhana yang dapat digunakan untuk proses klasifikasi maupun regresi.

KNN berjalan dengan menentukan jarak antara data baru terhadap data tersedia, memilih sejumalah K titik terdekat, lalu mengkelaskan data baru sesuai dengan mayoritas kelas yang dimiliki oleh titik K.

Selamat! Kamu telah belajar mengenai Algoritma K Nearest Neighbor.

Artikel ini merupakan bagian dari seri artikel yang menjelaskan tentang Algoritma Machine Learning.

Jika kamu sedang belajar mengenai algoritma machine learning meliputi pengertian, jenis dan macamnya, bagaimana cara kerjanya, silahkan mulai dari artikel ini dan menelusuri tautan-tautan di dalamnya:

Algoritma Machine Learning: Jenis-jenis dan Contoh Algoritmanya.