Skip to content Skip to sidebar Skip to footer
Home / Data Mining / Jurnal

Algoritma k-NN Pada Kasus Imbalanced Class

Penulis - Abdul Muiz Khalimi, S.Kom

Imbalacnce Class Distribution adalah suatu kasus dimana set data yang diperoleh memiliki atribut kelas yang tidak seimbang, dalam artian satu kelas positif dan negatif memiliki perbedaan jumlah record data yang signifikan.

Assalamualaikum Wr.Wb, Salam Sejahtera dan Salam Budaya

Pada artikel ini akan dituliskan sebuah analisis algoritma yang cocok dan memiliki kinerja yang bagus pada sebuah kasus set data yang memiliki ketidak seimbangan kelas. Artikel ini juga ditujukan untuk memberi kamu pengalaman edukasi pada ilmu data mining yang memiliki kasus imbalanced class

Dalam sebuah penelitian yang dilakukan Thammasiri et.al (2014) dikatakan bahwa sebuah set data yang bisa dibilang imbalaced class problem jika proporsi dari jumlah sebagian kecil sampel kelas lebih kecil dari 35%. Pada penelitian tersebut set data yang diperoleh sudah termasuk pada kasus imbalanced class. Dalam arti lain bisa digambarkan apabila terdapat dua kelas antara positif dan negatif memiliki perbandaingan jumlah data kelas antara 78,7% : 21,3%. Dan hasil yang diperoleh dengan membandingkan beberapa algoritma klasifikasi dengan beberapa teknik tambahan yang memiliki kinerja terbaik adalah algoritma Support Vector Machine (SVM) dengan digabungkan teknik SMOTE yang diperoleh pada beberapa nilai evaluasi performa antara lain accuracy, precision, sensitivity, specificity, FP-Rate, F-measure, CC dan GMEAN dengan cara perhitungan confusion matrix.

Dalam penelitian lain yang dilakukan oleh Brown dan Mues (2012). Dengan set data yang memiliki proporsi kelas antara 70% : 30% juga dikatakan termasuk kasus yang imbalanced class. Ia mengusulkan beberapa algoritma klasifikasi dan model kernel untutk membandingkan algoritma apa yang memiliki kinerja yang baik. Hasil yang diperoleh,  Least Square Support Vector Machines (LS-SVM) dan Random Forests serta Gradient Boosting memiliki kriteria terbaik untuk kelas masalah ketidak seimbangan, juga memberi hasil yang cukup kompetitif  dan kinerja kompetitif ini terus berlanjut ketika sampel menjadi jauh lebih tidak seimbang.

Baca Juga : Pengujian data menggunakan confusion matrix

Class Distribution in Data Mining

Pada artikel ini akan dilakukan analisis pada algoritma k-NN untuk kasus imbalanced class atau kelas yang tidak seimbang. Dengan melihat hasil yang sudah dilakukan pada tahun-tahun sebelumnya, terjadi banyak perubahan terhadap set data yang kelasnya tidak seimbang, mulai dari performa terbaik dimiliki oleh model kernel seperti SVM hingga pada model klasifikasi yeng diperoleh oleh Random Forest dan Gradients Boosting. Dengan nilai evaluasi yang diambil dari hasil Area Under Curve (AUC) dan Average Rank

Analisis Algoritma k-NN  Pada Kasus Imbalanced Class

Analisis yang akan saya tuliskan ini adalah dengan merujuk, meringkas dan review sebuah jurnal yang berjudul "Solution of class imbalance of k-nearest neighbor for data ofnew student admission selection" yang sudah dipublikasikan pada tahun 2019. 

Penelitian yang dilakukan adalah dengan mengusulkan metode klasifikasi dari data mining guna memprediksi calon peserta program tahfiz, apakah mereka Lulus atau Tidak. Hal ini dilakukan di Madrasah Tsanawiyah Plus Darul Ulum (MTs Plus DU) yang berada di Kompleks Pondok Pesantren Darul Ulum Kecamatan Peterongan Kabupaten Jombang Provinsi Jawa Timur memiliki program unggulan Tahfiz. Dimana proses pemberian keputusan sebelumnya dilakukan oleh beberapa penguji dengan waktu kurang lebih dalam seminggu, yang bisa dilakukan dengan klasifikasi dalam waktu skala yang cepat.

Data yang diperoleh setelah melakukan tahap pra proses data dengan metode cleansing duplicate data didapatkan sebanyak 259 record dan memiliki 4 kriteria penilian atau atribut berupa, membaca, menulis, kesanggupan mengikuti program tahfiz dan kemampuan menghafal. Dalam kasus konvensional penguji memberikan kriteria halafan yang berbeda-beda, namun akan diseragamkan menjadi bentuk binominal antara "ya" dan "tidak", dan akan dikonversi menjadi bilangan biner 1 untuk kategori "ya" dan 0 untuk kategori "tidak".

Klasifikasi tersebut akan dilakukan dengan menggunakan algoritma k-NN (k-Nearest Neighbor) dengan tahapan-tahapan yang sesuai standar perhitungan atau klasifikasi.
Baca Juga : Tahapan dan Cara Kerja yang Benar Algoritma k-NN (k-Nearest Neighbor)

Model validasi yang digunakan adalah menggunakan model 10-fold cross validation dimana in adalah sebuah model validasi yang dimana keseluruhan data akan dibagai menjadi 10 iterasi atau bagian , dan masing-masing iterasi akan berperan sebagai data latih dan set data uji secara bergantian dengan set sampel yeng berbeda-beda dari sebelumnya. Sedangkan metode evaluasinya sendiri akan dilakukan dengan menggunakan tabel confusion matrix yang akan mencari nilai accuracy, Error- Rate,  precision, recall dan AUC. Dengan metode tambahan pengambilan sampel yaitu teknik Linear sampling, Shuffled Sampling dan Startiffied Sampling

Baca Juga : Tutorial Rapidminer Uji Model dengan Cross Validation

Pengujian data sendiri dilakukan sebanyak 18 kali dengan penentuan uji nilai k masing-masing sebanyak 6 kali antara k = 1 , 10, 25, 50, 60, 100, hingga k = 200. Hal ini dilakukan karena algoritma k-NN, memiliki kelemahan yang bias antara parameter nilai k nya. 


Dengan hasil tersebut dikatakan bahwa metode pengambilan sampel dengan teknik Shuffled dan Stratiffied Sampling menggunakan nilai k > 60 dihasilkan algoritma k-NN memiliki nilai recall sebanyak 100%. Dalam artian bahwa k-NN mampu memprediksi dengan benar nilai yang positif atau siswa yang Lulus program tahfiz dan Tidak Lulus disetiap periodenya yang diambil siswa sebanyak 60 siswa dengan rata-rata siswa yang daftar sebanyak 259.

Kesimpulan Dari Penulis Blog

Dengan melihat hasil tersebut algoritma k-NN (k-Nearest Neighbor) juga mampu mengklasifikasikan sebuah set data yang memiliki kasus ketidakseimbangan kelas atau Imbalanced Class Distribution dengan beberapa metode tambahan seperti teknik pengambilan sampel. Tetapi nili k yang ditentukan juga sangat berpengaruh terhadap kinerja algoritma k-NN, terbukti nilai k yang ditentukan harus lebih dari 60. Meskipun dengan nilai k = 10 juga bisa optimal dengan melihat nilai AUC yang dihasilkan ( khusus untuk teknik huffled dan Stratiffied ).

Dalam jurnal atau penelitian tersebut meskipun algoritma k-NN bisa dikatakan mampu bekerja dengan baik untuk kasus imbalanced class distribution. Tetapi dalam jurnal tidak disebutkan berapa presentase atau perbandingan kelas yang tidak seimbang antara kelas Lulus dan Tidak Lulus. Tetapi kita juga bisa menganalisanya sendiri dengan melihat jumlah set data yang diperoleh dan berapa jumlah data yang akan diambil nilai Lulusnya.

Sekian itulah sebuah analisis algoritma k-NN pada kasus imbalanced class distribution dalam sebuah penelitian pada tahun 2019. Semoga tulisan ini bermanfaat dan bisa dijadikan sebagai pengalaman edukasi. " Jangan Lupa Bernafas dan Tetap Bersyukur"

Wassalamualaikum Wr.Wb

See You Later.

Sumber Referensi : 

D. Thammasiri, D. Delen, P. Meesad and N. Kasap, "A critical assessment of imbalanced class distribution problem: The case of predicting freshmen student attrition," Expert Systems with Applications, vol. 41, no. 2, pp. 321-330, 2014.

I. Brown and C. Mues, "An experimental comparison of classification algorithms for imbalanced credit scoring data sets," Expert Systems with Applications, vol. 39, no. 3, p. 3446– 3453, 2012.

S. Mutrofin, A. Mu'alif, R. V. H. Ginardi and C. Fatichah, "Solution of class imbalance of k-nearest neighbor for data of new student admission selection," International Journal Of Artificial Intelegence Research, vol. 3, no. 2, pp. 47-55, 2019.