Adatbányászat. Data Mining: Concepts and Techniques (3 rd ed.)

Adatbányászat Data Mining: Concepts and Techniques (3rd ed.) Jiawei Han, Micheline Kamber, and Jian Pei University of Illinois at Urbana-Champaign & Simon Fraser University ©2009 Han, Kamber & Pei. All rights reserved. Adattárházak és adatbányászat

1

Mirıl szól a kurzus?

Bevezetés az adattárházak és adatbányászat technológiákba

Bevezetés Ismerjük meg az adatainkat! Az adatok elıfeldolgozása (Data Preprocessing) Bevezetés az adattárházak és OLAP technológiákba (Data Warehouse and OLAP Technology) Adatkockák használata (Data Cube Technology ) Gyakori minták és asszociációk keresése (Mining Frequent Patterns & Association) Osztályozás (Classification) Klaszterezés (Cluster Analysis) Adattárházak és adatbányászat

2

A könyvben olvasható alkalmazási területek, haladó témák

Adatfolyamok, idısorok, szekvenciák adatbányászata

Gráfok, közösségi hálók, multirelációk adatbányászata

Objektumok, téridı-adatok, multimedia objektumok, szövegek, weben található információ adatbányászata Alkalmazások és aktuális irányzatok az adatbányászatban

Üzleti adatok bányászata

Biológiai adatok bányászata

Vizuális adatbányászat (képek, videók)

Adatvédelem-ırzı adatbányászat

Adattárházak és adatbányászat

3

A könyv szerzıjének oldala: http://www.cs.uiuc.edu/~hanj/


4

Bevezetés

Miért kell adatbányászat?

Mi az adatbányászat?

Az adatbányászat különbözı aspektusai

Adatbányászati funkciók: Milyen mintákat keressünk?

Milyen adatokban bányászunk?

Idıindexes és rendezett adatok: Szekvenciális minták, trendek keresése, fejlıdési minták keresése

Struktúrák és hálózatok elemzése

A tudás értéke

Adatbányászati alkalmazások

Új irányok az adatbányászatban

Az adatbányászat története dióhéjban


5


Adatrobbanás zajlik: terabájtokról áttérünk a petabájtokra

Nagy adatgyőjtemények keletkeznek és érhetık el

Automatikus adatgyőjtı mérıeszközök, adatbázisrendszerek, Web, közösségi hálók, számítógépes ügyfélszolgálatok

Nagy mennyiségő nyers adat keletkezik a következı területeken

Üzleti élet: Web, e-kereskedelem, pénzügyi tranzakciók, tızsde

Tudomány: távérzékelı berendezések, bioinformatika, tudományos szimulációk

Közösségi és mindennapos élet: Facebook, hírek, digitális kamerák, YouTube

Ellep bennünket a rengeteg adat, bár mi valójában inkább tudásra vágyunk!

A szükség szüli az új technológiát: Az adatbányászat a nagy mennyiségő adatok automatikus elemzése Adattárházak és adatbányászat

6

A tudomány fejlıdése

1600 elıtt, empirikus (tapasztaláson alapuló) tudomány

1600-1950, elméleti tudomány

1950-1990, számítógép-tudomány

Minden terület kifejlesztette a saját elméleti megalapozását. Az elméleti modellek kísérletezésre ösztönöznek, illetve általános érvényő tudást fogalmaznak meg. A legtöbb terület egy számítógépes részterületet is kifejlesztett (kísérleti, elméleti, számítógépes fizika vagy empirikus, elméleti nyelvészet, illetve formális nyelvek.) A számítógép-tudományt a szimulációk iránti igény hozta létre, mivel sok esetben a bonyolult matematikai modelleknek nincs zárt formulával megadható megoldása.

1990, adattudomány

A tudományos eszközök, szimulációk adatözönt generálnak.

Megnyílt a lehetıség, hogy több petabájtnyi adatot lehessen olcsón tárolni, kezelni.

Az Internet és a Grid rendszerek révén ezeket az adathalmazokat könnyen el lehet érni.

A tudományos információkezelési, információgyőjtési, szervezési, lekérdezési, megjelenítési feladatok száma az adatmennyiség arányában növekszik. (Minél több az adat, annál többféle feldolgozásra vagyunk kíváncsiak.) Az adatbányászat napjaink egyik fı kihívása!

A csillagászatban keletkezı hatalmas adathalmazok közös feldolgozására létrehozott architektúra:

The Sloan Digital Sky Survey http://www.sdss.org/

Jim Gray and Alex Szalay, The World Wide Telescope: An Archetype for Online Science, Comm. ACM, 45(11): 50-54, Nov. 2002 Adattárházak és adatbányászat

7

Az adatbázis technológia fejlıdése

1960:

Adatgyőjtemények, hálós és hierarchikus adatbázis-kezelık, IMS, IDMS

1970:

Relációs adatmodell bevezetése http://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf

1980:

RDBMS elterjedése, új adatmodellek támogatása (objektumorientált, deduktív, stb.) Alkalmazásspecifikus adatbázis-kezelık (térinformatika, mérnöki tervezések, stb.)

1990:

relációs adatbázis-kezelık (RDBMS) megjelenése

Adatbányászat, adattárházak, multimédia adatbázisok, web-adatbzisok

2000

Adatfolyamok kezelése, bányászata

Adatbányászat alkalmazása egyre több területen

Webtechnológiák, szemantikus technológiák, felhıkörnyezetek Adattárházak és adatbányászat

8

Bevezetés








A tudás értéke





9


Az adatbányászat (tudás kinyerése az adatokból)

Érdekes (nem triviális, implicit, eddig nem ismert és potenciálisan hasznos) mintákat (azaz tudást) akarunk kinyerni a nagyon nagy adathalmazokból lehetıleg automatikusan, és minél hatékonyabban.

Más elnevezések

Tudásfeltárás az adatbázisokban (Knowledge discovery in databases KDD), tudáskinyerés (knowledge extraction), adatelemzés, mintaelemzés (data/pattern analysis), információ-betakarítás (information harvesting), üzleti intelligencia (business intelligence).

Mi nem adatbányászat?

Egyszerő keresések, lekérdezések végrehajtása

(Deduktív) szakértıi rendszerek


10

A tudásfeltárás (KDD) folyamata Az adattárház használata ki is maradhat!

A minták értékelése

Adatbányászat Feladatorientált adatok Adatok kiválasztása

Adattárház Adattisztítás Adatintegráció Adatbázisok


11

Hogy néz ez ki a web-bányászat esetében?

Mibıl áll a web-adatokon végzett tudásfeltárás?

Adattisztítás

Több forrásból származó adatok integrációja

Az adatokból adattárház építése

Adatkockák készítése

Az adatbányászathoz szükséges adatok kiválasztása

Adatbányászat elvégzése

Az eredményekbıl jelentések készítése, megjelenítése

A talált minták, összefüggések (tudás) tárolása a tudásbázisban Adattárházak és adatbányászat

12

Adatbányászat az üzleti intelligenciában A döntéstámogatás piramisa Döntéshozó

Döntéshozatal Prezentáció

Üzleti elemzı

Vizualizációs technikák Adatbányászat Információfelderítés

Adatelemzı

Adatelemzés Statisztikai összegzések, lekérdezések, jelentések Elıfeldolgozás/Integráció, adattárház építése Adatforrások Dokumentumok, fájlok, weboldalak, kísérleti eredmények, adatbázisok Adattárházak és adatbányászat

Rendszergazda

13

A KDD folyamat: Mesterséges intelligencia és statisztikai nézıpontból Input adatok

Elıfeldolgozás

Adatintegráció Normalizálás Lényeges tulajdonságok kiválasztása Dimenziócsökkentés

Adatbányászat

Utófeldolgozás

Minták keresése Asszociáció és korreláció Osztályozás Klaszterezés Kiugró értékek elemzése …………


Minták Minták Minták Minták

értékelése kiválasztása interpretálása megjelenítése

14

Az adatbányászat, mint multidiszciplinális tudomány Gépi tanulás

Alkalmazások

Algoritmusok

Mintafelismerés

Adatbányászat

Adatbázisok


Statisztika

Megjelenítés

Hatékony számítási modellek

15

Bevezetés








A tudás értéke





16


Milyen típusú összefüggést, tudást bányászunk? Jellemzés, (karakterizáció), megkülönböztetés, (diszkrimináció), kapcsolódás (asszociáció), osztályozás (klasszifikáció), csoportosítás (klaszterezés), trendre illeszkedés/trendtıl eltérés, kiugró (outlier) esetek elemzése. Lehet leíró vagy elırejelzı (Descriptive vagy predictive) adatbányászat Több szintő adatbányászat Milyen adatokban bányászunk? Relációs adatbázis, adattárház, tranzakciós adatbázis, adatfolyam, objektumorientált vagy objektum relációs adatbázis, aktív adatbázis, térinformatikai adatbázis, multimédia adatbázis, heterogén adatbázis, örökölt adatbázis, webadatok, hálózatok Milyen technikákat használunk? Adatbázis technológiák, adattárház technológiák (OLAP), gépi tanulás, statisztika, vizualizáció Mire használjuk az adatbnyászatot Kereskedelem, telekommunikáció, bankrendszer, csalásfelderítés, bioinformatika, tızsdeelemzés, szövegbányászat (szemantikus web), webbányászat


17

Miért van szükség ennyiféle terület összevegyítésére?

Hatalmas adatmennyiséggel kell dolgozni

Nagy dimenziójú adatokkal kell dolgozni

A génchipek esetében például több tízezer dimenziójú adatok keletkezhetnek (minden pixelnek egy adatvektort felel meg)

Összetett struktúrájú, különféle típusú adatokat kell vizsgálni

Az algoritmusoknak skálázhatóknak kell lenniük több terabájt adat esetére is

Adatfolyam keletkeznek a mérımőszerekben Idısorok, szekvenciák Struktúrák, gráfok, közösségi hálók, összekapcsolt adatok (szemantikus web) Heterogén adatbázisok, örökölt (régi) adatbázisok Téradatok, téridı adatok, multimédia, szöveg, weboldalak szoftverek, forráskódok, szimulációk

Új összetett alkalmazásokat kell készíteni Adattárházak és adatbányászat

18

Bevezetés








A tudás értéke





19

Az adatbányászat technikái: 1. Általánosítás

Információ integráció, adattárház építése

Adatkockák technológiája

Adattisztítás, transzformálás, integráció, többdimenziós adatmodell készítése Ezek olyan skálázható módszerek, amelyek például materializációval többdimenziós aggregátumokat lehet hatékonyan kiszámítani OLAP (online analytical processing) – online elemzések

Többdimenziós fogalmi leírások: karakterizáció és diszkrimináció (hogyan jellemezhetı, hol vannak eltérések)

Az adatok általánosítása, jellemzése, például a száraz és csapadékos területek összehasonlítása


20

Az adatbányászat technikái: 2. Asszociáció és korreláció

Gyakori minták (gyakori elemhalmazok) keresése

Milyen termékeket vásárolnak gyakran együtt egy boltban?

Többféle összefüggés lehetséges: Asszociáció, korreláció, oksági viszony

Egy tipikus asszociációs szabály

Pelenka Sör [0.5%, 75%] (support, confidence) (támasz és megbízhatóság)

Vajon a szoros asszociációban álló elemek statisztikai értelemben is erısen korreláltak?

Hogy lehet ilyen szabályokat hatékonyan elıállítani egy nagy adatbázis esetében? Hogyan használhatjuk fel ezeket a szabályokat klaszterezésre, osztályozásra vagy más alkalmazásokra? Adattárházak és adatbányászat

21

Az adatbányászat technikái: 3. Osztályozás

Osztályozás, címkék elırejelzése

Egy tanuló adathalmazra modelleket (függvényeket illesztünk) Osztályokat, fogalmakat jellemzünk, vagy különböztetünk meg és ezt elırejelzésre is használhatjuk

Egy új megfigyelt egyed esetében a tulajdonságai alapján jósoljuk meg, hogy melyik osztályba fog tartozni.

Tipikus módszerek

Osztályozzuk az országokat éghajlatuk alapján (szárazföldi, mediterrán, trópusi), úgy hogy mérjük az évi középhımérsékletet, csapadékot, stb. vagy az autók márkája, kora, súlya, mérete, stb. ismeretében osztályozzuk az autókat, hogy mennyi az éves szervízköltség (sok, közepes, kevés)

Döntési fák, naïve Bayesian osztályozó, támaszvektor gépek (SVM - support vector machines), neurális hálók, szabályalapú osztályozás, mintalapú osztályozó, logistic regresszió, …

Tipikus alkalmazások:

Hitelkártyacsalások felderítése, direktmarketing, ajánló rendszerek, véelmények (csillagok) elırejelzése, betegség megjóslása a szimptómákból. Adattárházak és adatbányászat

22

Az adatbányászat technikái: 4. Klaszterezés

Nem felügyelt tanulás (Unsupervised learning) (vagyis nincsenek elıre megadott címkék a csoportokhoz, osztályokhoz rendelve) Magukat az adatokat csoportosítjuk, hogy új kategóriákat fedezzünk fel, például utcai rablások alapján különbözı veszélyezettségő területeket különböztethetünk meg, vagy a házak értékeit vizsgálva egy adott ház helyébıl az értékére következtethetünk Az alapelv: Maximalizáljuk az osztályokon belüli hasonlóságot ÉS minimalizáljuk az osztályok közötti hasonlóságot Rengeteg klaszterezési módszer létezik. Adattárházak és adatbányászat

23

Az adatbányászat technikái: 5. Kiugró objektumok elemzése

Mit tekintünk kiugró objektumnak?

Kiugró (Outlier) objektum: olyan adatobjektum, amely az adatobjektumok általános viselkedésének nem felel meg, például valamelyik komponense nagyon eltér az átlagtól. Minek tekintsük, zajnak vagy kivételnek? ― Ami az egyik szempontból hiba, szemét, az egy másik vizsgálat számára értéket jelent, például csalásra következtethetünk, ha a szokásos használattól nagyon eltér egy bankkártya használata. Milyen módszereket használhatunk? Klaszterezés, regresszió, … Ritka események felderítése (például CERN gyorsítójában a mért adatok alapján keletkezett-e új részecske)


24

Bevezetés








A tudás értéke





25


Az adatok egy részét adatbázisokban tároljuk, alkalmazásokkal dolgozzuk fel.

Relációs adatbázis, adattárház, tranzakciós adatbázis

Speciális adathalmazok és alkalmazások

Adatfolyamok, mőszerek adatai

Idısorok, idıszakos adatok, szekvenciák (például génszekvenciák)

Strukturált adatok, gráfok, hálózatok, összekapcsolt adatok

Objektumrelációs adatbázisok

Heterogén, örökölt adatbázisok

Tér- és téridıadatok

Multimédia adatbázisok

Dokumentumrendszerek, szöveges adatbázisok

Internet: World-Wide Web Adattárházak és adatbányászat

26

Bevezetés








A tudás értéke





27

Idıindexes és rendezett adatok: Szekvenciális minták, trendek

Alkalmazási terület: szekvenciák, trendek, fejlıdésvizsgálat Trendek, idısorok, eltérések elemzése: függvényillesztés, regresszió, például y érték elırejelzése az x ismeretében, ha lineáris viszonyt tételezünk fel. Szekvenciális minták bányászata Minta például, hogy a kamera vásárlása után venni fogunk nagy kapacitású SD kártyát is Ismétlıdések, periodicitás keresése, kiszőrése Biológiai (gén-) szekvenciák vizsgálata (motívumkeresés) Melyek a biológiai jelentéssel bíró motívumok, egymás utáni motívumok Hasonlóságalapú összehasonlító elemzések Adatfolyamok bányászata potenciálisan végtelen adatfolyamok (rendezett adatok vagy idısorok) Adattárházak és adatbányászat

28

Bevezetés








A tudás értéke





29


Gráfok adatbányászata Keressünk gyakori részgráfokat (például nagy molekulákban gyakori egyszerő összetevıket – gyógyszerkutatás), keressünk gyakori részfákat XML dokumentumokban Hálózatok elemzése Közösségi hálók felépítése: aktorok (objektumok - csúcsok) és kapcsolatok (irányított, vagy közönséges élek) például derítsük fel az Adatbányászattal foglalkozó szerzık kapcsolati hálóját, vagy derítsük fel a terroristák hálózatát (ki kit ismer, ki kinek telefonált, kik mikor hol voltak együtt) Többszörös heterogén hálózatok vizsgálata Egy személy egyszerre többféle hálózatnak is tagja: barátok hálózata, rokoni hálózat, osztálytársak hálózata, telefonhívások hálózata A kapcsolatok (Links) értelmezésének, szemantikájánakbányászata Webbányászat A Weboldalak hálózat, rangsorolásis (a Google PageRank és HITS algoritmusai) Alkalmazások webközösségek felderítése, véleménybányászat. klikkelemzés, reklám Adattárházak és adatbányászat

30

Bevezetés








A tudás értéke





31

A tudás értéke

Minden kibányászott minta érdekes?

Kimerítı kereséssel túl sok mintát kaphatunk Van, ami csak bizonyos helyre, idıre, dimenzióra jellemzı, vagyis nem elég általános Van, ami csak múló összefüggés, az aktuális adatokra véletlenül teljesül

Próbáljuk mérni a tudás érdekességét → és csak érdekes tudást bányásszunk ki az adatokból

milyen tudás kell: leíró vagy elırejelzı

milyen eseteket fed le, lehetıleg minél többet

mennyire tipikus vagy újszerő a minta (esıben viszünk ernyıt: érdektelen, esıben levisszük a vízilovat sétálni: érdekes)

mennyire pontos az összefüggés a lefedett esetekben

mennyire idıszerő (mindenki vízilovat tart otthon)


32

Bevezetés








A tudás értéke





33


Weboldalak elemzése: a weboldalak osztályozása témák szerint, fontosságuk szerint, spamoldalak felderítése, klaszterezése a PageRank és a HITS algoritmussal Közösségek felderítése (Collaborative analysis), ajánló rendszerek (milyen videó fog tetszeni azok alapján, amiket eddig néztünk)

Objektumok beazonosítása (Entity resolution)

Célzott marketing vásárlói kosár elemzésével

Biológiai, orvosi adatelemzések: osztályozás, klaszterezés (microchip adatokon), fertızések terjedése, biológiai hálózatok, génszekvenciák elemzése Adatbányászat a szoftvertervezésben, tesztelésben Ingyenes és kereskedelmi adatbányászati eszközök (weka, RapidMiner, R, SAS, MS SQL-Server Analysis Manager, Oracle Data Mining Tools)


34

Bevezetés








A tudás értéke





35


Adatbányászati algoritmusok hatékonysági javítása, skálázhatósága Párhuzamos, osztott adatok, adatfolyamok bányászata, inkrementális Nagyon nagy dimenziók kezelése Bizonytalanság, zajos, nem teljes adatok kezelése Kiegészítı összefüggések, megszorítások, szakértı háttértudás bevonása az adatbányászatba

Minták értékelése, tudásintegráció

Bioinformatika, közösségi hálózatok elemzése

Alkalmazásfüggı, szakmaspecifikus adatbányászat

Láthatalan adatbányászat (beágyazott rendszerekben, külöbözı modulok részeként) Adatbiztonság, adatvédelem, mint az adatbázis-kezelésben Adattárházak és adatbányászat

36

Bevezetés








A tudás értéke





37


1989 IJCAI Workshop on Knowledge Discovery in Databases

1991-1994 Workshops on Knowledge Discovery in Databases

Knowledge Discovery in Databases (G. Piatetsky-Shapiro and W. Frawley, 1991) Advances in Knowledge Discovery and Data Mining (U. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, 1996)

1995-1998 International Conferences on Knowledge Discovery in Databases and Data Mining (KDD’95-98)

Journal of Data Mining and Knowledge Discovery (1997)

ACM SIGKDD conferences since 1998 and SIGKDD Explorations

Adatbányászati konferenciák

PAKDD (1997), PKDD (1997), SIAM-Data Mining (2001), (IEEE) ICDM (2001), etc.

ACM Transactions on KDD 2007 Adattárházak és adatbányászat

38

Adatbányászati konferenciák és folyóiratok

KDD konferenciák ACM SIGKDD Int. Conf. on Knowledge Discovery in Databases and Data Mining (KDD) SIAM Data Mining Conf. (SDM) (IEEE) Int. Conf. on Data Mining (ICDM) Conf. on Principles and practices of Knowledge Discovery and Data Mining (PKDD) Pacific-Asia Conf. on Knowledge Discovery and Data Mining (PAKDD)

Nagy konferenciák részeként:

ACM SIGMOD

VLDB

(IEEE) ICDE

WWW, SIGIR

ICML, CVPR, NIPS

Folyóiratok

Data Mining and Knowledge Discovery (DAMI or DMKD) IEEE Trans. On Knowledge and Data Eng. (TKDE)

KDD Explorations

ACM Trans. on KDD


39

Hol találunk cikkeket? ACM, DBLP, CiteSeer, Google

Data mining and KDD (SIGKDD: CDROM)

Database systems (SIGMOD: ACM SIGMOD Anthology—CD ROM)

Conferences: SIGIR, WWW, CIKM, etc. Journals: WWW: Internet and Web Information Systems,

Statistics

Conferences: Machine learning (ML), AAAI, IJCAI, COLT (Learning Theory), CVPR, NIPS, etc. Journals: Machine Learning, Artificial Intelligence, Knowledge and Information Systems, IEEE-PAMI, etc.

Web and IR

Conferences: ACM-SIGMOD, ACM-PODS, VLDB, IEEE-ICDE, EDBT, ICDT, DASFAA Journals: IEEE-TKDE, ACM-TODS/TOIS, JIIS, J. ACM, VLDB J., Info. Sys., etc.

AI & Machine Learning

Conferences: ACM-SIGKDD, IEEE-ICDM, SIAM-DM, PKDD, PAKDD, etc. Journal: Data Mining and Knowledge Discovery, KDD Explorations, ACM TKDD

Conferences: Joint Stat. Meeting, etc. Journals: Annals of statistics, etc.

Visualization

Conference proceedings: CHI, ACM-SIGGraph, etc. Journals: IEEE Trans. visualization and computer graphics, etc. Adattárházak és adatbányászat

40

Néhány ajánlott könyv

S. Chakrabarti. Mining the Web: Statistical Analysis of Hypertex and Semi-Structured Data. Morgan Kaufmann, 2002

R. O. Duda, P. E. Hart, and D. G. Stork, Pattern Classification, 2ed., Wiley-Interscience, 2000

T. Dasu and T. Johnson. Exploratory Data Mining and Data Cleaning. John Wiley & Sons, 2003

U. M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy. Advances in Knowledge Discovery and Data Mining. AAAI/MIT Press, 1996

U. Fayyad, G. Grinstein, and A. Wierse, Information Visualization in Data Mining and Knowledge Discovery, Morgan Kaufmann, 2001

J. Han and M. Kamber. Data Mining: Concepts and Techniques. Morgan Kaufmann, 2nd ed., 2006

D. J. Hand, H. Mannila, and P. Smyth, Principles of Data Mining, MIT Press, 2001

T. Hastie, R. Tibshirani, and J. Friedman, The Elements of Statistical Learning: Data Mining, Inference, and Prediction, Springer-Verlag, 2001

B. Liu, Web Data Mining, Springer 2006.

T. M. Mitchell, Machine Learning, McGraw Hill, 1997

G. Piatetsky-Shapiro and W. J. Frawley. Knowledge Discovery in Databases. AAAI/MIT Press, 1991

P.-N. Tan, M. Steinbach and V. Kumar, Introduction to Data Mining, Wiley, 2005

S. M. Weiss and N. Indurkhya, Predictive Data Mining, Morgan Kaufmann, 1998

I. H. Witten and E. Frank, Data Mining: Practical Machine Learning Tools and Techniques with Java Implementations, Morgan Kaufmann, 2nd ed. 2005 Adattárházak és adatbányászat

41

Adatbányászat. Data Mining: Concepts and Techniques (3 rd ed.)

Recommend Documents