Systém pro získávání znalostí z dat
a jejich vizualizaci

SGI MineSet (v2.6)

[Úvod do práce s MineSetem] [Dolovací nástroje v MineSetu] [Ukázka použití MineSetu]

Co je to MineSet?

Firma Silicon Graphics si za dobu svého působení nashromáždila velké množství údajů. Pro jejich zpracování a rozumné využití se pokusila (a zdá se, že velmi úspěšně) napsat vlastní software schopný zpřístupnit důležité informace skryté v záplavě nepřehledných dat. Z původně interní pomůcky se vyvinul komerční produkt, sada nástrojů pro dolování údajů z rozsáhlých databází. MineSet obsahuje různé programy pro vizualizaci a zpracování dat, které lze spouštět jak samostatně (třeba i neinteraktivně), tak z jednotícího intuitivního grafického rozhraní (Tool Manage). Grafické výsledky jsou prezentovány na vysoké úrovni (dělal to Silicon Graphics ;)) pomocí 3D grafického standardu OpenGL pomocí Inventoru, ale je možné je i exportovat ve formátu vhodném pro prezentaci na Webu. MineSet umí pracovat s většinou používaných komerčních databází (Oracle, Informix, ...) tak s běžnými ASCII soubory. Výkonná část běží jako server (existují i paralelní verze) a lze k ní přistupovat pomocí klientského rozhraní z uživatelských stanic. Bohužel náročná grafika vyžaduje Xserver rozšířený o DGL.

K MineSetu je dostupná rozsáhlá dokumentace v elektronické formě (WWW, PostScript, PDF, nápověda ve formátu InSight).

Jak získat a nainstalovat MineSet?

Přestože je MineSet komerční produkt, dá se jeho zkušební verze (až na možnost paralelního zpracovávání dat identická s ostrou) stáhnout po internetu. Z domovské stránky se dozvíme, co vše potřebujeme. Vyplatí se postupovat podle podrobného návodu. Je třeba si vybrat podle verze Irixu, být zaregistrován v SurfZone a nezaleknout se rozšiřujících návazností potřebných instalačních balíků. MineSet vyžaduje přítomnost některých patchů v systému a správné verze používaných subsystémů (Java, OpenInventor,...). Vše je krok za krokem popsáno např. na stránce s Minesetem 2.6 pro Irix 6.2.

K instalaci se dá použít znakový instalační program inst, nebo grafické rozhrani swmgr. Jediné problémy (kromě asi tří iterací stahování různých patchů pro splnění závislostí) mohou být s nestandardně zavedenými částmi systému, kdy my víme, že Perl máme, ale nevíme, jak to říci instalátoru - řešit se to dá rozbalením balíku do pomocného adresáře, vypsáním cílového umístění jednotlivých souborů a ručním zkopírováním (potřebovala to pouze utilita dataschema usnadňující přípravu vstupních souborů).

Poslední, leč zásadní, částí instalace je získaní licence pro provozování serveru a clienta. Z Webu SGI (Key-O-Matic lze stáhout zkušební třicetidenní licenční klíče. Vzdělávací organizace zapojené do Varsity programu mají i další možnosti.

Lokální instalace MineSetu na FI MU

Na stroji aisa.fi.muni.cz je v tuto chvíli nainstalován MineSet verze 2.6 se všemi vyžadovanými podpůrnými programy a záplatami. Jeho licence nejspíš už ale vypršela ;). Pokud je v provozu, je dobré pro jeho spuštění vědět:

grafické zobrazení vyžaduje DGL display (je nutné sedět u SGI stroje - erinky, indy - a neforwardovat si Xy přes ssh: xhost + aisa; export DISPLAY=erinys??:0)
nezvládá iso-8859-2 (unset LC_CTYPE nebo LC_CTYPE=C)
klient i server poběží jen na aise - spouštět klienta z aisy a připojovat se k serveru aisa (login/passwd stejné jako k běžnému účtu v UNIXu)
je nakonfigurován pro spolupráci s databází Oracle běžící na Aise, do DBMS se přihlašuje pod jménem a heslem z databáze (nemusí být stejné, jako na UNIXovém účtu)

Prostřední hlavního správce MineSetu, ToolManager spustíte nejlépe příkazem:

aisa$ LC_CTYPE=C /usr/sbin/mineset &

Stručný úvod do práce s MineSetem

I když je možné pracovat s MineSetem neinteraktivně nebo vyvolávat jednotlivé výkonné části samostatně, budeme se zabývat pouze ovládáním z intuitivního prostředí ToolManageru:

Rozdělení obrazovky Tool Manageru:

Hlavní nabídka: dovoluje určit zdroj dat, rychle spustit vizualizační (často používané nástroje) a hlavně se dostat ke skutečně důkladné dokumentaci.
Informace o zpracovávaných datech: vypisují server, na kterém budou zpracovávána zadání a zdroj dat (soubor, či databáze)
Panel s údaji o datech a nástroji na jejich přípravu (Data transformation): umožňuje u vybraného zdroje dat blíže specifikovat, se kterými sloupci údajů chceme pracovat, vybírat řádky z tabulky podle jednoduchých výrazů, přetypovávat sloupce a podobně. U všech změn se udržuje historie, takže je možné se vracet.
Panel nástrojů na zpracování dat (Data destination): je hlavní pracovní plochou, na kterou pomocí jednotlivých záložek vybíráme karty příslušných pomůcek, ke kterým se pak dají zadávat dodatečné volby a spouštět je.
Stavové okno: zobrazuje trvale výstupy probíhajících operací, dají se v něm odečítat hodnoty některých zjištěných údajů či sledovat postup zpracování (a případně reagovat na chyby či neočekávané chování).

Vlastní práce s MineSetem

Ovládací prvky MineSetu jsou poměrně standardní v prostředí pracovních stanic SGI, snadno se v nich dá intuitivně myší vyklikávat vše potřebné, stisk klávesy F1 vyvolá občas i kontextovou nápovědu. Konkrétní metody práce se navolí záložkami a je dobré nezapomenout nastavit různé volby buď přímo v kartách či v rozbalitelných nabídkách.

Dolovací nástroje (Mining Tools)

Nástroje MineSetu můžeme rozdělit na induktory (Inducers) a klasifikátory (Classifiers). Induktory jsou algoritmy, ktere čtou vzorová data (Training Set) obsahující datové záznamy a návěští (labels). Úkolem dolování je z neznámých dat, která budou obsahovat pouze datové položky a nikoli návěští, generovat tato návěští s co největší přesností. Induktor vybuduje soustavu pravidel (podle typu induktoru jsou tato pravidla reprezentována různě) a na základě těchto pravidel vygeneruje klasifikátor. Klasifikátor je pak algoritmus, který je možné použít pro klasifikaci nových dat (již neoznačených návěštími).

MineSet obsahuje tyto induktory/klasifikátory:

generátor asociačních pravidel
rozhodovací stromy (decesion tree)
rozhodovací stromy s výběrem kritéria (option tree)
regresní stromy (regression tree)
shlukování (clustering)
hledání významných atributů (important columns)

Výsledky práce těchto algoritmů je možné vizualizovat pomocí vizuálnich nastrojů v podobě 3D stromů, sloupcových grafů a podobně s využitím barev, prostorových operací (rotací, zoomu, atd.) i animací.
V následujícím textu jsou popsány základní informace o jednotlivých nástrojích. Pro studium technických detailů algoritmů použitých při tvorbě MineSetu je dobré se podívat na stránku tříd MLC++ - jde o knihovnu v C++ vyvinutou ve Stanfordu implementující jednotlivé data mining algoritmy.
Všechny dolovací nástroje jsou přístupné v Tool Manageru v panelu Data Destination.

Generátor asociačních pravidel

Asociační pravidla se z dané množiny datových záznamů snaží odvodit pravidla typu

hodnoty A, B, C => hodnoty D, E, F

Typické použití je při analýze nákupních dat - atributy představují nakoupené druhy zboží, snažíme se zjistit pravidla, podle kterých zákazníci nakupují zboží.

MineSet dovoluje generovat buď pravidla s jedním atributem na levé i pravé straně (tato pravidla jsou pak vizualizována ve dvouosém 3D grafu, kde na jedné ose jsou atributy na levé straně a na druhé jsou atributy na pravé straně pravidel) nebo i pravidla s více atributy na obou stranách (tato pravidla pak nemohou být vizualizována jinak než svým vlastním výpisem).
Typické parametry pro tento algoritmus jsou

support - počet všech záznamů obsahujících všechny atributy pravidla
confidence - počet záznamů obsahujících atributy na levé i pravé straně pravidla dělený počtem záznamů obsahujících pouze záznamy na levé straně. Jde tedy o procento úspěšnosti pravidla vzhledem na všechny záznamy vyhovující premisám pravidla.

Tyto parametry mají podobu prahových hodnot, tj. uživatel zadá minimální hodnoty, které chce aby generovaná pravidla splňovala. Čím vyšší prahové hodnoty, tím je generování pravidel rychlejší.
Uvedené parametry lze počítat z počtu záznamů nebo z jejich vah. Jako váha záznamu se dá použít jeden jeho atribut, přičemž tento atribut může nebo nemusí být vyňat z budovaných pravidel.

Rozhodovací stromy (Decision Tree)

jsou struktury, které rozdělují zkoumaná data postupnou aplikací rozhodovacích kritérií. Každý uzel stromu reprezentuje jedno kritérium, podle kterého se data dělí do skupin. V listech stromu jsou hledané kategorie dat, odpovídající návěštím ve vzorových datech. V případě rozhodovacího stromu jsou přípustná pouze diskrétní návěští, tj. návěští nabývající pouze několika hodnot.
Pro vygenerování rozhodovacího stromu je v MineSetu třeba zadat

mód práce - zda si přejeme generovat klasifikátor nebo odhad chyb nebo obojí nebo jedno z toho. V případě generování klasifikátoru se tento vygenerovaný klasifikátor zobrazí pomocí vizualizéru, údaje o chybách se vypíší v okně Status
typ induktoru - v tomto případě Decision Tree
diskrétní návěští - atribut, pro který chceme data klsifikovat

Kromě těchto základních vstupů je možné zadat další parametry pomocí okna Further Inducer options .... Jsou to

omezení na výšku stromu - zadáním tohoto parametru donutíme algoritmus zastavit generování stromu na zadané hloubce. Toto omezení má vliv pouze na poslední generovanou úroveň stromu, předchozí úrovně jsou generovány stejně jako v případě bez omezení. Výhodou omezení je lepší orientace ve stromě, nevýhodou pak zmenšená přesnost stromu.
metoda dělení stromu - je implementováno několik metrik, definujících dělení otcovského uzlu stromu na potomky. Pro konkrétní zadání není možné stanovit, která metoda je nejlepší, autoři MineSetu doporučují vyzkoušet všechny metody a použít nejpřehlednější vygenerovaný strom nebo strom s nejmenším odhadem chyb.
dolní hranice pro váhu potomků - pomocí zadání této hranice stanovíme, kolik datových záznamů musí padnout alespoň do dvou potomků uzlu, aby tento uzel ještě bylo možné rozdělit. Toto je alternativní metoda omezení výšky stromu.
ořezání stromu (pruning) - po vygenerování stromu provádí MineSet ověřování statistické významnosti jednotlivých větví stromu. Najde-li větve, které je možné bez ztráty podstatných informací nahradit jedním uzlem, tak provede toto nahrazení. Je možné zadat ořezávací faktor (Pruning factor), doporučená hodnota je 0.7. Hodnota 0 znamená, že se strom nebude ořezávat vůbec, horní hranici faktor nemá. Ořezávání je pomalejší než omezení stromu na výšku nebo stanovení dolní hranice pro výhu potomků, jelikož je třeba nejdřív vygenerovat celý strom a pak teprve ho ořezat, ale je přesnější, protože jsou vybrány jen některé vhodné větve, zatímco předchozí kritéria jsou aplikována plošně.
povolit dělení typu jeden z - povolí rozdělení podle vybrané hodnoty jednoho atributu

Rozhodovací stromy s výběrem kritéria (Option Tree)

Jde o rozšíření rozhodovacích stromů o možnost zvolit jedno z více kritérií, podle kterých se v uzlech rozhodujeme. Tyto stromy jsou přesnější než klasické rozhodovací stromy, ale jejich generování je výrazně delší (10-15x) a jsou také hůře interpretovatelné. Kromě údajů zadávaných pro normální rozhodovací strom musíme pro Option Tree zadat navíc

maximální počet voleb pro kořenovou úroveň stromu
o kolik voleb klesá tento počet každou úroveň stromu

Ostatní vstupy mají stejný význam jako v případě rozhodovacího stromu. Většinou se používají stromy s volbami pouze v kořenové úrovni.

Regresní stromy

jsou rozhodovací stromy, jejichž návěští není diskrétní, ale spojité. Nelze proto použít normální rozhodovací strom, který je postaven na diskrétním návěští.
Parametry algoritmu jsou podobné jako u rozhodovacího stromu, jiná jsou kritéria pro dělení uzlů stromu a pro vizualizaci vygenerovaného stromu je potřeba použít jiný vizualizér.

Shlukování

je postup používaný pro analýzu neznámých dat. Nejde o určování hodnoty návěští na základě vzorové sady dat, analýza je prováděna vždy na celkové množině dat.
Algoritmus je založen na hledání shluků podobných datových záznamů, přičemž podobnost je možné měřit jako

euklidovskou - tj. jako odmocninu ze součtu druhých mocnin rozdílů jednotlivých atributů
manhattan - jako součet rozdílů jednotlivých atributů

Je možné zvolit jednoprůchodovou nebo víceprůchodovou variantu algoritmu. Při jednoprůchodové variantě je nutno zadat počet shluků, které algoritmus vytvoří, při víceprůchodové se zadá interval počtu výsledných shluků a parametr choice point, který udává pravděpodobnost volby více nebo méně shluků. Tato hodnota je mezi jedničkou a nulou, čím větší, tím se počet výsledných shluků bude blížit horní hranici.
Jeden z atributů je možné použít jako váhu záznamu, tento atribut je možné zahrnout do shlukování nebo vynechat. Kromě toho je možné též stanovit váhy jednotlivých atributů pro výpočet podobnosti (rozdíl více vážícího atributu více ovlivní podobnost záznamů než rozdíl méně vážícího atributu).
Jednotlivé vytvořené shluky jsou pak reprezentovány svými středovými záznamy, což jsou záznamy s průměrnými hodnotami atributů ze všech záznamů shluku. Pro jednotlivé shluky jsou uvedeny další statistické údaje, jako jsou odchylky a podobně.

Hledání důležitých atributů

Uživatel zadá vzorová data a návěští a algoritmus určí daný počet atirbutů, které nejlépe klasifikují daná data pro dané návěští. U každého nalezeného atributu vypíše algoritmus, jak dobře tento atribut dělí datovou množinu (purity). Lze použít také rozšířenou variantu algoritmu, která počítá kumulativní puritu pro vybranou skupinu atributů a pro ostatní atributy vypíše, jako puritu by dosáhl výběr atributů, kdyby k němu byl přidán příslušný atribut. Tímto postupem je možné optimalizovat výběr důležitých atributů.

Příklad použití (průzkum uživatelů Internetu)

Ke zpracování jsme dostali data z Průzkumu uživatelů internetu prováděného kdysi na VUT v Brně. Dotazník bohužel nebyl patrně příliš dobře navržen, nebo se počítalo se značnou prací při zpracování nasbíraných dat.

Předložená surová data měla 1008 záznamů a 54 sloupců, po vyčištění zůstalo 974 záznamů (odpovídajících odhadnutým typům sloupců) a 56 sloupců (čas připojení uvedený v jednom sloupci v agregovaném tvaru jsme rozděli na použitelnější části - den v týdnu, hodina ve dni a numericky seřaditelné datum). Po několika experimentech a s ohledem na kvalitu poskytnutých dat jsme pro další zpracování vybrali tyto sloupce (hodnoty reprezentované většinou číselníkem):

sex (pohlaví - muž, žena)
věk
stav (svobodný(á), ženatý/vdaná, rozvedený(á))
vzdělání (nejvyšší dosažené vzdělání - základní, středoškolské, středoškolské s maturitou, vysokoškolské technické, vysokoškolské ostatní)
xdoma (připojení k internetu z domu)
xpolitika (pravice, spíše pravice, střed, spíše levice, nevyplňuje)
xprijem (do 5 000, 5 000 - 10 000, 10 000 - 15 000, 15 000 - 20 000, 20 000 - 25 000, 25 000 - 30 000, 30 000 - 40 000, nad 40 000, nevyplňuji)
poczam (počet zaměstnanců
obor (vysoké skolství, věda a výzkum; střední a základní skolství; ostatní státní a veřejná správa; telekomunikace; informační technologie; informační služby; peněžní a finanční služby; obchodní činnost; marketing a reklama; média; stavebnictví a reality; doprava; energetika; zdravotnictví; strojírenství; ostatní výroba; ostatní služby)

K nalezení sloupců, které jsou důležité pro sledování určitého atributu lze použít funkci Color Importance popsanou výše. Dostali jsme např. tyto výsledky:

xprijem <= obor, vek, xpolitika (purity 39.34)
politika <= xprijem, obor, vek (purity 25.24)
xdoma <= obor, vek, sex (purity 32.74)
Pripojeni doma <= sex, vek (purity 25)

Při použití clusteringu na sloupce věk, xpolitika, xprijem jsme dostali tyto související kategorie:

politická orientace silně doprava, příjem nadprůměrný, věk 23 - 27
politická orientace doleva, příjem podprůměrný, věk 25 - 33

Clustering na sloupcích politika, xprijem, sex, věk, stav a vzdělání:

pravicova orientace, muž, příjem nadprůměrný, věk kolem 24 let, svobodný
žena
levicová orientace, muž, mírně podprůměrný příjem, věk kolem 28 let, nadprůměrné vzdělání

Závěrem

MineSet je velice kvalitně propracovaný a uživatelsky dost přívětivý systém, se kterým se dá snadno pracovat a vyhledávat závislosti v jinak těžko přehledných datech. Možná by mohl být více otevřený dalšímu rozšiřování či snadněji propojitelný s dalšími systémy, ale je třeba mít na paměti, že jde o komerční, nikoliv akademický systém. Rozhodně se dá, i díky velice dobré dokumentaci, použít pro snadnější orientaci v základech KDD. K dispozici jsou i animované komentované ukázky práce s MineSetem, které usnadní první seznámení a názorně předvedou, co vše MineSet umí - je ovšem pravda, že nad spletitými daty vypadají i velmi názorné vizualizační nástroje poněkud nepřehledně a je nutné investovat jistou námahu do skutečného vydolování znalostí ;-).

Systém pro získávání znalostí z dat a jejich vizualizaci