5.7
Metody založené na analogii
Případové usuzování (Case-Based Reasoning, CBR), pravidlo nejbližšího souseda (nearest neighbour rule), učení založené na instancích (Instance-Based Learning, IBL), líné učení (lazy learning), pamětové učení (Memory-Based Learning), shlukování (clustering) – to všechno jsou metody založené principu analogie: v neznámé situaci použij to řešení, které se osvědčilo v situaci podobné. Znalosti jsou tentokrát reprezentovány v podobě databáze již vyřešených problémů. Ve fázi učení se tedy neprovádí generalizace z příkladů (proto název líné učení). Při usuzování se pak v této databázi hledá nejpodobnější případ, dříve použité řešení někdy musí být adaptováno na novou situaci. Metody založené na analogii lze použít pro deskriptivní úlohy (segmentaci a shlukování) i pro úlohy klasifikační. Podobně jako na jiných místech knihy i zde bude větší důraz kladen na klasifikaci.
5.7.1
Podobnost mezi příklady
Klíčovým pojmem je koncept podobnosti, resp. vzdálenosti, Jak podobnost tak vzdálenost se vyjadřuje pomocí metriky. Metrika je definována jako funkce d: X × X → R taková, že 1. ∀x1,x2 ∈ X; d(x1,x2) ≥ 0 2. d(x1,x2) = 0 ⇔ x1 = x2 3. d(x1,x2) = d(x2,x1) 4. ∀x1,x2,x3 ∈ X; d(x1,x2) + d(x2,x3) ≥ d(x1,x3) Nejpoužívanější metriky již známe z kapitoly o statistických metodách. Jsou to vzdálenost m
∑δE(x1j,x2j)
dE(x1,x2) =
eukleidovská
, kde δE(x1j,x2j) = (x1j - x2j)2
j=1
a Hammingova vzdálenost (v komunitě strojového učení nazývaná Manhattan, nebo city-block)1 m
dH(x1,x2) =
∑ δH(x1j,x2j) ,
kde δH(x1j,x2j) = | x1j - x2j |
j=1
K nim se (pro kategoriální atributy) řadí ještě metrika překrytí („overlap“), počítající počet rozdílů v hodnotách stejných atributů m
dO(x1,x2) =
∑ δO(x1j,x2j) , j=1
⎧0 pro x 1j = x 2j kde δO(x1j,x2j) = ⎨ ⎩ 1 pro x 1j ≠ x 2j
1
V případě, že hodnoty atributů jsou pouze 0 a 1, počítá Hammingova vzdálenost (stejně jako metrika překrytí) počet „neshod“ v hodnotách vzájemně si odpovídajících atributů dvou příkladů. Takto je tato metrika používána například v teorii informace pro měření vzdálenosti dvou kódových slov reprezentovaných bitovými řetězci.
1
Podobnost pak můžeme spočítat jako 1/d(x1,x2) nebo jako 1 - d(x1,x2). První varianta se používá pro d(x1,x2) ∈ R (nenormalizovaná vzdálenost), druhá varianta se používá pro d(x1,x2) ∈ [0,1] (vzdálenost je normalizována např. tak, že je vydělena vzdáleností mezi dvěma krajními hodnotami definičního oboru).
Uvedené metriky trpí některými nedostatky. Liu [Liu, 1996] uvádí tyto dva problémy: 1. na určení podobnosti dvou příkladů se všechny atributy podílejí stejně; to může vést k přeučení systému, 2. měření podobnosti mezi dvěma hodnotami kategoriálního atributu jako shoda/neshoda hodnot (případ metriky překrytí) nedokáže často zachytit složitost a jemné nuance problému.
Řešení prvního problému spočívá ve vážení jednotlivých atributů. Při porovnávání hodnot téhož atributu se tedy pracuje s hodnotou δ’(x1i,x2i) = wi δ(x1i,x2i). Váhy atributů lze získat od experta, na základě analýzy celých trénovacích dat (např. na základě podmíněné pravděpodobnosti nebo entropie; obě možnosti vyjadřují, jak dobře se atribut hodí pro klasifikaci), nebo inkrementálně na základě výsledku klasifikace pro jeden přiklad (váhy „správně“ fungujících atributů se posilují, váhy „špatně“ fungujících atributů se oslabí podobně jako u neuronových sítí). Podrobněji o této problematice viz [Wettschereck, Aha, 1995]. V extremním případě (wi = 0) lze pomocí vážení provádět selekci atributů. Pro řešení druhého problému se nabízejí složitější metriky. Populární je zejména tzv. Value Difference Metric (VDM) [Stanfill, Waltz, 1986]. Tato metrika bere do úvahy celkovou podobnost příkladů patřících do různých tříd v celé trénovací množině. Nechť počty výskytu jednotlivých hodnot v1, v2,… vR atributu A pro příklady patřící do tříd C(v1), …., C(vS) ukazuje kontingenční tabulka Tab. 1.
C(v1)
C(v2)
……….
C(vS)
∑
A(v1)
a11
a12
……….
a1S
r1
A(v2)
a21
a22
……….
a2S
r2
:
:
:
:
:
:
:
:
:
:
A(vR)
aR1
aR2
……….
aRS
rR
∑
s1
s2
……….
sS
n
Tab. 1 Kontingenční tabulka
Tedy akl je četnost (frekvence) kombinace A(vk) ∧ C(vl ), S
rk = ∑akl , l=1
2
R
sl = ∑akl , k=1
a
R
S
n = ∑ ∑ akl . k=1 l=1
Je-li x1j = va a x2j = vb , potom vzdálenost mezi těmito dvěma hodnotami je 2 S
δ( x1j , x2j) =
∑| r − r | . aal
abl
a
b
l=1
Vzdálenost mezi dvěma příklady x1 a x2 přitom zůstává m
d(x1,x2) =
∑ δ(x1j,x2j) . j=1
Modifikace této metriky, Modified Value Difference Metric (MVDM) bere do úvahy i váhy příkladů x1 a x2 [Cost, Salzberg, 1993]: m
d(x1,x2) = wx1wx2 ∑ δ(x1j,x2j) . j=1
Je-li x1 nový příklad, který se má klasifikovat a x2 příklad v databázi, bude wx1 = 1 wx2 =
počet použití příkladu x2 pro klasifikaci počet správných použití příkladu x2 .
Váha příkladu x2 tedy bere do úvahy úspěšnost použití tohoto příkladu při klasifikaci.
Jinou možností jak měřit vzdálenost mezi hodnotami kategoriálního atributu je využít hierarchického uspořádání hodnot atributu (pokud takováto hierarchie existuje). Vzdálenost mezi dvěma hodnotami bude v tomto případě dána podílem maxima z hloubky obou hodnot-uzlů v minimálním společném podstromu a hloubky celé hierarchie. Tedy např. pro hierarchii hodnot atributu bydlení uvedenou na
Obr. 1 bude δ(vlastní_dům,vlastní_byt)= max(1,1)/2 = 0.5 (kořen minimálního společného podstromu je uzel vlastní) δ(vlastní_byt,družstevní) = max(2,1)/2 = 1 (kořen minimálního společného podstromu je uzel any).
any
vlastní
vlastní dům
družstevní
vlastní byt
nájemní
Nájemní byt státní
Nájemní byt s majitelem
Obr. 1 Hierarchie hodnot atributu “bydlení” 2
Připomeňme si, že aal/ra je odhad podmíněné pravděpodobnosti P(C(vl)|A(va)).
3
5.7.2
Podobnost mezi časovými řadami a sekvencemi
Zajímavým dílčím problémem je otázka, jak měřit podobnost mezi časovými řadami nebo sekvencemi [Gunopulos, Das, 2000]. U dat typu spotřeba elektrické energie, pohyb cen akcií, transakce na účtu klienta, či výskyt poruch v telekomunikační síti, lze využít toho, že nepracujeme s hodnotami různých atributů, ale s jediným atributem, jehož hodnoty sledujeme v průběhu určitého časového období. Nejjednodušší způsob, jak měřit podobnost mezi dvěma časovými řadami téže délky je standardním způsobem použít eukleidovskou metriku. Tento způsob je ovšem velmi citlivý na drobné posuvy v časové ose3. Proto se pro časové řady používá metoda dynamic time warping provádějící dynamickou deformaci časové osy [Berndt, Clifford, 1996]4. Místo abychom porovnávali sobě odpovídající vzorky dvou řad, hledáme vzorky, které si jsou nejblíže. Pro uvažované dvě řady X = x1, x2, …, xi ,…, xlx Y = y1, y2, …, yj ,…, yly hledáme tzv. deformační cestu (warping path) max(lx,ly) ≤ K < lx + ly + 1
W = w1,w2, …, wk ,… , wK ,
která specifikuje, které vzorky obou řad budeme porovnávat. Nějaká hodnota wk v této cestě je definována jako wk = (i,j)k, tedy jako volba hodnot xi a yj. Přitom musí platit [Keogh, Pazzani, 1999]: •
hraniční podmínky w1 = (1,1) a wK = (lx, ly),
•
spojitost: je-li wk = (ik,jk), potom wk-1 = (ik-1,jk-1), kde ik-ik-1 ≤ 1 a jk-jk-1 ≤ 1,
•
monotonicita: je-li wk = (ik,jk), potom wk-1 = (ik-1,jk-1), kde ik-ik-1 ≥ 0 a jk-jk-1 ≥ 0 .
Cílem je nalézt5 takovou deformační cestu, která bude minimalizovat vzdálenost mezi uvažovanými řadami X a Y počítanou jako ∑kδE(xik,yjk ) resp. ∑kδH(xik,yjk ). Obr. 3 ukazuje příklad cesty (1,1) (2,2) (2,3) (3,3) (4,4) …, která přiřadí třetí hodnotu řady Y ke druhé hodnotě řady X.
5
4
Y3
2
1 1
2
3
4
5
X
Obr. 3 Příklad deformační cesty
3
Připomeňme, že „klasické“ použití této metriky předpokládá, že každý příklad je popsán hodnotami m různých atributů, zde máme jeden atribut, s hodnotami získanými v m časových okamžicích; tyto hodnoty tedy nejsou vzájemně nezávislé.
4
Tato metoda byla původně navržena pro rozpoznávání řeči [Sakoe, Chiba, 1978].
5
Tato úloha se řeší metodami dynamického programování.
4
Jinou možností6 je transformovat časovou řadu na sekvenci elementárních úseků (např. vzrůst, pokles, beze změny, nebo hrot, sedlo) a pak použít některou z metod pro porovnávání sekvencí. Tyto sekvence mohou mít v zásadě dvojí podobu: •
sekvence dvojic (elementární úsek, časový okamžik)
•
sekvence elementárních úseků.
Vdálenost mezi dvěma sekvencemi můžeme například měřit na základě náročnosti transformace jedné sekvence na druhou. Pro první typ sekvencí definují Mannila a Rokainen ([Manilla, Rokainen, 1997]) tyto transformační operace: •
operace Ins(e,t) vloží událost e do časového okamžiku t
•
operace Del(e,t) zruší událost e z časového okamžiku t
•
operace Move(e,t,t’) přesune událost e z časového okamžiku t do časového okamžiku t’.
Každá z uvedených operací op(e,t) je spojena s určitými náklady c(op(e,t)). Vzdálenost mezi dvěma sekvencemi událostí je tedy dána cenou za transformaci jedné sekvence na sekvenci druhou. Tak například ([Manilla, Rokainen, 1997]) vzdálenost mezi sekvencemi X = (D,8) (D,12) (A,15) (B,17) (A,20) Y = (D,4) (D,8) (C,15) (B,17) (A,18) (C,20) je c(X → Y) = c(Move(D,8,4)) + c(Move(D,12,8)) + c(Ins(C,15)) + c(Del(A,15)) + c(Move(A,20,18)) + c(Ins(C,20)). V případě, že sekvence je tvořena pouze elementárními úseky, (a lze ji tedy chápat jako posloupnost symbolů) se aspekt času zcela stírá. Operace používané pro transformaci jedné sekvence (řetězce) na druhou jsou pak odstranění symbolu, náhrada symbolu a vložení symbolu. Pokud jsou ceny transformačních operací jednotkové, je vzdálenost mezi sekvencemi dána počtem provedených operací (tzv. Levensteinova vzdálenost)7. Kdybychom ve výše uvedeném příkladu sekvencí X a Y ignorovali čas, pak transformace X na Y je tvořena kroky nahraď(A,C)vlož(C) a tedy Levensteinova vzdálenost je rovna 2.
Podobnost mezi sekvencemi lze rovněž definovat jako délku největšího společného úseku (longest common subsequence LCS) [Gunopulos, Das, 2000]. Přitom se připouští, že v tomto úseku se mohou vyskytovat jiné události. Pro výše uvedené sekvence X a Y (opět bez uvažování časových okamžiků) je LCS(X, Y) = D D B A A tedy podobnost mezi X a Y je 4 (pokud uvažujeme absolutní délku |LCS(X, Y)| ), případně 4/5 |LCS(X, Y) | (pokud uvažujeme relativní délku ). min(lx,ly)
6
7
Existují samozřejmě další metody pro analýzu resp. transformaci časových řad, vyhlazování časové řady pomocí klouzavého průměru, autoregresní modely nebo Fourierova transformace. Tento způsob se používá například pro porovnávání dvou řetězců DNA.
5
5.7.3
Učení založené na instancích
Jedním z pionýrů v oblasti učení založeném na instancích (IBL) je David Aha. Vyjděme tedy z jeho popisu tohoto typu učení [Aha a kol., 1991]. Předpokladem použití metod učení založených na instancích je existence: •
funkce pro měření podobnosti dvou instancí,
•
funkce pro volbu instancí pro uložení do databáze,
•
funkce pro klasifikování nových příkladů.
Funkcemi pro měření podobnosti resp. vzdálenosti (metrikami) jsme se podrobněji zabývali v předcházejícím odstavci. Nejpoužívanější funkci pro klasifikování nových případů, pravidlo knejbližších sousedů (k-nearest neighbour rule) popisuje odstavec následující. Zde se tedy zaměříme na způsob volby instancí které si systém „zapamatuje“, tedy uloží do databáze. Aha uvádí následující možnosti postupně implementované v systémech IBx: •
IB1 – systém ukládá každý příklad z trénovacích dat; tato nejjednodušší varianta pracuje dobře i pro příklady zatížené šumem,
•
IB2 – systém se nejprve pokusí nový příklad klasifikovat. Pouze chybně zařazené příklady jsou uloženy do databáze. U této varianty dochází k významné redukci počtu ukládaných příkladů, dochází ale k problémům v případě šumu,
•
IB3 – systém používá složitější kritérium pro volbu příkladů pro uložení založené na souhrnné správnosti klasifikace. Pro každý příklad v databázi se sleduje, kolikrát se podílel na správné klasifikaci a kolikrát na nesprávné. Systém pak testuje, které příklady jsou dobré klasifikátory (ty ponechá) a které jsou špatné (ty odstraní). Tento postup umožňuje zachovat nízké nároky na paměť systému IB2 při růstu spolehlivosti klasifikace pro zašuměná data.
S otázkou ukládání příkladů do databáze úzce souvisí otázka vyhledávání. Sekvenční procházení všech uložených příkladů je (pro rozsáhlá data) časově značně náročné. Jsou-li však k dispozici efektivní indexovací techniky, lze redukovat dobu potřebnou na hledání v této databázi. Příkladem takovéto techniky je použití stromů. V případě k-d stromů jsou nelistové uzly tvořeny atributy, v listech jsou pak seznamy podobných příkladů ([Friedman a kol., 1977]). Tyto stromy se tedy používají pro uchovávání příkladů pro algoritmus k-nejbližších sousedů. K-d stromy byly původně navrženy jako binární stromy pro indexování příkladů popsaných pouze numerickými atributy8 , později byl algortimus pro vytváření k-d stromů rozšířen i pro práci s kategoriálními atributy. V případě algoritmu IGTree (IG zde znamená informační zisk [Daelemans a kol., 1996]) se vytváří strom v jehož listech jsou informace o třídě; lze tedy tento strom použít přímo pro klasifikaci. Na rozdíl od algoritmů pro indukci rozhodovacích stromů se ale neprovádí žádná generalizace. Druhým rozdílem je to, že pořadí atributů pro větvení se pevně stanoví před začátkem tvorby stromu. Atributy jsou uspořádány sestupně podle informačního zisku 9 pro celá trénovací data. V tomto pořadí se pak vybírají pro větveni; maximální hloubka stromu je tedy dána počtem atributů a pro uzly ve stejné 8
Při větvení se tedy provádí binarizace.
9
6
Tedy podle kritéria, které navrhl Quinlan pro volbu atributu v případě indukce rozhodovacích stromů (viz příslušná kapitola).
hloubce se pro větvení použije tentýž atribut. Ke každému uzlu je navíc přířazena majoritní (default) třída. Při tvorbě stromu se rovněž provádí komprese dat. Příklady nejsou uloženy v plné podobě: ukládají se pouze hodnoty těch atributů, které umožní klasifikovat příklady v daném uzlu. Odlišnosti mezi k-d stromy, IGTree a rozhodovacími stromy ilustruje jednoduchý příklad převzatý z [Daelemans a kol., 1996] (Obr. 4). Quinlanův algoritmus C4.5 zde zastupuje algoritmy TDIDT. Pro uvedená data je informační zisk (pro celá data) atributu počet_otvorů rovný 1.1, informační zisk atributu tvar rovný 0.9 a informační zisk atributu velikost rovný 0.75.
Obr. 4 Rozdíl mezi rozhodovacím stromem (C4.5), k-d stromem a IGTree
7
5.7.4
Nejbližší soused
Nejblíže ke statistickému pojetí má metoda nejbližšího souseda, resp. K-nejbližších sousedů (Knearest neighbour rule). K dříve uvedeným základním principům využití analogie •
ve fázi učení se neprovádí generalizace
•
klasifikace se provádí na základě podobnosti
se zde řadí ještě třetí princip • příklady jsou chápány jako body v n-rozměrném prostoru atributů.
Základní podobu algoritmu uvádí Obr. 5 ([Mitchell, 1997]). Ve fázi učení si systém zapamatuje všechny příklady [xk, yk] z trénovací množiny. Ve fázi klasifikace se pro nový příklad x nalezne (za použití zvolené metriky) K nejbližších příkladů, které pak „hlasují“ o zařazení příkladu x do třídy. Algoritmus k-NN Učení 1. Pro každý příklad [xi, yi] zařaď [xi, yi] do báze příkladů Klasifikace 1. Pro nový příklad x 1.1. Najdi x1, x2, … xK K nejbližších příkladů z báze příkladů 1.2. Přiřaď y = yj ⇔
K
K
∑ δ (y j , y k ) = max ∑ δ (y i , y k ) , i
k=1
k=1
kde δ(yi,yk) = 1 pro yi =yk, jinak δ(yi,yk) = 0 Obr. 5 Algoritmus K-nejbližších sousedů
Uvedený algoritmus předpokládá, že cílový atribut je kategoriální, jinými slovy, klasifikujeme příklady do konečného počtu tříd. V případě, že cílový atribut je numerický, počítáme místo nejčastější hodnoty cílového atributu hodnotu průměrnou: 1 K ŷ = K ∑yk . k=1
V obou případech (diskretní třídy i třídy spojité) má každý z K příkladů „rovný hlas“. To je sice demokratické, ale někdy neefektivní. Proto se používá vážené hlasování (resp. vážený průměr). Jeden příklad vážení příkladů jsme již uvedli v předcházející podkapitole u MVDM, jinou možností je volit váhu příkladu xi v bázi jako 1 wi = d(x,x )2 i
kde d(xx,xi) je vzdálenost obou příkladů.
8
Pokud budeme uvedeným algoritmem na základě trénovacích dat z našeho příkladu o úvěrech klasifikovat nového klienta s charakteristikami Přijem = 15000 Konto = 32000 Pak při použití eukleidovské vzdálenosti a pro parametr K=1 bude závěr klasifikace úvěr(ano), protože posuzovaný klient má nejblíže ke klientovi k5 (Tab. 2).
klient
příjem
k1 k2 k3 k4 k5 k6 k7 k8 k9 k10 k11 k12
3000 10000 17000 5000 15000 20000 2000 5000 10000 20000 10000 17000
konto 15000 15000 15000 30000 30000 50000 60000 90000 90000 90000 100000 100000
úvěr ne ne ano ne ano ano ne ano ano ano ano ano
vzdálenost příkladu 20808.65 17720.05 17117.24 10198.04 2000.00 18681.54 30870.70 58855.76 58215.12 58215.12 68183.58 68029.41
Tab. 2 Klasifikace nového příkladu podle jednoho nejbližšího souseda
V případě velkého množství příkladů, což je situace typická při dobývání znalostí z databází, ale nelze uvažovat o uložení všech příkladů. Neobejdeme se tedy ve fázi učení bez generalizace. Jednotlivé třídy pak budou reprezentovány centroidy, tak, jak to bylo zmíněno v kapitole o statistických metodách. V nejjednodušším případě budou hodnoty atributů pro centroid reprezentující určitou třídu dán průměrnými hodnotami atributů pro příklady této třídy. Tímto způsobem získáme pro naše data dva centroidy: C(ano): příjem = 14250, konto = 70625 C(ne): příjem = 5000, konto = 30000 Pro eukleidovskou vzdálenost se při klasifikaci trénovacích dat podle těchto centroidů dopustíme tří chyb (v Tab. 3 vyznačeno tučně). klient k1 k2 k3 k4 k5 k6 k7 k8 k9 k10 k11 k12
příjem 3000 10000 17000 5000 15000 20000 2000 5000 10000 20000 10000 17000
konto 15000 15000 15000 30000 30000 50000 60000 90000 90000 90000 100000 100000
úvěr ne ne ano ne ano ano ne ano ano ano ano ano
vzdálenost vzdálenost výsledek od C(ano) od C(ne) klasifikace 56751.24 15132.75 ne 55787.12 15811.39 ne 55692.94 19209.37 ne 41664.77 0.00 ne 40631.92 10000.00 ne 21411.52 25000.00 ano 16215.83 30149.63 ano 21469.82 60000.00 ano 19835.65 60207.97 ano 20210.22 61846.58 ano 29680.85 70178.34 ano 29503.44 71021.12 ano
Tab. 3 Klasifikace trénovacích dat podle centroidů – průměrů
9
To ale neznamená, že neexistují centroidy použitelné pro bezchybnou klasifikaci našich dat. Vzhledem k tomu, že data jsou lineárně separabilní (viz kapitola o neuronových sítích), mohou jako centroidy posloužit každé dva body v prostou atributů, které budou osově souměrné podle rozdělující přímky10. Tedy například C(ano): příjem = 15000, konto = 32000 C(ne): příjem = 5000, konto = 30000 Polohu těchto centroidů v prostoru atributů ilustruje Obr. 6. Výsledky klasifikace pomocí těchto centroidů pak ukazuje Tab. 4.
Obr. 6 Poloha centroidů
klient k1 k2 k3 k4 k5 k6 k7 k8 k9 k10 k11 k12
příjem 3000 10000 17000 5000 15000 20000 2000 5000 10000 20000 10000 17000
konto 15000 15000 15000 30000 30000 50000 60000 90000 90000 90000 100000 100000
úvěr ne ne ano ne ano ano ne ano ano ano ano ano
vzdálenost vzdálenost výsledek od C(ano) od C(ne) klasifikace 20808.65 15132.75 ne 17720.05 15811.39 ne 17117.24 19209.37 ano 10198.04 0.00 ne 2000.00 10000.00 ano 18681.54 25000.00 ano 30870.70 30149.63 ne 58855.76 60000.00 ano 58215.12 60207.97 ano 58215.12 61846.58 ano 68183.58 70178.34 ano 68029.41 71021.12 ano
Tab. 4 Klasifikace trénovacích dat podle centroidů – osově souměrných bodů 10
Reprezentace dvou lineárně separabilních tříd pomocí jedné lineární diskriminační funkce je tedy ekvivalentní reprezentaci pomocí dvou centroidů symetrických podle této funkce. V případě tříd, které nejsou lineárně separabilní je třeba jednu třídu reprezentovat více centroidy (viz kapitola o statistice).
10
5.7.5
Případové usuzování
To, čím se případové usuzování (Case-Based Reasoning, CBR) odlišuje od metody nejbližšího souseda a učení na základě instancí je skutečnost, že jednotlivé příklady již nelze chápat jako body v prostoru atributů. Popis „případů“ má charakter složitých struktur, často rámců, tak jak to ukazuje příklad na Obr. 7 (převzato z [Watson, Marir, 1994]). Takto složitá reprezentace vyžaduje složitější metody ukládání (indexování) i měření podobnosti.
Základní schéma případového usuzování lze charakterizovat jako 4R [Aamodt, Plaza, 1994]: •
retrieve – najdi nejpodobnější případy,
•
reuse – použij tyto případy pro řešení aktuálního problému,
•
revise – v případě nutnosti reviduj navržené řešení,
•
retain – uchovej nové řešení jako součást nového případu.
BEGIN CASE CASE11 TITLE Zásobník inkoustu je poškozen, způsobuje černé skvrny. DESCRIPTION Malé kulaté černé skvrny se objevují na přední nebo zadní straně papíru. Občas se objeví velké nesouvislé skvrny. QUESTIONS Máte problémy s kvalitou tisku? ANSWER: ano SCORING: (-) Jaká je kvalita tisku? ANSWER: černé skvrny SCORING: (default) Pomohlo vyčištění tiskárny? ANSWER: ne SCORING: (default) ACTIONS Zkontrolujte zásobník a vyměnte ho, je-li v něm málo náplně nebo je-li poškozen BROWSE TEXT CREATION 29/7/91 14:19:22 LAST_UPDATE 29/7/91 14:19:22 LAST_USED 29/7/91 14:19:22 STATUS ACTIVE END CASE Obr. 7 Reprezentace případu v systému CBR-Express
11
Případové usuzování (Case-Based Reasoning) se objevuje jako alternativa k usuzování založenému na pravidlech (Rule-Based Reasoning) počátkem 80. let. Systémy případového usuzování jsou založeny na představě, že expert se v neznámé situaci rozhoduje na základě podobnosti s již dříve řešenými (a vyřešenými) případy a nikoliv na základě soustavy pravidel. Tento postup odpovídá např. anglosaskému pojetí práva založenému na precedentech 11. CBR systémy soutěží o přízeň uživatelů s expertními a znalostními systémy. Vzhledem k tomu, že znalosti jsou tentokráte reprezentovány jako soubor typických příkladů, je vytvoření CBR aplikace podstatně rychlejší než tvorba „klasického“ znalostního systému. Problém získávání znalostí se zde transformuje na problém „získávání případů“. Klíčovou otázkou je zde volba vhodných příkladů, které dostatečně dobře pokrývají zvolenou oblast expertízy. To se dosti obtížně určuje jednorázově; tvorba (plnění) systému je opět iterativní proces. Některé systémy proto mají schopnost „doučovat se“. Jestliže konzultovaná situace neodpovídá žádnému případu z databáze, vyžádá se závěr od experta a vyřešený případ se zařadí do databáze jako nová znalost.
CBR systémy mohou být budovány na základě dat (data driven) nebo na základě zkušeností experta (experience driven). V prvním případě pozorujeme zřejmou vazbu na dobývání znalostí (výše uvedené metody IBL). Ovšem i ve druhém případě, kdy se ve velké míře využívají znalosti experta, lze těžit z metod dobývání znalostí. Někteří autoři uvádějí, že propojení metod dobývání znalostí a případového usuzování v sekvenci databáze → dobývání znalostí → případové usuzování → uživatel umožní překlenout propast mezi databázemi obsahujícími množství málo srozumitelných dat a koncovým uživatelem. Případové usuzování v tomto pojetí umožní v „databázi zkušeností“ nalézt data relevantní pro danou rozhodovací situaci, metody dobývání znalostí pak přispívají k naplňování této databáze ([Aamodt a kol., 1998]).
5.7.6
Systémy IBL
Algoritmus K-NN můžeme nalézt mimo jiné v systémech Clementine a Weka. Systém TiMBL z University v Tilburgu implementuje řadu zde popisovaných IBL technik. Používá např. vážení atributů na základě informačního zisku a MVDM metriku pro porovnávání dvou kategoriálních hodnot. Systém uchovává reprezentaci trénovacích dat v paměti a klasifikuje nové příklady na základě extrapolace z nejpodobnějších případů. Proces klasifikace je optimalizován s využitím indexování pomocí IGTree. Systém lze nalézt na http://ilk.kub.nl/software.html. Jiným příkladem je PEBLS, systém pro práci s kategoriálními atributy založený na pravidle nejbližšího souseda s využitím metriky MVDM [Cost, Salzberg, 1993]. Systém je volně dostupný na ftp://condor.cs.jhu.edu/pub/pebls. K aplikacím tohoto systému patří predikce struktury proteinů a identifikace vybraných sekvencí v DNA.
11
Aplikace v právnické oblasti ostatně patří mezi nejrozšířenější příklady použití systémů CBR.
12
Literatura: [Aamodt, Plaza, 1994] Aamodt,A. – Plaza,E.: Case-based reasoning: foundational issues, methodological variations and system approaches. AI Communications, 7(1), 1994, 39-59. [Aamodt a kol., 1998] Aamodt,A. – Sandtorv,H.A. – Winnem,O.M.: Combining case based reasoning and data mining – a way of revealing and reusing RAMS experience. In: Proc. Safety and Reliability ESREL’98, 1998, 1345-1351. [Aha a kol., 1991] Aha,D.W. - Kibler,D., - Albert, M. K.: Instance-based learning algorithms. Machine Learning, 6, 1991, 37-66. [Berndt, Clifford, 1996] Berndt,D. – Clifford,J.: Finding Patterns in Time Series: A Dynamic Programming Approach. In: Fayyad et al. Advances in Knowledge Discovery and Data Mining. AAAI Press/MIT Press, 1996, 229-248. [Cost, Salzberg, 1993] Cost,S. - Salzberg,S.: A weighted nearest neighbor algorithm for learning with symbolic features, Machine Learning, 10:1, (1993), 57-78. [Daelemans a kol., 1996] Daelemans,W. - van den Bosch,A. – Weijters,T.: IGTree: Using trees for compression and classification in lazy learning algorithms. In: D. Aha (ed.) Artificial Intelligence Review, special issue on Lazy Learning, 1996. [Friedman a kol., 1977] Friedman,J. – Bentley,J. – Finkel,A.R.: An algorithm for finding best matches in logaritmic expected time. ACM Transactions on Mathematical Software, 3(3), 1977. [Gunopulos, Das, 2000] Gunopulos,D. - Das,G.: Time Series Similarity Measures. KDD2000 tutorial, 2000. [Keogh, Pazzani, 1999] Keogh,E. - Pazzani,M.: Scaling up Dynamic Time Warping to Massive Datasets. In: (Zytkow, Rauch, eds.) Proc. European Konf. On Priniples and Practice of KDD PKDD’99, Springer, 1999, 111. [Kolodner, 1993] Kolodner, J.: Case-Based Reasoning. Morgan Kaufman, 1993. [Liu, 1996] Liu,W.Z.: An integrated approach for different attribute types in nearest neighbour classification. The Knowledge Engineering Review, Vol. 11:3, 1996, 245-252. [Manilla, Rokainen, 1997] Manilla,H. - Rokainen,P.: Similarity of Event Sequences. In: Proc. 4th Workshop on Temporal Representation and Reasoning TIME’97, 1997. [Mitchell, 1997] Mitchell,T.: Machine Learning. McGraw-Hill. 1997. ISBN 0-07-042807-7 [Sakoe, Chiba, 1990] Sakoe,H. - Chiba,S.: Dynamic Programming Algorithm Optimization For Spoken Word Recognition 1990. IEEE Trans. Acoustics, Speech and Signal Proc., Vol. ASSP-26, 1978, 43-49. [Stanfill, Waltz, 1986] Stanfill,C. – Waltz,D.: Towards memory-based reasoning. Communications of the ACM 29 (12), 1986, 1213-1228. [Watson, Marir, 1994] Watson,I. – Marir,F.: Case-based reasoning: An review. The Knowledge Engineering Review, Vol. 9:4, 1994, 327-354. [Wettschereck, Aha, 1995] Wettschereck,D. - Aha,D.: Weighting features. In Proc. 1st Int. Conf. on Case-Based Reasoning, Springer, 1995.
13
