K-Nearest Neighbors : Supervised Machine Learning Algorithm untuk Persoalan Klasifikasi Data



Original Source Here

K-Nearest Neighbors : Supervised Machine Learning Algorithm untuk Persoalan Klasifikasi Data

Algoritma K-Nearest Neighbors

Sebelum membahas algoritma K-Nearest Neighbors Algorithm dalam Machine Learning, ada beberapa konsep yang perlu dipahami terlebih dahulu. K-Nearest Neighbors Algorithm didasarkan pada ide pengelompokan data padaklasifikasi atau label tertentu berdasarkan kedekatan tingkat kemiripan dari data tersebut dengan data-data lain yang sudah diketahui klasifikasi atau labelnya. Untuk mendapatkan tingkat kemiripan tersebut, algoritma ini menerapkan konsep jarak antara dua titik. Setiap titik merepresentasikan suatu data yang semakin dekat jarak antar data tersebut maka semakin tinggi tingkat kemiripan data tersebut. Jika suatu data memiliki nilai kedekatan tingkat kemiripan yang tinggi atau dengan kata lain jarak antar dua titik yang merepresentasikan data tersebut kecil, data tersebut akan cenderung diklasifikasikan pada sebuah kelompok yang sama.

Titik dalam kode akan direpresentasikan dalam suatu list atau vektor dimana setiap elemen list tersebut akan merepresentasikan sebuah dimensi dari titik tersebut. Dalam implementasinya, titik tidak terbatas pada dua dimensi atau tiga dimensi saja. Suatu titik dapat terdiri dari banyak dimensi bergantung pada banyak parameter yang akan dijadikan tolak ukur untuk menghitung kedekatan data yang direpresentasikan oleh titik terkait.

Berikut beberapa jenis jarak antar dua titik yang sering digunakan dalam Machine learning :

Euclidean Distance

Euclidean Distance merupakan jarak garis lurus antara dua titik yang diukur pada sebuah bidang datar. Jarak ini diperoleh menggunakan formula pythagoras sebagai berikut.

Euclidian Distance antar titik A = [a1,a2,..,an] dan B = [b1,b2,b3,..,bn] dapat diperoleh dari perhitungan berikut :

Rumus perhitungan Euclidean Distance 2 Titik dengan n Dimensi
Fungsi perhitungan Euclidean Distance antar 2 Titik dengan asumsi kedua dimensi sama

Manhattan Distance

Manhattan Distance merupakan jumlah dari panjang ruas garis kedua titik tersebut terhadap tiap sumbu dalam koordinat Kartesius.

Manhattan Distance antar titik A = [a1,a2,..,an] dan B = [b1,b2,b3,..,bn] dapat diperoleh dari perhitungan berikut :

Rumus perhitungan Manhattan Distance 2 Titik dengan n Dimensi

Berikut implementasi pada kode dengan bahasa Python

Fungsi perhitungan Manhattan Distance antar 2 Titik dengan asumsi kedua dimensi sama

Berikut perbandingan Manhattan Distance yang dapat dihitung dari satuan grid yang dilewati garis merah, biru, atau kuning, yaitu sebesar 12 satuan, dengan Euclidian Distance yang dapat dihitung menggunakan Pythagoras sebesar 6√2 satuan.

Sumber : https://id.wikipedia.org/wiki/Jarak_Manhattan

Hamming Distance

Hamming Distance diperoleh dari membandingkan dua string data biner dengan panjang yang sama. Perhitungan jarak dilakukan dengan menghitung banyak posisi bit di mana kedua bit berbeda. Perhitungan ini dilakukan dengan menerapkan operasi XOR (notasi : ⊕) dan menghitung berapa banyak kemunculan bit ‘1’ dari string hasil operasi tersebut.

Contoh : A = 1001 dan B = 1100.
Maka diperoleh hasil dari operasi A ⊕ B = 0101 dimana terdapat 2 bit ‘1’ sehingga Hamming Distance dari kedua titik adalah 2.

Lalu bagaimana kaitan jarak dengan penyelesaian persoalan klasifikasi menggunakan KNN-Algorithm?

KNN-Algorithm sebagai salah satu supervised machine learning algorithm dapat digunakan pada data yang memiliki label. Label disini memiliki maksud yang sama dengan grup hasil klasifikasi data. Sesuai dengan namanya, K – Nearest Neighbors, ide dari algoritma ini sebenarnya cukup sederhana, yaitu menemukan sebanyak ‘K’ data yang labelnya telah diketahui dari suatu data yang labelnya ingin diketahui. Kemudian label dari data yang ingin diketahui labelnya tersebut akan diperoleh dari label data yang mendominasi dari pengambilan ‘K’ data tetangga terdekat tersebut. Pengambilan ‘K’ data terdekat tersebut dilakukan dengan melakukan perhitungan jarak dari setiap data yang sudah diketahui labelnya dengan data yang ingin diketahui labelnya kemudian melakukan pengurutan dari data terdekat.

Untuk memperoleh hasil yang baik, pengambilan nilai ‘K’ tentu sangat berpengaruh pada algoritma ini. Nilai K yang terlalu kecil atau terlalu besar dapat berpengaruh pada akurasi hasil yang diperoleh menjadi kurang baik. Untuk itu, pengambilan nilai K harus diperhatikan sebelum memodelkan data.

Aplikasi Algoritma K-Nearest Neighbors pada persoalan Klasifikasi

Berikut salah satu contoh aplikasi dari KNN-Algorithm yang telah banyak digunakan, yaitu pada pemodelan data Breast-Cancer sehingga model dapat mengklasifikasikan apakah seorang pengidap breast-cancer didiagnosis pada kategori M (Malignant/Ganas) atau B (Benign/Jinak). Data yang digunakan adalah Breast Cancer Wisconsin (Diagnostic) Data Set dari website UCI di link berikut:

https://archive.ics.uci.edu/ml/datasets/Breast+Cancer+Wisconsin+%28Diagnostic%29 .

Secara garis besar data ini menyimpan nilai-nilai dari beberapa karakteristik Nukleus / Inti sel orang-orang yang mengidap Breast Cancer.

Kode Import Library
Load dataset
Informasi atribut Dataset Breast-Cancer

Preprocessing Data

Pada pemodelan ini, atribut data yang digunakan sebagai parameter penentu klasifikasi hanyalah rata-rata dari tiap deskripsi nukleus sehingga atribut lain selain atribut tersebut dan atribut diagnosis yang merupakan atribut label dapat dihapus.

Souce code proses membersihkan dataset Breast-Cancer sesuai kebutuhan

Data Exploration

Berikut hasil visualisasi data untuk melihat perbandingan data Breast Cancer yang diklasifikasikan sebagai Malginant dan Benign.

Grafik perbandingan jumlah data kelompok M (Malignant) dan B (Benign)

Splitting Data

Pada tahap ini datataset akan dibagi menjadi 4, yaitu training_data serta training_labels yang digunakan sebagai training set dan validation_set validation_labels yang digunakan sebagai test set. Training set akan digunakan untuk memodelkan data sedangkan validation set akan digunakan untuk menghitung akurasi dari model yang telah dibangun menggunakan training set.

Pertama, data di-split secara vertikal untuk memisahkan atribut yang menjadi variabel bebas dan variabel terkait /label. Adapaun variabel bebas maksudnya adalah parameter yang dianggap akan memengaruhi hasil klasifikasi atau label dari suatu data. Nilai-nilai dari parameter ini akan menjadi elemen dari titik yang merepresentasikan data tersebut. Sedangkan variabel terkait adalah hasil klasifikasi atau diagnosis yang diperoleh, Malignant atau Benign.

Split data masing-masing dataframe hasil split sebelumnya secara horizontal sehingga 4 dataframe akan diperoleh.

Split data menjadi data training dan validasi

Data Modelling

Pada bagian ini KNN-Algorithm akan diterapkan. Untuk itu, pertama perlu ditentukan nilai K yang akan digunakan sedemikian sehingga akurasi yang diperoleh adalah akurasi terbaik. Untuk memperoleh akurasi dalam kode berikut akan digunakan fungsi KNeighborsClassifier yang terdapat pada library sklearn.neighbors

Grafik nilai K dengan akurasi yang diperoleh

Dari grafik terlihat bahwa saat nilai k = 6 atau k = 7, akurasi dari penerapan algoritma ini pada data diperoleh paling tinggi yaitu sebesar 90.35%

Sehingga dari pemodelan yang dilakukan menggunakan KNN-Algorithm serta evaluasi akurasi pada setiap nilai k dari range 1–100, diperoleh nilai k = 6 atau k=7 adalah pilihan terbaik untuk akurasi pada model dan data ini untuk mendiagnosis penderita Breast Cancer sebagai Malignant atau Benign dengan akurasi sekitar 90.35%.

Penerapan KNN-Algorithm pada kasus pengelompokan jenis diagnosis penderita Breast-Cancer terbilang baik dari segi nilai akurasi. Namun, algoritma ini memiliki beberapa kelemahan seperti kompleksitas komputasi yang cukup besar untuk mendapat nilai K yang paling akurat (perlu menerapkan exhaustive search untuk memperoleh nilai K dengan akurasi terbaik). Selain itu, seringkali juga kita tidak mengetahui secara pasti jenis perhitungan jarak apa yang terbaik untuk kasus tersebut. Pemilihan jenis perhitungan jarak yang tidak tepat tentu juga akan berpengaruh terhadap akurasi yang diperoleh.

AI/ML

Trending AI/ML Article Identified & Digested via Granola by Ramsey Elbasheer; a Machine-Driven RSS Bot

%d bloggers like this: