KATEGORI: MACHINE LEARNING
Membahas Algoritma-Algoritma Machine Learning Untuk Klasifikasi
Proses-proses singkat bagaimana algoritma menemukan pola terhadap data.
Sebelum membaca, saya mau memberikan peringatan untuk meng-Kritik saya apabila ada teori pemahaman yang salah. Terimakasih perhatiannya 😊.
Data Mining atau bahasa Indonesianya Penggalian Data adalah menemukan pola dan informasi bermakna lainnya dalam data. Seperti yang kita tahu, data sudah dapat ditemukan dimana saja, namun bagaimana mengolah data yang tidak bersih/biasa-biasa saja menjadi informasi yang sangat bermakna diperlukan pengetahuan khusus lagi, yaitu Data Mining.
Pada artikel kali ini kita akan mengenal sedikit lebih dalam tentang algoritma Machine Learning. Algoritma tersebut ditemukan dan dikembangkan oleh banyak peneliti, sehingga kita dapat fokus terhadap implementasi keilmuan tersebut.
Semua kegiatan menemukan pola dalam data, bisa dikerjakan oleh 5 algoritma yang hari ini kita bahas. Singkatnya, mereka hanyalah Persamaan Matematika yang di setel untuk memberikan kita jawaban yang paling akurat dan cepat. Kita tidak akan membahas panjang proses matematisnya, lebih kepada proses singkat bagaimana algoritma tersebut bekerja.
Silahkan pergi kesini untuk mengetahui Dasar-Dasar Machine Learning.
A. Support Vector Machines
Support Vector Machines (SVM) merupakan bagian dari Supervised Machine Learning yang digunakan untuk klasifikasi, regresi dan deteksi outlier. Umum digunakan untuk klasifikasi. Algoritma Klasifikasi SVM juga adalah alternatif lain setelah menggunakan algoritma KNN (akan kita bahas nanti).
SVM mencari Hyperplane terbaik untuk memisahkan 2 kelas atau lebih dan memaksimalkan margin.
Mari kita coba dengan ilustrasi, ini saya temukan dari Penulis Lujing Chen. SVM seperti jalan raya, tembok pemisah ditengah adalah Hyperplane. Sedangkan mobil yang paling dekat dengan tembok pemisah adalah Support Vector, lalu jarak antara keduanya disebut Margin.
Support Vector adalah titik data yang paling dekat dengan Hyperplane, jika dihapus itu akan mempengaruhi hyperplane yang akan dibentuk kembali. Karena hal itu, mereka dapat dianggap elemen penting dalam kumpulan data.
Margin adalah jarak antara Support Vector dengan garis, hyperplane yang dibentuk harus memenuhi 1 kriteria, yaitu jaraknya harus paling maksimal. Apa maksudnya?
1. Pemisahan Secara Linear
Coba tebak mana margin yang paling maksimal? Yap saya sudah tau pasti kalian memilih Third Plane, karena jarak antara Hyperplane dengan kedua support vector sudah paling maksimal.
Tapi mari kita bahas, kenapa kita tidak memilih First & Second Plane?
- First Plane, jarak dengan support vector berwarna hijau mungkin sudah bisa dibilang sangat jauh, namun tidak dengan jarak support vector warna oren. Sehingga tidak dapat dikatakan maksimal keduanya.
- Begitupun Second Plane, malah jarak dengan support vector oren menjauh, namun tidak dengan support vector warna hijau.
2. Pemisahan Secara Non-Linear
Dalam kasus pemisahan linear, SVM cukup mencari Hyperplane yang paling optimal dan benar memisahkan 2 kelas tersebut. Namun dataset yang ditemukan di dunia nyata jarang ditemukan kasus pemisahan secara linear, jadi kondisi akurasi 100% itu tidak ada. Bahkan kalaupun 100%, kita harus mulai waspada terhadap Overfitting.
SVM memperkenalkan 2 konsep yaitu Soft Margin dan Kernel Trick untuk mengatasi pemisahan secara Non-Linear.
a) Soft Margin
Kita lihat pada plot diatas, garis linear yang terbentuk tetap sama, padahal ada beberapa titik data oren yang terdapat pada area hijau. Soft Margin mengizinkan sedikit kesalahan klasifikasi, dan tetap memaksimalkan margin.
Soft Margin yang saya jelaskan tadi jangan disalah artikan hanya untuk pemisahan linear. Ini dapat digunakan pada keduanya. Tingkat toleransi terhadap kesalahan klasifikasi adalah train-parameter penting untuk SVM.
Dalam library Sklearn, nilai ini diwakili oleh parameter C. Semakin besar nilai C yang diberikan, semakin sedikit toleransi terhadap kesalahan klasifikasi. Lihat pada plot dikiri, hyperplane berusaha untuk tidak melakukan kesalahan klasifikasi, sedangkan yang dikanan memaklumi sedikit kesalahan klasifikasi.
Namun bukan berarti nilai C yang besar selalu buruk, lihat gambar dibawah.
b) Kernel Trick
Jika plot datanya sudah seperti diatas, kita memerlukan pemisahan yang semakin rumit (Non-Linear). Kernel Trick membuat fitur original menjadi dimensi yang lebih besar, sehingga titik datanya dapat dipisahkan secara linear. Dari titik data 2 dimensi diatas, diubah menjadi titik 3 dimensi, lihat dibawah.
Dengan begini, area titik data merah dan hijau sudah terlihat. SVM akan memberikan hyperplane papan kotak 3D di tengah sana, sehingga jika di kembalikan menjadi 2D, hyperplane yang terlihat seperti gambar dibawah.
Ada 5 tipe kernel dalam Scikit learn yaitu linear, poly, rbf, sigmoid, precomputed. Pada lain kesempatan akan saya bahas lebih dalam.
Sebelumnya kita sudah membahas Kernel Trick, terdapat 1 topik yang penting dibahas yaitu Gamma, merupakan train-parameter yang ada pada tipe kernel rbf, ini penting untuk memperluas dan memperkecil area setiap kelas.
Hati-hati saat menentukan nilai gamma, jika terlalu besar, resiko overfitting bisa terjadi.
Lalu bagaimana cara untuk menentukan nilai Gamma dan C yang optimal? Kita bisa melakukan Grid Search atau Cross Validation. Pada lain kesempatan, hal ini juga akan saya bahas.
B. Decision Tree
Decision Tree merupakan algoritma Supervised Machine Learning. Bisa digunakan untuk regresi dan klasifikasi. Tapi yang ingin kita bahas hari ini adalah bagian klasifikasi. Namun pembahasannya lebih ke bagaimana proses singkat dalam Decision Tree latihan dengan data latih (Training Data).
Sebelum membuat pohon keputusan, tentu kita akan mulai dari akar terlebih dahulu. Pada gambar dibawah, akarnya membuat kondisi, apakah X0 kurang dari atau sama dengan 5? Di tahap ini, kita sudah berhasil membuat garis vertical dan memisahkan setiap area untuk memiliki 2 label, namun masih belum benar pemisahan ini.
Kita perkecil lagi areanya menggunakan garis horizontal.
Keterangan:
- Kotak paling atas disebut Root Node atau cabang akar merupakan Cabang Teratas dari pohon. Node itu yang menerima input dari data baru untuk di prediksi, kemudian memperluas lagi cabangnya untuk di validasi dengan node lainnya.
- Kotak biru dua setelah Root Node dinamakan Internal Node atau cabang internal. Mereka hanya menerima 1 input dan memperluas lagi ke cabang lain minimal 2.
- Bentuk segitiga di akhir dinamakan Terminal Node atau Leaf Node atau Cabang Daun. Merupakan cabang paling akhir yang menghasilkan prediksi dari model Decision Tree.
C. K-Nearest Neighbors
K-Nearest Neighbors (KNN) merupakan algoritma Supervised Machine Learning yang digunakan untuk klasifikasi dan regresi. Umum digunakan untuk klasifikasi.
KNN bekerja saat melakukan klasifikasi terhadap data baru dengan memperhatikan tetangga terdekatnya. Lalu KNN menghitung berapa banyak label atau nilai target dari tetangga-tetangga terdekatnya, label yang paling banyak dan dekat dengan data baru maka data baru akan diklasifikasikan terhadap label tersebut.
Pada huruf pertama KNN, terdapat huruf K tunggal, apa maksudnya? Nilai K merupakan banyaknya tetangga terdekat yang ingin diperhatikan. Nilai itu ditentukan manual oleh kita.
KNN tidak melakukan pelatihan, hanya menyimpan histori dan letak titik data latih. Saat tiba melakukan proses klasifikasi / prediksi, maka saat itulah KNN mulai melakukan perhitungan.
Lihatlah pada titik data hitam diatas, itu merupakan data baru yang harus KNN coba klasifikasikan/prediksi. Berdasarkan nilai K yang kita berikan, KNN mencari jarak dari titik data hitam ke 2, 3, atau 4 titik data latih (training data) terdekat. Kita perlu menentukan nilai K yang paling optimal, jika tidak, bisa kalian lihat pada nilai K = 2 dan 4, data hitam tidak dapat diklasifikasikan dengan benar (bingung memilih). Namun berbeda dengan K = 3, titik hitam tersebut diklasifikasikan bersama dengan titik data oren, karena mayoritas titik paling terdekat adalah warna oren.
Untuk mencari jarak titik data hitam dengan titik yang paling terdekat dapat dihitung menggunakan Minkowski Distance, Manhattan Distance, Euclidean Distance, Cosine Distance, Jaccard Distance, Hamming Distance. Pada contoh plot data sebelumnya menggunakan Euclidean Distance.
Kalian bisa klik disini untuk mengetahui cara membaca titik koordinat.
Berikut beberapa hal yang perlu diperhatikan sebelum menggunakan KNN:
- Nilai K yang optimal, gunakanlah bantuan Elbow Method atau metode lainnya.
- Data tidak seimbang bisa menyebabkan kesalahan, misalkan jika plot data di gambar sebelumnya lebih banyak oren, maka prediksi KNN akan lebih condong ke titik data oren, dan tidak terhadap data hijau.
- Sensitif outlier, karena KNN mencari tetangga terdekat menggunakan jarak, sehingga outlier bisa mengganggu prediksi model.
D. Naïve Bayes
Naïve Bayes merupakan algoritma Supervised Machine Learning. Hanya digunakan untuk klasifikasi, dan juga untuk features atau kolom yang tidak memiki keterkaitan dengan kolom lainnya. Maksudnya tidak keterkaitan seperti pelemparan dadu, pelemparan dadu pertama tidak akan mempengaruhi kemunculan dadu kedua begitupun seterusnya, mereka saling independen.
Naïve Bayes bekerja menggunakan konsep peluang. Mari kita bahas dulu hal tersebut:
Disini Naïve Bayes ingin memprediksi kolom Flu berdasarkan keadaan seseorang yaitu menggigil, pilek, pusing dan demam. Dalam penulisan matematis untuk prediksi dengan Naïve Bayes dalam kasus tabel seperti di gambar sebelumnya adalah P(Flu | Menggigil, Pusing, Pilek, Demam) Selain itu Naïve Bayes juga mencari P(Tidak Flu | Menggigil, Pusing, Pilek, Demam). Nilai peluang yang paling besar maka menjadi jawaban prediksi.
Dari tabel sebelumnya, kita perlu mencari dulu atribut-atribut peluang penting untuk prediksi.
Setelah kita mendapatkan atributnya, model kita telah siap menerima data input baru. Mari kita coba dengan input dibawah ini.
Kenapa Naïve Bayes memilih jawaban tersebut? Mari kita selidiki.
Sekarang kita cari peluang tidak terjadinya Flu.
Kita mendapatkan peluang terjadinya Flu lebih sedikit daripada peluang tidak terjadinya Flu. Maka Naïve Bayes memilih Tidak Flu.
Sekarang kalian pasti memiliki pertanyaan, kenapa 1 dikurang 0.3, 1 dikurang 0.3 dan lain-lain. Anggap saja misalkan kalian melempar sebuah koin, dengan peluang munculnya sisi Angka dan sisi Gambar. Dimana peluang munculnya sisi Angka adalah ½ atau 0.5, maka sisa dari nilai peluang tersebut adalah 1–½ atau 1–0.5 miliknya sisi Gambar.
E. K-Means
K-Means merupakan algoritma Unsupervised Machine Learning, biasa digunakan untuk Clustering atau Pengelompokkan data. Tujuan K-Means adalah mencari group dalam kumpulan data, banyaknya group ditentukan oleh nilai K. Setiap titik data di berikan label berdasarkan titik centroid terdekat.
Titik centroid adalah titik yang menjadi pusat dari kelompok data. Biasanya terletak ditengah-tengah kumpulan data. Titik data kotak gambar atas adalah centroid.
Jangan disalah artikan dulu, centroid di gambar atas itu tidak langsung menemukan titik tengahnya kumpulan data. Dibutuhkan beberapa iterasi / proses perulangan sehingga centroid bisa menemukan pusat kelompok data yang pas. Untuk memperpendek panjangnya artikel ini, saya langsung menaruh titik centroidnya di pusat kelompok data.
Untuk menemukan nilai K yang optimal, sama seperti KNN, K-Means bisa menggunakan Elbow Method. Kita lihat gambar yang dikiri terlebih dahulu, gambar tersebut merupakan penjumlahan ragam/variance setiap kelompok data berdasarkan titik centroid. Semakin besar ragam dari kelompok data, maka penyebaran kelompok data tersebut makin variatif.
Pada K=2, jumlah ragam dari kelompok data oren masih terlalu besar. Terlihat juga di gambar plot data, bahwa kelompok data oren masih bisa dipisahkan lagi menjadi 2. Lanjut K=3, ini merupakan nilai K yang paling optimal, ragam setiap kelompok data saat dijumlahkan lumayan seimbang. Namun K=4 juga kira-kira seimbang, mengapa kita tetap memilih K=3?
Jika dilihat dari plot data sebelah kanan WCSS (Within Cluster Sum of Squares), perubahan antar titik data dari K=1 sampai K=3, selalu menurun jauh. Tapi ketika sudah mencapai K=4 dan K=5, perubahannya menurun pelan-pelan. Nah Elbow Method ini memilih K=3 karena perubahan setelah nilai 3 menurun secara pelan-pelan.
Sekarang anggaplah setiap kelompok data itu label. Berarti plot data di gambar sebelumnya memiliki 3 label diantaranya: Kelompok oren, kelompok hijau dan kelompok kuning.
Sekarang coba tebak, kemana titik data baru (titik hitam) itu akan di kelompokkan? Yap betul, ke kelompok data berwarna hijau, karena titik centroid hijau paling dekat dengan titik data baru tersebut.
Dalam dunia nyata ini bisa digunakan untuk Pengelompokkan Customer, kita bisa tau kategori-kategori pelanggan kita ini seperti apa, sehingga tim marketing bisa menargetkan pasar ke pelanggan tertentu. Silahkan klik disini untuk melihat implementasi di sektor lainnya.
Referensi
https://www.fromthegenesis.com/pros-and-cons-of-k-nearest-neighbors/
https://www.researchgate.net/post/How_can_I_define_the_SVM_parameters_Cost_and_gamma
