Asociační pravidla. Informační a komunikační technologie ve zdravotnictví. Biomedical Data Processing G r o u p

Asociační pravidla Informační a komunikační technologie ve zdravotnictví

Biomedical Data Processing G r o u p

Definice pojmů Stavový prostor S  je množina uzlů(stavů), kde cílem je najít stav splňující danou podmínku g.

Formálně je problém zadán trojicí (s0,g,O):  s0 je počáteční stav  g je cílová podmínka (tj. hledaný stav s splňuje g(s))  O je množina operátorů měnících stav  Stavový prostor je potom definován rekurzivně:  s0S, je-li sS, oO a o(s) je definováno potom o(s)  o(s) je potomek uzlu s

S

Prohledávání stavového prostoru:  hledá se stav daných vlastností Biomedical Data Processing G r o u p

Prohledávání stavového prostoru - do šířky Breadth-First Search – jde po patrech  seznam q se chová jako fronta  Úplný algoritmus  pokud nejsou nekonečné cesty nebo je lze detekovat.

 Složitost nalezení cílového uzlu v hloubce d:  nalezení cílového uzlu v hloubce d při b potomcích každého uzlu: čas O(bd), pamět O(bd)


Prohledávání stavového prostoru - do šířky

A B

E

C

D

F G H I

J

K L

1. OPEN(A), CLOSE(0) 2. OPEN(B,C,D), CLOSE(A) 3. OPEN(C,D,E,F,G), CLOSE(A,B) 4. OPEN(D,E,F,G,H,I), CLOSE(A,B,C) 5. OPEN(E,F,G,H,I,J,K,L), CLOSE(A,B,C,D)


Prohledávání stavového prostoru - do hloubky Depth-First Search (backtracking)  jde zvoleným směrem, návrat v případě neúspěchu

seznam q se chová jako zásobník Úplný algoritmus  pokud nejsou nekonečné cesty nebo je lze detekovat.

Složitost nalezení cílového uzlu v hloubce d:  čas záleží na směru (může prohledat až celý stavový prostor, ale také může jít přímo)  paměť O(d)


Prohledávání stavového prostoru - do hloubky A B

E

C

D

F G H I

J

K L

M N 1. OPEN(A), CLOSE(0) 2. OPEN(B,C,D), CLOSE(A) 3. OPEN(E,F,G,C,D), CLOSE(A,B) 4. OPEN(M,N,F,G,C,D), CLOSE(A,B,E) 5. OPEN(N,F,G,C,D), CLOSE(A,B,E,M) Biomedical Data Processing G r o u p

Prohledávání stavového prostoru - Gradientní algoritmus Hill-climbing Expanduje ten uzel, který byl vyhodnocen jako nejlepší Vyhodnocuj jeho následovníky Záleží jak hodnotící funkce postihuje vlastnosti charakter úlohy – kvalita použitých heuristik


Definice pojmů Dolování v relačních datech Relační tabulka  R=(H, RB)  kde H je záhlaví relační tabulky a B je její tělo

Tělo relační tabulky  množina n-tic řádků RB(t) = {r1, r2, ..., rm(t)},

Doména atributu  množina skalárních hodnot téhož typu, jichž může atribut nabýt


Rozhodovací pravidla Aproximace diskrétních cílových veličin Aproximační fce je ve tvaru množiny rozhodovacích pravidel Jetliže <podmínka> pak  selektor – jednoduchý test hondoty atributu (=,<,>,≠)  podmínka – konjunkce selektorů

Pravidla mají stejnou expresivitu jako stromy  stromy – rozděl a panuj – dělení, čistě shora dolů  pravidla – odděl a panuj – pokrytí, konstrukce oběma směry


Rozhodovací pravidla AQ algoritmus (Michalski) for each class Ci Ei = Pi Ni (PixNi – positivní x negativní příklady) pravidloBase(Ci) = empty repeat {find-set-of-rules} - find one rule R covering some positive example and no negative one - add R to pravidlaBase(Ci) - delete from Pi all positive examples covered by R until Pi is empty

Podstatná je find-one-rule procedura Jedná se o proces generalizace – přístup zdola-nahoru Biomedical Data Processing G r o u p

Rozhodovací pravidla find-one-rule  zvol náhodně pozitivní příklad (zrno)  generuj všechny maximální generalizace zrna  Pokrývá co nejvíce pozitivních příkladů  Nebokrývá žádný negativní příklad

 vyber nejlepší generalizaci (preferenční heuristika)

#

a

b

c

v

1

x

r

m

+

2

y

r

n

+

3

y

s

n

+

4

x

s

m

-

5

z

t

n

-

6

z

r

n

-

zrno 1: if (a1=y)^(b=s) ^(c=n) then + g1 ~ if (a=y) then + zrno 2: if (a=x) ^(b=r) ^(c=m) then + g1 ~ if (a=x) ^(b=r) then + g2 ~ if (b=r) ^(c=m) then + Biomedical Data Processing G r o u p

Rozhodovací pravidla AQ algoritmus  závisí na volbě zrna  není vhodný pro domény s chybami/šumem

CN2  Clark a Niblett 1989  přístup shora dolů – tzv. paprskové prohledávání  může generovat neuspořádané množiny pravidel  nebo uspořádané množiny pravidel – rozhodovací seznami


Asociační pravidla Definice:  Snaha zjistit mezi položkami takový vztah, že přítomnost jedné nebo více položek implikuje přítomnost jiných položek v téže transakci – pravděpodobnostní tvrzení o spoluvýskytu událostí v datech

A B

kde A,B jsou vzájemně disjunktní množiny položek množiny I

Charakter logické implikace  if then <sukcedent>  Ant, Suc jsou konjunkce selektorů

Generalizovaná asociační pravidla  význam: Ant a Suc jsou v asociaci dle metriky definované nad čtyřpolní tabulkou


Asociační pravidla Asociační vs. rozhodovací pravidla  deskripce vs. klasifikace (predikce)  Sukcedent může obsahovat libovolné atributy, nejen třídu  if teplota=nízká the vlhkost=normální  if obloha=proměnlivo then třída=ano

Asociační pravidla neřeší problém pokrytí  některých příkladů se nemusí dotknout žádné pravidlo  jde o nalezení zajímavých společných výskytů hodnot

Rozhodovací pravidla  aproximace diskrétní cílové funkce


Asociační pravidla  Pojmy:  Položky: I = {I1,I2,…,Im}  Transakce: D = {t1,t2,…,tn}, tj  I  případy, objekty

 Množiny položek: {Ii1,Ii2,…,Iik}  I  konjunkce selektorů, analogie podmínky

 Podpora množiny položek: (relativní četnost transakcí obsahujících danou množinu položek)  Frekventovaná množina položek: četnost výskytů dané množiny položek je vyšší než zvolený práh  Podpora  Spolehlivost


Asociační pravidla Motivace získávání asociačních pravidel  Úloha „Analýza nákupního košíku“  Snažíme se zjistit závislosti mezi jednotlivými prodejními položkami (př. asoc. pravidla: „pokud si zákazník kupuje mléko, zpravidla si koupí chleba“)

 Využití výsledků pro rozmisťování zboží, vytváření nabídkových katalogů, marketingové rozhodování apod.


Asociační pravidla Analýza nákupního košíku Transakce

Věci

t1

chleba, aspik, máslo

t2

chleba, máslo

t3

chleba, mléko, máslo

t4

pivo, chleba

t5

pivo, mléko

Cíl: nalézt položky kupované společně chleba  máslo ; podpora = 60%, spolehlivost = 75 %


Asociační pravidla Metriky pro asociační pravidla

Suc

non(Suc)



Ant

a

b

r = a+b

non(Ant)

c

d

s = c+d



k = a+c

l = b+d

n = a+b+c+d

podpora 

a n

a spolehlivost  r a pokrytí  k

(a  d ) n 1 a d   příčinná spolehlivost    2 ab bd  příčinná podpora 


Asociační pravidla Metriky pro asociační pravidla – WEKA  SPOLEHLIVOST (CONFIDENCE)  podíl příkladů pokrytých LHS které jsou současně pokryté i RHS

 ZDVIH (LIFT)  Stupeň o nějž pravidlo zvyšuje přesnost defaultní predikce své RHS

a n r k  PÁKA (LEVERAGE) lift 

 Podíl příkladů, které jsou pravidlem pokryté dostatečně nad rámec příkladů pokrytých za předpokladu nezávislosti LHS a RHS

leverage 

1 n  (a  r  k n)

 PŘESVĚDČIVOST (CONVICTION)  Podobná zdvihu, ale uvažuje příklady nehokryté RHS pravidla – musí pracovat s převráceným poměrem četností

c o n v ic tio n 

r l b n Biomedical Data Processing G r o u p

Asociační pravidla  Příklady metrik 450 50

500

10

1

450 50

500

90

899 989

11

450 50 50

500

450 500

900 100 1000

100 900 1000

500 500 1000

podpora  0.45 spolehlivost  0.9

podpora  0.01 spolehlivost  0.91 zdvih  9.09

podpora  0.45 spolehlivost  0.9

zdvih  1 páka  0 přesvědčivost  1

páka  0.01 přesvědčivost  9.9

Ant a Suc jsou nezávislé

závislost, ale může být náhodná

zdvih  1.8 páka  0.2 přesvědčivost  5 silná závislost Biomedical Data Processing G r o u p

Nalezení asociačních pravidel Silná pravidla  pravidla s vysokou (předem určenou) hodnotou a spolehlivostí

Cíl  nalézt taková pravidla, která jsou „silná“

Dolování asociačních pravidel  nalezení silných pravidel


Nalezení asociačních pravidel Dva kroky procesu nalezení asociačních pravidel:  Generování frekventovaných vzorů  nalezení predikátů, které mají podporu vyšší, než je zadaná minimální podpora  nalezení silných množin

 Generování asociačních pravidel  vygenerování asoc. pravidel s využitím silných množin  odstranění pravidel, jejichž spolehlivost (confidence) nedosahuje předem určené minimální hodnoty (minconf)


Nalezení asociačních pravidel Definice frekventovaného vzoru  fp je frekventovaný vzor, konjunkce predikátů tvar a1 ^ a2 ^ … ^ an  jednotlivé predikáty odpovídají hodnotám určitého počtu řádků, v případě kvantitativních atributů musí být hodnota uvnitř určitého intervalu  fp je množina frekventovaných vzorů  s(x) je podpora

FP = {fp | s(fp) ≥ minsup}


Nalezení asociačních pravidel Definice silných asociačních pravidel  ar … asociační pravidlo tvaru A  B, kde A, B jsou konjunkce predikátů tvaru a1 ^ a2 ^ … ^ an  c(ar) … spolehlivost pravidla  s(ar)… podpora pravidla  Poté je množina silných pravidel AR definována jako:

AR = {ar | c(ar) ≥ minconf ^s(ar) ≥ minsup}


Nalezení asociačních pravidel Faktory, určující výkon dolovacího algoritmu:  Efektivita generování frekventovaných vzorů  Časová a paměťová náročnost generování frekventovaných

vzorů

 Druhý krok (generování asociačních pravidel) je jednoduchý a nemá v konečném důsledku větší vliv na výkon dolovacího algoritmu


Nalezení asociačních pravidel Algoritmus APRIORI  algoritmus „prochází“ postupně databázi a počítá podporu pro kandidáty  v každém kroku generování tzv. kandidátů a poté kontrola

minimální podpory.

 v dalším kroku vznik kandidátů o velikosti o jednu větší, než v předchozím kroku atd.  konec při nenalezení kandidátů dané velikosti  funkce AprioriGen generuje všechny možné k množiny (kandidáty) z frekventovaných množin  poté vylučuje z výběru ty množiny, jejichž některá podmnožina není frekventovaná („podpora k-množiny nemůže být větší, než podpora její podmnožiny“)


Apriori algoritmus Výpočet podpory pro všechny prvky z množiny C1 for (k=2;;k++) begin

Lk-1={ kandidáti z Ck-1, kteří mají podporu vyšší než minimální}

if (množina Lk-1 je prázdná) break

Ck = AprioriGen(Lk-1); for each (transakce t) begin

Ct = subset(Ck, t); for each (kandidáti c є Ct) zvyš o 1 podporu kandidáta c end end Biomedical Data Processing G r o u p

Apriori algoritmus


Další typy asociačních pravidel  Víceúrovňová asociační pravidla  nad položkami v transakcích je definována konceptuální hierarchie, která je sdružuje do tzv. konceptů (jablko, pomeranč = ovoce)

 Asociační pravidla založená na omezeních  Zobecněná asociační pravidla


Děkuji za pozornost


Asociační pravidla. Informační a komunikační technologie ve zdravotnictví. Biomedical Data Processing G r o u p

Recommend Documents