Catatan Tentang kNN Algorithm

27 03 2008

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.


Actions

Information

10 responses

6 05 2016
untung saputra

mohon petunjuknya pak untuk algoritma KNN itu cara memberikan bobot pada suatu atribut data itu gimana pak . makasi pak dan untuk mencari nilai k itu seperti apa rumusnya makasi pak

6 05 2016
Yudi Agusta

Bobot suatu atribut sangat penting untuk memberikan keseimbangan kontribusi dalam perhitungan jarak. Normalisasi adalah suatu cara untuk bisa digunakan untuk memberikan bobot yang sama antar variabel yang digunakan dalam perhitungan. Sementara untuk nilai k dalam KNN, sudah dijelaskan dalam tulisan saya tentang kNN, dan yang pasti nilai k harus ganjil untuk bisa memberikan keputusan dalam pelaksanaan klasifikasi. Tks

21 12 2012
aditya

mohon di bantu cara menentukan nilai bobot pada akselerasi,bahan bakar,emisi dan setatus mutu saya memakai metode k-nn pada skipsi saya mohon bantuanya trimaksaih🙂

26 02 2014
Yudi Agusta

Nilai bobot, maksudnya jarak mungkin ya. Jarak bisa dihitung dengan berbagai konsep jarak seperti Eucledian yang paling umum. Untuk konsep jarak yang lain bisa lihat di https://yudiagusta.wordpress.com/2008/05/13/similarity-measure/

Regards,

13 05 2011
anggra

bisa minta alamat email??? soalnya saya ingin sharing dengan bapak… terima kasih

26 02 2014
Yudi Agusta

Bisa dilihat di vitae kita di : https://yudiagusta.wordpress.com/vitae/

Regards,

3 05 2010
tama

Tulisannya bermanfaat pak, tapi saya harus baca2 lagi referensi ttg K-NN ini, soalnya mo buat SPK mengenai Gizi pak, mungkin pak yudi bisa memberikan referensi untuk tugas akhir saya

3 05 2010
Yudi Agusta

Mungkin bisa memanfaatkan internet untuk mencari referensi. Saya sempat menulis tentang ini sebelumnya: https://yudiagusta.wordpress.com/2008/04/11/tips-mencari-artikel-ilmiah-gratis/. Mungkin bisa bermanfaat. Kalau ada buku diktat kuliah tentang data mining, mungkin akan sangat membantu.

Demikian semoga bisa jadi referensi.

5 08 2008
winda

terima kasih pak untuk informasinya, sangat bermanfaat

winda

28 03 2008
k-Nearest Neighbor Classifier « Corat-coret Anto S. Nugroho

[…] Lihat juga catatan diskusi 2008 oleh mas […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: