TUGAS “DATA MINING”
Nama Kelompok : I Putu Ari Ratna Pratama (1208605055) Putu Mega Suryawan (1208605069) Ida Bagus Surya Winantara (1208605085)
PROGRAM STUDI TEKNIK INFORMATIKA JURUSAN ILMU KOMPUTER - FMIPA UNIVERSITAS UDAYANA BUKIT JIMBARAN 2015
ALGORITMA ID3 Pengertian ID3 (Iterative Dichotomiser Three) atau yang disebut juga denganInduction of Decision Treeadalah suatu algoritma matematika yang digunakan untuk menghasilkan suatu pohon keputusan yang mampu mengklasifikasi suatu obyek. Pengertian laindari ID3 yaitu ID3 merupakan sebuah metode yang digunakan untuk membangkitkan pohon keputusan. ID3 diperkenalkan pertama kali oleh Ross Quinlan (1979).ID3 merepresentasi konsep-konsep dalam bentuk pohon keputusan.Aturan-aturan yang dihasilkan oleh ID3 mempunyai relasi yang hirarkis seperti suatu pohon (mempunyai akar, titik, cabang, dan daun). Beberapa peneliti menyebut struktur model yang dihasilkan ID3 sebagai pohon keputusan (decision tree) sementara peneliti yang lain menyebutnya pohon aturan (rule tree). Algoritma pada ID3 berbasis pada Occam’s razor: lebih memilih pohon keputusan yang lebih kecil (teori sederhana) dibanding yang lebih besar. Tetapi tidak dapat selalu menghasilkan pohon keputusan yang paling kecil dan karena itu occam’s razor bersifat heuristik. Occam’s razor diformalisasi menggunakan konsep dari entropi informasi. Algoritma ID3 Input : sampel training, label training, atribut
Membuat simpul akar untuk pohon yang dibuat Jika semua sampel positif, berhenti dengan suatu pohon dengan satu simpul
akar, beri label (+) Jika semua sampel negatif, berhenti dengan suatu pohon dengan satu simpul
akar beri label (-) Jika atribut kosong, berhenti dengan suatu pohon dengan satu simpul akar,
dengan label sesuai nilai yang terbanyak yang ada pada label training Untuk yang lain, Mulai A atribut yang mengklasifikasikan sampel dengan hasil terbaik
(berdasarkan gain ratio) Atribut keputusan untuk simpul akar A Untuk setiap nilai, vi, yang mungkin untuk A, - Tambahkan cabang di bawah akar yang berhubungan dengan A=vi
-
Tentukan sampel Svi sebagai subset dari sampel yang mempunyai
-
nilai vi untuk atribut A Jika sampel Svi kosong, Di bawah cabang tambahkan simpul daun dengan label = nilai yang terbanyak yang aa pada label training Yang lain, tambah cabang baru di bawah cabang yang sekarang C4.5 (sampel training, label training, atribut-[A])
Berhenti
Adapun sample data yang digunakan oleh ID3 memiliki beberapa syarat, yaitu :
Deskripsi atribut-nilai. Atribut yang sama harus mendeskripsikan tiap contoh
dan memiliki jumlah nilai yang sudah ditentukan. Kelas yang sudah didefinisikan sebelumnya. Suatu atribut contoh harus sudah
didefinisikan, karena mereka tidak dipelajari oleh ID3. Kelas-kelas yang diskrit. Kelas harus digambarkan dengan jelas. Kelas yang continue dipecah-pecah menjadi kategori-kategori yang relatif, misalnya saja
metal dikategorikan menjadi “hard, quite hard, flexible, soft, quite soft”. Jumlah contoh (example) yang cukup. Karena pembangkitan induktif digunakan, maka dibutuhkan test case yang cukup untuk membedakan pola yang valid dari peluang suatu kejadian. Pemillihan atribut pada ID3 dilakukan dengan properti statistik, yang disebut
dengan information gain.Gain mengukur seberapa baik suatu atribut memisahkan training example ke dalam kelas target. Atribut dengan informasi tertinggi akan dipilih. Dengan tujuan untuk mendefinisikan gain, pertama-tama digunakanlah ide dari teori informasi yang disebut entropi.Entropi mengukur jumlah dari informasi yang ada pada atribut. Rumus untuk menghitung entropi informasi adalah : −¿ −¿ log 2 p ¿ +¿−p ¿ +¿ log 2 p ¿ Entropy ( S ) ≡−p ¿
Rumus untuk menghitung gain adalah :
Gain ( S , A ) ≡ Entropy ( S )−Σ
|Sv| Entropy (Sv ) |S|
Contoh Mencatat Keadaan 14 Minggu Permainan Tenis pada Setiap Sabtu Pagi Ming
Ramalan_Cu
gu
aca
M1
Cerah
Suhu
Panas
Kelemba
Angi
Bermain_Te
ban
n
nis
Tinggi
Lema
Tidak
h M2
Cerah
Panas
Tinggi
Kuat
Tidak
M3
Mendung
Panas
Tinggi
Lema
Ya
h M4
Hujan
Sejuk
Tinggi
Lema
Ya
h M5
Hujan
Dingin
Normal
Lema
Ya
h M6
Hujan
Dingin
Normal
Kuat
Tidak
M7
Mendung
Dingin
Normal
Kuat
Ya
M8
Cerah
Sejuk
Tinggi
Lema
Tidak
h M9
Cerah
Dingin
Normal
Lema
Ya
h M10
Hujan
Sejuk
Normal
Lema
Ya
h M11
Cerah
Sejuk
Normal
Kuat
Ya
M12
Mendung
Sejuk
Tinggi
Kuat
Ya
M13
Mendung
Panas
Normal
Lema
Ya
h
M14
Hujan
Sejuk
Tinggi
Kuat
Tidak
Atribut Tujuan adalah Bermain Tenis yang memiliki value ya atau tidak. Atribut adalah Ramalan_Cuaca, Suhu, Kelembaban, dan Angin. Algoritma Dan Flowchart Entropy
adalah
formula
untuk
menghitung
homogenitas
dari
sebuah
sample/contoh. Solusi menggunakan entropy dari contoh kasus di atas : S adalah koleksi dari 14 contoh dengan 9 contoh positif dan 5 contoh negatif, ditulis dengan notasi [9+,5-]. Positif di sini maksudnya value Bermain_Tenis = Ya sedangkan negatif sebaliknya. Entropy dari S adalah : c
i 1
Entropy(S) =
pi =
- pi log2pi
Zi N
Zi = contoh positif + contoh negatif N = jumlah data Entropy([9+,5-])
= - (9/14) log2 (9/14)
- (5/14) log2 (5/14)
= - (0.6429) ((log (9/14))/log 2) - (0.3571) ((log (5/14))/log 2) = - (0.6429) (-0.1919/0.3010) - (0.3571) (-0.4472/0.3010) = - (0.6429) (-0.6375) - (0.3571) (-1.4857) = 0.4098 + 0.5305 = 0.94029 Catatan :
Entropy(S) = 0, jika semua contoh pada S berada dalam kelas yang sama.
Entropy(S) = 1, jika jumlah contoh positif dan jumlah contoh negative
dalam S adalah sama. 0 < Entropy(S) < 1, jika jumlah contoh positif dan jumlah contoh negatif dalam S tidak sama.
Gain(S,A) adalah Information Gain dari sebuah atribut A pada koleksi contoh S :
Gain(S,A)
=
| Sv | vValues( A ) | S |
Entropy(S)
-
1. Values(Angin)
= Lemah, Kuat
SLemah
= [6+,2-]
SKuat
= [3+,3-]
Gain(S,Angin)
Entropy(Sv)
=
Entropy(S)
-
(8/14)Entropy(SLemah)
(6/14)Entropy(SKuat) = 0.94029 - (8/14)0.81128 - (6/14)1.0000 = 0.04813 2. Values(Kelembaban) STinggi SNormal
= Tinggi, Normal = [3+,4-] = [6+,1-]
Gain(S,Kelembaban) = Entropy(S) - (7/14)Entropy(STinggi) (7/14)Entropy(SNormal) = 0.94029 - (7/14)0.98523 - (7/14)0.59167 = 0.15184 3. Values(Suhu) SPanas
= Panas, Sejuk, Dingin = [2+,2-]
SSejuk
= [4+,2-]
SDingin
= [3+,1-]
-
Gain(S,Suhu)
= Entropy(S) - (4/14)Entropy(SPanas) (6/14)Entropy(SSejuk) (4/14)Entropy(SDingin) = 0.94029 - (4/14)1.00000 - (6/14)0.91830 (4/14)0.81128 = 0.02922
4. Values(Ramalan_Cuaca) = Cerah, Mendung, Hujan SCerah = [2+,3-] SMendung
= [4+,0-]
SHujan
= [3+,2-]
Gain(S,Ramalan_Cuaca) = Entropy(S) - (5/14)Entropy(SCerah) (4/14)Entropy(SMendung) (5/14)Entropy(SHujan) = 0.94029 - (5/14)0.97075 - (4/14)1.00000 (5/14)0.97075 = 0.24675 Jadi, information gain untuk 3 atribut yang ada adalah : Gain(S,Angin) = 0.04813 Gain(S,Kelembaban) = 0.15184 Gain(S,Suhu) = 0.02922 Gain(S,Ramalan_Cuaca) = 0.24675 Tampak bahwa attribute Ramalan_Cuaca akan menyediakan prediksi terbaik untuk target attribute Bermain_Tenis. [M1, M2, ..., M14] [9+,5-]
Ramalan_Cuaca Cerah
Mendung
Hujan
Ya ?
?
[M1, M2, M8, M9, M11]
[M4, M5, M6, M10, M14]
[2+,3-]
[3+,2-]
Untuk node cabang Ramalan_Cuaca = Cerah, SCerah = [M1, M2, M8, M9, M11] Ming
Ramalan_Cu
gu
aca
M1
Cerah
Suhu
Panas
Kelemba
Angi
Bermain_Te
ban
n
nis
Tinggi
Lema
Tidak
h M2
Cerah
Panas
Tinggi
Kuat
Tidak
M8
Cerah
Sejuk
Tinggi
Lema
Tidak
h M9
Cerah
Dingin
Normal
Lema
Ya
h M11
Cerah
1. Values(Suhu) SPanas
Sejuk
Normal
Kuat
Ya
= Panas, Sejuk, Dingin = [0+,2-]
SSejuk
= [1+,1-]
SDingin
= [1+,0-]
Gain(SCerah,Suhu)
= Entropy(SCerah) - (2/5)Entropy(SPanas) (2/5)Entropy(SSejuk) (1/5)Entropy(SDingin) = 0.97075 - (2/5)0.00000 - (2/5)1.00000 (1/5)0.00000 = 0.57075
2. Values(Kelembaban) STinggi SNormal
= Tinggi, Normal = [0+,3-] = [2+,0-]
Gain(SCerah,Kelembaban) = Entropy(SCerah) - (3/5)Entropy(STinggi) (2/5)Entropy(SNormal) = 0.97075 - (3/5)0.00000 - (2/5)0.00000 = 0.97075 3. Values(Angin)
= Lemah, Kuat
SLemah
= [1+,2-]
SKuat
= [1+,1-]
Gain(SCerah,Angin)
= Entropy(SCerah) - (3/5)Entropy(SLemah) (2/5)Entropy(SKuat) = 0.97075 - (3/5)0.91830 - (2/5)1.00000 = 0.01997
Atribut Kelembaban menyediakan prediksi terbaik pada level ini. [M1, M2, ..., M14] [9+,5-]
Ramalan_Cuaca Cerah
Hujan
Mendung
[M1, M2, M8, M9, M11] [2+,3-]
?
Ya
Kelembaban
[M4, M5, M6, M10, M14] [3+,2-]
Normal
Tinggi
Tidak
Ya
[M1, M2, M8]
[M9, M11]
[0+,3-]
[2+,0-]
Untuk node cabang Ramalan_Cuaca = Hujan, SHujan = [M4, M5, M6, M10, M14] Mingg
Ramalan_Cua
u
ca
M4
Hujan
Suhu
Kelembab
Angin
Bermain_Teni
an Sejuk
Tinggi
s Lema h
Ya
M5
Hujan
Dingin
Normal
Lema
Ya
h M6
Hujan
Dingin
Normal
Kuat
Tidak
M10
Hujan
Sejuk
Normal
Lema
Ya
h M14
Hujan
1. Values(Suhu) SSejuk
Sejuk
Tinggi
Kuat
Tidak
= Sejuk, Dingin (Tidak ada suhu = panas saat ini) = [2+,1-]
SDingin
= [1+,1-]
Gain(SHujan,Suhu)
= Entropy(SHujan) - (3/5)Entropy(SSejuk) (2/5)Entropy(SDingin) = 0.97075 - (3/5)0.91830 - (2/5)1.00000 = 0.01997
2. Values(Kelembaban) STinggi SNormal
= Tinggi, Normal = [1+,1-] = [2+,1-]
Gain(SHujan,Kelembaban) = Entropy(SHujan) - (2/5)Entropy(STinggi) (3/5)Entropy(SNormal) = 0.97075 - (2/5)1.00000 - (3/5)0.91830 = 0.01997 3. Values(Angin) SLemah SKuat
= Lemah, Kuat = [3+,0-] = [0+,2-]
Gain(SHujan,Angin) = Entropy(SHujan) - (3/5)Entropy(SLemah) (2/5)Entropy(SKuat) = 0.97075 - (3/5)0.00000 - (2/5)0.00000 = 0.97075 Atribut Angin menyediakan prediksi terbaik pada level ini.
Algoritma : If Ramalan_Cuaca = Cerah AND Kelembaban = Tinggi THEN Bermain_Tenis = Tidak If
Ramalan_Cuaca = Cerah AND Kelembaban = Normal THEN Bermain_Tenis = Ya
If Ramalan_Cuaca = Mendung THEN Bermain_Tenis = Ya If Ramalan_Cuaca = Hujan AND Angin = Kuat THEN Bermain_Tenis = Tidak If Ramalan_Cuaca = Hujan AND Angin = Lemah THEN Bermain_Tenis = Ya Ramalan_Cuaca
Suhu
Kelembaban
Angin
Bermain_Tenis
Cerah
Panas
Tinggi
Kuat
Tidak
Cerah
Panas
Tinggi
Lemah
Tidak
Cerah
Panas
Normal
Kuat
Ya
Cerah
Panas
Normal
Lemah
Ya
Cerah
Sejuk
Tinggi
Kuat
Tidak
Cerah
Sejuk
Tinggi
Lemah
Tidak
Cerah
Sejuk
Normal
Kuat
Ya
Cerah
Sejuk
Normal
Lemah
Ya
Cerah
Dingin
Tinggi
Kuat
Tidak
Cerah
Dingin
Tinggi
Lemah
Tidak
Cerah
Dingin
Normal
Kuat
Ya
Cerah
Dingin
Normal
Lemah
Ya
Mendung
Panas
Tinggi
Kuat
Ya
Mendung
Panas
Tinggi
Lemah
Ya
Mendung
Panas
Normal
Kuat
Ya
Mendung
Panas
Normal
Lemah
Ya
Mendung
Sejuk
Tinggi
Kuat
Ya
Mendung
Sejuk
Tinggi
Lemah
Ya
Mendung
Sejuk
Normal
Kuat
Ya
Mendung
Sejuk
Normal
Lemah
Ya
Mendung
Dingin
Tinggi
Kuat
Ya
Mendung
Dingin
Tinggi
Lemah
Ya
Mendung
Dingin
Normal
Kuat
Ya
Mendung
Dingin
Normal
Lemah
Ya
Hujan
Sejuk
Tinggi
Kuat
Tidak
Hujan
Sejuk
Tinggi
Lemah
Ya
Hujan
Sejuk
Normal
Kuat
Tidak
Hujan
Sejuk
Normal
Lemah
Ya
Hujan
Dingin
Tinggi
Kuat
Tidak
Hujan
Dingin
Tinggi
Lemah
Ya
Hujan
Dingin
Normal
Kuat
Tidak
Hujan
Dingin
Normal
Lemah
Ya
Flowchart :
ALGORITMA C4.5 Pengertian Algoritma C4.5 merupakan algoritma yang digunakan untuk membangun sebuah pohon keputusan (decision tree) dari data.Algoritma C4.5 merupakan pengembangan dari algoritma ID3 yang juga merupakan algoritma untuk membangun
sebuah
pohon
keputusan.Algoritma
C4.5
secara
rekursif
mengunjungi tiap simpul keputusan, memilih percabangan optimal, sampai tidak ada cabang lagi yang mungkin dihasilkan.
Algoritma C4.5 merupakan salah satu algoritma machine learning. Dengan algoritma ini, mesin(komputer) akan diberikan sekelompok data untuk dipelajari yang disebut learning dataset.Kemudian hasil dari pembelajaran selanjutnya akan digunakan untuk mengolah data-data yangbaru yang disebut test dataset. Karena algoritma C4.5 digunakan untuk melakukan klasifikasi,jadi hasil dari pengolahan test dataset berupa pengelompokkan data ke dalam kelas-kelasnya. Algoritma C4.5 Algoritma C4.5 menggunakan konsep information gain atau entropy reduction untuk memilih percabangan yang optimal. Misalkan terdapat sebuah variabel X dimana memiliki sejumlah k nilai yang mungkin dengan probabilitas p1, p2, …, pk. Entropy menggambarkan keseragaman data dalam variabel X. Entropy variabel X (H(X)) dihitung dengan menggunakan persamaan sebagai berikut. H ( X )=−∑ P j log 2 ( P j ) j
Misalkan terdapat sebuah kandidat simpul yang akan dikembangkan (S), yang membagi data T ke dalam sejumlah subset T1, T2, …, Tk. Dengan menggunakan persamaan entropy diatas, nilai entropy tiap subset dihitung (HS(Ti)). Kemudian total bobot subset simpul S dihitung dengan menggunakan persamaan sebagai berikut. k
H s ( T ) =∑ Pi H s ( T i ) i=1
dimana Pi merupakan proporsi record pada subset i. Semakin seragam sebuah subset terhadap kelas-kelas pembaginya, maka semakin kecil nilai entropy. Nilai entropy paling kecil adalah 0, yang dicapai ketika record subset berada pada satu kelas yang sama. Sedangkan nilai entropy paling tinggi adalah 1, yang dicapai ketika record subset terbagi sama rata pada untuk tiap kelas. Semakin kecil nilai entropy, semakin baik subset tersebut. Dari nilai-nilai entropy yang didapat, nilai information gain untuk simpul S dihitung melaui persamaan sebagai berikut.
gain ( S )=H ( T ) −H s (T ) Pada algoritma C4.5, nilai information gain dihitung untuk seluruh simpul yang mungkin dikembangkan. Simpul yang dikembangkan adalah simpul yang memiliki nilai information gain yang paling besar. Contoh Berikut ini adalah uraian langkah-langkah dalam algoritma C4.5 untuk menyelesaikan kasussuatu pertandingan tenis akan dilakukan atau tidak, berdasarkan keadaan cuaca, suhu,kelembaban, dan angin. Data yang telah ada pada Tabel 1, akan digunakan untuk membentukpohon keputusan. Pada Tabel 1, atribut-atributnya adalah Cuaca, Suhu, Kelembaban, dan Berangin. Setiap atributmemiliki 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 (lihat Tabel 2). Tabel 1. Learning Dataset No
Cuaca
Suhu
Kelembaba
Berangin
Main
1 2 3 4 5 6 7 8 9 10 11 12 13 14
Cerah Cerah Berawan Hujan Hujan Hujan Berawan Cerah Cerah Hujan Cerah Berawan Berawan Hujan
Panas Panas Panas Sejuk Dingin Dingin Dingin Sejuk Dingin Sejuk Sejuk Sejuk Panas Sejuk
n Tinggi Tinggi Tinggi Tinggi Normal Normal Normal Tinggi Normal Normal Normal Tinggi Normal Tinggi
Salah Benar Salah Salah Salah Benar Benar Salah Salah Salah Benar Benar Salah Benar
Tidak Tidak Ya Ya Ya Ya Ya Tidak Ya Ya Ya Ya Ya Tidak
Kemudian hitung entropi dengan rumus sebagai berikut :
k
Entropi ( S )=∑ −P j log 2 P j j=1
Keterangan :
S adalah himpunan (dataset) kasus k adalah banyaknya partisi S Pj adalah probabilitas yang di dapat dari Sum(Ya) dibagi Total Kasus
(( )
Jadi Entropi ( S )= −
( )) ( ( )
( ))
10 10 4 4 × log 2 +− × log2 =0.8631 14 14 14 14
Tabel 2. Hasil Perhitungan Pada Dataset Total Kasus 14
Sum (Ya) 10
Sum (Tidak) 4
Entropi Total 0.8631
Setelah mendapatkan entropi dari keseluruhan kasus, lakukan analisis pada setiap atribut dannilai-nilainya dan hitung entropinya seperti yang ditampilkan pada Tabel 3. Tabel 3. Analisis Atribut, Nilai, Banyaknya Kejadian Nilai, Entropi dan Gain Node 1
Atribut Cuaca
Nilai
Sum
Sum
Sum
Entropi
Berawa
(Nilai) 4
(Ya) 4
(Tidak) 0
0
n Hujan Cerah
5 5
4 2
1 3
0.7219 0.9709
Dingin Panas Sejuk
4 4 6
4 2 4
0 2 2
0 1 0.9182
Gain
0.2585 Suhu
0.1838 Kelembaba n Berangin
Tinggi Normal
7 7
3 7
4 0
0.9852 0
Salah Benar
8 6
6 2
2 4
0.8112 0.9182
0.3705 0.0059
Untuk menghitung gain setiap atribut rumusnya adalah :
¿ Si ∨
¿ ¿ S∨¿× Entropi(S i) ¿ k
Gain ( A )=Entropi ( S ) −∑ ¿ i=1
Jadi Gain (Cuaca ) =0.8631−
4 5 5 × 0+ × 0.7219+ ×0.9709 =0.2585 14 14 14
(( ) ( )
( )
)
Hitung pula Gain (Suhu), Gain (Kelembaban), dan Gain (Berangin). Hasilnya dapat
dilihat
padaTabel
3.Karena
nilai
gain
terbesar
adalah
Gain
(Kelembaban).Maka Kelembaban menjadi nodeakar (root node).Kemudian pada kelembaban normal, memiliki 7 kasus dansemuanya memiliki jawaban Ya (Sum(Total) / Sum(Ya) = 7/7 = 1).Dengan demikian kelembaban normal menjadi daun atau leaf.Lihat Tabel 3 yang selnya berwarna hijau.
Gambar. Pohon Keputusan Node 1 (root node) Berdasarkan pembentukan pohon keputusan node 1 (root node), Node 1.1 akan dianalisis lebihlanjut. Untuk mempermudah, Tabel 1 difilter, dengan mengambil data yang memilikiKelembaban = Tinggi sehingga jadilah Tabel 4. Tabel 4. Data yang Memiliki Kelembaban = Tinggi No
Cuaca
Suhu
Kelembaba
Berangin
Main
1 2 3
Cerah Cerah Berawan
Panas Panas Panas
n Tinggi Tinggi Tinggi
Salah Benar Salah
Tidak Tidak Ya
4 5 6 7
Hujan Cerah Berawan Hujan
Sejuk Sejuk Sejuk Sejuk
Tinggi Tinggi Tinggi Tinggi
Salah Salah Benar Benar
Ya Tidak Ya Tidak
Kemudian data di Tabel 4 dianalisis dan dihitung lagi entropi atribut Kelebaban Tinggi danentropi setiap atribut serta gainnya sehingga hasilnya seperti data pada Tabel 5. Setelah itutentukan pilih atribut yang memiliki gain tertinggi untuk dibuatkan node berikutnya. Tabel 5. Hasil Analisis Node 1.1 Kelembaban
Sum (Ya)
Sum (Tidak)
Entropi
Tinggi 7
3
4
0.9852
Node 1
Atribut Cuaca
Nilai
Sum
Sum
Sum
Entropi
Berawa
(Nilai) 2
(Ya) 2
(Tidak) 0
0
n Hujan Cerah
2 3
1 0
1 3
1 0
Dingin Panas Sejuk
0 3 4
0 1 2
0 2 2
0 0.9182 1
Gain
0.6995 Suhu
0.0202 Berangin
Salah Benar
4 3
2 2
2 1
1 0.9182 0.0202
Dari Tabel 5, gain tertinggi ada pada atribut Cuaca, dan Nilai yang dijadikan daun atau leafadalah Berawan dan Cerah. Jika divualisasi maka pohon keputusan tampak seperti Gambar (Pohon Keputusan Analisis Node 1.1).Untuk menganalisis node 1.1.2, lakukan lagi langkah-langkah yang sama seperti sebelumnya.Hasilnya ditampilkan pada Tabel 6 dan Gambar (Pohon Keputusan Akhir).
Gambar. Pohon Keputusan Analisis Node 1.1 Tabel 6.Hasil Analisi Node 1.1.2. No 1 2
Cuaca Hujan Hujan
Suhu
Kelembaba
Berangin
Main
Sejuk Sejuk
n Tinggi Tinggi
Salah Benar
Ya Tidak
Kelembaban
Sum (Ya)
Sum (Tidak)
Entropi
Tinggi & Hujan 2
1
1
1
Node 1
Atribut Suhu
Nilai
Sum
Sum
Sum
Entropi
Dingin Panas Sejuk
(Nilai) 0 0 2
(Ya) 0 0 1
(Tidak) 0 0 1
0 0 1
Gain
0 Berangin
Salah Benar
1 1
1 0
0 1
0 0 1
Gambar. Pohon Keputusan Akhir ALGORITMA CART Pengertian Metode CART ini pertama kali diajukan oleh Leo Breiman et al. pada tahun 1984.Pohon keputusan yang dihasilkan CART merupakan pohon biner dimana tiap simpul wajib memiliki dua cabang. CART secara rekursif membagi records pada data latihan ke dalam subset-subset yang memiliki nilai atribut target (kelas) yang sama. Algoritma CART Algoritma CART mengembangkan pohon keputusan dengan memilih percabangan yang paling optimal bagi tiap simpul.Pemilihan dilakukan dengan menghitung segala kemungkinan pada tiap variabel. Misalkan Ф(s|t) merupakan nilai “kebaikan” kandidat cabang s pada simpul t, maka nilai Ф(s|t) dapat dihitung sebagai berikut: ¿ P ( j|t L )−P( j∨t R )∨¿ ¿ kelas
∅ ( s|t )=2 P L P R
Dimana
∑¿ j=1
t L =simpul anak kiri dari simpult t R=simpul anak kanan dari simpul t PL =
jumlah record pada t L jumlah seluruh record pada datalatihan
PR =
jumlah record padat R jumlah seluruhrecord pada datalatihan
P( j∨t L )=
jumlah record kelas j pada t L jumlah record pada simpult
P( j∨t R )=
jumlah record kelas j pada t R jumlah record pada simpult
¿ P ( j|t L )−P( j∨t R )∨¿ ¿kelas
Nilai
∑¿
maksimal ketika record yang berada pada
j=1
cabang kiri atau kanan simpul memiliki kelas yang sama (seragam). Nilai maksimal yang dicapai sama dengan jumlah kelas pada data. Misalkan jika data
¿ P ( j|t L )−P( j∨t R )∨¿ terdiri atas dua kelas, maka nilai maksimal
¿kelas
∑¿
adalah 2.
j=1
Semakin seragam record pada cabang kiri atau kanan, maka semakin tinggi
¿ P ( j|t L )−P( j∨t R )∨¿
nilai
¿kelas
∑¿
. Nilai maksimal 2PLPR sebesar 0.5 dicapai ketika
j=1
cabang kiri dan kanan memiliki jumlah record yang sama. Kandidat percabangan yang dipilih adalah kandidat yang memiliki nilai Ф(s|t) paling besar. Contoh
Anda diberi data mengenai 8 orang nasabah yang pernah memperoleh kredit dari Bank Indra. Data tersebut meliputi besarnya tabungan (yang berjenis kategorial: rendah, sedang, atau tinggi), besarnya aset (yang berjenis kategorial: rendah, sedang, atau tinggi), besarnya pendapatan pertahun (dalam ribuan dollars, yang berjenis numerik dan berskala ration) dan risiko kredit (yang berjenis kategorial: risiko baik atau buruk) Nasabah A B C D E F G H
Tabungan Sedang Rendah Tinggi Sedang Rendah Tinggi Rendah Sedang
Aset Tinggi Rendah Sedang Sedang Sedang Tinggi Rendah Sedang
Pendapatan 75 50 25 50 100 25 25 75
Risiko Kredit Baik Buruk Buruk Baik Baik Baik Buruk Baik
Klasifikasi Cart
Noktah yang berbentuk elips disebut dengan noktah keputusan. Noktah jenis ini adalah notkah yang masih akan bercabang karena pada noktah ini
suatu record belum ditentukan klasifikasinya. Noktah keputusan pertama biasanya disebut noktah dasar Noktah yang berbentuk persegi panjang disebut dengan noktah terminasi
Pembahasan Permasalahan
Pertama, kita memiliki data dari 8 nasabah seperti tertera di tabel sebelumnya dan ingin memperoleh pengetahuan yang dapat diaplikasikan kepada mereka yang berpotensi menjadi nasabah ke-9, ke-10, etc sehingga dengan mengetahui aset, tabungan, dan pendapatan, ,kita dapat menentukan risiko
kredit mereka Kedua, data itu kelak akan kita jadikan input bagi suatu algoritma Ketiga, sebagai keluaran dari algoritma, kita akan memperoleh pengetahuan yang secara sederhana dapat direpresentasikan dalam bentuk pohon keputusan
Langkah-Langkah Algoritma CART :
Pertama, susun calon cabang (candidate split). Penyusunan ini dlakukan terhadap seluruh variabel prediktor. Daftar yang berisi calon cabang disebut daftar calon cabang mutakhir. Calon cabang prediktor tabungan Tabungan=rendah, dan tabungan={sedang, tinggi} Tabungan=sedang, dan tabungan={rendah, tinggi} Tabungan=tinggi, dan tabungan={rendah, sedang} Calon cabang prediktor aset Aset=rendah, dan aset={sedang, tinggi} Aset=sedang, dan aset={rendah, tinggi} Aset=tinggi, dan aset={rendah, sedang} Calon cabang preditor pendapatan Pendapatan ≤ 25.000 dan pendapatan > 25.000 Pendapatan ≤ 50.000 dan pendapatan > 50.000 Pendapatan ≤ 75.000 dan pendapatan > 75.000
Nama Calon Cabang
Calon Cabang Kiri
Calon Cabang Kanan
1
tabungan=rendah
tabungan={sedang, tinggi}
2
tabungan=sedang
tabungan={rendah, tinggi}
3
tabungan=tinggi
tabungan={rendah, sedang}
4
aset=rendah
aset={sedang, tinggi}
5
aset=sedang
aset={rendah, tinggi}
6
aset=tinggi
aset={rendah, sedang}
7
pendapatan <= 25.000
pendapatan > 25.000
8
pendapatan <= 50.000
pendapatan > 50.000
9
pendapatan <= 75.000
pendapatan > 75.000
Kedua, menilai kinerja keseluruhan calon cabang yang ada di daftar calon cabang mutakhir dengan jalan menghitung nilai besaran kesesuaian. Kinerja setiap calon cabang akan diukur melalui ukuran yang disebut dengan kesesuaian (goodness). Kesesuain dari calon cabang s pada noktah keputusan t dilambangkan dengan ɸ (s|t)
¿ P ( j|t L )−P( j∨t R )∨¿ ¿ kelas
∅ ( s|t )=2 P L P R
∑¿ j=1
Dimana t L =simpul anak kiri dari simpult t R=simpul anak kanan dari simpul t PL =
jumlah record pada t L jumlah seluruh record pada datalatihan
PR =
jumlah record padat R jumlah seluruhrecord pada datalatihan
P( j∨t L )=
jumlah record kelas j pada t L jumlah record pada simpult
P( j∨t R )=
jumlah reco rd kelas j pada t R jumlah record pada simpul t
N o
1
Risiko PL
PR
3/8=0,37
5/8=0,62
5
5
Kredit
2xPLxP P(j|tL)
P(j|tR)
R
Phi (s| Q(s|t)
1/3=0,33 Baik:
3
t) 0,437
4/5=0,8
0,46875
0,933
5
2/3=0,66 Buruk:
2
3/8=0,37
5/8=0,62
5
5
7
0,562 Baik:
3/3=1
2/5=0,4
Buruk:
0/3=0
3/5=0,6
2/8=0,25 3
0
1/5=0,2
0,46875
1,2
5
0,375
0,333
0,125
4/6=0,66 6/8=0,75
Baik:
1/2==0,5
7 2/6=0,33
Buruk:
1/2=0,5
3
2/8=0,25 4
0
5/6=0,83 6/8=0,75
Baik:
0/2=0
3
0,375
1,667
0,625
0,5
0,5
0,5
0,375
1
0,375
0,933
0,437
3
5
1/6=0,16
5
6
7
4/8=0,5
2/8=0,25
4/8=0,5
6/8=0,75
3/8=0,37
5/8=0,62
5
5
Buruk:
2/2=1
7
Baik:
3/4=0,75
2/4=0,5
Buruk:
1/4=0,25
2/4=0,5
Baik:
2/2=1
3/6=0,5
Buruk:
0/2=0
3/6=0,5
1/3=0,33 Baik:
3
4/5=0,8
0,46875
2/3=0,66 Buruk:
8
9
5/8=0,62
3/8=0,37
5
5
7/8=0,87
1/8=0,12
5
5
7
1/5=0,2 0,562
Baik:
2/5=0,4
3/3=1
Buruk:
3/5=0,6
0/3=0
0,46875
1,2
4/7=0,57 Baik:
1
5
0,187 1/1=0
0,21875
0,857
5
3/7=0,42 Buruk:
9
0/1=0
Ketiga, menentukan calon cabang manakah yang akan benar-benar menjadi cabang dengan memilih calon cabang yang memiliki nilai kesesuaian ɸ (s|t) terbesar. Setelah itu gambarkan percabangan. Menentukan calon cabang yang manakah yang benar-benar menjadi cabang à ɸ (s|t) terbesar
Noktah Keputusan A {Catatan A, C, D, E, F, H}
Kembali ke Langkah Kedua dengan melihat daftar calon cabang mutakhir masalah nasabah
Nama Calon Cabang
Calon Cabang Kiri
Calon Cabang Kanan
1
tabungan=rendah
tabungan={sedang, tinggi}
2
tabungan=sedang
tabungan={rendah, tinggi}
3
tabungan=tinggi
tabungan={rendah, sedang}
4
aset=rendah
aset={sedang, tinggi}
5
aset=sedang
aset={rendah, tinggi}
6
aset=tinggi
aset={rendah, sedang}
7
pendapatan <= 25.000
pendapatan > 25.000
8
pendapatan <= 50.000
pendapatan > 50.000
9
pendapatan <= 75.000
pendapatan > 75.000
Risik o N o
1
Kredi PL
PR
1/6=0,16
5/6=0,83
7
3
t
P(j|tL)
P(j|tR)
2xPLxP
Q(s|
Phi
R
t)
(s|t) 0,111
Baik:
1/1=1
4/5=0,8
0,27778
0,4
1
Buruk :
0/1=0
1/5=0,2 2/3=0,66
2
3/6=0,5
3/6=0,5
Baik:
3/3=1
Buruk
3
2/6=0,33
4/6=0,66
3
7
7
0,66 0,5
7
0,333
0,444
1
0,444
0,444
0,5
0,222
0,444
0,5
0,222
0,444
1
0,444
1/3=0,33
:
0/3=0
3
Baik:
1/2==0,5
4/4=1
:
1/2=0,5
0/4=0
Baik:
3/4=0,75
2/2=1
:
1/4=0,25
0/2=0
Baik:
2/2=1
3/4=0,75
:
0/2=0
1/4=0,25
Baik:
1/2=0,5
4/4=1
1/2=0,5
0/4=0
Buruk
5
4/6=0,66
2/6=0,33
7
3
Buruk
6
2/6=0,33
4/6=0,66
3
7
Buruk
7
2/6=0,33
4/6=0,66
3
7
Buruk :
2/3=0,66 8
9
3/6=0,5
3/6=0,5
5/6=0,83
1/6=0,16
3
7
0,66
Baik:
7
3/3=1
Buruk
1/3=0,33
:
3
0/3=0
Baik:
4/5=0,8
1/1=0
0,5
7
0,333
0,27778
0,4
0,111
Buruk :
1/5=0,2
0/1=0
Tabungan={rendah, sedang}
Kembali ke Langkah Kedua dengan melihat daftar calon cabang mutakhir masalah nasabah
Nama Calon Cabang
Calon Cabang Kiri
Calon Cabang Kanan
1
tabungan=rendah
tabungan={sedang, tinggi}
2
tabungan=sedang
tabungan={rendah, tinggi}
3
tabungan=tinggi
tabungan={rendah, sedang}
4
aset=rendah
aset={sedang, tinggi}
5
aset=sedang
aset={rendah, tinggi}
6
aset=tinggi
aset={rendah, sedang}
7
pendapatan <= 25.000
pendapatan > 25.000
8
pendapatan <= 50.000
pendapatan > 50.000
9
pendapatan <= 75.000
pendapatan > 75.000
Risiko
Phi
No
PL
PR
Kredit
P(j|tL)
P(j|tR)
2xPLxPR
Q(s|t)
(s|t)
1
0/2=0
2/2=1
Baik:
0
1/2=0,5
0
1
0
Buruk:
0
1/2=0,5
Baik:
0
1/2=0,5
0
1
0
Buruk:
0
1/2=0,5
Baik:
0/1=0
1/1=0
0,5
2
1
Buruk:
1/1=1
0/1=0
Baik:
1/1=1
0/1=0
0,5
2
1
Buruk:
0/1=0
1/1=1
Baik:
1/2=0,5
0/2=0
0
1
0
Buruk:
1/2=0,5
0/2=0
Baik:
1/2=0,5
0
0
1
0
Buruk:
1/2=0,5
0
Baik:
4/5=0,8
0
0
1
0
Buruk:
1/5=0,2
0
2
5
6
7
8
9
0/2=0
1/2=0,5
1/2=0,5
2/2=1
2/2=1
5/6=0,833
2/2=1
1/2=0,5
1/2=0,5
0/2=0
0/2=0
1/6=0,167
Aset=tinggi
Pegawai
Jabatan
Kelamin
Umur
Asal
Kategori Level
1
Service
Perempuan
45
Kota besar
Level 3
2
Service
Laki-laki
25
Kota besar
Level 1
3
Service
Laki-laki
33
kota kecil
Level 2
4
Manajemen
Laki-laki
25
Kota besar
Level 3
5
Manajemen
perempuan
35
kota kecil
Level 4
6
Manajemen
Laki-laki
26
kota kecil
Level 3
7
Manajemen
Perempuan
45
Kota besar
Level 4
8
Sales
Perempuan
40
kota kecil
Level 3
9
Sales
Laki-laki
30
Kota besar
Level 2
10
Sales
Perempuan
50
Kota besar
Level 2
11
Sales
Laki-laki
25
kota kecil
Level 1
Jika tidak ada noktah keputusan, pelaksanaan algoritma CART dihentikan dan sebaliknya jika ada kembali ke langkah kedua.
Referensi : “Pengertian
dan
Konsep
Algoritma
ID3”.
Diakses
dari
web,
http://s3.amazonaws.com/academia.edu.documents/31971224/Interactive_Dychot omizer_Three.docx, pada tanggal 28 Maret 2015 “Pengertian dan Konsep Algoritma C4.5 dan CART”. Diakses dari web, http://download.portalgaruda.org/article.php? article=161148&val=5450&title=PERBANDINGAN%20PERFORMANSI %20ALGORITMA%20C4.5%20DAN%20CART%20DALAM %20%20KLASIFIKSI%20DATA%20NILAI%20MAHASISWA%20PRODI %20TEKNIK%20KOMPUTER%20%20POLITEKNIK%20NEGERI %20PADANG, pada tanggal 28 Maret 2015 “Contoh
Algoritma
ID3”.
Diakses
dari
web,
https://kaparang.files.wordpress.com/2011/09/bahan-6-ai-id3.doc, pada tanggal 28 Maret 2015 “Contoh
Algoritma
C4.5”.
Diakses
dari
web,
http://s3.amazonaws.com/academia.edu.documents/32989710/Belajar_Mudah_Al goritma_Data_Mining_C4.5.pdf, pada tanggal 28 Maret 2015 “Contoh
Algoritma
CART”.
Diakses
dari
http://dc492.4shared.com/download/L2h55DbQ/metode_klasifikasi.pptx, tanggal 28 Maret 2015
web, pada
