Informační systémy pro podporu rozhodování

Machine Learning, Artificial Intelligence, Data Mining

Informační systémy pro rozhodování

Informační systémy pro podporu rozhodování 5 Jan Žižka, Naděžda Chalupová Ústav informatiky PEF Mendelova universita v Brně

Machine Learning, Artificial Intelligence, Data Mining Jan Žižka – Teaching Supplements

Asociační pravidla Asociační pravidla (sdružovací pravidla, association rules) vyjadřují vztah mezi veličinami. Pomocí asociačních pravidel lze vyhledávat v databázi záznamy, které mají něco (dle pravidel) společného a tak vytvářet skupiny, shluky. Pravidlo má fromu X → Y, kde X je antecedent, předchůdce, který musí být splněn, aby platil konsekvent Y, důsledek. Typickým příkladem použití asociačních pravidel je např. analýza obsahu nákupního koše. Cílem této analýzy je najít vztah mezi zákazníkem nakoupenými druhy zboží.


Lidé nakupující X typicky nakupují také Y, a proto zákazník, který koupil X a nikoliv Y, je potenciální zákazník i pro Y. Jakmile najdeme takové zákazníky, můžeme na ně zaměřit tzv. křížový prodej (cross-selling). V databázi o nákupech (obsazích jednotlivých košů) se třeba typicky vyskytují slané brambůrky (X ) a pivo (Y ). Hledáme pak podmíněnou pravděpodobnost:

P (Y |X ), kde Y je zboží, které bychom rádi prodali za předpokladu, že bylo zakoupeno X . Tj. zákazníkovi, který má v koši pivo, ale nikoliv slané brambůrky, nabídneme ty brambůrky, pokud je pravděpodobnost P (X | Y ) dostatečně velká.


Řekněme, že disponibilní data dávají:

P (brambůrky | pivo) = 0.7. Pak je definováno pravidlo:

70 % zákazníků, kteří kupují pivo, kupují taky brambůrky. Cílem může být rozlišení zákazníků, popsaných v databázi určitými atributy (věk, pohlaví, stav, atd.):

P (Y | X , D ), kde D je množina atributů zákazníků.


Automatizované vyhledávání asociačních pravidel používá typicky tři míry: 1. Podpora (support) pravidla X → Y:

Support (X ,Y ) ≡ P (X ,Y ) = NX+Y / N tj. počet těch, kteří koupili X a Y vůči počtu všech. 2. Spolehlivost, důvěra (confidence) v pravidlo X → Y:

Confidence (X →Y ) ≡ P (Y |X ) = P (X ,Y ) / P (X ) tj. počet kupců X a Y vůči počtu kupců X .


3. Zvýšení (lift, interest) X → Y: Lift (X →Y ) = P (X ,Y ) / P (X )P (Y ) = P (Y |X ) / P (Y ) V praxi se používají zejména první dvě míry.

Confidence je podmíněná pravděpodobnost P (Y |X ), což se běžně počítá (ti, co koupili obojí vůči kupcům jen jednoho). Tato “důvěra” v pravidlo by se měla co nejvíc blížit 1 a být podstatně větší než P (Y ). Potom je pravidlo spolehlivé. Snaha je rovněž o maximalizaci podpory (support ), protože i když existuje velmi silná závislost mezi X a Y , pravidlo může být bezcenné, pokud je vytvořeno na malém vzorku zákazníků.


Support ukazuje statistickou významnost pravidla, zatímco Confidence jeho “sílu”. Minimální přijatelné hodnoty nastavuje firma nebo organizace, která data analyzuje. V databázi se pak vyhledávají (“dolují”) pravidla splňující nastavená kritéria. Jsou-li X a Y nezávislé, pak očekávaný Lift je blízký 1. Pokud ve vztahu P (Y |X ) /P (Y ) jsou obě pravděpodobnosti číselně odlišné, očekáváme mezi X a Y závislost. Pro Lift > 1 lze říci, že X zvyšuje pravděpodobnost Y . Pro Lift < 1 naopak X pravděpodobnost koupě Y snižuje.


V případě, že se hledají závislosti mezi více než dvěma položkami, lze uvedené vztahy zobecnit. Např. pro množinu prvků {X, Y, Z } lze hledat pravidlo pro míru závislosti X, Z → Y , tedy:

P (Y | X , Z ). Databáze obvykle obsahují velmi veliký soubor dat, takže vyhledávání pravidel v nich má vysokou výpočetní složitost. Cílem je minimalizovat počet průchodů databází. Existuje poměrně účinný algoritmus Apriori (z roku 1996), který postupuje ve dvou krocích:


1. Vyhledání těch položek v databázi, které mají vysokou četnost – neboli položek, které mají dostatečný support. 2. Převod položek do formy pravidel, která mají dostatečně vysokou confidence. Položky jsou rozděleny do dvojic coby antecedent X a konsekvent Y. Ad 1: k vyhledání položek s vysokou četností (bez nutnosti vyčíslit všechny podmnožiny položek) využívá Apriori fakt, že aby {X, Y, Z } měla velkou četnost (vysoký support ), všechny její podmnožiny {X, Y }, {X, Z } a {Y, Z } musí mít taky vysokou frekvenci. Znamená to, že stačí pro tříprvkové množiny testovat jen její dvouprvkové podmnožiny. Pokud některá dvouprvková má nízkou frekvenci, pak i její nadmnožina ji má nízkou.


Jinými slovy, pokud nějaká dvouprvková podmnožina má nízkou frekvenci, pak všechny její nadmnožiny ji mají taky nízkou a mohou být hned vyřazeny, aniž jsou všechny prozkoumávány. Dále se iterativně v každém kroku pro jednoprvkové podmnožiny (k = 1) generují dvouprvkové (k = 2), atd., tj. z k–prvkových (k + 1)–prvkové. Následovně se zkontroluje jejich support. Apriori ukládá frekventní položky do hašovací tabulky pro rychlý přímý přístup. S rostoucím k velmi rychle klesá počet kandidátů pro vytváření pravidel. Pokud má nejrozsáhlejší množina položek n členů, pak je zapotřebí n + 1 průchodů.


Ad 2: jakmile jsou nalezeny frekventní množiny s k prvky, jsou převedeny na pravidla rozdělením prvků tak, že do antecedentu přije k – 1 prvků a do konsekventu 1. Tento postup se zkouší pro všechny prvky z podmnožiny. Každé kandidátské pravidlo je ověřeno z hlediska confidence a pokud nesplňuje toto kritérium, je vyřazeno. Za povšimnutí stojí, že pro jednu množinu lze takto vytvořit mnoho pravidel s různými konsekventy. Dále lze zkoušet přesouvat z antecedentu jednotlivé prvky do konsekventu. Pokud takové pravidlo splňuje confidence, pak je použito. Výhoda pravidel s více prvky v konsekventu je v tom, že jsou specifičtější, nikoliv příliš obecná, takže jsou užitečnější.


Bayesovské sítě Bayesovské sítě (Bayesian networks) patří do skupiny algoritmů zvaných grafické modely. Tyto modely představují vzájemné působení (interakce) mezi proměnnými v grafické formě, visuálně. Jejich velkou výhodou je, že pro velký počet proměnných, popisujících zkoumané případy, umožňují rozložit problém na soubor lokálních výpočtů s malým počtem proměnných. Využívá se k tomu podmíněná nezávislost.


Pozn.: V anglické literatuře bývají bayesovské sítě uváděny také pod názvy belief networks, resp. probabilstic networks. Jsou to grafy složené z uzlů a hran mezi uzly. Každý uzel odpovídá jedné náhodné proměnné X a má hodnotu odpovídající pravděpodobnosti X, tj. P (X ). Pokud je hranou spojen uzel X s uzlem Y, tak to znamená, že X má přímý vliv na Y. Tento vliv X na Y je určen podmíněnou pravděpodobností P (Y |X ). Síť je orientovaný acyklický graf: déšť d P(d)=0.4

mokrý trávník mt P(mt|d)=0.9 P(mt|¬d)=0.2

Model situace, kdy déšť může (nebo nemusí) být příčinou mokrého trávníku.


Uvedené tři hodnoty zcela popisují rozložení P (d, mt ). Pokud platí

P (d ) = 0.4, pak P (¬d ) = 0.6, a podobně (doplňky do 1.0, viz předchozí slide) pro

P (¬mt |d ) = 0.1 a P (¬mt |¬d ) = 0.8. Vztah lze zapsat jako

P (d |mt ) = P (d )P (mt |d ).


Pravděpodobnost toho, že trávník bude mokrý (kvůli dešti nebo kvůli jiné příčině) se vypočítá jako součet možných hodnot, které “rodičovský” uzel déšť může nabýt:

P (mt ) = P (mt |d )P (d ) + P (mt |¬d )P (¬d ) = = 0.9·0.4 + 0.2·0.6 = 0.48. Pravděpodobnost 0.48, že je mokrý trávník, znamená, že nevíme, zda pršelo nebo nepršelo. déšť d P(d)=0.4

mokrý trávník mt P(mt|d)=0.9 P(mt|¬d)=0.2

Uvedený graf zobrazující vztah mezi deštěm a mokrým trávníkem je tzv. kauzální graf.


Příklad složitější situace (pochází od Dr. Judea Pearl, UCLA): Judea si pořídil nový alarm proti zlodějům. Alarm se rozezvoní při vloupání, ale někdy i při mírném zemětřesení (Judea žije v Los Angeles, CA). Judea má dva sousedy: John a Mary. John skoro vždy zavolá, když slyší alarm, ale někdy, když mu zazvoní telefon, splete si to s alarmem a volá (zbytečně) taky. Mary ráda poslouchá nahlas hudbu, také někdy alarm úplně přeslechne, nebo naopak jí z hlasité hudby zvoní v uších. Pravděpodobnost vloupání zloděje do Judeova bytu se dá spočítat, pokud existují podklady (pravděpodobnosti), kdo v jakém případě volal nebo nevolal.


Jedná se o typický příklad zpracování nejistoty. Například: 0.001 0.002 0.950 0.940 0.290 0.001 0.900 0.050 0.700 0.010

je pravděpodobnost loupeže (nepodmíněná), je pravděpodobnost zemětřesení (nepodmíněná), spuštění alarmu při loupeži a zároveň zemětřesení, spuštění alarmu při vloupání, není zemětřesení, spuštění alarmu při zemětřesení, není vloupání, spuštění alarmu při ani zemětřesení, ani vloupání, John zavolá, když zvoní alarm, John zavolá, když mu zvoní telefon (a alarm nezvoní), Mary zavolá, když nepřeslechne (nepouští si hudbu), a Mary zavolá, i když alarm nezvoní (zvoní jí v uších).

Jaká je tedy pravděpodobnost, že opravdu došlo ke vloupání k Judeovi?


Bayesovská síť, která odpovídá popsanému případu, je na obrázku. To, zda zavolá John nebo Mary, závisí pouze na podmínce, zda byl spuštěn alarm. Zvonění alarmu závisí na loupeži nebo zemětřesení. Nepředpokládá se, že John a Mary přímo vidí loupež, že detekují zemětřesení, nebo že se spolu radí před zatelefonováním Judeovi.

loupež

zemětřesení alarm

volá John

volá Mary


Pro uvedený případ lze počítat řadu různých pravděpodobností. Například pravděpodobnost, že alarm a zazvonil, aniž došlo ke vloupání b či zemětřesení e, a zároveň zavolala Mary m i John j.

P (j, m, a,¬b,¬e ) = = P (j |a )P (m |a )P (a |¬b AND ¬e )P (¬b )P (¬e ) = = 0.9·0.7·0.001·0.999·0.998 = 0.000628. Pozn.: P (¬x ) = 1.0 – P (x ).

Informační systémy pro podporu rozhodování

Recommend Documents