Hledání vzorů v datech je základním úkolem dolování znalostí. Pokud rozdělíme všechny vzory na silné (strong), slabé (weak), a náhodné (random), tradiční technologie dolování znalostí jsou navrženy pouze na hledání silných vzorů, které se užívají na numerické objekty a obvykle jsou v souladu s očekáváním expertů. Zatímco silné vzory jsou užitečné při predikci, neočekávanost a rozpor vyjadřované slabými vzory jsou také velmi užitečné ačkoliv reprezentují relativně malý počet objektů. V tomto článku bude popsán problém hledání slabých vzorů (tzv. spolehlivých výjimek) v databázi. Je navržen jednoduchý a účinný přístup, který využívá analýzu odchylek k identifikování zajímavých výjimek a prozkoumání spolehlivých. Tato metoda umožňuje zpracovávat jek subjektivní tak i objektivní výjimky.
Dolování znalostí přitahuje v posledních letech hodně pozornost doktorů a výzkumníků. Kombinací technik z oblasti strojového učení, statistiky a databází slouží dolování znalostí k hledání vzorů v obrovských databázích a jejich využití pro zdokonalení rozhodování. Vzory se rozdělují do kategorií:
Tradiční techniky dolování znalostí jsou navrženy k vyhledávání pouze silných vzorů, které mají přesnost při predikci. To je proto, že normálně je snahou nalezení takového druhu vzorů, které pomáhají při předpovědích. Přesto v jistých úkolech dolování znalostí můžeme požadovat více , než predikci. Silné vzory jsou obvykle v souladu s očekáváním expertů, my však chceme najít v datech to, co ještě neznáme. Proto, v některých případech, nás zajímá více nalezení jiných vzorů, než silných. Obvykle jsou takové vzory (spolehlivé výjimky) neznámé, neočekávané a neslučitelné s představami uživatele. Proto jsou originální a potenciálně pro uživatele zajímavější než silné vzory. například, pokud řekneme, že “nějaká skupina nezaměstnaných poskytuje půjčky”, je to mnohem originálnější, než “nezaměstnaní neposkytují půjčky”.
Většina běžných technik dolování znalostí nemůže efektivně podporovat vyhledávání slabých vzorů. Vezměme například hledání asociací. Všechny asociační pravidla X==>Y s podporou p a spolehlivostí s jsou v databázi vyhledávány ve dvou fázích. V první nákladné fázi jsou v databázi vyhledávány všechny četné množiny položek, tzn. množiny položek , které nastanou dohromady v nejméně p% záznamů v databázi. Rychlý algoritmus Apriori byl vymyšlen na popsání podstaty tohoto problému. Odvozuje časté množiny k položek z častých množin k-1 položek. Apriori sestrojují množinu kandidátů Ck z množin položek Lk-1, spočítá počet výskytů každé množiny kandidátů množin položek a potom určí množinu Lk častých množin položek založenou na předem dané hodnotě podpory p.
S touto pěknou klesající vlastností (jestliže má množina k+1 položek podporu p, musí mít všechny podmnožiny k položek mít podporu p) může Apriori účinně vyloučit některé množiny k+1 položek, které nemají podporu p, a kontrolovat jen zbývající množiny k+1 položek. Např. dejme tomu Podpora({nezaměstnaný, nepůjčuje}) = 0,70 a Podpora({nezaměstnaný, půjčuje}) = 0,30. Nastavením hodnoty podpory na 0,5, je ponechána jen častější množina položek {nezaměstnaný, nepůjčuje}, druhá množina je vyloučena a nejsou prozkoumány další množiny položek jako ({nezaměstnaný, žena, nepůjčuje}). Tím je silně redukován prohledávaný prostor.
Po získání všech četných množin položek generuje druhá fáze asociační pravidla z každé množiny položek tak, že více než s% záznamů, které obsahují X, obsahují také Y. Vzhledem k tomu, že relativně nečetné množiny položek jako {nezaměstnaný, žena, půjčuje} jsou vypouštěny, některé spolehlivé výjimky jako “nezaměstnaný ^ žena ==> půjčuje” nemohou být objeveny, přestože ukazují vysokou důvěryhodnost.
Mohly by vás napadnout nějaké intuitivní způsoby, jak generovat tyto slabé vzory s využitím tradičních technik dolování dat. K nalezení výjimečných asociací můžeme například zavést dvě hodnoty podpory [p1, p2] jako hranice oproti dřívější jedné (tedy [p1, 100%]). V tomto případě sice neexistuje dolní ohraničující podmínka, ale může to vést k nesnesitelné náročnosti algoritmu.
Další přímá metoda je “vytvoř a odstraň” (generate-and-remove). Pro množinu dat D určí oblíbený indukční algoritmus, vygeneruje pravidla R nad D, odstraní D’ z D, které je pokryto korektně R, potom generuje pravidla R’ nad D – D’, opakuje tento proces dokud jsou k dispozici nějaká data. Můžeme si být jistí, že tato procedura může najít mnoho slabých vzorů. Je zřejmé, že tyto slabé vzory jsou nezávislé na silných vzorech. Hlavním problémem je, že slabých pravidel může být příliš mnoho. Přestože jich je mnoho, některé zajímavé výjimky mohou být přehlédnuty, protože jsou vynechány vybraným indukčním algoritmem.
Generování všech možných pravidel Rall je také možný přístup. Je jisté, že Rall bude obsahovat všechna zajímavá slabá pravidla. Pravidel však může být příliš mnoho – může to být mnohem více než je množství záznamů v datech.
Existují dva směry hledání zajímavých a neočekávaných vzorů: subjektivní a objektivní. Hlavní objektivní faktory užívané na určení zajímavosti objevených vzorů jsou síla (strength), spolehlivost (confidence), dosah (coverage) a jednoduchost (simplicity).
Ne všechna silná pravidla s vysokou spolehlivostí a podporou jsou zajímavá, protože mohou být shodná s dřívějšími znalostmi nebo očekáváním. Významnost dříve známých informací není příliš velká. Někteří autoři užívají šablony pravidel k nalezení zajímavých pravidel z množiny všech objevených asociačních pravidel. Jiní analyzují objevená klasifikační pravidla porovnáním s obecnými specifikovanými užitím reprezentačního jazyka. Pouze pravidla vyhovující těmto obecným vlastnostem jsou považována za neočekávaná.
Protože zajímavost vzoru samotného je subjektivní, pravidlo může být zajímavé pro jednoho uživatele , ale už ne pro jiného. Proto většina dřívějších prací spoléhá na to, že spolehlivé výjimečné vzory rozliší uživatel. Potencionálním problémem je, že uživatelovo subjektivní posouzení může být nespolehlivé a nejisté v případě, kdy jsou objevená pravidla četná. Nedávno někteří autoři nabídli přístup nabízející autonomní pravděpodobnostní odhad, který může objevit páry pravidel s vysokou spolehlivostí. Nepožadují vyhodnocení uživatelem ani znalost oboru.
V tomto článku se zabýváme problémem vyhledávání slabých vzorů z dat. Jednoduchý, ale flexibilní přístup navrhovaný v této práci pracuje na základě silných vzorů a užívá analýzu odchylek k nalezení spolehlivých výjimek. Na rozdíl od dřívější práce pana E. Suzukiho (Autonomous discovery of reliable exception rules v Proc. of the 3rd International Conference of Knowledge Discovery and Data Mining, stránky 259-263) se vyhýbáme vyhledávaní silných vzorů v běžném smyslu. Spíše přímo identifikujeme výjimečné příklady a získáme z nich slabé vzory. Mimo slibované efektivity hledání slabých vzorů, navrhovaná metoda může pracovat jak s subjektivními, tak i objektivními výjimkami. K demonstrování efektivnosti této nové metody ji aplikujeme na data z reálného života a skutečně nalezneme některé zajímavé výjimečné vzory. Z datového souboru hub můžeme najít více spolehlivých výjimek v porovnání s výsledky pana Suzukiho.
Náš přístup je založen na následujících zjištěních:
Pozorovaní 1. říká, že výjimky nemohou být objeveny v datech užitím standardní techniky strojového učení. zjištění 2. a 3. nám dovolují se zaměřit na zajímavé vlastnosti a je možná účinná metoda pro hledání spolehlivých výjimek. Náš přístup se skládá ze 4 fází:
1. Nalezení pravidel a zaměření se na některá z nich
Tato fáze získává silné vzory. Normálně zde může uživatel ukončit předběžné zkoumání při dolování znalostí. Pokud je počet nalezených pravidel příliš velký, uživatel může vybrat k dalšímu zkoumání jen nejsilnější z nich nebo postupovat podle metod navržených jinými autory (B. Liu, W. Hsu, S. Chen – Using general impression to analyze discovered classification rules). Předpokládejme, že naši pozornost přitahuje jen několik pravidel a my jsme zvědaví na všechny spolehlivé výjimky s ohledem na tyto silné vzory. Je to filtrovací krok, který nám pomáhá zaměřit se rychle na pár atributů. Pokud máme představu o tom, co chceme vyzkoumat (tzn. známe důležité atributy), potom tento krok můžeme nahradit specifikací důležitých atributů uživatelem.
2. Tabulka nahodilostí a odchylka
Teď se zaměříme na některé atributy v pravidle. Můžeme použít tyto atributy na vytvoření tabulky nahodilostí, která slouží k vypočítání odchylek.
Třída |
Atribut |
Celkové R |
|||
---|---|---|---|---|---|
V1 |
V2 |
… |
Vc |
||
C1 C2 … Cr |
(n11)x11 (n21)x21 … (nr1)xr1 |
(n12)x12 (n22)x22 … (nr2)xr2 |
… … … … |
(n1c)x1c (n2c)x2c … (nrc)xrc |
n1. n2. … nr. |
Celkové C |
n.1 |
n.2 |
… |
n.c |
n |
V tabulce xij jsou četnosti výskytu nalezené v datech.
nij = ni.n.j / n jsou očekávané četnosti výskytu,
n = Si=1r Sj=1c xij,
n.j = Si=1r xij je součet sloupce,
ni. = S j=1c xij je řádkový součet.
Při použití očekávané četnosti jako normy můžeme definovat odchylku jako
dij = xij – nij / nij.
3. Pozitivní, negativní a význačné odchylky
Po použití výše popsaného definice počítání odchylek můžeme předpokládat, že máme tři typy odchylek: kladné, záporné a nulové. Pokud je odchylka kladná, ukazuje to, že to, čeho se týká, je silný vzor. Pokud je nulová, je to normální, a pokud je záporná, je to, čeho se týká, neslučitelné se silnými vzory. Hodnota d ukazuje důležitost odchylky. Velká hodnota znamená, že odchylka může být způsobena náhodně. Protože se zaměřujeme na spolehlivé výjimky a spolehlivost je subjektivní podle potřeb uživatele, specifikujeme hodnotu dt pro definici, jak je spolehlivost spolehlivá. Pokud dt > 0, každá odchylka d > dt je jistě významná. Pokud dt < 0, každá odchylka d < dt je negativně významná. Odchylky jsou silné a užitečné v případě, že poskytují jednoduchý způsob identifikace zajímavých vzorů v datech. To je ukázáno v aplikaci zvané KEFIR.
4. Spolehlivé výjimky
Po tom, co jsme identifikovali význačné, negativní odchylky hodnot atributů s přihlédnutím k označení třídy, můžeme získat všechny záznamy, které obsahují tyto hodnoty atributů a páry tříd a provést další dolování na vybrané množině dat (tzv. okno) použitím libovolné techniky dolování znalostí. Např. můžeme pokračovat hledáním četností množin položek k prozkoumání výjimečných kombinací. Protože počet záznamů je teď mnohem menší než původní, výkon dolováni by se měl mnohem zvýšit. Spolehlivé výjimky mohou být ty nejčetnější množiny položek s vysokou podporou v okně.
Silná asociační pravidla nalezena v okně mohou být silnými pravidly, které by mohly být nalezeny v celé množině dat. Potřebujeme se ujistit, že to ,co jsme našli, jsou slabé vzory – malá podpora, ale velká spolehlivost. Jinak řečeno, každé podmnožiny položek nalezené ve spolehlivé výjimce mohou být vyloučeny, pokud mají velkou podporu v celých datech. Jednoduchá metoda je taková: za předpokladu, že X je podmnožina položek, která nezahrnuje atributy s negativní odchylkou v silném asociačním pravidle nalezeném v okně, můžeme porovnat podporu supwin X v okně a její doplněk supwho v celých datech. Poznamenejme, že to co skutečně chceme zjistit je P(X,c) pro okno a P(X) pro celá data s přihlédnutím k X-->c. Pokud uvažujeme jejich poměr, jsou ve skutečnosti hodnotami spolehlivostí. Proto, je-li rozdíl confwin – confwho dostatečně velký (protože confwin je vždy 1, velký rozdíl znamená malou confwho), můžeme být spokojeni, že velká spolehlivost X je jednoznačná pro okno, jinak není dostatečný důvod přidávat X mezi konečné spolehlivé výjimky.
Od výjimečných pravidel k pravidlům jasným z reality a odkazujícím pravidlům
Dříve než ověříme navrhovaný přístup, měli bychom říct několik slov o výjimkách nalezených při tomto přístupu a těch definovaných panem Suzuki. Suzuki navrhuje, že pro výjimečná pravidla bychom měli být schopni najít odpovídající pravidlo jasně plynoucí z reality a odkazující pravidlo (reference rule). Odkazující pravidlo by mělo mít malou podporu a malou spolehlivost. Vzhledem k povaze negativních odchylek, je jasné, že každé výjimečné pravidlo nalezené naším přístupem má odpovídající pravidlo plynoucí z reality (s pozitivní odchylkou). Odkazující pravidlo může také být nalezeno, když odstraňujeme podmnožiny položek s vysokou spolehlivostí zmíněné výše. Shrneme-li to, pravidlo jasně plynoucí z reality a odkazující pravidla mohou být získány na základě výjimečných pravidel.
Databáze má 10 atributů a 125 záznamů o tom, kdy lidé poskytují nebo neposkytují půjčky.
Krok 1. Identifikace významných atributů
Pustili jsme C4.5 pravidla na data a získali 5 pravidel. Podmínková část 3 z nich obsahuje atribut “nezaměstnaný”. Proto rozhodneme, že je významný, a že třídní atribut je “půjčka”. Jak můžeme vidět, tento krok může být objektivní – významné atributy jsou získány algoritmem, nebo subjektivní – významné atributy vybere expert nebo uživatel.
Krok 2. Vytvoření tabulky nahodilostí
Tabulka 1. je tabulka nahodilostí pro “nezaměstnaný” a “půjčka”. Pro spojité atributy jsou různě velké skupiny získány přímo kategorizací standardní metodou stejně širokých intervalů. Cílem tabulky je určit, jestli dva atributy “nezaměstnaný” a “půjčka” jsou nezávislé (jako v testu c2). Každá buňka tabulky reprezentuje jednu z k =2 x 2 = 4 kategorií dvourozměrné klasifikace n = 125 pozorování. Součty řádků jsou n1. = 40 pro “půjčka = ne” a n2. = 85 pro “půjčka = ano”, zatímco součty sloupců jsou n.1 = 111 pro “nezaměstnaný = ne” a n.2 = 14 pro “nezaměstnaný = ano”. Např. x12 reprezentuje počet nezaměstnaných, kteří neposkytují půjčku, zatímco n12 reprezentuje odpovídající očekávanou hodnotu.
Tabulka 1. Očekávané a skutečné počty pro klasifikaci nezaměstnaných
Třída Půjčuje |
Atribut = nezaměstnaný |
Celkové R |
|
---|---|---|---|
Ne |
Ano |
||
Ne |
(35,5) 28 |
(4,5) 12 |
40 |
Ano |
(75,5) 83 |
(9,5) 2 |
85 |
Celkové C |
111 |
14 |
125 |
Pokud jsou při analýze tabulky nahodilostí dva atributy nezávislé, pravděpodobnost, že je položka klasifikována v nějaké buňce je dána jako důsledek příslušných okrajových pravděpodobností. To je proto, že ve statistickém významu, pokud jsou události A a B nezávislé, potom P(A ^ B) = P(A)P(B). Můžeme ukázat, že nulová hypotéza, že klasifikace jsou nezávislé (v tabulce 1.) je ekvivalentní s hypotézou, že každá pravděpodobnost v buňce je rovná důsledku příslušné řádkové a sloupcové okrajové pravděpodobnosti.
Krok 3. Identifikace význačných negativních odchylek
V tabulce 1., za předpokladu nezávislosti, můžeme spočítat odchylku dij počtů výskytů z očekávaného počtu jako (xij – nij / nij). Tabulka 2. ukazuje odchylky setříděné podle jejich důležitosti.
Tabulka 2. Odchylky analýzy klasifikace nezaměstnaných
Nezaměstnaný |
Třída |
xij |
nij |
d |
---|---|---|---|---|
Ano |
Ne |
12 |
4,5 |
* +1,68 |
Ano |
Ano |
2 |
9,5 |
* -0,79 |
Ne |
Ne |
28 |
35,5 |
-0,21 |
Ne |
Ano |
83 |
75,5 |
+0,10 |
Pokud je standardní hodnota dt = -0,30, máme dvě význačné odchylky označené znakem “*” v tabulce 2. Velká pozitivní odchylka odpovídá očekávané skutečnosti. Je to velká negativní odchylka, která může vést ke spolehlivé výjimce. Vzor “nezaměstnaný neposkytuje půjčky” ukazuje nejvýznamnější kladnou odchylku d = +1,68. Takové vzory jsou statisticky významné, intuitivní a reprezentovány silnými vzory. Např. asociace níže má velmi vysokou spolehlivost.
nezaměstnaný = “ano”, … --> třída = “ne” [spolehlivost = 0,857]
Významná negativní odchylka (d = -0,79) říká, že “nezaměstnání poskytují půjčku”. To je intuitivně špatné nebo neočekávané a přirozeně vhodné k prozkoumání.
Krok 4. Nalezení spolehlivých výjimek
Pokračujeme ve zkoumání výsledků význačných negativních odchylek. Vybereme záznamy vyhovující nezaměstnaný = “ano” a půjčuje = “ano”, neboli “nezaměstnání poskytují půjčku”. Vyhovující záznamy tvoří okno, počet záznamů určuje velikost okna. Aplikováním algoritmu Apriori získáme slabý vzor “nezaměstnané ženy s malou pracovní zkušeností poskytují půjčku” po odstranění položek s vysokou spolehlivostí (> 0,70) jako oblast = “dobrá” (0,72) a ženatý/vdaná = “ano” (0,71).
Počet kandidátů na výjimky je určen hodnotou dt – čím větší je jeho hodnota, tím méně je kandidátů. Ačkoli nemůže existovat výjimka pro každý samostatný atribut, čím víc je atributů, tím více výjimek můžeme najít.
Soubor má 22 atributů, každý má 2-12 možných hodnot, a 8124 záznamů s binární třídou. Dva typy (třídy) hub jsou “jedovatá” a “jedlá”. Na této množině se pokusíme ověřit, že náš přístup nalezne stejné výjimky jako pan Suzuki.
Krok 1. Identifikace významných atributů
Protože všechna 4 pravidla objevena panem Suzukim obsahují “spodek nožky = ?”, vybereme “spodek nožky” a třídu pro zkoumání.
Krok 2. Vytvoření tabulky nahodilostí
Tento krok je rutinní a výsledky jsou zobrazeny v tabulce níže. Pouze vložíme očekávané četnosti pro “spodek nožky = ?”.
Tabulka nahodilostí pro kategorie spodku nožky
Třída |
Atribut = spodek nožky |
Celkové R |
||||
---|---|---|---|---|---|---|
b |
c |
e |
r |
? |
||
jedovatá |
1856 |
44 |
256 |
0 |
(1195)1760 |
3916 |
jedlá |
1920 |
512 |
864 |
192 |
(1285)720 |
4208 |
Celkové C |
3776 |
556 |
1120 |
192 |
2480 |
8124 |
Krok 3. Identifikace význačných negativních odchylek
V tabulce níže ukazujeme odchylky pro “spodek nožky = ?” a zanedbáváme ostatní. Význačná negativní odchylka je –0,44 pro “Třída = jedlá”.
Tabulka 2. Odchylky analýzy klasifikace nezaměstnaných
Spodek nožky |
Třída |
xij |
nij |
d |
---|---|---|---|---|
? |
jedovatá |
1760 |
1195 |
+0,47 |
? |
jedlá |
720 |
1285 |
-0,44 |
... |
|
|
|
Krok 4. Nalezení spolehlivých výjimek
Při použití “spodek nožky = ?” a “třída = jedlá” utvoříme okno se 720 záznamy. Pokud jednoduše spustíme Apriori na okno pro nalezení četných množin položek, získáme dvě množiny položek (připomeňme, že spolehlivost pro okno je vždy 1). Pro 1. kandidáta na výjimku máme následující množiny položek. “Vybrano” níže znamená, že položka byla vybrána, aby zůstala v množině.
Hodnota atributu |
Celková spolehlivost |
Vybráno |
---|---|---|
Spodek nožky = ? |
0,29 |
Ano |
Typ závoje = p |
0,52 |
Ano |
Tvar nožky = e |
0,46 |
Ano |
Velikost lupenů = b |
0,70 |
Ano |
Potlučení = f |
0,31 |
Ano |
Typ prstence = p |
0,79 |
Ne |
Po odstranění těch s vysokou spolehlivostí (> 0,70), máme pravidlo 1 stejné jako pan Suzuki:
CS: potlučení = f, velikost lupenů = b, tvar nožky = e --> třída = jedovatá
RE: potlučení = f, velikost lupenů = b, tvar nožky = e, spodek nožky = ? --> třída = jedlá
RR: spodek nožky = ? --> třída = jedlá
kde CS je pravidlo očekávané z reality (common sense rule), RE je spolehlivá výjimka (reliable exception) a RR je odkazující pravidlo (reference rule).
Pro kandidáta na výjimku číslo 2 po odstranění položek s vysokou spolehlivostí dostaneme nadmnožinu položek pro výjimečná pravidla 2, 3, 4 pana Suzukiho.
Hodnota atributu |
Celková spolehlivost |
Vybráno |
---|---|---|
spodek nožky = ? |
0,29 |
Ano |
barva spor = w |
0,24 |
Ano |
barva závoje = w |
0,51 |
Ano |
typ závoje = p |
0,52 |
Ano |
tvar nožky = e |
0,46 |
Ano |
velikost lupenů = b |
0,70 |
Ano |
sklon lupenů = f |
0,51 |
Ano |
počet prstenců = t |
0,88 |
Ne |
vůně = n |
0,97 |
Ne |
CS: sklon lupenů = f, spodek nožky = ? --> třída = jedovatá
RE: sklon lupenů = f, spodek nožky = ?, velikost lupenů = b, tvar nožky = 3, barva závoje = w --> třída = jedlá
RR: velikost lupenů = b, tvar nožky = 3, barva závoje = w --> třída = jedlá
CS: spodek nožky = ?, barva spor = w --> třída = jedovatá
RE: spodek nožky = ?, barva spor = w, sklon lupenů = f, velikost lupenů = b, tvar nožky = e --> třída = jedlá
RR: sklon lupenů = f, velikost lupenů = b, tvar nožky = e --> třída = jedlá
CS: spodek nožky = ?, barva spor = w --> třída = jedovatá
RE: spodek nožky = ?, barva spor = w, barva závoje = w, velikost lupenů = b, tvar nožky = e --> třída = jedlá
RR: barva závoje = w, velikost lupenů = b, tvar nožky = e --> třída = jedlá
Prezentujeme tady jednoduchý přístup, který nám umožňuje studovat spolehlivé výjimky s přihlédnutím k pravidlu našeho zájmu nebo atributům specifikovaným uživatelem. Většina technik jsou analýza odchylek, tvorba oken a tradiční nástroje dolování (např. Apriori pro hledání asociací). Pro atributy, týkající se našeho problému, nejprve určíme jejich negativní odchylky, které určí okno, a potom hledáme spolehlivé vzory z okna s použitím libovolného nástroje dolování znalostí. Spolehlivé výjimky jsou ty vzory, které jsou platné pouze v okně.
Tento přístup je efektivní, protože:
Kromě toho je tento přístup také flexibilní k zpracování jak subjektivních tak i objektivních dřívějších znalostí.