Získávání znalostí z databází
Alois Kužela
Obsah související pojmy – datové sklady, … získávání znalostí asocia ní pravidla
2/37
Úvod získávání znalostí z dat, dolování (z) dat, data mining proces netriviálního objevování implicitních, dop edu neznámých a potenciáln použitelných znalostí v datech související pojmy: –
Datové sklady, datové trhy „Topíme se v datech, ale trpíme nedostatkem znalosti“.
– 3/37
OLAP
Pro data mining? roste objem dat uložený v databázích – –
vznikají rychlejší, levn jší a pokro ilejší databázové technologie neustále generujeme nová data obchodní a bankovní transakce výzkum, astronomie, biologie, …
z rozsáhlých dat se obtížn vyvozují záv ry dát uloženým dat m význam 4/37
Data, informace, znalosti? data (údaje) – –
„surové“ hodnoty, fakta 25, erná
informace – –
data, která mají smysl a p ínos pr m rný plat zákazník v tisících, nejprodávan jší barva telefonu
znalosti (poznatky) – –
5/37
informace + objevování, analýzy, … zákazník si pravd podobn koupí i notebook
Definice informace (Oracle) máme údaje víme, že máme údaje víme, kde tyto údaje máme máme k nim p ístup zdroji údaj m žeme d v ovat
6/37
Vztah údaje – informace – znalosti
Moudrost znalosti informace údaje
Business Inteligence – proces transformace údaj na informace a p evod informací na poznatky prost ednictvím objevování. 7/37
Data Mining a Business Intelligence Rostoucí potenciál podpory rozhodování Rozhodování Prezentace dat
Vizualiza ní techniky
Koncový uživatel Obchodní analytik
Dolování dat
Objevování informace
Zkoumání dat
analýza, dotazování, sestavy
Datový analytik
Datové sklady / datová tržišt OLAP techniky
Datové zdroje
Papír, soubory, databázové systémy, OLTP systémy
8/37
DBA
Co je získávání znalostí z databází? extrakce zajímavých model dat a vzor z velkých objem dat hledané modely jsou: – – – – – 9/37
netriviální skryté d íve neznámé platné potenciáln užite né
P íklady aplikací pr mysl (diagnostika poruch, predikce spot eby, …) obchod (marketing, bankovnictví) v da (charakterizace karcinogenních látek, hypotézy, …) medicína (mapování lidského genomu)
10/37
Proces získávání znalostí z dat Stanovení cíl – – – – –
Jaký typ znalosti chceme nalézt? Nad jakými daty budeme proces získávání znalostí provád t? Je problém ešitelný? Budou získané výsledky užite né v praxi? V jakém tvaru a form chceme výsledky získávání znalostí zobrazit?
Výb r zdroj dat 11/37
Proces získávání znalostí z dat 1) 2) 3) 4) 5) 6) 7) 12/37
išt ní dat integrace dat výb r dat transformace dat dolování dat hodnocení model a vzor prezentace znalostí
p edzpracování dat
P edzpracování dat Je tato fáze nezbytná? – – –
Objemné databáze – je pot eba vybrat relevantní data Nesprávná, nekonzistentní data, chyb jící hodnoty Zvýší efektivitu a usnadní proces získávání znalostí
nejpracn jší ást celého procesu asto se provádí opakovan 13/37
P edzpracování dat p íprava dat – – – – – –
14/37
selekce atribut – výb r relevantních atribut išt ní dat získávání odvozených atribut p evod typ dat transformace dat do jedné velké tabulky formátování pro jednotlivé modelovací techniky
Dolování dat Aplikace zvoleného algoritmu na p edzpracovaná data, dle typu znalosti a dat Typy znalostí – – – –
15/37
Asocia ní pravidla - hledání vazeb mezi objekty Shlukování - seskupování podobných objekt Klasifikace - p i azení t ídy objektu Predikce - p edpov chování objektu v ase
Vyhodnocení zhodnocení dosažených výsledk zhodnocení výsledk z pohledu zadání asto návrat zp t na za átek celého procesu a stanovení nových cíl (úprava zadaní) vizualizace
16/37
Typy dolovacích úloh prediktivní: – –
regrese klasifikace
deskriptivní: – – –
17/37
shlukování / sdružování podobností asocia ní pravidla a jejich varianty detekce odchylek
Asocia ní pravidla hledání zajímavých asociací i korelací ve velkém množství dat p vodn pro transak ní data –
obchodní transakce
analýza nákupního košíku –
18/37
podpora rozhodování
Základní pojmy pravidla tvaru ⊂ T, A ∩
!
19/37
∅
!
"
D ležité metriky udávají významnost nalezených pravidel # $% #
% ∪
$
spolehlivost – –
20/37
c (confidence) kolik % ze všech transakcí tvaru A "
&
Metriky Zápis s využitím pravd podobnosti s(A c(A
21/37
% '# ∪ % % '# ( %
P íklad analýzy košíku získané pravidlo o nákupu položek po íta
)*+
,
-$
./$
význam: – –
8 % všech nákup obsahovalo ob položky p i koupi po íta e se kupoval v 60 % také OS
záv ry
22/37
–
60 % poctivých uživatel OS Windows
–
návrh akcí, katalog na základ t chto informací
Další pojmy silné asocia ní pravidlo –
má podporu a spolehlivost vyšší než uživatelem zadaná hodnota
frekventovaná množina –
23/37
množina položek, která má podporu vyšší než minimální hodnota
Hledání asocia ních pravidel výpo et frekventovaných množin – –
na základ minimální podpory asov náro n jší krok
generování silných asocia ních pravidel z frekventovaných množin –
24/37
na základ minimální spolehlivosti
Apriori Transak ní databáze
0
"
princip postupného generování kandidát na frekventované množiny za íná se u množin velikosti 1 – –
25/37
spojovací fáze: spojení dvou stejn velkých množin, které se liší pouze v jednom prvku vylu ovací fáze: odstran ní množin, jejichž libovolná podmnožina není frekventovaná
P íklad smin = 22 % (2 výskyty)
26/37
TID
Položky
T100 T200 T300 T400 T500 T600 T700 T800 T900
I1, I2, I5 I2, I4 I2, I3 I1, I2, I4 I1, I3 I2, I3 I1, I3 I1, I2, I3, I5 I1, I2, I3
P íklad – 1. iterace Ci
Po et
L1
Po et
{I1} {I2} {I3} {I4} {I5}
6 7 6 2 2
{I1} {I2} {I3} {I4} {I5}
6 7 6 2 2
zjistíme všechny kandidáty 27/37
porovnáme s min. podporou
P íklad – 2. iterace
28/37
C2
Po et
L2
Po et
{I1, I2} {I1, I3} {I1, I4} {I1, I5} {I2, I3} {I2, I4} …
4 4 1 2 4 2 …
{I1, I2} {I1, I3} {I1, I5} {I2, I3} {I2, I4} {I2, I5}
4 4 2 4 2 2
generujeme kandidáty C1 + výpo et podpory
porovnáme s min. podporou
P íklad – 3. iterace C3
Po et
L3
Po et
{I1, I2, I3} {I1, I2, I5} {I1, I3, I5} {I2, I3, I4} {I2, I3, I5} {I2, I4, I5}
2 2 1 0 1 0
{I1, I2, i3} {I1, I2, i5}
2 2
generujeme kandidáty C3 + výpo et podpory 29/37
porovnáme s min. podporou
P íklad – 4. iterace C4
Po et
L4
{I1, I2, i3, I5}
1
∅
generujeme kandidáty C4 + výpo et podpory
30/37
porovnáme s min. podporou
Po et
Generování asocia ních pravidel spolehlivo st ( A – –
31/37
podpora ( A ∪ B ) B ) = P ( B A) = podpora ( A)
pro každou frekventovanou množinu l, generuj všechny její neprázdné podmnožiny pro každou podmnožinu x, generuj pravidlo x # 1 % 2 3 !
P íklad Frekventovaná množina {I1, I2, I5} Neprázdné podmnožiny: {I1, I2}, {I1, I5}, {I2, I5}, {I1}, {I2}, {I5} I1, I2, I5 T100 Vygenerovaná pravidla: I2, I4 T200 – – – – – –
32/37
I1 ∧ I2 I5; c = 2/4 = 50 % I2 ∧ I5 I1; c = 2/2 = 100 % I2 I1 ∧ I5; c = 2/7 = 29 % I1 ∧ I5 I2; c = 2/2 = 100 % I1 I2 ∧ I5; c = 2/6 = 33 % I5 I1 ∧ I2; c = 2/2 = 100 %
T300 T400 T500 T600 T700 T800 T900
I2, I3 I1, I2, I4 I1, I3 I2, I3 I1, I3 I1, I2, I3, I5 I1, I2, I3
Zvýšení efektivity algoritmu hašování redukce transakcí vzorkování odstranit generování kandidát –
…
33/37
metoda vzr stu generovaných množin
Další algoritmy hledání víceúrov ových asocia ních pravidel multidimenzionální asocia ní pravidla asocia ní pravidla založená na omezeních …
34/37
Další využití data miningu sekven ní vzory –
podobné asocia ím pravidl m, závisí ale na ase
klasifikace –
rozd lení dat do kone ného po tu t íd na základ vlastností
predikce –
35/37
p edpovídání hodnoty dat na základ znalostí získaných z již známých dat
Existující ešení MS SQL Server Oracle SAS Bee Bizgres
36/37
Využití data miningu Analýza nákupního košíku –
Nalezení závislostí mezi r zným zbožím, které si zákazník koupí
len ní (segmentace) zákazník –
Cíl: porozum t zákazníkovi a jeho chování
Management rizik –
Odhalení rizikových zákazník (nap . u pojiš oven)
Detekce podvod –
Nap . hledání extrémních útrat na kreditní kart
Odhalování zlo innosti –
Odhalení potenciálních neplati
Predikce požadavk –
37/37
P edpov
p j ek…
zájmu zákazník o r zné zboží…