Instytut

Podstaw

Konstrukcji

Maszyn

Wydział

Mechaniczny

Technologiczny

Politechnika

Śląska

ul. Konarskiego 18a

44-100 Gliwice

tel. [phone]

fax. [phone]

http://ipkm.polsl.pl

Metody Sztucznej

Inteligencji

Rok akademicki 2012/13

Instrukcja do ćwiczeń laboratoryjnych

Temat:

Zapisywanie reguł w postaci
tablic decyzyjnych

Opracował: dr inż. P. Chrzanowski

Gliwice 2013-02-05

- 1/13 -

1. Cel ćwiczenia

Celem ćwiczenia jest zapoznanie się z najważniejszymi zagadnieniami związanymi z zapisywa-

niem reguł i definiowaniem tablic decyzyjnych.

2. Wprowadzenie teoretyczne

Jednym ze sposobów reprezentacji wiedzy jest forma opisowa, przedstawiająca kombinację

działań i warunków. Prowadzi to do formułowania pytań lub testów, zbiorów potencjalnych

odpowiedzi i działań podjętych dla danego zbioru odpowiedzi. Do zredukowania niejednoznacz-

ności czy ułatwienia interpretacji rozwiązywanego problemu, stosowana jest tabelaryczna forma

zapisu warunków oraz działań. Tablice decyzyjne są taką formą zapisu wiedzy umożliwiającą

komputerowe wspomaganie podejmowania decyzji. Stosowane są między innymi do:

• opisu zadań przekazywanych innemu człowiekowi,

• opisu funkcji wykonywanych przez komputer,

• definiowania modułu w programie lub systemie,

• wspomagania procesu projektowania,

• standaryzacji sposobów komunikacji pomiędzy inżynierami wiedzy.

Tablice decyzyjne mogą być pierwowzorem regułowej reprezentacji wiedzy, jak też służyć

do badania kompletności (braku/nadmiaru) reguł i ich niesprzeczności.

2.1. Budowa tablic decyzyjnych

Wśród form zapisu tablic decyzyjnych możemy wyróżnić:

• tablice o ograniczonych wejściach (LEDT),

• tablice o rozszerzonych wejściach (EEDT),

• tablice o mieszanych wejściach (MEDT).

Ogólna postać tablicy decyzyjnej została przedstawiona na Rys.1

obszar opisów warunków

obszar warunków

obszar opisów działań

obszar działań

Rysunek 1: Obszary tablicy decyzyjnej

Kolumny znajdujące się z prawej strony tablicy wyznaczają reguły. Obszar warunków za-

wiera zbiór odpowiedzi na pytania znajdujące się w obszarze opisu warunków. Obszar opisów

działań zawiera zbiór wszystkich rozpatrywanych działań, natomiast obszar działań zawiera

zbiór działań należących do określonej reguły.

Gliwice 2013-02-05

- 2/13 -

Rys. 2 przedstawia przykładową tablicę decyzyjną, w której:

• wiersze oznaczone symbolem C zawierają warunki, pytania, testy,

• wiersze oznaczone symbolem A zawierają działania i/lub wnioski,

• wiersze oznaczone symbolem E zawierają wyjścia,

R

1

R

2

R

3

R

4

C

1

grypa

Y

Y

N

N

C

2

zapalenie płuc

Y

N

Y

N

A

1

terapia 1

X

A

2

terapia 2

X

A

3

terapia 3

X

A

4

terapia 4

X

E

1

stop

X

X

X

X

Rysunek 2: Postać tablicy decyzyjnej

Definicje reguł umieszczone są w kolumnach oznaczonych numerami od R

1

do R

n

. Reguła

zawiera wartości warunków, które pozwalają na rozstrzygnięcie, czy warunki reguły są uznawane

za spełnione, czy też nie. Dopuszczalnymi wartościami warunków są:

• Y oznaczające odpowiedź TAK,

• N oznaczające odpowiedź NIE,

• -" oznaczające dowolną wartość/odpowiedź (TAK/NIE) - bez znaczenia.

Kolumna opisująca regułę może zawierać następujące oznaczenia działań (i wyjść):

• -", jeżeli działanie nie ma być wykonywane,

• "X", jeżeli działanie ma być wykonane. Działania zaznaczone do wykonania są realizo-

wane według kolejności ź góry na dół".

Zakłada się, że każda reguła posiada dokładnie jedno wyjście. Przyjmuje się, że działania

A

1

, A

2

, .., realizowane są w kolejności z góry na dół. Natomiast wartości warunków badane

są dla reguł w kolejności z lewej strony na prawą. Warunkiem koniecznym do uznania tablicy

decyzyjnej za tablice kompletną jest występowanie każdej możliwej kombinacji warunków jeden

i tylko jeden raz. W tablicach decyzyjnych (o podstawowej postaci) nie dopuszcza się reguł

pominiętych, nadmiarowych oraz reguł sprzecznych.

Tablica decyzyjna posiada kompletny zestaw reguł wtedy, gdy każda permutacja dopusz-

czalnych odpowiedzi na pytania jest zawarta dokładnie jeden raz w regule.

2.1.1. Reguła nadmiarowa

Jeżeli w tablicy decyzyjnej zostanie zdefiniowana reguła zawierająca ten sam zbiór warunków

jak inna reguła, oraz ten sam zbiór działań, wówczas taką regułę nazywa się nadmiarową. Na

Gliwice 2013-02-05

- 3/13 -

Rys.3, reguła R

5

jest nadmiarowa względem reguły R

2

. Stan taki jest niedopuszczalny, wobec

czego jedną z reguł należy usunąć.

R

1

R

2

R

3

R

4

R

5

C

1

Y

Y

N

N

Y

C

2

Y

N

Y

N

N

C

3

Y

N

Y

N

N

A

1

X

-

-

-

-

A

2

-

X

-

-

X

A

3

-

-

X

-

-

A

4

-

-

-

X

-

Rysunek 3: Przykład tablicy decyzyjnej z regułą nadmiarową

2.1.2. Reguła sprzeczna (konfliktowa)

Jeżeli w tablicy decyzyjnej zostanie zdefiniowana reguła zawierająca ten sam zbiór warunków

jak inna reguła, a zbiór działań jest różny wówczas taką regułę nazywa się sprzeczną. W

tablicy decyzyjnej przedstawionej na Rys.4, reguła R

5

jest sprzeczna względem reguły R

2

.

R

1

R

2

R

3

R

4

R

5

C

1

Y

Y

N

N

Y

C

2

Y

N

Y

N

N

C

3

Y

N

Y

N

N

A

1

X

-

-

-

-

A

2

-

X

-

-

-

A

3

-

-

X

-

X

A

4

-

-

-

X

-

Rysunek 4: Przykład tablicy decyzyjnej z regułą sprzeczną

2.2. Binarne drzewo decyzyjne

Istnienie reguły sprzecznej i/lub nadmiarowej w zdefiniowanej tablicy decyzyjnej jest błędem

popełnionym przez eksperta ustalającego zbiór reguł. Gdy liczba wartości każdego z warunków

wynosi 2 wówczas liczba reguł wynosi 2

N

, gdzie N jest liczbą warunków.

W przykładowej tablicy przedstawionej na Rys.2, liczba reguł wynosi 2

2

.

W przypadku N-warunkowego drzewa binarnego, którego warunki mogą przyjmować dokładnie

dwie możliwe wartości/stany TAK lub NIE, liczba reguł np. dla N = 4 wynosi 16 (Rys.5).

Każda tablica decyzyjna powinna mieć co najmniej jedno wyjście. Wyjścia mogą być czasowe

(wyjście do innej tablicy), które wprowadza się do zbioru działań oraz wyjścia stałe wprowa-

dzone w osobnych wierszach wyjść oznaczonych E

1

, E

2

, ....

Gliwice 2013-02-05

- 4/13 -

Rysunek 5: Przykład binarnego drzewa decyzyjnego dla N = 4 warunków

W tablicach decyzyjnych uwzględnia się również odpowiedź bez znaczenia oznaczaną po-

ziomą kreską, która może być rozpatrywana jako TAK lub NIE.

Zaleca się, by reguły wskazujące identyczne działania oraz posiadające identyczne wyjścia

były łączone w jedną regułę. Łączenie reguł można uzyskać między innymi przez wskazanie

wartości dowolnej -"w części warunkowej. [1]

2.3. Podstawowe cechy tablic decyzyjnych

Przykładowo rozpatrzmy następującą tablicę decyzyjną:

R

1

R

2

R

3

R

4

C

1

Y

N

-

Y

C

2

Y

-

N

Y

C

3

Y

-

-

N

A

1

X

A

2

X

A

3

X

A

4

X

A

5

X

X

E

1

X

X

X

X

Rysunek 6: Przykład tablicy decyzyjnej

Gliwice 2013-02-05

- 5/13 -

Liczba kolumnowa CC

j

dla j-tej kolunmy - określa ile elementarnych reguł zawiera reguła

złożona (posiadająca odpowiedzi bez znaczenia. W przedstawionym przykładzie dla reguły R

2

,

CC

2

= 4, gdyż można ją przedstawić w postaci:

N

N

N

N

Y

Y

N

N

Y

N

Y

N

W przypadku reguły R

3

, CC

3

= 4, gdyż można ją przedstawić w postaci:

Y

Y

N

N

N

N

N

N

Y

N

Y

N

Reguły R

2

oraz R

3

pokrywają się w zakresie dwóch ostatnich reguł elementarnych:

N

N

N

N

Y

N

Odejmując pokrycie od reguły R

3

, uzyskuje się CC

3

= 2

Mechaniczna doskonałość tablicy decyzyjnej wyraża się wg:

X

j

CC

j

=

Y

i

M

i

(1)

gdzie M

i

jest to liczba modułowa określająca liczbę wartości przyjmowanych przez warunki.

Dla przykładu przedstawionego na Rys.7: M

1

= 2, M

2

= 2, M

3

= 2, oraz CC

1

= 1,

CC

2

= 4, CC

3

= 2, CC

4

= 1. Uwzględniając zależność (1): 1 + 4 + 2 + 1 = 2 ∗ 2 ∗ 2.

Równanie (1) jest spełnione dla następującej tablicy skorygowanej:

Na kompletność tablicy decyzyjnej składają się następujące czynniki:

• każda reguła musi posiadać stałe wyjście,

• suma liczb kolumnowych musi być równa iloczynowi liczb modułowych,

• wejścia warunków każdy reguły muszą być unikalne.

Badanie unikalności wejść warunków polega na porównaniu reguły R

1

z pozostałymi regu-

łami. Jeżeli reguła ta jest unikalna, wówczas porównuje się kolejną regułę R

2

z pozostałymi.

Proces badania unikalności jest zakończony, kiedy wszystkie reguły zostaną porównane.

Dla tablic decyzyjnych można wyznaczyć następujące cechy:

RCM - macierz liczbowa wierszy - zawiera sumy wartości odpowiedzi oraz liczby odpowiedzi

bez znaczenia w poszczególnych wierszach;

Gliwice 2013-02-05

- 6/13 -

R

1

R

2

R

3

R

4

M

C

1

Y

N

Y

Y

2

C

2

Y

-

N

Y

2

C

3

Y

-

-

N

2

A

1

X

A

2

X

A

3

X

A

4

X

A

5

X

X

E

1

X

X

X

X

Rysunek 7: Przykład skorygowanej tablicy decyzyjnej

WDC - ważona liczba odpowiedzi - wyznaczana dla każdego wiersza, jako suma liczb odpo-

wiedzi bez znaczenia pomnożone przez odpowiednią liczbę kolumnową CC

j

;

DEL - liczba delta - jest to różnica między sumami odpowiedzi TAK(Y) i NIE(N);

DOM - wykaz dominancji - wskazuje, które warunki mają tendencję zdominowania innych.

Dominacje mogą być wykrywane wg następującej reguły: Warunek zawierający jedną lub więcej

odpowiedzi bez znaczenia jest zdominowany przez wszystkie warunki ponad nim, w których

reguły z odpowiedziami TAK i NIE w tym warunku (wierszu) są unikalnie różne od każdej

reguły zawierającej odpowiedzi bez znaczenia w tym wierszu.

W tablicy przedstawionej na Rys.6, warunek C

1

zawiera 3 odpowiedzi TAK, Żaden inny

warunek (wiersz) nie zawiera trzech odpowiedzi bez znaczenia pod trzema odpowiedziami

TAK. Ponadto C

1

zawiera tylko jedną odpowiedź NIE, która znajduje się nad odpowiedziami

bez znaczenia w warunkach C

2

i C

3

, co oznacza, że wszystkie odpowiedzi NIE w warunku C

1

są umiejscowione nad odpowiedziami bez znaczenia w warunkach C

2

i C

3

. Dlatego warunek

C

1

dominuje warunki C

2

i C

3

.

Przykład:

R

1

R

2

R

3

R

4

M

RCM (Y ) RCM (N ) RCM (−) W DC

DEL

DOM

C

1

Y

N

Y

Y

2

3

1

0

0

2

C

2

, C

3

C

2

Y

-

N

Y

2

2

1

1

4

1

C

3

C

3

Y

-

-

N

2

1

1

2

6

0

−

CC

1

4

2

1

8:8

Rysunek 8: Tablica decyzyjna i jej cechy [2]

Gliwice 2013-02-05

- 7/13 -

2.4. Łączenie reguł i dekompozycja tablic decyzyjnych

W przypadku, kiedy w tablicy decyzyjnej znajdują się reguły posiadające identyczny ciąg dzia-

łań, wówczas reguły te powinny być ze sobą łączone.

Ponadto, reguły posiadające identyczne ciągi działań, można łączyć jeżeli różnią się od-

powiedziami tylko w jednym warunku. Po połączeniu odpowiedź dla tego warunku będzie

odpowiedzią typu bez znaczenia.

Przykład:

Poniżej przedstawiono tablicę decyzyjną

R

1

R

2

R

3

R

4

R

5

R

6

M

C

1

Y

Y

Y

Y

Y

Y

2

C

2

-

1

2

-

4

3

4

C

3

N

N

N

N

N

N

2

C

4

A

B

B

C

B

B

3

CC

4

1

1

4

1

1

12:48

W pierwszym etapie można połączyć reguły R

2

, R

3

, R

5

, R

6

uzyskując następującą tablicę:

R

1

R

2

/R

3

/R

5

/R

6

R

4

M

C

1

Y

Y

Y

2

C

2

-

-

-

4

C

3

N

N

N

2

C

4

A

B

C

3

CC

4

4

4

12:48

W następnym etapie można połączyć reguły R

1

, R

4

i R

2

, R

3

, R

5

, R

6

uzyskując końcową postać

tablicy decyzyjnej:

R

1

/R

2

/R

3

/R

4

/R

5

/R

6

M

C

1

Y

2

C

2

-

4

C

3

N

2

C

4

-

3

CC

12

12:48

W wyniku przedstawionych operacji uzyskano jedną regułę zastępującą sześciu reguł.

Dekompozycję tablicy decyzyjnej przeprowadza się wg następującego algorytmu [2]:

1. Rozwinąć tablicę decyzyjną do postaci kompletnej,

2. Połączyć reguły,

Gliwice 2013-02-05

- 8/13 -

3. Zapewnić, że przynajmniej jeden wiersz nie posiada odpowiedzi bez znaczenia, w przy-

padku braku takiego wiersza dopisać wiersz z minimalną liczbą takich odpowiedzi,

4. Wyznaczyć cechy RCM, WDC, DEL,

5. Dokonać sortowania warunków biorąc pod uwagę wzrastającą wartość WDC z góry na

dół (główne sortowanie)

6. Dokonać osobnego sortowania zbiorów wierszy o tych samych WDC z góry w dół, przy

wzrastających DEL (sortowanie pośrednie),

7. Wyznaczyć wartość cechy DOM,

8. Przeprowadzić osobne sortowanie wierszy przez wstawienie dominujących wierszy nad

wiersze zdominowane (sortowanie drugorzędne).

9. Dokonać sortowania kolumn (reguł) począwszy od pierwszego wiersza od góry i schodząc

w dół w rozsądny sposób, tak, aby "Y"było przed Ń", a Ń"przed -", itd.

10. Dokonać przenumerowania warunków (od góry do dołu rosnąco) i reguł (od lewej do

prawej rosnąco).

Przykład:

Przyjmując, iż dekompozycja tablicy decyzyjnej została zrealizowana w punktach od 1 do 8,

dalszy etap przedstawia się następująco:

R

2

C

1

Y

Y

Y

N

C

2

-

C

3

-

Następnie, sortując kolumny w warunku C

2

otrzymuje się:

R

3

R

2

C

1

Y

Y

Y

N

C

2

Y

Y

N

-

C

3

-

-

Sortując odpowiedzi w wierszu C

2

otrzymuje się następująca postać:

R

1

R

4

R

3

R

2

C

1

Y

Y

Y

N

C

2

Y

Y

N

-

C

3

Y

N

-

-

Końcowa postać tablicy decyzyjnej po przenumerowaniu:

Gliwice 2013-02-05

- 9/13 -

R

1

R

2

R

3

R

4

C

1

Y

Y

Y

N

C

2

Y

Y

N

-

C

3

Y

N

-

-

Postać tablicy decyzyjnej po dekompozycji, zawierającj zbiór działań przedstawia Rys.9

R

1

R

2

R

3

R

4

C

1

Y

Y

Y

N

C

2

Y

Y

N

-

C

3

Y

N

-

-

A

1

X

A

2

X

A

3

X

A

4

X

A

5

X

X

X

1

X

X

X

X

Rysunek 9: Tablica po dekompozycji

3. Oprogramowanie

Do przeprowadzenia ćwiczenia stosowany jest program Interpreter Tablic Decyzyjnych, działa-

jący w środowisku Windows NT/95/98.

Rysunek 10: Okno aplikacji ITD

Gliwice 2013-02-05

- 10/13 -

Program ten umożliwia:

• edycję tablicy decyzyjnej o ściśle określonym formacie,

• zapisywanie opracowanej tablicy decyzyjnej w postaci pliku tekstowego (Plik/Zapisz),

• odczytanie pliku tekstowego zawierającego tablicę decyzyjną (Plik/Otwórz);

• interakcyjne testowanie opracowanej tablicy decyzyjnej (Tablica/Uruchom).

Format pliku zawierającego treść tablicy decyzyjnej jest następujący:

• w wierszach zapisywane są warunki (pytania), działania i/lub wnioski oraz wyjścia wraz

z wartościami reguł,

• każdy wiersz należy poprzedzić znakiem identyfikującym typ wiersza (pierwszy znak w

wierszu):

Typ wiersza

Znak identyfikacyjny

Komentarz

;

Warunek, pytanie

C

Działanie lub wniosek

A

Wyjście

E

• treść warunku, pytania, działania, wniosku lub informacji o wyjściu z tablicy należy

poprzedzić znakiem dwukropka,

• wszystkie elementy znajdujące się w wierszach tablicy należy oddzielić białym znakiem

(zalecany jest jeden znak spacji).

Wymagany format przykładowej tablicy decyzyjnej (Rys.11) przedstawiono na Rys.12.

1

2

3

4

Opis

C

Y

Y

N

N

Czy jest zimno?

C

Y

N

Y

N

Czy Pada deszcz?

A

X

-

X

-

Weź parasol.

A

X

X

-

-

Ubierz się ciepło.

A

-

-

-

X

Życzę udanego dnia.

E

X

X

X

X

Koniec.

Rysunek 11: Przykładowa tablica decyzyjna

Gliwice 2013-02-05

- 11/13 -

;

1

2

3

4

C

Y

Y

N

N

:

Czy jest zimno?

C

Y

N

Y

N

:

Czy Pada deszcz?

A

X

-

X

-

:

Weź parasol.

A

X

X

-

-

:

Ubierz się ciepło.

A

-

-

-

X

:

Życzę udanego dnia.

E

X

X

X

X

:

Koniec.

Rysunek 12: Przykład tablicy decyzyjnej zapisanej w formacie programu ITD.

4. Sposób przeprowadzenia ćwiczenia

Dla otrzymanego tematu lub opisu należy:

1. opracować zbiór reguł w postaci:

Jeżeli <przesłanka1> [i <przesłanka2> i ...] To <konkluzja>

2. zbudować kompletną tablicę decyzyjną,

3. stosując program Interpreter Tablic Decyzyjnych:

• sprawdzić kompletność opracowanej tablicy decyzyjnej,

• sprawdzić czy występują reguły sprzeczne - jeżeli tak to należy je zmodyfikować,

• sprawdzić czy występują reguły nadmiarowe - jeżeli tak to należy je zmodyfikować,

• jeżeli nie wystąpiły reguły sprzeczne sprawdzić działanie opracowanej tablicy w

przypadku wystąpienia takich reguł (celowo wprowadzić taką regułę do tablicy),

• jeżeli nie wystąpiły reguły nadmiarowe sprawdzić działanie opracowanej tablicy w

przypadku wystąpienia takich reguł (celowo wprowadzić taką regułę do tablicy).

5. Przygotowanie do ćwiczenia

Przygotowanie do ćwiczenia obejmuje zapoznanie się z treścią niniejszej instrukcji. W cza-

sie zajęć będą przedstawione zagadnienia związane z tablicami decyzyjnymi. Wiadomości z

omawianej dziedziny zostaną sprawdzone w ramach kolokwium końcowego.

5.1. Przykładowe tematy

1. Nie działa radio

2. Drukarka drukuje nieprawidłowo

Gliwice 2013-02-05

- 12/13 -

Literatura

[1] Cholewa W., Kaźmierczak J.: Monitorowanie stanu maszyn - Przetwarzanie sygnałów.

Skrypty Politechniki Śląskiej, Gliwice, 1992.

[2] Cholewa W., Czogała E.: Podstawy systemów ekspertowych. Prace IBIB PAN, 1989, nr

28, Warszawa.

[3] Cholewa W., Pedrycz W.: Systemy doradcze. Skrypt Politechniki Śląskej nr 1447, Gliwice

1987.

[4] Pollack S.L., Hicks H.T. Jr, Harrison W.J.: Tablice decyzyjne. PWN Warszawa 1975.

Gliwice 2013-02-05

- 13/13 -