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{%}$

Decision Tree Learning: Avoiding Overfitting

Salah satu kelemahan dari metode divide-and-conquer ialah tidak adanya cara menghindari overfitting. Pohon keputusan yang dihasilkan cenderung terkesan ‘sangat rindang’ dan mengandung struktur yang tidak diperlukan sehingga dapat menyebabkan pohon keputusan tidak dapat melakukan generalisasi dengan baik. Dampaknya akan mengurangi akurasi prediksi atau klasifikasi data baru. Cara yang dilakukan untuk mengatasi hal ini ialah dengan pruning. Pruning bisa diartikan sebagai ‘memangkas pohon’, membuat pohon keputusan menjadi lebih simpel.

Terdapat dua cara pruning, yaitu postpruning dan prepruning. Kalo postpruning, pemangkasan dilakukan setelah pohon keputusan jadi dengan mengganti subtree menjadi leaf node. Sedangkan kalo prepruning, pemangkasan dilakukan selama pohon keputusan dikonstruksi, kapan harus berhenti dan tidak melanjutkan pembentukan subtree. Masing-masing memiliki kelebihan dan kekurangan.

Prepruning

Keuntungannya ialah lebih hemat waktu. Kita tidak membuang-buang waktu untuk membuat subtree yang pada akhirnya tidak digunakan (setelah dilakukan simplifikasi). Prepruning dilakukan dengan melakukan statistical significance test pada setiap splitting. Jika hasil tesnya dibawah threshold artinya konstruksi pohon keputusan berhenti. Menentukan threshold ini yang tidak mudah, karena jika terlalu tinggi maka pohon keputusan yang dihasilkan terlalu simple dan prematur (underfit) dan jika threshold terlalu rendah maka simplifikasinya terlalu kecil (overfit). Umumnya statistical significant test yang diterapkan ialah menggunakan chi-squared test.

Postpruning

Kebanyakan algoritma decision tree menerapkan postpruning ini. Walaupun membutuhkan waktu yang lebih banyak, postpruning menghasilkan simplified tree yang lebih baik akurasinya. Ada dua cara dalam melakukan postpruning ini. Pertama, subtree replacement. Ide dari subtree replacement ialah mengganti subtree dengan sebuah leaf node. Replacement berjalan mulai dari node yang paling bawah atau yang memiliki leaf node hingga root node. Pohon keputusan dibawah ini adalah contohnya. Konteksnya ialah dalam negosiasi kontrak antara pekerja dan perusahaan. Berdasarkan kondisi tertentu (kenaikan gaji, tunjangan kesehatan, jam kerja, dsb) apakah suatu kontrak bakal diterima kedua pihak atau ada satu pihak yang tidak menerima.

Selain subtree replacement, cara kedua untuk melakukan postpruning ialah subtree raising. Pada subtree raising, sebuah node akan dibuang dan digantikan dengan salah satu cabang node tersebut. Contohnya pada pohon keputusan dibawah ini. Terlihat bahwa setelah pruning dilakukan, node B sudah tidak ada lagi dan telah digantikan dengan salah satu cabangnya yakni node C. Dengan kata lain, node C naik satu level. Namun setelah node C naik level, kita perlu mengklasifikasi ulang data yang ada pada leaf node 4 dan 5. Jadi leaf node 1, 2, dan 3 setelah pruning akan mendapat anggota baru yang merupakan peralihan dari leaf node 4 dan 5, tergantung hasil klasifikasi ulang.

Biasanya subtree raising dilakukan jika salah satu cabang dari sebuah node memiliki instances jauh lebih banyak dibandingkan jumlah instances pada cabang yang lain. Pada contoh diatas, node C memiliki jumlah instances yang jauh lebih banyak dibandingkan leaf node 4 dan 5. Subtree raising lebih jarang digunakan dibandingkan subtree replacement.

Lalu bagaimana menentukan apakah suatu node lebih baik dipangkas atau tetap begitu saja?

Ada dua cara yang dapat digunakan. (1) yang melibatkan validation set dan training set, (2) hanya melibatkan training set. Training set ialah data yang kita gunakan untuk membuat pohon keputusan. Sedangkan validation set tidak dilibatkan dalam pembentukan pohon keputusan, namun digunakan untuk menghitung akurasi pohon keputusan tersebut. Kedua cara ini pada prinsipnya hampir sama, yakni dengan membandingkan error yang dihasilkan sebelum pruning dan setelah pruning. Jika error setelah pruning lebih kecil dari sebelum pruning maka pruning dilanjutkan, begitu sebaliknya.

Jika kita menggunakan cara (1) maka ada dua teknik yang dapat digunakan, yakni reduced-error pruning dan cost-complexity pruning. Reduced-error pruning hanya mengukur error akibat pruning semata-mata berdasarkan validation set, berapa error yang dihasilkan oleh validation set sebelum dan setelah pruning. Kekurangan dari teknik ini ialah pohon keputusan yang terbentuk dihasilkan dari training set yang lebih sedikit. Jadi teknik ini akan lebih bermanfaat jika jumlah data yang kita punya cukup banyak.

Berbeda dengan reduced-error pruning, pada cost-complexity pruning proses pruning ditentukan dari akurasi pohon keputusan dan kompleksitas pohon keputusan tersebut. Disini, banyaknya leaf node dihitung sebagai cost. Pohon keputusan setelah pruning ialah pohon keputusan yang memiliki cost akibat error dan cost akibat kompleksitas pohon keputusan paling rendah. Cost-complexity pruning ini yang diterapkan dalam algoritma CART.

Kemudian jika kita menggunakan cara (2) kita dapat menggunakan pendekatan statistik untuk mengestimasi error sebelum dan setelah pruning. Cara ini yang diterapkan dalam algoritma C4.5. Penjelasan lebih lanjut mengenai pruning di algoritma C4.5 dapat dibaca disini.

Referensi

C4.5: Programs for Machine Learning

Data Mining: Practical Machine Learning Tools and Techniques

 

Decision Tree Learning: Constructing Decision Tree

Decision Tree Learning (DTL) merupakan salah satu metode dalam pembelajaran mesin untuk menyelesaikan masalah klasifikasi. Berbeda dengan regresi linear yang menggunakan persamaan garis linear sebagai cara memodelkan, DTL menggunakan representasi pohon keputusan (decision tree) untuk memodelkan suatu masalah. Sebagai outputnya DTL akan menghasilkan sekumpulan rules atau aturan yang digunakan untuk mengklasifikasi suatu data baru.

Sebagai contoh misalnya kita ingin mengetahui bagaimana resiko sakit jantung seseorang berdasarkan atribut Umur, Jenis Kelamin, Kebiasaan Diet (Baik/Buruk), dan Status Merokok(Perokok/Bukan Perokok). Yang kita inginkan ialah jika diberikan suatu data baru, kita dapat mengklasifikasi apakah orang tersebut masuk ke dalam kategori dengan resiko sakit jantung yang tinggi atau rendah. Gambar dibawah ini merupakan pohon keputusan untuk masalah tersebut.

Perhatikan bahwa semua atribut input akan menjadi node dalam pohon keputusan dengan jumlah branch sesuai dengan jumlah kategori tiap atribut. Atribut target (resiko sakit jantung) akan menjadi leaf node. Pertanyaan selanjutnya ialah bagaimana membuat pohon keputusan tersebut? Mengapa atribut Merokok yang menjadi root node? Mengapa atribut Jenis Kelamin tidak dilibatkan?

Divide-and-Conquer DTL

Untuk memberikan gambaran bagaimana proses konstruksi pohon keputusan, gw bakal pake dataset dibawah. Dengan dataset ini kita ingin memprediksi apakah suatu komunitas skateboard di Bandung akan menggelar latihan atau tidak berdasarkan data cuaca, suhu, kelembapan, dan kondisi awan.

Cuaca Suhu Kelembapan Berawan Main
 Cerah  Panas  Tinggi  Tidak  Tidak
 Cerah  Panas  Tinggi  Ya  Tidak
 Mendung  Panas  Tinggi  Tidak  Ya
 Hujan  Sejuk  Tinggi  Tidak  Ya
 Hujan  Dingin  Normal  Tidak  Ya
 Hujan  Dingin  Normal  Ya  Tidak
 Mendung  Dingin  Normal  Ya  Ya
 Cerah  Sejuk  Tinggi  Tidak  Tidak
 Cerah  Dingin  Normal  Tidak  Ya
 Hujan  Sejuk  Normal  Tidak  Ya
 Cerah  Sejuk  Normal  Ya  Ya
 Mendung  Sejuk  Tinggi  Ya  Ya
 Mendung  Panas  Normal  Tidak  Ya
 Hujan  Sejuk  Tinggi  Ya  Tidak

Secara umum, proses konstruksi pohon keputusan ialah sebagai berikut:

  • Pertama, pilih sebuah atribut yang akan menjadi node
  • Setelah itu buatlah sejumlah cabang berdasarkan kemungkinan nilai dari atribut tersebut. Hal ini juga akan membagi dataset menjadi beberapa bagian sesuai jumlah cabang.
  • Ulangi proses diatas secara rekursif sampai yang menjadi leaf node ialah nilai dari atribut target.

Proses ini disebut juga proses divideandconquer.

Lalu bagaimana menentukan atribut mana yang harus dipilih menjadi node terlebih dahulu?

Menentukan Root Node

Oke, gw kasih contoh lain dulu. Misalnya kita punya sebuah dataset yang memiliki 10 data dan terdiri dari 3 atribut input dan 1 atribut output. Kita ingin menentukan dari 3 atribut input tersebut atribut mana yang semestinya dipilih terlebih dahulu untuk menjadi node.

 A B C X
 A1  B1  C1  Ya
 A2  B1  C1  Tidak
 A2  B2  C1  Ya
A1  B2  C2  Tidak
 A2  B2  C2  Tidak
 A2  B3  C1  Ya
 A1  B1  C2  Tidak
 A2  B3  C1  Ya
 A1  B3  C1  Ya
 A2  B1  C2  Tidak

Sekarang menurut lo atribut mana yang seharusnya pilihan pertama untuk jadi root node, A, B, atau C?

Harusnya, lo bisa pilih dengan hanya melihat atau menghitung jumlah Ya dan Tidak dalam suatu atribut. Lo bisa lihat bahwa atribut C paling homogen, 5/6 bernilai Ya pada C1 dan 4/4 bernilai Tidak pada C2. Dengan kondisi seperti ini kita akan lebih yakin dalam mengklasifikasi suatu data baru, misalnya kalo ada data dengan nilai C=C2 maka secara pasti output-nya bernilai Tidak (karena berdasarkan dataset, output seluruh data dengan nilai C2 pada atribut C ialah Tidak). Hal ini berbeda kalo ada data baru dengan nilai A=A1, kemungkinannya masih 50:50. Jelas?

Konsep homogenitas diatas dinamakan (im)purity, yaitu seberapa murni output yang dihasilkan dari suatu atribut. Semakin homogen suatu atribut maka purity nya semakin tinggi, begitu juga sebaliknya. Oleh karena itu, kita pilih atribut yang memiliki purity yang paling tinggi. Secara kuantitatif, kita bisa menghitung kadar purity atau impurity berdasarkan nilai entropi. Entropi ini mirip dengan entropi dalam kimia yang menggambarkan tingkat ketidakteraturan suatu sistem. Semakin tinggi nilai entropi maka semakin tinggi ketidakteraturannya, atau dengan kata lain semakin tinggi impurity nya. Sebaliknya, semakin rendah nilai entropi maka semakin teratur, semakin homogen, semakin tinggi purity nya. Kita ingin mencari atribut yang memiliki nilai entropi terendah atau information gain tertinggi untuk dipilih sebagai node.

$$E(a_1, a_2, …, a_n)=-p_1 log_2 p_1-p_2 log_2 p_2…-p_n log_2 p_n$$

dimana $n$ merupakan jumlah kemungkinan output. Kalo kemungkinan output-nya Ya atau Tidak maka $n=2$. $a_1, a_2, …, a_n$ merupakan jumlah output suatu data. $p_1, p_2, …, p_n$ merupakan probabilitas output suatu data dimana $p_1=\frac{a_1}{a_1+a_2+…+a_n}$. Pada data skateboard diatas, output-nya terdiri dari 9 Ya dan 5 Tidak, sehingga:

$$E(9, 5)=-\frac{9}{14}log_2\frac{9}{14}-\frac{5}{14}log_2\frac{5}{14}=0.940$$

Nilai entropi berkisar antara nol hingga $log_2(jumlah kemungkinan output)$. Jadi untuk data skateboard, yang merupakan klasifikasi biner, nilai entropi berkisar dari nol sampai $log_2(2)$, atau dari 0-1.

Selanjutnya kita hitung entropi tiap atribut. Untuk atribut Cuaca terdiri dari 3 kemungkinan nilai (Cerah, Mendung, Hujan) dengan distribusi sebagai berikut:

 Ya  Tidak
 Cerah  2  3  5
 Mendung  4  0  4
 Hujan  3 2  5

Sebelum menghitung entropi atribut Cuaca, kita hitung terlebih dahulu entropi tiap-tiap kemungkinan nilainya.

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

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

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

Selanjutnya entropi Cuaca dihitung secara kumulatif dengan pembobotan

$$E(\text{Cuaca})= P(\text{Cerah}) \times E(\text{Cerah}) + P(\text{Mendung}) \times E(\text{Mendung}) + P(\text{Hujan}) \times E(\text{Hujan})$$

$$E(\text{Cuaca})=\frac{5}{14} \times 0.971 + \frac{4}{14} \times 0 + \frac{5}{14} \times 0.971$$

$$E(\text{Cuaca})=0.693$$

Setelah kita mendapatkan nilai entropi calon atribut dan parent node, selanjutnya kita hitung information gain untuk atribut tersebut. Information gain merupakan selisih antara entropi parent node dengan entropi calon atribut. Information gain menggambarkan seberapa besar ketidakpastian yang  dapat dihindari jika memilih atribut tersebut. Oleh karena itu kita mencari atribut yang memiliki information gain tertinggi.

$$Gain(\text{Cuaca})=0.940-0.693=0.247$$

Dengan cara yang sama kita dapat menghitung entropi untuk semua atribut lain, sehingga akan menghasilkan:

$Gain(\text{Cuaca})=0.247$

$Gain(\text{Suhu})=0.029$

$Gain(\text{Kelembapan})=E(\text{Kelembapan})=0.152$

$Gain(\text{Berawan})=E(\text{Berawan})=0.048$

Dari keempat information gain diatas, atribut Cuaca memiliki information gain yang paling tertinggi, sehingga atribut ini yang kita jadikan node. Dari node ini terbentuk 3 cabang, masing-masing untuk Cerah, Mendung, dan Hujan.

Menentukan Internal Node

Langkah selanjutnya setelah kita dapatkan root node beserta cabang-cabangnya ialah melakukan langkah sebelumnya secara rekursif. Sekarang gw akan perlihatkan bagaimana menentukan atribut yang tepat untuk cabang Cuaca=Cerah. Kita pilih data yang memilki Cuaca=Cerah sehingga tampak seperti dataset berikut.

Suhu Kelembapan Berawan Main
 Panas  Tinggi  Tidak  Tidak
 Panas  Tinggi  Ya  Tidak
 Sejuk  Tinggi  Tidak  Tidak
 Dingin  Normal  Tidak  Ya
 Sejuk  Normal  Ya  Ya

Selanjutnya kita hitung entropi tiap atribut. Untuk atribut Suhu terdiri dari 3 kemungkinan nilai (Panas, Sejuk, Dingin) dengan distribusi sebagai berikut:

 Ya  Tidak
 Panas  0  2  2
 Sejuk  1  1  2
 Dingin  1  0  1

Pertama, kita hitung entropi dataset ini, yang merupakan parent node

E(\text{Parent Node})=E(2, 3)==-\frac{2}{5}log_2\frac{2}{5}-\frac{3}{5}log_2\frac{3}{5}=0.971$$

Selanjutnya kita hitung entropi untuk atribut Cuaca dengan terlebih dahulu menghitung entropi tiap-tiap kemungkinan nilainya.

$$E(\text{Panas})=E(0, 2)=0$$

$$E(\text{Sejuk})=E(1, 1)=1$$

$$E(\text{Dingin})=E(1, 0)=0$$

Selanjutnya entropi Suhu dihitung secara kumulatif dengan pembobotan

$$E(\text{Suhu})= P(\text{Panas}) \times E(\text{Panas}) + P(\text{Sejuk}) \times E(\text{Sejuk}) + P(\text{Dingin}) \times E(\text{Dingin})$$

$$E(\text{Suhu})=\frac{2}{5} \times 0 + \frac{2}{5} \times 1 + \frac{1}{5} \times 0$$

$$E(\text{Suhu})=0.4$$

$$Gain(\text{Suhu})=Entropi(\text{Parent Node})-Entropi(\text{suhu})=0.971-0.4=0.571$$

Dengan cara yang sama kita dapat menghitung entropi untuk semua atribut lain, sehingga akan menghasilkan:

$Gain(\text{Suhu})=0.571$

$Gain(\text{Suhu})=0.971$

$Gain(\text{Suhu})=0.020$

Dari ketig information gain diatas, atribut Kelembapan memiliki information gain yang paling tinggi, sehingga atribut ini yang kita jadikan node. Dari node ini terbentuk 2 cabang, masing-masing untuk Tinggi dan Normal.

Langkah-langkah diatas diulangi sehingga hasil akhirnya akan tampak seperti pohon keputusan berikut:

Atribut Super

Dari dataset saat ini misalnya gw tambah sebuah atribut baru bernama Hari yang kemungkinan nilainya mulai dari H1 sampai H14.

Hari Cuaca Suhu Kelembapan Berawan Main
 H1  Cerah  Panas  Tinggi  Tidak  Tidak
 H2  Cerah  Panas  Tinggi  Ya  Tidak
 H3  Mendung  Panas  Tinggi  Tidak  Ya
 H4  Hujan  Sejuk  Tinggi  Tidak  Ya
 H5  Hujan  Dingin  Normal  Tidak  Ya
 H6  Hujan  Dingin  Normal  Ya  Tidak
 H7  Mendung  Dingin  Normal  Ya  Ya
 H8  Cerah  Sejuk  Tinggi  Tidak  Tidak
 H9  Cerah  Dingin  Normal  Tidak  Ya
 H10  Hujan  Sejuk  Normal  Tidak  Ya
 H11  Cerah  Sejuk  Normal  Ya  Ya
 H12  Mendung  Sejuk  Tinggi  Ya  Ya
 H13  Mendung  Panas  Normal  Tidak  Ya
 H14  Hujan  Sejuk  Tinggi  Ya  Tidak

Apa yang akan terjadi terhadap pohon keputusan setelah penambahan atribut ini? Coba kita cari dulu root node nya dengan menghitung entropi Hari.

$$E(\text{Hari})=\frac{1}{14} \times E(0, 1) + \frac{1}{14} \times E(0, 1) + … + \frac{1}{14} \times E(0, 1)$$

Nilai dari $E(0, 1)$ adalah $0$ sehingga $E(\text{Hari})=0$. Ini artinya, atribut Hari memiliki entropi yang paling rendah atau information gain yang paling tinggi sehingga otomatis menjadi root node. Root node dengan 14 cabang!

Gimana kalo punya data baru dengan Hari=H32, Cuaca=Cerah, Suhu=Panas, Kelembapan=Tinggi, dan Berawan=Ya? Gak bisa coy! Dengan kondisi seperti ini kita tidak bisa melakukan prediksi, bahkan pohon keputusan tersebut tidak memberikan informasi bermanfaat mengenai proses klasifikasi. Inilah yang disebut atribut super.

Lalu bagaimana mengatasinya?

Kita bisa atasi dengan memberikan penalti berdasarkan banyak cabang. Semakin banyak cabang makin besar penaltinya. Penalti ini dinamakan Split Information. Split information menunjukkan seberapa murni cabang suatu atribut. Jika semakin sedikit maka semakin murni, begitu pula sebaliknya. Oleh karena itu perhitungan penalti atau split information ini menggunakan perhitungan entropi. Misalnya split information atribut Cuaca ialah:

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

$$SplitInfo(\text{Cuaca})=1.577$$

Dengan cara yang sama maka split information dari atribut Hari ialah 3.807. Selanjutnya untuk menentukan atribut mana yang dipilih sebagai node, kita hitung berdasarkan nilai Gain dibagi SplitInfo. Nilai ini dinamakan GainRatio.

$$GainRatio(Atribut)=\frac{Gain(Atribut)}{SplitInfo(Atribut)}$$

Berikut ini GainRatio untuk seluruh atribut diatas:

$$GainRatio(Hari)=0.247$$

$$GainRatio(Cuaca)=0.156$$

$$GainRatio(Temperature)=0.019$$

$$GainRatio(Kelembapan)=0.152$$

$$GainRatio(Berawan)=0.049$$

Mengapa gain ratio atribut Hari masih yang tertinggi? Hal ini karena data yang sedikit. Bayangkan jika ada 200 instances unik, maka split information akan jauh lebih besar dan gain ratio yang dihasilkan akan jauh lebih kecil.

Pendidikan Kita: Sedikit Refleksi

Dulu waktu gw kelas 6 SD duru gw seneng banget ngasih PR matematika dan juga soal-soal latihan di kelas. Masa-masa SD kelas 6 ini juga salah satu masa ‘kejayaan’ gw. Kenapa? Gw bisa dapet uang jajan tambahan cuma-cuma dari guru gw. Jadi gini, kelas gw terdiri dari anak-anak yang mempunyai beragam kemampuan dan passion. Ada yang jago ngaji dan ceramah, ada yang jago main bulu tangkis, ada yang jago matematika, ada yang jago menghimpun massa, dan ada juga yang jago jualan barang. Masing-masing memiliki passion-nya sendiri.

Sebagai anak baik, gw tentu kerjain semua PR yang dikasih guru, nyimak pas guru nerangin, dan pulang sekolah sesuai jamnya. Tapi guru gw suka ngecek PR yang dikasih di hari sebelumnya. Satu-satu anak dipanggil secara acak buat maju ngerjain PR yang dikasih, yang ga bisa atau belum ngerjain di denda 1000 perak. Hahaha. Soal tersebut kemudian dilempar ke anak lain, yang mau dan jawabannya benar bakal dikasih 1000 perak hasil dari uang denda tadi. Reward & punishment gitu lah. Jadi lah gw yang kebagian rejeki karena suka maju.

Tapi sebenarnya gw tau, temen-temen gw yang lain punya bakat di bidang lain, cuma kasiannya bakatnya gak di tes aja di dalam kelas. Ulay misalnya, dia jago menghimpun massa. Dia punya banyak anak buah dan anak geng yang loyal sama dia. Beberapa konspirasi dan rencana geng nya berhasil di eksekusi. Ada juga Azis, si ‘tukang’ ngaji. Pernah nyabet juara MTQ se-DKI. Sekarang doi lagi ngaji di Mesir. Dan banyak anak-anak lain yang memiliki keunikan dalam bakat dan passion nya.

Sayang oh sayang, gak bakal ada nilai public speaking di rapor, gak bakal ada nilai leadership saat ujian, dan gak bakal ada nilai bisnis dan entrepreneurship di UN. Yang di-UN-kan ya semata-mata kemampuan kognitif lo. Inilah sistem pendidikan kita. Parahnya lagi, orang tua juga belum paham tentang talenta anaknya. Kalo dapet rapor merah pasti anaknya diomel-omelin. Tapi kita patut sedikit bahagia, menurut survei PISA tahun 2012 Indonesia merupakan negara dengan siswa paling bahagia di dunia, walaupun memiliki kemampuan matematika, membaca, dan pengetahuan yang rendah (posisi 9 dari bawah, dari 65 negara). Anomali? I don’t think so.

Tapi semakin gw belajar mengenai pendidikan, gw semakin yakin bahwa sebenarnya kita bisa lebih baik dari itu. Ada Abah Rama yang bikin gw sedikit tahu tentang talent mapping. Ada om Blake Boles yang bikin gw tahu tentang Bootcamp sebagai alternatif belajar, belajar dari kehidupan. Banyak juga riset mengenai Personalized Learning, Self-Directed Learning, Learning Sciences, EdTech, dan lain sebagainya. Sekarang waktunya untuk aksi, bukan cuma pinter nyinyir dan mengeluh. Semoga bisa!

Hakikat Kebahagiaan dan Kesuksesan

Kebahagiaan dan kesuksesan bukan terletak pada banyaknya harta. Ada orang kaya, tapi ia tidak bahagia. Apakah dengan memiliki setumpuk emas dan seperti Qorun? Bahkan hartanya ikut menenggelamkannya!

Kebahagiaan dan kesuksesan bukan pula terletak pada tingginya pangkat dan jabatan. Ada yang menjadi menteri, tapi ia tetap korupsi. Ada yang menjadi raja bahkan mengaku sebagai Tuhan (Fir’aun), tapi lihatlah bagaimana Allah jadikan akhir hayatnya.

Kebahagiaan dan kesuksesan bukan pula terletak pada popularitas. Berapa banyak artis yang terkenal tapi terlilit narkoba? Berapa banyak artis yang rumah tangganya berantakan? Berapa luas pula network yang seseorang punya tapi tak ada yang bisa membuatnya tersenyum?

Kebahagiaan dan kesuksesan bukan pula terletak pada banyaknya anak, sederetnya gelar, panjangnya umur, dan besarnya pengaruh di masyarakat.

Kebahagiaan dan kesuksesan di dunia dan akhirat hanya bisa didapat jika manusia mengamalkan amalan agama secara sempurna, yaitu dengan mengikuti seluruh kehidupan Rasulullah saw.. Ibadahnya, muamalahnya, mu’asyarahnya, akhlaknya, semuanya dengan mengikuti apa yang dicontohkan Rasulullah saw..

Deliberate Practice: Yang Bikin Orang Jadi Jago

Pernah liat kemampuan menggocek dan shooting Cristiano Ronaldo? Keren kan? Sampai-sampai beberapa kali doi menyabet gelar top scorer Liga Spanyol. Pernah juga menjadi pemain terbaik dunia. Selain CR7 ada juga Sean Wrona (pasti lo belum pernah denger nama yang ini), seorang fast typist yang bisa ngetik pake keyboard sampai lebih dari 200 kata per menit. Coba aja lo tes kecepatan mengetik lo di Typeracer. Karena gw suka ngetik ngebut jadi gw tau orang ini. Dan orang jago yang terakhir yang gw mau sebut ialah temen gw sendiri, Ahmad Faiz. Doi sobat sekamar gw pas SMA Aliyah. Doi pernah menyabet medali emas OSN bidang kimia, dan sekarang melanjutkan kuliahnya di Jepang dalam bidang yang sama.

Ketiganya punya persamaan dan perbedaan. Ketiganya sama-sama jago di bidangnya. Namun CR7 dan Sean sama-sama jago dalam hal psikomotorik, sedangkan Faiz jago dalam bidang kognitif. Tapi yang gw ingin bahas disini ialah bagaimana mereka bisa seperti itu.

Banyak orang yang ingin jago/proficient/expert/mahir dalam suatu bidang. Bidang yang mereka sukai. Tapi banyak yang salah kaprah juga gimana caranya untuk sampai kesana. Ada yang bilang, “Itu kan bakat mereka”. Dan ada juga yang bilang, “Perfect practices make perfect. Even imperfect practices make perfect.” Latihan, latihan, latihan. Jadi ya latihan aja terus menerus nanti juga mahir. Begitu katanya.

Eits belum tentu lho. Ada penelitian yang pernah dilakukan oleh bang Ericcson (kaya merek hape yah?) pada tahun 1993. Doi mengumpulkan pemain biola di akademi musik ternama di Jerman yang telah banyak menelurkan pemain-pemain biola dunia. Mereka sama-sama memiliki bakat. Pemain biola tersebut kemudian dibagi menjadi tiga kelompok menurut tingkat keahliannya. Dan ternyata waktu yang mereka habiskan untuk berlatih sama, sekitar 51 jam per minggu.

Jadi sebenernya apa yang bikin seseorang jago?


Jawabannya, Latihan. (Lah sama aja dong?)

Tapi latihan ini yang kita sebut deliberate practice. Terjemahan kasarnya, “Latihan yang disengaja”. Yang bikin suatu bentuk latihan dibilang deliberate practice, bukan latihan biasa, ialah jika punya 3 karakteristik berikut:

Pertama, setiap bentuk latihan yang dilakukan mesti fokus pada sebuah aspek keahlian, bukan dengan memainkannya dengan “full-game”. Maksudnya gini, kalo lo mau jago main bola bukan berarti latihan yang harus lo lakukan cuma main bola tiap hari (main full game, 11 vs 11). Tapi yang bener ialah lo asah skill dribbling, shooting, heading, dsb satu per satu. Contoh lainnya kalo mau jago ngetik cepat bukannya asal ngetik yang penting cepat. Tapi fokus misalnya latihan untuk meningkatkan akurasi mengetik, biar lambat yang penting akurasinya bagus.

Kedua, latihan yang sama dilakukan berulang-ulang sampai pada tingkat kemahiran tertentu. Tetapkan target atau metrik yang ingin dicapai, lalu berlatih seperti pada poin pertama sampai target tersebut tercapai. Misalnya, kalo lo mau jago di bidang kimia, maka kerjakanlah soal-soal stoikiometri dasar sampai jawaban yang lo hasilkan semuanya benar. Lalu tingkatkan lagi pada stoikiometri menengah, dan seterusnya.

Ketiga, berikan feedback selama proses latihan, feedback langsung untuk setiap progres. Hal ini bisa dilakukan sendiri atau dengan bantuan orang lain. Misalnya kalo ada jawaban dari stoikiometri yang salah lo dapet feedback salahnya dimana, sehingga proses latihan berikutnya akan ada perbaikan. Atau ketika latihan dribble bola, ternyata ada teknik yang salah atau lebih baik menggunakan teknik yang ini dan itu.

Tapi oh tapi, sesungguhnya deliberate practice itu tidaklah mudah. Butuh kegigihan dan konsistensi. Namun percayalah bahwa lo akan menuai hasilnya. Hal inilah yang didapatkan oleh para jagoan yang gw sebut di awal tulisan ini.

Selamat Berusaha!

Referensi:

Chen, Z., Chudzicki, C., Palumbo, D. et al. (2016). Researching for better instructional methods using AB experiments in MOOCs: results and challenges. Research and Practice in Technology Enhanced Learning.
doi: 10.1186/s41039-016-0034-4

Ericsson, K. A., Krampe, R. Th., & Tesch-Roemer, C. (1993). The role of deliberate practice in the acquisition of expert performance. Psychological Review, 100, 363-406.

Implementasi Regresi Linear Menggunakan Python

Pada tulisan ini gw jelaskan bagaimana mencari persamaan regresi, yakni dengan menghitung semua parameter estimasi menggunakan perhitungan matriks. Namun coba bayangkan matriks yang dihasilkan jika terdapat ratusan data dengan puluhan atribut, akan sangat besar. Matriks yang besar ini membutuhkan memori yang besar pula untuk melakukan komputasi antar matriks. Inilah kekurangannya jika kita menyelesaikan masalah regresi linear menggunakan matriks. Oleh karena itu, cara yang lebih efisien untuk menyelesaikan masalah regresi ialah menggunakan gradient descent. Silakan baca tulisan mengenai gradient descent disini.

Dalam implementasi ini kita gunakan bahasa pemrograman Python.

  • Meng-import package yang dibutuhkan. Numpy digunakan untuk menyimpan data dalam bentuk matriks dan untuk manipulasi matrix. Matplotlib digunakan untuk menampilkan grafik/plot regresi linear.
    import numpy as np
    import matplotlib.pyplot as plt
  • Memuat data set (data_rumah_bdg). Data set yang gw pakai adalah data penjualan rumah di Bandung yang terdiri dari atribut Luast Tanah, Luas Bangunan, Jumlah Kamar Tidur, Jumlah Kamar Mandi, dan Harga Jual Rumah. Karena baris pertama pada data set merupakan nama kolom, kita buang baris pertama ini.
    data = np.genfromtxt("../data_rumah_bdg.csv", dtype=int, delimiter=",")
    data = data[1:, :]
  • Menambahkan sebuah kolom baru di awal data yang diisi dengan nilai 1. Mengapa kita tambahkan ini? Karena kita akan melakukan perkalian antara matriks yang berisi koefisien pada persamaan regresi dengan matriks data set ini. Tulisan ini mungkin membantu.
    data = np.insert(data, 0, 1, axis=1)
  • Kita tidak menggunakan semua atribut, kita hanya gunakan atribut Luas Tanah saja sebagai input dan Harga Jual sebagai output. So, kita ambil kolom pertama dan kedua (kolom pertama merupakan hasil penambahan sebelumnya dan kolom kedua merupakan atribut Luas Tanah) sebagai input.
    X = data[:, :2]
    y = data[:, 5]
  • Mengatur learning rate atau $\alpha$ dan banyak iterasi yang akan dilakukan selama proses learning.
    alpha = 0.00005
    num_iterations = 1500
  • Menginisialisasi nilai $\beta$ (nilai yang kita cari) dengan 0.
    beta = np.zeros(shape=(1, 2))
  • Variabel lain yang dibutuhkan: variabel N untuk menyimpan jumlah data dan variabel tmp_beta untuk menyimpan nilai beta sementara.
    N = y.size
    tmp_beta = [0] * X.shape[1]
  • Proses learning sebanyak iterasi yang telah ditentukan. Implementasi dari gradient descent pada tulisan ini.
    for i in range(num_iterations):
         y_hat = np.inner(beta, X)
         error = np.subtract(y_hat, y)
         for p in range(X.shape[1]):
              sum_of_dot = np.inner(error, X[:, p])
              tmp_beta[p] = beta[0, p] - alpha * (2 / float(N)) * sum_of_dot
         for p in range(X.shape[1]):
              beta[0, p] = tmp_beta[p]
  • Menampilkan plot regresi linear
    p_x = np.arange(30, 200+1, 1)
    p_y = beta[0, 0] + beta[0, 1] * p_x
    
    plt.plot(X[:, 1], y,'bo')
    plt.plot(p_x,p_y,'r-',label='Regresi linear gradient descent')
    plt.xlim(30, 200)
    plt.ylim(300, 1600)
    plt.show()
  • Selesai

Perbandingan dengan Scikit-Learn dan Perhitungan Manual

Gw coba bandingkan gimana perbedaan antara hasil implementasi diatas dengan hasil regresi jika menggunakan package yang telah tersedia dan jika menggunakan perhitungan manual. Yang gw bandingin ialah nilai MSE dan $\beta$.

MSE $\beta_0$ $\beta_1$
Gradient Descent  18797.49 2.251 7.435
Scikit-Learn  16399.49  167.624  6.063
Hitung Manual  16399.49  167.624  6.063

Hasil dari Scikit-learning sama persis dengan perhitungan manual sedangkan hasil dari implementasi gradient descent cukup berbeda dengan menghasilkan MSE yang lebih besar. Mengapa hal ini terjadi?

Mengenal Gradient Descent

Pada regresi linear, kita mencoba meminimalkan error untuk mendapatkan persamaan regresi yang terbaik dan cara mendapatkannya ialah dengan melakukan perhitungan berdasarkan perkalian matriks. Namun apakah hanya dengan rumus ini kita bisa mendapatkan persamaan regresi? Jawabannya tidak, ada cara lain juga.

Kita mulai dengan pertanyaan ini, cari nilai $x$ sehingga $f(x)=2(x-2)^2+8$ bernilai minimum! Gimana mencarinya? Yap, turunin $f(x)$ terhadap $x$, jadikan nilainya 0, kemudian selesaikan persamaannya. Kurang lebih akan seperti ini:

$$f(x)=2(x-2)^2+8$$

$$\frac{df(x)}{dx}=2*2(x-2)=4x-8$$

$$\frac{df(x)}{dx}=0$$

$$4x-8=0$$

$$x=2$$

Hal yang sama dilakukan untuk fungsi yang terdiri dari 2 variabel. Pertama kita turunkan fungsinya terhadap tiap variabel, lalu jadikan tiap turunannya bernilai 0, dan selesaikan persamaannya. Cara ini juga yang kita gunakan untuk mencari nilai $\beta$ pada persamaan regresi. Lo bisa baca lagi disini.

Namun ada cara lain yang bisa dicoba, yakni menggunakan gradient descent. Kita bisa mulai dari sembarang nilai $x$. Lalu kita bergerak menuju error yang lebih kecil dengan menghitung gradient pada nilai $x$ tersebut. Gradient pada titik ini memberikan informasi arah kita bergerak, dimana kalau nilainya positif maka kita harus bergerak ke arah kiri untuk mendapatkan gradient yang lebih kecil (dan sebaliknya). Proses ini terus dilakukan sampai gradient nya 0. Nilai $x$ dengan gradient 0 merupakan nilai minimum. Setiap kali kita bergerak nilai $x$ akan berubah berdasarkan formula berikut:

$$x_{k+1}=x_k-\alpha\nabla f(x_k)$$

$\alpha$ disebut learning rate, yaitu seberapa jauh kita bergerak. Semakin tinggi $\alpha$ maka loncatan yang kita buat akan semakin besar dan sebaliknya semakin kecil $\alpha$ maka proses bergeraknya akan semakin kecil sehingga akan semakin lama mencapai convergence (gradient 0). Biasanya nilai $\alpha$ < 0.5.

Untuk lebih memahami maksudnya gw kasih contoh simpel.

Kita ingin mendapatkan nilai $x$ sehingga $f(x)=2(x-2)^2$ bernilai minimum.

Pertama, tentukan nilai $\alpha$ dan hitung $\nabla  f(x)$
kita ambil nilai $\alpha=0.1$ dan $\nabla  f(x)=4x-8$

Kedua, ambil nilai $x$ sembarang
kita mulai dari $x_0=6$

Ketiga, jalankan proses learning

  • $x_1=x_0-\alpha\nabla f(x_0)$
    $x_1=6-0.1*16$
    $x_1=4.4$
  • $x_2=x_1-\alpha\nabla  f(x_1)$
    $x_2=4.4-0.1*9.6$
    $x_2=3.44$
  • $x_3=x_2-\alpha\nabla  f(x_2)$
    $x_3=3.44-0.1*5.76$
    $x_3=2.864$
  • $x_4=x_3-\alpha\nabla  f(x_3)$
    $x_4=2.864-0.1*3.456$
    $x_4=2.5184$
  • $x_5=x_4-\alpha\nabla  f(x_4)$
    $x_5=2.5184-0.1*2.0736$
    $x_5=2.31104$
  • $x_6=x_5-\alpha\nabla  f(x_5)$
    $x_6=2.31104-0.1*1.24416$
    $x_6=2.18662$
  • $x_7=x_6-\alpha\nabla  f(x_6)$
    $x_7=2.18662-0.1*0.7465$
    $x_7=2.11197$
  • $x_8=x_7-\alpha\nabla  f(x_7)$
    $x_8=2.11197-0.1*0.44788$
    $x_8=2.0671$
  • $x_9=x_8-\alpha\nabla  f(x_8)$
    $x_9=2.0671-0.1*0.26872$
    $x_9=2.04$
  • $x_{10}=x_7-\alpha\nabla  f(x_7)$
    $x_{10}=2.04-0.1*0.161$
    $x_{10}=2.0239$

Proses learning tersebut berjalan sampai convergence.

(diadaptasi dari onmyphd.com)

Coba kita lihat mulai dari $x_0$ sampai $x_{10}$, gradient nya semakin menurun menuju 0 dan nilai $x$ nya semakin berkurang. Jika proses learning diatas dijalankan terus maka nilai $x$ akan mendekati $2$ dan gradient nya akan mendekati $0$. Nilai ini sama dengan perhitungan menggunakan cara tradisional. Pertanyaannya ialah, sampai kapan proses learning tersebut berjalan? Apakah akan convergence?

Cara yang paling umum digunakan ialah dengan mengatur jumlah iterasi yang dilakukan. Biasanya proses learning dilakukan sebanyak 1000-1500 iterasi.

Gradient Descent pada Regresi Linear

Pada regresi linear, kita ingin mencari persamaan garis yang memiliki MSE yang paling rendah. MSE ini disebut cost function, yang kita ingin sekecil mungkin. Karena kita ingin mencari persamaan garis maka yang kita cari ialah nilai $\beta$ atau parameter estimates. Misalnya kita memiliki persamaan regresi sederhana:

$$\hat{y}=\beta_0+\beta_1 x$$

Catatan: $\hat{y}$ merupakan estimasi nilai $y$, ini berbeda dengan nilai $y$ yang berasal dari data

Maka kita akan mencari $\beta_0$ dan $\beta_1$ sehingga $f(\beta_0, \beta_1) = \frac{1}{n} \sum_{i=1}^n ((\beta_0+\beta_1x_i)-y_i)^2$ bernilai minimum. Karena terdapat 2 variabel yang kita cari, maka ketika melakukan update, yang diupdate ialah 2 variabel ini, $\beta_0$ dan $\beta_1$

$$\beta_0 = \beta_0-\alpha \frac{\partial}{\partial \beta_0} f(\beta_0, \beta_1)$$

$$\beta_1 = \beta_1-\alpha \frac{\partial}{\partial \beta_1} f(\beta_0, \beta_1)$$

dimana

$$\frac{\partial}{\partial \beta_0} f(\beta_0, \beta_1)=\frac{\partial}{\partial \beta_0} \frac{1}{n} \sum_{i=1}^n ((\beta_0+\beta_1x_i)-y_i)^2$$

$$=\frac{2}{n} \sum_{i=1}^n ((\beta_0+\beta_1x_i)-y_i)$$

$$\frac{\partial}{\partial \beta_1} f(\beta_0, \beta_1)=\frac{\partial}{\partial \beta_1} \frac{1}{n} \sum_{i=1}^n ((\beta_0+\beta_1x_i)-y_i)^2$$

$$=\frac{2}{n} \sum_{i=1}^n ((\beta_0+\beta_1x_i)-y_i) x_i$$

Jadi, proses learning gradient descent pada regresi linear akan seperti berikut:

$$\beta_0 = \beta_0-\alpha \frac{2}{n} \sum_{i=1}^n ((\beta_0+\beta_1x_i)-y_i)$$

$$\beta_1 = \beta_1-\alpha \frac{2}{n} \sum_{i=1}^n ((\beta_0+\beta_1x_i)-y_i) x_i$$

Namun kita harus hati-hati ketika mengimplementasikan fungsi diatas, nilai $\beta_0$ dipanggil dua kali, yakni untuk mendapatkan nilai $\beta_0$ itu sendiri dan untuk mendapatkan nilai $\beta_1$. Oleh karena itu jangan meng-update $\beta_0$ sebelum fungsi yang kedua dijalankan. Untuk menghindari hal ini, maka kita gunakan variabel lain untuk sementara waktu menampung nilai $\beta_0$.

$$tmp\_\beta_0 = \beta_0-\alpha \frac{2}{n} \sum_{i=1}^n ((\beta_0+\beta_1x_i)-y_i)$$

$$tmp\_\beta_1 = \beta_1-\alpha \frac{2}{n} \sum_{i=1}^n ((\beta_0+\beta_1x_i)-y_i) x_i$$

$$\beta_0 = tmp\_\beta_0$$

$$\beta_1 = tmp\_\beta_1$$

Pertanyaan selanjutnya, bagaimana gradient descent untuk regresi linear multivariabel sehingga persamaan regresinya akan tampak seperti berikut:

$$\hat{y}=\beta_0+\beta_1 x_1+\beta_2 x_2+…+\beta_p x_p$$

jawabannya ialah:

$$\beta_0 = \beta_0-\alpha \frac{2}{n} \sum_{i=1}^n ((\beta_0+\beta_1 x_{1\_i}+\beta_2 x_{2\_i}+…+\beta_p x_{p\_i})-y_i)$$

$$\beta_1 = \beta_1-\alpha \frac{2}{n} \sum_{i=1}^n ((\beta_0+\beta_1 x_{1\_i}+\beta_2 x_{2\_i}+…+\beta_p x_{p\_i})-y_i) x_{1\_i}$$

$$\beta_p = \beta_p-\alpha \frac{2}{n} \sum_{i=1}^n ((\beta_0+\beta_1 x_{1\_i}+\beta_2 x_{2\_i}+…+\beta_p x_{p\_i})-y_i) x_{p\_i}$$

nb: $x_{p\_i}$ ialah data ke-$i$ pada variabel ke-$p$.

Bahan Bacaan:

Menentukan Kapan Convergence

Menangani Data Berkategori Pada Regresi Linear

Regresi linear memang ditujukan untuk data-data yang bersifat kontinu seperti angka, namun ada kalanya data set yang kita punya terdiri dari data berkategori atau data diskrit, misalnya jenis kelamin (pria/wanita), cuaca (mendung, berawan, cerah, hujan), dan suku (betawi, sunda, minang, batak, dll).

Contoh permasalahan yang paling sederhana misalnya kita punya data kehamilan seseorang. Kita ingin melihat bagaimana hubungan antara berat badan calon bayi dengan kebiasaan merokok sang ibu selama kehamilan. Data tersebut terdiri dari Lama Kandungan (minggu), Status Merokok (merokok/tidak merokok), dan Berat Badan Bayi (gram). Atribut Status Merokok merupakan data kualitatif yang kemungkinan nilainya hanya dua, merokok atau tidak merokok.

Coba lihat pada grafik yang pertama, terlihat jelas hubungan antara Lama Kandungan dengan Berat Badan bayi, dimana semakin lama kandungannya maka berat badan bayi semakin bertambah. Tapi coba lihat pada grafik yang kedua, gimana hubungannya? Complicated!

Oke, persamaan regresi linear untuk data diatas cukup mudah:

$$\text{Berat Badan} = \beta_0+\beta_1\text{Lama Kandungan} + \beta_2\text{Status Merokok}$$

Untuk nilai Lama Kandungan sudah jelas, nilanya berupa angka (minggu) tapi gimana untuk Status Merokok? Kan kemungkinan nilainya hanya Merokok/Tidak Merokok. Jawabannya simpel, untuk atribut yang hanya memiliki dua kemungkinan nilai (benar-salah, merokok-tidak merokok, cowok-cewek, dsb) maka kita kodekan dulu nilainya menjadi variabel dummy yang nilainya numerik, 0 dan 1, sehingga $Status Merokok = 0$ jika tidak merokok dan $Status Merokok = 1$ jika merokok. Persamaan sebelumnya akan menjadi:

$$\text{Berat Badan} =
\begin{cases}
\beta_0+\beta_1\text{Lama Kandungan}, & \text{jika tidak merokok} \\[2ex]
\beta_0+\beta_1\text{Lama Kandungan}+\beta_2, & \text{jika merokok}
\end{cases}$$

Dengan men-set nilai Status Merokok menjadi 0 atau 1 maka kita akan memperoleh persamaan linear yang menghasilkan dua garis yang paralel dan memiliki slope atau kemiringan yang sama. Persamaan regresi tersebud dapat dicari seperti menyelesaikan regresi linear multi variabel.

Lalu bagaimana jika atributnya memiliki lebih dari dua kemungkinan nilai?

Caranya hampir mirip, andaikan kita punya data penjualan online yang atributnya Jumlah Order, Diskon (0-100%), dan Waktu (Pagi, Siang, dan Malam). Persamaan regresi linear untuk data tersebut kurang lebih seperti berikut:

$$\text{Jumlah Order} = \beta_0+\beta_1\text{Diskon} + \beta_2\text{Waktu}$$

Nah, lalu variabel Waktu kita isi apa? Caranya ialah dengan mengkodekan waktu menjadi nilai numerik, sama seperti kasus sebelumnya. Dari 3 kemungkinan nilai yang ada kita buat menjadi dua variabel baru, Pagi dan Siang sehingga persamaan regresi linearnya berubah menjadi:

$$\text{Jumlah Order} = \beta_0+\beta_1\text{Diskon} + \beta_2\text{Pagi} + \beta_3\text{Siang}$$

Jika suatu data memiliki Waktu yang nilainya Pagi, maka Pagi=1 dan Siang=0. Jika suatu data memiliki waktu yang nilainya siang maka Pagi=0 dan Siang=1. Dan jika suatu data memiliki waktu yang nilainya Malam maka Pagi=0 dan Siang=0. Lihat tabel berikut:

Variabel Dummy
Pagi Siang
Pagi 1 0
Siang 0 1
Malam 0 0

Persaman regresi linear akhir yang dihasilkan ialah:

$$\text{Jumlah Order} =
\begin{cases}
\beta_0+\beta_1\text{Diskon}+\beta_2, & \text{jika waktu=pagi} \\[2ex]
\beta_0+\beta_1\text{Diskon}+\beta_3, & \text{jika waktu=siang} \\[2ex]
\beta_0+\beta_1\text{Diskon}, & \text{jika waktu=malam}
\end{cases}$$

Sebenarnya ada banyak cara mengkodekan nilai kategori menjadi nilai numerik, seperti pada tulisan ini dan ini. Namun yang paling umum digunakan ialah cara yang saya gunakan diatas yang disebut dengan dummy coding.

Masalah-masalah yang Terdapat pada Regresi Linear

Regresi linear merupakan algoritma machine learning yang paling sederhana. Kesederhanaannya dapat membawa angin positif dan negatif. Positifnya, regresi linear sangat mudah di-train dan hasil modelnya mudah diinterpretasi. Namun tidak sedikit juga masalah-masalah yang dapat ditimbulkan. Pada tulisan ini gw ingin membahas apa aja masalah yang bisa terjadi saat kita menerapkan teknik regresi linear. Dengan mengetahui masalah ini kita bisa meng-improve model yang telah kita bangun sehingga hasilnya bisa lebih baik.

Mengenal Residual Plot

Sebelum masuk ke inti pembahasan, gw mau mengenalkan dulu sebuah visualisasi data yang sangat berguna untuk mengidentifikasi masalah yang mungkin muncul. Namanya residual plot. residu = error = $\epsilon = y_i-\hat{y_i}$. Error ini yang kita plot untuk tiap data. Gambar dibawah ini menunjukkan residual plot untuk data set harga penjualan rumah. Gambar yang sebelah kanan merupakan residual plot.

Pada residual plot, sumbu X merupakan prediksi kelas target untuk tiap data berdasarkan model regresi sedangkan sumbu Y menunjukkan error atau yang dihasilkan prediksi tersebut. Jarak tiap point dari garis 0 menunjukkan seberapa baik prediksi yang dihasilkan oleh model. Namun jika kita menggunakan residu, maka tiap case akan mendapatkan skala residu yang berbeda, dalam kasus diatas nilai residunya dalam skala ratusan, namun dalam persoalan lain bisa jadi hanya skala puluhan. Oleh karena itu kita standardisasi dulu residunya agar untuk setiap kasus yang berbeda kita menggunakan skala yang sama. Standardisasi residu mudah saja dilakukan, yakni dengan cara membagi residu dengan RSE.

Idealnya, residual plot tampak seperti salah satu pada grafik berikut:


(Keterangan: grafik diadaptasi dari Statwing)

Ciri-ciri residual plot yang ideal ada tiga, yaitu:

  1. Point-point pada residual plot terdistribusi cukup simetris dan cenderung berpusat di tengah-tengah grafik (residu = 0)
  2. Point-point pada residual plot berpusat pada daerah dengan residu yang rendah (misalnya 0.5, 1.5, atau 3) bukan residu yang tinggi (misalnya 40, 70, dsb).
  3. Secara umum tidak ada pattern yang jelas, misalnya berbentuk kurva.

Beberapa contoh residual plot yang tidak ideal seperti ini:


Grafik-grafik diatas menunjukkan suatu kejanggalan dan tidak memenuhi ciri residual plot yang ideal. Saat kita tahu bahwa ada masalah pada model yang dihasilkan atau masalah pada sumber data, kita bisa memperbaiki model tersebut sehingga akan didapatkan hasil yang lebih baik. Berikut ini beberapa masalah yang dapat timbul pada regresi linear.

Non-linearity

Asumsi utama regresi linear, data bersifat linear. Artinya hubungan antara atribut dan kelas seperti garis lurus yang linear. Namun jika pada kenyataannya hubungan tersebut tidak linear (non linear) maka hasil regresi linear akan ‘jelek’. Kita bisa lihat Residual plot apakah menunjukkan non-linearity tersebut. Dibawah ini beberapa yang termasuk non-linear.

Terus gimana meng-handle masalah non-linearity ini?

Jika residual plot menunjukkan pola non-linear yang jelas, maka cara yang mudah ialah menggunakan model regresi non-linear.

Correlation of Error Terms

Kalo kita lihat pada contoh residual plot yang ideal, terlihat memang tidak ada pattern yang jelas, error yang dihasilkan terdistribusi secara simetris dan tidak saling terkait. Namun bisa saja terjadi error tersebut saling terkait. Misalnya, berdasarkan error ke-$i$ kita bisa tahu perkiraan error ke-$i+1$ berapa. Nah ini yang menjadi masalah pada regresi, dimana error-error tersebut memiliki makna sehingga residual plot-nya membentuk pattern tertentu. Biasanya masalah ini terjadi pada data time series, dimana terdapat seasonality atau cycle.

Lalu bagaimana mengatasinya?

Untuk data yang sifatnya time series perlu pendekatan lain yang lebih cocok. Gw bakal bahas tentang time series ini suatu saat. Stay tune ya! 😀

Heteroscedasticity

Apa itu heteroscedasticity? (bacanya aja uda ribet ya…) Heteroscedasticity itu kondisi dimana residu/error yang semakin besar atau kecil seiring dengan hasil prediksi yang semakin besar (bisa juga semakin kecil). Coba perhatikan grafik dibawah ini supaya lebih jelas.

Semakin bergerak ke kanan/kiri, error yang dihasilkan semakin besar atau kecil sehingga mengakibatkan variansi error menjadi tidak konstan. Sebagai contoh, jika seseorang menanam modal/investasi untuk suatu bisnis, semakin banyak uang yang diinvestasikan maka keuntungannya akan semakin besar, pun jika rugi maka kerugiannya akan semakin besar.

Jika kondisi ini terjadi, cara yang paling umum untuk meningkatkan kualitas model kita ialah dengan mentranformasi response/kelas target yang semula nilainya $Y$, ditransformasi sehingga nilainya $log(Y)$ atau $\sqrt Y$. Dengan transformasi ini diharapkan variansi error akan lebih konstan dan residual plot-nya akan lebih ideal. (Note: kalo datanya bernilai negatif, menggunakan transformasi $\sqrt Y$ akan lebih sulit dan perlu sedikit diakalin).

Outliers

Outlier merupakan data yang dianggap menyimpang dari data yang umumnya. Misalnya dari data penjualan rumah ternyata ada rumah yang dijual di Antapani Bandung dengan luas tanah 350$m^2$ seharga 45 juta. Bisa aja sih, misalnya si yang jual lagi baik hati :D. Dua grafik dibawah ini memperlihatkan residual plot yang mengandung outlier.

 

Outlier bisa terjadi pada 2 kondisi. Pertama, pada data yang memiliki respons yang gak wajar. Misalnya, ada orang jual rumah dengan luas tanah 150$m^2$ seharga 20 miliar. Kedua, outlier yang disebabkan karena ada input yang tidak normal dan respons yang dimiliki juga tidak normal. Misalnya kita ingin melihat hubungan antara lama belajar siswa dengan nilai ujian yang diperoleh. Rata-rata siswa belajar 40-60 jam per minggunya dengan nilai yang diperoleh bervariasi tergantung lama belajar. Yang termasuk dalam outlier jenis kedua ini ketika ada siswa yang belajar 140 jam per minggu tapi nilainya jeblok, katakan lah 20 dari total 100. Inputnya gak wajar, dimana siswa belajar 140 jam per minggu atau setara 20 jam sehari. Pun hasilnya yang diberikan juga tidak sesuai harapan, harusnya kan semakin lama kita belajar nilai yang didapatkan semakin bagus.

Outlier bisa membawa pengaruh walaupun tidak terlalu signifikan. Outlier bisa membuat RSE lebih tinggi jika tidak ada outlier, sehingga bisa mengubah hasil interpretasi model regresi.

Lalu bagaimana mengatasinya? Kita lihat dulu seberapa pengaruh outlier tersebut. Coba kita bandingkan hasil regresi ketika masih ada outlier dengan hasil regresi setelah outlier dihapus. Jika tidak ada perbedaan yang signifikan maka outlier bisa dibiarkan saja.

Tapi kalo outlier memberikan pengaruh yang signifikan, kita analisis dulu apakah datanya masih make sense atau enggak. Outlier bisa aja dihapus asalkan ada justifikasi yang jelas.

Collinearity

Collinearity merupakan kondisi dimana ada dua atau lebih atribut yang saling terkait, jika yang satu naik . Walaupun masalah ini tidak berpengaruh pada kualitas prediksi model regresi, namun tetap akan membuat parameter estimasi ($\beta$) menjadi tidak stabil dan sulit diinterpretasi. Hal ini karena atribut-atribut yang co-linear sifatnya rendundan. Yap, co-linear berarti ada atribut yang berkaitan dimana masing-masing atribut nilainya sama-sama naik atau sama-sama turun sehingga sulit menentukan sebenernya yang berpengaruh terhadap hasil prediksi itu yang mana.

Misalnya kita memiliki dataset mengenai kesehatan seseorang yang memiliki atribut: tinggi badan, berat badan, tekanan darah, dan umur. Gambar dibawah ini menunjukkan plot antara tekanan darah dengan umur dan tekanan darah dengan tinggi badan. Kita bisa lihat antara tekanan darah dengan berat badan memiliki hubungan yang sangat linear. Cara lain untuk meng-kuantifikasi apakah terdapat collinearity atau tidak ialah melalui variance inflation factor (VIF) atau correlation matrix yang menampilkan korelasi antar atribut.

Ada dua solusi untuk masalah ini. Pertama, dengan menghapus salah satu atribut yang bermasalah. Karena dua atribut ini memberikan respons yang redundan maka menghapus salah satunya tidak akan membawa perubahan yang signifikan. Atau dengan cara yang kedua, yaitu dengan mengkombinasikan dua atribut tersebut menjadi satu atribut.

 

Daftar Bacaan:

[1] Interpreting residual plots to improve your regression

[2] ISLR Sixth Printing