Decision Tree Learning: Handling Missing Values

Dalam tulisan ini gw akan coba terangkan bagaimana algoritma C4.5 memperlakukan missing value. Dalam data di dunia nyata, dimana kesempurnaan merupakan sebuah keniscayaan, data yang sempurna merupakan sebuah mitos. Sering kali kita akan menemukan data yang tidak lengkap dan terdapat nilai yang kosong. Sedangkan dalam membentuk sebuah pohon keputusan, algoritma ID3 sangat bergantung pada kualitas data, algoritma ID3 tidak mampu menangani data yang tidak lengkap atau lebih dikenal dengan missing value. Algoritma C4.5 ini merupakan perbaikan dari ID3, salah satunya mampu menangani missing value.

Sangat tidak elok kalo kita meniadakan keberadaan missing value, dibiarkan saja begitu. Apalagi dibuang. Missing value bisa saja membawa informasi penting yang dapat membangun pattern pohon keputusan. Sejatinya yang menjadi pertanyaan terkait missing value dalam pohon keputusan ialah:

  1. Seperti sebelumnya gw udah jelasin kalo pemilihan atribut saat splitting dilakukan berdasarkan gain ratio atau entropi yang ujung-ujungnya melibatkan frekuensi kemunculan suatu data. Lalu jika ada dua atribut dengan jumlah missing value yang berbeda, bagaimana pengaruhnya pada pemilihan atribut saat splitting? Perubahan apa yang sebaiknya dilakukan untuk mengakomodir missing value ini?
  2. Setelah node dipilih, dan jika terdapat instances dengan missing value pada node tersebut, maka instances tersebut mau dimasukin ke branch mana? Instances tersebut kan tidak memiliki nilai, sedangkan gak ada branch bernama ‘missing values
  3. Ketika pohon keputusan digunakan untuk memprediksi atau mengklasifikasi suatu data baru, bagaimana jika terdapat missing value pada suatu decision node? Mirip pertanyaan sebelumnya, kan gak ada branch khusus untuk ‘missing values

Gw akan memberikan contoh menggunakan dataset yang udah gw pake pada tulisan-tulisan sebelumnya. Dari 14 instances terdapat sebuah instance yang memiliki missing value, yakni pada atribut Cuaca.

Tabel 1. Dataset

Cuaca Suhu Kelembapan Berawan Main
 Cerah  85  85  Tidak  Tidak
 Cerah  80  90  Ya  Tidak
 Mendung  83  86  Tidak  Ya
 Hujan  70  96  Tidak  Ya
 Hujan  68  80  Tidak  Ya
 Hujan  65  70  Ya  Tidak
 Mendung  64  65  Ya  Ya
 Cerah  72  95  Tidak  Tidak
 Cerah  69  70  Tidak  Ya
 Hujan  75  80  Tidak  Ya
 Cerah  75  70  Ya  Ya
 ?  72  90  Ya  Ya
 Mendung  81  75  Tidak  Ya
 Hujan  71  91  Ya  Tidak

Penghitungan Information Gain

$$E(\text{Parent Node})=E(8, 5)=-\frac{8}{13}log_2\frac{8}{13}-\frac{5}{13}log_2\frac{5}{13}=0.961$$

$$E(\text{Cerah})=E(2, 3)=0.971$$

$$E(\text{Mendung})=E(3, 0)=0$$

$$E(\text{Hujan})=E(3, 2)=0.971$$

$$E(\text{Cuaca})=\frac{5}{13} \times 0.971 + \frac{3}{13} \times 0 + \frac{5}{13} \times 0.971=0.747$$

$$Gain(\text{Cuaca})=\frac{13}{14} \times (0.961-0.747)=0.199$$

Information gain ini lebih kecil dari information gain jika tidak ada missing value. Selanjutnya missing value juga mempengaruhi split information. Dengan adanya missing value, kita diibaratkan membuat sebuah kategori baru.

$$SplitInfo(\text{Cuaca})=E(5, 3, 5, 1)=-\frac{5}{14}log_2\frac{5}{14}-\frac{3}{14}log_2\frac{3}{14}-\frac{5}{14}log_2\frac{5}{14}-\frac{1}{14}log_2\frac{1}{14}=1.809$$

Split information ini lebih besar dari split information jika tidak ada missing value. Selanjutnya kita hitung gain ratio untuk atribut Cuaca:

$$GainRatio(Cuaca)=\frac{Gain(Cuaca)}{SplitInfo(Cuaca)}=\frac{0.199}{1.809}$$

Yap, secara otomatis dengan information gain yang berkurang dan split information yang meningkat akan membuat gain ratio lebih kecil jika dibandingkan tidak ada missing value. Inilah jawaban untuk pertanyaan no. 1 diatas.

Membangun Subtree

Asumsikan setelah perhitungan gain ratio untuk semua atribut, yang menjadi root node ialah atribut Cuaca. Selanjutnya dari root node ini akan terbentuk 3 cabang, Cerah, Mendung, dan Hujan. 14 instances tersebut dibagi berdasarkan nilai pada atribut Cuaca, sehingga ada 5 instances ke cabang Cerah, 3 instances ke cabang Mendung, dan 5 instances ke cabang Hujan. 1 instance yang memiliki missing value kemana? 1 instance ini kita bagi sama rata ke semua cabang secara proporsional. Artinya ada 5/13 instance ke cabang Cerah, 3/13 instance ke cabang Mendung, dan 5/13 instance ke cabang Hujan. Jika ada 2 instance yang memiliki missing value (dataset terdiri 15 instances), maka proporsinya menjadi 10/13, 6/13, 10/13. Begitu seterusnya.

Tabel 2. Subset untuk branch Cuaca

Cuaca Suhu Kelembapan Berawan Main  Bobot
 Cerah  85  85  Tidak  Tidak  1
 Cerah  80  90  Ya  Tidak  1
 Cerah  72  95  Tidak  Tidak  1
 Cerah  69  70  Tidak  Ya  1
 Cerah  75  70  Ya  Ya  1
 ?  72  90  Ya  Ya  5/13

Tabel 3. Subset untuk branch Mendung

Cuaca Suhu Kelembapan Berawan Main Bobot
 Mendung  83  86  Tidak  Ya  1
 Mendung  64  65  Ya  Ya  1
 Mendung  81  75  Tidak  Ya  1
 ?  72  90  Ya  Ya  3/13

Tabel 4. Subset untuk branch Hujan

Cuaca Suhu Kelembapan Berawan Main Bobot
 Hujan  70  96  Tidak  Ya  1
 Hujan  68  80  Tidak  Ya  1
 Hujan  65  70  Ya  Tidak  1
 Hujan  75  80  Tidak  Ya  1
 Hujan  71  91  Ya  Tidak  1
 ?  72  90  Ya  Ya  5/13

Klasifikasi Data Baru

Gw coba lanjutkan membangun subtree untuk branch Cuaca = Cerah. Setelah dihitung gain ratio nya maka ditetapkanlah kelembapan sebagai node, dengan distribusi subset sebagai berikut:

Tabel 5. Subset untuk Kelembpan <= 75

Cuaca Suhu Kelembapan Berawan Main  Bobot
 Cerah  69  70  Tidak  Ya  1
 Cerah  75  70  Ya  Ya  1

Tabel 6. Subset untuk Kelembapan > 75

Cuaca Suhu Kelembapan Berawan Main  Bobot
 Cerah  85  85  Tidak  Tidak  1
 Cerah  80  90  Ya  Tidak  1
 Cerah  72  95  Tidak  Tidak  1
 ?  72  90  Ya  Ya  5/13

Terlihat bahwa pada subset Kelembapan > 75 leaf node menjadi tidak murni lagi. Ini juga terjadi pada cabang Cuaca = Hujan. Mungkin jika bobot missing value-nya  sangat kecil hal ini tidak akan terlalu masalah, namun jika bobotnya sudah besar apalagi lebih besar dari yang selain missing value, ini akan menimbulkan masalah dalam mengklasifikasi suatu data baru. Oleh karena itu kita perlu menangani hal ini.

Suatu contoh misalnya kita punya sebuah data baru, Cuaca=Cerah, Suhu=70, Kelembapan=?, dan Berawan=Tidak. Apa output yang dihasilkan dari pohon keputusan tersebut?

Oke, karena Cuaca=Cerah, maka selanjutnya kita tentukan dari nilai Kelembapan. Ups, tapi nilai Kelembapan merupakan missing value. Terdapat dua kemungkinan kalau begitu:

  • Jika Kelembapan <= 75, maka Main=Ya
  • Jika Kelembapan > 75, maka probabilitas Main=Ya adalah (5/13)/total = 12% dan probabilitas Main=Tidak adalah 3/Total = 88%.

Note: 5/13 = 0.4

Karena kita tidak tahu berapa nilai Kelembapan, maka kita gunakan weighting untuk menentukan persentase output. Total ada 5.4 instances dalam node ini yang terbagi menjadi dua cabang, masing-masing berjumlah 2 dan 3.4 instances. Probabilitas suatu data baru memiliki Kelembapan <= 75 ialah 2/5.4 sedangkan probabilitas suatu data baru memiliki Kelembapan > 75 ialah 3.4/5.4. Namun karena node ini tidak murni maka probabilitas akhirnya ialah:

Main=Ya : $\frac{2}{5.4} \times 100\text{%} + \frac{3.4}{5.4} \times 12\text{%}=44\text{%}$

Main=Tidak: $\frac{3.4}{5.4} \times 88\text{%} = 56\text{%}$

One thought on “Decision Tree Learning: Handling Missing Values

Leave a Reply

Your email address will not be published. Required fields are marked *