Klasifikasi dokumen teks menggunakan KNN berbasis TF-IDF (Part 1)
KNN merupakan salah satu algoritma/metode klasifikasi yang cukup populer digunakan untuk melakukan proses prediksi berdasarkan data atau fakta yang sudah diketahui sebelumnya. Contoh sederhana pengaplikasian dari klasifikasi adalah proses mendeteksi spam pada email. Sebelum proses klasifikasi dilakukan, kita harus memiliki beberapa data email yang tergolong sebagai spam sekaligus email yang bukan merupakan spam. Artinya disini kita memiliki dua klasifikasi yaitu email yang memiliki label spam dan email yang memiliki label bukan spam. Pada tulisan ini akan saya ulas mengenai proses klasifikasi pada objek data berupa dokumen teks.
KNN Classifier
KNN merupakan singkatan dari K-Nearest Neighbor (k-tetangga terdekat) yang memiliki maksud bahwa k adalah variabel yang menunjukan jumlah tetangga terdekat yang dianggap mempengaruhi data lain. Oke, lebih jauh lagi KNN merupakan salah satu algoritma yang berdasarkan machine learning. Algoritma ini merupakan salah satu algoritma paling sederhana dan juga dianggap paling “lazy” atau malas. Tujuan algoritma ini adalah untuk mengklasifikasikan objek ke dalam kelas-kelas yang sudah didefinisikan sebelumnya. Algoritma ini sedikit berbeda dengan algoritma klasifikasi lainnya karena pada tahap pembentukan classifier KNN tidak membutuhkan data yang diketahui label/kelasnya terlebih dahulu (algoritma klasifikasi pada umumnya membutuhkan data training untuk membentuk model classifier), lalu bagaimana cara algoritma ini bekerja? apakah tidak bertentangan dengan prinsip klasifikasi? KNN bekerja dengan prinsip dasar mencari tingkat kemiripan suatu objek dengan beberapa objek lainnya. Proses untuk mengetahui tingkat kemiripan dilakukan dengan menggunakan melakukan perhitungan jarak dengan Euclidean. Perhitungan jarak dilakukan pada bidang datar dengan sumbu x dan y dimana masing-masing objek dianggap sebagai sebuah titik yang memiliki koordinat, misalkan ada 2 titik p dan q, masing-masing adalah p=(a,b) dan q=(c,d). Dapat dituliskan bahwa jarak antara p dan q adalah sebagai berikut:
Saya akan membuat ilustrasi dengan membuat masalah yang sangat sederhana, seperti pada gambar dibawah ini, terdapat 2 kelompok besar, polisi dan pencuri. Ada satu orang yang belum diketahui identitasnya sehingga kita belum bisa menentukan apakah dia polisi atau pencuri. Tugas utama kita adalah mencari tahu apakah orang tersebut adalah polisi atau pencuri.
Dengan menggunakan KNN maka kita harus mencari tingkat kemiripan/jarak antara seseorang yang belum kita ketahui identitasnya dengan seluruh orang yang ada dalam 2 kelompok tersebut. Setelah kita mengetahui tingkat kemiripan dengan hitungan jarak, maka jarak-jarak tersebut diurutkan berdasarkan nilai terkecil (terdekat) sampai ke jarak yang paling besar. Setelah terurut, maka kita tentukan berapa jumlah tetangga terdekat yang akan kita anggap sebagai penentu. Pada contoh kasus ilustrasi diatas nilai k maksimal adalah 16 dan minimal adalah 1. Berikut ini adalah urutan jarak antara orang yang belum diketahui identitasnya dengan objek lain mulai dari yang terdekat sampai terjauh. Misalkan kita menentukan bahwa nilai k adalah 5, maka dari 5 terdekat adalah Pencuri, Pencuri, Pencuri, Polisi, Pencuri. Dapat dipastikan bahwa orang yang belum diketahui identitasnya adalah seorang Pencuri karena dari 5 data tersebut komposisinya adalah 4 Pencuri dan 1 Polisi.
