Rule-Based Classifier. Data Mining Pengklasifikasian: Rule-based Classifier. Catatan Kuliah untuk Bab 4. Pengantar Data Mining

http://staffsite.gunadarama.ac.id/didi/

Data Mining Pengklasifikasian: Rule-based Classifier

Rule-Based Classifier z

Mengklasifikasikan record dengan menggunakan koleksi aturan “if…then…”

z

Aturan/Rule:

Catatan Kuliah untuk Bab 4 Pengantar Data Mining oleh Tan, Steinbach, Kumar

Pengantar Data Mining

4/18/2004

1

Rule-based Classifier (Contoh) Name

human python salmon whale frog komodo bat pigeon cat leopard shark turtle penguin porcupine eel salamander gila monster platypus owl dolphin eagle

Blood Type

warm cold cold warm cold cold warm warm warm cold cold warm warm cold cold cold warm warm warm warm

Give Birth

yes no no yes no no yes no yes yes no no yes no no no no no yes no

Can Fly

no no no no no no yes yes no no no no no no no no no yes no yes

Live in Water

no no yes yes sometimes no no no no yes sometimes sometimes no yes sometimes no no no yes no


Kondisi adalah konjungsi atribut-atribut

y adalah label kelas

(Blood Type=Warm) ∧ (Lay Eggs=Yes) → Birds

(Taxable Income < 50K) ∧ (Refund=Yes) → Evade=No

© Tan,Steinbach, Kumar


4/18/2004

2

Aplikasi dari Rule-Based Classifier

Class

mammals reptiles fishes mammals amphibians reptiles mammals birds mammals fishes reptiles birds mammals fishes amphibians reptiles mammals birds mammals birds

z

Aturan r menutupi (covers) contoh x ijika atribut dari contoh tersebut memenuhi kondisi dari aturan itu R1: (Give Birth = no) ∧ (Can Fly = yes) → Birds

R2: (Give Birth = no) ∧ (Live in Water = yes) → Fishes R3: (Give Birth = yes) ∧ (Blood Type = warm) → Mammals R4: (Give Birth = no) ∧ (Can Fly = no) → Reptiles R5: (Live in Water = sometimes) → Amphibians Name

R1: (Give Birth = no) ∧ (Can Fly = yes) → Birds R2: (Give Birth = no) ∧ (Live in Water = yes) → Fishes R3: (Give Birth = yes) ∧ (Blood Type = warm) → Mammals R4: (Give Birth = no) ∧ (Can Fly = no) → Reptiles R5: (Live in Water = sometimes) → Amphibians © Tan,Steinbach, Kumar

– LHS: aturan antecedent atau kondisi – RHS: rule consequent – Contoh aturan pengklasifikasian:

dialihbahasakan oleh Tim Pengajar Konsep Data Mining Universitas Gunadarma


(Kondisi) → y

– dimana

4/18/2004

hawk grizzly bear

Blood Type

warm warm

Give Birth

Can Fly

Live in Water

Class

no yes

yes no

no no

? ?

The rule R1 covers a hawk => Bird The rule R3 covers the grizzly bear => Mammal 3



4/18/2004

4

Lingkup Aturan dan Keakurasiannya Lingkup aturan: – Pecahkan recordrecord yang memenuhi antecedent aturan z Keakurasian aturan: – Pecahkan recordrecord yang memenuhi antecedent dan consequent aturan z


Cara kerja Rule-based Classifier

Tid Refund Marital Status

Taxable Income Class

R1: (Give Birth = no) ∧ (Can Fly = yes) → Birds

1

Yes

Single

125K

No

R3: (Give Birth = yes) ∧ (Blood Type = warm) → Mammals

2

No

Married

100K

No

R4: (Give Birth = no) ∧ (Can Fly = no) → Reptiles

3

No

Single

70K

No

R5: (Live in Water = sometimes) → Amphibians

4

Yes

Married

120K

No

5

No

Divorced 95K

Yes

6

No

Married

No

7

Yes

Divorced 220K

8

No

Single

85K

Yes

9

No

Married

75K

No

10

No

Single

90K

Yes

60K

No

z


Give Birth

Can Fly

Live in Water

Class

yes no yes

no no no

no sometimes yes

? ? ?

Turtle memicu R4 dan R5 Dogfish shark tidak memicu satu aturan pun

Coverage = 40%, Accuracy = 50% 4/18/2004

5

4/18/2004



4/18/2004

6

Dari Pohon Keputusan ke Aturan (Rules)

Aturan Exhaustive – Classifier memiliki lingkupan exhaustive jika mencatat untuk setiap kemungkinan kombinasi nilai atribut – Setiap record paling sedikit dilingkupi oleh satu aturan


Blood Type

warm cold cold

Lemur memicu aturan R3, maka ia diklasifikasikan sebagai mammal

(Status=Single) → No

Aturan Mutually exclusive – Pengklasifikasi (Classifier) mengandung aturan mutually exclusive jika aturan-aturan independen satu sama lain – Setiap record paling banyak dilingkupi oleh satu aturan


Name

lemur turtle dogfish shark

10

Karakteristik Rule-Based Classifier z

R2: (Give Birth = no) ∧ (Live in Water = yes) → Fishes

7

Aturan Pengklasifikasian (Refund=Yes) ==> No

Refund Yes

No

NO

Marita l Status

{Single, Divorced}

{Married}

NO

(Refund=No, Marital Status={Single,Divorced}, Taxable Income>80K) ==> Yes (Refund=No, Marital Status={Married}) ==> No

NO

Taxable Income < 80K

(Refund=No, Marital Status={Single,Divorced}, Taxable Income<80K) ==> No

> 80K YES

Aturan bersifat mutually exclusive dan exhaustive Himpunan atturan mengandung Himpunan aturan informasi sebanyak pada Pohon



4/18/2004

8

Suatu Aturan dapat disederhanakan

Efek dari Penyederhanaan Aturan

Tid Refund Marital Status

Taxable Income Cheat

1

Yes

Single

125K

No

2

No

Married

100K

No

3

No

Single

70K

No

4

Yes

Married

120K

No

5

No

Divorced 95K

6

No

Married

7

Yes

Divorced 220K

No

8

No

Single

85K

Yes

9

No

Married

75K

No

10

No

Single

90K

Yes

z

Refund Yes

No

NO

Marita l Status

{Single, Divorced}

{Married} NO

Taxable Income < 80K

> 80K

NO

YES

Himpunan aturan terurut Unordered rule set – menggunakan skema voting

No

z

10

Aturan tidak lagi bersifat exhaustive – Satu record dapat tidak memicu satupun aturan – Solusi?

(Refund=No) ∧ (Status=Married) → No

Aturan Awal:

Himpunan aturan terurut (Ordered rule set)

Yes

60K

Aturan tidak lagi bersifat mutually exclusive – Satu record dapat memicu lebih dari satu aturan – Solusi?

Menggunakan kelas default

Aturan yang disederhanakan: (Status=Married) → No © Tan,Steinbach, Kumar


4/18/2004

9

Himpunan Aturan Terurut z


4/18/2004

10

Skema Pengurutan Aturan

Aturan dirangking terurut sesuai dengan prioritasnya

z

Pengurutan berbasis Aturan (Rule-based ordering)

z

Pengurutan berbasis Kelas (Class-based ordering)

– Aturan individual di rangking berdasarkan pada kualitasnya

– Himpunan aturan terurut dikenal sebagai daftar keputusan

z


Ketika record test disajikan ke dalam

– Aturan yang dimiliki oleh kelas yang sama akan muncul bersamaan

– Maka ia akan ditugaskan ke label kelas dari aturan dengan ranking tertinggi yang telah dipicu – Jika tidak ada satupun aturan yang dikeluarkan, maka akan ditugaskan ke kelas default R1: (Give Birth = no) ∧ (Can Fly = yes) → Birds

R2: (Give Birth = no) ∧ (Live in Water = yes) → Fishes R3: (Give Birth = yes) ∧ (Blood Type = warm) → Mammals R4: (Give Birth = no) ∧ (Can Fly = no) → Reptiles R5: (Live in Water = sometimes) → Amphibians Name

turtle © Tan,Steinbach, Kumar

Blood Type

cold

Give Birth

Can Fly

Live in Water

Class

no

no

sometimes

?


4/18/2004

11



4/18/2004

12

Membangun Aturan Pengklasifikasian z

Metode Langsung: Sequential Covering

Metode Langsung (Direct Method):

1.

Mengekstrak aturan langsung dari data misal: RIPPER, CN2, Holte’s 1R

2.

3. z

Metode Tidak Langsung (Indirect Method): Ekstraksikan aturan dari model klasifikasi lainnya (misal: pohon keputusan, neural networks, dll). misal: aturan C4.5



4/18/2004

4.

13

Contoh Sequential Covering

Mulai dari aturan hampa Kembangkan aturan menggunakan fungsi Learn-One-Rule Hilangkan record training yang dilingkupi oleh aturan Ulangi langkah (2) dan (3) hingga mencapai kriteria berhenti



4/18/2004

14

Contoh of Sequential Covering…

R1

R1

R2


(iii) Langkah 2

(ii) Langkah 1

(i) Data asal


4/18/2004

15


(iv) Langkah 3


4/18/2004

16

Aspek-aspek dari Sequential Covering z

Pertumbuhan Aturan Rule Growing

z

Instance Elimination

z

Evaluasi Aturan (Rule Evaluation)

z

Kriteria Berhenti (Stopping Criterion)

z

Pemangkasan Aturan (Rule Pruning)



Rule Growing z

4/18/2004

17

Rule Growing (Contoh) z


Algoritma CN2 :

z

z

18

z

R0: {} => class (initial rule) R1: {A} => class (rule after adding conjunct) Gain(R0, R1) = t [ log (p1/(p1+n1)) – log (p0/(p0 + n0)) ] where t: number of positive instances covered by both R0 and R1 p0: number of positive instances covered by R0 n0: number of negative instances covered by R0 p1: number of positive instances covered by R1 n1: number of negative instances covered by R1

4/18/2004

4/18/2004

20

Mengapa kita memerlukan eliminate instances?

Mengapa kita menghilangkan positive instances? – Untuk memastikan bahwa aturan selanjutnya akan berbeda

– Mulai dari aturan hampa: {} => class – Tambahkan konjungsi yang memaksimumkan pengukuran FOIL’s information gain :


4/18/2004

– Jika tidak maka aturan selanjutnya akan identik dengan aturan sebelumnya

Algoritma RIPPER:



Instance Elimination

– Mulai dari konjungsi hampa: {} – Tambahkan konjungsi yang meminimalkan pengukuran entropi : {A}, {A,B}, … – Tentutkan aturan konsekwen dengan mengambil kelas mayoritas/besar dari contoh yang dilingkupi aturan z

Dua strategi umum

Mengapa kita menghilangkan negative instances? – Untuk mencegah underestimating keakurasian aturan – Untuk Memmbadingkan aturan R2 dan R3 pada diagram

19



Stopping Criterion and Rule Pruning

Rule Evaluation z

Metrik: – Accuracy

– Laplace

n = c n

=

– M-estimate


nc + 1 n+k

=

nc + kp n+k

n : Number of instances covered by rule

z

Stopping criterion – Menghitung hasil yang didapat (gain) – Jika gain tidak signifikan, maka jangan perhatikan aturan yang bar

z

Rule Pruning – Serupa dengan pasca pemangkasan (post-pruning) pada pohon keputusan – Mereduksi Error Pruning:

nc : Number of instances covered by rule k : Number of classes

Hilangkan satu konjungsi dalam aturan Bandingkan tingkat error pada himpunan validasi sebelum dan sesudah pruning Jika error berubah, lakukan pemangkasan pada konjungsi

p : Prior probability


4/18/2004

21

Kesimpulan Metode Langsung z

Kembangkan aturan tunggal

z

Menghilangkan Instances dari aturan


z

z

Lakukan Pemangkasan aturan (jika diperlukan)

z

Tambah aturan ke dalam himpunan Current Rule

z

Ulangi langkah-langkah sebelumnya Pengantar Data Mining

4/18/2004

22

Metode Langsung : RIPPER

z



4/18/2004

23

Untuk permasalahan 2-kelas, pilih satu kelas sebagai kelas positif dan lainnya sebagai kelas negatif – Pelajari aturan untuk kelas positif – Kelas negatif sebagai kelas default Untuk permasalahan banyak-kelas – Urutkan kelas menurut kelaziman kelas meningkat (bagian dari instances yang dimiliki oleh kelas tertentu) – Pelajari himpunan aturan untuk kelas pertama (lakukan pertama kali) dan perlakukan sisanya sebagai kelas negatif – Ulangi dengan kelas terkecil selanjutnya sebagai kelas positif



4/18/2004

24

Metode Langsung : RIPPER z

Metode Langsung : RIPPER

Mengembangkan aturan: – Mulai dari aturan hampa – Tambah konjungsi apabila dapat merubah FOIL’s information gain – Berhenti ketika aturan tidak lagi melingkupi conothcontoh negatif – Pangkas aturan segera, menggunakan incremental reduced error pruning – Mengukur nilai pruning: v = (p-n)/(p+n)

z

Cari aturan terbaik yang melingkupi himpunan sekarang/terbaru dari contoh positif Eliminasi contoh positif dan negatif yang dilingkupi aturan

– Pada setiap aturan ditambahkan ke dalam himpunan aturan, maka hitung panjang deskripi yang baru

p: banyaknya contoh positif yang dilingkupi aturan dalam himpinan validasi n: banyaknya contoh negative yang dilingkupi aturan dalam himpinan validasi

hentikan penambahan aturan baru ketika panjang deskripsi yang baru lebih panjang d bits dibanding panjang deskripsi terkecil yang pernah didapat

– Metode Pangkas: Hapus semua barisan akhir dari kondisi yang memaksimumkan v © Tan,Steinbach, Kumar


4/18/2004

25

Metode Langsung : RIPPER z

Membangun himpunan Aturan: – Menggunakan algoritma sequential covering



4/18/2004

26

4/18/2004

28

Metode Tidak Langsung

Optimalkan himpunan aturan: – Untuk setiap aturan r dalam himpunan aturan R

Pertimbangkan 2 aturan alternatif: – Aturan Penggantian (r*): mengembagkan aturan baru dari mula – Aturan Revisi (r’): tambahkan konjungsi untuk memperluas aturanadd r

Bandingkan himpunan aturan r terhadap himpunan aturan r* dan r’

Pilih himpunan aturan yang meminimumkan prinsip MDL

– Ulangi pembangkitan aturan dan pengoptimalan aturan untuk sisa-sisa contoh positif



4/18/2004

27



Metode Tidak Langsung : C4.5rules

Metode Tidak Langsung : C4.5rules

Ekstrak aturan dari pohon aturan yang tidak dipangkas (unprunned) z Untuk tiap aturan, r: A → y, – Pertimbangkan aturan alternatif r’: A’ → y diman A’ didapat dengan memindahkan satu konjungsi di A – Bandingkan tingkat error pessimistic untuk r terhadap semua r – Pangkas jika satu dari rmempunyai tingkat error pessimistic lebih rendah – Ulangi sampai kita tidak dapat merubah error generalisasi

z

z



4/18/2004

29

Contoh Name

human python salmon whale frog komodo bat pigeon cat leopard shark turtle penguin porcupine eel salamander gila monster platypus owl dolphin eagle © Tan,Steinbach, Kumar

Lakukan pengurutan subset dari aturan (pengurutan kelas) – Setiap subset adalah koleksi aturan-aturan dengan aturan selanjutnya yang sama (kelas) – Hitung panjang deskripsi untuk setiapsubset Panjang deskripsi = L(error) + g L(model) g adalah parameter yang dibutuhkan kedalam akun kemunculan dari atribut redundan dalam himpunan aturan (nilai default = 0.5)



4/18/2004

30

C4.5 versus C4.5rules versus RIPPER Give Birth

yes no no yes no no yes no yes yes no no yes no no no no no yes no

Lay Eggs

no yes yes no yes yes no yes no no yes yes no yes yes yes yes yes no yes

Can Fly

no no no no no no yes yes no no no no no no no no no yes no yes


Live in Water Have Legs

no no yes yes sometimes no no no no yes sometimes sometimes no yes sometimes no no no yes no

yes no no no yes yes yes yes yes no yes yes yes no yes yes yes yes no yes

Class

4/18/2004

C4.5rules:

Give Birth?

mammals reptiles fishes mammals amphibians reptiles mammals birds mammals fishes reptiles birds mammals fishes amphibians reptiles mammals birds mammals birds

(Give Birth=No, Can Fly=Yes) → Birds (Give Birth=No, Live in Water=Yes) → Fishes

Yes

No

(Give Birth=Yes) → Mammals

Live In Water?

( ) → Amphibians

(Give Birth=No, Can Fly=No, Live in Water=No) → Reptiles

Mammals

Yes

RIPPER:

No

(Live in Water=Yes) → Fishes (Have Legs=No) → Reptiles

Sometimes Fishes

Yes

Birds

31


(Give Birth=No, Can Fly=No, Live In Water=No) → Reptiles

Can Fly?

Amphibians

(Can Fly=Yes,Give Birth=No) → Birds

No

() → Mammals

Reptiles


4/18/2004

32

C4.5 versus C4.5rules versus RIPPER

Keuntungan dari Rule-Based Classifiers

PREDICT ED CLASS Amphibians Fishes Reptiles Birds 2 0 0 ACT UAL Amphibians 0 2 0 CLASS Fishes 1 0 3 Reptiles 1 0 0 Birds 0 0 1 M ammals

0 0 0 3 0

M ammals 0 1 0 0 6

0 0 0 2 0

M ammals 2 0 1 1 4

RIPPER: PREDICT ED CLASS Amphibians Fishes Reptiles Birds 0 0 0 ACT UAL Amphibians 0 3 0 CLASS Fishes 0 0 3 Reptiles 0 0 1 Birds 0 2 1 M ammals


Sangat ekspresif seperti pohon keputusan Mudah diartikan/terjemahkan z Mudah untuk dibangkitkan z Dapat mengklasifikasikan instances baru dengan cepat z Kinerjanya dapat dibandingkan dengan pohon keputusan z

C4.5 dan C4.5rules:


4/18/2004

33

z



4/18/2004

34

Rule-Based Classifier. Data Mining Pengklasifikasian: Rule-based Classifier. Catatan Kuliah untuk Bab 4. Pengantar Data Mining

Recommend Documents