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
DM-MA/S1IF/FTI/UKM/2010
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’
DM-MA/S1IF/FTI/UKM/2010
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?
DM-MA/S1IF/FTI/UKM/2010
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
DM-MA/S1IF/FTI/UKM/2010
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
DM-MA/S1IF/FTI/UKM/2010
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
DM-MA/S1IF/FTI/UKM/2010
9
age? <=30
31..40 overcast
student? no no
yes yes
>40 credit rating? excellent
fair yes
yes
DM-MA/S1IF/FTI/UKM/2010
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
DM-MA/S1IF/FTI/UKM/2010
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)
DM-MA/S1IF/FTI/UKM/2010
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
DM-MA/S1IF/FTI/UKM/2010
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.
DM-MA/S1IF/FTI/UKM/2010
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
DM-MA/S1IF/FTI/UKM/2010
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”
DM-MA/S1IF/FTI/UKM/2010
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
DM-MA/S1IF/FTI/UKM/2010
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.
DM-MA/S1IF/FTI/UKM/2010
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
DM-MA/S1IF/FTI/UKM/2010
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
DM-MA/S1IF/FTI/UKM/2010
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.
DM-MA/S1IF/FTI/UKM/2010
26