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

Tentang Anto Satriyo Nugroho

My name is Anto Satriyo Nugroho. I am working as research scientist at Center for Information & Communication Technology, Agency for the Assessment & Application of Technology (PTIK-BPPT : Pusat Teknologi Informasi & Komunikasi, Badan Pengkajian dan Penerapan Teknologi). I obtained my doctoral degree (Dr.Eng) from Nagoya Institute of Technology, Japan in 2003. My office is located in Serpong, Tangerang Selatan City.Since 2015, I was appointed as Program Director of R&D activities in Intelligent Computing Laboratory (former name: Digital Signal Processing Laboratory). The activities in the laboratory are organized into three groups : (i) Natural Language Processing (ii) Multimodal biometrics Identification (iii) ICT solution for Tropical Disease. I also enjoy to teach the students, as a part time lecturer in Swiss German University Serpong & UNS Sebelas Maret Surakarta. Should you want to know further information on my academic works, please visit my professional site at http://asnugroho.net
Pos ini dipublikasikan di neuro, research. Tandai permalink.

34 Balasan ke k-Nearest Neighbor Classifier

  1. iin berkata:

    kalo boleh, saya pinjam tulisan bapak ttg k-nearest ini, karena kebetulan saya sedang mencoba meneliti menggunakan algoritma ini. Trims sebelum dan sesudahnya.

  2. Silakan Mbak Iin. Saya senang kalau tulisan ini bermanfaat untuk orang banyak. Untuk gambar hasil eksperimen saya, sekiranya diperlukan boleh juga dipakai, selama menyebutkan sumber aslinya (URL blog ini).

  3. Arief F Huda berkata:

    Matur Nuhun Artikelnya,

    Saya lagi penelitian ttg face recognition,
    klasifikasi yang saya gunakan kNN,
    data face 2 Dimensi, namun hasilnya kok tidak bagus, ya..
    saya gunakan data training, kan harusnya mendekati 100%, namun ini hanya 67 %
    Setelah saya cek, (data terdiri dari 47 sample dengan 6 kelas), kelas ke 1 – 2 dikenali 100%, kelas 3-4 diatas 60%, kelas 5-6 dibawah 20%
    Apa ya sebabnya ?

  4. Mas Arief,
    Kalau melihat hasilnya, dugaan saya banyak sekali data di kelas 3-4 dan kelas 5-6 yang overlap dengan kelas 1-2. Coba diteliti error pada kelas 3-6 itu diklasifikasikan ke kelas mana ? Analisa errornya lebih baik pakai 1-NN dulu, jangan k-NN. Dengan begitu kita bisa memperkirakan distribusi data itu di feature space.

  5. Arief FH berkata:

    matur nuwun

    sudah saya coba, dan hasilnya 100%,
    termasuk untuk data testing-nya

    Jika classifier saya gunakan Back Prop (BP) dengan 3 layer, hasilnya berkisar antara 96%-98%.

    dengan BP tiap kali diulang classifikasi-nya memberikan hasil yang berbeda, memang begitu ya.. kalo pake Neural Network ?!

    Terima kasih,
    dan tak lupa saya ucapkan
    Selamat Idul Fitri
    Mohon Maaf Lahir Batin

  6. Mas Arief,

    1. Hasil neural network (MLP dilatih dg BP)
    biasanya lebih rendah daripada k-NN yang
    mengandalkan memory based learning.
    k-NN sering dipakai dalam komparasi model, karena
    memberikan hasil sub-optimal (mendekati
    optimal), jika datanya “cukup banyak”.
    Tetapi k-NN memiliki kelemahan di
    recognition-time-nya, yang sangat
    lambat, disamping itu memerlukan memory yg
    besar karena harus menyimpan prototye data
    (subset dari training set yang dipakai untuk
    klasifikasi k-NN). Sedangkan neural network
    (MLP-BP) normalnya menghasilkan model yang
    lebih sederhana, dan hanya makan memory yang
    jauh lebih kecil dibanding k-NN, karena yang
    disimpan hanya weight-nya saja.

    2. Ada kesalahan pada tulisan mas Arief yang
    sangat sering terjadi.
    BP bukan nama classifier, melainkan algoritma
    pembelajaran. Sedangkan classifier-nya adalah
    multilayer perceptron.

    3. Hasil klasifikasi yg berbeda untuk tiap
    pelatihan (dengan catatan parameternya tetap)
    disebabkan oleh perbedaan weight yang
    dihasilkan. Perbedaan weight yang dihasilkan
    karena initial weight memakai bilangan random
    yang berbeda untuk tiap kali trial. Saya
    lebih suka memakai bilangan random yang fixed,
    seed-nya konstan, tidak memakai seed yang
    selalu berubah (spt. misalnya memakai waktu).
    Keuntungannya kalau initial weight-nya selalu
    sama, kita bisa membuat perbandingan hasil
    dengan merubah parameter lain dari neural
    network tsb. (banyaknya hidden neuron, learning
    rate, sigmoid slope, dsb).
    Kalau initial weight-nya selalu berubah,
    kita tidak bisa membuat perbandingan fair
    dari berbagai parameter network tsb.

    Selamat idul fitri, dan mohon maaf lahir batin juga.

  7. maulied berkata:

    Assalamualaikum WrWb

    Bapak bisa bantu saya, mendapatkan referensi tentang metode k-nearest neighbor ini. sekarang saya lagi mengerjakan Tugas akhir tapi kesulitan mendapatkan penjelasan lengkap tentang K-NN (kalau bisa berbahasa indonesia)ini.
    Sudi kiranya bapak mau membantu saya, sebelumnya saya ucapkan terima kasih.

    Wassalam…

  8. Mas Maulied
    Wa alaikum salam Wr Wb
    Untuk penjelasan k-NN referensi yang bagus & terkenal adalah buku2 tema pattern recognition, tulisan Duda-Hart-Stork, atau Keisuke Fukunaga. Kesemuanya tertulis dalam bahasa Inggris. Tetapi kalau dalam bahasa Indonesia, saya tidak tahu apakah ada referensi yang baik atau tidak.
    Wassalam

  9. wakhid berkata:

    assalamualaikum pak anto
    saya mahasiswa sedang mengejarkan tugas akhir tentang identifikasi suara bawah air dengan menggunakan nearest neighbor. suara2 untuk training sudah saya trasformasikan dengan fft. saya masih bingung dalam proses trainingnya. saya menggunakan matlab dalam tugas akhir ini. mohon bantuan bapak untuk menjelaskan hal ini. trimakasih sebelumnya

  10. Mas Wakhid,
    Wa alaikum salam Wr Wb
    Nearest neighbor tidak mengenal fase training. Penentuan kategori sebuah test pattern dilakukan dengan cara mengukur jarak test pattern tersebut dengan semua prototype (subset dari training data yang dipakai untuk klasifikasi). Hasil klasifikasi itu adalah class dari prototype yang berjarak terdekat dengan test pattern.
    Mengenai matlab saya menyerah deh, karena nggak memakai bahasa tsb. 😀 Saya biasa membuat program sendiri pakai bhs.C.

  11. gina berkata:

    ass… saya gina mahasiswa STTTelkom bandung, senang bisa menemukan blog2 yg membahas tentang bioinformatic. saya kebetulan sedang menyusun TA saya tentang iris recognition. analisi saya di feature ekstraksinya, rencanya saya akan menggunakan circular symmetric filter (CSF), dan matching nya menggunkan NFL (nearest feature line). kesulitan saya adalah ketika mencari referensi tentang CSf nya juga NFL nya, hanya sedikit org2 yg memakai metode tersebut. jika bapak mengetahui tentang kedua metode itu, mungkn saja bapak bisa share pengetahuan tentang itu dengan saya, saya akan sangat berterima kasih. atau mungkin menshare file2 referensi yg bapak punya tentang metode itu.

  12. elisabeth berkata:

    pak,saya mahasiswa yg sedang menyusun tugas akhir tentang klasifikasi dengan menggunakan weight adjusted k-nearest neighbor tetapi referensi tentang metode ini sedikit.apa metode ini cara kerjanya berdasarkan knn hanya diperbaiki sedikit?atau apakah bapak pny referensi lain?
    terima kasih pak untuk jawabannya.

  13. pakonk berkata:

    pak klo nearest neighbor dibandingkan dengan naive bayes classifier kira2 bisa ga(sebanding)?
    perlu diadakan penelitian dahulu atau sudah jelas yg mana yg lebih bagus…
    thanks for ur answer…

  14. pakonk berkata:

    oh ya pak di tulisan bpk yg no 8 saya mo nanya juga apakah k-nn dan naive bayes decision boundary hasil klasifikasinya sama? atau ada yang membedakan?

  15. Ping balik: Catatan Tentang kNN Algorithm « Rehat With Yudi Agusta

  16. iin berkata:

    Pak Anto, sebetulnya masih banyak yang ingin saya ketahui tentang knn, namun referensi yang saya milki sangat terbatas (saya cuma punya buku dari Han & Kamber, Kaufmann, T. LArose, M. Kartandzic) untuk buku springer saya tidak ada, jadi saran dari bapak pd waktu lalu belum terlaksana. Inginnya sih ngobrol lagi langsung dengan bapak, seperti saat sebelumnya saya pernah belajar dgn bapak ttg SVM di kantor bapak, tapi mungkin saya harus menyesuaikan diri dengan waktu kerja bapak supaya tidak mengganggu. Alhamdulillah kartu nama dan no kontak ke bapak saya masih simpan. Trims pak sebelum dan sesudahnya.

  17. gina berkata:

    aslm…pa, saya ingin bertanya ttg knn sedikit. beberapa waktu yg lalu saya sempat bertanya ttg nfl dan csf. skrang saya memakai knn untuk pengenalan irisnya. yg saya ingin tanyakan adalah:
    1. sejauh yg saya tahu, kalau knn harus memakai banyak data latih, agar pengklasifikasiannya akurat. yang dimaksud banyak data tersebut, banyak kelas (otomatis banyak data juga) atau banyak data latih didalam satu kelas (ini berarti data latihnya yg banyak dari satu kelas, kelasnya bisa sedikit aja)?

    2. menyangkut data juga, jika saya memakai data banyak, ko pengkalsifikasiannya jd salah. banyak data yg tidak cocok. saya bingung. saya sudah cek, ternyata ada beberapa matrik ciri yg overlap. saya bingung, apa yg harus saya lakukan?

    3. saya memakai 4data mata untuk data latih, dan 3 data uji dalam satu kelas. apakah benar kalau k yg dipakai tidak boleh melebihi jumlah data latih dalam 1kelas. disini tidak blh melebihi 4?

    4. selain poling setelah kita memilih k ada tidak cara lain dalam pemilihan kelasnya?? slnya saya bingung menentuka rulenya jika dengan poling. jika ada, adakah referensinya? bisakah saya mendapatkannya?

    5. adakah yg sudah membuat iris recognition dengan knn?? saya ingin tahu k berapa yg dipakai.

    terima ksaih sebelumnya pak, semoga bapak berkenan untuk menjawab pertanyaan saya. waslm….

  18. Mbak Gina,

    1. Bukan hanya k-nn saja, tetapi semua metode klasifikasi memerlukan data yang “cukup banyak” agar hasilnya bagus. Bagus di sini adalah generalisasi, atau kemampuan mengenali dengan benar data yang tidak diikutsertakan dalam proses training. “Banyak” yang dimaksud adalah jumlah sample, bukan jumlah kelas.

    2. Apakah tidak karena kesalahan program ? Kalau matrik cirinya banyak yang overlap, berarti ciri/feature itu tidak terlalu baik. Feature yang baik adalah yang mampu membedakan satu klas dengan yang lain.

    3. Tidak ada ketentuan demikian. Tapi kalau cuma 4 datamata (4 pattern), terlalu sedikit dong. Untuk character recognition, biasanya skala ribuan sampel.

    4. Poling itu memang algoritma k-NN. Untuk referensinya coba dilihat di buku Pattern Classification, Richard O. Duda, Peter E. Hart, David G. Stork, John Wiley & Sons Inc, 2000

    5. Saya belum pernah membaca papernya, tapi tentunya sudah banyak banget, karena metode knn itu klasik. Memakai kNN dalam data iris, bukan satu hal yang baru/novel. kNN sering dipakai sebagai komparator performa metode yang dibangun seseorang. Kecuali kalau data iris itu diambil sendiri dari data yang lain, dan memiliki karakter problem yang berbeda dengan yang lain, barangkali baru menarik.

  19. winda berkata:

    terima kasih pak untuk informasi nya, saya ingin menyimpannya , saya ingin mempelajari lebih lanjut,

  20. nisya berkata:

    pak, perkenalkan saya mahasiswi statistika ITS. saya mo tanya tentang nonlin pca pada high dimensional data yang bukan neural network. apakah pake isomap sudah bisa, dan bagaimana cari eigen valuenya. trz bagaimana juga dengan robpca? yang pake MCD?
    terima kasih

  21. puji berkata:

    ass.
    salam kenal pak, saya puji
    kalo saya sedang mencari ttg rumus metode cross validation
    yang gunanya buat mewncari k optimum,,,(dalam hal ini k-means bukan k-nn) bapak punya referensinya ga pa??
    maksih banyak pak…

  22. yoyon berkata:

    pak, saya mau tanya…

    kenapa untuk memecahkan masalah untuk pengkelasifikasian lebih baik menggunakan metode KNN…..tidak menggunakan metode yang lain…

  23. Rio Andita Setiabakti berkata:

    aslm,

    saya sedang optimasi metode ICR yang saya gunakan. Googleing eh sampe juga ke blognya pak Anto. Bagaimana kabarnya pak?

    Saya sedang eksplorasi metode k-NN untuk digunakan dalam ICR saya pak. Seperti yang bapak bilang, k-NN dalam kecepatan rekognisinya memang cenderung lebih lama. Walaupun bisa dipercepat dengan pruning.

    Seperti sebelumnya kita pernah berdiskusi di KPU pak, saya gunakan metode ANN dengan pixel, saya ingin vektor dijadikan 2nd opinion dari peringkat hasil keputusan ANN. Sehingga harapan saya akurasi bertambah.

    Nah, menurut pandangan bapak metode k-NN ini tepat gak jika saya gunakan dalam aplikasi komersil yang membutuhkan waktu cepat dalam rekognisi? Karena setahu saya k-NN banyak digunakan dalam online recognition bukan offline.

  24. arif windarto berkata:

    pak saya boleh minta referensinya tentang k-nn…
    kebetulan saya meneliti itu untuk pengenalan sinyal wicara

  25. ely berkata:

    pak, saya sedang menjalani tugas akhir credit skoring dengan KNN, namun saya masih kurang paham dengan konsepnya. adakah literatur yang mudah untuk saya pelajari? dan memakai software apakah nantinya dalam aplikasi datanya? terimakasih

  26. david berkata:

    pak, saya tertarik membaca tentang artikel yang bapak teliti ttg k-NN, untuk sekarang saya sedang menyelesaikan tugas akhir sebagai mahasiswa, yang ingin saya tanyakan, apakah k-NN akan lebih baik dalam analisi klasifikasi kelas suara? lalu bagaimana jika memakai klasifikasi SVM? apa kah SVM lebih baik dari klasfks k-NN? terimakasih informasi pengetahuannya ^^

  27. krisna berkata:

    pa, saya mahasiswa tingkat akhir yang mengambil skripsi tentang klasifikasi. saya ingin membandingkan performansi algoritma knn dan naive bayes untuk pengklasifikasian teks. saya masih kekurangan sumber mengenai knn ini. kebanyakan pembahasan knn lebih ke patern recognition.
    mohon tutorialnya mengenai knn untuk klasifikasi teks, saya masih kurang faham mengenai alur kerja algoritmanya.

  28. poullos berkata:

    salam kenal…..,pak saya sedang melakukan penelitian TA menggunakan SVM dalam mengidentifikasi sidik jari ,mau tanya?perancangan alur diagram tahap demi tahap yang lebih baik bagai mana ya pak? dan pengetahuan tentang SVM dalak klasifikasi…,atas bantuan napak saya ucapkan terima kasih….,by: polo_4035@yahoo.co.id

  29. danis berkata:

    ass.
    salam kenal pak, saya danis
    kalo saya sedang mencari ttg rumus metode cross validation
    yang gunanya buat mewncari k optimum,,,(dalam hal ini k-means bukan k-nn) bapak punya referensinya ga pa??
    maksih banyak pak…

  30. gerry berkata:

    saya mo tanya donk??

    ad artikel credit scoring memakai metode knn, nah disitu ad rumus :
    d(x,y)={(x-y)pangkat T(I+Dwwpangkat T)(x-y)}pangkat 1/2

    maaf katro saya nulis rumusnya,,,

    saya ngk ngerti nama2 variabel ini I untuk apa Dww untuk apa??
    mohon penjelasannya???

    terima kasih atas bantuannya

  31. azura berkata:

    saya mahasiswa tingkat akhir lagi kebingungan neih pak,,,mau minta tolong masukkannya kira2 algoritma apa ya yang cocok untuk membandingkan sesuatu,,judul saya berkaitan dengan menganalisis perbandingan kesehatan dan kecerdasan bayi/balita

  32. nicky berkata:

    ass ..
    maaf pak, saya masih binggung dengan penghitungan rumus knn ,, terutama di variable nya pak ,, bisa tolong dijelaskan pak .
    trim’s..

  33. randy berkata:

    ass..maaf pak sedikit oot, saya mau nanya pak, saya lagi ngerjain tugas akhir dibidang image processing, mengidentifikasikan manfaat tumbuhan herbal.. menggunakan bahasa pemrograman java untuk di implementasikan sebagai aplikasi pada smartphone android, cuma saya masih bingung dalam pemilihan metode klasifikasi mana yang paling tepat.. saya mohon bantuan bapak berupa ide metode mana yang kira2 tepat selain template matching, terimakasih banyak pak,,

  34. Abdullah Arief berkata:

    Asslammualaikum Pak.. Saya mahasiswa semester akhir dalam proses pengerjaan Tugas Akhir mau bertanya masalah metode KNN ini, bagaimana cara menghitung manual dari eror rate untuk metode KNN ini.. trimss..

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s