Algoritma K-Nearest Neighbors (k-NN): Panduan Lengkap

Algoritma K-Nearest Neighbors (k-NN) adalah salah satu algoritma supervised learning yang paling sederhana dan intuitif dalam dunia machine learning. Algoritma ini digunakan baik untuk masalah klasifikasi maupun regresi. Idenya adalah, sebuah data baru diklasifikasikan atau diprediksi nilainya berdasarkan mayoritas kelas atau rata-rata nilai dari k tetangga terdekatnya dalam dataset pelatihan. k-NN banyak diterapkan dalam berbagai bidang, mulai dari sistem rekomendasi, pengenalan pola, hingga deteksi anomali.

Apa itu Algoritma K-Nearest Neighbors?

Algoritma K-Nearest Neighbors (k-NN) adalah metode supervised learning yang digunakan untuk mengklasifikasikan objek berdasarkan data pembelajaran yang jaraknya paling dekat dengan objek tersebut. “K” dalam k-NN adalah singkatan dari jumlah tetangga terdekat yang digunakan untuk menentukan kelas atau nilai dari data baru. Jadi, “K-Nearest Neighbor” secara harfiah berarti “K Tetangga Terdekat”. Algoritma ini termasuk dalam kategori lazy learner, yang berarti ia tidak membangun model secara eksplisit selama fase pelatihan, melainkan menyimpan seluruh data pelatihan dan melakukan perhitungan hanya saat melakukan prediksi.

Algoritma k-NN dapat digunakan untuk masalah klasifikasi dan regresi. Dalam klasifikasi, data baru diklasifikasikan berdasarkan mayoritas kelas dari k tetangga terdekatnya. Dalam regresi, nilai data baru diprediksi berdasarkan rata-rata (atau median) nilai dari k tetangga terdekatnya. Beberapa contoh penerapan k-NN dalam dunia nyata meliputi sistem rekomendasi produk (misalnya, rekomendasi film di Netflix), deteksi fraud, diagnosis medis, dan klasifikasi gambar.

Konsep Dasar Algoritma k-NN

Cara Kerja Algoritma k-NN

Prinsip dasar algoritma k-NN sangat sederhana. Ketika diberikan data baru yang belum diketahui kelas atau nilainya, algoritma ini akan melakukan langkah-langkah berikut:

1. Menghitung Jarak: Algoritma menghitung jarak antara data baru dengan semua data yang ada dalam dataset pelatihan. Jarak ini dihitung menggunakan distance metric (akan dibahas di bagian selanjutnya).
2. Mencari Tetangga Terdekat: Algoritma mengurutkan data pelatihan berdasarkan jaraknya dari data baru, dari yang terdekat hingga yang terjauh.
3. Memilih k Tetangga Terdekat: Algoritma memilih k data pelatihan dengan jarak terdekat (tetangga terdekat).
4. Melakukan Prediksi:
   • Klasifikasi: Data baru diklasifikasikan ke dalam kelas yang paling banyak muncul di antara k tetangga terdekat.
   • Regresi: Nilai data baru diprediksi sebagai rata-rata (atau median) dari nilai k tetangga terdekat.

Baca juga: Apa itu Algoritma AI? Panduan Lengkap untuk Pemula

Distance Metrics: Mengukur Jarak Antar Data

Konsep distance metrics sangat krusial dalam algoritma k-NN karena menentukan seberapa “dekat” atau “jauh” dua titik data. Beberapa distance metrics yang umum digunakan adalah:

Euclidean Distance

Euclidean distance adalah metrik jarak yang paling umum digunakan. Ini mengukur jarak garis lurus antara dua titik dalam ruang n-dimensi. Rumusnya adalah:

d(p, q) = √((p1 - q1)² + (p2 - q2)² + ... + (pn - qn)²)

dengan:

• p dan q adalah dua titik data yang ingin dihitung jaraknya.
• p_i dan q_i adalah koordinat titik p dan q pada dimensi ke-i.

Euclidean Distance cocok digunakan ketika data memiliki atribut yang bersifat kontinu dan tidak ada korelasi yang kuat antar atribut.

Manhattan Distance

Manhattan distance (juga dikenal sebagai city block distance atau L1 norm) mengukur jarak antara dua titik dengan menjumlahkan selisih absolut dari koordinat masing-masing dimensi. Rumusnya adalah:

d(p, q) = |p1 - q1| + |p2 - q2| + ... + |pn - qn|

Manhattan distance cocok digunakan ketika pergerakan antar titik data hanya bisa dilakukan secara horizontal atau vertikal (seperti pergerakan di blok-blok kota). Ini juga lebih robust terhadap outlier dibandingkan Euclidean distance.

Minkowski Distance

Minkowski distance adalah bentuk umum dari Euclidean dan Manhattan distance. Rumusnya adalah:

d(p, q) = (|p1 - q1|^r + |p2 - q2|^r + ... + |pn - qn|^r)^(1/r)

dengan r adalah parameter yang menentukan jenis jarak.

• Jika r = 1, maka Minkowski distance menjadi Manhattan distance.
• Jika r = 2, maka Minkowski distance menjadi Euclidean distance.

Minkowski distance memberikan fleksibilitas dalam memilih jenis jarak yang paling sesuai dengan karakteristik data.

Memilih Nilai k yang Optimal

Pemilihan nilai k (jumlah tetangga terdekat) sangat penting dalam algoritma k-NN. Nilai k yang terlalu kecil dapat menyebabkan model menjadi terlalu sensitif terhadap noise dan outlier (overfitting). Sebaliknya, nilai k yang terlalu besar dapat menyebabkan model kehilangan detail penting dan menjadi terlalu general (underfitting).

Ada beberapa pendekatan yang dapat membantu menentukan nilai k terbaik. Beberapa tips untuk memilih nilai k yang optimal:

• Cross-Validation: Salah satu metode yang umum digunakan adalah cross-validation. Data pelatihan dibagi menjadi beberapa fold, dan algoritma k-NN dilatih dan diuji pada setiap fold dengan nilai k yang berbeda-beda. Nilai k yang memberikan performa terbaik (misalnya, akurasi tertinggi) pada data validasi dipilih sebagai nilai k optimal.
• Elbow Method: Metode ini melibatkan plotting nilai k terhadap error rate (atau metrik evaluasi lainnya). Biasanya, error rate akan menurun seiring dengan meningkatnya nilai k, tetapi pada titik tertentu, penurunan error rate akan melambat dan membentuk “siku”. Nilai k pada titik “siku” ini dapat dianggap sebagai nilai k yang optimal.
• Aturan Praktis: Beberapa praktisi menggunakan aturan praktis seperti akar kuadrat dari jumlah data pelatihan (√n, dengan n adalah jumlah data pelatihan) sebagai nilai k. Namun, ini hanyalah pedoman kasar dan mungkin tidak selalu optimal.

Langkah-langkah Implementasi Algoritma k-NN

Berikut adalah langkah-langkah detail dalam mengimplementasikan algoritma k-NN:

Persiapan Data

Langkah pertama adalah mempersiapkan data. Ini meliputi:

• Pengumpulan Data: Mengumpulkan data yang relevan untuk masalah yang ingin dipecahkan.
• Pembersihan Data: Menangani missing values, outlier, dan inkonsistensi data.
• Transformasi Data: Mengubah data ke format yang sesuai untuk algoritma k-NN (misalnya, mengubah data kategorikal menjadi numerik).
• Pembagian Data: Membagi data menjadi data latih (training set) dan data uji (testing set).

Normalisasi/Standarisasi Data (Jika Diperlukan)

Jika atribut data memiliki rentang nilai yang sangat berbeda, normalisasi atau standarisasi data perlu dilakukan. Ini untuk mencegah atribut dengan rentang nilai yang besar mendominasi perhitungan jarak. Normalisasi atau standarisasi membantu memastikan bahwa setiap fitur berkontribusi secara proporsional terhadap perhitungan jarak.

• Normalisasi: Menskalakan nilai atribut ke rentang antara 0 dan 1.
• Standarisasi: Menskalakan nilai atribut sehingga memiliki mean 0 dan standar deviasi 1.

Memilih Nilai k

Pilih nilai k yang optimal menggunakan salah satu metode yang telah dijelaskan sebelumnya (cross-validation, elbow method, atau aturan praktis). Pemilihan nilai *k* yang tepat akan sangat memengaruhi performa model.

Menghitung Jarak

Hitung jarak antara data baru (yang ingin diprediksi) dengan semua data dalam data latih menggunakan distance metric yang dipilih (Euclidean, Manhattan, atau Minkowski).

Menentukan k Tetangga Terdekat

Urutkan data latih berdasarkan jaraknya dari data baru, dan pilih k data dengan jarak terdekat.

Melakukan Prediksi (Klasifikasi atau Regresi)

• Klasifikasi: Tentukan kelas data baru berdasarkan mayoritas kelas dari k tetangga terdekat.
• Regresi: Hitung rata-rata (atau median) nilai dari k tetangga terdekat untuk memprediksi nilai data baru.

Evaluasi Model

Evaluasi performa model k-NN menggunakan metrik yang sesuai dengan jenis masalah (klasifikasi atau regresi). Metrik evaluasi memberikan gambaran seberapa baik model bekerja.

• Klasifikasi: Akurasi, presisi, recall, F1-score.
• Regresi: Mean Squared Error (MSE), Root Mean Squared Error (RMSE), Mean Absolute Error (MAE).

Kelebihan Algoritma k-NN

Algoritma k-NN memiliki beberapa kelebihan:

• Sederhana dan Mudah Dipahami: Konsepnya intuitif dan mudah diimplementasikan, bahkan untuk pemula.
• Tidak Memerlukan Training yang Lama: k-NN adalah lazy learner, jadi tidak ada fase pelatihan yang eksplisit. Ini membuat proses “pelatihan” menjadi sangat cepat.
• Fleksibel: Dapat digunakan untuk masalah klasifikasi dan regresi.
• Non-Parametrik: Tidak ada asumsi tentang distribusi data yang mendasarinya. Ini membuat k-NN cocok untuk berbagai jenis data.

Kekurangan Algoritma k-NN

Algoritma k-NN juga memiliki beberapa kekurangan:

• Komputasi Mahal untuk Data Besar: Untuk setiap data baru, algoritma harus menghitung jarak ke semua data dalam dataset pelatihan. Ini menjadi sangat mahal secara komputasi jika dataset pelatihan sangat besar.
• Sensitif terhadap Outliers dan Noise: Outlier (data yang jauh berbeda dari data lainnya) dan noise dapat memengaruhi hasil prediksi secara signifikan, terutama jika nilai k kecil.
• Performa Menurun pada Data Berdimensi Tinggi: Curse of dimensionality dapat terjadi pada k-NN. Ketika jumlah dimensi (atribut) data sangat tinggi, jarak antar titik data cenderung menjadi sama, sehingga sulit untuk menentukan tetangga terdekat.
• Perlu Memilih Nilai k yang Optimal: Pemilihan nilai k yang tidak tepat dapat mengakibatkan overfitting atau underfitting.

Baca juga: Active Learning: Strategi Cerdas Hemat Biaya Pelabelan Data Machine Learning

Studi Kasus dan Contoh Penggunaan k-NN

Contoh Penerapan Algoritma k-NN

• Sistem Rekomendasi: k-NN dapat digunakan untuk merekomendasikan produk atau layanan kepada pengguna berdasarkan kesamaan preferensi dengan pengguna lain.
• Deteksi Fraud: k-NN dapat digunakan untuk mengidentifikasi transaksi keuangan yang mencurigakan berdasarkan kesamaan dengan transaksi fraud yang diketahui.
• Diagnosis Medis: k-NN dapat digunakan untuk membantu mendiagnosis penyakit berdasarkan kesamaan gejala dengan pasien lain.
• Klasifikasi Gambar: k-NN dapat digunakan untuk mengklasifikasikan gambar (misalnya, mengidentifikasi jenis objek dalam gambar) berdasarkan kesamaan fitur dengan gambar lain.
• Pengenalan Tulisan Tangan: k-NN dapat digunakan untuk mengenali karakter tulisan tangan berdasarkan kesamaan bentuk dengan karakter yang telah dipelajari.

Baca juga: Panduan Lengkap Proyek AI Sederhana untuk Pemula di Rumah

Contoh Studi Kasus: K-NN untuk Klasifikasi

Misalkan kita memiliki dataset yang berisi informasi tentang jenis bunga Iris, yang mencakup panjang dan lebar sepal serta panjang dan lebar petal. Tujuan kita adalah menggunakan k-NN untuk mengklasifikasikan spesies Iris (Setosa, Versicolor, atau Virginica) berdasarkan data ini.

Contoh Data (sebagian):

Langkah-langkah dengan k-NN:

1. Persiapan Data: Data sudah dikumpulkan dan dibersihkan. Kita akan membagi data menjadi data latih dan data uji.
2. Normalisasi Data: Karena rentang nilai setiap fitur (panjang/lebar sepal/petal) berbeda, kita perlu melakukan normalisasi.
3. Memilih Nilai k: Misalkan kita pilih k = 3.
4. Menghitung Jarak: Untuk setiap data uji, kita hitung jaraknya ke semua data latih (misalnya, menggunakan Euclidean distance).
5. Menentukan k Tetangga Terdekat: Kita pilih 3 data latih dengan jarak terdekat.
6. Melakukan Klasifikasi: Kita lihat kelas mayoritas dari 3 tetangga terdekat. Jika mayoritas adalah “Setosa”, maka data uji diklasifikasikan sebagai “Setosa”.
7. Evaluasi Model: Kita hitung akurasi model k-NN pada data uji.

Contoh Studi Kasus: K-NN untuk Regresi

Anggaplah Anda memiliki dataset yang berisi informasi tentang harga rumah berdasarkan luas tanah, jumlah kamar tidur, dan jarak ke pusat kota. Kita akan menggunakan K-NN untuk memprediksi harga sebuah rumah baru berdasarkan fitur-fiturnya.

Contoh data (sebagian):

Langkah-langkah dengan K-NN:

1. Persiapan Data: Data sudah dikumpulkan dan dibersihkan. Bagi data menjadi data latih dan data uji.
2. Normalisasi Data: Normalisasikan setiap fitur (luas tanah, jumlah kamar, jarak) karena memiliki rentang nilai yang berbeda.
3. Memilih Nilai *k*: Misalnya kita memilih *k* = 5.
4. Menghitung Jarak: Untuk data rumah baru yang ingin diprediksi harganya, hitung jaraknya ke setiap rumah dalam data latih.
5. Menentukan *k* Tetangga Terdekat: Pilih 5 rumah dalam data latih dengan jarak terdekat.
6. Melakukan Prediksi (Regresi): Hitung rata-rata harga dari 5 rumah tetangga terdekat. Nilai rata-rata ini adalah prediksi harga rumah baru.
7. Evaluasi Model: Evaluasi model menggunakan MSE, RMSE, atau MAE.

Kesimpulan

Algoritma K-Nearest Neighbors (k-NN) adalah algoritma supervised learning yang sederhana, serbaguna, dan mudah diimplementasikan. Algoritma ini bekerja dengan mencari k tetangga terdekat dari data baru berdasarkan jarak, dan kemudian mengklasifikasikan atau memprediksi nilai data baru berdasarkan tetangga-tetangga tersebut. Meskipun memiliki kelebihan seperti kemudahan implementasi dan fleksibilitas, k-NN juga memiliki kekurangan, terutama dalam hal komputasi yang mahal untuk dataset besar dan sensitivitas terhadap outlier.

K-NN cocok digunakan ketika:

• Dataset tidak terlalu besar.
• Data relatif bersih dari noise dan outlier.
• Tidak ada kendala waktu komputasi yang ketat.
• Anda membutuhkan algoritma yang sederhana dan mudah dipahami.

Jika Anda membutuhkan solusi yang lebih canggih dan terintegrasi untuk kebutuhan bisnis, Kirim.ai menawarkan berbagai layanan berbasis AI. Dengan platform SaaS, pengembangan aplikasi, dan strategi pemasaran digital, Kirim.ai dapat membantu Anda mengoptimalkan operasi bisnis, meningkatkan engagement pelanggan, dan mencapai pertumbuhan yang berkelanjutan. Pelajari lebih lanjut tentang bagaimana Kirim.ai dapat membantu bisnis Anda.