Classification (1) Classification (3) Classification (2) Contoh Classification. Classification (4)

Knowledge Discovery in Databases (IS704) dan Data Mining (CS704)

Classification (1) Sebelum bicara terlalu jauh, adalah baik jika kita mencoba memperhatikan beberapa captured slides yang menarik untuk memahami hakikat dasar Machine Learning Sumber: www.cs.ucr.edu/~eamonn/205/MachineLearning.ppt.

Kuliah #5: Classification (Bagian 1)

– “The Pigeon Problem” Jangan lupakan bahwa Data Mining adalah irisan dari salah satu subdisiplin Artificial Intelligence

Gunawan

– Machine Learning. Learning

Jurusan Teknik Informatika Sekolah Tinggi Teknik Surabaya Revisi 14 Agustus 2007

1 October 2007

Gunawan, Teknik Informatika STTS

Classification (2)

Classification (3)

Termasuk dalam Data Mining Task: Predictive Modeling. Diberikan himpunan examples (instances) yang telah dipreklasifikasi (dilabeli) sebelumnya, {p1,t1}, {p2,t2}, ..... {pn,tn}, konstruksilah sebuah model yang dapat menyarikan pengetahuan dalam examples tersebut dan dapat digunakan untuk keperluan prediksi, yaitu memprediksi class/target dari instance yang belum dilabeli.

Ukuran sukses klasifikasi biasanya diukur dengan menguji data baru (fresh data) yang tidak digunakan sebagai training set, tetapi labelnya juga telah diketahui sebelumnya sebelumnya. Kemudian dihitung proporsi jumlah data/instance yang dapat diklasifikasi secara benar (akurasinya). Dikenal term-term seperti 80:20 atau 75:25 atau 70:30 yang menunjukkan perbandingan persentase (training set : testing set).

– pi adalah vektor input, sedangkan ti adalah target (class) terkait. – Examples yang digunakan untuk membentuk model disebut

sebagai training set.

1 October 2007


3

1 October 2007


2

4

Contoh Classification

Classification (4)

Diberikan examples berikut:

Definisi yang lebih memperjelas peran classification dalam mining database: – Diberikan sebuah database P = {p1, p2, ....., pn} dari

sejumlah tuples (atau items / records / examples / instances) dan himpunan class T = {t1, t2, ....., tm}, classification problem adalah mendefinisikan suatu pemetaan f : P Æ T yang mengarahkan pi ke dalam salah satu class tj.

Walaupun terdapat model lainnya (mis. Naïve Bayes), model yang mendefinisikan pemetaan tersebut biasanya berupa varian dari:

Bangunlah sebuah model yang dapat memprediksi class dari instance outlook=sunny, temperature=hot, humidity=low, dan windy=true.

– Classification rules – Classification tree 1 October 2007


5

1 October 2007


6

1

Masalah pada Jenis Atribut yang Diklasifikasi

Termasuk pada Target Atributnya Input Attributes dan Target Atrribute, semua numerik:

Terdapat 2 (dua) tipe utama atribut:

Cycle time (ns)

– Numerik – nilai-nilainya adalah angka.

MYCT

MMIN

MMAX

CACH

CHMIN

CHMAX

PRP

1

125

256

6000

256

16

128

198

2

29

8000

32000

32

8

32

269

… 207

… 125

… 2000

… 8000

… 0

… 2

… 14

… 52

208

480

512

8000

32

0

0

67

209

480

1000

4000

0

0

0

45

– Nominal – nilai-nilainya termasuk dalam beberapa kemungkinan yang

jumlahnya terbatas dan dispesifikasi sebelumnya.

Main memory (Kb)

Cache (Kb)

Channels

Performance

Solusi “Tidak Sederhana” Sederhana” Linear Regression: PRP = -55.9 + 0.0489 MYCT + 0.0153 MMIN + 0.0056 MMAX + 0.6410 CACH - 0.2700 CHMIN + 1480 CHMAX 1 October 2007


7

1 October 2007

8

Algoritma 1R

1R

FOR EACH atribut FOR EACH value dari atribut ini, bentuk sebuah rule sets dengan cara Menghitung seberapa sering sebuah kelas dihasilkan dari pasangan atribut=value ini D Dapatkan tk sebuah b h kelas k l yang paling li b banyak k dihasilkan atribut dengan value ini Tambahkan sebuah rule “IF atribut = value THEN kelas” ke dalam rule sets Hitunglah tingkat kesalahan dari rules set ini Pilihlah sebuah rules set dengan tingkat kesalahan terkecil

Diperkenalkan oleh R.C. Holte (1983).(*) Dikenal juga dengan “1-R Holte”. 1R sendiri adalah kependekan dari “1-rule” atau “Infering Rudimentary Rule” (?) Output algoritma 1R adalah “one level decision tree” yang dapat j juga j g melalui sebuah classification rule sets. disajikan 1R tidak menekankan akurasi sempurna atau 100% benar pada rule sets yang dihasilkan. 1R tidak pernah dipertimbangkan sebagai salah satu pendekatan formal dalam Machine Learning atau Data Mining. Namun tetap harus diingat: “Mengapa harus dipusingkan dengan sebuah decision tree yang kompleks, ketika sebuah rule sets sederhana dapat melakukannya?” (*) Holte, R.C. 1993. Very simple classification rules perform well on most commonly used datasets. Machine Learning, 11:63-90. 1 October 2007



9

1 October 2007


10

Weather Problem Datasets Outlook Sunny Sunny Overcast Rain Rain Rain Overcast Sunny Sunny Rain Sunny Overcast Overcast Rain 1 October 2007

Temperature Hot Hot Hot Mild Cool Cool Cool Mild Cool Mild Mild Mild Hot Mild

Humidity High High High High Normal Normal Normal High Normal Normal Normal High Normal High


Windy Weak Strong Weak Weak Weak Strong Strong Weak Weak Weak Strong Strong Weak Strong

Play No No Yes Yes Yes No Yes No Yes Yes Yes Yes Yes No

1R-Holte untuk Weather Problem

Tanda * = Pilihan Random 11

1 October 2007


12

2

PRISM

Prinsip Algoritma Covering

Diperkenalkan oleh J. Cendrowska (1987).(*) Termasuk kategori algoritma covering, berbeda dengan ID3 yang termasuk dalam kategori algoritma divide and conquer. Disebut dengan pendekatan covering, karena pada setiap g diidentifikasi rule yyang g mengcover g sejumlah j stage instances. Output algoritma PRISM adalah sejumlah classification rules. PRISM hanya menghasilkan rule-rule yang sempurna atau 100% benar.

Space untuk semua instances/examples Yang dicover rules sejauh ini Rules yang akan ditambahkan kemudian

Classification Rules untuk Masalah yang Sama: IF x<=1.2 THEN kelas=b IF x>1.2 AND y>2.6 THEN kelas=a IF x>1.2 AND y<=2.6 THEN kelas=b

(*) Cendrowska, J. (1987). PRISM: an Algorithm for Inducing Modular Rules. International Journal of Man-Machine Studies, Vol. 27, No. 4, pp. 349-370. 1 October 2007


Bagaimana dengan Decision Treenya? 13

1 October 2007


14

Contact Lens Dataset Algoritma PRISM

Berdasarkan kondisi apa seorang ahli optik akan menyarankan seseorang yang mengalami gangguan mata: menggunakan soft contact-lense, menggunakan hard contact-lenses, atau justru tidak disarankan menggunakan contact-lense? Diperkenalkan juga oleh J. Cendrowska. Catatan terms:

FOR EACH kelas c Inisialisasi E dengan instance set WHILE E mengandung instances dalam kelas C Bentuk sebuah rule dengan LHS kosong yang meprediksi kelas C UNTIL R sempurna (tak ada atribut yang dapat dipakai), lakukan FOR EACH atribut A yang tidak termasuk R R,dan dan tiap nilai v v, Pertimbangkan untuk menambah kondisi A=v pada LHS dari R Pilih A dan v untuk memaksimalkan akurasi p/t (tips: pilih kondisi dengan nilai P yang terbesar) Tambahkan A=v ke dalam R Hapuslah semua instance yang tercover oleh R dari E

– spectacle p pprescription p = pperuntukan kaca mata yyang g diketahui – myope = rabun dekat – hypermetrope = rabun jauh – astigmatism = pandangan kabur, "lack of point focus…..”, “an

astigmatism refers to an irregular curvature of the cornea”. – presbyopic ( > +45 tahun) = batas usia lazimnya untuk mampu melihat

obyek pada jarak jauh (45 tahun)

Catatan: p = positive examples dari suatu kelas t = total instances

1 October 2007

– pre-presbyopic ( < +45 tahun) = sebelum masa presbyopic Sumber term: WordNet 2.0, http://www.allaboutvision.com/askdoc/astigmatism.htm


15

Contact Lens Dataset age young young young young young young young young pre-presbyopic pre-presbyopic pre-presbyopic p p y p pre-presbyopic pre-presbyopic pre-presbyopic pre-presbyopic pre-presbyopic presbyopic presbyopic presbyopic presbyopic presbyopic presbyopic presbyopic presbyopic

1 October 2007

spectacle prescription myope myope myope myope hypermetrope hypermetrope hypermetrope hypermetrope myope myope myope y p myope hypermetrope hypermetrope hypermetrope hypermetrope myope myope myope myope hypermetrope hypermetrope hypermetrope hypermetrope

Astigmatism no no yes yes no no yes yes no no yes y yes no no yes yes no no yes yes no no yes yes

tear production rate reduced normal reduced normal reduced normal reduced normal reduced normal reduced normal reduced normal reduced normal reduced normal reduced normal reduced normal reduced normal


1 October 2007


16

PRISM untuk Contact Lens (#1)

reccomended lenses none soft none hard none soft none hard none soft none hard none soft none none none none none hard none soft none none

Dibentuk rule yang mengcover setiap class: hard,soft, dan none. Misalnya dimulai dari hard. IF ? THEN recommended = hard Untuk kondisi pada LHS yang masih kosong terdapat 9 pilihan: age = young age = pre-presbyopic age = presbyopic spectacle prescription spectacle prescription astigmatism = no astigmatism = yes tear production rate = tear production rate =

= myope = hypermetrope

reduced normal

2/8 1/8 1/8 3/12 1/12 0/12 4/12 0/12 4/12

dipilih bagian yang terbesar = 4/12, secara acak dipilih salah satu antara nomor 7 dan nomor 9 pada daftar di atas, misalnya nomor 7: IF astigmatism = yes THEN recommended = hard 17

1 October 2007


18

3



Rule If astigmatism = yes then recommended = hard jelas tidak akurat. Lihat tabel berikut:

IF astigmatism = yes AND ? THEN recommended = hard

age young young young young pre-presbyopic pre-presbyopic pre presbyopic pre-presbyopic pre-presbyopic presbyopic presbyopic presbyopic presbyopic

spectacle prescription myope myope hypermetrope hypermetrope myope myope hypermetrope hypermetrope myope myope hypermetrope hypermetrope

Astigmatism yes yes yes yes yes yes yes yes yes yes yes yes

tear production rate reduced normal reduced normal reduced normal reduced normal reduced normal reduced normal

Untuk kondisi pada LHS yang masih kosong terdapat 7 pilihan: age = young age = pre-presbyopic age = presbyopic spectacle prescription spectacle prescription tear production rate = tear production rate =

reccomended lenses none hard none hard none hard none none none hard none none

= myope = hypermetrope reduced normal

2/4 1/4 1/4 3/6 1/6 0/6 4/6

dipilih bagian yang terbesar = 4/6, yaitu nomor 6: IF astigmatism = yes AND tear production rate = normal THEN recommended = hard

Sebenarnya untuk sebuah class (misalnya hard), algoritma dapat dipaksa berhenti (misalnya disini pada kasus contact lens). Namun, bagaimana jika exact rule harus diperoleh, tanpa mempedulikan sekompleks apapun rulenya?

Tampak bahwa rule tersebut hanya mengcover 4 instance yang benar dari total 12 instances. Sehingga refinement perlu dilakukan untuk rule: IF astigmatism = yes AND ? THEN

recommended = hard 1 October 2007


19

1 October 2007


20



Rule IF astigmatism = yes AND tear production rate = normal THEN recommended = hard jelas masih belum akurat. Lihat tabel berikut:

IF astigmatism = yes AND tear production rate = normal AND ? THEN recommended = hard

age

spectacle prescription young myope young hypermetrope pre-presbyopic myope pre-presbyopic b i hypermetrope h t presbyopic myope presbyopic hypermetrope

Astigmatism yes yes yes yes yes yes

tear production rate normal normal normal normall normal normal

Untuk kondisi pada LHS yang masih kosong terdapat 5 pilihan:

reccomended lenses hard hard hard none hard none

age = young age = pre-presbyopic age = presbyopic spectacle prescription = myope spectacle prescription = hypermetrope

Sehingga harus dipilih bagian yang terbesar, tetapi yang mana? 2/2 atau 3/3? Dalam hal ini “sebaiknya dipilih yang mengcover lebih banyak instance”, atau nomor 4, sehingga rule sejauh ini adalah: IF astigmatism = yes AND tear production rate = normal AND spectacle presciption = myope THEN recommended = hard

Tampak bahwa rule tersebut hanya mengcover 4 instance yang benar dari total 6 instances. Sehingga refinement perlu dilakukan kembali untuk rule:

IF astigmatism = yes AND tear production rate = normal AND ? THEN recommended = hard

1 October 2007


2/2 1/2 1/2 3/3 1/3

21

1 October 2007




Karena rule IF astigmatism = yes AND tear production rate = normal AND spectacle prescription = myope THEN recommended = hard sudah akurat. Lihat tabel berikut:

Dengan cara yang sama pada stage sebelumnya, berturut-turut diperoleh: – age = young, adalah yang terbaik untuk condition pertama (mengcover 1 dari 7). Mengapa angka 7 ? – astigmatism = yes, adalah yang terbaik untuk condition kedua (dipilih 1/3). Apakah pilihan ini karena “tips” ? – tear production rate = normal, adalah yang terbaik untuk condition ketiga (dipilih 1/1). Rule yang diperoleh adalah: IF age = young AND antigmatism = yes AND tear production rate = normal THEN recommended = hard sudah akurat. Mengcover 1/1? Atau 3/3? Jadi seluruh kasus hard telah tercover, sehingga langkah-langkah berikutnya adalah untuk kasus soft dan none.

age

spectacle prescription young myope pre-presbyopic myope presbyopic myope

astigmatism yes yes yes

tear production rate normal normal normal

reccomended lenses hard hard hard

Tampak bahwa rule tersebut hanya mengcover 3 instance yang benar dari total 24 instances, dan baru 3 dari 4 instance untuk recommended = hard. Selanjutnya 3 instance pada tabel di atas dihapus dari total 24 instances, dan mencari rule lainnya dengan bentuk:

IF ? THEN recommended = hard 1 October 2007


23

1 October 2007


22

24

4



Koleksi Rule Lengkap pada Akhir Proses (9 Rule)

akhirnya.....

• If spectacle prescription = myope and astigmatic = yes and tear production rate = normal then recommendation = hard • If age = young and astigmatic = yes and tear production rate = normal then recommendation = hard • If age = young and astigmatic = no and tear production rate = normal then recommendation = soft • If age = pre-presbyopic and astigmatic = no and tear production rate = normal then recommendation = soft • If spectacle prescription = hypermetrope and astigmatic = no and tear production rate = normal then recommendation = soft • If tear production rate = reduced then recommendation = none • If age = presbyopic and spectacle prescription = myope and astigmatic = no then recommendation = none • If age = pre-presbyopic and spectacle prescription = hypermetrope and astigmatic = yes then recommendation = none • If age = presbyopic and spectacle prescription = hypermetrope and astigmatic = yes then recommendation = none 1 October 2007


AWAS!!! JANGAN G DICOBA CO untuk mengatasi Gangguan Mata Anda yang sebenarnya.

25

1 October 2007


26

5

Classification (1) Classification (3) Classification (2) Contoh Classification. Classification (4)

Recommend Documents