Gliwice 2013-02-05

- 1/8 -

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

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.