Gliwice 2013-02-05
- 1/8 -
Instytut
Podstaw
Konstrukcji
Maszyn
Wydział
Mechaniczny
Technologiczny
Politechnika
Ś
l
ą
ska
ul. Konarskiego 18a
44-100 Gliwice
tel. 237 1467
fax 237 1360
http://ipkm.polsl.pl
Metody sztucznej
inteligencji
Pozyskiwanie wiedzy
Rok akademicki 2012/13
Opracował: dr in
ż
. K. Ciupke
Gliwice 2013-02-05
- 2/8 -
1. Cel
ć
wiczenia
Celem
ć
wiczenia jest zapoznanie si
ę
z zagadnieniami pozyskiwania wiedzy z baz
danych i nabycie praktycznych umiej
ę
tno
ś
ci zarówno w zakresie pozyskiwania
wiedzy jak i jej oceny.
2. Wprowadzenie
Wiedza, któr
ą
nast
ę
pnie mo
ż
e by
ć
u
ż
yta w systemach sztucznej inteligencji, mo
ż
e
by
ć
pozyskiwana z dwóch głównych
ź
ródeł:
•
od specjalistów z danej dziedziny (bezpo
ś
rednio lub po
ś
rednio poprzez np.
publikacje)
•
z baz danych.
Pozyskiwanie wiedzy od specjalistów nastr
ę
cza wiele ró
ż
norakich problemów, m.in.:
•
jest czasochłonne,
•
jest mało efektywne,
•
nie bez znaczenia jest równie
ż
niech
ęć
specjalistów do dzielenia si
ę
swoj
ą
wiedz
ą
.
Dlatego te
ż
bazy danych stały si
ę
przedmiotem zainteresowania jako
ź
ródło
potencjalnej wiedzy.
Jedn
ą
z cz
ę
sto stosowanych form pozyskiwanej wiedzy s
ą
tzw. klasyfikatory, czyli
wiedza (w postaci np. reguł lub drzew decyzyjnych) pozwalaj
ą
ca na
przyporz
ą
dkowanie
analizowanych
danych
do
okre
ś
lonych
klas
(np. przyporz
ą
dkowanie ro
ś
liny do odpowiedniego gatunku na podstawie opisuj
ą
cych
j
ą
danych). Innym sposobem pozyskiwania wiedzy z baz danych jest odkrywanie
zale
ż
no
ś
ci funkcyjnych pomi
ę
dzy danymi w bazie danych. Zagadnienie to nie jest
jednak przedmiotem niniejszego laboratorium.
3. Przykładowe zadanie
Wzi
ę
to pod uwag
ę
trzy, trudne do rozró
ż
nienia, gatunki irysów:
•
setosa,
•
versicolor,
•
virginica,
Dokonano pomiarów wybranych cech kwiatów tych ro
ś
lin, mierz
ą
c długo
ść
i szeroko
ść
kielichów oraz długo
ść
i szeroko
ść
płatków. W sumie zmierzono kwiaty
150 ro
ś
lin, po 50 z ka
ż
dego gatunku. Zadanie polega na pozyskaniu wiedzy,
pozwalaj
ą
cej na rozró
ż
nienie poszczególnych gatunków na podstawie warto
ś
ci
badanych cech.
3.1. Drzewa decyzyjne
Jedn
ą
z form zapisu wiedzy s
ą
drzewa decyzyjne. Istniej
ą
algorytmy pozwalaj
ą
ce na
pozyskiwanie wiedzy i zapisanie jej w postaci drzew. Przykładowe drzewo decyzyjne
pozyskane dla danych opisanych w punkcie 3. przedstawia Rys. 1.
Gliwice 2013-02-05
- 3/8 -
Z przedstawionego drzewa wynika,
ż
e klasyfikacja odbywa si
ę
w pierwszej kolejno
ś
ci
na podstawie szeroko
ś
ci płatka. Je
ż
eli szeroko
ść
ta jest mniejsza b
ą
d
ź
równa
0,6 mm to kwiat nale
ż
y zaklasyfikowa
ć
do gatunku setosa (w przypadku
analizowanych danych 50 przypadków zostało tak wła
ś
nie zaklasyfikowanych).
Je
ż
eli natomiast szeroko
ść
płatka jest wi
ę
ksza od 1,7 mm to mamy do czynienia
z gatunkiem virginica. W przypadku, gdy szeroko
ść
płatka jest mniejsza b
ą
d
ź
równa
1,7 mm, wówczas dalsza klasyfikacja jest mo
ż
liwa dopiero po okre
ś
leniu długo
ś
ci
płatka (je
ż
eli długo
ść
płatka <= 4,9 mm to kwiat nale
ż
y do gatunku versicolor - 48
przypadków z bazy sklasyfikowano w ten sposób) W przypadku, gdy długo
ść
płatka
byłaby wi
ę
ksza od 4,9 mm nale
ż
y znowu wzi
ąć
pod uwag
ę
szeroko
ść
płatka i na tej
podstawie dokona
ć
klasyfikacji pozostałych 6 przypadków.
Rys. 1. Przykładowe drzewo decyzyjne
3.2. Reguły
Inn
ą
form
ą
zapisu wiedzy s
ą
reguły. Ogólna posta
ć
reguły jest nast
ę
puj
ą
ca:
Je
ż
eli przesłanka to konkluzja
cz
ęść
warunkowa
cz
ęść
decyzyjna
Jest to posta
ć
reguły prostej. Reguła zło
ż
ona natomiast to taka, której cz
ęść
warunkowa składa si
ę
z kilku przesłanek, np.:
Je
ż
eli przesłanka1 i przesłanka2 to konkluzja
Podobnie jak w przypadku drzew decyzyjnych, istniej
ą
metody pozyskiwania wiedzy
z danych, pozwalaj
ą
ce na generowanie wiedzy w postaci reguł. Jak mo
ż
na łatwo
zauwa
ż
y
ć
, opisuj
ą
c drzewo decyzyjne posłu
ż
ono si
ę
ju
ż
form
ą
reguły:
Je
ż
eli szeroko
ść
płatka <= 0.6 to gatunek setosa
Gliwice 2013-02-05
- 4/8 -
Je
ż
eli szeroko
ść
płatka > 0.6 i szeroko
ść
płatka < 1.7 i
długo
ść
płatka <= 4.9 to gatunek versicolor
W istocie, obydwie formy zapisu s
ą
sobie równowa
ż
ne, tzn. ka
ż
de drzewo decyzyjne
da si
ę
zapisa
ć
w postaci reguł i odwrotnie.
4. Przykład pozyskiwania wiedzy
Do przeprowadzenia
ć
wiczenia zastosowano oprogramowanie: Orange 2.0b for
Windows (GNU General Public License) dost
ę
pne na stronie
http://www.ailab.si/orange/
4.1. Pozyskiwanie wiedzy w postaci drzewa decyzyjnego
W systemie Orange zaimplementowano dwa algorytmy generowania drzew
decyzyjnych: algorytm Classification Tree oraz algorytm C4.5 [2]. Sposób tworzenia
drzew decyzyjnych w systemie Orange oraz ich wizualizacji przedstawiono na
Rys. 2. Drzewa przedstawiono w postaci graficznej jak i w postaci tekstowej.
Rys. 2. Przykład tworzenia i wizualizacji drzew decyzyjnych.
4.2. Pozyskiwanie wiedzy w postaci reguł
Algorytmy pozyskiwania reguł ró
ż
ni
ą
si
ę
od algorytmów tworzenia drzew
decyzyjnych, st
ą
d te
ż
wiedza pozyskana w postaci reguł i drzew decyzyjnych mo
ż
e
si
ę
w niektórych przypadkach ró
ż
ni
ć
.
Gliwice 2013-02-05
- 5/8 -
Reguły, podobnie jak drzewa decyzyjne, mo
ż
na pozyskiwa
ć
z danych stosuj
ą
c ró
ż
ne
algorytmy. W systemie Orange zaimplementowany jest algorytm CN2 [1]. Przykład
zastosowania algorytmu pozyskiwania reguł i ich prezentacji pokazano na Rys. 3.
Rys. 3. Przykład pozyskiwania wiedzy w postaci reguł
5. Ocena wiedzy
Istotnym zagadnieniem w przypadku pozyskiwania wiedzy jest jej ocena. Maj
ą
c do
czynienia z wiedz
ą
zapisan
ą
w postaci klasyfikatorów, mo
ż
emy ocenia
ć
tzw. sprawno
ść
klasyfikacji. Im jest ona wy
ż
sza, tym pozyskana wiedza jest „lepsza”.
Sprawno
ść
klasyfikatora wyznaczana jest na podstawie oceny poprawno
ś
ci działania
(klasyfikacji) utworzonego klasyfikatora. Proces ten nosi nazw
ę
testowania
klasyfikatora. Klasyfikator ma za zadanie sklasyfikowa
ć
przypadki, które nie były
uwzgl
ę
dniane w procesie jego pozyskiwania, a których poprawna klasyfikacja jest
znana. Wówczas wyznaczaj
ą
c iloraz liczby poprawnie sklasyfikowanych przypadków
do liczby wszystkich przypadków testowych uzyskuje si
ę
sprawno
ść
klasyfikacji.
Przyjmijmy nast
ę
puj
ą
ce oznaczenia:
•
cały zbiór dost
ę
pnych danych nazywamy zbiorem danych ucz
ą
cych –
U,
•
zbiór danych zastosowanych do tworzenia klasyfikatora nazywamy zbiorem
danych trenuj
ą
cych –
L,
•
zbiór danych u
ż
ytych do testowania okre
ś
lamy mianem danych testowych –
T
.
W praktyce stosowanych jest kilka sposobów testowania klasyfikatorów:
1. losowy podział zbioru
U
na dwa rozł
ą
czne podzbiory
T
∪
L
(ang. random
sampling), przy czym wielko
ść
zbiorów okre
ś
lana jest procentowo np. 70%
przypadków w zbiorze
L
, pozostałe w zbiorze
T
,
2. podział zbioru
U
na
k
podzbiorów
U={U
1
, U
2
,…, U
k
)
, wówczas
L=U\U
i
, T=U
i
∀
i=(1,…,k)
(ang. cross-validation); najcz
ęś
ciej, operacj
ę
tworzenia klasyfikatora i jego testowania dokonywana jest
k
-krotnie,
a uzyskane wyniki s
ą
u
ś
redniane,
3. ze zbioru
U
usuwany jest jeden przypadek
u
i
(
L=U\ u
i
), tworzony jest
klasyfikator, a zbiór testowy jest zbiorem jednoelementowym
L={u
i
}
(ang. leave-one-out); operacje powtarzana jest
n
-krotnie, gdzie
n=|U|
okre
ś
la
liczno
ść
zbioru
U
.
Gliwice 2013-02-05
- 6/8 -
Do oceny pozyskanej wiedzy, w systemie Orange przewidziany jest widget Test
Lerners (por. Rys. 4). Uzyskane u
ś
rednione wyniki mo
ż
na przedstawi
ć
np. w postaci
tzw. macierzy pomyłek (ang. confusion matrix) – Rys. 5, w której prezentowane s
ą
liczby przypadków poprawnie i bł
ę
dnie sklasyfikowanych, z podziałem na
poszczególne klasy.
Rys. 4. Schemat pozyskiwania wiedzy w postaci reguł i drzew decyzyjnych oraz
sposób prezentacji wyników jej oceny
Rys. 5. Macierz pomyłek
Szczegółowe
wyniki
dotycz
ą
ce
np.
dokładno
ś
ci
klasyfikacji
(sprawno
ś
ci
klasyfikatora) mo
ż
na znale
źć
w informacjach podawanych przez widget Test lerners
(por. Rys. 6).
Gliwice 2013-02-05
- 7/8 -
Rys. 6. Wyniki podawane przez widget Test lerners
Na jednym schemacie mo
ż
na zastosowa
ć
kilka metod pozyskiwania wiedzy i jej
oceny, co pokazano na Rys. 7.
Rys. 7. Przykład zastosowania kilku metod pozyskiwania wiedzy jednocze
ś
nie
Dane stosowane w procesie pozyskiwania wiedzy mo
ż
emy wst
ę
pnie przetworzy
ć
,
m.in. podda
ć
procesowi dyskretyzacji (zamieni
ć
dane ci
ą
głe na dane dyskretne) i/lub
wybra
ć
cechy, które b
ę
d
ą
uwzgl
ę
dniane w procesie pozyskiwania wiedzy. Przykłady
tego typu działa
ń
w systemie Orange przedstawia Rys. 8.
Gliwice 2013-02-05
- 8/8 -
Rys. 8. Proces pozyskiwania wiedzy uwzgl
ę
dniaj
ą
cy dyskretyzacj
ę
warto
ś
ci i
selekcj
ę
cech
6. Zadania do wykonania
1. Opracowa
ć
schemat pozyskiwania wiedzy w postaci reguł.
2. Wczyta
ć
wskazane przez prowadz
ą
cego dane.
3. Pozyska
ć
wiedz
ę
w postaci reguł klasyfikacji.
4. Uzupełni
ć
schemat tak, by mo
ż
liwe było testowanie klasyfikatora metod
ą
cross-
validation dla
k=10
.
5. Przetestowa
ć
klasyfikator i przeanalizowa
ć
uzyskane wyniki.
6. Uzupełni
ć
schemat w sposób pozwalaj
ą
cy na pozyskiwanie wiedzy w postaci
drzew decyzyjnych stosuj
ą
c dwa ró
ż
ne algorytmy generowania drzew.
7. Wygenerowa
ć
drzewa decyzyjne i porówna
ć
je ze sob
ą
.
8. Przetestowa
ć
pozyskane klasyfikatory i przeanalizowa
ć
uzyskane wyniki.
9. Przeanalizowa
ć
wyniki klasyfikacji dla ró
ż
nych metod testowania klasyfikatorów.
10. Dokona
ć
dyskretyzacji danych.
11. Pozyska
ć
wiedz
ę
dla danych dyskretnych i oceni
ć
jako
ść
pozyskanej wiedzy.
12. Ograniczy
ć
liczb
ę
uwzgl
ę
dnianych cech.
13. Pozyska
ć
wiedz
ę
dla ograniczonych danych i oceni
ć
jako
ść
pozyskanej wiedzy.
14. Przeanalizowa
ć
uzyskane wyniki.
15. Wskaza
ć
metod
ę
dzi
ę
ki której pozyskano „najlepsz
ą
” wiedz
ę
.
16. Opracowa
ć
sprawozdanie obejmuj
ą
ce wyniki i wnioski wynikaj
ą
ce ze wszystkich
opisanych wy
ż
ej punktów.
Literatura
[1] Clark P., Niblett T. The CN2 induction algorithm. Machine Learning, 3(4): 261–
283, 1989.
[2] Quinlan, J. R. C4.5: Programs for Machine Learning. Morgan Kaufmann
Publishers, 1993.