k-Nearest Neighbor Classifier

Di milis indo-dm@yahoogroups.com, pak Budi (ITS) menyampaikan e-tutorial mengenai k-Nearest Neighbor Classifier. Tema ini sangat menarik bagisaya, karena metode ini sering saya pakai sebagai pembanding performa metode yang saya kembangkan. Walau algoritma k-NN sangat sederhana, tetapi performanya sangat handal. Issue terpenting pada k-NN adalah computational cost, karena dalam proses klasifikasi, seluruh/sebagian data dipakai untuk menentukan class dari test pattern. Beberapa point yang saya catat dari diskusi tsb. adalah sbb.

1. k-NN yang dijelaskan dalam presentasi ini memakai seluruh data training-set untuk proses klasifikasi (complete storage type k-NN). Salah satu pendekatan lain adalah dengan memilih beberapa data yang mewakili untuk tiap class (prototype patterns), misalnya dengan mean vector dari data pada class tersebut. Jadi tiap class diwakili oleh satu prototype (mean vector). Kalau kasusnya binary classification, jumlah prototype nya 2. Kalau kasusnya 3 class, prototypenya 3, dst. Tetapi kalau memakai mean vector sebagai prototype untuk tiap class, tentunya decision boundary yang dihasilkan kurang memuaskan. Tiap class hanya dipisahkan oleh linear hyperplane yang ditarik lurus tepat ditengah dua buah prototype. Semakin banyak prototype, semakin halus hyperplane yang dibuat. Ada trade-off relation antara jumlah prototype (computational cost) dengan kualitas decision boundary yang dihasilkan. Apakah ada teknik lain yang bagus untuk memilih prototype tiap class ?
2. Ditinjau dari algoritmanya, k-NN sensitif terhadap keberadaan noise & irrelevant input, dibandingkan dengan neural network misalnya. Dalam proses training neural network (perceptron), weight untuk atribut yang tidak memiliki kontribusi terhadap klasifikasi akan di-adjust agar nilainya mendekati 0. Tetapi dalam k-NN, tidak ada pembedaan weight/bobot untuk tiap atribut. Apakah k-NN memiliki solusi untuk hal ini ?
3. k-NN masuk kategori supervised algorithm karena label data tetap dipakai dalam proses training, yaitu optimisasi nilai k (dan juga saat klasifikasi). Yang membedakan adalah kalau neural network, misalnya, pasangan data-label
   dipakai untuk menentukan parameter vector (weights) dalam proses training. Setelah proses training selesai, training data itu “dibuang”, tidak diperlukan lagi dalam proses klasifikasi. Adapun k-NN termasuk kategori “memory based method”, yaitu seluruhnya atau sebagian dari training set tetap disimpan dan dipakai dalam proses klasifikasi. Yang satu keluarga dengan k-NN adalah SVM, dimana sebagian ata disimpan untuk klasifikasi(yaitu data yang terpilih sbg. support vector). Ciri dari memory based method a.l. proses trainingnya berlangsung cepat, sedangkan proses klasifikasi-nya lambat.
4. Penentuan nilai k yang tepat memakai cross validation (5, 10 folds), atau leave-one-out CV jika datanya berskala kecil (sering dijumpai pada clinical database)
5. Analisa Cover yang membuktikan secara teori tingkat error estimasi 1-NN (k-NN dengan k=1) tidak akan lebih dari dua kali bayesian error [1]. Oleh Fukunaga [2], teori ini dibantah, bahwa dalam data yang berdimensi tinggi, tingkat error 1-NN bisa jadi lebih dari dua kali, tiga kali bahkan 4 kali daripada tingkat error bayes. Apakah hal ini berlaku juga untuk k>1 ? –> periksa buku Duda Hart
6. Jarak yang dipilih (e.g. (Euclidean, Minkowski ) untuk menghitung similarity pattern pada k-NN perlu pakai coba-coba. Manhattan Distance robust terhadap data ekstrim (outlier).
7. Teknik untuk mereduksi computational complexity pada proses klasifikasi k-NN dikupas di buku Duda-Hart. Yaitu
   1. Partial Distance : jarak dua titik tidak perlu dihitung dengan seluruh dimensi data yg ada. Cukup dimabil r dari d (dimensi otal). Jika dari r< d diketahui jarak antar dua titik besar, tdk perlu iteruskan utk semua dimensi. Ini mensyaratkan jenis jarak yg nondecreasing dengan bertambahnya dimensi.
   2. Search Tree
   3. Editing memakai diagram Voronoi. Data yang tidak berperan dalam training diabaikan, terutama titik data yang dikelilingi data lain dengan label yang sama.
8. Apakah decision boundary yang dihasilkan k-NN memiliki karakteristik tertentu yang membedakannya dengan neural network, SVM dan metode klasifikasi yg lain ? Saya mencoba membandingkan output space yang dihasilkan oleh 1-NN dan MLP-Backprop untuk Spiral Data sebagaimana gambar di bawah. Hidden Neuron pada MLP masing-masing 10, 50, dan 100. Stopping Criteria pada proses pembelajaran MLP adalah MSE mencapai nilai 10^-4 atau maksimal 10^3 epochs. Gambar di bawah memperlihatkan bahwa MLP tidak mampu memisahkan secara sempurna data pada kedua class.

1 Nearest Neighbor Classifier

3-layer MLP trained by backprop with hidden neuron 10, 50, 100, respectively.

Update: Lihat juga catatan diskusi 2008 oleh mas Yudi.

Referensi

1. Cover, T.M. and Hart, P.E.: Nearest neighbor pattern Classification, IEEE Trans. Inf. Theory, Vol.IT-13, No.1,
   pp.21–27, 1967
2. Fukunaga, K.: Bias of nearest neighbor error estimation, IEEE Trans. Pattern Analysis and Machine Intelligence, Vol.PAMI-9, No.1, pp.103–112, 1987