...

Sistem Berbasis Aturan

by user

on
Category: Documents
0

views

Report

Comments

Transcript

Sistem Berbasis Aturan
Chapter
3
Sistem Berbasis Aturan
Tujuan Instruksional Khusus
• Mahasiswa mampu menjelaskan representasi pengetahuan dalam bentuk Sistem Berbasis Aturan (Ruledbased System).
• Mahasiswa memahami model inferensi forward chaining
dan backward chaining dalam sistem berbasis aturan.
3.1
Pendahuluan
Sistem berbasis aturan (rule-based system) menggunakan Modus Ponens
sebagai dasar untuk memanipulasi aturan, yaitu:
fakta A benar, dan
operasi A → B benar,
maka fakta B adalah benar
Dengan menggunakan teknik searching yang telah didefinisikan dalam
30
Chapter 3. Sistem Berbasis Aturan
Bab 1 dan penyesuaian pola (pattern matching), sistem berbasis aturan melakukan proses reasoning mulai dari fakta awal sampai menuju
pada kesimpulan.
Dalam proses ini mungkin akan dihasilkan fakta-
fakta baru menuju pada penyelesaian masalah. Jadi dapat disimpulkan
bahwa proses penyelesaian masalah pada sistem berbasis aturan adalah
menciptakan sederet fakta-fakta baru yang merupakan hasil dari sederetan proses inferensi sehingga membentuk semacam jalur antara definisi
masalah menuju pada solusi masalah. Deretan proses inferensi tersebut
adalah inference chain.
Sebagai contoh, sebuah sistem peramal cuaca dibangun dengan sistem
berbasis pengetahuan untuk mengetahui keadaan cuaca pada 12 sampai
24 jam ke depan.
RULE 1:
RULE 2:
RULE 3:
IF
suhu udara sekitar di atas 32o C
THEN
cuaca adalah panas
IF
kelembaban udara relatif di atas 65%
THEN
udara sangat lembab
IF
cuaca panas dan udara sangat lembab
THEN
sangat mungkin terjadi badai
• Jika hanya rule 1 (tanpa rule 2 dan rule 3), sistem berbasis pengetahuan tidak berarti apa2.
• Karena itu sebuah sistem berbasis pengetahuan harus terdiri atas
sekelompok aturan yang membentuk rangakaian aturan rule chain.
• Fakta didefisinikan sebagai statemen yang dianggap benar. Contoh:
Suhu udara di sekitar adalah 35o C dan kelembaban udara relatif
70% adalah fakta.
• Maka proses inferensi melihat fakta-fakta dari premis pada Rule 1
dan Rule 2 sebagai dasar untuk menghasilkan fakta baru: Cuaca
panas dan Udara lembab.
31
Chapter 3. Sistem Berbasis Aturan
• Selanjutnya proses inferensi melihat bahwa kedua fakta ini sesuai
dengan premis pada Rule 3, maka akan dihasilkan fakta baru lagi:
Sangat mungkin terjadi badai.
3.2
Proses Reasoning
Note:
• Proses reasoning dari sebuah sistem berbasis aturan adalah tahapan proses mulai dari sekumpulan fakta menuju solusi, jawaban
dan kesimpulan.
• Terdapat dua macam cara yang dapat digunakan untuk menghasilkan suatu kesimpulan, yaitu:
– Forward Chaining (data driven): kesimpulan dihasilkan dari
seperangkat data yang diketahui.
– Backward Chaining (goal driven): memilih beberapa kesimpulan yang mungkin dan mencoba membuktikan kesimpulan
tersebut dari bukti-bukti yang ada.
Sebagai contoh, seperangkat rule di bawah ini akan digunakan untuk
menjelaskan proses forward chaining dan backward chaining.
Kasus 1: Identifikasi Binatang
32
Chapter 3. Sistem Berbasis Aturan
Rule 1:
If
Menyusui = tidak and
Kaki > 4 and
Warna bulu = polos
Then Binatang = belalang
Rule 2:
If
Menyusui = ya and
kaki = 4 and
berdarah = panas
Then Kelas = mamalia
Rule 3:
If
Makanan = binatang
Then Kategori = carnivora
Rule 4:
If
Makanan = tumbuhan
Then Kategori = herbivora
Rule 5:
If
Kelas = mamalia and
Warna bulu = berbintik and
Tinggi > 80 centimeter
Then Binatang = Harimau
Rule 6:
If
Kelas = mamalia and
Warna bulu = polos and
Tinggi > 80 centimeter
Then Binatang = Kuda
33
Chapter 3. Sistem Berbasis Aturan
Rule 7:
If
Kelas = mamalia and
Kategori = herbivora and
Warna bulu = bergaris and
Tinggi > 80 centimeter
Then Binatang = Zebra
Rule 8:
If
Kelas = mamalia and
Kategori = carnivora and
Warna bulu = polos or berbintik or bergaris and
Tinggi < 80 centimeter
Then Binatang = Kucing
Rule 9:
If
Kaki = 2 and
Berdarah = panas and
Warna Bulu = berbintik or
Menyusui = tidak
Then Binatang = elang
Rule 10:
If
Berdarah = dingin and
Tinggi < 80 centimeter
Then Binatang = salmon
Pengetahuan yang telah didefinisikan di atas dapat juga direpresentasikan dalam bentuk diagram pohon and-or tree, seperti di tunjukkan
dalam Gambar 3.1.
Data yang diberikan oleh user diletakkan pada
bagian kiri gambar, sedangkan kesimpulan berada pada bagian kanan
gambar. Beberapa data dihubungkan dengan kesimpulan memiliki tanda
penghubung lengkung mewakili hubungan AND, sedangkan tanpa penghubung
lengkung mewakili OR. Sedangkan, intermediate facts atau parameter
34
Chapter 3. Sistem Berbasis Aturan
diletakkan di tengah-tengah di antara data dan kesimpulan.
Sekarang muncul pertanyaan, dari fakta-fakta yang telah tersedia di
atas bagaimana sistem pakar melakukan proses tracing dari satu fakta
ke fakta berikutnya dengan menggunakan rule yang telah ditentukan
sehingga menghasilkan suatu kesimpulan? Proses ini dikenal dengan
istilah reasoning. Dalam sistem berbasis aturan dikenal adanya dua
macam proses reasoning, yaitu forward reasoning dan backward reasoning. Sekarang marilah kita bicarakan masing-masing proses reasoning
tersebut dengan lebih detail, diawali dengan pembahasan tentang forward reasoning.
3.2.1
Forward Reasoning
Note:
Dalam forward reasoning, proses inferensi dimulai dari seperangkat data
yang ada menuju ke kesimpulan. Pada proses ini akan dilakukan pengecekan terhadap setiap rule untuk melihat apakah data yang sedang diobservasi tersebut memenuhi premis dari rule tersebut. Apabila memenuhi,
maka rule akan dieksekusi untuk menghasilkan fakta baru yang mungkin
akan digunakan oleh rule yang lain. Proses pengecekan rule ini disebut
sebagai rule interpretation. Pada sistem berbasis pengetahuan, rule interpretation (interpretasi rule) dilakukan oleh inference engine. Proses
interpretasi rule ini merupakan proses berulang seperti terlihat dalam
Gambar 3.2
Fungsi masing-masing step untuk gambar di atas dijelaskan sebagai
berikut:
1. Matching. Pada step ini, setiap rule yang ada pada basis pengetahuan dibandingkan dengan fakta-fakta yang diketahui untuk mencari rule mana yang memenuhi (istilah ’memenuhi’ berarti: situasi,
premis, atau antecedent bernilai benar).
35
Chapter 3. Sistem Berbasis Aturan
Figure 3.1: Representasi and-or tree untuk identifikasi binatang.
36
Chapter 3. Sistem Berbasis Aturan
Figure 3.2: Proses inferensi forward reasoning.
2. Conflict Resolution. Pada langkah pertama sangat mungkin dihasilkan suatu kondisi dimana beberapa rule dipenuhi. Conflict
Resolution bertugas untuk mencari rule mana yang memiliki prioritas tertinggi yang berpotensi untuk dieksekusi.
3. Execution. Langkah terakhir dari proses forward reasoning adalah
eksekusi (firing) dari rule. Proses ini menghasilkan dua kemungkinan, yaitu: fakta baru diturunkan dan ditambahkah fact base atau
rule baru dihasilkan dan ditambahkan ke knowledge base.
Sebagai contoh penyelesaian Kasus 1 di atas dengan menggunakan
forward reasoning dimulai dengan memasukkan fakta-fakta berikut:
Database:
Menyusui = ya
Jumlah kaki = 4
Berdarah = panas
Warna bulu = berbintik
Tinggi = 20 cm
Makanan = binatang
Hasil penelusuran dari proses eksekusi ditunjukkan dalam Tabel 3.1.
37
Chapter 3. Sistem Berbasis Aturan
Table 3.1: Hasil Penelusuran Dengan Forward Reasoning
Execution Applicable
Selected Derived
cycle
rules
rule
fact
1
2, 3
2
Kelas = mamalia
2
2, 3
3
Kategori = carnivora
3
2, 3, 7
7
Binatang = kucing
4
2, 3, 7
−−
−−
Sebagai latihan, jika fakta-fakta baru dimasukkan seperti dibawah
ini, tentukan bagaimana hasil penelusuran sistem pakar dengan menggunakan forward reasoning!
Database:
Menyusui = ya
Jumlah kaki = 4
Berdarah = panas
Warna bulu = polos
Tinggi = 2,2 meter
Kasus 2: Flood Identification
Untuk memberikan gambaran tentang penerapan sistem berbasis aturan secara nyata, berikut ini adalah sebuah contoh tentang penggunaan
forward reasoning dalam membantu menyelesaikan permasalahan banjir
seperti ditulis oleh Gonzales (1993).
Penduduk dari sebuah daerah bernama Low Lands di Florida, US,
menemukan bahwa desa dimana mereka berharap dapat menghabiskan
masa tuanya berada di daerah banjir luapan dari sungai Suwannee. Banjir selalu terjadi pada setiap musim semi. Karena itu mereka mengundang
seorang pakar Sistem Pakar bernama Dr. Paul Peters untuk membangun
sebuah sistem berbasis pengetahuan untuk memberitahu mereka mengetahui apabila banjir akan datang dan apakah perlu dilakukan evakuasi.
38
Chapter 3. Sistem Berbasis Aturan
Dr. Peters menemukan bahwa diperlukan 10 buah paramater dan
18 rule untuk menyelesaikan masalah ini. Paramater dan rule tersebut
ditunjukkan sebagai berikut:
Paramaters
Possible Values
month
any month of the year
upstream precipitation none, light, heavy
weather forecast
sunny, cloudy, stormy
river height
measurement in feet
season
dry, wet
local rain
none, light rain, heavy rain
river change
none, lower, higher
river level
low, normal, high
flood warning
yes, no
evacuation order
yes, no
39
Chapter 3. Sistem Berbasis Aturan
R1
R2
R3
If
month = may · · · oct
Then
season = wet
If
month = nov · · · apr
Then
season = dry
If
upstream = none AND
season = dry
R4
Then
change = lower
If
upstream = none AND
season = wet
R5
R6
R7
R8
Then
change = none
If
upstream = light
Then
change = none
If
upstream = heavy
Then
change = higher
If
level = low
Then
flood = no AND evac = no
If
change = none | lower AND
level = normal | lower
R9
Then
flood = no AND evac = no
If
change = higher AND
level = normal
rain = heavy
Then
flood = yes (CF = 0.4) AND evac = no
40
Chapter 3. Sistem Berbasis Aturan
R10
If
change = higher AND
level = normal
rain = light
R11
Then
flood = no AND evac = no
If
change = higher AND
level = high
rain = none | light
Then
flood = yes (CF = 0.5) AND
evac = yes (CF = 0.2)
R12
If
change = higher AND
level = high
rain = heavy
Then
flood = yes AND
evac = yes (CF = 0.8)
R13
R14
R15
R16
If
height < 10
Then
level = low
If
height ≥ 10 AND ≤ 16
Then
level = normal
If
height > 16
Then
level = high
If
forecast = sunny
Then
rain = none
41
Chapter 3. Sistem Berbasis Aturan
R17
R18
If
forecast = cloudy
Then
rain = light
If
forecast = stormy
Then
rain = heavy
Sistem berbasis aturan di atas dapat digambarkan dalam bentuk inference network seperti terlihat dalam Gambar 3.3.
Figure 3.3: Inference network dari kasus 2.
Lebih lanjut Dr. Peter melakukan identifikasi untuk setiap rule sebagai berikut:
1. Memiliki nomor rule.
2. Memiliki parameter yang digunakan dalam premise (upstream element).
3. Memiliki parameter yang digunakan dalam kesimpulan (downstream
42
Chapter 3. Sistem Berbasis Aturan
element).
4. Memiliki seperangkat premise.
5. Memiliki seperangkat kesimpulan.
Dan identifikasi untuk setiap paramater:
1. Nama dari parameter tersebut.
2. Seperangkat rule yang menurunkan nilai untuk parameter ini (disebut set-by).
3. Seperangkat rule yang menggunakan parameter ini untuk bagian
premise (disebut premise-for).
4. Nilai dari parameter ini yang berasosiasi dengan confidence fator
(CF).
Sebagai contoh rule R1 dan parameter change dideskripsikan sebagai:
Rule:
R1
Upstream-elements:
month
Downstream-elements: season
Premises:
month = may · · · oct
Conclusions:
season = wet
Parameter:
change
Set-by:
(R3 R4 R5 R6)
Premise-for:
(R8 R9 R10 R11 R12)
Values:
−−
Berdasarkan Gambar 3.3, dapat dilihat bahwa terdapat beberapa parameter sebagai input data dan beberapa parameter untuk menarik kesimpulan, yaitu:
Input data:
(month upstream forecast height)
Conclusions:
(flood evac)
43
Chapter 3. Sistem Berbasis Aturan
Misalkan, dari beberapa sensor yang telah terpasang diketahui data
sebagai berikut:
month = may
upstream = light
forecast = cloudy
height = 15
Dengan memadankan fakta yang ada dengan rule-based dan Gambar
3.3, antrian rule yang akan diproses adalah sbb:
Q = (R1 R2 R3 R4 R5 R6 R13 14 R15 R16 R17 R18)
Rule pertama yang harus diuji adalah premise dari R1, apakah match
dengan salah satu fakta. Seperti terlihat dalam R1, nilai may dan parameter month terpenuhi, maka R1 dieksekusi dan menghasilkan season=wet.
Parameter season terpakai dalam premise R3 dan R4, tapi karena kesua rule tersebut sudah ada di dalam antrian Q, maka R3 dan R4 tidak
perlu ditambahkan dalam Q. Selanjutnya R1 dikeluarkan dari Q dan pengujian dilanjutkan menuju R2. R2, R3 dan R4 tidak memenuhi, maka
ketiga rule tersebut dikeluarkan dari Q, pengujian dilanjutkan ke R5.
R5 memenuhi dan menghasilkan change=none. Nilai dari dari parameter change digunakan oleh R8, R9, R10, R11, R12 yang tidak termasuk
dalam, maka update terhadap Q menghasilkan:
Q = (R6 R13 14 R15 R16 R17 R18 R8 R9 R10 R11 12)
dan diketahui fakta-fakta:
month = may
upstream = light
forecast = cloudy
height = 15
season = wet
change = none
44
Chapter 3. Sistem Berbasis Aturan
Proses ini dilanjutkan sampai Q menjadi kosong. Setelah Q kosong,
diketahui fakta-fakta sebagai berikut:
month = may
upstream = light
forecast = cloudy
height = 15
season = wet
change = none
level = normal
rain = light
flood = no
evac = no
3.2.2
Backward Reasoning
Note:
Sekarang mari kita beralih dari forward reasoning ke backward reasoning. Mekanisme inferensi pada backward reasoning berbeda dengan forward reasoning. Walaupun kedua proses melibatkan pengujian terhadap
masing-masing rule, backward reasoning mulai dari konklusi yang diharapkan menuju fakta-fakta yang mendukung konklusi tersebut. Misalnya,
pada saat awal fakta yang diketahui dalam database kosong, seperti:
Fakta yang diketahui:
()
Dengan mengambil contoh pada Kasus 1: Identifikasi Binatang, didapatkan bahwa goal yang diharapkan adalah:
Goal:
(Binatang)
Dengan melihat semua rule yang ada pada knowledge-based didapatkan bahwa rule yang dapat menurunkan goal tersebut adalah: 1,5,6,7,8,9,dan
45
Chapter 3. Sistem Berbasis Aturan
10. Eksekusi dimulai dari rule 1. Premise pertama dari rule tersebut
(menyusui=tidak) diuji dan ternyata tidak ada nilai menyusui ditemukan dalam database. Karena tidak ada rule yang dapat menurunkan
nilai dari premise menyusui, maka inference engine bertanya kepada user:
Apakah termasuk binatang menyusui?
Selanjutnya user memberi respon dengan menambahkan fakta pada
database:
Fakta yang diketahui:
( (Menyusui = ya) )
Sampai disini, evaluasi menunjukkan bahwa premise pada rule 1 tidak
sesuai dengan fakta pada database, karena itu rule 1 tidak dapat diproses.
Evaluasi dilanjutkan menuju rule 5. Premise pertama adalah (Kelas=mamalia).
Proses pencarian terhadap rule menemukan bahwa rule 2 mampu menurunkan nilai untuk kelas, karena itu untuk sementara proses pencarian
untuk solusi binatang dihentikan dan menambahkan parameter dibawah
ini pada stack:
Goal:
(kelas binatang)
Sekarang evaluasi dilanjutkan untuk rule 2. Premise pertama pada
rule 2 adalah menyusui, karena menyusui ada di dalam database dengan
nilai ya, pengujian dilanjutkan ke premise berikutnya. Nilai kaki tidak
ada dalam database, maka inference engine bertanya kepada user:
Berapa jumlah kaki binatang tersebut?
User memberikan response dengan nilai 4, maka sekarang update terhadap database menghasilkan:
Fakta yang diketahui:
( (Menyusui = ya) )
( (Kaki = 4) )
46
Chapter 3. Sistem Berbasis Aturan
Premise ketiga dari rule 2 menunjuk pada sebuah fakta baru lagi
yang berkaitan dengan suhu badan dari binatang. Dalam istilah biologi,
berdasarkan suhu badannya binatang dibedakan atas binatang berdarah
panas dan binatang berdarah dingin. Karena fakta tentang suhu badan
ini belum ada dalam database, maka inference engine akan bertanya
kepada user.
Binatang tersebut berdarah panas atau dingin?
User memberikan response dengan nilai panas, maka update terhadap
database menghasilkan kumpulan fakta-fakta baru sebagai berikut:
Fakta yang diketahui:
( (Menyusui = ya) )
( (Kaki = 4) )
( (Berdarah = panas) )
Karena semua fakta pada premise dari rule 2 telah terpenuhi, maka
sekarang rule 2 firing dan memberikan keluaran (goal) dengan nilai mamalia. Sehingga fakta baru lagi dimasukkan ke dalam database menjadi:
Fakta yang diketahui:
( (Menyusui = ya) )
( (Kaki = 4) )
( (Berdarah = panas) )
( (Kelas = mamalia) )
Setelah goal kelas memperoleh jawaban, sekarang sistem kembali ke
rule 5 dengan goal: binatang.
Premise pertama pada rule 5 berpadanan dengan kelas=mamalia
seperti terdapat dalam database. Evaluasi dilanjutkan ke premise berikutnya. Fakta dari premise ini ternyata tidak ditemukan dalam database,
sehingga inference engine akan bertanya kepada user:
Bagaimana warna bulu dari binatang tersebut?
47
Chapter 3. Sistem Berbasis Aturan
User menjawab dengan nilai berintik. Sehingga fakta baru lagi ditambahkan pada database menjadi seperti berikut:
Fakta yang diketahui:
( (Menyusui = ya) )
( (Kaki = 4) )
( (Berdarah = panas) )
( (Kelas = mamalia) )
( (Warna bulu = berbintik) )
Masih pada rule 5, premise terakhir diuji. Fakta dari premise ini
ternyata tidak ditemukan dalam database, sehingga inference engine
akan bertanya kepada user:
Berapa tinggi binatang tersebut?
Maka user meresponse dengan nilai tinggi = 20 cm. Fakta ini selanjutnya dimasukkan kembali ke dalam database menghasilkan daftar
fakta sebagai berikut:
Fakta yang diketahui:
( (Menyusui = ya) )
( (Kaki = 4) )
( (Berdarah = panas) )
( (Kelas = mamalia) )
( (Warna bulu = berbintik) )
( (Tinggi = 20 cm) )
Karena fakta ini tidak memenuhi premise terakhir dari rule 5, maka
rule 5 tidak dikerjakan. Berlanjut ke rule 6. Seperti terlihat bahwa
premise kedua dari rule 6 tidak memenuhi fakta warna bulu yang ada
dalam database, maka rule 6 tidak dikerjakan. Berlanjut ke rule 7.
Premise pertama pada rule 7 terpenuhi. Maka evaluasi dilanjutkan
ke premise berikutnya. Premise ini memunculkan fakta baru: kategori
48
Chapter 3. Sistem Berbasis Aturan
yang tidak ada dalam database. Dari penelusuran yang dilakukan, sistem
mendapati bahwa fakta ini dapat dihasilkan oleh rule 3 dan 4. Untuk
sementara goal binatang digeser masuk ke dalam stack, goal yang baru
adalah:
Goal:
(kategori binatang)
Evaluasi terhadap rule 3 menghasilkan fakta baru: makanan. Karena
makanan tidak ada dalam database, sistem akan bertanya kepada user:
Apakah makanan dari binatang tersebut?
User menjawab dengan nilai makanan adalah binatang. Sehingga
rule 3 firing dan menghasilkan nilai keluaran dari goal adalah carnivora.
Sedangkan isi dari database sekarang diupdate menjadi seperti berikut:
Fakta yang diketahui:
( (Menyusui = ya) )
( (Kaki = 4) )
( (Berdarah = panas) )
( (Kelas = mamalia) )
( (Warna bulu = berbintik) )
( (Tinggi = 20 cm) )
( (Kategori = carnivora) )
Karena goal kategori sudah terjawab, goal ini dibuang dari stack.
Proses dilanjutkan kembali ke goal mula-mula. Seperti terlihat, premise
kedua dari rule 7 tidak terpenuhi. Maka rule 7 tidak dikerjakan. Dilanjutkan dengan rule 8. Nampaknya semua premise terpenuhi oleh faktafakta yang ada dalam database. Menghasilkan keluaran binatang yang
dimaksud adalah kucing.
Karena binatang telah diketahui, maka binatang dikeluarkan dari
goal. Karena itu stack sekarang menjadi kosong, proses backward reasoning berhenti sampai di sini. Secara keseluruhan urutan proses backward
49
Chapter 3. Sistem Berbasis Aturan
reasoning dari identifikasi binatang ini dapat digambarkan dalam Gambar 3.4.
Figure 3.4: Urutan backward reasoning untuk kasus identifikasi binatang.
Kasus 2: Beverage and Main Course Identification
Sebagai contoh kasus ke-2 untuk backward reasoning, mari kita perhatikan Beverage and Main Course Identification. Contoh ini diambil
dari Gonzales(1993).
Perhatikan rule di bawah ini:
Parameter-parameter yang digunakan adalah:
guest-age: positive integer between 15 and 100
alcohol-indicated: yes/no
meal: formal/informal
drink: wine/beer/soda
guest: boss/neighbor/friend
dinner: fish/veal/read-meat/pultry/pizza
day: moday/tuesday/ . . . /sunday
Sistem dimulai dengan:
Known Fact Base: ()
Misalnya goal yang diharapkan adalah:
50
Chapter 3. Sistem Berbasis Aturan
Goals: (drink wine-type dinner)
Tentukan hasil akhir dari database jika saat ini adalah Tuesday, kita
mengundang neighbor berumur 30 th untuk casual meal.
R1
If
guest-age < 21
Then alcohol-indecated = no
R2
If
guest-age ≥ 21
Then alcohol-indecated = yes
R3
If
alcohol-indecated = yes AND
meal = formal
Then drink = wine
R4
If
alcohol-indecated = yes AND
guest = boss
Then drink = wine
R5
If
alcohol-indecated = yes AND
guest = neighbor
Then drink = beer
R6
If
drink = wine AND
dinner = fish
Then wine-type = white
R7
If
drink = wine AND
dinner = red-meat
Then wine-type = red
R8
If
guest = boss AND
day = friday
Then dinner = fish
51
Chapter 3. Sistem Berbasis Aturan
R9
If
guest = boss AND
day <> friday
R10
R11
R12
Then
dinner = red-meat
If
guest-age < 21
Then
dinner = pizza
If
guest-age ≥ 21
Then
dinner = fish
If
alcohol not indicated
Then
drink = soda
52
Fly UP