K-Nearest Neighbors (KNN): Apa Itu dan Bagaimana Penggunaannya dalam Pembelajaran Mesin

K-nearest neighbours (KNN) adalah teknik dasar dalam pembelajaran mesin (ML). Panduan ini akan membantu Anda memahami KNN, cara kerjanya, serta penerapan, manfaat, dan tantangannya.

Daftar isi

Apa algoritma k-nearest neighbours?

Bagaimana cara kerja KNN?

Perbedaan antara k-nearest neighbour dan algoritma lainnya

Bagaimana KNN digunakan dalam pembelajaran mesin?

Aplikasi KNN

Keunggulan KNN

Kekurangan KNN

Apa algoritma k-nearest neighbours?

Algoritme k-nearest neighbour (KNN) adalah teknik pembelajaran terawasi yang digunakan untuk klasifikasi dan regresi. KNN menentukan label (klasifikasi) atau nilai prediksi (regresi) dari titik data tertentu dengan mengevaluasi titik data terdekat dalam kumpulan data.

Bagaimana cara kerja KNN?

KNN didasarkan pada premis bahwa titik-titik data yang secara spasial berdekatan dalam suatu kumpulan data cenderung memiliki nilai yang sama atau termasuk dalam kategori yang serupa. KNN menggunakan ide sederhana namun kuat ini untuk mengklasifikasikan titik data baru dengan menemukan nomor preset (hiperparameter k) dari titik data tetangga dalam kumpulan data pelatihan berlabel. Nilai ini, k, adalah salah satu hyperparameter KNN, yang merupakan variabel konfigurasi preset yang digunakan oleh praktisi ML untuk mengontrol cara algoritma belajar.

Kemudian, algoritme menentukan nilai tetangga mana yang paling dekat dengan titik data baru, dan memberinya label atau kategori yang sama dengan tetangganya. Nilai k yang dipilih mempengaruhi kinerja model. Nilai yang lebih kecil meningkatkan sensitivitas kebisingan, sedangkan nilai yang lebih besar meningkatkan ketahanan namun dapat menyebabkan KNN kehilangan pola lokal.

Kedekatan, atau jarak, antar titik data dihitung menggunakan metrik yang awalnya dikembangkan untuk mengukur kesamaan titik dalam ruang matematika. Metrik umum mencakup jarak Euclidean, jarak Manhattan, dan jarak Minkowski. Performa KNN dipengaruhi oleh metrik yang dipilih, dan metrik yang berbeda berperforma lebih baik dengan tipe dan ukuran data yang berbeda.

Misalnya, jumlah dimensi dalam data, yang merupakan atribut individual yang menjelaskan setiap titik data, dapat memengaruhi performa metrik. Terlepas dari metrik jarak yang dipilih, tujuannya adalah untuk mengkategorikan atau memprediksi titik data baru berdasarkan jaraknya dari titik data lainnya.

• Jarak Euclideanadalah jarak sepanjang garis lurus antara dua titik dalam ruang dan merupakan metrik yang paling umum digunakan. Cara ini paling baik digunakan untuk data dengan jumlah dimensi yang lebih sedikit dan tidak ada outlier yang signifikan.
• Jarak Manhattanadalah jumlah perbedaan absolut antara koordinat titik data yang diukur. Metrik ini berguna ketika data berdimensi tinggi atau ketika titik data membentuk struktur seperti kisi.
• Jarak Minkowskiadalah metrik merdu yang dapat bertindak seperti jarak Euclidean atau Manhattan bergantung pada nilai parameter yang dapat disesuaikan. Menyesuaikan parameter ini mengontrol cara penghitungan jarak, yang berguna untuk mengadaptasi KNN ke berbagai jenis data.

Metrik lain yang kurang umum mencakup jarak Chebyshev, Hamming, dan Mahalanobis. Metrik ini lebih terspesialisasi dan cocok untuk tipe data dan distribusi tertentu. Misalnya, jarak Mahalanobis mengukur jarak suatu titik dari sebaran titik, dengan mempertimbangkan hubungan antar variabel. Oleh karena itu, jarak Mahalanobis sangat cocok untuk bekerja dengan data yang fiturnya menggunakan skala berbeda.

KNN sering disebut sebagai algoritma pembelajaran “malas” karena tidak memerlukan pelatihan, tidak seperti algoritma lainnya. Sebaliknya, KNN menyimpan data dan menggunakannya untuk mengambil keputusan hanya ketika titik data baru memerlukan regresi atau klasifikasi. Namun, ini berarti bahwa prediksi sering kali memerlukan persyaratan komputasi yang tinggi karena seluruh kumpulan data dievaluasi untuk setiap prediksi. ∫

Perbedaan antara k-nearest neighbour dan algoritma lainnya

KNN adalah bagian dari rangkaian besar teknik ML terawasi yang ditujukan untuk klasifikasi dan regresi, yang mencakup pohon keputusan/hutan acak, regresi logistik, dan mesin vektor pendukung (SVM). Namun, KNN berbeda dari teknik ini karena kesederhanaannya dan pendekatan langsung dalam menangani data, serta beberapa faktor lainnya.

Pohon keputusan dan hutan acak

Seperti KNN, pohon keputusan dan hutan acak digunakan untuk klasifikasi dan regresi. Namun, algoritma ini menggunakan aturan eksplisit yang dipelajari dari data selama pelatihan, tidak seperti pendekatan berbasis jarak yang dilakukan KNN. Pohon keputusan dan hutan acak cenderung memiliki kecepatan prediksi yang lebih cepat karena memiliki aturan yang telah dilatih sebelumnya. Artinya, mereka lebih cocok dibandingkan KNN untuk tugas prediksi waktu nyata dan menangani kumpulan data besar.

Regresi logistik

Regresi logistik mengasumsikan bahwa data terdistribusi secara linier dan mengklasifikasikan data menggunakan garis lurus atau hyperplane (batas yang memisahkan titik-titik data dalam ruang berdimensi lebih tinggi) untuk memisahkan data ke dalam kategori. KNN, sebaliknya, tidak mengasumsikan distribusi data tertentu. Oleh karena itu, KNN dapat lebih mudah beradaptasi terhadap data yang kompleks atau non-linier, sedangkan regresi logistik paling baik digunakan dengan data linier.

Mendukung mesin vektor

Daripada melihat jarak antar titik seperti KNN, support vector machine (SVM) fokus pada pembuatan garis pemisah yang jelas antar kelompok titik data, seringkali dengan tujuan membuat jarak antar titik selebar mungkin. SVM sangat bagus dalam menangani kumpulan data kompleks dengan banyak fitur atau ketika diperlukan pemisahan yang jelas antara kelompok titik data. Sebagai perbandingan, KNN lebih sederhana untuk digunakan dan dipahami tetapi tidak berfungsi dengan baik pada kumpulan data yang besar.

Bagaimana KNN digunakan dalam pembelajaran mesin?

Banyak algoritma ML hanya dapat menangani satu jenis tugas. KNN menonjol karena kemampuannya menangani bukan hanya satu tapi dua kasus penggunaan umum: klasifikasi dan regresi.

Klasifikasi

KNN mengklasifikasikan titik data dengan menggunakan metrik jarak untuk menentukan k tetangga terdekat dan memberikan label ke titik data baru berdasarkan label tetangga. Kasus penggunaan klasifikasi KNN yang umum mencakup klasifikasi spam email, mengelompokkan pelanggan ke dalam kategori berdasarkan riwayat pembelian, dan pengenalan nomor tulisan tangan.

Regresi

KNN melakukan regresi dengan memperkirakan nilai suatu titik data berdasarkan rata-rata (atau rata-rata tertimbang) dari k-tetangga terdekatnya. Misalnya, KNN dapat memprediksi harga rumah berdasarkan properti serupa di lingkungan sekitar, harga saham berdasarkan data historis untuk saham serupa, atau suhu berdasarkan data historis cuaca di lokasi serupa.

Penerapan algoritma KNN di ML

Karena kesederhanaannya, dan kemampuannya untuk melakukan klasifikasi dan regresi, KNN memiliki beragam aplikasi. Ini termasuk pengenalan gambar, sistem rekomendasi, dan klasifikasi teks.

Pengenalan gambar

Pengenalan gambar adalah salah satu aplikasi KNN yang paling umum karena kemampuan klasifikasinya. KNN melakukan pengenalan gambar dengan membandingkan fitur pada gambar yang tidak diketahui, seperti warna dan bentuk, dengan fitur dalam kumpulan data gambar berlabel. Hal ini membuat KNN berguna dalam bidang seperti computer vision.

Sistem rekomendasi

KNN dapat merekomendasikan produk atau konten kepada pengguna dengan membandingkan data preferensi mereka dengan data pengguna serupa. Misalnya, jika pengguna telah mendengarkan beberapa lagu jazz klasik, KNN dapat menemukan pengguna dengan preferensi serupa dan merekomendasikan lagu yang disukai pengguna tersebut. Dengan demikian, KNN dapat membantu mempersonalisasi pengalaman pengguna dengan merekomendasikan produk atau konten berdasarkan data serupa.

Klasifikasi teks

Klasifikasi teks berupaya mengklasifikasikan teks yang tidak dikategorikan berdasarkan kemiripannya dengan teks yang sudah dikategorikan sebelumnya. Kemampuan KNN untuk mengevaluasi kedekatan pola kata menjadikannya alat yang efektif untuk kasus penggunaan ini. Klasifikasi teks sangat berguna untuk tugas seperti analisis sentimen, yang mana teks diklasifikasikan menjadi positif, negatif, atau netral, atau menentukan kategori artikel berita.

Keunggulan algoritma KNN di ML

KNN memiliki beberapa manfaat penting, termasuk kesederhanaan, keserbagunaan, dan kurangnya fase pelatihan.

Kesederhanaan

Dibandingkan dengan banyak algoritma ML lainnya, KNN mudah dipahami dan digunakan. Logika di balik KNN bersifat intuitif—mengklasifikasikan atau memprediksi (regresi) titik data baru berdasarkan nilai titik data terdekat—menjadikannya pilihan populer bagi praktisi ML, terutama pemula. Selain itu, selain memilih nilai k, diperlukan penyetelan hyperparameter minimal untuk menggunakan KNN.

Keserbagunaan

KNN dapat digunakan untuk tugas klasifikasi dan regresi, yang berarti dapat diterapkan pada berbagai masalah dan tipe data, mulai dari pengenalan gambar hingga prediksi nilai numerik. Tidak seperti algoritme khusus yang terbatas pada satu jenis tugas, KNN dapat diterapkan pada kumpulan data berlabel terstruktur apa pun.

Fase pelatihan eksplisit

Banyak model ML memerlukan fase pelatihan yang menghabiskan banyak waktu dan sumber daya sebelum menjadi berguna. KNN, sebaliknya, hanya menyimpan data pelatihan dan menggunakannya langsung pada waktu prediksi. Dengan demikian, KNN dapat diperbarui dengan data baru, yang segera tersedia untuk digunakan dalam prediksi. Hal ini membuat KNN sangat menarik untuk kumpulan data kecil.

Kekurangan Algoritma KNN di ML

Terlepas dari kelebihannya, KNN juga hadir dengan beberapa tantangan. Hal ini mencakup biaya komputasi dan memori yang tinggi, sensitivitas terhadap noise dan fitur yang tidak relevan, serta “kutukan dimensi”.

Biaya komputasi prediksi

Karena KNN menghitung jarak antara titik data baru dan setiap titik data dalam keseluruhan kumpulan data pelatihannya setiap kali membuat prediksi, biaya komputasi prediksi meningkat dengan cepat seiring bertambahnya kumpulan data. Hal ini dapat mengakibatkan prediksi yang lambat ketika kumpulan data berukuran besar, atau KNN dijalankan pada perangkat keras yang tidak mencukupi.

Kutukan dimensi

KNN menderita apa yang disebut “kutukan dimensi”, yang membatasi kemampuannya untuk menangani data berdimensi tinggi. Seiring bertambahnya jumlah fitur dalam kumpulan data, sebagian besar titik data menjadi jarang dan jaraknya hampir sama satu sama lain. Oleh karena itu, metrik jarak menjadi kurang berguna, sehingga menyulitkan KNN untuk menemukan tetangga dalam kumpulan data berdimensi tinggi yang benar-benar berdekatan.

Memori intensif

Fitur unik KNN adalah menyimpan seluruh kumpulan data pelatihan dalam memori untuk digunakan pada waktu prediksi. Ketika berhadapan dengan memori yang terbatas atau kumpulan data yang besar, hal ini dapat menjadi masalah dan tidak praktis. Algoritme ML lainnya menghindari tantangan ini dengan memadatkan dan menyaring data pelatihan menjadi fitur yang dipelajari melalui pelatihan model dan pengoptimalan parameter. KNN, di sisi lain, harus menyimpan setiap titik data, yang berarti memori bertambah secara linier seiring dengan ukuran kumpulan data pelatihan.

Sensitivitas terhadap kebisingan dan fitur yang tidak relevan

Kekuatan KNN terletak pada penghitungan jarak yang sederhana dan intuitif. Namun, hal ini juga berarti bahwa fitur atau gangguan yang tidak penting dapat menyebabkan penghitungan jarak yang menyesatkan, sehingga berdampak negatif terhadap keakuratan prediksi. Oleh karena itu, teknik pemilihan fitur atau reduksi dimensi, seperti analisis komponen utama (PCA), sering digunakan dengan KNN untuk memastikan fitur penting memiliki pengaruh paling besar terhadap prediksi.