Catatan Tentang kNN Algorithm

Kebetulan di milis indo-dm ada diskusi panjang tentang kNN algorithm, saya buat post untuk catatan.

Definisi: kNN algorithm merupakan metode pengklasifikasian data yang bekerja relatif dengan cara yang lebih sederhana dibandingkan dengan metode pengklasifikasian data lainnya. Algorithm ini berusaha mengklasifikasikan data baru yang belum diketahui class-nya dengan memilih data sejumlah k yang letaknya terdekat dari data baru tersebut. Class terbanyak dari data terdekat sejumlah k tersebut dipilih sebagai class yang diprediksikan untuk data yang baru. k umumnya ditentukan dalam jumlah ganjil untuk menghindari munculnya jumlah jarak yang sama dalam proses pengklasifikasian.

Beberapa hal yang diperhatikan untuk menggunakan algoritma ini dengan efektif dan dapat menghasilkan pengklasifikasian dengan akurasi tinggi antara lain:

• Pemilihan k: Pemilihan jumlah k yang paling tepat perlu dijajaki agar error rate bisa diperkecil. Dalam diskusi di indo-dm, Mas Anto menjelaskan bahwa pemilihan nilai k dapat dilakukan dengan coba-coba dengan cara seperti berikut ini:

  ——————————————————————————————-

  Misalnya ada 30 ribu sampel. Pilih secara random:
  10 ribu sampel dipakai untuk “training” set
  10 ribu sampel dipakai untuk validation-set
  10 ribu sampel dipakai untuk test-set

  1. Pilih k=1
  2. Asumsinya kita pakai complete storage k-nearest neighbor, jadi seluruh data pada training set dipakai sebagai prototype. Pakai training set untuk klasifikasi data pada validation-set dengan k=1. Catat score-nya, misalnya classification rate pada validation set.
  3. Update k = k + 2.
  4. Kembali ke step 2, dengan k yang baru

  Misalnya eksperimen sudah dilakukan hingga k=11. Selanjutnya tentukan k yang terbaik, yang ditunjukkan dari score yang diperoleh. Misalnya saat k=5 scorenya tertinggi. Selanjutnya pakai k=5 untuk menguji akurasi final pada test-set. Yang dipakai tentunya training set dan test set, sedangkan validation-set tidak dipakai lagi. (Catatan sendiri: Ini mungkin kalau ingin memperbandingkan akurasi pengklasifikasian yang didapat dengan kNN dengan akurasi pengklasifikasian menggunakan classifier yang lain.)

  Sumber: The Elements of Statistical Learning: Data Mining, Inference, and Prediction (Springer)

  ——————————————————————————————-

• Feature Selection: Untuk meningkatkan tingkat akurasi pengklasifikasian, satu hal yang juga bisa dilakukan adalah dengan melakukan feature selection. Berbeda dengan Neural Network, dimana setiap input diberikan bobot yang berbeda-beda, kNN tidak memberikan bobot (weight) pada data inputnya. Dengan kata lain, semua data input mempunyai bobot (weight) dengan nilai 1. Untuk menghilangkan feature yang irrelevant, perlu dilakukan feature selection.

  Untuk melakukan feature selection, ada banyak alternatif yang bisa digunakan dan harus dicoba-coba untuk mencari yang cocok. Ada dua jenis yang dibicarakan dalam diskusi yaitu tipe filter dan tipe wrapper. Tipe filter mempunyai low computation cost sedangkan tipe wrapper umumnya sangat time consuming. Filter method menggunakan intrinsic statistical properties dari data. Contohnya: Individual Merit-Base Feature Selection dengan selection criterion: Fisher Criterion, Bhattacharyya, Mahalanobis Distance atau Divergence. Metode filter ini memilih suatu feature subset secara independen terhadap kNN classifier dan dilakukan pada tahapan preprocessing.

  Untuk tipe wrapper, selection criterion memanfaatkan classification rate dari k-nearest neighbor. Untuk menghindari time consuming, proses pemilihan umumnya cukup dengan menggunakan classification rate saat k=1. Untuk tipe wrapper, perlu untuk terlebih dahulu melakukan feature subset selection sebelum menentukan subset mana yang mempunyai ranking terbaik. Feature subset selection bisa dilakukan dengan metode sequential forward selection, sequential backward selection, sequential floating selection, GA, among others. Selain dua metode di atas ada juga metode embedded selection yang memanfaatkan suatu learning machine dalam proses feature selection.

  Sumber: J.Kittler, “Feature Selection & Extraction”, in Handbook of Pattern Recognition and Image Processing, Tzay Y. Young, King Sun Fu Ed. Academic Press, 1986.

• Feature Scaling: berfungsi untuk mengkonversi variable (feature) asli ke dalam bentuk variabel (feature) bayangan yang merupakan cerminan gabungan dari feature-feature yang diikutkan dalam proses pengklasifikasian. Cerminan gabungan ini berisikan variabel summary yang terkait erat dengan kelas-kelas model yang menjadi tujuan pengklasifikasian.

  Beberapa metode yang dapat digunakan untuk melakukan feature scaling antara lain Principal Component Analysis (PCA), Multidimensional Scaling (MDS) dan metode-metode sejenisnya. Yang perlu diperhatikan dalam melakukan feature selection dan feature scaling adalah adanya kemungkinan informasi yang berguna terabaikan dan keadaan pengklasifikasian tidak benar-benar mencerminkan keadaan lapangan karena adanya loss of information tersebut.

• Searching Algorithm (Indexing Algorithm): Untuk mempercepat proses pencarian data terdekat sejumlah k, khususnya untuk data dalam jumlah besar, pemilihan searching algorithm dalam bentuk indexing algorithm dapat meningkatkan keefektifan proses pengklasifikasian. Ada beberapa searching algorithm yang bisa digunakan termasuk Linear Scan, Kd-trees, Ball-trees, Metric-trees, Locality Sensitive Hashing (LSH) dan Agglomerative Nearest Neighbour.

  Sumber: Ian Witten, “Data Mining Practical Machine Learning Tools and Techniques”.

Beberapa property dari kNN algorithm:

• k bertambah seiring dengan pertambahan jumlah data
• Seiring dengan jumlah data yang makin banyak dan mendekati infinity, error rate dari kNN algorithm tidak akan mencapai dua kali error rate dari Bayesian Classifiers. Dengan kata lain:

  P(nb) < P(nn) < P(nb) * (2 – (P(nb) * (M / (M-1) ) ) ) < 2*P(nb)

  Atau :

  P(nb) < P(nn) < 2*P(nb)

  Sumber: Nils J. Nilsson, “Introduction to Machine Learning”; Ville Kyrki, Pattern Recognition

Mas Anto Satriyo Nugroho juga membuat catatan tentang kNN Algorithm dari diskusi yang pernah dilakukan terdahulu.