Vytěžování znalostí z dat

Vytěžování znalostí z dat Pavel Kordík, Jan Motl Department of Computer Systems Faculty of Information Technology Czech Technical University in Prague

Přednáška 13: Web mining BI-VZD, 09/2011 MI-POA

Evropský sociální fond Praha & EU: Investujeme do vaší budoucnosti

Pavel Kordík, Jan Motl (ČVUT FIT)

Vytěžování znalostí z dat

BI-VZD, 2012, Přednáška 13

1/14

Rozdělení

Web Mining • Web mining se nechá rozdělit do tří typů:

Obsahu

• Mining textů, obrázků a videa pro vyhledávače • Například kdysi vyhledávač AltaVista

Používání

• Co lidi vyhledávají (keywords)? • Na co klikají?

Struktury

• Pomocí teorie grafů se hledají vzory • Například PageRank od Google




2/14

Text mining

Text mining „Tak nám zabili Ferdinanda,” řekla posluhovačka panu Švejkovi, který opustiv před léty vojenskou službu, když byl definitivně prohlášen vojenskou lékařskou komisí za blba, živil se prodejem psů, ošklivých nečistokrevných oblud, kterým padělal rodokmeny. JAROSLAV HAŠEK: Osudy dobrého vojáka Švejka za Světové války




3/14

Text mining

Tokenizace • Rozdělení textu na jednotlivá slova. „Tak nám zabili Ferdinanda,” řekla posluhovačka panu Švejkovi, který … Tak | nám | zabili | Ferdinanda | řekla posluhovačka | panu | Švejkovi | který …

• Součástí tokenizace mohou být interpunkční znamínka; nebo taky ne.




4/14

Text mining

Převod na malá písmenka • Pro vyvarování se duplicitních záznamů Tak | nám | zabili | Ferdinanda | řekla posluhovačka | panu | Švejkovi | který … tak | nám | zabili | Ferdinanda | řekla posluhovačka | panu | Švejkovi | který … • Jak ale rozpoznat vlastní jména…




5/14

Text mining

Stop slova • Stop slova (stop words) jsou pojmy, které nenesou samy o sobě žádný význam, přitom jsou velmi častá. Proto je užitečné je odfiltrovat pro ušetření paměti a zrychlení dalšího zpracování. V češtině jde především o předložky, spojky a některá další slova.




6/14

Text mining

n-Gramy • N-Gram je sekvence n slov jdoucích po sobě.




7/14

Text mining

Lemmatizace, stemming • Lemmatizace nalezne ke každému slovu jeho základní tvar (lemma, základní tvar) • Stemming ořízne slova o předpony a přípony s koncovkami (stem, kořen slova) Slovo/a

Lemma

Stem

arcivévoda, arcivévodu

vévoda

vévod

zabili

zabít

zab

vojenskou, vojenská

vojenský

vojensk




8/14

Asociativní pravidla

Asociativní pravidla V americkém řetězci Walmart bylo zjištěno, že muži, kteří nakupují plenky, také často nakupují pivo. Na základě toho bylo pivo přesunuto vedle plenek, aby se vazba zesílila. Zisky z prodeje piva potom šli raketově nahoru. Data miningová legenda, 1992




9/14


Asociativní pravidla TransaNákup-id

Koupeno

10

A, B, C

20

A, C

30

A, D

40

B, E, F

Zákazník koupí obé

Zákazník koupí pivo


• Položky X={x1, …, xk} • Najdi pravidlo XY s alespoň minimální jistotou a podporou – podpora, s, je pravděpodobnost, že nákup obsahuje X∪Y – jistota, c, je podmíněná pravděpodobnost, že nákup mající X má také Y

Zákazník koupí plenky

min_podpora = 50%, min_jistota = 50%: A C (50%, 66,7%) C A (50%, 100%)



10/14


Asociativní pravidlo - příklad Nákup-id

Koupeno

10

A, B, C

20

A, C

30

A, D

40

B, E, F

min_podpora = 50%, min_jistota = 50%

Pro pravidlo A ⇒ C: podpora = podpora({A}∪{C}) = 50% jistota = podpora({A}∪{C})/podp ora({A}) = 66,6% Pavel Kordík, Jan Motl (ČVUT FIT)


Vzor

Podpora

{A}

75%

{B}

50%

{C}

50%

{A, C}

50%


11/14


Apriori: Výběr kandidátů • Jakákoliv podmnožina frekventované množiny musí být frekventovaná o If {pivo, plenky, oříšky} je frekventované, potom {pivo, plenky} je taky frekventované o Každý nákup obsahující {pivo, plenky, oříšky} také obsahuje {pivo, plenky}

• Apriori prořezávání: Pokud je množina nefrekventovaná, její nadmnožina bude taky nefrekventovaná. Nadmnožinu potom nemusíme testovat. • Postup: o vytvoř kandidáty o (k+1) položkách z častých nákupů o k položkách o ověř proti databázi

• Studie ukazují, že algoritmus je rychlý a škálovatelný.




12/14


Důležité detaily Apriori • Jak vygenerovat kandidáty? o Krok 1: křížové spojení Lk o Krok 2: prořezávání

• Jak spočítat podporu kandidátů? • Příklad generování kandidátů o L3={abc, abd, acd, ace, bcd} o Křížové spojení: L3×L3 • abcd z abc a abd • acde z acd a ace

o Prořezání: • acde je odebráno, protože ade není v L3

o C4={abcd}




13/14

Odkazy

Odkazy • http://www.youtube.com/watch?v=EjD2M4r4m BM&feature=related




14/14

Vytěžování znalostí z dat

Recommend Documents