Algoritma ID3 (Iterative Dichotomiser 3) : Pengertian dan Contoh Studi Kasus

Assalamualaikum Warahmatullahi Wabarokatuh.

Halo teman-teman, kali ini kita akan mengulas sedikit tentang salah satu metode sistem cerdas yaitu algoritma ID3. Ketika teman-teman membaca, mungkin sekilas terlihat rumit, namun percayalah bahwa semua terasa gampang ketika sudah dipahami.

Yuk mulai belajar! 

Oh iya, jangan lupa untuk berdo'a terlebih dahulu ya.

1. Pengertian ID3

Algoritma ID3 merupakan algoritma yang dipergunakan untuk membangun sebuah decision tree atau pohon keputusan. Algoritma ini ditemukan oleh J. Ross Quinlan (1979), dengan memanfaatkan Teori Informasi atau Information Theory milik Shanon. ID3 sendiri merupakan singkatan dari Iterative Dichotomiser 3.

2. Langkah-langkah konstruksi pohon keputusan dengan algoritma ID3 

Adapun langkah-langkah dalam konstruksi pohon keputusan adalah sebagai berikut : 

1. Pohon dimulai dengan sebuah simpul yang mereperesentasikan sampel data pelatihan yaitu dengan membuat simpul akar. 
2. Jika semua sampel berada dalam kelas yang sama, maka simpul ini menjadi daun dan dilabeli menjadi kelas. Jika tidak, information gain akan digunakan untuk memilih atribut terbaik dalam memisahkan data sampel menjadi kelas-kelas individu.
3. Cabang akan dibuat untuk setiap nilai pada atribut dan data sampel akan dipartisi lagi.
4. Algoritma ini menggunakan proses rekursif untuk membentuk pohon keputusan pada setiap data partisi. Jika sebuah atribut sduah digunakan disebuah simpul, maka atribut ini tidak akan digunakan lagi di simpul anak-anaknya.
5. Proses ini berhenti jika dicapai kondisi seperti berikut : a) Semua sampel pada simpul berada di dalam satu kelas. b) Tidak ada atribut lainnya yang dapat digunakan untuk mempartisi sampel lebih lanjut. Dalam hal ini akan diterapkan suara terbanyak. Ini berarti mengubah sebuah simpul menjadi daun dan melabelinya dengan kelas pada suara terbanyak.

3. Entropy dan Gain

Algoritma pada metode ini menggunakan konsep dari entropi. Konsep Entropi yang digunakan untuk mengukur “seberapa informatifnya” sebuah node (yang biasanya disebut seberapa baiknya).

Catatan: 

• Entropi(S) = 0, jika semua contoh pada S berada dalam kelas yang sama. 
• Entroiy(S) = 1, jika jumlah contoh positif dan jumlah contoh negatif dalam S adalah sama. 
• 0 < Entropi(S) < 1, jika jumlah contoh positif dan negatif dalam S tidak sama. 

a. Rumus Entropy

Dimana: 

S adalah himpunan (dataset) kasus 

n adalah banyaknya partisi S 

pi adalah probabilitas yang di dapat dari Jumlah(Ya) dibagi Total Kasus. 

Setelah mendapat nilai entropi, pemilihan atribut dilakukan dengan nilai information gain terbesar.

b. Rumus Gain

Dimana: 

S = ruang (data) sample yang digunakan untuk training. 

A = atribut. 

|Si| = jumlah sample untuk nilai V. 

|S| = jumlah seluruh sample data. 

Entropi(Si) = entropy untuk sample-sample yang memiliki nilai i 

 

Nah bagaimana teman-teman? Teori diatas tentunya akan susah dipahami jika kita belum mencobanya. Berikut ini adalah contoh studi kasus dan perhitungan menggunakan ID3.

4. Studi Kasus

Data yang telah ada pada Tabel dibawah akan digunakan untuk membentuk pohon keputusan dimana memiliki atribut-atribut seperti Cuaca, Suhu, Kelembaban, dan Berangin. Setiap atribut memiliki nilai. Sedangkan kelasnya ada pada kolom Main yaitu kelas “Tidak” dan kelas “Ya”. Kemudian data tersebut dianalisis; dataset tersebut memiliki 14 kasus yang terdiri 10 “Ya” dan 4 “Tidak” pada kolom Main. 

Penyelesaian:

a. Menghitung Entropy(S) dan Gain Seluruh Atribut

Hitunglah entropi dengan rumus seperti diatas. Jika rumus diatas terkesan rumit, mari kita sederhanakan cara membacanya menjadi seperti ini,

Entropy(S) = (-(Instance Positif/Jumlah Seluruh Instance) x log2(Instance Positif/Jumlah Seluruh Instance) + -(Instance Negatif/Jumlah Seluruh Instance) x log2(Instance Negatif/Jumlah Seluruh Instance))

• Intance Positif adalah jumlah data "Ya" pada tabel data training yang sedang dihitung, yaitu 10
• Intance Negatif adalah jumlah data "Tidak" pada tabel data training yang sedang dihitung, yaitu 4
• Jumlah Instance adalah jumlah seluruh data pada tabel data training yang sedang dihitung, yaitu 14

Kenapa saya tuliskan pada tabel data training yang sedang dihitung? Karena setelah kita menemukan entropy keseluruhan dan menemukan gain terbesar pada perhitungan pertama, selanjutnya kita juga akan mencari entropy lainnya seiring proses pembentukan pohon keputusan, termasuk juga entropy dari setiap atribut seperti Cuaca, Kelembaban dan lainnya.

Rumus sederhana diatas merupakan rumus yang akan kita gunakan dalam perhitungan baik manual maupun menggunakan microsoft excel. Namun teman-teman perlu menyesuaikan misalnya x menjadi * sebagai operator perkalian dalam Excel. 

Entropi (S) = (-(10/14) x log2 (10/14) + (-(4/14) x log2 (4/14)) = 0.863120569

Nah baris diatas contoh penghitungan manual dari Entropy(S) atau entropy keseluruhan. Namun bagaimana untuk menghitung Entropy setiap atribut? Buatlah tabel pada microsoft Excel seperti dibawah ini.

Gambar 1. Menghitung Entropy dan Gain untuk mencari node awal

Nah bagaimana? Hasil Entropy(S) manual dan pada Excel sama bukan? yaitu 0.863120569

Lalu sebagai contoh, untuk rumus dari Entropy pada Cuaca Berawan bagaimana? Jawabannya adalah sama dengan rumus sederhana yang kita tulis tadi. Jadi instance positifnya = 4, instance negatif = 0, dan jumlah instance berawan = 4. Mudah bukan? Tentunya akan lebih mudah ketika teman-teman melakukan perhitungan menggunakan Microsoft Excel selama penulisan rumusnya benar.

Kemudian untuk rumus pencarian Gain, mari kita baca rumus diatas. Jika terlihat rumit, berikut adalah cara membacanya,

Gain(S,Cuaca) = Entropy(S) - ((Jumlah instance Berawan/Jumlah instance)*Entropy(Berawan) + (Jumlah instance Hujan/Jumlah instance)*Entropy(Hujan) + (Jumlah instance Cerah/Jumlah instance)*Entropy(Cerah))

Gain(S,Cuaca) = 0.863120569 – ((4/14) x 0 + (5/14) x 0.721928095 + (5/14) x 0.970950594) = 0.258521037  

Rumus diatas adalah contoh penghitungan gain untuk cuaca. Hitung pula Gain (Suhu), Gain (Kelembaban), dan Gain (Berangin) dengan rumus yang sama (namun menyesuaikan).

Pada tabel perhitungan diatas, kita sudah menemukan gain terbesar yaitu pada atribut Kelembaban.  Karena nilai gain terbesar adalah Gain (Kelembaban), maka atribut “Kelembaban” menjadi node akar (root node). Kemudian pada “Kelembaban” normal, memiliki 7 kasus dan semuanya memiliki jawaban Ya (Sum(Total) / Sum(Ya) = 7/7 = 1). Dengan demikian “Kelembaban” normal menjadi daun atau leaf.

Gambar 2. Node awal

b. Mencari Node Kedua Berdasarkan Node Pertama

Berdasarkan pembentukan pohon keputusan node 1 (root node), Node 1.1 akan dianalisis lebih lanjut. Untuk mempermudah, Tabel dibawah difilter, dengan mengambil data yang memiliki “Kelembaban” = Tinggi. 

Tabel 2. Filter berdasarkan kelembaban = tinggi

Gambar 3. Menghitung Entropy dan Gain untuk mencari node kedua

Gain tertinggi yang didapat ada pada atribut “Cuaca”, dan Nilai yang dijadikan daun atau leaf adalah Berawan dan Cerah. Hal ini dikarenakan pada Cuaca Berawan, dari 2 data training semuanya bernilai "Ya". Sedangkan pada cuaca Cerah, dari 3 data training semuanya bernilai "Tidak". Jadi tidak perlu dilakukan perhitungan lanjutan pada 2 nilai tersebut. Jika dievualisasi maka pohon keputusan tampak seperti Gambar dibawah. 

Gambar 4. Node kedua

c. Mencari Node Ketiga Berdasarkan Node Kedua

Lakukan lagi langkah-langkah yang sama seperti sebelumnya hingga semua node berbentuk node leaf. Karena Hujan belum menjadi leaf, maka kita lakukan perhitungan dengan memfilter tabel berdasarkan "Cuaca"=Hujan.

Tabel 3. Filter berdasarkan kelembaban = tinggi, dan cuaca = hujan

Gambar 5. Menghitung Entropy dan Gain untuk mencari node ketiga

Sekarang kita perhatikan, rupanya gain terbesar terletak pada atribut "Berangin". Kemudian pada atribut tersebut, nilai "Salah" sudah menjadi leaf karena dari 1 data memilih "Ya" dan "Tidak" = 0. Selanjutnya pada "Benar"  juga sudah menjadi leaf karena dari 1 data memilih "Tidak" dan "Ya" = 0. Maka hasil pohon keputusan akhir adalah seperti dibawah ini.

Gambar 5. Hasil tree decision akhir dari studi kasus ID3

Kurang lebih seperti itulah cara membuat pohon keputusan dengan algoritma ID3. Cukup mudah bukan? Selamat Belajar dan Semoga Bermanfaat. Mohon maaf jika ada kekeliruan atau kekurangan dalam artikel ini.

Jika ada pertanyaan, tulis di kolom komentar ya!

See you!

Wassalamualaikum Warahmatullahi Wabarokatuh.

DFS (Depth First Search) : Pengertian, Kekurangan, Kelebihan, dan Contohnya

 

Assalamualaikum Warahmatullahi Wabrokatuh.

Halo teman-teman, bagaimana kabarnya hari ini? Semoga kalian semua berada dalam keadaan sehat walafiyat. Tetap semangat, selalu jaga kesehatan, dan jaga ibadah.

Kali ini kita akan membahas kelanjutan dari materi sebelumnya yaitu BFS. Dan sekarang kita akan belajar mengenai algoritma DFS (Depth First Search). Berikut ini adalah beberapa uraian mengenai algoritma DFS.

DFS (Depth First Search) : Pengertian, Kekurangan, Kelebihan, dan Contohnya

1. Pengertian DFS

    Algoritma Depth First Search adalah algoritma pencarian mendalam yang dimulai dari node awal dilanjutkan dengan hanya mengunjungi node anak paling kiri pada tingkat selanjutnya. 

Gambar 1. DFS dan BFS

   

Cara kerja algoritma Depth First Search yaitu masukan masukan node akar kedalam sebuah tumpukan. Kemudian ambil simpul pertama pada level paling atas, jika simpul merupakan solusi pencarian selesai dan hasil dikembalikan. Jika simpul bukan merupakan solusi, masukan seluruh simpul yang bertetangga dengan simpul tersebut ke dalam tumpukan. Apabila semua simpul sudah dicek dan antrean kosong, pencarian selesai dengan mengembalikan hasil solusi tidak ditemukan. Pencarian diulang dari simpul awal antrean.

2. Kelebihan dan Kekurangan DFS

Kelebihan DFS	Kekurangan DFS
Membutuhkan memori yang relatif kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan.	Jika pohon yang dibangkitkan mempunyai level dalam (tak terhingga), maka tidak ada jaminan untuk menemukan solusi (Tidak Complete).
Secara kebetulan, metode DFS akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan.	Jika terdapat lebih dari 1 solusi yang sama tetapi berada pada level yang berbeda, maka pada DFS tidak ada jaminan untuk menemukan solusi yang paling baik (Tidak Optimal).

3. Contoh Penerapan BFS dalam Studi Kasus

Pencarian jarak terdekat Arad-Bucharest. Berikut ini adalah Peta Rumania.

Gambar 2. Peta Rumania

      Dalam menyelesaikan kasus diatas, kita perlu membuat peta Rumania menjadi gambaran graph yang lebih sederhana. Berikut ini adalah gambaran peta Rumania dalam bentuk graph sederhana:

Gambar 3. Graph Peta Rumania

Penyelesaian dengan DFS:

        Algoritma Depth First Search adalah algoritma pencarian mendalam yang dimulai dari node awal dilanjutkan dengan hanya mengunjungi node anak paling kiri pada tingkat selanjutnya. Dari Gambar 2. Graph Arad-Bucharest, selanjutnya kita dapat membuat Tree untuk melakukan penyelesaian kasus dengan algoritma DFS. Berikut ini adalah gambar tree untuk DFS yang sedikit berbeda dengan tree yang digunakan pada BFS.

Gambar 4. Tree untuk DFS

        Pada tree, tidak semua kota saya tuliskan. Contohnya yaitu kota yang tersambung dari node S dan T secara lengkap. Hal itu dikarenakan target B sudah ditemukan di anak paling kiri, dan pencarian berhenti disana. Sehingga pohon tengah dan pohon kanan tidak akan dilewati. Berikut ini adalah gambaran penyelesaian pencarian kota Bucharest (B) menggunakan algoritma DFS.

Implementasi: Start (A), Goal (B)

Gambar 5. Pencarian Jarak dengan DFS

Penjelasan:

        Pencarian rute dengan DFS, yaitu dengan melakukan pencarian mendalam yang dimulai dari node awal, dilanjutkan dengan hanya mengunjungi node anak paling kiri pada tingkat selanjutnya. Pada tree diatas, rupanya target terletak di anak terdalam paling kiri. Sehingga didapatkan rute berdasarkan algoritma DFS yaitu A Z O S F R. 

       Dari hasil pencarian diatas, maka ditemukan jarak yang dipilih dari Arad ke Bucharest dengan menggunakan algoritma DFS adalah sebagai berikut:

Gambar 6. Hasil Pencarian

Path = A > Z > O > S > F > R
Path-cost = 75 + 71 + 151 + 99 + 211 = 607 KM

Kesimpulan:

    Pada kasus ini, algoritma BFS dengan path-cost 450 KM rupanya lebih efisien dari DFS yang memiliki path-cost 607 KM. Namun pada kasus lainnya, bisa saja algoritma DFS lebih efisien, hal itu tergantung dari kasus itu sendiri.

Itu tadi penjelasan seputar algoritma DFS dan contoh penyelesaian kasus yang pernah saya kerjakan dalam tugas kuliah, sebagai lanjutan postingan sebelumnya. 

Mohon maaf jika ada kekurangan dan kekeliruan. Semoga bermanfaat!

Wassalamualaikum Warahmatullahi Wabarokatuh.

BFS (Breadth First Search) : Pengertian, Kekurangan, Kelebihan, dan Contohnya

 

Assalamualaikum Warahmatullahi Wabrokatuh.

Halo teman-teman, bagaimana kabarnya hari ini? Semoga kalian semua berada dalam keadaan sehat walafiyat. Bagi yang sedang sakit, semangat yaa. Semoga Allah mengampuni dosa kalian lewat sakit itu. Semoga cepat sembuh.

Kali ini kita akan membahas tentang BFS (Breadth First Search). Berikut ini adalah beberapa uraian mengenai algoritma BFS.

BFS (Breadth First Search) : Pengertian, Kekurangan, Kelebihan, dan Contohnya

1. Pengertian BFS

    Algoritma Breadth First Search adalah algoritma pencarian melebar yang dilakukan dengan mengunjungi node pada level n terlebih dahulu sebelum mengunjungi node-node pada level n+1. Algoritma BFS berbeda dengan DFS. Hal itu dapat dilihat pada gambar dibawah ini. Untuk penjelasan algoritma DFS akan dijelaskan di postingan selanjutnya.

Gambar 1. DFS dan BFS

   

 Cara kerja algoritma Breadth First Search yaitu masukkan simpul ujung ke dalam sebuah antrean kemudian ambil simpul dari awal antrean. Lakukan pengecekan apakah simpul awal merupakan solusi. Jika simpul merupakan solusi pencarian selesai dan hasil dikembalikan. Jika simpul bukan merupakan solusi, masukan seluruh simpul yang bertetangga dengan simpul tersebut. Apabila semua simpul sudah dicek dan antrean kosong, pencarian selesai dengan mengembalikan hasil solusi tidak ditemukan. Pencarian diulang dari simpul awal antrean.

2. Kelebihan dan Kekurangan BFS

Kelebihan BFS	Kekurangan BFS
Tidak akan menemui jalan buntu.	Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam satu pohon.
Jika ada satu solusi, maka BFS akan menemukannya. Dan jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan.	Membutuhkan waktu yang cukup lama, karena akan menguji n level untuk mendapatkan solusi pada level ke-(n+1).

3. Contoh Penerapan BFS dalam Studi Kasus

Pencarian jarak terdekat Arad-Bucharest. Berikut ini adalah Peta Rumania.

Gambar 2. Peta Rumania

      Dalam menyelesaikan kasus diatas, kita perlu membuat peta Rumania menjadi gambaran graph yang lebih sederhana. Berikut ini adalah gambaran peta Rumania dalam bentuk graph sederhana:

Gambar 3. Graph Peta Rumania

Penyelesaian dengan BFS:

    Algoritma Breadth First Search adalah algoritma pencarian melebar yang dilakukan dengan mengunjungi node pada level n terlebih dahulu sebelum mengunjungi node-node pada level n+1. Dalam penyelesaian kasus diatas, kita dapat menggambarkan graph diatas ke dalam bentuk Tree. Node paling kiri dimulai dari jarak tetangga terdekat yaitu Z (75) lalu berurutan ke S dan T.

Gambar 4. Tree untuk BFS

Pada tree, tidak semua kota saya tuliskan. Contohnya yaitu kota D. Hal itu dikarenakan kota D tidak termasuk dalam perhitungan, dan berada di level 4. Berikut ini adalah gambaran penyelesaian pencarian kota Bucharest (B) menggunakan algoritma BFS.
Implementasi: Start (A), Goal (B)

Gambar 5. Pencarian Jarak dengan BFS

Penjelasan:

        Pencarian rute dengan BFS, yaitu dengan mengecek setiap level mulai dari level n atau level 1, baru dilanjutkan ke level n+1 hingga target atau goalnya ditemukan. Meski demikian, yang dihitung pada akhirnya bukanlah jarak yang ditempuh selama mencari target, namun rute yang dipilih adalah rute yang terhubung ke target (yaitu A S F B). Oleh karena itu, BFS membutuhkan banyak memori untuk menyimpan semua simpul dalam satu pohon dan ini menjadi salah satu kekurangan BFS.

        Dari hasil pencarian diatas, maka ditemukan jarak yang dipilih dari Arad ke Bucharest dengan menggunakan algoritma BFS adalah sebagai berikut:

Gambar 6. Hasil Pencarian

Path = A > S > F >  B
Path-cost = 140 + 99 + 211 = 450 KM

Itu tadi penjelasan seputar algoritma BFS dan contoh penyelesaian kasus yang pernah saya kerjakan dalam tugas kuliah. Mohon maaf jika ada kekurangan dan kekeliruan. Semoga bermanfaat!

Wassalamualaikum Warahmatullahi Wabarokatuh.