31/10/2014
Klasifikasi S1 Teknik Informatika Fakultas Teknologi Informasi Universitas Kristen Maranatha
Agenda •
Pendahuluan
•
Klasifikasi
•
Induksi Pohon Keputusan
•
Klasifikasi Bayesian classification
2
1
31/10/2014
Pendahuluan •
Klasifikasi: •
•
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)
•
Prediksi memodelkan fungsi kontinyu, mis. prediksi nilai hilang atau tidak diketahui
•
Contoh aplikasi • • • •
•
Persetujuan kredit: pinjaman aman atau beresiko Target pemasaran: konsumen potensial Diagnosis medis Deteksi penipuan
Teknik-teknik : •
•
Klasifikasi: decision tree induction, Bayesian classification, Bayesian belief network, neural network, k-nearest neighbour classifier, CBR, algoritma genetic, rough set, fuzzy logic Prediksi: Linear, nonlinear, generalized linear regression
3
Klasifikasi: Proses Dua Langkah •
Konstruksi Model: menjelaskan sebuah set dari class yang ditentukan sebelumnya Setiap sample diasumsikan termasuk class yang ditentukan sebelumnya, ditentukan oleh label atrbut dari class • Kumpulan sample yang dipakai untuk konstruksi model: set training • Model direpresentasikan sebagai aturan klasifikasi, pohon keputusan, atau rumus matematka •
•
Pemakaian Model: mengklasifikasi obyek – obyek di masa datang atau yang tidak diketahui Estimasi keakuratan model • Label yang diketahui dari test sample dibandingkan dengan hasil klasifikasi dari model • Tingkat keakuratan = persentase dari kumpulan test sample yang diklasifikasikan dengan benar oleh model • Set tes bersifat independen terhadap set training • Jika tingkat keakuratan dapat diterima, pakai model untuk klasifikasi sample data yang class labelnya belum diketahui •
4
2
31/10/2014
Proses (1): Konstruksi Model Algoritma Klasifikasi
Training Data
NA ME Mike Mary Bill Jim Dave Anne
R AN K YEA RS TEN UR ED Assistant Prof 3 no Assistant Prof 7 yes Professor 2 yes Associate Prof 7 yes Assistant Prof 6 no Associate Prof 3 no DM-MA/S1IF/FTI/UKM/2010
Klasifier (Model)
IF rank = ‘professor’ OR years > 6 THEN tenured = ‘yes’ 5
Proses (2): Menggunakan Model dalam Prediksi
Klasifier Data Testing
Data Tidak Diketahui (Jeff, Professor, 4)
NA M E Tom M erlisa George Joseph
RANK YEARS TEN URED Assistant Prof 2 no Associate Prof 7 no Professor 5 yes Assistant Prof 7 yes
Tenured?
6
3
31/10/2014
Evaluasi metode Klasifikasi •
Keakuratan Prediksi: •
•
Kecepatan: •
•
kemampuan model untuk membuat prediksi yang benar jika terdapat noise atau missing data
Skalabilitas: •
•
biaya komputasi untuk menghasilkan dan menggunakan model
Kehandalan: •
•
kemampuan model untuk memprediksi secara benar class label untuk data baru
kemampuan membangun model secara efisien dalam data yang berjumlah sangat besar
Pemahaman: •
tingkat pemahaman dan pengertian yang disediakan oleh model
7
Induksi Pohon Keputusan •
•
Pohon keputusan: 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 pohon: (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
4
31/10/2014
Induksi Pohon Keputusan: Training Dataset 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
Keluaran: Sebuah Pohon Keputusan untuk “buys_computer” age? <=30
31..40 overcast
student? no no
yes yes
>40 credit rating? excellent
fair yes
yes
10
5
31/10/2014
Pengukuran Seleksi Atribut: 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) 11
Seleksi Atribut: Information Gain 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 DM-MA/S1IF/FTI/UKM/2010 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 “age <=30” has 5 out of 14 I ( 2,3means ) 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 12
6
31/10/2014
Klasifikasi dalam Basis Data Besar •
Klasifikasi — problem klasik yang diteliti secara ekstensif oleh ahli statistik dan peneliti machine learning
•
Skalabilitas: klasifikasi kumpulan data dengan jutaan contoh dan ratusan atribut dengan kecepatan yang masuk akal
•
Mengapa memakai induksi pohon keputusan dalam data mining? • • • •
Kecepatan belajar relatif lebih tinggi (dibandingkan cara klasifikasi yang lain) Mudah diubah menjadi aturan dan mudah dipahami Dapat memakai SQL query utk mengakses basis dat Tingkat akurasinya dapat setara dengan metode klasifikasi yang lain
13
Klasifikasi Bayesian •
Bayesian classifier : klasifier statistik. 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
7
31/10/2014
Teorema Bayes •
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 warna dan bentuk. Jika X : merah,bulat ; H : X adalah apel maka P(H|X) : keyakinan bahwa X adalah apel karena X adalah merah dan bulat
15
Teorema Bayes •
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 merah & bulat 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 merah & bulat.
16
8
31/10/2014
Klasifikasi Naive Bayesian 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, klasifier akan memprediksi bahwa X adalah anggota class yang memiliki posterior probability tertinggi dengan kondisi X.
17
Klasifikasi Naïve Bayesian •
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.
18
9
31/10/2014
Klasifier Naïve Bayesian: Training Dataset
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
Klasifier Naïve Bayesian: Contoh •
P(Ci): P(buys_computer = “yes”) = 9/14 = 0.643
•
X = (age <= 30 , income = medium, student = yes, credit_rating = fair)
P(buys_computer = “no”) = 5/14= 0.357
•
Compute P(X|Ci) for each class P(age = “<=30” | buys_computer = “yes”) = 2/9 = 0.222 P(age = “<= 30” | buys_computer = “no”) = 3/5 = 0.6
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(income = “medium” | buys_computer = “yes”) = 4/9 = 0.444 = 0.007
P(X|buys_computer = “no”) * P(buys_computer = “no”)
P(income = “medium” | buys_computer = “no”) = 2/5 = 0.4 P(student = “yes” | buys_computer = “yes) = 6/9 = 0.667 Therefore, X belongs to class (“buys_computer = yes”) 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
20
10
31/10/2014
Menghindari Masalah 0-Probability Naïve Bayesian prediction memerlukan setiap conditional prob. harus nonzero. Jika tidak, predicted probability akan bernilai 0
•
P ( X | C i) =
n ∏ 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
Klasifier Naïve Bayesian: Komentar •
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
11
31/10/2014
Menggunakan Aturan IF-THEN untuk Klasifikasi •
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
Ekstraksi aturan dari Pohon Keputusan age?
•
Rules lebih mudah dipahami dibandingkan tree
•
Satu rule diciptakan untuk setiap jalur dari akar ke daun
<=30
•
Setiap pasang attribute-value dalam suatu jalur membentuk conjunction: daun adalah class prediction
•
31..40
student? no
yes
yes
no
yes
>40
credit rating? excellent
fair
yes
Rules bersifat mutually exclusive dan exhaustive •
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 IF age = mid-age
THEN buys_computer = yes 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
12
31/10/2014
Latihan id
age
student
income
class:buys_funky_tshirt
1 no
member
<=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
Latihan •
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
13
