BAB II
INDUCT/RIPPLE-DOWN RULE (RDR) Bab ini berisi tentang uraian mengenai teori Ripple-Down Rules (RDR), yang meliputi RDR
dengan pengembangan manual dan RDR yang menerapkan algoritma Induct untuk pengembangannya.
II.1 Ripple-Down Rule (RDR) Ripple-Down Rule (RDR) merupakan suatu metode akuisisi pengetahuan dalam
pengembangan basis pengetahuan secara bertahap dari suatu sistem pakar atau sistem berbasis
pengetahuan. RDR dikembangkan oleh Compton dan Jansen [COM89] sebagai suatu metode
akuisisi pengetahuan dan pengelolaan dari suatu sistem berbasis aturan berukuran besar. RDR
telah berhasil digunakan untuk menstrukturkan ulang sistem GARVAN-ES1, sebuah sistem pakar pengecekan kesehatan yang memberikan diagnosa terhadap pasien berdasarkan pengukuran tingkat hormon thyroid. RDR dipandang sebagai metode yang berhasil dalam
membangun sistem berbasis pengetahuan untuk permasalahan klasifikasi [COM00].
RDR dibangun untuk mengatasi permasalahan tidak adanya penjelasan yang lengkap dari
pakar mengenai keputusan yang mereka ambil. Dalam RDR, pakar mengekspresikan
pengetahuannya dalam bentuk pemecahan terhadap kasus-kasus yang diberikan. Oleh karena itu, pendekatan dengan teori RDR dapat digolongkan ke dalam pendekatan berbasis kasus
(case-based). Teori RDR menggunakan prinsip bahwa pengetahuan selalu diberikan oleh
pakar untuk satu konteks tertentu, dan akan dapat bernilai benar hanya untuk konteks yang sama [COM00].
Dalam RDR, pengetahuan baru ditambahkan jika terjadi kesalahan sistem dalam memberikan klasifikasi untuk suatu kasus. Kasus yang menyebabkan penambahan pengetahuan ini akan disimpan sebagai kasus cornerstone pada basis pengetahuan. Penambahan pengetahuan baru
menjamin akurasi sistem secara bertahap karena pengetahuan yang ditambahkan akan
mengklasifikasikan kasus terkini secara benar dan tidak menyebabkan kesalahan interpretasi
pada kasus-kasus sebelumnya [COM00]. Penambahan pengetahuan ini merupakan bagian
dari proses akuisisi pengetahuan, yaitu suatu proses mentransfer pengetahuan dan
mengubahnya dengan kemampuan kepakaran menjadi solusi untuk pemecahan masalah.
Akusisi pengetahuan secara bertahap merupakan keuntungan dari penggunaan RDR dalam
II-1
II-2 suatu sistem berbasis pengetahuan, karena dalam masa pemakaian pun sistem masih terus dapat berkembang.
Proses akuisisi pengetahuan dapat dilakukan secara manual oleh pakar atau secara otomatis
melalui program komputer. Compton dan Gaines [GAI92] mengembangkan suatu algoritma
pembelajaran mesin yang membangun RDR secara otomatis menggunakan metode Induct. Algoritma ini dikenal dengan sebutan Induct/RDR. Penjelasan mengenai metode Induct dan
Induct/RDR akan diberikan pada sub-bab II.2.
II.1.1 Representasi Pengetahuan RDR [KHO98 Pengetahuan RDR direpresentasikan dalam bentuk pohon biner dengan setiap simpul
menyatakan satu kaidah. Setiap simpul memiliki maksimal dua cabang yaitu cabang except
dan cabang else kecuali pada simpul akar yang hanya memiliki satu cabang yaitu cabang except. Komponen-komponen pengetahuan RDR tersebut dapat dijelaskan di bawah ini.
Simpul (node) pohon menyatakan kaidah dalam pengetahuan, yang berisi serangkaian kondisi
beserta konklusi yang dihasilkan apabila kondisi terpenuhi. Dalam RDR, suatu kaidah dapat menjadi perkecualian bagi kaidah yang lain. Kondisi dalam kaidah dapat berbentuk konjungsi sebagai berikut :
IF klausa-1 AND klausa-2 AND ... AND klausa-n THEN kelas-X
atau berbentuk disjungsi sebagai berikut :
IF klausa-1 OR klausa-2 OR ... OR klausa-n THEN kelas-X
Cabang except disebut juga cabang IF-TRUE, pada umumnya direpresentasikan sebagai anak
cabang kanan pada pohon RDR. Cabang except mendefinisikan suatu perkecualian positif dari
kaidah pada simpul induk. Cabang ini akan dieksekusi bila kondisi kaidah induk (kaidah
dengan level satu tingkat di atasnya) terpenuhi. Solusi pada cabang ini akan menganulir solusi sebelumnya jika kondisinya terpenuhi.
Cabang else disebut juga cabang IF-FALSE, pada umumnya direpresentasikan sebagai anak
cabang kiri pada pohon RDR. Cabang else mendefinisikan suatu perkecualian negatif dari kaidah pada simpul induk. Cabang ini akan dieksekusi bila kondisi induk tidak terpenuhi.
Solusi pada cabang ini juga akan menganulir solusi kaidah sebelumnya jika kondisinya terpenuhi.
Representasi pengetahuan RDR dapat dilihat pada gambar di bawah ini.
II-3
Gambar II-1 Representasi pengetahuan RDR dalam bentuk pohon biner
Basis pengetahuan RDR terdiri atas sekumpulan kaidah beserta kasus cornerstone yang
terkait. Kasus cornerstone merupakan kasus yang menyebabkan terjadinya penambahan
kaidah baru, yang disimpan ketika terjadi penambahan kaidah baru untuk mengoreksi adanya
kesalahan klasifikasi oleh sistem. Setiap kaidah terhubung dengan satu kasus cornerstone, kecuali kaidah pada simpul akar.
Kaidah RDR mempunyai secara umum mempunyai bentuk formulasi :
if
then [because of ] except if then [because of ] else if then [because of ]
Formulasi ini dapat dituliskan dalam pernyataan “if-then-else” biasa sehingga menjadi :
if then if then else else if then
II.1.2 Inferensi RDR Proses inferensi pada RDR dimulai pada simpul akar. Kasus masukan akan diperiksa apakah
memenuhi kaidah-kaidah dalam pohon RDR untuk mendapatkan konklusi. Setiap kasus
masukan pasti akan memenuhi kaidah pada simpul akar. Jika kaidah induk terpenuhi, maka konklusi dari kaidah induk akan menjadi konklusi untuk kasus terkait jika kaidah induk tidak memiliki cabang.
Jika kaidah induk memiliki cabang, maka penelusuran dilanjutkan ke cabang IF-TRUE untuk
memeriksa perkecualian positif dari kaidah induk. Jika kondisi kaidah terpenuhi, maka
konklusi kasus adalah konklusi kaidah tersebut. Jika kondisi kaidah tidak terpenuhi, maka
konklusi kasus adalah konklusi kaidah sebelumnya yang dipenuhi dan penelusuran dilanjutkan ke cabang IF-FALSE untuk memeriksa perkecualian negatif dari kaidah induk.
II-4 Penelusuran berakhir jika simpul yang dievaluasi tidak memiliki cabang dan konklusi akhir sistem adalah konklusi kaidah terakhir yang dipenuhi pada jalur inferensi.
Gambar II-2 Contoh inferensi dengan RDR
Pada Gambar II-2 di atas, digunakan kasus [a, b, e, f, g, i] sebagai kasus masukan. Proses
inferensi dimulai dengan mengevaluasi kaidah 0.0 terhadap kasus masukan. Kondisi true
dipenuhi untuk semua kasus, sehingga konklusi awal sistem adalah konklusi kaidah 0.0 yaitu
none. Proses inferensi dilanjutkan dengan mengevaluasi cabang IF-TRUE yaitu kaidah 1.1 dengan kondisi (a,b). Karena kondisi (a,b) terpenuhi, maka konklusi sementara sistem
berubah dari none menjadi kelas 1 dan penelusuran dilanjutkan pada cabang IF-TRUE. Kaidah 2.2 mempunyai kondisi (c) yang tidak terpenuhi oleh kasus, sehingga penelusuran selanjutnya ke cabang IF-FALSE dan konklusi sistem tetap kelas 1. Kaidah 4.5 pada cabang
IF-FALSE dengan kondisi (e,g) dipenuhi oleh kasus, sehingga konklusi sistem berubah
menjadi konklusi kaidah 4.5 yaitu kelas 5. Penelusuran berhenti pada kaidah 4.5 yang sudah tidak mempunyai cabang.
Dengan demikian jalur inferensi untuk kasus [a, b, e, f, g, i] adalah [(kaidah 0.0, none),
(kaidah 1.1, kelas 1), (kaidah 2.2, kelas 1), (kaidah 4.5, kelas 5) ]
II.1.3 Pengembangan Manual pada RDR Pengembangan RDR menyangkut proses akuisisi pengetahuan untuk meningkatkan
performansi sistem. Akuisisi pengetahuan akan menambahkan pengetahuan baru pada RDR
II-5 dan dilakukan apabila terjadi kesalahan klasifikasi terhadap kasus masukan sehingga sistem
memberikan solusi yang salah. Untuk itu, diperlukan solusi yang benar terhadap kasus masukan tersebut dan kondisi untuk kaidah yang akan ditambahkan.
Jika konklusi kelas 5 yang diberikan oleh sistem pada struktur RDR yang ditunjukkan oleh
gambar Gambar II-2 dinyatakan salah, dengan konklusi yang benar adalah kelas 3, maka
kaidah baru dapat ditambahkan sebagai perkecualian positif dari kaidah 4.5. Dalam hal ini, kondisi kasus adalah memenuhi kondisi pada kaidah.
Pemilihan kondisi untuk membentuk kaidah baru dilakukan berdasarkan pada perbedaan kondisi antara kasus masukan dan kasus kunci pada kaidah terakhir yang dipenuhi pada jalur inferensi. Berdasarkan contoh di atas, daftar perbedaan tersebut adalah sebagai berikut : kasus kunci kaidah 4.5
: [a, b, e, g]
daftar perbedaan
: [f, i]
kasus masukan
: [a, b, e, f, g, i]
Kondisi untuk penambahan kaidah baru dipilih dari daftar perbedaan yang diperoleh, salah
satu kondisi atau kombinasinya. Kondisi yang dipilih dapat membentuk suatu kaidah menjadi bersifat generik maupun spesifik. Untuk kaidah bersifat generik, maka penanganan terhadap
kasus-kasus lain yang tercakup dilakukan dengan menambahkan cabang IF-TRUE
baru,sehingga kaidah ini dapat mencakup lebih banyak kasus. Kaidah bersifak spesifik jika kondisi yang dipilih lebih banyak, sehingga kaidah jenis ini hanya dapat menangani kasus
dengan kondisi lebih spesifik. Kasus yang tercakup di dalamnya juga akan berjumlah lebih sedikit.
Untuk kasus di atas, maka kedua kondisi dari daftar perbedaan dipilih sebagai kondisi pada kaidah baru. Sehingga struktur pohon RDR dari gambar di atas menjadi seperti pada Gambar II-3.
II-6
Gambar II-3 Contoh akuisisi pengetahuan pada RDR
II.2 Pembelajaran Induct pada RDR [GAI92] Akusisi pengetahuan pada RDR secara manual untuk membangun pohon kaidah awal
dianggap tidak praktis [LIT96]. Oleh karena itu, dikembangkan suatu metode pembelajaran Induct untuk membangun RDR secara otomatis, yang kemudian dikenal sebagai
Induct/Ripple-Down Rules (RDR) [GAI92].
II.2.1 Definisi Induct Induct didefinisikan sebagai : suatu metode pembelajaran yang menghasilkan ruang hipotesa H dari sekumpulan instans X untuk mendefinisikan konsep target c. Setiap hipotesa h dalam H menunjukkan sebuah fungsi boolean terhadap X, yaitu h : X {0,1}. Tujuan pembelajaran inductive adalah untuk memperoleh sebuah hipotesa h sedemikian sehingga h(x) = c(x) untuk semua x dalam X [MIT97].
Dalam pembelajaran inductive, dilakukan observasi terhadap sekumpulan data atribut-nilai
dari
suatu
konsep,
yang
biasa
disebut
sebagai
data
latih.
Pembelajaran
akan
mengidentifikasikan kombinasi atribut-nilai yang mendefinisikan konsep dari data. Hasil
II-7 pendefinisian konsep ini kemudian digunakan untuk mengklasifikasikan data baru, atau data uji dengan menggunakan asumsi bahwa hipotesa terbaik yang sesuai dengan data uji adalah
hipotesa terbaik yang sesuai pada data latih. Oleh karena itu, kualitas data latih sangat mempengaruhi kualitas pembelajaran yang dihasilkan.
Sebuah inductive system dapat digambarkan sebagai sebuah sistem yang menerima masukan
training example dengan kelas terdefinisi dan instance baru yang belum terklasifikasi.
Inductive system menggunakan beberapa pendekatan untuk membangun ruang hipotesa H
yang mendeskripsikan training example. Sistem mengklasifikasikan instance baru
menggunakan H, menghasilkan keluaran berupa klasifikasi instance baru atau nilai ”don’t know”.
Pendekatan Induct pada RDR menggunakan metodologi statistik untuk menghasilkan kaidah
dari data. Penelitian dilakukan terhadap data pada [GAI89] dan menghasilkan sistem yang
menurunkan kaidah-kaidah dengan eksepsi, yang merupakan struktur dari RDR. Ekstensi
Induct ke RDR menggunakan statistical decision procedure untuk membangkitkan kaidah. Prosedur statistik tersebut akan dipanggil secara rekursif pada data yang tersisa untuk membangkitkan kaidah IF-TRUE dan IF-FALSE.
II.2.2 Pembangkitan Premis Kaidah Untuk membangun sebuah rule lengkap, klausa penyusun premis dibangkitkan satu demi
satu. Premis terdiri atas klausa-klausa yang harus dipenuhi oleh data sebagai kondisi dari
kelas data. Terpenuhinya premis akan mengklasifikasikan data latih ke dalam klasifikasi kelas
yang sesuai. Pembangkitan premis dalam Induct/RDR menggunakan pertimbangan bahwa
premis akan menghasilkan rule yang sensitif terhadap data uji, dan mengklasifikasikan data latih dengan tepat.
Gambar II-4 menunjukkan analisa kesalahan yang memberikan control statistik dari algoritma
yang digunakan dalam Induct. Data dibagi ke dalam beberapa diagnosa yaitu D0, D1, D2, D3,
dan sebagainya. Diagnosa D0 merupakan diagnosa target yang digunakan oleh Induct untuk
mendefinisikan sebuah kaidah. Elips luar menunjukkan cakupan kasus untuk kaidah sebelum
diubah, yaitu meliputi kasus-kasus dengan diagnosa D0, D8, D9, D12, D15, dan D18. Elips
dalam menunjukkan cakupan kasus jika ditambahkan klausa pada kaidah, yaitu meliputi kasus-kasus dengan diagnosa D0, D8, dan D9. Hal ini menunjukkan adanya pengurangan
dalam jumlah kasus yang dicakup oleh kaidah jika ditambahkan klausa terhadap kaidah tersebut, yang membuat suatu kaidah menjadi semakin spesifik terhadap kasus tertentu.
II-8
Gambar II-4 Error analysis untuk statistical control algoritma Induct [GAI92]
Pembangkitkan premis untuk kaidah RDR secara inductive dapat dilakukan dengan langkahlangkah sebagai berikut:
1. klasifikasi yang paling sering muncul dari data dipilih sebagai konklusi target. 2. premis awal diinisialisasi tanpa mempunyai klausa. Premis ini akan meluluskan semua kasus karena tidak ada kondisi khusus yang harus dipenuhi.
3. untuk setiap kombinasi atribut-nilai dilakukan pengujian secara iteratif terhadap kemungkinannya sebagai klausa. Pasangan atribut-nilai yang terbaik dipilih sebagai klausa berdasarkan pengujian statistik.
4. pengambilan keputusan untuk menambahkan klausa dilakukan dengan menggunakan
pengujian statistik yang sama dan pertimbangan apakah penambahan klausa terpilih
tersebut dapat meningkatkan performansi kaidah atau sebaliknya. Jika terdapat peningkatan, maka proses kembali ke langkah 3. Sedangkan jika tidak terdapat peningkatan, proses berhenti dengan kaidah yang dihasilkan sebagai keluaran.
Proses pembangkitan premis melibatkan suatu fungsi statistik untuk memilih klausa terbaik
yang akan melakukan pemangkasan (pruning) pada setiap rule yang sudah lengkap.
Pembangkitan suatu rule secara lengkap memunculkan kemungkinan overfitting terhadap
training set. Untuk mengantisipasi hal ini, penghapusan klausa dilakukan dari bagian
belakang sebuah rule lengkap. Penghapusan dilakukan sampai kualitas rule mencapai nilai
maksimal, dan berhenti jika penghapusan dapat memperburuk kualitas rule. Pengukuran
kualitas rule ini melibatkan fungsi probabilitas untuk mengukur kemungkinan rule terpilih
secara acak (random) [WIT00]. Penjelasan mengenai fungsi-fungsi statistik tersebut diberikan
pada sub-bab II.2.3.
II-9
II.2.3 Pemilihan Klausa Terbaik Pemilihan klausa terbaik melibatkan suatu pengujian statistik untuk memilih pasangan atribut-nilai sebagai klausa pada premis rule. Pasangan atribut-nilai yang dipilih adalah yang
mempunyai nilai probabilitas terkecil untuk terpilih secara acak. Nilai probabilitas diperlukan
untuk melakukan pembandingan antara pemilihan secara acak dengan pemilihan oleh rule yang dibangun. Pembandingan dilakukan pada derajat generalitas yang sama.
Derajat generalitas dari suatu rule merupakan cakupan rule terhadap kasus. Kasus yang dapat
tercakup oleh rule adalah kasus yang memenuhi kondisi rule. Dua buah rule dengan derajat
generalitas yang sama dapat diartikan bahwa kondisi-kondisi dalam masing-masing rule yang
harus dipenuhi oleh kasus adalah sama dan jumlah kasus yang dapat tercakup oleh rule adalah sama.
Dasar pengujian statistik untuk pemilihan klausa terbaik ditunjukkan dalam Diagram Venn
pada Gambar II-5 di bawah ini. Diberikan himpunan semesta entitas E, predikat target Q, dan himpunan predikat uji S. S akan digunakan untuk membangun rule set yang dapat
menghasilkan kesimpulan berupa predikat target jika diketahui nilai dari predikat uji. S akan
memilih entitas e dari E yang benilai benar untuk Q dan membandingkan proses pemilihan
oleh rule R dengan pemilihan secara acak.
Gambar II-5 Dasar untuk pengujian statistik pada Induct[GAI92]
Untuk mendefinisikan probabilitas penyeleksian secara acak dari derajat generalitas yang
sama, diketahui Q sebagai entitas relevan dalam E dengan Q(e) terpenuhi (Persamaan II-1), S
entitas terpilih dalam E dengan S(e) terpenuhi (Persamaan II-2), dan C entitas benar dalam E
dengan Q(e) dan S(e) terpenuhi (Persamaan II-3).
II-10
Persamaan II-1 Persamaan II-2 Persamaan II-3
Kardinalitas dari E, Q, S, dan C masing-masing dinyatakan dengan e, q, s, dan c. Probabilitas
terpilihnya sebuah entitas yang memenuhi Q (e yang bernilai benar untuk Q) dari himpunan entitas E secara random, dinyatakan dengan notasi p, adalah :
Persamaan II-4
dengan q adalah jumlah kasus dengan kelas Q, e adalah jumlah seluruh kasus dalam data. Probabilitas suatu rule yang terpilih secara acak untuk memilih s dan memperoleh sejumlah c
atau lebih entitas bernilai benar, dinyatakan dengan notasi r, didefinisikan dengan
menjumlahkan distribusi binomial standar untuk memperoleh Persamaan II-5:
Persamaan II-5
dengan s adalah jumlah kasus dengan pasangan atribut-nilai yang diuji, i adalah jumlah kasus dengan kelas Q dari pasangan atribut-nilai yang diuji. Tanda kurung dalam fungsi kombinatorial dengan
menyatakan
.
Penggunaan r untuk mengukur kualitas suatu rule adalah dengan mengambil pasangan
atribut-nilai yang mempunyai nilai r terkecil, yaitu pasangan atribut-nilai yang mempunyai
probabilitas terkecil untuk terpilih secara acak. Kualitas suatu rule ditentukan dari nilai
probabilitas ini, nilai r yang besar menunjukkan buruknya kualitas rule tersebut. Nilai
probabilitas r membandingkan performansi antara pemilihan acak dan pemilihan oleh rule
pada derajat generalitas yang sama [WIT00].
Nilai atribut missing value dalam pengujian dapat diperhitungkan sebagai false positive (salah yang memang bernilai salah). Kontribusi missing value dalam false positive penting dalam
akuisisi pengetahuan karena pakar dapat memasukkan conjunctive rule yang tidak lengkap
yang akan dianggap sebagai entitas dengan missing value. Induct kemudian membangkitkan
set kaidah yang sama atau ekivalen lebih kecil.
II-11 Algoritma untuk memilih klausa terbaik yang digunakan dalam Induct tersebut oleh [LIT96]
didefinisikan di bawah ini.
BestClause(Class,Attr,Training_Set) {Fungsi ini menghasilkan klausa terbaik untuk ditambahkan ke dalam kaidah} loop
tmpTerm term dengan atribut A nilai V yang akan menghasilkan nilai r minimal jika ditambahkan ke kaidah clause clause + tmpTerm hapus A dari attr z jumlah example dalam trainingSet dengan kelas=class dan clause bernilai true s jumlah example dalam trainingSet dengan clause bernilai true if z=s then stop end loop while r(clause) > r(clause – lastTerm) do clause clause – lastTerm return clause
end BestClause Algoritma II-1 Pemilihan Klausa Terbaik [LIT96]
Fungsi BestClause melakukan pemangkasan (pruning) pada rule yang telah lengkap. Pemangkasan ini dilakukan dari bagian belakang, dan akan berhenti jika terjadi penurunan
kualitas rule yaitu peningkatan nilai r. Fungsi BestClause akan mengembalikan klausa yang
mempunyai nilai r terkecil.
Pemangkasan setelah rule lengkap ini dilakukan untuk mengantisipasi terjadinya overfitting, seperti telah dinyatakan sebelumnya. Di samping fakta ini, pemangkasan yang dihentikan
pada saat nilai r meningkat dapat menjadi keputusan yang tidak tepat. Misalnya ketika
pemangkasan dihentikan pada klausa ketiga dari belakang karena pada klausa ini nilai r meningkat. Sedangkan pada klausa kelima, nilai r lebih kecil daripada klausa ketiga, dan
mencapai nilai minimal. Oleh karena itu, pada pemangkasan sampai dengan klausa kelima, dapat diperoleh rule yang lebih baik daripada rule yang diperoleh pada pemangkasan sampai
dengan klausa ketiga. Meskipun demikian, metode ini dianggap dapat menghasilkan rule
yang cukup baik dengan komputasi yang lebih rendah.
Pada Gambar II-4, himpunan semesta E merupakan data yang diperlukan, predikat target Q
adalah D0, dan entitas terpilih S berada di dalam elips luar. Pemilihan terhadap klausa terbaik
pada setiap stage berdasarkan pada nilai r (Persamaan II-5), dengan mencari nilai r minimum.
Permasalahan pada Induct/RDR adalah memilih antara tetap mempertahankan kaidah yang
bersifat lebih umum sesuai dengan elips luar atau menambahkan klausa sesuai dengan elips dalam. Pada Gambar II-4, elips luar tidak hanya mencakup D0 tetapi juga D7, D8, D9, dan
II-12 sebagainya. Pada struktur RDR, diagnosa D7, D8, D9, dan sebagainya diperlakukan sebagai
eksepsi.
Kemampuan menangani eksepsi yang dimiliki Induct/RDR tidak berpengaruh pada akurasi dari BP final. Pengaruhnya lebih pada struktur BP yaitu kecenderungan terhadap penggunaan kaidah yang umum dengan banyak eksepsi daripada kaidah yang lebih spesifik dengan sedikit eksepsi. Hal ini berpengaruh pada ukuran BP secara kuantitatif yaitu jumlah kaidah dan klausa yang terlibat.
II.2.4 Pembangkitan Kaidah RDR RDR menstrukturkan dirinya sendiri dengan menggunakan metode Induct berdasarkan nilai probabilitas r untuk memperoleh rule dengan kualitas yang baik. Algoritma yang digunakan
untuk pembangkitan rule dari data latih dalam [GAI95] dapat dideskripsikan sebagai berikut : 1. Kelas yang paling besar kejadiannya dalam data dipilih sebagai kelas default.
2. Kelas dengan kejadian paling besar berikutnya dipilih sebagai kelas target.
Berdasarkan nilai r dari setiap pasangan atribut-nilai, dibangun eksepsi positif yaitu rule R untuk kelas target. Subset data yang memenuhi kondisi rule dipisahkan dari data latih. Jika pada subset ini terdapat lebih dari satu kelas, maka proses diulang secara rekursif. Data yang memenuhi R dihapus dari data latih.
3. Untuk data yang tidak memenuhi kondisi R, dibangun rule alternatif yaitu eksepsi negatif dari rule R.
4. Proses diulang secara rekursif pada data set yang tersisa, dan berhenti jika pada data set hanya terdapat satu kelas.
Pembangkitan struktur lengkap RDR dengan metode Induct ini untuk selanjutnya disebut
Induct/RDR. Untuk permasalahan dalam Gambar II-4, pembangkitan rule dengan Induct/RDR
dideskripsikan sebagai berikut. Premis yang terkait dengan elips luar dipilih untuk
membangkitkan rule. Algoritma Induct secara rekursif memanggil dirinya dua kali.
Pemanggilan pertama untuk membangkitkan cabang IF-TRUE untuk data yang berada pada
elips luar. Pemanggilan yang kedua untuk membangkitkan cabang IF-FALSE untuk data di
luar elips. Untuk membangkitkan cabang IF-TRUE, D0 sebagai diagnosis yang mempunyai kejadian terbanyak dalam data menjadi diagnosis default sehingga target untuk pembangkitan
rule berikutnya adalah diagnosis yang mempunyai kejadian terbanyak berikutnya. Untuk
membangkitkan cabang IF-FALSE, pemilihan diagnosis yang dijadikan sebagai default dilakukan dengan cara yang sama.
Algoritma Induct/RDR didefinisikan sebagai berikut :
II-13
BuildRDR(Default_Class,Attrs,Training_Set) {Fungsi ini menghasilkan kaidah RDR dengan struktur data terdiri atas komponen Class,Clause,ifTrue,ifFalse} untuk Class = (set of class values) jika Class = Default_Class TempClause BestClause(Class,Attr,Training_Set) jika r(TempClause) < r(T.Clause) T.Clause TempClause T.Class Class Covered himpunan semua entitas e dalam Training_Set dengan T.Clause(e) bernilai benar NotCovered himpunan semua entitas e dalam Training_Set dengan T.Clause(e) bernilai salah jika e berada dalam Covered and e.Class = Class hapus dari Attrs semua atribut yang digunakan dalam T.Clause T.ifTrue BuildRDR(Class,Attrs,Covered) restore atribut yang dihapus ke Attrs jika e berada dalam NotCovered dan e.Class = Class hapus dari Attrs semua atribut yang digunakan dalam T.Clause T.ifFalse BuildRDR(Default_Class,Attrs,NotCovered)
return T
Algoritma II-2 Pembangkitan RDR dengan Induct [LIT96]
Dalam algoritma pembangkitan RDR ini digunakan fungsi BestClause untuk menentukan
klausa yang akan digunakan dalam membangun rule untuk mengklasifikasikan seluruh entitas
e dalam Training_Set. Untuk membangun struktur RDR awal, sebuah kelas yang paling
banyak muncul dalam data dipilih sebagai kelas default pada top-level rule. Kemudian
algoritma membangun rule yang memiliki nilai r terkecil menggunakan fungsi BestClause untuk kelas selain kelas default. Dalam hal ini, kelas yang dimaksud adalah kelas dengan
kejadian terbanyak dalam data setelah kelas default. Training_Set dipisahkan menjadi dua
subset, yaitu Covered jika kondisi klausa untuk rule bernilai True; dan Not_Covered jika kondisi klausa bernilai False. Jika salah satu dari kedua subset ini masih mengandung lebih dari satu kelas, maka BuildRDR memanggil dirinya secara rekursif pada subset tersebut.
Pemanggilan pada subset Covered menggunakan kelas pada rule, sedangkan pemanggilan
pada subset Not_Covered menggunakan kelas default. Algoritma ini menghasilkan struktur RDR.
