Algoritma Data Mining (2) Tugas Klasifikasi

Algoritma  Data  Mining  (2)   Tugas  Klasifikasi   Anief  Fauzan  Rozi,  S.  Kom.,  M.  Eng.  

12/5/13  

Data  Mining  dan  Data  Warehouse   Universitas  Mercu  Buana  Yogyakarta    

1  

Kompentensi   •  Mahasiswa  mengetahui  algoritma  data   mining  pada  tugas  klasifikasi  

12/5/13  

Data  Mining  dan  Data  Warehouse     Universitas  Mercu  Buana  Yogyakarta    

2  

Pokok  Bahasan   •  Algoritma  C4.5  

12/5/13  

Data  Mining  dan  Data  Warehouse   Universitas  Mercu  Buana  Yogyakarta    

3  

Supervised  Learning  à  Klasifikasi   Nasabah     Tabungan  

Aset  

Pendapatan  

Risiko     Kredit  

A  

Sedang  

Tinggi  

75  

Baik  

B  

Rendah  

Rendah  

50  

Buruk  

C  

Tinggi  

Sedang  

25  

Buruk  

D  

Sedang  

Sedang  

50  

Baik  

E  

Rendah  

Sedang  

100  

Baik  

F  

Tinggi  

TInggi  

25  

Baik  

G  

Rendah  

Rendah  

25  

Buruk  

H  

Sedang  

Sedang  

75  

Baik  

I  

Tinggi  

Rendah  

50  

?  

12/5/13  

K l a s i fi k a s i   d i g u n a k a n   u n t u k   mengetahui   variabel   target   jika   diketahui   hubungan   tersembunyi   antara  variabel  input.   Tabel   di   samping   contoh   dari   masalah   yang   dapat   diselesaikan   dengan   tugas   data  mining  klasifikasi.     Variabel  target  dari  masalah  ini  adalah   resiko  kredit.   Sedangkan   variabel   inputnya   adalah   tabungan,  aset,  dan  pendapatan.  

Data  Mining  dan  Data  Warehouse   Universitas  Mercu  Buana  Yogyakarta    

4  

Algoritma  C4.5  (1)   •  Algoritma  C4.5  merupakan  algoritma  yang  digunakan  untuk  membentuk   pohon  keputusan.   •  Dapat  diekspresikan  dalam  bentuk  bahasa  basis  data  seperti  SQL  untuk   mencari  record  pada  kategori  tertentu.   •  Berguna  untuk  mengeksplorasi  data,  menemukan  hubungan  tersembunyi   antara  sejumlah  calon  variabel  input  dengan  sebuah  variabel  target.   •  Proses  pada  pohon  keputusan  adalah  mengubah  bentuk  data  (tabel)   menjadi  model  pohon,  mengubah  model  pohon  menjadi  rule,  dan   menyederhanakan  rule  (Basuki  &  Syarif,  2003)   12/5/13  

Data  Mining  dan  Data  Warehouse   Universitas  Mercu  Buana  Yogyakarta    

5  

Algoritma  C.45  (2)   Langkah-­‐langkah  secara  umum:   1.  Pilih  atribut  sebagai  akar  (root)   2.  Buat  cabang  untuk  tiap-­‐tiap  nilai   3.  Bagi  kasus  dalam  cabang   4.  Ulangi  proses  untuk  setiap  cabang  (langkah  1,  2,  dan   3)  sampai  semua  kasus  pada  cabang  memiliki  kelas   yang  sama.   12/5/13  

Data  Mining  dan  Data  Warehouse   Universitas  Mercu  Buana  Yogyakarta    

6  

Contoh  Kasus  (1)   •  Diberikan  beberapa  data  tentang  keputusan   bermain  tenis.   •  Buatlah  pohon  keputusan  dengan  algoritma   c4.5  agar  kelak  kita  dapat  memutuskan   bermain  atau  tidak  jika  diketahui  informasi   lainnya.   12/5/13  

Data  Mining  dan  Data  Warehouse   Universitas  Mercu  Buana  Yogyakarta    

7  

Contoh  Kasus  (2)  

12/5/13  

Data  Mining  dan  Data  Warehouse   Universitas  Mercu  Buana  Yogyakarta    

8  

Penyelesaian     1.  Tentukan  mana  variabel  tujuan,  mana   variabel  input.   2.  Lakukan  tahap-­‐tahap  algoritma  C4.5  pada   variabel  input  untuk  menentukan  variabel   tujuan.  

12/5/13  

Data  Mining  dan  Data  Warehouse   Universitas  Mercu  Buana  Yogyakarta    

9  

Penentuan  Variabel  Tujuan  dan     Variabel  Input   •  Berdasar  tabel  dan  pertanyaan,  maka  dapat   dituliskan  bahwa:   –  Variabel  tujuan  adalah  kolom  “play”   –  Variabel  input  adalah  kolom  “outlook”,   “temperature”,  “humidity”,  “windy”  

12/5/13  

Data  Mining  dan  Data  Warehouse   Universitas  Mercu  Buana  Yogyakarta    

10  

Langkah  1:  Pilih  atribut  sebagai  akar  (1)     •  Untuk  memilih  atribut  sebagai  akar,  didasarkan  pada  nilai   gain  tertinggi  dari  variabel  input.  Rumusnya:  

Keterangan:   S  =  himpunan  kasus   A  =  atribut   n  =  jumlah  partisi  atribut  A   |Si|  =  jumlah  kasus  pada  partisi  ke-­‐1   |S|  =  jumlah  kasus  dalam  S   12/5/13  

Data  Mining  dan  Data  Warehouse   Universitas  Mercu  Buana  Yogyakarta    

11  

Langkah  1:  Pilih  atribut  sebagai  akar  (2)     •  Sedangkan  untuk  mencari  nilai  entrophy,  digunakan  rumus   berikut  ini:  

Keterangan:   S  =  himpunan  kasus   n  =  jumlah  partisi  S   pi    =  proporsi  dari  Si  terhadap  S  

12/5/13  

Data  Mining  dan  Data  Warehouse   Universitas  Mercu  Buana  Yogyakarta    

12  

Langkah  1:  Pilih  atribut  sebagai  akar  (3)     •  Hasil  perhitungan  gain  pada  masing-­‐masing  atribut  adalah  seperti  tertera   pada  tabel  perhitungan  node  1  berikut  ini:  

12/5/13  

Data  Mining  dan  Data  Warehouse   Universitas  Mercu  Buana  Yogyakarta    

Tips  mengitung  nilai   entrophy:     Jika  salah  satu  nilai   dari  kolom  “ya”  dan   “tidak”  ada  yang   nilainya  “0”,  maka   dipastikan  nilai   entrophy  juga  “0”     Jika  nilai  kolom  “ya”   dan  “tidak”  bernilai   sama,  maka   entrophy  bernilai  “1’   13  

Langkah  1:  Pilih  atribut  sebagai  akar  (4)     •  Pada  tabel  tersebut  dapat  dilihat  bahwa  nilai  gain  tertinggi   adalah  pada  artibut  “humidity”,  yaitu  0,3705065.   •  Maka  atribut  “humidity”  ini  adalah  akar  dari  pohon   keputusan.  

12/5/13  

Data  Mining  dan  Data  Warehouse   Universitas  Mercu  Buana  Yogyakarta    

14  

Langkah  2:  buat  cabang  untuk  masing-­‐ masing  nilai  

Keterangan:   Pengisian  cabang   berdasar  pada  nilai   yang  ada  di  kolom   humidity,  yaitu  high   dan  normal  (lihat   soal).   12/5/13  

Data  Mining  dan  Data  Warehouse   Universitas  Mercu  Buana  Yogyakarta    

15  

Langkah  3:  Bagi  kasus  dalam  cabang  

Keterangan:   Humidity  memiliki  dua  nilai,  high  dan  normal.  Pada  perhitungan  node  1,  untuk  nilai   normal  menghasilkan  7  keputusan  yes  dan  0  keputusan  no.  Artinya  untuk  semua  nilai   humidity  normal  keputusannya  adalah  yes,  maka  anak  cabang  dari  normal  adalah  yes.     Sedangkan  untuk  high,  terdapat  3  keputusan  yes  dan  4  keputusan  no.  Artinya  untuk   nilai  high  belum  jelas  keputusannya,  maka  anak  cabang  dari  high  perlu  dicari  kembali   (perhitungan  node  2)     12/5/13  

Data  Mining  dan  Data  Warehouse   Universitas  Mercu  Buana  Yogyakarta    

16  

Langkah  4:  ulangi  langkah  1,  2,  dan  3  sampai   tidak  ada  percabangan  lagi  (1).   •  Penentuan  anak  cabang  untuk  humidity  “high”  

12/5/13  

Data  Mining  dan  Data  Warehouse   Universitas  Mercu  Buana  Yogyakarta    

17  

Langkah  4:  ulangi  langkah  1,  2,  dan  3  sampai   tidak  ada  percabangan  lagi  (2)   •  Pada  tabel  tersebut  dapat  dilihat  bahwa  nilai  gain  tertinggi   adalah  pada  artibut  “outlook”,  yaitu  0,69951385.   •  Maka  atribut  “outlook”  ini  adalah  anak  cabang  dari   humidity  “high”.  

12/5/13  

Data  Mining  dan  Data  Warehouse   Universitas  Mercu  Buana  Yogyakarta    

18  

Langkah  4:  ulangi  langkah  1,  2,  dan  3  sampai   tidak  ada  percabangan  lagi  (3)  

Keterangan:   Outlook  memiliki  tiga  nilai  yaitu:  sunny,  cloudy,  dan  rainny.  Pada  perhitungan  node  2,   dapat  dilihat  untuk  semua  nilai  outlook  sunny  keputusannya  adalah  no.  Untuk  semua   nilai  cloudy  keputusannya  adalah  yes.         Sedangkan  untuk  rainny  belum  jelas  keputusannya,  maka  anak  cabang  dari  rainny  perlu   dicari  kembali  (perhitungan  node  3)     12/5/13  

Data  Mining  dan  Data  Warehouse   Universitas  Mercu  Buana  Yogyakarta    

19  

Langkah  4:  ulangi  langkah  1,  2,  dan  3  sampai   tidak  ada  percabangan  lagi  (4).   •  Penentuan  node  untuk  outlook  “rainny”  

12/5/13  

Data  Mining  dan  Data  Warehouse   Universitas  Mercu  Buana  Yogyakarta    

20  

Langkah  4:  ulangi  langkah  1,  2,  dan  3  sampai   tidak  ada  percabangan  lagi  (5)   •  Pada  tabel  tersebut  dapat  dilihat  bahwa  nilai  gain  tertinggi  adalah  pada   artibut  “windy”,  yaitu  1.   •  Maka  atribut  “windy”  ini  adalah  anak  cabang  dari  outlook  “rainny”.  

12/5/13  

Data  Mining  dan  Data  Warehouse   Universitas  Mercu  Buana  Yogyakarta    

21  

Langkah  4:  ulangi  langkah  1,  2,  dan  3  sampai   tidak  ada  percabangan  lagi  (6)  

Keterangan:   Windy  memiliki  dua  nilai  yaitu:  true  dan  false.  Pada  perhitungan  node  3,  dapat  dilihat   untuk  semua  nilai  windy  true  keputusannya  adalah  no.  Untuk  semua  nilai  false   keputusannya  adalah  yes.         Karena  pada  kondisi  ini  semua  anak  cabang  telah  jelas,  maka  perhitungan  berhenti.   12/5/13  

Data  Mining  dan  Data  Warehouse   Universitas  Mercu  Buana  Yogyakarta    

22  

Hasil  Akhir  Klasifikasi  (1)  

12/5/13  

Data  Mining  dan  Data  Warehouse   Universitas  Mercu  Buana  Yogyakarta    

23  

Hasil  Akhir  Klasifikasi  (2)   •  Dari  pohon  keputusan  tersebut  dapat  dibuat  suatu   rumusan:   –  Humidity:  Normal  à  main  tenis   –  Humidity:  High,  Outlook:  Cloudy  à  main  tenis   –  Humidity:  High,  Outlook:  Sunny  à  tidak  main  tenis   –  Humidity:  High,  Outlook:  Rainny,  Windy:  false  à  main  tenis   –  Humidity:  High,  Outlook:  Rainny,  Windy:  trueà  tidak  main   tenis  

12/5/13  

Data  Mining  dan  Data  Warehouse   Universitas  Mercu  Buana  Yogyakarta    

24  

Implementasi   Data  mining  tugas  klasifikasi  (algoritma  c4.5)   dengan  php-­‐mysql  

12/5/13  

Data  Mining  dan  Data  Warehouse     Universitas  Mercu  Buana  Yogyakarta    

25  

Pertanyaan  ???  

12/5/13  

Data  Mining  dan  Data  Warehouse     Universitas  Mercu  Buana  Yogyakarta    

26  

Kuis  (1)   • 

Diberikan  data  sebagai  berikut:  

12/5/13  

Data  Mining  dan  Data  Warehouse     Universitas  Mercu  Buana  Yogyakarta    

27  

Kuis  (2)   •  Buatlah  pohon  keputusan  yang  dapat   mengklasifikasikan  rekomendasi  lensa   berdasar  atribut  yang  lain!  

12/5/13  

Data  Mining  dan  Data  Warehouse     Universitas  Mercu  Buana  Yogyakarta    

28