S1 Teknik Informatika Fakultas Teknologi Informasi Universitas Kristen Maranatha

S1 Teknik Informatika Fakultas Teknologi Informasi Universitas Kristen Maranatha

Pendahuluan Classification Decision tree induction Bayesian classification

DM-MA/S1IF/FTI/UKM/2010

2

Classification : ◦ klasifikasi data berdasarkan training set and nilai-nilai (class labels) dalam klasifikasi atribut, dan menggunakannya dalam klasifikasi data baru ◦ memprediksi label kelas secara kategorikal (diskrit/nominal)

Prediction memodelkan fungsi kontinyu, mis. prediksi nilai hilang atau tidak diketahui Contoh aplikasi ◦ ◦ ◦ ◦

Credit approval : pinjaman aman atau beresiko Target marketing : customer potensial Medical diagnosis Fraud detection

Teknik-teknik : ◦ Classification : decision tree induction, Bayesian classification, Bayesian belief network, neural network, k-nearest neighbour classifier, CBR, algoritma genetic, rough set, fuzzy logic ◦ Prediction : Linear, nonlinear, generalized linear regression DM-MA/S1IF/FTI/UKM/2010

3

Model construction: describing a set of predetermined classes ◦ Setiap sample diasumsikan termasuk predefined class, ditentukan oleh class label attribute ◦ Kumpulan sample yang dipakai untuk model construction : training set ◦ Model direpresentasikan sebagai classification rules, decision trees, atau l formula matematis

Model usage: classifying future or unknown objects ◦ Estimasi keakuratan model Label yang diketahui dari test sample dibandingkan dengan hasil klasifikasi dari model Accuracy rate = persentase dari kumpulan test sample yang diklasifikasikan dengan benar oleh model Test set bersifat independen terhadap training set ◦ Jika accuracy rate dapat diterima, pakai model untuk klasifikasi sample data yang class labelnya belum diketahui


4

Classification Algorithms

Training Data

NAM E M ike M ary Bill Jim Dave Anne

RANK YEARS TENURED Assistant Prof 3 no Assistant Prof 7 yes Professor 2 yes Associate Prof 7 yes Assistant Prof 6 no Associate Prof 3 no

Classifier (Model)

IF rank = ‘professor’ OR years > 6 THEN tenured = ‘yes’


5

Classifier Testing Data

Unseen Data (Jeff, Professor, 4)

NAME Tom Merlisa George Joseph

RANK YEARS TENURED Assistant Prof 2 no Associate Prof 7 no Professor 5 yes Assistant Prof 7 yes

Tenured?


6

Predictive accuracy : ◦ kemampuan model untuk memprediksi secara benar class label untuk data baru

Speed : ◦ biaya komputasi untuk menghasilkan dan menggunakan model

Robustness : ◦ kemampuan model untuk membuat prediksi yang benar jika terdapat noise atau missing data

Scalability : ◦ kemampuan membangun model secara efisien dalam data yang berjumlah sangat besar

Interpretability : ◦ tingkat pemahaman dan pengertian yang disediakan oleh model


7

Decision tree : struktur pohon, tiap internal node menyatakan sebuah test pada suatu atribut, tiap cabang menyatakan hasil test, dan node daun menyatakan class. Node paling atas adalah node akar (root). Algoritma pembentukan tree : (top down recursive, divide and conquer) ◦ Tree mulai dengan node akar ◦ Jika seluruh sample ada di class yang sama, maka node tsb menjadi leaf dan diberi label dengan class tsb. ◦ Jika tidak, gunakan information gain untuk memilih atribut yang paling baik dalam memisahkan sample ke class. ◦ Buat cabang untuk tiap nilai dari atribut test ◦ Ulangi proses pembuatan tree sampai : Seluruh sample masuk ke class yang sama, atau Tidak terdapat lagi atribut yang dapat memisahkan data sample Tidak terdapat sample untuk cabang test atribut


8

age <=30 <=30 31…40 >40 >40 >40 31…40 <=30 <=30 >40 <=30 31…40 31…40 >40

income student credit_rating high no fair high no excellent high no fair medium no fair low yes fair low yes excellent low yes excellent medium no fair low yes fair medium yes fair medium yes excellent medium no excellent high yes fair medium no excellent

buys_computer no no yes yes yes no yes no yes yes yes yes yes no


9

age? <=30

31..40 overcast

student? no no

yes yes

>40 credit rating? excellent

fair yes

yes


10

Attribute Selection Measure: Information Gain (ID3/C4.5)

Pilih atribut dengan information gain tertinggi Bila pi : probabilitas sembarang tuple dalam D termasuk class Ci, diestimasi sbg |Ci, D|/|D| Expected information (entropy) untuk klasifikasi suatu m tuple dalam D: Info ( D ) = − ∑ pi log 2 ( pi ) i =1

Information (setelah memakai A utk membagi D ke dlm v v |D | partisi) utk klasifikasi D: j InfoA (D) = ∑ × I (Dj ) j =1 | D | Information gained dengan pencabangan pada atribut A

Gain(A)= Info(D)− InfoA(D) DM-MA/S1IF/FTI/UKM/2010

11

Class P: buys_computer = “yes” g Class N: buys_computer = “no”

Info age ( D ) =

g

Info ( D ) = I (9,5 ) = −

age <=30 31…40 >40 age <=30 <=30 31…40 >40 >40 >40 31…40 <=30 <=30 >40 <=30 31…40 31…40 >40

9 9 5 5 log 2 ( ) − log 2 ( ) = 0 .940 14 14 14 14

pi 2 4 3

n i I(p i, n i) 3 0.971 0 0 2 0.971

income student credit_rating high no fair high no excellent high no fair medium no fair low yes fair low yes excellent low yes excellent medium no fair low yes fair medium yes fair medium yes excellent medium no excellent high yes fair medium no excellent

buys_computer no no yes yes yes no yes no yes yes yes yes yes no

+

5 4 I ( 2 ,3 ) + I ( 4,0 ) 14 14

5 I (3, 2 ) = 0 .694 14

5 I ( 2 ,3) means “age <=30” has 5 out of 14 14 samples, with 2 yes’es and 3 no’s. Hence

Gain ( age ) = Info ( D ) − Info age ( D ) = 0.246 Similarly,

Gain(income) = 0.029 Gain( student ) = 0.151 Gain(credit _ rating ) = 0.048 DM-MA/S1IF/FTI/UKM/2010

12

Classification— problem klasik yang diteliti secara ekstensif oleh ahli statistik dan peneliti machine learning

Scalability: klasifikasi kumpulan data dengan jutaan contoh dan ratusan atribut dengan reasonable speed

Mengapa memakai decision tree induction dalam data mining? ◦ Kecepatan belajar relatif lebih tinggi (dibandingkan cara classification yang lain) ◦ Mudah diubah menjadi rule dan mudah dipahami ◦ Dapat memakai SQL query utk mengakses database ◦ Tingkat akurasinya dapat dibandingkan (comparable) dengan metoda classification yang lain


13

Bayesian classifier : statistical classifier. Dapat memprediksikan kemungkinan keanggotaan class, misalnya probabilitas suatu sample menjadi anggota suatu class tertentu. Bayesian classification didasari oleh teorema Bayes P(X|H) P(H) P(H|X) = -----------------------------P(X)


14

X : data sample yang label classnya belum diketahui H : hipotesis, misalnya data sample X anggota class C. Untuk classification, kita ingin menentukan P(H|X), yaitu probabilitas hipotesis H dipenuhi terhadap sample data X. P(H|X) : posterior probability / posteriori probability untuk H sesuai kondisi X. Misalnya Buah, digambarkan dengan color dan shape. Jika X : red,round ; H : X adalah apel maka P(H|X) : keyakinan bahwa X adalah apel karena X adalah red dan round


15

P(H) : prior probability / probability awal dari H. Mis. probabilitas bahwa data sample adalah apel, tanpa peduli bagaimana wujud sample P(X|H) : posterior probability untuk X, probabilitas observasi sample X, bila hipotesis dipenuhi Mis. probabilitas X adalah red & round jika kita tahu bahwa X adalah apel. P(X) : prior probability dari X, yaitu probability bahwa sample data diobservasi Mis. probabilitas bahwa data sample adalah red & round. DM-MA/S1IF/FTI/UKM/2010

16

Cara kerja naive Bayesian : Tiap data sample dengan n atribut disajikan dalam bentuk n-dimensional feature vector, X = (x1,x2,….,xn) Misalkan terdapat m class, C1,C2, … Cm. Dengan data sample X, classifier akan memprediksi bahwa X adalah anggota class yang memiliki posterior probability tertinggi dengan kondisi X.


17

Sesuai teorema Bayes:

P(X|Ci) P(Ci) P(Ci|X) = -----------------------------P(X)

Karena P(X) konstan untuk seluruh class, maka hanya P(X|Ci) P(Ci) yang perlu dimaksimalkan. P(Ci) = Si/S, dengan Si adalah jumlah training sample dari class Ci, dan S adalah jumlah seluruh training sample. Karena menghitung P(X|Ci) memerlukan komputasi mahal, maka dibuat asumsi yaitu bahwa tidak ada hubungan ketergantungan antar atribut. Hitung P(Xk|Ci) = Sik/Si. Sik adalah jumlah training sample class Ci yang mempunyai nilai Xk, Si adalah jumlah training sample dari class Ci. DM-MA/S1IF/FTI/UKM/2010

18

Class: C1:buys_computer = ‘yes’ C2:buys_computer = ‘no’ Data sample X = (age <=30, Income = medium, Student = yes Credit_rating = Fair)

age

income

<=30 <=30 31…40 >40 >40 >40 31…40 <=30 <=30 >40 <=30 31…40 31…40 >40

high high high medium low low low medium low medium medium medium high medium

student credit_rating buys_c

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


fair excellent fair fair fair excellent excellent fair fair fair excellent excellent fair excellent

no no yes yes yes no yes no yes yes yes yes yes no 19

P(Ci):

Compute P(X|Ci) for each class

P(buys_computer = “yes”) = 9/14 = 0.643 P(buys_computer = “no”) = 5/14= 0.357

P(age = “<=30” | buys_computer = “yes”) = 2/9 = 0.222 P(age = “<= 30” | buys_computer = “no”) = 3/5 = 0.6 P(income = “medium” | buys_computer = “yes”) = 4/9 = 0.444 P(income = “medium” | buys_computer = “no”) = 2/5 = 0.4 P(student = “yes” | buys_computer = “yes) = 6/9 = 0.667 P(student = “yes” | buys_computer = “no”) = 1/5 = 0.2 P(credit_rating = “fair” | buys_computer = “yes”) = 6/9 = 0.667 P(credit_rating = “fair” | buys_computer = “no”) = 2/5 = 0.4

X = (age <= 30 , income = medium, student = yes, credit_rating = fair)

P(X|Ci) : P(X|buys_computer = “yes”) = 0.222 x 0.444 x 0.667 x 0.667 = 0.044 P(X|buys_computer = “no”) = 0.6 x 0.4 x 0.2 x 0.4 = 0.019 P(X|Ci)*P(Ci) : P(X|buys_computer = “yes”) * P(buys_computer = “yes”) = 0.028 (MAX) P(X|buys_computer = “no”) * P(buys_computer = “no”) = 0.007 Therefore, X belongs to class (“buys_computer = yes”) DM-MA/S1IF/FTI/UKM/2010

20

Naïve Bayesian prediction memerlukan setiap conditional prob. harus nonzero. Jika tidak, predicted probability akan bernilai 0 n P( X | C i ) = ∏ P( x k | C i ) k =1

Mis. Terdapat dataset dengan 1000 tuples, income=low (0), income= medium (990), and income = high (10), Memakai Laplacian correction ( Laplacian estimator) ◦ Tambahkan 1 pada setiap kasus Prob(income = low) = 1/1003 Prob(income = medium) = 991/1003 Prob(income = high) = 11/1003

◦ Estimasi “corrected” prob. mendekati perhitungan “uncorrected”


21

Keuntungan ◦ Mudah diimplementasikan ◦ Memberikan hasil cukup baik pada banyak kasus

Kerugian ◦ Asumsi: class conditional independence => kehilangan akurasi ◦ Secara Praktis, dependency ada di antara variabel Mis., hospitals: patients: Profile: age, family history, dll Symptoms: fever, cough , dll Disease: lung cancer, diabetes, dll Dependency antara variabel tidak dapat dimodelkan dengan Naïve Bayesian Classifier

Bagaimana menangani dependency? ◦ Bayesian Belief Networks


22

Representasi pengetahuan dalam bentuk IF-THEN rules R: IF age = youth AND student = yes THEN buys_computer = yes ◦ Rule antecedent/precondition vs. rule consequent

Penilaian rule: coverage and accuracy ◦ ncovers = # of tuples covered by R ◦ ncorrect = # of tuples correctly classified by R coverage(R) = ncovers /|D| /* D: training data set */ accuracy(R) = ncorrect / ncovers

Jika lebih dari satu rule ditrigger, maka perlu conflict resolution ◦ Size ordering: berikan prioritas tinggi untuk rules yang bersifat “toughest” (mis., rule dengan most attribute test) ◦ Class-based ordering: mengurangi order dari prevalence atau misclassification cost per class ◦ Rule-based ordering (decision list): rules diorganisasi menjadi satu daftar prioritas, mengikuti ukuran kualitas rule atau saran pakar.


23

age? <=30

•

Rules lebih mudah dipahami dibandingkan tree

•

student?

Satu rule diciptakan untuk setiap jalur dari akar ke daun

•

Setiap pasang attribute-value dalam suatu jalur membentuk conjunction: daun adalah class prediction

•

Rules bersifat mutually exclusive dan exhaustive

31..40

no

no

yes

yes

yes

>40

credit rating? excellent

fair

yes

Example: Rule extraction from our buys_computer decision-tree IF age = young AND student = no

THEN buys_computer = no

IF age = young AND student = yes

THEN buys_computer = yes

IF age = mid-age

THEN buys_computer = yes

IF age = old AND credit_rating = excellent THEN buys_computer = yes IF age = young AND credit_rating = fair

THEN buys_computer = no


24

id

member

age

student

income

class:buys_funky_tshirt

1 no

<=20

n

high

n

2 yes

<=20

n

high

n

3 no

21 .. 25

n

high

y

4 no

26 .. 30

n

medium

y

5 no

26 .. 30

y

low

y

6 yes

26 .. 30

y

low

n

7 yes

21 .. 25

y

low

y

8 no

<=20

n

medium

n

9 no

<=20

y

low

y

10 no

26 .. 30

y

medium

y

11 yes

<=20

y

medium

y

12 yes

21 .. 25

n

medium

y


25

Dengan training data set tersebut, buatlah decision tree-nya. Jangan lupa sertakan langkah-langkah, perhitungan, serta pertimbangan untuk menghilangkan node tertentu (jika ada). Cari prediksi dengan naïve Bayesian classifier untuk sample X = (member=yes, age=26..30, student=no, income=high), sertakan langkah-langkah dan perhitungannya.


26

S1 Teknik Informatika Fakultas Teknologi Informasi Universitas Kristen Maranatha

Recommend Documents