Curs 1 Data Mining

Introducere în Data MiningCurs 1: Prezentare generală

Lucian Sasu, Ph.D.

Universitatea Transilvania din Braşov, Facultatea de Matematică şi Informatică

April 7, 2014

[email protected] (UNITBV) Curs 1 April 7, 2014 1 / 42

Outline

1 Bibliografia recomandatăBibliografie pentru cursBibliografie pentru laborator

2 Data Mining - introducereDefiniţii, exemple şi motivaţieData Mining şi Knowledge DiscoveryPuncte de dificultateOriginile DMTipuri de aplicaţii DM


Bibliografie pentru curs

1 Pang-Ning Tan, Michael Steinbach, Vipin Kumar: Introduction toData Mining, Addison-Wesley, 2006




2 David J. Hand, Heikki Mannila and Padhraic Smyth: Principles ofData Mining, MIT Press, 2001





3 Jiawei Han, Micheline Kamber, Jian Pei: Data Mining: Concepts andTechniques, 3rd ed., Morgan Kaufmann Publishers, 2011





3 Jiawei Han, Micheline Kamber, Jian Pei: Data Mining: Concepts andTechniques, 3rd ed., Morgan Kaufmann Publishers, 2011

4 Trevor Hastie, Robert Tibshirani, Jerome Friedman: The Elements ofStatistical Learning: Data Mining, Inference, and Prediction, 2ndedition, Springer 2009, liberă la download


http://www-stat.stanford.edu/~tibs/ElemStatLearn/download.html

Bibliografie pentru laborator

1 RapidMiner: http://rapidminerresources.com


http://rapidminerresources.com


1 RapidMiner: http://rapidminerresources.com2 RapidMiner: http://rapidminer.com/learning/getting-started/



http://rapidminer.com/learning/getting-started/


1 RapidMiner: http://rapidminerresources.com2 RapidMiner: http://rapidminer.com/learning/getting-started/3 Weka: Ian H. Witten, Eibe Frank: Data Mining: Practical Machine

Learning Tools and Techniques, 2nd edition, Morgan Kaufmann, 2005





1 RapidMiner: http://rapidminerresources.com2 RapidMiner: http://rapidminer.com/learning/getting-started/3 Weka: Ian H. Witten, Eibe Frank: Data Mining: Practical Machine

Learning Tools and Techniques, 2nd edition, Morgan Kaufmann, 20054 Weka: Curs Weka la

https://weka.waikato.ac.nz/dataminingwithweka/course




https://weka.waikato.ac.nz/dataminingwithweka/course

Unelte folosite la laborator (1)

Weka: Data Mining Software in Java, Download de aiciWeka is a collection of machine learning algorithms for data mining tasks. The algorithms

can either be applied directly to a dataset or called from your own Java code. Weka

contains tools for data pre-processing, classification, regression, clustering, association

rules, and visualization. It is also well-suited for developing new machine learning

schemes.


http://www.cs.waikato.ac.nz/ml/weka/



Weka: Data Mining Software in Java, Download de aiciWeka is a collection of machine learning algorithms for data mining tasks. The algorithms

can either be applied directly to a dataset or called from your own Java code. Weka

contains tools for data pre-processing, classification, regression, clustering, association

rules, and visualization. It is also well-suited for developing new machine learning

schemes.

Software multiplatformă dezvoltat în Java; poate fi folosit din GUI sau prin API-ul expus;

posibil să se apeleze din .NET via ikvm.net.




http://www.ikvm.net/


RapidMiner Community EditionThe main product of Rapid-I, the data analysis solution RapidMiner, is the world-leading

open-source system for data and text mining.

Mecanisme: Data Integration, Analytical ETL, Data Analysis, andReporting; graphical user interface for the design of analysisprocesses; Repositories for process, data and meta data handling;Hundreds of data loading, data transformation, data modeling, anddata visualization methods [. . . ]

Alte softuri larg folosite, dar neabordate la laborator:http://www.kdnuggets.com/software/index.html,

http://www.kdnuggets.com/polls/2010/data-mining-analytics-tools.html

http://www-users.cs.umn.edu/~kumar/dmbook/resources.htm


http://rapid-i.com/index.php?lang=en

http://rapid-i.com/content/view/181/196/lang,en/

http://www.kdnuggets.com/software/index.html

http://www.kdnuggets.com/polls/2010/data-mining-analytics-tools.html

http://www-users.cs.umn.edu/~kumar/dmbook/resources.htm

Outline

1 Bibliografia recomandatăBibliografie pentru cursBibliografie pentru laborator

2 Data Mining - introducereDefiniţii, exemple şi motivaţieData Mining şi Knowledge DiscoveryPuncte de dificultateOriginile DMTipuri de aplicaţii DM


Definiţii

Definiţie

Data Mining este procesul descoperirii (semi)automate a informaţiilor utileîn depozite mari de date (Tan et al).

Definiţie

Data Mining este analiza seturilor de date – deseori de dimensiuni mari –rezultate prin observaţii pentru a găsi relaţii noi şi pentru sumarizareadatelor în moduri care sunt atât uşor de înţeles cât şi utile celui ce deţinedatele (Hand et al).

Definiţie

Data mining este procesul netrivial de extragere a informaţiei implicite,anterior necunoscute, interesante şi potenţial utile din date, de regulă subforma de modele şi şabloane de cunoaştere (Schapiro et al).


Termeni alternativi:

mineritul cunoştinţelor din date

extragere de cunoştinţe (eng: Knowledge Discovery) – sinonimdiscutabil

analiza date/şabloane

Ce NU e Data Mining:

găsirea datelor complete privind o persoană folosind interogare într–obază de date;

găsirea paginilor web care conţin anumiţi termeni;

Acestea sunt activităţi de regăsire a informaţiei.


Ce poate fi Data Mining:

să descoperi că anumite nume sunt mai frecvente în unele zone:O’Brien, O’Rurke, O’Reilly în zona Boston;

gruparea clienţilor pe baza unui profil de consum comun;

gruparea paginilor dintr-un motor de căutare pe baza similarităţilor:motorul http://clusty.com/;


http://clusty.com/

Clustering de pagini web in Clusty


Farecast: să cumpăr sau nu acum un bilet de avion?


De ce Data Mining: din punctul de vedere al afacerilor (1)

O mulţime de date sunt colectate şi depozitate prin sisteme de datawarehouse

date din Web, comerţ electroniccumpărături în magazine/lanţuri de desfaceretranzacţii financiare, carduri de debit/credit

Calculatoarele au devenit tot mai ieftine şi mai puternice; procesareadistribuită este ceva comun.


De ce Data Mining: din punctul de vedere al afacerilor (2)

Presiunea impusă de competiţie este motivantă: aducerea unui nouclient într–o reţea de telefonie este de până la 4 ori mai scumpă decâtpăstrarea lui: Customer attrition

Cerinţe specifice mediului de afaceri: customer profiling, targettedmarketing, fraud detection

Probleme stringente: “Care sunt cei mai profitabili clienţi?”, “Careproduse cumpărate atrag achiziţia altor produse?”, “Care va fi evoluţiacompaniei/pieţei pe segmentul . . . ?”, “Care sunt nişele de piaţă?”


http://en.wikipedia.org/wiki/Customer_attrition

De ce Data Mining: din punct de vedere ştiinţific

În domenii precum medicina, inginerie şi ştiinţă se acumulează rapiddate ce trebuie exploatate pentru a duce la noi descoperiri;

Exemplu: dezvoltarea de sisteme de sateliţi pentru observaţiiclimatice;

Date genetice generate prin “microarrays”; se doreşte decodificareacompletă a genomului uman, determinarea genelor care cauzeazădiferite afecţiuni, înţelegerea structurii şi funcţionalităţii genelor;

DM e unealtă de bază pentru bioinformatică = “aplicarea statisticii şia informaticii în domeniul biologiei moleculare”.


http://en.wikipedia.org/wiki/Bioinformatics

Competiţii

Neflix prize: 100.480.507 rating-uri date de 480.189 utilizatori pentru17.770 filme

KDDCup:

2013: Author-Paper Identification Challenge2012: User Modeling based on Microblog Data and Search Click Data2011: Recomandare de muzică2010: Evaluarea performanţelor studenţilor2009: Predicţia relaţiei cu clienţiicompetiţia merge până în 1997

Alte competiţii —www.kdnuggets.com, kaggle


http://en.wikipedia.org/wiki/Netflix_prize

http://www.sigkdd.org/kddcup/index.php

http://www.kdnuggets.com/2013/04/kdd-cup-2013-author-paper-identification-challenge.html

https://www.kddcup2012.org/

http://www.kdnuggets.com/2011/02/kdd-cup-2011-recommending-music.html

http://www.sigkdd.org/kdd-cup-2010-student-performance-evaluation

http://www.sigkdd.org/kdd-cup-2009-customer-relationship-prediction

http://www.kdnuggets.com/datasets/competitions.html

http://www.kaggle.com/

Paşii unui proces de extragere de cunoştinţe (1)

Data Mining este parte integrantă a domeniului Knowledge discoveryin databases (KDD), care e un întreg proces de conversie a datelorprimare în cunoştinţe (informaţie).

Procesul constă într–o succesiune de paşi:

Datele de intrare se pot găsi într-o largă varietate de formate: fişieretext, baze de date relaţionale, date semistructurate (e.g. XML,HTML), imagini, filme etc.


Paşii unui proces de extragere de cunoştinţe (2)

Datele se selectează din multitudinea de surse;

Preprocesarea şi transformarea pot include: selectarea dimensiunilor,reducerea dimensionalităţii, tratarea datelor incomplete, normalizarea;

Preprocesarea şi transformarea pot lua chiar şi 60% din durata totalăa unui proces de extragere a cunoştinţelor;

Partea de Data Mining se face printr–o varietate de tehnici; deseori setestează mai multe metode;

La final, cunoştinţele rezultate sunt post–procesate (e.g. se eliminărezultatele invalide sau neinteresante) şi trebuie prezentate într–oformă inteligibilă factorilor de decizie (e.g. vizualizare sau reguli deforma “if–then”), sau integrate în alte sisteme (e.g. sistemele utilizatepentru detectare de fraude);


Atenţie la ce se obţine

Tehnici folosite la preprocesare: testarea ipotezelor prin metodestatistice – se elimină rezultatele nerealiste;

Eliminarea cunoştinţelor “neinteresante” — element subiectiv,dependent de cunoştinţele anterioare;

Limitarea complexităţii modelelor folosite în procesul de DM: “If youtorture the data long enough, it will confess” (Ronald Harry Coase,economist);

Principiul lui Bonferroni: if you look harder than the quantity of datasupports, you will find a pattern that “fits”.


Principiul lui Bonferroni: paradoxul Rhine (1)

Joseph Rhine: parapsiholog în anii ’50 care a încercat să dovedeascăfaptul că unii oameni au percepţie extra-senzorială;

“experimentul” lui Rhine: a cerut unor oameni să ghicească culorile a10 cartonaşe ascunse – se ştiau cele două posibilităţi: roşu şi albastru;

a “descoperit” că aproximativ 1/1000 din oameni au ghicit toate cele10 cartoane

a spus oamenilor respectivi că au abilităţi extrasenzoriale şi i-a chematpentru alte experimente

la un nou experiment, oamenii de la pasul anterior nu au mai ghicitaproape deloc culoarea cartoanelor.

“Concluzia”:


Principiul lui Bonferroni: paradoxul Rhine (2)

Nu ar fi trebuit să le spună oamenilor că au capacităţiextra-senzoriale: asta îi face să şi le piardă!!

Un calcul probabilistic simplu arată că raportul de aproximativ 1/1000poate fi explicat prin evenimente aleatoare şi legea numerelor mari;

Cunoaşterea principiului lui Bonferroni poate să salveze de astfel de“descoperiri”.


Scalabilitatea şi dimensiunea datelor

A leading retail bank is using Cloudera and Datameer to validate dataaccuracy and quality to comply with regulations like Dodd-Frank;1TB of data / month; studiu de cazA health IT company instituted a policy of saving seven years ofhistorical claims and remit data, but its in-house database systemshad trouble meeting the data retention requirement while processingmillions of claims every day; 1TB of data / day; studiu de cazStoring billions of mobile call records and providing real time accessto the call records and billing information to customers. Traditionalstorage/database systems couldn’t scale to the loads and provide acost effective solution; 30TB of data is added monthly; studiu de cazProiectul genomului uman: 3.4 miliarde de perechi şi între 20000 şi25000 gene;Experimentul “Compact Muon Solenoid” la CERN’s Large HadronCollider generează 40 de terabytes de date pe secundă.

Primele 3 exemple sunt preluate de [email protected] (UNITBV) Curs 1 April 7, 2014 22 / 42

http://www.cloudera.com/content/dam/cloudera/Resources/PDF/connect_case_study_datameer_banking_financial.pdf

http://www.cloudera.com/content/dam/cloudera/Resources/PDF/Cloudera_Case_Study_Healthcare.pdf

http://hadoop.intel.com/pdfs/IntelChinaMobileCaseStudy.pdf

http://calculatoredge.tradepub.com/free/w_hado01/?p=w_hado01

Scalabilitatea şi dimensiunea datelor (2)

variante: structuri de date specifice, care să uşureze interogareadatelor

scalarea pe orizontală sau pe verticală a resurselor hardware;

scalarea pe verticală: rareori suficientă, datele nu încap în RAM

scalarea pe orizontală – cazuri remarcabile: Apache Hadoop, ApacheMahout — proiecte open–source.


Date eterogene şi complexe

atribute eterogene: numerice, categoriale;

ce faci cu datele lipsă? eliminarea înregistrărilor cu goluri de date nu eîntotdeauna o opţiune;

colecţii de documente (e.g. pagini Web); date ADN cu structurăspaţială şi secvenţială; serii de timp

tehnicile de DM trebuie să ia în considerare relaţiile dintre date(corelaţie spaţială şi temporală; conectivitate de grafuri; relaţiepărinte–copil).


Gestiunea şi distribuirea datelor

datele pot fi prezente în locaţii multiple, nu doar într–o organizaţie;

necesitate: DM distribuit sau suport de tip Data Warehouse

în caz de distribuire: comunicarea necesară poate să domine timpulde calcul

în caz de data warehouse: integrarea datelor necesită timp îndelungat

“data privacy”: problemă delicată, diferite aspecte legislative potinterveni


Analiză nestandard

Statistica: enuntarea de ipoteze şi apoi testarea lor;

Problemă evidentă: procesul este laborios

DM are ca scop tocmai determinarea pe cât posibil automată a astfelde ipoteze;

În timp ce statistica este în mare măsură tributară modelelorparametrice, datele reale pot avea cu totul alte distribuţii decât celepresupuse;

Dar statistica oferă unelte utile – de exemplu metode de testare,determinarea intervalelor de confidenţă, inferenţa statistică etc.


Originile DM

Statistică – eşantionare, estimare, testarea ipotezelor, modeleparametrice;

Inteligenţă artificială — tehnici de raţionament probabilist şimanagement al incertitudinii

Învăţare automată (machine learning) — pornind de la date secreează modele adecvate

Recunoaştere de şabloane (pattern recognition)

Sisteme de baze de date – suport pentru stocarea (eventualdistribuită a ) datelor; probleme pot apărea din cauză că nu toatedatele se pot reprezenta uşor sub model relaţional;

Calcul paralel—distribuit — pentru a rezolva problema scalabilităţiiaplicaţiilor de DM;


Sunt două categorii majore de aplicaţii:

Predicţia — scopul e de a prezice valoarea concretă a unui atribut pebaza altor atribute. Atributul ce urmează a fi prezis senumeşte variabilă dependentă sau ţintă; cele care se folosescpentru predicţie sunt variabile independente sau explicative;

Descrierea — determinarea de şabloane, e.g. corelaţii, tendinţe, grupări,traiectorii, anomalii


Clasificare — predicţie

Grupare (Clustering) — descriere

Determinarea relaţiilor de asociere — descriere

Descoperirea şabloanelor secvenţiale — descriere

Regresie — predicţie

Detectarea deviaţiilor — predicţie


Clasificarea: definiţie

Se pleacă de la o colecţie de înregistrări = setul de antrenare

Fiecare înregistrare e formată din atribute, dintre care unul este“clasa”: bun/rau, risc mare/risc moderat/risc mic;

Scopul este găsirea unui model (a unui mecanism, a unei funcţii) caresă determine clasa pe baza atributelor;

Modelul trebuie să facă o clasificare cât mai fidelă pentru înregistrăricare nu fac parte din setul de test = date din setul de testare;


Clasificarea: exemplu


Clasificarea: aplicaţia 1

Marketing direct:

scopul: reducerea costurilor de trimitere a reclamelor prin poştă prinalegerea unui set de consumatori pentru care şansele de achiziţie aunui produs sunt mari

modalitate de lucru:

se pleacă de la produse similarepentru aceste produse ştim dacă au fost sau nu cumpărate de cătreconsumatorii în cauză; asta dă clasa unei înregistrări, ca valoareposibilă din mulţimea {a cumpărat, nu a cumpărat}se colectează date demografice despre clienţi, istoricul tranzacţiilor etc.se folosesc aceste date pentru a construi un clasificator.



Prevenirea migrării clientului:

Scop: să se determine dacă un client al serviciilor oferite este pe calede a pleca la un competitor


se folosesc înregistrări detaliate despre tranzacţiile făcute de client (e.g.telefonie: apelurile efectuate, reţelele către care s–au efectuat, durata,frecvenţa);se folosesc date demografice: situaţia financiară, starea civilă etc.se etichetează clientul ca fiind loial sau nuplecând de la acest set de antrenare se creează un clasificator care săfie utilizat pentru alţi clienţi



Clasificarea obiectelor cereşti

Scop: să se prezică clasa unor obiecte cereşti pe baza imaginilor luatede telescoape


se pleacă de la o colecţie de imagini; caz concret: 3000 imagini cu23040 x 23040 pixeli pe imaginese segmentează imaginease măsoară anumite trăsăturise construieşte un clasificator plecând de la aceste segmente de imaginicu clase ataşate - pentru fiecare segment se ştie exact ce reprezintăpoveste de succes: s–au găsit 16 noi quasari, elemente greu dedescoperit şi catalogat prin mijloace tradiţionale.



Clasificarea galaxiilor în: galaxii tinere, de vârstă medie, vechi.

Scop: clasificarea galaxiilor relativ la stadiul de formare: galaxii tinere,de nivel intermediar, stadiu final;

set de date: 20 de milioane de galaxii, 72 de milioane de stele

baza de date de 150 GB

atribute: trăsături extrase din imagini, caracteristicile lungimilor deundă primite etc.

sursa: http://aps.umn.edu


http://aps.umn.edu

Clustering: definiţie

Dându–se un set de puncte, fiecare având un set de atribute şi omăsură de similaritate, să se găsească grupări (cluster–e) cuproprietatea:

punctele care aparţin unui aceluiaşi cluster sunt similare între elepunctele din clustere separate sunt mai puţin similare

măsură de similaritate: distanţa Euclidiană sau alte măsuri specifice

deosebire faţă de clasificare: printre atributele considerate nu existăun atribut de clasă


Clustering: exemplu

Gruparea automată de documente

scop: găsirea grupurilor de documente care sunt similare pe bazatermenilor pe care îi conţin

modalitate de lucru

se contorizează cuvintelese formează o măsură de similaritate între documente pe bazafrecvenţelorpe baza similarităţii se formează grupurileutilitate: pentru un nou document se descoperă rapid care esteclusterul căruia îi aparţine în mod natural;

utilitate: detectare de plagiate, căutare de documente similare etc.


Analiza asocierilor: definiţie

Dându–se un set de colecţii de înregistrări, să se producă regulile dedependenţă care prezic apariţia unui item pe baza apariţiei altor itemi


Analiza asocierilor: exemple

găsirea grupurilor de gene care au funcţii înrudite

identificarea paginilor Web dintr–un site care sunt accesate împreună

Market Basket Analysis: care sunt produsele care se vând bineîmpreună; în funcţie de aceste grupări se poate specula partea decross-selling (ieftineşti un produs dar îl scumpeşti pe un altul) saudispunerea pe raft a lor (cele care se vând împreună să fie dispuseapropiat);

echiparea maşinilor care participă la reparaţii cu anumite unelte,pentru a reduce numărul de deplasări la client


Descoperirea şabloanelor secvenţiale: definiţie

Dându–se un set de obiecte, fiecare cu timpul la care apare, să segăsească regulile care pot prezice dependinţele secvenţiale dintreevenimente;

Spre deosebire de analiza asocierilor: apariţia evenimentelor estereglată de restricţii de timp.


Regresie: definiţie, exemple

Prezicerea unui atribut continuu pe baza unor atribute independente;

Similar cu clasificarea, dar la regresie valorile variabilei dependentesunt numerice

Intens studiată în statistică şi reţele neurale artificiale

Exemple:

prezicerea volumului de vânzăriprezicerea vitezei vântului pe baza umidităţii, presiunii, temperaturiietc.prezicerea consumului de curent într–o anumită perioadă, pe o zonăspecificată


Detectarea anomaliilor

detectarea deviaţiilor semnificative de la comportamentul normal

aplicaţii:

detectarea fraudelor cu card bancardetectarea intruziunilor în reţele de calculatoare


Date post:	26-Jun-2015
Category:	Education
Upload:	lucian-sasu
View:	3,936 times
Download:	0 times

Curs 1 Data Mining

Education