Klasifikasi: k-Nearest Neighbours

Anda diundang ke sebuah pertemuan. Namun, Anda tidak tahu tema dari pertemuan tersebut, maupun kegiatan apa saja yang akan dilakukan di pertemuan tersebut. Anda benar-benar tidak tahu apakah pertemuan itu akan bermanfaat atau tidak untuk Anda. Yang Anda tahu, beberapa orang teman Anda juga diundang ke acara yang sama. Dalam kondisi seperti itu, apa yang Anda lakukan?

Cara yang biasanya dilakukan oleh banyak orang dalam menangani masalah seperti itu adalah dengan bertanya kepada teman-teman apakah mereka akan datang ke pertemuan tersebut atau tidak. Biasanya, orang-orang yang pertama ditanya adalah orang-orang yang dekat dengan Anda. Maka, Anda mencoba mengontak enam orang teman yang biasa jadi teman main Anda. Dari enam orang tersebut, empat orang menyatakan akan datang, tapi dua orang ternyata memutuskan tidak datang, entah mengapa alasannya. Kalau sudah seperti itu, keputusan apa yang Anda akan ambil?

Kemungkinan, Anda akan memutuskan untuk datang pada pertemuan itu, karena toh teman Anda banyak yang akan datang juga. Namun, apa yang terjadi jika dari tiga orang teman yang Anda tanya pertama kali (asumsikan mereka teman terdekat Anda dari enam orang tersebut), dua orang memutuskan tidak datang dan satu orang memutuskan untuk datang? Bila hanya tiga orang tersebut yang Anda tanya, apakah Anda akan tetap datang?

Bertanya pada Tetangga

Kasus di atas menggambarkan ide dari algoritma k-Nearest Neighbours (kNN). Anda ingin mengambil sebuah keputusan (kelas) antara datang atau tidak datang ke sebuah pertemuan. Untuk mendukung pengambilan keputusan tersebut, Anda melihat mayoritas dari keputusan teman-teman Anda (instance lainnya). Teman-teman tersebut Anda pilih berdasarkan kedekatannya dengan Anda. Ukuran kedekatan pertemanan ini bisa bermacam-macam: tetangga, satu hobi, satu kelas, atau hal-hal lainnya. Ukuran-ukuran tersebut bisa juga digunakan bersamaan, misalnya si A itu tetangga, satu hobi, dan satu kelas; sedangkan si B hanya satu kelas saja.

Asumsikan bahwa Anda sebegitu kolotnya(?) sehingga Anda bertanya dengan menyambangi satu per satu rumah teman Anda (yang kebetulan masih bertetangga dengan Anda). Jika digambarkan dalam diagram, maka kurang lebih bisa terlihat seperti di bawah ini.

bound

Gambar 1: k-Nearest Neighbour

Diagram tersebut merupakan peta lokasi tempat tinggal Anda dan teman-teman Anda. Dari gambar tersebut, Anda adalah bintang merah di tengah — yang belum mempunyai kelas, bundaran berwarna ungu adalah teman yang memutuskan tidak datang, dan bundaran berwarna kuning adalah teman yang memutuskan untuk datang ke pertemuan tersebut. Nilai k adalah jumlah teman terdekat (nearest neighbours) yang akan Anda tanya.

Representasi Matematis

Dalam cerita di atas, kelas yang dianggap sebagai mayoritas adalah kelas yang jumlah instance-nya setengahnya atau lebih dari k tetangga yang dipilih (karena hanya terdapat dua kelas).

Pr(Y = j|X = x_0) = \frac{1}{k}\sum_{i \in N_0} I(y_i = j)

Formula itu dibaca: probabilitas kelas j jika diberikan x_0 sebagai data uji diestimasi sebagai jumlah dari kelas j dalam k tetangga terdekat dari x_0 dibagi dengan jumlah k tetangga terdekat yang dipilih. Nah, probabilitas untuk masing-masing kelas kemudian dihitung. Kelas dengan nilai probabilitas yang paling besar lah yang kemudian dipilih sebagai kelas hasil prediksi.

Yang jadi pertanyaan berikutnya biasanya adalah, “Berapakah nilai k yang sebaiknya digunakan?”

Menentukan Nilai k

Masalah penyesuaian parameter ini memang selalu menjadi permasalahan bagi kebanyakan algoritma pembelajaran mesin. Penentuan nilai k pun menjadi penting karena dapat sangat mempengaruhi classifier yang dihasilkan. Jika nilai k kecil, maka classifier yang dihasilkan biasnya akan rendah, tetapi variansinya tinggi. Sementara nilai k yang besar akan menghasilkan classifier yang biasnya tinggi, tetapi variansinya rendah. Contohnya bisa Anda lihat pada gambar di bawah ini.

Gambar 2: Pengaruh nilai k terhadap pembatas keputusan | sumber: [1]

Dengan nilai k yang kecil, 1 misalnya, maka error rate dari data latih bisa mencapai 0, tetapi error rate yang dihasilkan untuk data ujinya bisa menjadi tinggi. Classifier semacam itu disebut sebagai classifier yang sangat fleksibel. Lihat bagaimana pada Gambar 2 ketika k=1 pembatas keputusannya (decision boundary) meliuk-liuk sedangkan pada saat k=25 cenderung linear? Nah, ketika nilai k bertambah, error rate pada data latih akan meningkat (titik ungu yang masuk ke area kuning), tapi secara umum seharusnya error rate pada data uji akan menurun sampai pada titik tertentu sebelum naik kembali.

Galat data latih vs data uji | sumber: [2]

Gambar 3: Galat data latih vs data uji | sumber: [2]

Grafik di atas menunjukkan, dalam penelitian lain, error rate dari data latih (biru muda; 200 observasi) dan data uji (jingga; 5000 observasi). Perhatikan bahwa semakin ke kanan (nilai k mengecil, i.e.classifier semakin fleksibel), maka error rate data latihnya semakin mengecil, tetapi error rate data ujinya tidak mencapai titik minimumnya. Walakin, semakin kaku classifier-nya, i.e. semakin besar nilai k, tidak serta-merta berarti bahwa error rate data ujinya secara konstan mengecil.

Penjelasan di atas nyatanya tidak menjawab pertanyaan sebelumnya secara utuh, karena pada akhirnya ini menjadi sangat bergantung kepada kasus yang dihadapi. Lalu, apa makna bias dan variansi yang telah disebut di atas? Bagaimana pula cara mengukur “jarak” antarvariabel? Nah, untuk penjelasan lebih lanjutnya akan dibahas di pos-pos berikutnya ya!

Referensi:
[1] DeWilde, Burton. “Classification of Hand-written Digits (3).” Burton DeWilde. 26 Oktober 2012. Web. 28 Agustus 2015.
[2] James, G., Witten, D., Hastie, T., & Tibshirani, R. (2013). An Introduction to Statistical Learning (p. 39-42). New York: Springer.

Tinggalkan komentar