How KNN Algorithm Works
Algoritma KNN adalah salah satu algoritma paling simple dan juga yang paling mudah digunakan. Namun sebelum kita membahas mengenai algoritma ini, yuk kita bahas dahulu apa itu Machine Learning
Secara singkat Machine Learning adalah pembelajaran mesin menggunakan data yang kita berikan. Machine Learning secara umum terbagi atas Supervised Learning, Unsupervised Learning, dan Reinforcement Learning, tapi dalam kesempatan kali ini saya hanya akan menjelaskan tentang Supervised Learning karena KNN adalah salah satu contoh dari Supervised Learning.
Seperti namanya Supervised Learning, artinya kita ‘mengajari’ sendiri model dari Machine Learning yang kita buat. Model ini akan kita beri data-data berisi fitur-fitur dan juga label atau yang biasa disebut variabel target. Karena cukup sulit untuk menjelaskannya mari kita umpamakan model ini sebagai anak kecil, data berisi fitur-fitur adalah gambar anjing atau bukan anjing dan variabel target berupa jawaban ‘anjing’ atau ‘bukan anjing’. Saat anak kecil itu kita beri gambar anjing kita katakan ‘ini adalah anjing’ dan jika bukan maka kita katakana ‘bukan’, lama kelamaan anak kecil tersebut akan bisa membedakan anjing dan bukan anjing.
Nah, sekarang mari kita bahas mengenai algoritma KNN
KNN atau K-Nearest Neighbor adalah salah satu algoritma Supervised Learning. Seperti namanya, model KNN akan melihat jumlah tetangga terbanyak yakni jumlah data terbanyak yang paling dekat. Metode ini cukup sulit dijelaskan oleh kata-kata jadi mari kita coba visualisasikan model ini dengan K=3.
Letak dari masing-masing data melambangkan fiturnya, dan warna merah dan biru adalah variabel targetnya. Titik berwarna hitam melambangkan data yang belum pernah ada di model yang harus kita prediksi targetnya. Karena dipilih K = 3 artinya melihat 3 ‘Tetangga’ terbanyak, karena 3 tetangga terdekat semuanya warna biru, artinya menurut model ini, titik hitam tersebut akan termasuk yang warna biru.
Sekarang mari terlebih dahulu kita bahas penentuan ‘tetangga’ ini.
Ya, dari gambar diatas sudah dapat ditebak bukan? Penentuan tetangga ini menggunakan Euclidean Distance (default) dari titik hitam (yang ingin diprediksi) ke masing-masing data. Rumus yang dipakai tidak lain adalah rumus Pythagoras!
Sebagai contoh dalam gambar 2 diatas, jarak titik hitam ke titik B1 (L1), ke B2 (L2), ke B3 (L3) dst akan diurutkan dari nilai yang terkecil ke terbesar. Nilai yang sudah berurut itu kemudian akan diambil dari yang terkecil hingga bilangan ke-3 terkecil (bergantung pada nilai K). Dalam gambar contoh ialah B3, B4, dan B5 .Setelah itu hasil prediksi dari titik hitam itu akan berupa modus dari data variabel target yaitu target karena B3, B4, dan B5 adalah biru artinya modusnya juga biru, jadi hasil prediksi titik hitam itu menurut model ini adalah biru.
Lho, kalau prediksinya berdasarkan modus maka kalau diambil K=7 bukannya hasil prediksi jadi merah? Benar! Dalam KNN pemilihan K benar-benar crucial dan perlu banyak pertimbangan, karena jumlah k yang dipilih akan benar-benar mempengaruhi hasil prediksi.
Lantas bagaimana cara memilih K?
Sebenarnya tidak ada cara spesifik untuk menentukan nilai K karena tiap data pasti memiliki model optimalnya masing-masing, namun ada beberapa hal yang perlu diperhatikan:
1. Semakin kita mengecilkan nilai K, maka kebanyakan data akan diabaikan. Bayangkan saja jika kita mengambil K = 1 dan titik yang ingin kita prediksi berada di sekeliling titik biru yang sangat banyak namun ada 1 titik merah (outlier) yang sangat dekat dengan titik tersebut. Tentunya hasil prediksi ini tidaklah besar persentase kebenarannya.
2. Semakin kita menaikkan nilai K, maka hasil prediksi akan semakin sama. Jika K = jumlah data, artinya semua titik baru akan mendapat prediksi yang sama. Tentunya hal ini akan berakibat fatal.
3. Pemilihan nilai K sebaiknya ganjil untuk menghilangkan kemungkinan adanya 2 nilai modus.
Kapan kita menggunakan KNN dan kapan kita harus menghindarinya?
Perlu diperhatikan algoritma KNN hanya dapat dipakai saat data yang ada relatif kecil. Hal ini dikarenakan pada algoritma nya, tiap kali ada data yang ingin di prediksi, jarak dari setiap titik harus dihitung.
KNN vs Other Supervised Learning Algorithms
Pada Supervised Learning, masih terdapat banyak algoritma lain seperti KNN. Diantaranya seperti Linear Regression, Similarity Learning, Decision Tree, dan lainnya. Salah satu kelebihan KNN dari algoritma yang lain adalah KNN sangat fleksibel, yakni dapat digunakan dalam Klasifikasi maupun Regresi dan menghasilkan hasil yang cukup baik tidak seperti metode Decision Tree yang hanya dapat dipakai di Klasifikasi ataupun Linear Regression yang hanya dipakai di Regresi.
KNN vs K-Means Clustering
Pada Unsupervised Learning ada metode bernama K-Means Clustering yang sering kali disamakan dengan K-Nearest Neighbor. Meskipun keduanya melibatkan jarak terdekat (pada K-Means jarak dari tiap titik ke centroid dan pada KNN jarak dari titik ke titik lain) namun kedua algoritma ini sebenarnya sangatlah berbeda. Pada K-Means Clustering tidak ada data yang ingin diprediksi, yang ada adalah Clusetering atau pengelompokan data. Dengan kata yang lebih sederhana, KNN itu sebenarnya bertujuan melabeli data baru dengan menggunakan bantuan data berlabel yang ada, sedangkan K-Means Clustering ingin melabeli setiap data yang sama sekali tidak berlabel.
Akhir kata
Algoritma KNN merupakan algoritma sederhana yang hanya menggunakan jarak sebagai penentu. Algoritma ini sangatlah cocok digunakan oleh pemula yang ingin mengetahui konsep kerja Machine Learning dan bagi mereka yang ingin lebih mendalami Machine Learning. Algoritma KNN merupakan algoritma yang sangat fleksibel yang bahkan dapat digunakan dalam Klasifikasi maupun Regresi. Dengan menggunakan model yang tepat, algoritma KNN ini dapat menjadi tool yang sangat kuat!
Daftar Pustaka
Harrison, O. (2018). ”Machine Learning Basics with the K-Nearest Neighbors Algorithm”. [Online]. Diakses 26 Juli 2020 dari https://towardsdatascience.com/machine-learning-basics-with-the-k-nearest-neighbors-algorithm-6a6e71d01761
Srivastava, Tavish. (2018). “Introduction to k-Nearest Neighbors: A powerful Machine Learning Algorithm (with implementation in Python & R)”. [Online]. Diakses 28 Juli 2020 dari https://www.analyticsvidhya.com/blog/2018/03/introduction-k-neighbours-algorithm-clustering/
