Účinné vyhledávání spolehlivých výjimek
(reliable exceptions)

Zdroj informací

Obsah

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.

1. Úvod

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í:

• silné vzory (strong patterns) – společné pro velký počet objektů
• slabé vzory (weak patterns) – spolehlivé výjimky reprezentující relativně malý počet objektů
• náhodné vzory (random patterns) – náhodné a nespolehlivé výjimky

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”.

1.1 Nedostatečná podpora běžných technik dolování znalostí

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ů C_k z množin položek L_k-1, spočítá počet výskytů každé množiny kandidátů množin položek a potom určí množinu L_k č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.

1.2 Ani intuitivní rozšíření nepomůže

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 R_all je také možný přístup. Je jisté, že R_all 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.

1.3 Práce související s naší

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.

1.4 Vlastní práce

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.

2. Navrhovaný přístup

Náš přístup je založen na následujících zjištěních:

1. každá výjimka by měla mít malou podporu, jinak by to měl být silný vzor
2. rozumný indukční algoritmus může sumarizovat data a najít pravidla
3. atributy v pravidlech jsou význačné rysy

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í:

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.

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.

V tabulce x_ij jsou četnosti výskytu nalezené v datech.

n_ij = n_i.n_.j / n jsou očekávané četnosti výskytu,
n = S_i=1^r S_j=1^c x_ij,
n_.j = S_i=1^r x_ij je součet sloupce,
n_i. = S _j=1^c x_ij je řádkový součet.

Při použití očekávané četnosti jako normy můžeme definovat odchylku jako

d_ij = x_ij – n_ij / n_ij.

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 d_t pro definici, jak je spolehlivost spolehlivá. Pokud d_t > 0, každá odchylka d > d_t je jistě významná. Pokud d_t < 0, každá odchylka d < d_t 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 sup_win X v okně a její doplněk sup_who 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 conf_win – conf_who dostatečně velký (protože conf_win je vždy 1, velký rozdíl znamená malou conf_who), 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.

3. Hledání výjimek v datovém souboru

3.1 Množina dat o půjčkách

Databáze má 10 atributů a 125 záznamů o tom, kdy lidé poskytují nebo neposkytují půjčky.

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.

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 c²). 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 n_1. = 40 pro “půjčka = ne” a n_2. = 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ř. x₁₂ reprezentuje počet nezaměstnaných, kteří neposkytují půjčku, zatímco n₁₂ reprezentuje odpovídající očekávanou hodnotu.

Tabulka 1. Očekávané a skutečné počty pro klasifikaci nezaměstnaných

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 d_ij počtů výskytů z očekávaného počtu jako (x_ij – n_ij / n_ij). Tabulka 2. ukazuje odchylky setříděné podle jejich důležitosti.

Tabulka 2. Odchylky analýzy klasifikace nezaměstnaných

Pokud je standardní hodnota d_t = -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í.

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 d_t – čí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.

3.2 Množina dat o houbách

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.

Protože všechna 4 pravidla objevena panem Suzukim obsahují “spodek nožky = ?”, vybereme “spodek nožky” a třídu pro zkoumání.

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

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

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ě.

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.

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á

4. Závěr

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:

1. pracuje nad vybranými argumenty, což zabraňuje prohledávání všech atributů v databázi
2. zaměřujeme se pouze na negativní odchylky
3. prochází data pouze jednou pro vytvoření okna
4. velikost okna (tzn. počet záznamů) je obvykle mnohem menší než celkový počet záznamů

Kromě toho je tento přístup také flexibilní k zpracování jak subjektivních tak i objektivních dřívějších znalostí.