Resume Video 3 : Mechine learning

 RESUME VIDEO PEMBELAJARAN 3
MECHINE LEARNING
SITI FITRIANAH (18.01.013.120)

ALGORITMA K-NN

1. Apa itu K-NN?

Algoritma K-Nearest Neighbor (K-NN) adalah sebuah metode klasifikasi terhadap sekumpulan data berdasarkan pembelajaran data yang sudah terklasifikasikan sebelumya. Termasuk dalam supervised learning, dimana hasil query instance yang baru diklasifikasikan berdasarkan mayoritas kedekatan jarak dari kategori yang ada dalam K-NN.

K-Nearest Neighbor atau yang sering disingkat dengan KNN adalah salah satu algoritma yang digunakan untuk melakukan klasifikasi terhadap objek berdasarkan dari data pembelajaran (data training) yang jaraknya paling dekat dengan objek tersebut. Tujuan dari algoritma KNN adalah mengklasifikasikan objek baru berdasarkan atribut dan sampel-sampel dari data training.

KNN adalah algoritma supervised learning yang maksudnya algoritma ini menggunakan data yang telah ada dan outputnya telah diketahui. KNN banyak dipergunakan pada aplikasi data mining, pattern recognition, image processing, dll.

2. Tahapan Langkah Algoritma K-NN

a. Menentukan parameter k (jumlah tetangga paling dekat).

b. Menghitung kuadrat jarak eucliden objek terhadap data training yang diberikan.

c. Mengurutkan hasil no 2 secara ascending (berurutan dari nilai tinggi ke rendah)

d. Mengumpulkan kategori Y (Klasifikasi nearest neighbor berdasarkan nilai k)

e. Dengan menggunakan kategori nearest neighbor yang paling mayoritas maka dapat dipredisikan kategori objek.

3. Kelebihan dan Kekurangan dari Algoritma K-NN

a. Kelebihan

 Sangat nonlinear

KNN merupakan salah satu algoritma (model) pembelajaran mesin yang bersifat nonparametrik. Pembahasan mengenai model parametrik dan model nonparametrik bisa menjadi artikel sendiri, namun secara singkat, definisi model nonparametrik adalah model yang tidak mengasumsikan apa-apa mengenai distribusi instance di dalam dataset. Model nonparametrik biasanya lebih sulit diinterpretasikan, namun salah satu kelebihannya adalah garis keputusan kelas yang dihasilkan model tersebut bisa jadi sangat fleksibel dan nonlinear.

 Mudah dipahami dan diimplementasikan

Dari paparan yang diberikan dan penjelasan cara menghitung jarak dalam artikel ini, cukup jelas bahwa algoritma kNN mudah dipahami dan juga mudah dimplementasikan. Untuk mengklasifikasi instance x menggunakan kNN, kita cukup mendefinisikan fungsi untuk menghitung jarak antar-instance, menghitung jarak x dengan semua instance lainnya berdasarkan fungsi tersebut, dan menentukan kelas x sebagai kelas yang paling banyak muncul dalam k instance terdekat.

b. Kekurangan

 Perlu menunjukkan parameter K (jumlah tetangga terdekat)

 Tidak menangani nilai hilang (missing value) secara implisit

Jika terdapat nilai hilang pada satu atau lebih variabel dari suatu instance, perhitungan jarak instance tersebut dengan instance lainnya menjadi tidak terdefinisi. Bagaimana coba, menghitung jarak dalam ruang 3-dimensi jika salah satu dimensi hilang? Karenanya, sebelum menerapkan kNN kerap dilakukan imputasi untuk mengisi nilai-nilai hilang yang ada pada dataset. Contoh teknik imputasi yang paling umum adalah mengisi nilai hilang pada suatu variabel dengan nilai rata-rata variabel tersebut (mean imputation).

 Sensitif terhadap data pencilan (outlier)

Seperti yang telah dijelaskan Ali pada artikel sebelumnya, kNN bisa jadi sangat fleksibel jika k kecil. Fleksibilitas ini mengakibatkan kNN cenderung sensitif terhadap data pencilan, khususnya pencilan yang terletak di “tengah-tengah” kelas yang berbeda. Lebih jelasnya, perhatikan ilustrasi di bawah. Pada gambar kiri, seluruh instance bisa diklasifikasikan dengan benar ke dalam kelas biru dan jingga. Tetapi, ketika ditambahkan instance biru di antara instance jingga, beberapa instance jingga menjadi salah terklasifikasi.Perlu dipilih k yang tepat untuk mengurangi dampak data pencilan dalam kNN.

 Rentan terhadap variabel yang non-informatif

Meskipun kita telah menstandardisasi rentang variabel, kNN tetap tidak dapat mengetahui variabel mana yang signifikan dalam klasifikasi dan mana yang tidak.

4. Algoritma Perhitungan KNN

a. Menentukan parameter K sebagai banyaknya jumlah tetangga terdekat dengan objek baru.

b. Menghitung jarak antar objek/data baru terhadap semua objek/data yan gtelah di training.

c. Urutkan hasil perhitungan tersebut.

d. Tentukan tetangga terdekat berdasarkan jarak minimum ke K.

e. Tentukan kategori dari tetangga terdekat dengan objek/data.

f. Gunakan kategori mayoritas sebagai klasifikasi objek/data baru.

5. Contoh soal Perhitungan KNN

Diberikan data Training berua dua atribut Bad dan Good untuk mengklasiikasikan sebuah data apakah tergolong Bad atau Good , berikut ini adalah contoh datanya :

Kita diberikan data baru yang akan kita klasifikasikan, yaitu X = 3 dan Y = 5. Jadi termasuk klasifikasi apa data baru ini ? Bad atau Good ?

Langkah penyelesaian

Pertama, Kita tentukan parameter K. Misalnya kita buat jumlah tertangga terdekat K = 3.

Ke-dua, kita hitung jarak antara data baru dengan semua data training. Kita menggunakan Euclidean Distance. Kita hitung seperti pada table berikut :

Ke-tiga, kita urutkan jarak dari data baru dengan data training dan menentukan tetangga terdekat berdasarkan jarak minimum K.

Dari kolom 4 (urutan jarak) kita mengurutkan dari yang terdekat ke terjauh antara jarak data baru dengan data training. ada 2 jarak yang sama (yaitu 4) pada data baris 2 dan baris 6, sehingga memiliki urutan yang sama. Pada kolom 5 (Apakah termasuk 3-NN?) maksudnya adalah K-NN menjadi 3-NN , karena nilai K ditentukan sama dengan 3.

Ke-empat, tentukan kategori dari tetangga terdekat. Kita perhatikan baris 3, 4, dan 5 pada gambar sebelumnya (diatas). Kategori Ya diambil jika nilai K<=3. Jadi baris 3, 4, dan 5 termasuk kategori Ya dan sisanya Tidak.

penentuan kategori yang termasuk K=3

Kategori ya untuk K-NN pada kolom 6, mencakup baris 3,4, dan 5. Kita berikan kategori berdasarkan tabel awal. baris 3 memiliki kategori Bad, dan 4,5 memiliki kategori Good.

Ke-lima, gunakan kategori mayoritas yang sederhana dari tetangga yang terdekat tersebut sebagai nilai prediksi data yang baru.

Data yang kita miliki pada baris 3, 4 dan 5 kita punya 2 kategori Good dan 1 kategori Bad. Dari jumlah mayoritas (Good > Bad) tersebut kita simpulkan bahwa data baru (X=3 dan Y=5) termasuk dalam kategori Good.