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.
- 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 ?
- 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 ? Baca entri selengkapnya »
