Data Analysis Series: Classifier using K-Nearest Neighbors

Posting kali ini saya akan membahas tentang salah satu classifier yang cukup banyak digunakan karena kesederhanaan komputasinya, yaitu K-Nearest Neighbors. Jika sebelumnya anda pernah membaca postingan saya sebelumnya tentang clustering menggunakan DBScan, algoritma ini sebenarnya cukup mirip dengan DBScan, yaitu dengan memperhitungkan seberapa banyak tetangga sekitar yang memiliki similarity, yang ditentukan dengan perhitungan jarak.

Heuristic

Berikut strategi pendekatan untuk melakukan implementasi dari K-NN:

1. Untuk tutorial kali ini (lagi-lagi) saya menggunakan data Iris.
2. Asumsi terdapat n baris data yang terbagi atas c kelas target.
3. Gunakan sample salah satu data untuk mengukur akurasi dari model
4. Untuk setiap itemset dari dataset Iris, ukur jarak menggunakan Euclidian Distance
5. Simpan hasil pengukuran jarak poin no 4
6. Lakukan sorting berdasarkan jarak terkecil.
7. Ambil top k teratas jarak terkecil.
8. Evaluasi hasil top k, kelas terbanyak yang ada di dalam top k, merupakan hasil prediksi dari model.

Implementasi

Berikut adalah implementasi model K-NN di python. Untuk evaluasi model, dilakukan iterasi sebanyak 100 kali, untuk setiap itemset pada setiap kelas. Sehingga total iterasi sebanyak 150x100=15000. Kemudian, untuk asumsi, diambil nilai k=30, artinya hasil prediksi mengambil 30 itemset yang mempunyai jarak terkecil dari sample.

Membaca itemset dari file Iris.

f = open('iris','r')
data = f.read().split('\n')
f.close()

Mengambil sample 20 itemset secara random, untuk setiap kelas.

[reduced_datasets.append(d) for d in (datasets[0:50][np.random.choice(50, 20, replace=False), :])]
[reduced_datasets.append(d) for d in (datasets[50:100][np.random.choice(50, 20, replace=False), :])]
[reduced_datasets.append(d) for d in (datasets[100:150][np.random.choice(50, 20, replace=False), :])]

Ukur jarak dari sample yang diambil, simpan hasil pengukurannya, kemudian lakukan sorting dari yang terkecil ke yang terbesar.

for itemset in reduced_datasets:
	ed = eucldian_distance(sample, itemset)			
	result.append([ed, itemset[4]])

	resultset = np.array(result)
	top_k = resultset[resultset[:,0].argsort()][:top_k]

Lakukan perbandingan antara kelas aktual, dengan kelas hasil prediksi.

if predicted_class == true_class:
	TRUE +=1
	total_true +=1
	print('TRUE')
else:
	FALSE +=1
	total_false +=1
	print('FALSE')

Presentasikan hasil evaluasi.

print(total_true/(epoch*number_of_data))

Summary

Dari hasil evaluasi, hasil yang didapat 100 persen sample itemset berhasil diprediksi. Hasil ini dipengaruhi oleh jumlah k yang akan diambil sebagai dasar pengambilan hasil perhitungan teratas. Sebagai contoh, apabila diambil nilai k = 20, hanya 53 persen sample itemset berhasil diprediksi. Faktor lain yang mempengaruhi adalah kualitas dataset. Apabila dataset sudah terpisah dengan baik, seperti Iris, maka tentu lebih mudah melakukan klasifikasi.