Katedra Podstaw Konstrukcji Maszyn

Rok akademicki 1998/99

Metody i Techniki Sztucznej Inteligencji

Laboratorium nr 5

Indukcja reguł metodą generowania pokryć

1.Cel ćwiczenia

Celem ćwiczenie jest nabycie umiejętności opisywania danej przestrzeni zainteresowania za pomocą przykładów oraz uogólniania tych opisów do zbioru reguł stosując metodę generowania pokryć.

2.Wprowadzenie

Ćwiczenie obejmuje następujące zagadnienia podstawowe:

• identyfikacja reguł za pomocą generowania pokryć,

• pojęcie cechy obiektu i wartości cechy,

• pojęcie obiektu,

• pojęcie klasy obiektu,

• pojęcie przykładów uczących,

• pojęcie przykładów testowych,

• pojęcie reguły.

Metoda generowania pokryć jest jedną z szeroko stosowanych indukcyjnych metod „uczenia maszynowego” używanych do pozyskiwania wiedzy. Celem metody generowania pokryć jest utworzenie nowych reguł poprawnie opisujących przykłady wstępnie zaklasyfikowane do danej klasy i przykłady (tzw. kontrprzykłady) nie należące do tej klasy [5]. Metoda ta jest oparta na idei budowania pokryć stosowanych w algorytmach AQ opracowanych przez prof. Michalskiego.

Cecha obiektu opisuje jego własności i właściwości np. cechą owoców lub warzyw jest ich kolor. Wartościami jakie ta cecha może przyjmować są np.: czerwony, zielony itp.

Opisywanym takimi cechami obiektem może być np. JABŁKO lub PAPRYKA.

Zbiór owoców (jabłka, gruszki, itp.) lub warzyw (papryki, pomidory, itp.) jest klasą obiektów o podobnych (identycznych) cechach.

Na podstawie zdefiniowanych wcześniej: klas obiektów, obiektów, cech oraz ich wartości możliwe staje się zapisanie przykładów uczących opisujących dane obiekty np.:

kolor kształt smak obiekt

czerwony okrągły słodki jabłko

zielony okrągły ostry papryka

Na podstawie tak przygotowanego zbioru uczącego, indukowany jest zbiór reguł zgodnie z przedstawioną poniżej koncepcją generowania pokryć.

Przykłady testowe służą do testowania wygenerowanego zbioru reguł. Postać tych przykładów jest identyczna jak przykładów uczących.

Reguła zbudowana jest przesłanki oraz konkluzji. Poniżej przedstawiono ogólną postać reguły [1]:

jeśli przesłanka to konkluzja (działanie)

Poniższy przykład przedstawia ogólną koncepcję sposobów generowania pokryć. Przyjmujemy, że znany jest pewien skończony zbiór przykładów, które będą podlegać klasyfikacji. Załóżmy, że w tym zbiorze wyróżnić możemy podzbiór przykładów należących do pewnej klasy JABŁKA oraz podzbiór przykładów nie należących do tej klasy a należących do klasy PAPRYKA. Dla przykładu przyjmijmy, że są dane trzy przykłady:

JABŁKO₁ = [kolor=czerwony] [kształt=okrągły] [smak=słodki]

PAPRYKA₁ = [kolor=czerwony] [kształt=podłużny] [smak=słodki]

PAPRYKA₂ = [kolor=zielony] [kształt=okrągły] [smak=ostry]

W omawianej metodzie, dla klasy JABŁKO oraz PAPRYKA tworzone są różnice wartości cech d_i, przy czym w poniższym przykładzie każda pojedyncza część różnicy opisuje klasę JABŁKO i nie opisuje klasy PAPRYKA. Różnice mają postać:

JABŁKO₁ = [kolor=czerwony] [kształt=okrągły] [smak=słodki]

- PAPRYKA₁ = [kolor=czerwony] [kształt=podłużny] [smak=słodki]

d₁ = [kształt=okrągły]

oraz

JABŁKO₁ = [kolor=czerwony] [kształt=okrągły] [smak=słodki]

- PAPRYKA₂ = [kolor=zielony] [kształt=okrągły] [smak=ostry]

d₂ = [kolor=czerwony] [smak=słodki]

Pokrycia budujemy łącząc kolejno każdy z pojedynczych warunków różnicy d₁ z każdym z pojedynczych warunków różnicy d₂. Dla powyższego przykładu mamy:

C₁ = [kształt=okrągły] [kolor=czerwony]

C₂ = [kształt=okrągły] [smak=słodki]

Identyczna zasada obowiązuje przy tworzeniu różnic oraz przy budowie pokryć opisujących klasę PAPRYKA a nie opisujących klasy JABŁKO. Różnice mają postać:

PAPRYKA₁ = [kolor=czerwony] [kształt=podłużny] [smak=słodki]

- JABŁKO₁ = [kolor=czerwony] [kształt=okrągły] [smak=słodki]

d₁ = [kształt=podłużny]

oraz

PAPRYKA₂ = [kolor=zielony] [kształt=okrągły] [smak=ostry]

- JABŁKO₁ = [kolor=czerwony] [kształt=okrągły] [smak=słodki]

d₂ = [kolor=zielony] [smak= ostry]

Pokrycia dla klasy PAPRYKA mają postać:

C₁ = [kolor=zielony] [kształt=podłużny]

C₂ = [kolor=zielony] [smak=ostry]

W celu pozyskania reguł ze zbioru zapisanych przykładów, zastosować można program AQ15c [2] [4]. Program jest implementacją algorytmu generowania pokryć STAR [3]. Program działa w środowisku DOS lub Windows w trybie tekstowym.

W celu wygenerowania reguł należy przygotować plik z przykładami uczącymi (o rozszerzeniu *.dat) zawierający:

• tablicę parametrów uruchomienia programu (parameters),

• tablicę opisującą dziedzinę zastosowania (variables),

• tablice cech wraz z ich wartościami (names),

• tablice przykładów uczących z nazwą klasy (events),

• oraz (opcjonalnie) tablice przykładów testowych (tevents).

W przypadku zapisu tablicy „variables” zawierającej nazwy cech, możliwe jest zapisanie typu tych cech. Wyróżnić możemy trzy podstawowe typy cech:

- nom - cecha, której zbiór wartości nie jest uporządkowany np. kolor: zielony, czerwony, itp.,

- lin - cecha, której zbiór wartości jest uporządkowany z zachowaniem relacji „>”, np.: liczba kół pojazdów: jeden, dwa, itp.,

- cyc - cecha, której zbiór wartości jest uporządkowany w sposób cykliczny z zachowaniem relacji „>” np.: miesiące: styczeń, luty, itd.

Do przygotowania pliku należy użyć dowolnego edytora tekstowego (UWAGA: w pliku nie należy stosować znaku tabulacji). Szczegóły dotyczące formatu zapisu przykładów w plikach zostaną podane przez prowadzącego zajęcia. Korzystać można także z załączonego do instrukcji wydruku przykładowego pliku pojazdy.dat.

Program uruchamia się wydając polecenie w linii komend DOS'a (należy stosować nazwy plików formatu „8.3”)

aqpc.exe < nazwa_pliku_z_danymi > nazwa_pliku_z_regułami

Sposób przeprowadzenia ćwiczenia

Każda z sekcji otrzyma od prowadzącego zajęcia notatkę z zidentyfikowanymi klasami, cechami oraz wartościami cech, na podstawie których należy zapisać przykłady opisujące daną dziedzinę zastosowania.

Należy zapisać co najmniej 5 przykładów dla każdej klasy. Po przygotowaniu odpowiedniego pliku z przykładami należy uruchomić program AQ15c w celu wygenerowania reguł. W przypadku stwierdzenia błędów w zapisie należy je usunąć aż do uzyskania zbioru reguł.

Po wygenerowaniu reguł należy dopisać przykłady testowe (patrz plik przykładowy pojazdy.dat) w celu testowania reguł.

Zaliczenie ćwiczenia polega na wykonaniu czynności podanych w instrukcji oraz opracowaniu sprawozdania zawierającego:

1. opracowany zbiór przykładów,

2. opracowany zbiór reguł,

3. uzyskane tablice klasyfikacji przykładów testowych,

4. wnioski do przeprowadzonego ćwiczenia.

 

Literatura

[1] cholewa W., pedrycz W.: Systemy doradcze, Skrypt nr 1447, Politechnika Śląska, Gliwice 1987.

[2] MANIAK P.: Zastosowanie metod uczenia maszynowego do akwizycji wiedzy z zakresu konstruowania maszyn, Praca dyplomowa magisterska, Gliwice 1995.

[3] MICHALSKI R. S.: A Theory and Methodology of Inductive Learning, Artificial Intelligence 20 (1983), pp. 111 - 161.

[4] MOCZULSKI W.: Metody pozyskiwania wiedzy dla potrzeb diagnostyki maszyn, praca habilitacyjna, Zeszyty naukowe Pol. Śl. nr 130 - Mechanika, Gliwice 1997.

[5] MULAWKA J.: Systemy ekspertowe, WNT, Warszawa 1996.

 

„pojazdy.dat” (komentarze w nawiasach /* */ nie są częścią formatu pliku)

parameters /* tablica parametrów uruchomieniowych programu */

run mode ambig trim wts maxstar echo verbose test

1 ic pos mini cpx 10 v 1 mc

variables /* tablica definiująca rozpatrywane cechy; kolumna: type - rodzaj */

type size name /* cechy, size - liczba wartości cechy, name - nazwa cechy */

lin 4 liczba_kol

nom 5 silnik

lin 4 liczba_osob

lin 4 ladunek

liczba_kol-names /* tablice definiujące wartości rozpatrywanych cech */

value name

0 2_kola

1 3_kola

2 4_kola

3 pow_4_kol

silnik-names

value name

0 elektr

1 benzyn

2 diesel

3 bez_sil

4 nap_hyb

liczba_osob-names

value name

0 1_os

1 2_os

2 3_os

3 pow_4_os

ladunek-names

value name

0 minimum

1 maly

2 sredni

3 duzy

rower-events /* tablice z przykładami dla rozpatrywanych klas */

# l_kol silnik l_osob ladunek /* wiersz z nazwami cech */

1 2_kola bez_sil 1_os minimum /* wiersz z przykładem dla danej klasy */

2 2_kola bez_sil 2_os minimum

3 3_kola bez_sil 1_os minimum

4 2_kola elektr 1_os minimum

motocykl-events

# l_kol silnik l_osob ladunek

1 2_kola benzyn 1_os minimum

2 2_kola benzyn 1_os maly

3 2_kola benzyn 2_os minimum

4 2_kola benzyn 2_os maly

5 3_kola benzyn 2_os maly

sam_os-events

# l_kol silnik l_osob ladunek

1 4_kola benzyn pow_4_os maly

2 4_kola benzyn pow_4_os sredni

3 4_kola elektr pow_4_os maly

4 4_kola elektr pow_4_os sredni

5 4_kola diesel pow_4_os maly

6 4_kola diesel pow_4_os sredni

7 4_kola benzyn 2_os minimum

8 4_kola benzyn 2_os maly

9 4_kola benzyn 2_os sredni

10 4_kola diesel 2_os sredni

11 4_kola nap_hyb 2_os maly

12 4_kola nap_hyb pow_4_os sredni

ciezar-events

# l_kol silnik l_osob ladunek

1 4_kola diesel 2_os sredni

2 4_kola diesel 2_os duzy

3 4_kola diesel 3_os sredni

4 4_kola diesel 3_os duzy

5 pow_4_kol diesel 2_os sredni

6 pow_4_kol diesel 2_os duzy

7 pow_4_kol diesel 3_os sredni

8 pow_4_kol diesel 3_os duzy

sam_os-tevents /* tablice z przykładami testowymi */

# l_kol silnik l_osob ladunek

1 ? elektr ? maly /* w przypadku, gdy nie znamy wartości */

2 4_kola ? 2_os sredni /* danej cechy, umieszczamy znak „?” */

 

„pojazdy.rul”

rower-outhypo /* tablice z wygenerowanymi regułami */

# cpx

1 [l_kol=2_kola..3_kola] [silnik=elektr,bez_sil] (t:4, u:4)

/* t - liczba przykładów, które brały udział w generowaniu danej reguły */

/* u - liczba przykładów, które brały udział tylko i wyłącznie w generowaniu danej reguły */

motocykl-outhypo

# cpx

1 [l_kol=2_kola..3_kola] [silnik=benzyn] (t:5, u:5)

 

sam_os-outhypo

# cpx

1 [l_osob=pow_4_os] (t:6, u:6)

2 [l_kol=4_kola] [l_osob=2_os] [ladunek=minimum..sredni] (t:4, u:4)

 

ciezar-outhypo

# cpx

1 [silnik=diesel] [l_osob=2_os..3_os] (t:8, u:8)

 

 

This learning used:

System time: 0.010 seconds

User time: 0.00 seconds

/* tablica z klasyfikacjami przykładów testowych do poszczególnych klas */

***************************************************************************

Testing Summary (Rform)

***************************************************************************

# Event Class member rower motocykl sam_os ciezar

---------------------------------------------------------------------------

sam_os:

1 rower no 0.50 0.00 0.33 0.00

2 0.00 0.00 0.40 0.00

---------------------------------------------------------------------------

# Events Correct: 1 # Events Incorrect: 1 Accuracy: 50%

...........................................................................

# Total Selectors: 10 # Total Complexes: 5

***************************************************************************

/* wartości liczbowe - z przedziału [0, 1] - w kolumnach pod nazwami klas są wartościami */

/* stopni pewności co do przynależności klasyfikowanego przykładu do danej klasy */

 

This testing used:

System time: 0.016 seconds

User time: 0.00 seconds

---