Kemal Idris: Klasifikasi

Pengertian Klasifikasi

Klasifikasi merupakan salah satu topik utama dalam data mining atau machine learning. Klasifikasi adalah suatu pengelompokan data dimana data yang digunakan tersebut mempunyai kelas label atau target. Sehingga algoritma-algoritma untuk menyelesaikan masalah klasifikasi dikategorisasikan ke dalam supervised learning atau pembelajaran yang diawasi. Maksud dari pembelajaran yang diawasi adalah data label atau target ikut berperan sebagai ‘supervisor’ atau ‘guru’ yang mengawasi proses pembelajaran dalam mencapai tingkat akurasi atau presisi tertentu.
Gambar 1 dibawah ini adalah contoh klasifikasi hewan dengan label atau target adalah reptile (reptile), serangga (insect), ikan (fish), burung (bird) dan mamalia (mammal), dan menggunakan fitur-fitur tertentu, seperti mempunyai telinga, dapat berenang, beranak, bertelur dan sebagainya, sebagai indikator-indikator suatu hewan masuk dalam kelompok hewan tertentu.

Gambar 1: Klasifikasi Hewan.

Ada beberapa jenis teknik klasifikasi antara lain:

1. Regresi Logistik

Regresi Logistik adalah suatu analisis regresi yang digunakan untuk menggambarkan hubungan antara variabel respon dengan sekumpulan variabel prediktor dimana variabel respon bersifat biner atau dikotomus. Regresi logistik Biner digunakan saat variabel dependen merupakan variabel dikotomus (kategorik dengan 2 macam kagegori),. Regresi Logistik tidak memodelkan secara langsung variabel dependen (Y) dengan variabel independen (X), melainkan melalui transformasi variabel dependen ke variabel logit yang merupakan natural log dari odds rasio (Fractal, 2003). metode ini cukup tahan (robust) untuk dapat diterapkan dalam berbagai skala/keadaan data breima(Tatham et. al, 1998). Model regresi logistik multivariate dengan k variabel prediktor adalah :

2. K-Nearest Neighboor ( yang dijelaskan mendalam )

1. Apa itu KNN?

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.

Ilustrasi cerita dari K-NN adalah sebagai berikut:

Bertanya pada Tetangga – Anda diundang ke sebuah pertemuan. Namun, Anda tidak tahu tema dari pertemuan tersebut, maupun kegiatan apa saja yang akan dilakukan di pertemuan tersebut. Anda benar-benar tidak tahu apakah pertemuan itu akan bermanfaat atau tidak untuk Anda. Yang Anda tahu, beberapa orang teman Anda juga diundang ke acara yang sama. Dalam kondisi seperti itu, apa yang Anda lakukan?

Cara yang biasanya dilakukan oleh banyak orang dalam menangani masalah seperti itu adalah dengan bertanya kepada teman-teman apakah mereka akan datang ke pertemuan tersebut atau tidak. Biasanya, orang-orang yang pertama ditanya adalah orang-orang yang dekat dengan Anda. Maka, Anda mencoba mengontak enam orang teman yang biasa jadi teman main Anda. Dari enam orang tersebut, empat orang menyatakan akan datang, tapi dua orang ternyata memutuskan tidak datang, entah mengapa alasannya. Keputusan apa yang Anda akan ambil?

Kasus di atas menggambarkan ide dari algoritma k-Nearest Neighbours (kNN). Anda ingin mengambil sebuah keputusan (kelas) antara datang atau tidak datang ke sebuah pertemuan. Untuk mendukung pengambilan keputusan tersebut, Anda melihat mayoritas dari keputusan teman-teman Anda (instance lainnya). Teman-teman tersebut Anda pilih berdasarkan kedekatannya dengan Anda. Ukuran kedekatan pertemanan ini bisa bermacam-macam: tetangga, satu hobi, satu kelas, atau hal-hal lainnya. Ukuran-ukuran tersebut bisa juga digunakan bersamaan, misalnya si A itu tetangga, satu hobi, dan satu kelas; sedangkan si B hanya satu kelas saja.

Gambar di atas menggambarkan ide dari algoritma k-Nearest Neighbours (kNN). Anda ingin mengambil sebuah keputusan (kelas) antara datang atau tidak datang ke sebuah pertemuan. Untuk mendukung pengambilan keputusan tersebut, Anda melihat mayoritas dari keputusan teman atau tetangga Anda (instance lainnya). Teman atau tetangga tersebut Anda pilih berdasarkan kedekatannya dengan Anda. Ukuran kedekatan pertemanan ini bisa bermacam-macam: satu hobi, satu kelas, atau hal-hal lainnya. Ukuran-ukuran tersebut bisa juga digunakan bersamaan, misalnya si A itu tetangga, satu hobi, dan satu kelas; sedangkan si B hanya satu kelas saja.

Dekat atau jauhnya tetangga biasanya dihitung berdasarkan Euclidean Distance, atau dapat juga menggunakan rumus jarak yang lain, seperti yang dijelaskan pada artikel Vector Space Model dan Pengukuran Jarak.

Kedekatan dapat dianggap sebagai invers jarak, alias berbanding terbalik dengan jarak. Semakin kecil jarak antara dua instance, semakin besar “kedekatan” antara dua instance tersebut. Dengan demikian, k nearest neighbours dari sebuah instance x didefinisikan sebagai k instance yang memiliki jarak terkecil (kedekatan terbesar, nearest) dengan x.

2. Tahapan Langkah Algoritma K-NN

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

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

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

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

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

3. Kelebihan dan Kekurangan dari Algoritma K-NN

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.

Pada ilustrasi di atas, kNN dapat melakukan klasifikasi dengan tepat karena garis keputusan kelasnya nonlinear. Bandingkan dengan model linear (e.g. logistic regression) yang tentunya akan menghasilkan banyak misklasifikasi jika garis keputusan kelas dalam dataset sebenarnya bersifat 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.

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. Lihat contoh berikut:

Pada ilustrasi di atas, klasifikasi sebetulnya bisa dilakukan menggunakan variabel a saja (perhatikan garis vertikal yang memisahkan kedua kelas secara linear). Namun, kNN tidak dapat mengetahui bahwa variabel b tidak informatif. Alhasil, dua instance kelas biru terklasifikasi dengan salah, karena kedua instance tersebut dekat dengan instance kelas jingga dalam dimensi b. Andaikan kita hanya menggunakan variabel a dan membuang variabel b, semua instance akan terklasifikasi dengan tepat.Pemilihan variabel sebelum menerapkan kNN dapat membantu menangani permasalahan di atas. Selain itu, kita juga bisa memberi bobot pada variabel dalam perhitungan jarak antar-instance. Variabel yang kita tahu noninformatif kita beri bobot yang kecil, misalnya:

Rentan terhadap dimensionalitas yang tinggi

§ Berbagai permasalahan yang timbul dari tingginya dimensionalitas (baca: banyaknya variabel) menimpa sebagian besar algoritma pembelajaran mesin, dan kNN adalah salah satu algoritma yang paling rentan terhadap tingginya dimensionalitas. Hal ini karena semakin banyak dimensi, ruang yang bisa ditempati instance semakin besar, sehingga semakin besar pula kemungkinan bahwa nearest neighbour dari suatu instance sebetulnya sama sekali tidak “near“.

Masalah tingginya dimensionalitas (terkadang) bisa diatasi dengan pemilihan variabel atau rekayasa fitur, misalnya dengan PCA.

§ Rentan terhadap perbedaan rentang variabel

§ Dalam perhitungan jarak antar-instance, kNN menganggap semua variabel setara atau sama penting (lihat bagian penjumlahan pada rumus perhitungan jarak di atas). Jika terdapat variabel p yang memiliki rentang jauh lebih besar dibanding variabel-variabel lainnya, maka perhitungan jarak akan didominasi oleh p. Misalkan ada dua variabel, a dan b, dengan rentang variabel a 0 sampai 1.000 dan rentang variabel b 0 sampai 10. Kuadrat selisih dua nilai variabel b tidak akan lebih dari 100, sedangkan untuk variabel a kuadrat selisihnya bisa mencapai 1.000.000. Hal ini bisa mengecoh kNN sehingga kNN menganggap a tidak membawa pengaruh dalam perhitungan jarak karena rentangnya sangat besar dibanding rentang b.Ilustrasinya diberikan di bawah ini. Manakah yang merupakan nearest neighbour dari instance x? Jika dilihat dari “kacamata” komputer, nearest neighbour x bukanlah y, melainkan z, Mengapa?
Untuk mengatasi perbedaan rentang, biasanya dilakukan preproses berupa standardisasi rentang semua variabel sebelum menerapkan algoritma kNN. Contohnya yaitu melalui operasi centre-scale atau operasi min-max.

§ Nilai komputasi yang tinggi.

§ Untuk mengklasifikasi sebuah instance x, kNN harus menghitung jarak antara x dengan semua instance lain dalam dataset yang kita miliki. Dengan kata lain, kompleksitas waktu klasifikasi kNN berbanding lurus dengan jumlah instance latih. Jika dataset yang kita miliki berukuran besar (terdiri dari banyak instance dan/atau banyak variabel), proses ini bisa jadi sangat lambat. Bayangkan, jika kita punya 10.000 instance dengan masing-masing 20 variabel dan kita ingin mengklasifikasi 100 instance baru (instance uji), maka total operasi yang harus dilakukan menjadi:(100 instance uji x 10.000 instance latih) x 20 variabel/instance x 2 operasi/variabel = 40 juta operasiBeberapa cara pengindexan (K-D tree) dapat digunakan untuk mereduksi biaya komputasi.

4. Contoh Kasus Perhitungan K-NN

Terdapat beberapa data yang berasal dari survey questioner tentang klasifikasi kualitas kertas tissue apakah baik atau jelek, dengan objek training dibawah ini menggunakan dua attribute yaitu daya tahan terhadap asam dan kekuatan.

Akan diproduksi kembali kertas tissue dengan attribute X1=7 dan X2=4, tanpa harus mengeluarkan biaya untuk melakukan survey, maka dapat diklasifikasikan kertas tissue tersebut termasuk yang baik atau jelek.

Dengan mengurutkan jarak terkecil, semisal diambil K=3, maka perbandingan nya adalah 2 (Baik) >1 (Jelek). Maka dapat disimpulkan kertas tissue dengan attribute X1=7 dan X2=4 masuk ke kelas Baik.

3. Super Vector Machine

Metode SVM SVM bertujuan untuk mencari hyperplane yang optimal. Hyperplane yang dapat membagi kedua class dengan jarak margin terjauh antar class. Margin adalah jarak antara hyperplane tersebut dengan pola terdekat dari masing-masing class. Instance yang paling dekat ini disebut sebagai support vector. Pada garis merah yang berada di atas garis hitam tebal dapat instance dengan tanda “+” yang menjadi support vector untuk kelas Men. Sedangkan pada garis merah di bawah garis hitam tebal terdapat Fajar Sodik P, Bayu Dwi P, Iqbal K 691 PRISMA 2020, Vol. 3, 689-694 instace dengan tanda “o” yang menjadi support vector untuk kelas Women. Sehingga dapat disimpulkan bahwa tujuan utama SVM adalah mencari hyperplane terbaik dengan bantuan support vector dari masingmasing class sehingga akhirnya didapat hyperplane optimal.

4. Naive bayes Metode

Naive Bayes adalah metode yang menggunakan sebuah teorema kuno warisan abad ke 18 yang ditemukan oleh Thomas Bayes (Suyanto, 2018). Dalam teorema tersebut suatu probabilitas bersayarat dinyatakan sebagai berikut:

Dimana 𝑋 adalah bukti, 𝐻 adalah hipotesis, 𝑃(𝐻|𝑋) adalah probabilitas bahwa hipotesis 𝐻 benar untuk bukti 𝑋 atau dengan kata lain 𝑃(𝐻|𝑋) merupakan probabilitas posterior 𝐻 dengan syarat 𝑋. Dalam bidang machine learning X adalah sebuah objek data, H adalah hipotesis bahwa X adalah kelas C. Secara spesifik, dalam masalah klasifikasi dapat dihitung 𝑃(𝐻|𝑋) sebagai probabilitas bahwa hipotesis benar untuk tuple 𝑋, dengan kata lain 𝑃(𝐻|𝑋) adalah probabilitas bahwa tuple 𝑋 berada dalam kelas C

5. Decision Tree

Decision tree yang dikenal juga sebagai top-down induction of decision trees (TIDIDT) adalah teknik supervised learning yang membangun representasi aturan klasifikasi berstruktur sekuensial hirarki dengan cara mempartisi himpunan data latih secara rekursif (Suyanto, 2018). Teknik ini menghasilkan pohon keputusan yang berupa n-ary branching tree yang mereprensentasikan suatu aturan klasifikasi. Beberapa teknik decision tree adalah: classification and regression tree (CART), itterative dychotomizer (ID3), C4.4 Quinlan, C5.0 Quinlan, Cubist Quinlan, Assistant Cestnik. digunakan untuk pengenalan pola dan termasuk dalam pengenalan pola secara statistik.decision tree dibentuk dari 3 tipe simpul

§ Simpul leaf memuat suatu keputusan akhir atau kelas target untuk suatu decision tree

§ Simpul root adalah titik awal dari decision tree

§ Setiap simpul perantara berhubungan dengan suatu pertanyaan atau pengujian

Gambar 3. Visualisasi Decision Tree

6. Random Forest

Metode random forest adalah pengembangan dari metode CART, yaitu dengan menerapkan metode bootstrap aggregating (bagging) dan random feature selection (Breiman, 2001). Dalam random forest, banyak pohon ditumbuhkan sehingga terbentuk hutan (forest), kemudian analisis dilakukan pada kumpulan pohon tersebut. Pada gugus data yang terdiri atas n amatan dan p peubah penjelas, random forest dilakukan dengan cara (Breiman 2001; Breiman & Cutler 2003):

§ Lakukan penarikan contoh acak berukuran n dengan pemulihan pada gugus data. Tahapan ini merupakan tahapan bootstrap.

§ Dengan menggunakan contoh bootstrap, pohon dibangun sampai mencapai ukuran maksimum (tanpa pemangkasan). Pada setiap simpul, pemilihan pemilah dilakukan dengan memilih m peubah penjelas secara acak, dimana m << p. Pemilah terbaik dipilih dari m peubah penjelas tersebut. Tahapan ini adalah tahapan random feature selection.

§ Ulangi langkah 1 dan 2 sebanyak k kali, sehingga terbentuk sebuah hutan yang terdiri atas k pohon.

Daftar Pustaka

https://journal.unnes.ac.id/sju/index.php/prisma/

https://www.megabagus.id/classification/

https://informatikalogi.com/algoritma-k-nn-k-nearest-neighbor/

https://mti.binus.ac.id/2017/11/24/klasifikasi/