LISp-Miner
11.5.2004 Martin Šulc Projekt do předmětu Vyhledávání znalostí v databázích
Zadání Popis systému LISp-Miner a experimenty s databází. Abstrakt Tento projekt popisuje systém LISp-Miner, jeho instalaci, strukturu systému, vlastnosti modulů pro předzpracování a pro dolování asociačních pravidel. Projekt obsahuje i podrobný ukázkový test, který by měl usnadnit začínajícím práci s modulovým systémem LISp-Miner.
1 Úvod Akademický softwarový sytém LISp-Miner, který je vyvíjen na Fakultě informatiky a statistiky VŠE v Praze od roku 1996, je určen studentům pro seznámení se s procesem dobývání znalostí z databází. Je to náhrada drahých komerčních systémů, které se používají na složitě strukturované databáze, které vznikají i desítky let v organizacích jako jsou nemocnice, banky, průmyslové podniky, školy, obchodní řetězce a podobně. Z těchto databází lze často získat více informací než se původně předpokládalo. Tyto informace se stávají cenné pro marketing podniků a v lékařství pro odhalení závislostí mezi nemocemi a charakteristikami pacientů. Kurzívou jsou psané poznámky, rady, kritika autora a příklady práce se systémem LISp-Miner.
2 Instalace Systém LISp-Miner je nenáročný na instalaci. To znamená, že pro práci jsou zapotřebí jen *.exe soubory, které lze uložit do jakéhokoliv adresáře na jakémkoliv logickém disku (i síťovém). Všechny soubory lze stáhnout z webové adresy http://lispminer.vse.cz/download/download.php, kde jsou v balíčcích s příponou *.zip.
3 Vlastnosti LISp-Miner je modulový systém skládající se z modulů/programů, které lze rozdělit do tří kategorií: 1- Moduly pro seznámení se s daty a transformaci dat (tvorba atributů, úprava spojitých dat, …) 2- Zpracování analýz (vytváření úloh, dolování - hledání asociačních pravidel, …) 3- Reprezentace výsledků (asociační pravidla, …)
Obrázek 3.1 Znázorňuje rozložení modulů podle fáze Data-Mining.
4 Databáze 4.1 Testovaná data, příprava dat Příprava dat je časově většinou nejnáročnější část procedury dolování, ze zkušenosti lze říct, že zabírá kolem 80% celkového času. LISp-Miner používá databázi Microsoft Access, takže se data musí importovat do této databáze, pokud není zdrojem dat soubor aplikace Microsoft Access, která splňuje nároky na ODBC. ODBC (Open Database Connectivity) je univerzální rozhraní na platformě Microsoft Windows, které umožňuje jednotný přístup ze strany klienta, nezávisle na tom, jaký databázový server používá. Rady začátečníkům: Nepoužívejte v názvech souborů pro testování ani v názvech tabulek a atributů, které databáze používají pro modelování jiné znaky než znaky abecedy ‘A’ až ‘Z’ a číslice 0 až 9. Jinak se můžete během práce s moduly dočkat chybových hlášek jako je na obrázku 4.1.1 nebo 4.1.2.
Obrázek 4.1.1 Ukázka chybové hlášky u atributu „Pole 12“ při inicializaci tabulky modulem LMDataSource.exe, název obsahuje mezeru. Tabulka bude přidána, ale chybné atributy budou odfiltrovány.
Obrázek 4.1.2 Chybová hláška při inicializaci databáze modulem LMAdmin.exe (Název zdrojového souboru obsahuje nepovolené znaky). 4.2 Metabase Velmi důležitou součástí systému je „prázdná databáze“, která je systémem LISp-Miner nazývána Metabase. Je to databáze, která neobsahuje žádná data, ale obsahuje 68 tabulek a je velmi důležité, aby při inicializaci souborem LMAdmin.exe byly tabulky prázdné. Pokud není metabáze „prázdná“ a byla například použitá při předchozích dolováních, tak budete dotázáni na heslo administrátora nebo budete moci zadat jinou prázdnou databázi, viz obrázek 4.2.1. Prázdná metabáze LMEmpty.mdb je na adrese http://lispminer.vse.cz/download/download.php
Obrázek 4.2.1 Použití neprázdné metabáze vyvolá výzvu pro vložení hesla administrátora nebo vybrání nové metabáze. Kritika: Nepřišel jsem na to, jaké heslo to má na mysli, i když jsem při původní inicializaci žádné nezadával. Nepodařilo se mi to obejít ani vybráním nové správné metabáze. Zřejmě je to větev programu, na kterou autor zapomněl, a která potřebuje doladit. (Toto okno však není součást programu, je to služba ODBC a chyba spočívá v tom, že LMAdmin.exe nedokáže převzít hodnoty od této služby, hodnotou může být jiná databáze nebo původní s ověřeným loginem a heslem.) Tato větev je důležitá, pokud chcete provést nové testy na již testované databázi, podmínkou však je aby se od posledního testování nezměnila, jinak by se stala nekorektní, protože do metabáze se ukládají i podrobné informace o testované databázi, takže by se pak neshodovali (podmínka konzistence dat).
5 Ukázkový test Na tento test je zapotřebí minimálně šest souborů. Jsou to: databáze, metabáze, LMAdmin.exe, LMDataSource.exe, 4ftTask.exe a 4ftResult.exe. Databáze a Metabase jsou popsány výše. Programy jsou ke stažení na adrese http://lispminer.vse.cz/download/download.php a jsou všechny v balíku LISpMiner.zip nebo také v LISp-Miner.4ft.zip. 5.1 Modul LMAdmin.exe Tento modul nemá příliš významnou funkci, kromě toho, že částečně zkontroluje metabázi a databázi s testovanými daty. Je to modul, který se spouští jako první a provádí se jím inicializace databází. Po spuštění se tlačítkem Create new data source přepne do okna, kde se tlačítky Browse vyberou do horní části data, ve kterých se bude dolovat a do střední části metabáze, do které se budou ukládat výsledky dolování a další informace, tak jak to je vidět na obrázku 5.1.1. V dolní části je přepínač DSN typů,
který je zapotřebí přepnout do User DSN v počítačových učebnách, na vlastním PC se ponechává default, tedy System DSN. Pro testování si vybereme databázi z fiktivní banky Barbora, kterou lze i s metabází stáhnout z adresy uvedené výše a je v balíčku Barbora.zip. Před testováním si všimněte, že metabáze přiložená k Barboře má jinou velikost než metabáze, která je v souboru LMEmpty.zip. Autoři zřejmě zmenšili původní metabázi na 63 tabulek z toho důvodu, že Barbora asi nevyužije všechny tabulky obsažené v LMEmpty.mdb. Ale my použijeme právě tu původní nezmenšenou metabázi LMEmpty.mdb, abychom se mohli podívat, které tabulky jsou nevyužity. Před inicializací je ještě důležité přejmenovat metabázi třeba na LMMetaBarbora.mdb, protože název metabáze se používá i později pro identifikaci při výběru v ostatních modulech.
Obrázek 5.1.1 Výběr databáze a metabáze modulem LMAdmin.exe. 5.2 Modul LMDataSource.exe Modul je součástí fáze pro přípravu a seznámení se s daty před dobýváním znalostí z databází a lze jím data procházet. Je možné vytvářet v tabulce nové sloupce, které budou odvozené z tabulky. Tato nová data mohou
urychlit a usnadnit dolování. Například vytvoření nového atributu „Vek“ odvozeného od sloupce s rodnými čísly v lékařských záznamech nebo vytvoření atributu „DenVTydnu“ odvozeného od datumu. Tím například docílíme vytvoření nového atributu rozděleného do sedmi tříd Po, Ut, St, Ct, Pa, So, Ne. To umožní hledání určitých asociačních pravidel, pro dny v týdnu. LMDataSource umožňuje i kategorizaci intervalů nebo hodnot, takže týden je možné seskupit do dvou shluků, tedy „PracTyden“ a „Vikend“.
Obrázek 5.2.1 Modul LMDataSource.exe pro přípravu databáze. Spustíme si LMDataSource.exe a z nabídky vybereme metabázi, kterou jsme si před tím pojmenovali LMMetaBarbora.mdb. Tlačítkem Select potvrdíme. Bude provedena kontrola databáze, při které se může objevit chybová hláška podobná obrázku 4.1.1, což je špatně pojmenovaný sloupec (atribut) a bude odfiltrován pro další práci s databází, ale Barbora by měla být v pořádku. Zřejmě je provedeno i načtení celé databáze do paměti, ale to jen usuzuji podle dalšího chování modulu, které je velice rychlé, a také velikost alokované paměti programem se po načtení zvětší z 3536kB na 8076kB (pro testování jsem použil Microsoft Windows Server 2003 Trial 180 32bit. Edition, pro zjištění velikosti programu jsem použil TaskMgr.exe). Na obrázku 5.2.1 je hlavní okno modulu LMDataSource, ve kterém je vidět, že
databáze Barbora obsahuje jedinou tabulku Loans. Přepnutím tlačítkem Columns a následným výběrem tabulky Loans zjistíme, že tabulka má osm atributů a jaké jsou jejich datové typy, obrázek 5.2.2. Tlačítko Rows odhalí pohled na celý obsah databáze (pokud nebyly některé atributy odfiltrovány), viz obr. 5.2.3. Výběrem položky Order by Column určíme setřídění určitého sloupce, implicitně je nastaveno u prvního sloupce v databázi. Poslední položkou Frequencies zjistíme procenta i počet výskytů hodnot v určitém sloupci tabulky viz obrázek 5.2.4.
Obrázek 5.2.2 LMDataSource.exe – informace o sloupcích (atributech).
Obrázek 5.2.3 LMDataSource.exe – náhled na hodnoty a informace, že tabulka obsahuje 6181 řádků.
Obrázek 5.2.4 LMDataSource – nejvíce je zákazníků patřících do skupiny C, tedy 58,7% splácí půjčku bez problému. A = splaceno, B = nebylo řádně splaceno, D = splácí se, ale se zpožděním. Další důležitou fází pro přípravu dat je vytvoření atributů, ve kterých se budou dobývat asociační pravidla. Musí být určen i primární klíč, který nesmí obsahovat duplicitní hodnoty. Modul obsahuje procedury na kontrolu, zda jsou tyto podmínky splněny. Lze vytvářet nové atributy odvozené z původních atributů pomocí popisu, který lze zadat. V menu Database položkou Data Matrice F5 nebo tlačítkem vybereme pohled na tabulky v databázi, vybereme Loans tlačítkem Details. Primární klíč vytvoříme z atributu loan_id tak, že vybereme tento řádek a stiskem tlačítka Primary key označíme atribut. Kontrolu na duplicitu lze provést tl. Check. Databáze banky Barbora obsahuje atribut birth_number což je rodné číslo. Tento atribut je nevhodný pro dolování, ale obsahuje užitečnou informaci o věku zákazníků, takže vytvoříme nový atribut Vek odvozený od rodného čísla. Přes Add derived vytvoříme vyplněním vhodných informací nový atribut Vek, který je odvozený z rodného čísla přes tento vzorec: Year(Now())-1900-Clng(birth_number/10000) , viz obr. 5.2.5
Obrázek 5.2.5 LMDataSource při tvorbě atributu Vek přepočtem z rodného čísla (birth_number). Aby bylo možné v dalších modulech dobývat asociační pravidla, musíme vytvořit několik dalších atributů. Přes menu Database a Attributes List Ctrl+F7 nebo se dostaneme do seznamu atributů, přes Add a výběrem tabulky Loans tlačítkem Select se dostaneme do podobného okna jako při vytváření atributu Vek s tím rozdílem, že teď budeme určovat, které atributy budou při dobývání asociačních pravidel k dispozici, spojité atributy se budou dělit do intervalů, a tak dále. Všimněme si, že zde přibylo tlačítko Create attribute. Použijeme ho na atribut Amount, v následujícím okně ho přejmenujeme na Castka, odklikneme OK. Okno Automatic creation of categories je významné pro předzpracování dat. Volbou možnosti Equidistant intervals a zadání počáteční hodnoty nula do pole From a velikosti (délky) intervalu 50 000 do pole Length, jak je vidět na obrázku 5.2.6 diskretizujeme spojitý atribut. OK.
Obrázek 5.2.6 LMDataSource – úprava atributu Okno Atribute nabízí možnosti pohledu na data přes různé analýzy. Například frekvenční analýza, tlačítko Fr. Analysis ukáže, že by bylo vhodné sloučit poslední dva intervaly. V okně Attribute je tedy označíme a tlačítkem Join sloučíme do jednoho. Název nového intervalu Join: <500000;550000), <550000;600000) můžeme přes Category a následně Edit category přejmenovat na <500000;600000). Podobným způsobem vytvoříme atributy Mesto z atributu Distinct u nějž ponecháme Each value – one category. U Mesice z Duration postupujeme stejně, a navíc sloučíme hodnoty 12 a 13. Čtvrtý atribut jsou Splatky z atributu Payments u něhož postupujeme podobně jako u prvního, intervaly začínají na nule a jsou dlouhé 2000, s tím že nulové hodnoty od intervalu <10000;12000) do konce odstraníme (tlačítko Del) a zůstane tam jen pět intervalů. Atribut Plat ze Salary vytvoříme jako intervaly od hodnoty 8000 s délkou 1000. Předposlední atribut Kategorie vytvoříme z atributu Status, který má čtyři kategorie, jsou to kategorie, které charakterizují zákazníka, jemuž byla poskytnuta půjčka. V lékařství by takovéto rozdělení mohlo být podle toho, jak dopadla léčba pacienta s tím že by byly kategorie rozdělené podle následků od kategorie žádné následky, dočasné, trvalé až po smrt. V bance Barbora to jsou kategorie: A – splaceno bez problémů, B – nebylo řádně splaceno, C – doposud se splácí bez problémů, D – Doposud se splácí, ale se zpožděním. U
tohoto atributu ponecháme Each value – one category. Poslední bude atribut Vek, který upravíme na intervaly od 20-ti s délkou 5 let. Modul LMDataSource umožňuje i analýzu kontingenčními tabulkami. Tabulka se zobrazí jako odstínovaná plocha červené až tmavě červené barvy, a také jako graf v provedení 3D, který nabízí velice užitečný pohled na data. Bohužel graf, v době testování byl jako beta-verze, takže při jeho otáčení v něm při některých pozicích vznikali grafické chyby. Pro otáčení 3D grafem by bylo vhodnější použít plynulé otáčení myší.
Obrázek 5.2.7 LMDataSource – Ukázka kontingenční tabulky. Pro zobrazení grafu jako na obrázku 5.2.7 je v modulu LMDataSource v menu Analysis položka KxL Contingency Table. Další ovládání je jednoduché a intuitivní, které nepotřebuje další popis. 5.3 Modul 4ftTask.exe Tento modul je jeden z několika pro dobývání asociačních pravidel systému LISp-Miner. Další jsou CFTask, KexTask a KLTask. Každý modul používá
jinou metodu pro dobývání asociačních pravidel. Modul pracuje tak, že uživatel vytvoří úlohu, ve které pak pracuje a její výsledky se ukládají do souboru s metabází. Až do této fáze je metabáze v původním stavu. Po každém testu modul nabídne výsledky v textové podobě s možností snadného kopírování textu. Na programu je vidět, že je ještě „čerstvý a nevychytaný“ a obsahuje chyby. Mockrát jsem narazil na neošetřená místa a takových „printskrýnů“ jako je na obrázku 5.3.1 mám hodně. Tento vznikl tak, že v modulu 4ftTask vytvoříte první úlohu, pak ji tlačítkem Del smažete. Po smazání se nezakryje v menu Task description položka Task clone Shift+F6, která před tím byla zakrytá, což je první chyba a druhá, která na to navazuje, je ta, že když Task clone použijete, tak nepozná, že není vybraná žádná úloha, jelikož tam žádná není a program skončí chybou. Jinak systém LISp-Miner je z pohledu dolování asociačních pravidel bez chyby, resp. jsem žádnou chybu takového charakteru, který by bránil dolování nenašel.
Obrázek 5.3.1 Chyba v modulu 4ftMiner Novou úlohu vytvoříme v menu Task description volbou New task F6 nebo přes . Opět vybereme tabulku Loans. Pak zadáme název úlohy, který bude „Neplatící“, protože budeme dolovat z kategorie B. OK. V okně Task se nastavují všechny parametry pro dolování. Okno je přehledné a dá se s ním rychle pracovat. Nastavíme v něm parametry, jako to je vidět na obrázku
5.3.2, a to tak, že v položce ANTECEDENT přes Add přidáme atribut Castka, který změníme na typ Interval s minimem jedna a maximem dva. Takto vybereme zbytek atributů jako na obr. 5.3.2. V položce SUCCEDENT přidáme jediný atribut Kategorie jako typ One category, a Category vybereme B. Parametr p je konfidence a můžeme jej ponechat na výchozí hodnotě p = 0,9 s kvantifikátorem FUI (Flounded Implication). V okně pod tlačítkem Params zadáme parametr BASE, což je support neboli podpora na hodnotu 18. Odškrtneme políčko BASE in %, a obě políčka v Options. Tím jsme nastavili parametry pro dolování a můžeme stisknout Generate čímž se spustí samotné dolování. Za 1 minutu a 12 sekund bylo provedeno 12519 verifikací a nalezeno 8 asociačních pravidel, které jsou ve výsledku uvedeny jako hypotézy, jak je to vidět na obrázku 5.3.3.
Obrázek 5.3.2 4ftTask – nastavení parametrů pro dolování asociačních pravidel v úloze Neplatící.
Obrázek 5.3.3 4ftTask – výsledné okno po dolování v úloze Neplatící Výhoda systému LISp-Miner je jistě v tom, že na rozdíl od většiny ostatních systémů hledá (umí hledat) jen taková asociační pravidla, která nás skutečně zajímají! Tj. jako v uvedeném příkladu hledá pravidla, která popíší uživatele, kteří nejčastěji nesplácí své půjčky. Při porovnání s ostatními systémy (uvedeno níže), je vidět, že systém LISp-Miner je vhodnější pro dolování v datech, která jsou roztříděna do nějakých kategorií (tříd). 5.4 Modul 4ftResult.exe Tento modul je jeden z několika pro prohlížení asociačních pravidel systému LISp-Miner v grafech a čtyřpolních tabulkách. Další jsou CFResult, KexResult a KLResult. Každým modulem lze prohlížet pouze taková data, která vyhledal modul, který s ním souvisí, například 4ftResult pro 4ftTask. Spustíme 4ftResult a přes menu Task description a Task list F7 nebo přes vybereme položku Neplatící a zobrazí se nám seznam s asociačními pravidly, která jsou na první pohled dobře čitelná (pochopitelná).
Tip na porovnávací test platících zákazníků: Zadejte následující hodnoty do nové úlohy v modulu 4ftTask, postup je stejný jako v předchozí úloze Neplatící. Název: Platící Antecedent: Castka: int, 1-1, B, pos Mesice: int, 1-1, B, pos Mesto: subsett, 1-1, B, pos Plat: int, 1-1, B, pos Splatky: int, 1-1, B, pos Vek: int, 1-2, B, pos Succedent: Kategorie A p = 0,95 Include antecedent extensions of all implications: No Include succedent extensions of 100% implications: No Výsledek si opět můžeme prohlédnout v modulu 4ftResult tak, že si vybereme úlohu Platící. Úlohy můžeme měnit v menu Task Description položka Task List F7. V úloze Platící bude nalezeno 16 asociačních pravidel, ze kterých bude na první pohled vidět, že nejspolehlivější pro banku je půjčovat částky 50000 až 100000 nebo půjčky se splácením po dobu 12-ti měsíců. Moduly typu Result toho umí, ale mnohem více. Stačí si vybrat libovolné asociační pravidlo ze seznamu v modulu 4ftResult, stisknout tlačítko Detail a vybrat záložku GRAPH, jako je to vidět na obrázku 5.4.1. V této záložce vidíme čtyřpolní tabulku, která ukáže závislosti mezi Antecedent-em (podmínkou) a Succedent-em (závěrem) a jejich graf.
Obr. 5.4.1 4ftResult – náhled na asociační pravidlo přes čtyřpolní tabulku.
6 Experiment Experiment byl proveden na metalovských datech Australian. Soubor Australan.data byl importován do databáze Microsoft Access bez problému. Maximum možných nalezených častých vzorů pro LISp-Miner je 9999. LISp-Miner při dolování asociačních pravidel bere atributy v určitém pořadí, které zadá uživatel, to může mít vliv na konečný výsledek, pokud počet nalezených asociačních pravidel dosáhne v počtu 9999. Sloupec s názvem 0,01/0,95 znamená, že support byl nastaven na 1 % a confidence zvýšena na 0,95, aby bylo nalezeno více maximálních častých vzorů (prohledá se celá databáze a nejen část do nalezení 9999 pravidel). Ve sloupcích kde není uvedena konfidence byla použita hodnota 0,5. V tabulce jsou výsledky testu v závislosti na minimálním supportu (v jednotlivých buňkách jsou hodnoty x/y, kde x = celkový počet nalezených častých vzorů, y = počet maximálních častých vzorů, součet x+y nepřesahuje 9999).
Data/Min. support
0,01/ 0,02/ 0,03 0,05 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1 0,95 0,9 851/ 3220/ 7256/ 3537/53 1004/0 168/0 42/0 9/0 0/0 0/0 0/0 0/0 0/0 0/0 LISp-Miner 5190 1062 362
Úprava dat: Všechny tři spojité atributy, tj. sloupce 2, 3 a 7 byli rozděleny do deseti intervalů s odpovídající hustotou hodnot. Rozdělení je vidět na obrázku 6.1 u atributu Pole2, tj. druhý sloupec z databáze Australian. Nastavení LISp-Miner: Atributy jsou pojmenovány podle pořadí od prvního sloupce jako Pole 1 až Pole 15. Sloupce Pole 1 až Pole 14 jsou jako Antecedent a sloupec Pole 15 je jako Succedent, jak je vidět na obrázku 6.2. U spojitých atributů (2, 3, 7) je nastaveno, že mohou být dvě sousední hodnoty při dolování sjednoceny jako interval pokud to bude významné pro nalezení asociačního pravidla, tím se rozšíří možnosti hledání (obr. 6.2).
Obr. 6.1 LMDataSource – úprava spojitých atributů (Pole 2).
Obr. 6.2 4ftTask – vytváření úlohy pro dolování.
7 Závěr Akademický systém LISp-Miner je dosti specifický systém, který se výkonnostně porovnává s jinými systémy jen těžko. Je to protože se od ostatních systémů liší tím, že se dá úzce specifikovat charakter asociačního pravidla, zatím co většina ostatních systémů, které hledají asociační pravidla, se většinou snaží najít v datech všechna asociační pravidla (ale jsou i výjimky). Díky tomuto zúžení výběru se dolování stává rychlejší. Pro testování byl použit PC s hardwarem: AMD Athlon 3000+, 512MB RAM, 120GB disk s rozhraním SATA 150 a 8MB cache. To že pro přístup k datům používá rozhranní ODBC firmy Microsoft ho nezpomaluje, jak je vidět z výsledku dolování na obrázku 5.3.3. Systém vyniká svou snadnou instalací a pestrou nabídkou různých technik pro dolování asociačních pravidel z databází. Tím že jde o modulový systém, je možné snadno měnit jednotlivé moduly, které mezi sebou dobře spolupracují. Systém umožňuje několik pohledů na data (grafy, tabulky, …). LISp-Miner najde uplatnění
v organizacích, které shromaždují delší dobu data do databází, jako jsou například banky, nemocnice, policie, školy a další. Je zvláště vhodný pro dolování v datech, která mají nějaký atribut rozdělený do tříd.
