Buku TA : K-Nearest Neighbor (KNN)

13 02 2010

K-Nearest Neighbor (KNN) adalah suatu metode yang menggunakan algoritma supervised dimana hasil dari query instance yang baru diklasifikan berdasarkan mayoritas dari kategori pada KNN. Tujuan dari algoritma ini adalah mengklasifikasikan obyek baru bedasarkan atribut dan training sample. Classifier tidak menggunakan model apapun untuk dicocokkan dan hanya berdasarkan pada memori. Diberikan titik query, akan ditemukan sejumlah k obyek atau (titik training) yang paling dekat dengan titik query. Klasifikasi menggunakan voting terbanyak diantara klasifikasi dari k obyek.. algoritma KNN menggunakan klasifikasi ketetanggaan sebagai nilai prediksi dari query instance yang baru.

Algoritma metode KNN sangatlah sederhana, bekerja berdasarkan jarak terpendek dari query instance ke training sample untuk menentukan KNN-nya. Training sample diproyeksikan ke ruang berdimensi banyak, dimana masing-masing dimensi merepresentasikan fitur dari data. Ruang ini dibagi menjadi bagian-bagian berdasarkan klasifikasi training sample. Sebuah titik pada ruang ini ditandai kelac c jika kelas c merupakan klasifikasi yang paling banyak ditemui pada k buah tetangga terdekat dari titik tersebut. Dekat atau jauhnya tetangga biasanya dihitung berdasarkan Euclidean Distance yang direpresentasikan sebagai berikut :

dimana matriks D(a,b) adalah jarak skalar dari kedua vektor a dan b dari matriks dengan ukuran d dimensi.

Pada fase training, algoritma ini hanya melakukan penyimpanan vektor-vektor fitur dan klasifikasi data training sample. Pada fase klasifikasi, fitur-fitur yang sama dihitung untuk testing data (yang klasifikasinya tidak diketahui).  Jarak dari vektor baru yang ini terhadap seluruh vektor training sample dihitung dan sejumlah k buah yang paling dekat diambil. Titik yang baru klasifikasinya diprediksikan termasuk pada klasifikasi terbanyak dari titik-titik tersebut.

Sebagai contoh, untuk mengestimasi p(x) dari n training sample dapat memusatkan pada sebuah sel disekitar x dan membiarkannya tumbuh hingga meliputi k samples. Samples tersebut adalah KNN dari x. Jika densitasnya tinggi di dekat x, maka sel akan berukuran relatif kecil yang berarti memiliki resolusi yang baik. Jika densitas rendah, sel akan tumbuh lebih besar, tetapi akan berhenti setelah memasuki wilayah yang memiliki densitas tinggi. Pada Gambar 2.13 dan Gambar 2.14 ditampilkan estimasi densitas satu dimensi dan dua dimensi dengan KNN [11].

Nilai k yang terbaik untuk algoritma ini tergantung pada data. Secara umum, nilai k yang tinggi akan mengurangi efek noise pada klasifikasi, tetapi membuat batasan antara setiap klasifikasi menjadi semakin kabur. Nilai k yang bagus dapat dipilih dengan optimasi parameter, misalnya dengan menggunakan cross-validation. Kasus khusus dimana klasifikasi diprediksikan berdasarkan training data yang paling dekat (dengan kata lain, k = 1) disebut algoritma nearest neighbor.

Ketepatan algoritma KNN sangat dipengaruhi oleh ada atau tidaknya fitur-fitur yang tidak relevan atau jika bobot fitur tersebut tidak setara dengan relevansinya terhadap klasifikasi. Riset terhadap algoritma ini sebagian besar membahas bagaimana memilih dan memberi bobot terhadap fitur agar performa klasifikasi menjadi lebih baik.

KNN memiliki beberapa kelebihan yaitu ketangguhan terhadap training data yang memiliki banyak noise dan efektif apabila training data-nya besar. Sedangkan, kelemahan KNN adalah KNN perlu menentukan nilai dari parameter k (jumlah dari tetangga terdekat), training berdasarkan jarak tidak jelas mengenai jenis jarak apa yang harus digunakan dan atribut mana yang harus digunakan untuk mendapatkan hasil terbaik, dan biaya komputasi cukup tinggi karena diperlukan perhitungan jarak dari tiap query instance pada keseluruhan training sample.

Posted By : Evan Yofiyanto @ Evan’s Blog : Kuliah Informatika (kuliahinformatika.wordpress.com)

[FREAX]


Actions

Information

19 responses

1 07 2010
Yogie

Bro, aku ijin ngutip tulisannya bwt bahan Skripsiku yah..
Trims sbelumnya🙂

27 09 2010
okaDP

ijin salin jg bro..

20 10 2010
fakhrul

Idem kaya bung yosie bro, saya juga ngutip tulisan buat bahan TA.
Thx😀

19 01 2011
gerry

bro w minta refrensi bukunya donk bli dmna??

sangat – sangat membutuhkan nie

Thx

19 01 2011
gerry

w tanya donk??w ada rumus d2(x,y)={(x-y)pangkat T(I+Dwwpangkat T)(x-y)}pangkat 1/2
maaf katro ditulis kyk gini rumusnya, nie rumus w dapat pada contoh k-nn kredit scoring

w ngk tau x itu apa, y itu apa?mgkn dari grafik ya? trus T,I, ama Dww itu apa??

w mohon banget bantuannya??

19 01 2011
gerry

w 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 w nulis rumusnya,,,

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

terima kasih atas bantuannya

28 01 2011
r1024

thx tutorialnya🙂

6 03 2011
radika666

permisi bos, saya minta ijin ngutip tulisannya ya??makasi

13 04 2011
mirza-13

thanks ya atas info na…

4 08 2011
azura

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

11 09 2011
ismi

boleh minta referensi yang lebih lengkap lagi tentang KNN gk?
kalo bisa sama studi kasusnya

9 11 2011
henry

ijin salin bro…..

12 01 2012
muklis

ijin salin mas

21 11 2012
aditya

maz saya lagi cari buku ttg metode knn kl beli di mn?… kl sampean pnya saya beli ya… tlg dgn sabgat….

28 03 2013
Hotlin Derbero

ijin copas yaa. .

17 02 2014
Putria Febriana

mas, numpang nanya, kalo knn sebagai cluster itu untuk fase trainingnya seperti apa ya, langkah2nya…

5 05 2014
oemar4share

Reblogged this on Catatan Keyboard.

4 02 2015
ollein

thanks.. ijin kutip buat TA ya…

17 03 2015
top

ijin copas 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: