Software

n Weka 3
¨ Pachet software ce include algoritmi de data
Introducere în Data Mining mining
¨ Open Source
¨ Scris in limbajul Java
¨ [Link]

Introducere în Data Mining 3

Bibliografie Detalii Organizatorice

n Pang-Ning Tan, Michael Steinbach, Vipin Kumar: n Curs

Introduction to Data Mining, Addison-Wesley, 2006 ¨ Prezentarea conceptelor teoretice legate de domeniul Data Mining
n Jiawei Han, Micheline Kamber, Jian Pei: Data Mining: n Laborator
Concepts and Techniques, 3rd ed., Morgan Kaufmann ¨ Implementări practice pentru algoritmi prezentati la curs
Publishers, 2011 ¨ Utilizarea de pachete software dedicate pentru data mining: Weka,
n David J. Hand, Heikki Mannila and Padhraic Smyth: RapidMiner, s.a.
Principles of Data Mining, MIT Press, 2001 n Evaluare
n Data Mining – Practical Machine Learning. Tools and ¨ nota de laborator = NL
Techniques with Java Implementation(3rd Edition) - Ian H. ¨ examen scris = NE
Witten, Morgan Kaufman Publishers, 2011 ¨ nota finală: (NL+NE)/2

Introducere în Data Mining 2 Introducere în Data Mining 4

Ce este data mining? Unde se foloseste?
n Data mining este procesul de extragere automata ¨ Business management
sau semi-automata a cunostintelor din baze de date
¨ Production control
foarte mari (Pang-Ning Tan)
n Data Mining este analiza seturilor de date – deseori ¨ Market analysis
de dimensiuni mari – rezultate prin observatii pentru ¨ Engineering design
a gasi relatii noi si pentru sumarizarea datelor in
¨ Science exploration
moduri care sunt atat usor de ınteles cat si utile celui
ce detine datele (David J. Hand et al).

Introducere în Data Mining 5 Introducere în Data Mining 7

Ce este data mining? Knowledge Discovery in Databases (KDD)

n Data mining este o componenta a procesului de Knowledge Discovery in

n Data mining este procesul de descoperiere de Databases (KDD)
cunostinte noi, precum:
¨ sabloane (patters)
¨ asocieri (associations)
¨ modificari (changes)
Prin studiul sistematic al volumelor mari de date

Introducere în Data Mining 6 Introducere în Data Mining 8

Etapele KDD Originile Data Mining
n Curăţarea Datelor (Data Cleaning) - Este procesul de
determinare şi eliminare a informaţiilor eronate, nerelevante
şi incomplete.
n Integrarea Datelor (Data Integration) - Este procesul de Statistics/ Machine Learning/
integrare a datelor provenite din surse eterogene. AI Pattern
Recognition
n Selecţia Datelor (Data Selection) - Este procesul prin care
se extrag din sursele de date informaţiile relevante pentru
analiză. Data Mining

n Transformarea Datelor (Data Transformation) - Este

procesul prin care datele sunt transformate sau consolidate
în structuri adecvate execuţiei procesului de analiză. Database
systems

Introducere în Data Mining 9 Introducere în Data Mining 11

Etapele KDD Data Mining – Clasificare Obiective

n Minarea Datelor (Data Mining) - Este procesul prin care La nivel înalt principale obiective ale sistemelor de data
datele sunt analizate utilizând metode matematice, din
inteligenţa artificială (teoria fuzzy, reţele neuronale), teoria mining pot fi clasificate în două mari categorii:
probabilitaţilor, etc. cu scopul determinării de noi informaţii
precum: şabloane (pattern-uri), structuri, modele de date, n Predicţia - realizează o inferenţă asupra valorilor
etc. datelor curente din bazele de date cu scopul de a
n Evaluarea Modelelor (Pattern Evaluation) - Este procesul prezice valori necunoscute sau viitoare ale acestora.
prin care se identifică modelele relevante din mulţimea
anterior determinată (în baza unor măsuri de evaluare). n Descrierea - realizează o caracterizare generală a
n Reprezentarea Cunoştinţelor (Knowledge Presentation) - datelor uşor de interpretat de către om.
Este procesul de reprezentare şi vizualizare a cunoştinţelor
descoperite.

Introducere în Data Mining 10 Introducere în Data Mining 12

Task-uri in Data Mining Arhitectura unui sistem data mining
n Clasificare - taskul de determinare a unei funcţii Graphical user interface
prin care datele să fie încadrate (clasificate) într-
una sau mai multe clase predefinite. Pattern evaluation
n Regresie - taskul de determinare a unei funcţii
care să permită evaluarea valorii unei variabile Data mining engine
reale.
n Clusterizare - taskul prin care datele ce au Knowledge-base
Database or data
caracteristici similare sunt grupate în clase sau warehouse server
clustere. Gruparea se realizează pe baza unor Data cleaning & data integration Filtering
metrici de similaritate.
Data
Databases Warehouse
Introducere în Data Mining 13 Introducere în Data Mining 15

Task-uri in Data Mining (cont.)

n Extragere de reguli de asociere - taskul de
determinare de relaţii (reguli de asociere) între
atributele unei baze de date cu tranzacţii.
n Sumarizare sau condensare - taskul de
determinare a unei descrieri compacte pentru o
mulţime de date.
n Analiza secvenţelor - taskul de determinare a
paternurilor secvenţiale din date.

Introducere în Data Mining 14

 Valorile atributelor
n Valoarea unui atribut poate să fie un număr sau un
simbol
Preprocesarea datelor n Trebuie să facem disticție între atribute și valorile
atributelor
¨ Acelasi atribut poate să fie exprimat prin valori diferite
n Ex: distanta poate fi exprimată în km sau mile
¨ Atribute diferite pot fi exprimate prin aceiași mulțime de
valori și să aibe semnificații diferite
n Ex: varsta unei persoane și id-ul unei înregistrări pot fi exprimată
printr-un număr întreg

Preprocesarea Datelor 3

Seturi de date Atribute Tipuri de atribute

n Un set de date este o colecție de Ramb- Status n Categoriale (calitative)
obiecte caracterizate de o mulțime de Tid unsare Marital
Venit Trișor

atribute ¨ Nominale – permit identificarea diferentelor

1 Yes Necasatorit 1250 No
n Un atribut este o proprietate sau o n Operatii: =, ≠
caracteristică a unui obiect ce poate să 2 No Casatorit 1000 No
difere de la un obiect la altul, sau de la n Ex: sex (masculin, feminin), codul postal
3 No Necasatorit 700 No
un moment de timp la altul ¨ Ordinale – permit ordonarea valorilor
¨ Ex: sexul unei persoane, greutatea,
temperatura, etc.
4 Yes Casatorit 1200 No
n Operatii: =, ≠, <, >
¨ Denumiri alternative pentru atribut: 5 No Divortat 950 Yes n Ex: grade didactice (asistent, lector, conferentiar, profesor)
variabilă, câmp (field), caracteristică, Obiecte
trăsărură
6 No Casatorit 600 No
n Numerice (cantitative)
n Un obiect este descris de o mulțime de 7 Yes Divortat 2200 No
¨ Interval
atribute 8 No Necasatorit 850 Yes
¨ Obiectul este întâlnit și sub numele de n Ex: data calendaristica, temperatura exprimate in grade Celsius sau
înregistrare (record), tranzacţie, 9 No Casatorit 750 No Fahrenheit;
exemplu (sample), entitate, sau
instanţă 10 No Necasatorit 900 Yes ¨ Multiplicative – permit înmultiri şi împărţiri
Ex: valoarea creditului
1
0

Preprocesarea Datelor 2 Preprocesarea Datelor 4

Tipuri de atribute (cont.) Record-uri
n Atribute discrete – mulţimea valorilor este o n Date ce constau într-o colecție de înregistrari,
multime cel mult numarabilă
fiecare înregistrare avand un set fix de atribute
¨ Ex: nota unui student (1,…,10), multimea de cuvinte dintr-o
colecție de documente Tid Ramb-unsare Status Marital Venit Trișor

¨ Atributele boolene sunt un caz particular: true/false 1 Yes Necasatorit 1250 No

2 No Casatorit 1000 No
n Atribute continue – valorile sunt exprimate prin 3 No Necasatorit 700 No

numere reale 4 Yes Casatorit 1200 No

5 No Divortat 950 Yes

¨ Reprezentate de regulă în virgulă mobilă 6 No Casatorit 600 No

¨ Ex: greutatea 7 Yes Divortat 2200 No

8 No Necasatorit 850 Yes

9 No Casatorit 750 No

10 No Necasatorit 900 Yes

10

Preprocesarea Datelor 5 Preprocesarea Datelor 7

Tipuri de seturi de date Date Document

n Înregistrări sau Record-uri n Reprezinta termeni dintr-o mulţime de documente sub forma unui vector,
¨ Fiecare termen este o componentă (atribut) al vectorului,
¨ Matrice de date
¨ Valorile componentelor indică numărul de apariţii ale termenului în document.
¨ Date Document
¨ Tranzactii

n Graf
¨ World Wide Web

timeout

season
coach

game
score
team

ball

lost
play
¨ Structurile Moleculare

win
n Ordonate
¨ Date spatiale
¨ Date Temporale
¨ Date secventiale
¨ Genetic Sequence Data

Preprocesarea Datelor 6 Preprocesarea Datelor 8

Tranzactii Caracteristici ale seturilor de date structurate

n Un tip special de înregistrari, în care n dimensionalitatea = numarul de atribute pe care obiectele le

¨ Fiecare înregistrare (tranzactie) au
implică o mulțime de articole.
n caracterul rarefiat al datelor = procentul de date utile; de
¨ Ex: Multimea produselor
cumparate de un client la o vizită exemplu, numarul de valori nenule. Aceasta informatie poate
intr-un supermarket fi folosită pentru a reduce spaţiul de memorie sau timpul de
procesare;
TID Produse
n rezoluţia = scara la care se face raportarea valorilor; e posibil
1 Paine, Cola, Lapte
ca scări diferite sa releve (sau sa ascundă) pattern-uri; ex:
2 Bere, Paine masuratori meteo raportate pe zile pot arăta iminenţa unei
3 Bere, Cola, Scutece, Lapte furtuni, dar la scala de săptamâni asa ceva nu mai e vizibil.
4 Bere, Paine, Scutece, Lapte
5 Cola, Scutece, Lapte

Preprocesarea Datelor 9 Preprocesarea Datelor 11

Date Graf Preprocesarea Datelor

n Lista prietenilor de pe Facebook
n De ce este necesară preprocesarea?
n Legaturile dintre paginile web
n Curăţirea datelor
n Integrarea si transformarea datelor
n Reducerea datelor
n Discretizarea datelor
n Sumarizarea datelor

Preprocesarea Datelor 10 Preprocesarea Datelor 12

De ce e necesară preprocesarea? Curatirea datelor (Data Cleaning)
n Datele din lumea reală conţin imperfecţiuni n Importanta
¨ incomplete: valorile anumitor atribute lipsesc, lipsesc ¨ “Curatirea datelor este principala problema in cadrul
atribute relevante, sau contin numai valori agregate sistemelor data warehousing”
n ex: ocupatia=""
n Task-uri in procesul de curăţire
¨ zgomote: contin erori sau anomali
n ex: salariul= -10 ¨ Completarea valorilor lipsa
¨ inconsistente: conțin discrepanțe în coduri sau denumiri ¨ Identificarea valorilor anormale si eliminarea zgomotelor
n ex: varsta=“20” data-nasterii=“03/07/1970”
¨ Corectarea datelor inconsistente
n ex: a fost notat cu “1,2,3”, in loc de “A, B, C”
n ex: discrepanţă între valori duplicate ¨ Rezolvarea redundantelor cauzate de integrarea datelor

Preprocesarea Datelor 13 Preprocesarea Datelor 15

De ce e importantă preprocesarea? Datele Lipsă

n Date de calitate slaba = rezultate slable ale n Anumite date nu sunt intodeauna disponibile
procesului de minare! ¨ Ex: venitul unui client nu e intodeauna disponibil
¨ Deciziile de calitate se iau pe baza datelor de calitate
n Ex, valori lipsa sau duplicate poate conduce la statistici n Datele lipsa pot fi cauzate de
incorecte ¨ Funcționarea incorecta a echipamentelor
n Pregatirea datelor, curatirea, si transformarea lor ¨ Inconsistenta cu alte inregistrari si eliminarea acestora
¨ Nu au fost considerate relevante în momentul culegerii
constituie un efort major intr-o aplicatie de data
¨ Etc.
mining

Preprocesarea Datelor 14 Preprocesarea Datelor 16

Cum gestionam datele lipsa? Cum eliminam zgomotele?
n Ignorăm tuplurile n Partitionarea datelor:
n Completam valorile lipsa manual: plictisitor + imposibil? ¨ Datele sunt sortate si apoi grupate in parti
n Le completam automat cu (intervale) egale
¨ O constanta globala : ex., “unknown”
¨ Media valorilor atributului n Grupare
¨ Cea mai probabilă valoare: infrerată prin formula lui Bayes, arbore de ¨ Detectarea si eliminarea anomaliilor
decizie, sau algoritmul EM
n Inspectarea semi-automată (computer-om)

Preprocesarea Datelor 17 Preprocesarea Datelor 19

Zgomote Integrarea Datelor

n Zgomot (eng. noise): o eroare aleatoare sau o n Integrarea datelor:
variatie a unei variabile masurate. ¨ Combinarea datelor ce provin din surse multiple
n Pot fi cauzate de n Integrarea schemelor bazelor de date
¨ Eroriale instrumetelor de colectare ¨ Integrarea metadatelor ce provin surse diferite
¨ Probleme de introducere a datelor n Detectarea si eliminarea valori conflictuale
¨ Probleme de trasmisie a datelor ¨ Ex: distanta exprimata in km sau mile
¨ etc
n Eliminarea duplicatelor si a datelor redundante

Preprocesarea Datelor 18 Preprocesarea Datelor 20

Trasformarea datelor Discretizarea
n Netezirea: eliminarea zgomotelor din date n Imparțirea spatiului de valori a unui atribut
n Normalizarea: scalarea unei multimi de valori intr-un continuu in intervale si inlocuirea valorilor
interval specificat initiale cu etichetele asociate intevalelor
pentru a putea aplica algoritmi de data mining
n Construirea de atribute noi ce utilizeaza doar atribute categoriale
n Agregarea: sumarizarea n Tehnici de discretizare
n Generalizarea: incadrarea in ierarhii de concepte ¨ Metode de binning – equal-width, equal-frequency
¨ Metode bazate pe entropie

Preprocesarea Datelor 21 Preprocesarea Datelor 23

Reducerea datelor Preprocesarea Datelor

n Datele pot fi prea mari pentru a fi minate
n Reducerea
¨ Obtinerea unei reprezentari reduse ca si volum a setului de
date dar care sa producă aceleasi rezultate in urma
analizei
n Strategii de reducere
¨ Reducerea dimensionalitati — înlăturarea atributelor
nerelevante
¨ Agregarea și clusterizarea
¨ Eșantionarizarea

Preprocesarea Datelor 22 Preprocesarea Datelor 24

 Data Warehouse –Date orientate-subiect

n Un data warehouse este organizat în jurul subiectelor majore,

precum cumpărator, produs, vânzări
Data warehouse
n Un data warehouse se concentrează pe modelarea şi analiza
datelor necesare luării deciziilor, şi nu pe procesarea
tranzacţiilor de zi cu zi.
n Furnizează o formă simplă şi concisă a noţiunilor/subiectelor,
eliminând datele nerelevante în luarea deciziilor

Data Warehouse 3

Ce este un Data Warehouse? Data Warehouse – Date integrate

n Data Warehouse = Depozit de date n Un Data Warehouse se obţine integrând date
n Există multiple definiţii, fiind dificil a se da o definitie riguroasă
eterogene ce provin din surse multiple
¨ Baze de date relaţionale, fişiere brute, înregistrări ale
¨ O bază de date utilizată în luarea deciziilor menţinută separat de baza de date
tranzacţiilor online
operaţională a unei organizaţii
n Sunt aplicate tehnici de curăţire şi integrare asupra
¨ Permite procesarea informaţiilor furnizând o platformă solidă pentru consolidare,
acestora:
consultare a datelor istorice în vederea analizei.
¨ Asigurarea consistenţei numelor, structurilor de codificare,
n “Un data warehouse este o colecţie de date orientate-subiect, integrate, timp- unităţilor de măsură, etc.
variante, şi nevolatile ce ajută în managementul luării deciziilor”- W. H. Inmon ¨ Atunci când datele sunt memorate în data warehouse se
realizează o convertire a lor.

Data Warehouse 2 Data Warehouse 4

 OLTP (On-line Transaction Processing) vs.
Data Warehouse – Date Timp-variante
OLAP (On-line Analytical Processing)
OLTP OLAP
n Orizontul de timp pentru datele din data warehouse este semnificativ mai
utilizatori Functionari, muncitori Analisti, factori de decizie, directori
mare decât al celor din sistemele operaţionale scop Operatii de zi cu zi Operatii pentru luarea de decizii
¨ Baza de date operaţională: valorile curente ale datelor design-ul BD orientata-aplicatie orientata-subiect
date curente, up-to-date istorice,
¨ Datele dintr-un data warehouse: funizează informaţiile din perspectivă istorică detaliate sumarizate, multidimensionale
(ex, ultimii 5-10 ani) integrate, consolidate
utilizare repetitiva ad-hoc
n Datele dintr-un data warehouse acces read/write Scanari multiple
index/hash pe prim. key
¨ Conțin chei ce implică explicit sau implicit un element legat de timp unitatea de lucru Interogari, transacti simple Interogari complexe
¨ Chiar dacă baza de date operaţională nu conţine “elementul timp” nr. de inregistrari zeci milioane
accesate
nr. useri mii sute
Dimensiune DB 100MB-GB 100GB-TB

Data Warehouse 5 Data Warehouse 7

Data Warehouse: Arhitectura multi-nivel

Data Warehouse – Date Nevolatile
Monitor OLAP Server
n Datele transformate sunt fizic memorate separat de datele din mediul Other Metadata &
operaţional sources Integrator
n Spre deosebire de datele operaţionale care necesită actualizări, operaţiile Analysis
cu datele dintr-un data warehouse odată creat sunt în general de citire
Operational Extract Query
DBs Transform Data Serve
¨ Nu mai este necesar un sistem de control al concurenţei si procesarea Load Reports
tranzacţiilor Refresh
Warehouse Data mining
¨ Necesită doar două operaţii:
n Crearea iniţială a datelor şi accesarea datelor

Data Marts

Data Sources Data Storage OLAP Engine Front-End Tools

Data Warehouse 6 Data Warehouse 8
8
 Data cube (exemplu)
Modelul de date multidimesional
Total annual sales
Date
sum of TVs in U.S.A.

t
2Qtr 3Qtr

uc
n Un data warehouse utilizează un model model multidimensional de date în care datele sunt 1Qtr 4Qtr
TV

od
organizate sub foma unui cub n-dimensional (hypercub) U.S.A
PC

Pr
VCR

Country
n Un data cub (eng. data cube) permite modelarea si vizualizarea datelor în dimensiuni
multiple. El este definit de dimensiuni şi fapte. sum
Canada
n Dimensiunile sunt perspectivele sau entitățile unei organizatii pentru care dorim să păstram
înregistrări
Mexico
n Faptele sunt măsuri numerice ce pot fi văzute ca niște cantități utilizate pentru a analiza
relațiile dintre dimensiuni
n În literatura de specialitate, un cub n-dimesional se numeste cuboid de bază. Cuboidul 0-
sum
dimensional, care retine cel mai inalt nivel de sumaziare, se numeste apex cuboid (cuboid
vârf). Laticea de cubizi formează un data cub.

Data Warehouse 9 Data Warehouse 11

Modelul de date multidimesional (exemplu) Laticea de cuboizi (exemplu)

n Data warehouse ce contine vanzarile (sales) dintr-un all

0-D (apex) cuboid
magazin product date country
1-D cuboids
¨ Tabelele de dimensiuni item (item_name, brand, type),
product,date product,country date, country
sau time(day, week, month, quarter, year)
2-D cuboids
¨ Tabela de fapte contine măsuri (precum dollars_sold,
volumul de vanzari în dolari, units_sold, nr de unitati 3-D (base) cuboid
product, date, country
vandute)

Data Warehouse 10 Data Warehouse 12

 Scheme pentru bazele de date
Schema Fulg de Zapada
multidimensionale time
item
time_key
day item_key supplier
n Modelarea data warehouse-urilor: dimensiuni & măsuri Sales Fact Table
day_of_the_week item_name supplier_key
¨ Schema Stea: O tabelă principală de fapte este conectata cu o month time_key brand supplier_type
mulțime de tabele ce reprezintă dimensiuni quarter type
year item_key supplier_key
¨ Schema fulg de zăpadă (Snowflake) : O rafinare a schemei stea in
branch_key
care anumite dimesiuni ierarhice sunt normalizate într-o multime de branch location
tabele de dimensiuni, formând un fulg de zapada location_key
location_key
branch_key
¨ Constelatie de fapte: Exista mai multe tabele de fapte care partajază units_sold street
branch_name
city_key city
tabelele de dimensiuni, poate fi vazută ca o colecție de scheme stea, branch_type dollars_sold
de aici și numele de schema galaxie sau constelatie de fapte city_key
avg_sales
city
Measures state_or_prov
Data Warehouse 13 Data Warehouse
ince 15
country

time
Schema stea time
Schema Constelatie
item time_key item Shipping Fact Table
time_key day item_key
day item_key day_of_the_week Sales Fact Table time_key
item_name
day_of_the_week Sales Fact Table item_name month brand
month quarter time_key item_key
time_key brand type
year supplier_type
quarter type shipper_key
item_key item_key
year supplier_type
branch_key from_location
branch_key
branch location branch location_key to_location
location_key location
branch_key location_key branch_key location_key dollars_cost
units_sold
branch_name units_sold street branch_name street
city branch_type dollars_sold city
units_shipped
branch_type dollars_sold
state_or_province province_or_state
avg_sales country shipper
avg_sales country
Measures shipper_key
Measures shipper_name
Data Warehouse 14
location_key
shipper_type
Măsuri într-un Data Cub Operatii OLAP in Modelul Multidimensional

n Roll up (drill-up): sumarizarea datelor

n Definitie: O măsură într-un data cub este
¨ Obținută prin urcarea in ierahie sau reducerea dimensiuni
funcție numerică ce poate fi evaluată în orice n Roll down (Drill down): operatia inversa operatiei de roll-up
punct din spațiul cubului. Valoarea ei este (detalierea)
¨ Coborârea în ierarhia de concepte sau introducerea de
calculată prin agregarea datelor dimensiuni noi
corespunzatoare perechilor de valori ale n Slice/dice: este operatia de selectare dupa o dimensiune/mai
multe dimensiuni a cubului
dimensiunilor definite de punct. n Pivot (rotate):
¨ Reorientarea axelor cubului pentru a obtine o reprezentare
alternativă a datelor

Data Warehouse 17 Data Warehouse 19

Clasificarea măsurilor
n Distributive: daca rezultatul obtinut prin aplicarea functiei asupra a n partitii
de valori ce le dorim agregate este acelasi cu cel obtinut prin aplicarea
functiei tuturor valorilor fara a fi partitionate
n Ex, count(), sum(), min(), max()
n Algebrice: daca ele pot fi calculate ca o funcție algerică cu M argumente
(unde M este un întreg pozitiv), argumente obtinute prin aplicarea unei
functii de agregare distributive
n Ex., avg()=sum()/count(), standard_deviation()
n Holistice: nu există nici o funcție algebrică cu M argumente care să
descrie calculul ei
n Ex., median(), mode(), rank()

Data Warehouse 18 Data Warehouse 20

 Specificarea Task-urilor Data Mining

n Un task data mining este o formă de analiză ce se poate efectua asupra unor date

¨ Poate fi specificat printr-o interogare a sistemului de data mining

Primitive Data Mining n O interogare data mining este definită de următoarele primitive:

¨ Definirea datelor relevante

¨ Tipurile de cunoştinţe ce vor fi minate

¨ Cunoştinţe apriorii

¨ Măsuri de relevanţă

¨ Modalităţi de vizualizare

Primitive Data Mining 3

De sunt Primitivele Data Mining? Definirea datelor relevante

n Este posibilă extragerea tuturor cunoştinţelor (şabloane, asocieri, etc)
dintr-o bază de date în mod automat? n Definirea datelor relevante – specificarea fragmentelor bazei de date
¨ NU! Imposibil deoarece acestea pot fi foarte multe, multe neinteresanate
n Procesul de minare a datelor trebuie să fie unul interactiv asupra cărora se va executa task-ul de minare
¨ Utilizatorul va indica ce tip de patternuri/cunoştinte vor fi minate
n Utilizatorul va “comunica” cu sistemul de data mining pe baza unui set de ¨ Numele bazei de date sau data warehouse-ului
primitive data mining elaborate pentru a facilita descoperirea eficientă a
cunoştinţelor ¨ Numele tabelelor sau data cuburilor
n Aceste primitive sunt incluse intr-un limbaj de interogare data mining
(DMQL = Data Mining Query Language) ¨ Criterii de selecţie a datelor
¨ iteracţiunea user-ului cu sistemul devine mult mai flexibilă
¨ Constituie baza pentru design-ul interfeţelor grafice cu utilizatorul ¨ Atribute sau dimensiuni relevante
¨ standardizarea sistemelor industriale de data mining
¨ Criterii de grupare a datelor

Primitive Data Mining 2 Primitive Data Mining 4

Tipurile de cunoştinţe ce vor fi minate
Măsuri de relevaţă
n Măsurile de relevanţă sau de calitate sunt utilizate pentru elimina
n Se specifică funcţiile de data mining ce se vor executa: patternurile neinteresante.
n Sunt utile pentru a ghida procesul de minare sau dupa descoperirea
¨ Caracterizare patternurilor pentru a evalua relevanţa sau calitatea acestora
¨ Discriminare n Simplitate
ex., lungimea regulii de asociere, dimensiunea arborelui de decizie
¨ Asociere n Certitudinea
ex., confidenţa, P(A|B) = #(A and B)/ #(B), acurateţea clasificărilor,
¨ Clasificare/predicţie factorul de încredere, etc.
¨ Grupare (Clusterizare) n Utilitatea
ex, suportul unei reguli de asociere
¨ Etc. n Noutatea
patternuri necunoscute anterior, surprinzatoare

Primitive Data Mining 5 Primitive Data Mining 7

Cunoştinţe apriorii Modalităţi de vizualizare

n În definirea task-ului data mining utilizatorul poate specifica cunoştinţe anterioare n Se referă la modul în care sunt reprezentate patternurile descoperite.
cu privire la datele ce vor fi minate. Acestea sunt utile în ghidarea procesului de
Utilizatorul poate specifica diferite forme de reprezentare
minare
¨ Ex: reguli, tabele, chart-uri, arbori de decizie, cuburi de date, etc.
n Ierarhii de concepte
¨ Ex: strada < oras < judet < tara n Ierarhiile de concepte sunt de asemenea importante
n Ierarhii determinate de multimi de grupare ¨ Cunostintele descoperite pot fi mult mai ușor de înteles când sunt reprezentate
¨ Ex: {20-39} = tanar, {40-59} = varsta-medie la un nivel înalt de abstractizare
n Ierarhii derivate din concepte ¨ Operațiile de drill up/down, pivotare, slicing şi dicing funizează perspective
¨ email: mihaiug@[Link] login-name < departament < universitate < tara
diferite ale datelor
n Ierarhii bazate pe reguli
¨ profit_mic (X) <= pret(X, P1) and cost (X, P2) and (P1 - P2) < $50

Primitive Data Mining 6 Primitive Data Mining 8

 Data Mining Query Language (DMQL)
DMQL: Specificarea datelor relevante
n Motivare
¨ Un DMQL poate furniza abilitatea de specifica operațiile de data n use database database_name, or use data warehouse
mining
data_warehouse_name
¨ Furnizarea un limbaj standard similar limbajului SQL
n Baza pentru dezvoltarea sistemelor data mining
n from relation(s)/cube(s) [where condition]
n Facilitează schimbul de informație, transferul de tehnologie, n in relevance to att_or_dim_list
comercializarea şi acceptarea la scara largă
n order by order_list
n Design
n group by grouping_list
n DMQL este realizat cu ajutorul primitivelor data mining descrise anterior
n having condition

Primitive Data Mining 9 Primitive Data Mining 11

DMQL: Specificarea datelor relevante

Sintaxa DMQL
(cont)
n Sintaxa pentru specificarea Exempu:
use database AllElectronics db
¨ datelor relevante task-ului in relevance to [Link], [Link], [Link], [Link]
¨ tipul de cunostinte ce vor fi minate from customer C, item I, purchases P, items sold S
where [Link] ID = [Link] ID and [Link] ID = [Link] ID and
¨ ierarhiilor de concepte [Link] ID = [Link] ID
¨ masurile de evaluare and [Link] = " Canada"
group by [Link]
¨ prezentarea şi vizualizarea patternurilor (sursa: Data Mining: Concepts and Techniques, Jiawei Han,
n O interogare DMQL = specificarea tuturor Micheline Kamber 1st Ed, 2001, ch. 4)

Primitive Data Mining 10 Primitive Data Mining 12

DMQL: specificarea tipului de DMQL: Specificarea Ierarhiilor de
cunoştinţe ce vor fi minate Concepte
n Caracterizare n Sintaxa pentru specificarea ierahiilor de concepte:
Mine_Knowledge_Specification ::= use hierarchy <hierarchy> for <attribute_or_dimension>
mine characteristics [as pattern_name]
n In functie de tipul de ierahie utilizam diferite sintaxe
analyze measure(s)
¨ Ierarhii definite de schema
n Discriminare
define hierarchy time_hierarchy on date as [date,month,quarter,year]
Mine_Knowledge_Specification ::=
¨ Ierarhii definite pring guparea de multimi
mine comparison [as pattern_name]
for target_class where target_condition define hierarchy age_hierarchy for age on customer as
{versus contrast_class_i where contrast_condition_i} level1: {young, middle_aged, senior} < level0: all
analyze measure(s)
level2: {20, ..., 39} < level1: young
Ex mine comparison as purchaseGroups
level3: {40, ..., 59} < level2: middle_aged
for bigSpenders where avg([Link]) >= $100
versus budgetSpenders where avg([Link]) < $100
level4: {60, ..., 89} < level3: senior
analyze count

Primitive Data Mining 13 Primitive Data Mining 15

DMQL: specificarea tipului de DMQL: Specificarea Ierarhiilor de

cunoştinţe ce vor fi minate (cont.) Concepte (cont)
n Asociere ¨ Ierarhi bazate pe reguli
Mine_Knowledge_Specification ::= define hierarchy profit_margin_hierarchy on item as
mine associations [as pattern_name]
level_1: low_profit_margin < level_0: all
[matching <metapattern>]
if (price - cost)< $50
Ex. mine associations as buyingHabits
matching P(X:custom, W) ^ Q(X, Y)=>buys(X, Z) level_1: medium-profit_margin < level_0: all
n Clasificare if ((price - cost) > $50) and ((price - cost) <= $250))
Mine_Knowledge_Specification ::= level_1: high_profit_margin < level_0: all
mine classification [as pattern_name]
analyze classifying_attribute_or_dimension if (price - cost) > $250
§ Alte tipuri
clusterizare, predictie …

Primitive Data Mining 14 Primitive Data Mining 16

DMQL: Specificarea Măsurilor de Evaluare (eng.
Interestingness Measures) DMQL: Exemplu de interogare
use database AllElectronics_db
n Masurile de evaluare sau pragurile pot fi exprimate prin use hierarchy location_hierarchy for [Link]
enunturi de forma: mine characteristics as customerPurchasing
with <interest_measure_name> threshold = threshold_value analyze count%
in relevance to [Link], [Link], I.place_made
n Exemplu: from customer C, item I, purchases P, items_sold S, works_at W,
branch
with support threshold = 0.05 where I.item_ID = S.item_ID and S.trans_ID = P.trans_ID
with confidence threshold = 0.7 and P.cust_ID = C.cust_ID and P.method_paid = ``AmEx''
(specificarea pragurilor pentru suportul si confidenta unei reguli de and P.empl_ID = W.empl_ID and W.branch_ID = B.branch_ID
and [Link] = ``Canada" and [Link] >= 100
asociere) with noise threshold = 0.05
display as table

Primitive Data Mining 17 Primitive Data Mining 19

DMQL: Specificarea modului de reprezentare

n Specificarea modului de afisare a patternurilor descoperite:

display as <result_form>

n Pentru a facilita vizualizarea interactiva pe diferite nivele:

Multilevel_Manipulation ::= roll up on attribute_or_dimension
| drill down on attribute_or_dimension
| add attribute_or_dimension
| drop attribute_or_dimension

Primitive Data Mining 18

 Descrierea conceptelor vs. OLAP
n Descrierea conceptelor:
Descrierea Conceptelor: ¨ poate gestiona tipuri de date complexe (numerice sau
nominale), agregări ale acestora
Caracterizare şi Comparare ¨ un proces automat

n OLAP:
¨ este restricţionat la un număr de dimensiuni, agregările
realizându-se în general asupra atributelor numerice
¨ Este un proces controlat de user

Descrierea Conceptelor 3

Ce este Descrierea Conceptelor? Caracterizarea prin generalizare

n Din punct de vedere al analizei datelor, data mining se poate n Generalizarea datelor
împărţi în două categorii: ¨ Este un proces care abstractizează mulţimea de date relevante taskului dintr-o
¨ Data mining descriptiv: care realizează descrierea conceptelor într-un bază de date de la concepte de nivel scăzut de abstractizare la concepte de
mod concis, sumar, informativ, prezentând proprietăţile esenţiale ale
datelor nivel înalt. 1
2
¨ Data mining predictiv: analizează datele pentru a construi modele pe 3
baza cărora se fac predicţii ale comportamentului mulţimilor noi de 4
date Nivele de Concepte
5
n Descrierea Conceptelor se realizează prin:
¨ Metode:
¨ Caracterizare: realizează un sumar concis şi succint al unui set de
date n Bazate pe Data Cube (OLAP)
¨ Comparare: furnizează descrieri comparând două sau mai multe seturi n Bazate pe Inducţia Orientată Atribut
de date; furnizează descrieri prin comparare cu alte mulțimi de date.

Descrierea Conceptelor 2 Descrierea Conceptelor 4

 Generalizarea bazată pe Inducţia Orientată Atribut
Generalizarea bazată pe Data Cube

n Datele sunt memorate într-un data cub n A fost propusă în 1989 (KDD ‘89 workshop)
n Nu este limitata la date categoriale şi nici la măsuri specifice.
n Se identifică calcule ce necesită efort de calcul mare
n Cum se realizează?
¨ e.x., count( ), sum( ), average( ), max( ) ¨ Se extrag datele relevante task-ului utilizând interogari specifice bazelor de
n Se efectuează aceste calcule și se memorează date relaţionale
¨ Se efectuează generalizarea prin eliminarea de atribute sau prin generalizarea
rezultatele în data cuburi atributelor
n Generalizarea şi specializarea poate fi efectuată prin ¨ Realizarea agregărilor prin unirea tuplurilor identice sau generalizarilor
operații de roll-up şi drill-down asupra cubului cumulându-se numărul acestora
¨ Prezetarea interactivă utilizatorului
n Constituie o modalitate eficientă de generalizare

Descrierea Conceptelor 5 Descrierea Conceptelor 7

Generalizarea bazată pe Data Cube (cont.) Exemplu

n DMQL: Sa se descrie caracteristicile generale ale absolventilor de master
n Limitări din baza de date Big-University
use Big_University_DB
¨ Putem manipula numai atribute (dimensiuni) non- mine characteristics as “Science_Students”
numerice simple, pot fi agregate doar valori in relevance to name, gender, major, birth_place, birth_date, residence,
phone#, gpa
numerice. from student
where status in “graduate”
¨ Absența unui mecanism de analiză inteligent care n Fraza SQL ce selecteaza datele relevate taskului:
sa ne spună care atribut trebuie generalizat Select name, gender, major, birth_place, birth_date, residence, phone#, gpa
from student
where status in {“Msc”, “MBA”, “PhD” }

Descrierea Conceptelor 6 Descrierea Conceptelor 8

 Exemplu: Caracterizarea claselor Eliminarea atributelor
Name Gender Major Birth-Place Birth_date Residence Phone # GPA

Initial Jim M CS Vancouver,BC, 8-12-76 3511 Main St., 687-4598 3.67

Woodman Canada Richmond
Relation Scott M CS Montreal, Que, 28-7-75 345 1st Ave., 253-9106 3.70 n Eliminarea atributelor se bazează pe urmatoarea
Lachance
Laura Lee F Physics
Canada
Seattle, WA, USA 25-8-70
Richmond
125 Austin Ave., 420-5232 3.83
regula:
… … … … … Burnaby
…
… … Daca în relatia (tabela) initiala de lucru exista un
Removed Retained Sci,Eng,
Bus
Country Age range City Removed Excl,
VG,..
atribut A cu un numar foarte mare de valori distincte
G end er M ajor Birth_region A ge_range R esid ence G PA C ount si
Prime M Science C anada 20-25 R ichm ond V ery-good 16 (1) fie nu exista nicio relatie de generalizare a atributului
Generalized F Science Foreign 25-30 Burnab y Excellent 22
Relation … … … … … … …
(adica nu exista nicio ierarhie de concepte definita pe el)
sau
Birth_Region
Canada Foreign Total (2) concepte sale de la un nivel superior pot fi exprimate in
Gender functie de alte atribute
M 16 14 30
F 10 22 32
atunci atributul respectiv poate fi eliminat din relatie.
Total 26 36 62

Descrierea Conceptelor Descrierea Conceptelor 11

Inducţia Orientată Atribut Generalizarea atributelor

n Inducţia Orientată Atribut este o generalizare a n Se bazeaza pe urmatoarea regula: Daca in relatia (tabela) de
lucru initiala exista un atribut A cu un numar foarte mare de
datelor ce poate fi realizată prin: valori distincte, si exista o multime de operatori de
¨ Eliminarea de atribute generalizare a atributului atunci se selecteaza unul dintre
acestia si se generalizeaza A.
¨ Generalizarea atributelor
n In functie de atribute sau de aplicatiile implicate un user poate
sa decida ca anumite atribute sa se retina la un nivel mic de
abstactizare, in timp ce pentru altele se prefera un grad inalt
de abstractizare. Controlul acestui proces se numeste
controlul generalizarii atributelor.

Descrierea Conceptelor 10 Descrierea Conceptelor 12

Caracterizarea prin Comparare a Claselor Compararea claselor: Etape (cont.)
3. Generalizarea sincronă: asupra clasei target se aplică o
n Compararea sau discriminarea claselor se generalizare pana la un nivel controlat de utilizator sau de
ocupa cu determinarea caracteristicilor ce pragul dimensiunii specificat de un expert rezultând un cub
(relatie) generalizat(a) a clasei target. Conceptele din
disting o clasa (clasa ţintă sau target) de o clasele de contrast sunt generalizate şi ele la acelasi nivel
cu cele din clasa target rezultand un cub (relatie)
multime de alte clase de contrast. generalizat(a) a clasei de contrast.
n Pentru a realiza acest lucru este necesar ca, 4. Prezentarea comparatiei: rezultatul comparatiei poate fi
vizualizat sub forma de tabel, grafice sau [Link]
clasa tinta si clasele de contrast sa fie include de regula masuri de contrast (ex: count %) care
refelecta comparatia dintre clasa target si clasele de
comparabile contrast.

Descrierea Conceptelor 13 Descrierea Conceptelor 15

Compararea claselor: Etape Exemplu

1. Colectarea datelor: multimea de date relevate din
n Task
B.D. este colectata cu ajutorul interogarilor,
¨ Sa se compare absolventii de master (graduate) cu cei de
procesata si partitionata in clasa target si una sau
licenta (undergraduate)
mai multe clase de contrast.
n DMQL query
2. Analiza relevantei dimensiunilor: daca avem multe use Big_University_DB
dimensiuni trebuie realizata o analiza a acestora si mine comparison as “grad_vs_undergrad_students”
in relevance to name, gender, major, birth_place, birth_date, residence, phone#, gpa
retinute cele mai relevante pentru analiza ulterioara for “graduate_students”
where status in “graduate”
versus “undergraduate_students”
where status in “undergraduate”
analyze count%
from student

Descrierea Conceptelor 14 Descrierea Conceptelor 16

Reguli de Asociere

Mihai Gabroveanu

Mihai Gabroveanu Reguli de Asociere

Cuprins

1 Introducere

2 Clasificarea regulilor de asociere

3 Reguli de asociere boolene

Concepte de bază
Determinarea itemseturilor frecvente
Algoritmul Apriori
Generarea regulilor de asociere

Mihai Gabroveanu Reguli de Asociere

 Introducere
Clasificarea regulilor de asociere
Reguli de asociere boolene

Determinarea regulilor de asociere boolene

Extragerea regulilor de asociere reprezintă o metodă

nesupervizată din data mining care permite identificarea de
asocieri interesante, corelaţii ı̂ntre diferite atribute sau obiecte,
paternuri frecvente existente ı̂n baze de date tranzacţionale
Problema a fost introdusă Rakesh Agrawal, Imielinski, şi
Swami ı̂n:
Mining association rules between sets of items in large
databases. In Proc. of the ACM SIGMOD Conference on
Management of Data, pp. 207–216, Washington, D.C., May
1993.

Mihai Gabroveanu Reguli de Asociere

 Introducere
Clasificarea regulilor de asociere
Reguli de asociere boolene

Determinarea regulilor de asociere boolene

Motivatia: Analiza coşului de cumpărături (Market Basket Analysis)

TID Lista de produse

1 paine, lapte
2 paine, scutece, bere, oua
3 lapte, scutece, bere, carne
4 paine, unt, oua, lapte
5 paine, lapte, scutece, bere
6 lapte, scutece, bere
Bază de date cu tranzactii

Regulă de asociere booleană

lapte ∧ scutece ⇒ bere (1)

Semnificaţia Clienţii care au cumpărat lapte şi scutece au cumpărat deasemenea

şi bere ı̂n aceeaşi tranzacţie.

Mihai Gabroveanu Reguli de Asociere

 Introducere
Clasificarea regulilor de asociere
Reguli de asociere boolene

Tranzacţii - Reprezentare

Tranzacţiile pot fi reprezentate binar astfel:

TID paine lapte scutece oua bere carne

1 1 1 0 0 0 0
2 1 0 1 1 1 0
3 0 1 1 0 1 1
4 1 1 0 1 0 0
5 1 1 1 0 1 0
6 0 1 1 0 1 0
Tranzacţii - Reprezentarea Binara

Semnificatie: 1 = Produsul este prezent, 0 = Produsul nu e

prezent in tranzactie
Nu ne interesează cantitatea

Mihai Gabroveanu Reguli de Asociere

 Introducere
Clasificarea regulilor de asociere
Reguli de asociere boolene

Aplicaţii ale regulilor de asociere

Analiza coşului de cumpăraturi:

Realizarea promoţiilor
Designul catalogelor
Arajarea produselor ı̂n magazin
...

Mihai Gabroveanu Reguli de Asociere

 Introducere
Clasificarea regulilor de asociere
Reguli de asociere boolene

Clasificarea pe baza tipurilor valorilor implicate ı̂n regulă

Reguli de asociere boolene (crisp): asocierea se referă la
prezenţa sau absenţa produselor.
popcorn ⇒ bere [suport = 7%, confidenta = 74%] (2)
Reguli de asociere cantitative: aceste reguli descriu asocieri
ı̂ntre atribute cantitative sau cantităţi de articole. În acest
caz, valorile atributelor sunt partiţionate ı̂n intervale.
varsta(X , ”20...30”) ∧ venit(X , ”2000...3000”) ⇒ masini(X , ”0..1”) (3)

Reguli de asociere nominale (categoriale): atributele referite

de reguli sunt nominale, ca ocupaţie sau sex.
ocupatie(X , ”student”)∧sex(X , ”barbat”) ⇒ joaca(X , ”basket”)
(4)
Mihai Gabroveanu Reguli de Asociere
 Introducere
Clasificarea regulilor de asociere
Reguli de asociere boolene

Clasificarea pe baza numărului de dimensiuni implicate ı̂n

regulă

Reguli de asociere unidimensionale: atributele implicate ı̂n

reguli referă o singură dimensiune.
cumpara(X , ”bere”) ∧ cumpara(X , ”cola”) ⇒ cumpara(X , ”popcorn”) (5)

Dimensiunea referită este cumpără.

Reguli de asociere multidimensionale: regulile referă două sau
mai multe atribute.
varsta(X , ”20...30”) ∧ venit(X , ”2000...3000”) ⇒ masini(X , ”0..1”) (6)

Dimensiunile referite sunt vârsta,venit şi maşini.

Mihai Gabroveanu Reguli de Asociere

 Introducere
Clasificarea regulilor de asociere
Reguli de asociere boolene

Clasificarea pe baza nivelelor de abstractizare ale datelor

Reguli de asociere uninivel: regulile referă atribute sau articole

aflate pe acelaşi nivel de abstractizare, adică pe nivelul cel mai
de jos al unei ierarhii.
cumpara(X , ”Schlossgold”) ∧ cumpara(X , ”Pepsi”) ⇒ cumpara(X , ”Nescafé”)
(7)

Reguli de asociere multinivel: regulile referă atribute sau

articole aflate pe nivele de abstractizare diferite ale unei
ierahii.

cumpara(X , ”bere fara alcool”) ⇒ cumpara(X , ”suc”) (8)

Mihai Gabroveanu Reguli de Asociere

 Concepte de bază
Introducere
Determinarea itemseturilor frecvente
Clasificarea regulilor de asociere
Algoritmul Apriori
Reguli de asociere boolene
Generarea regulilor de asociere

Definiţia Formală: Itemset-uri, Tranzacţii

Fie I = {i1 , . . . , im } o mulţime de m articole distincte sau atribute
boolene distincte.
Itemset, k-Itemset
O submulţime de itemi (atribute) X = {i1 , . . . , ik } ⊆ I

Tranzacţie
O mulţime de itemi T ⊆ I, căreia ı̂i asociem un identificator unic
TID.

Acoperirea unui itemset X

Multimea tranzactiilor din baza de date ce conţin pe X
Notatie
cover (X , DB) = DX = {T ∈ DB|X ⊆ T } (9)

Mihai Gabroveanu Reguli de Asociere

 Concepte de bază
Introducere
Determinarea itemseturilor frecvente
Clasificarea regulilor de asociere
Algoritmul Apriori
Reguli de asociere boolene
Generarea regulilor de asociere

Regulă de Asociere

Regulă de asociere
Fie X şi Y două itemset-uri. O regulă de asociere este o
implicaţie de forma X ⇒ Y , unde X ⊂ I, Y ⊂ I, şi X ∩ Y = ∅.

Semnificaţia
Dacă o tranzacţie conţine pe X , atunci ea va conţine de asemenea
şi pe Y

Mihai Gabroveanu Reguli de Asociere

 Concepte de bază
Introducere
Determinarea itemseturilor frecvente
Clasificarea regulilor de asociere
Algoritmul Apriori
Reguli de asociere boolene
Generarea regulilor de asociere

Evaluarea calitatii regulilor de asociere

Calitatea unei reguli de asociere se poate exprima prin intermediul

unor măsuri de calitate care arată gradul de importanţă al acesteia.
Două dintre acestea sunt esenţiale:
suportul
confidenţa
propuse de Agrawal şi Srikant.

Mihai Gabroveanu Reguli de Asociere

 Concepte de bază
Introducere
Determinarea itemseturilor frecvente
Clasificarea regulilor de asociere
Algoritmul Apriori
Reguli de asociere boolene
Generarea regulilor de asociere

Suportul unui itemset

Fie X ⊂ I un itemset.
Suportul Relativ al unui Itemset
Definim suportul relativ sau simplu suportul itemsetului X ca fiind procentul
tranzacţiilor din DB care conţin itemset-ul X .

|{T ∈ DB|X ⊆ T }| |DX |

supp(X ) = = = P(X ) (10)
|DB| |DB|

Adica, probabilitatea de apariţie a itemset-ului X ı̂n baza de date DB.

Suportul Absolut al unui Itemset (eng. support count)

Definim suportul absolut sau frecvenţa itemsetului X ca fiind numărul de tranzacţii
din DB care conţin itemset-ul X .

supp#(X ⇒ Y ) = |DX | (11)

Un itemset ce are suportul mai mare decat un prag minim dat se numeste itemset
frecvent.
Mihai Gabroveanu Reguli de Asociere
 Concepte de bază
Introducere
Determinarea itemseturilor frecvente
Clasificarea regulilor de asociere
Algoritmul Apriori
Reguli de asociere boolene
Generarea regulilor de asociere

Suportul unei reguli

Fie X ⇒ Y o regulă de asociere.

Suportul Relativ
Definim suportul relativ sau simplu suportul ca fiind procentul tranzacţiilor din DB
care conţin atât itemset-ul X cât şi itemset-ul Y (probabilitatea ca ambele itemset-uri
X respectiv Y să apară ı̂mpreună ı̂n DB.

|DX ∩ DY | |DX ∪Y |
supp(X ⇒ Y ) = = = P(X ∪ Y ) (12)
|DB| |DB|

Suportul Absolut
Definim suportul absolut al regulii de asociere X ⇒ Y ca fiind numărul de tranzacţii
din DB care conţin atât itemset-ul X cât şi itemset-ul Y .

supp#(X ⇒ Y ) = |DX ∩ DY | (13)

Mihai Gabroveanu Reguli de Asociere

 Concepte de bază
Introducere
Determinarea itemseturilor frecvente
Clasificarea regulilor de asociere
Algoritmul Apriori
Reguli de asociere boolene
Generarea regulilor de asociere

Confidenţa unei reguli

Fie X ⇒ Y o regulă de asociere.

Confidenţa
Definim confidenţa regulii de asociere X ⇒ Y ca proporţia (procentul) de tranzacţii
ce conţin itemset-ul X din DB care conţin de asemenea şi itemset-ul Y (probabilitatea
condiţionată a lui Y dându-se X , P(Y /X )):

|DX ∩ DY |
conf (X ⇒ Y ) = = P(Y /X ) (14)
|DX |

Regulă de asociere tare

O regulă de asociere care are suportul şi confidenţa mai mare decât un
prag de suport minim (minsup) şi respectiv un prag de confidenţă minim
(minconf )

Mihai Gabroveanu Reguli de Asociere

 Concepte de bază
Introducere
Determinarea itemseturilor frecvente
Clasificarea regulilor de asociere
Algoritmul Apriori
Reguli de asociere boolene
Generarea regulilor de asociere

Reguli de Asociere Boolene. Exemplu

1 I = {paine, unt, oua, lapte}

TID Lista de produse 2 DB = {T1 , T2 , T3 , T4 , T5 , T6 }
1 unt, oua, lapte
2 paine, unt 3 Doua = {T1 , T3 , T4 , T5 , T6 }
3 paine, oua, lapte
4 paine, unt, oua, lapte
5 oua, lapte
4 D{oua,lapte} = {T1 , T3 , T4 , T5 }
6 paine, oua
Bază de date cu tranzacţii 5 {oua} ⇒ {lapte}
Suport
 
 
D{oua,lapte}  |{T1 ,T3 ,T4 ,T5 }|
supp({oua} ⇒ {lapte}) = |DB|
= |DB|
= 64 = 0.66

Semnificaţie: 66% din clienţi au cumpărat oua şi lapte ı̂n acelaşi timp

Confidenţa

|{T1 ,T3 ,T4 ,T5 }|

conf ({oua} ⇒ {lapte}) = = 54 = 0.80
|{T1 ,T3 ,T4 ,T5 ,T6 }|
Semnificaţie: din totalul clienţilor care au cumpărat oua 80% au cumpărat şi lapte

Mihai Gabroveanu Reguli de Asociere

 Concepte de bază
Introducere
Determinarea itemseturilor frecvente
Clasificarea regulilor de asociere
Algoritmul Apriori
Reguli de asociere boolene
Generarea regulilor de asociere

Minarea Regulilor de Asociere

Problema Minării Regulilor de Asociere Boolene
Dându-se o mulţime de itemi I, o bază de date DB peste I, un prag de
suport minim şi un prag de confidenţă minim, să se găsească mulţimea
tuturor regulilor de asociere tari.

Problema se descompune ı̂n două subprobleme:

1 determinarea tuturor itemset-urilor frecvente
2 generarea regulilor de asociere tari pe baza itemset-urilor frecvente
găsite la pasul anterior

Proprietatea Apriori
Dacă itemsetul X este frecvent ı̂n DB, atunci orice subitemset Y ⊆ X
nevid este de asemenea frecvent ı̂n DB.
Algoritmi: AIS, Apriori, FP-growth
Mihai Gabroveanu Reguli de Asociere
 Concepte de bază
Introducere
Determinarea itemseturilor frecvente
Clasificarea regulilor de asociere
Algoritmul Apriori
Reguli de asociere boolene
Generarea regulilor de asociere

Exemplu: Itemseturile frecvente din baza de date DB

Considerăm tranzacţiile din exemplul anterior, pragul de suport minim de
30% şi pragul de confidenţă minim de 60%. În tabelul urmator sunt
reprezentate toate itemset-urile frecvente ı̂n raport cu pragul de support
minim.

Itemset Suport Absolut Suport (%)

{paine} 4 66.66%
{unt} 3 50.00%
{oua} 5 83.33%
{lapte} 4 66.66%
{paine, unt} 2 33.33%
{paine, oua} 3 50.00%
{paine, lapte} 2 33.33%
{unt, oua} 2 33.33%
{unt, lapte} 2 33.33%
{oua, lapte} 4 66.66%
{paine, oua, lapte} 2 33.33%
{unt, oua, lapte} 2 33.33%

Tabela: Itemseturile frecvente din baza de date DB

Mihai Gabroveanu Reguli de Asociere

 Concepte de bază
Introducere
Determinarea itemseturilor frecvente
Clasificarea regulilor de asociere
Algoritmul Apriori
Reguli de asociere boolene
Generarea regulilor de asociere

Exemplu: regulile de asociere tari din baza de date DB

În tabelul de mai jos sunt reprezentate toate regulile de asociere

tari ı̂n raport cu pragul de suport şi confidenţă minim din DB.

Regula Confidenţa (%) Suport (%)

{oua} ⇒ {lapte} 80.0% 66.66%
{lapte} ⇒ {oua} 100.0% 66.66%
{oua} ⇒ {paine} 75.0% 50.00%
{paine} ⇒ {oua} 60.0% 50.00%
{oua} ⇒ {paine, lapte} 100.0% 33.33%

Tabela: Regulile de asociere tari din DB

Observatie: {oua} ⇒ {lapte} si {lapte} ⇒ {oua} au acelasi suport

insa confindenţa diferă!

Mihai Gabroveanu Reguli de Asociere

 Concepte de bază
Introducere
Determinarea itemseturilor frecvente
Clasificarea regulilor de asociere
Algoritmul Apriori
Reguli de asociere boolene
Generarea regulilor de asociere

Problema determinarii itemseturilor frecvente

Complexitate de calcul exponentiala
Daca avem o multime cu m itemi atunci se pot genera 2m − 1 itemseturi posibile

Laticea itemseturilor
Mihai Gabroveanu Reguli de Asociere
 Concepte de bază
Introducere
Determinarea itemseturilor frecvente
Clasificarea regulilor de asociere
Algoritmul Apriori
Reguli de asociere boolene
Generarea regulilor de asociere

Brute-force

O metodă trivială pentru determinarea itemset-urilor frecvente este

următoarea:
se generează toate cele 2m itemset-uri posibile din I
se scanează baza de date DB pentru a determina suportul
fiecărui itemset.
se retin itemseturile cu suportul mai mare sau egal decât
pragul de suport minim care vor reprezenta itemseturile
frecvente.
Complexitatea acestui algoritm este O(2m n).
Pentru m = 100 atunci numărul de itemseturi posibile este de
aproximativ 1.27 × 1030 .

Mihai Gabroveanu Reguli de Asociere

 Concepte de bază
Introducere
Determinarea itemseturilor frecvente
Clasificarea regulilor de asociere
Algoritmul Apriori
Reguli de asociere boolene
Generarea regulilor de asociere

Algoritmul Apriori

Algoritmul Apriori propus de Agrawal şi Srikant ı̂n 1994 este unul dintre
cei mai populari algoritmi pentru determinarea itemseturilor frecvente.
Lemma (Proprietatea Apriori)
Dacă itemsetul X este frecvent ı̂n DB, atunci orice subitemset Y ⊆ X
nevid este de asemenea frecvent ı̂n DB.

Demonstraţie.
Fie X un itemset frecvent. Presupunem prin reducere la absurd că itemsetul Y ⊆ X
nu este frecvent. Atunci, acest lucru ı̂nseamnă că numărul de tranzacţii care conţin pe
Y este mai mic decât frecvenţa minimă.
Deoarece X este obţinut din Y prin adaugarea de itemi, atunci numărul de tranzacţii
care ı̂l conţin pe X este mai mic sau egal decât numărul de tranzacţii care ı̂l conţin pe
Y . Prin urmare, frecvenţa itemsetului X este mai mică decât frecvenţa minimă, adică
X nu este un itemset frecvent. Acest rezultat contrazice presupunerea iniţială, deci Y
este un itemset frecvent.

Mihai Gabroveanu Reguli de Asociere

 Concepte de bază
Introducere
Determinarea itemseturilor frecvente
Clasificarea regulilor de asociere
Algoritmul Apriori
Reguli de asociere boolene
Generarea regulilor de asociere

Algoritmul Apriori

Proprietatea Apriori este o proprietate antimonotonă ı̂n sensul că dacă o

mulţime nu trece un test atunci nicio supramulţime a ei nu va trece
acelaşi test.
Corollary
Dacă un itemset X conţine un sub-itemset care nu este frecvent, atunci
itemsetul X nu este frecvent.

Corollary
Dacă un k-itemset conţine un (k − 1)-itemset cere nu este frecvent,
atunci el nu este frecvent.
În continuare vom nota cu Lk mulţimea tuturor k-itemseturilor frecvente,
si cu Ck mulţimea tuturor k-itemseturilor candidate la a fi frecvente.

Mihai Gabroveanu Reguli de Asociere

 Concepte de bază
Introducere
Determinarea itemseturilor frecvente
Clasificarea regulilor de asociere
Algoritmul Apriori
Reguli de asociere boolene
Generarea regulilor de asociere

Eliminarea itemseturilor infrecvente

Eliminarea itemseturilor infrecvente

Mihai Gabroveanu Reguli de Asociere

 Concepte de bază
Introducere
Determinarea itemseturilor frecvente
Clasificarea regulilor de asociere
Algoritmul Apriori
Reguli de asociere boolene
Generarea regulilor de asociere

Algoritmul Apriori - Descriere

Algoritmul Apriori constă ı̂ntr-o căutare iterativă ı̂n care

k-itemseturile frecvente sunt utilizate pentru a determina
(k + 1)-itemseturile frecvente. Iniţial se determină mulţimea
1-itemseturilor frecvente, L1 . Pentru acesta se scanează baza de
date DB pentru a determina suportul tuturor 1-itemseturilor.
Itemseturile care satisfac pragul de suport minim vor forma
mulţimea 1-itemseturilor frecvente, L1 . Apoi, mulţimea L1 este
utilizată pentru a determina mulţimea L2 a 2-itemseturilor
frecvente. L2 este utilizată pentru a determina L3 , şi aşa mai
departe pănă când mulţimea generată Lk devine vidă. La fiecare
pas, k, pentru a determina mulţimea Lk a k-itemseturilor frecvente
este necesară o parcurgere completă a bazei de date.

Mihai Gabroveanu Reguli de Asociere

 Concepte de bază
Introducere
Determinarea itemseturilor frecvente
Clasificarea regulilor de asociere
Algoritmul Apriori
Reguli de asociere boolene
Generarea regulilor de asociere

Algoritmul Apriori - Schema Logica

Schema logica a algoritmului Apriori

Mihai Gabroveanu Reguli de Asociere

 Concepte de bază
Introducere
Determinarea itemseturilor frecvente
Clasificarea regulilor de asociere
Algoritmul Apriori
Reguli de asociere boolene
Generarea regulilor de asociere

Algoritmul Apriori - Pasul de unire

Procesul de determinare a lui Lk din Lk−1 , pentru k ≥ 2, constă din doi
pasi importanţi:

1) (Pasul de unire) În acest pas, pentru determinarea mulţimii

k-itemseturilor frecvente, Lk , se generează o mulţime Ck de
k-itemseturi candidate, supramulţime a lui Lk , prin unirea mulţimi
Lk−1 cu ea ı̂nsăşi.
Prin convenţie, presupunem că itemi din cadrul itemseturilor sunt
ordonaţi lexicografic. Astfel, mulţimea Ck se obţine astfel:
Ck = Lk−1 ./ Lk−1 = {{x1 , . . . , xk−1 , yk−1 }|X ∈ Lk−1 , Y ∈ Lk−1 ,
X = {x1 , . . . , xk−2 , xk−1 }, Y = {y1 , . . . , yk−2 , yk−1 },
x1 = y1 ∧ · · · ∧ xk−2 = yk−2 ∧ xk−1 < yk−1 }

Condiţia xk−1 < yk−1 ne asigură faptul că nu se vor genera

itemseturi duplicate.

Mihai Gabroveanu Reguli de Asociere

 Concepte de bază
Introducere
Determinarea itemseturilor frecvente
Clasificarea regulilor de asociere
Algoritmul Apriori
Reguli de asociere boolene
Generarea regulilor de asociere

Algoritmul Apriori - Pasul de reducere

2) (Pasul de reducere) Pentru a determina mulţimea Lk , a

k-itemseturilor frecvente trebuie să determinăm suportul fiecărui
itemset din Ck . Pentru a realiza acest lucru este necesară o
parcurgere completă a bazei de date DB. Numărul itemseturilor
candidate din Ck poate fi ı̂nsă redus pe baza proprietăţii Apriori
ı̂nainte de a se ı̂ncepe parcurgerea bazei de date. Astfel, ı̂n baza
Corolarului 3, vom elimina toate k-itemseturile care conţin
(k − 1)-subitemseturi care nu sunt ı̂n Lk−1 .
Acest test se poate realiza rapid prin reţinerea unui hashtree1 cu
toate itemseturile frecvente. Mulţimea Ck atfel obţinută este o
supramulţime a lui Lk .

1
Un hashtree este o structură de date organizată sub forma unui arbore ı̂n
care fiecare nod este o tabelă de dispersie (hash table).
Mihai Gabroveanu Reguli de Asociere
 Concepte de bază
Introducere
Determinarea itemseturilor frecvente
Clasificarea regulilor de asociere
Algoritmul Apriori
Reguli de asociere boolene
Generarea regulilor de asociere

Algoritmul Apriori
INPUT:
DB : baza de date cu tranzacţiile
minsup: pragul de suport minim
OUTPUT:
L: mulţimea itemseturilor frecvente din DB.
METHOD:
1: L = ∅
2: C1 = {{i}|i ∈ I}
3: k = 1
4: while (Ck 6= ∅) do
5: //calculăm suportul absolut pentru fiecare itemset candidat
6: for all tranzaction T ∈ DB do
7: for all candidate X ∈ Ck do
8: if X ⊆ T then
9: X .count + +
10: end if
11: end for
12: end for
13: Lk = {X ∈ Ck |X .count ≥ minsup × |DB|}
14: L = L ∪ Lk
15: k++
16: Ck = apriori gen(Lk−1 , minsup)
17: end while
18: return L

Mihai Gabroveanu Reguli de Asociere

 Concepte de bază
Introducere
Determinarea itemseturilor frecvente
Clasificarea regulilor de asociere
Algoritmul Apriori
Reguli de asociere boolene
Generarea regulilor de asociere

Algoritmul Apriori
INPUT: Lk−1 : mulţimea (k − 1)-itemseturilor frecvente
OUTPUT: Ck : mulţimea k-itemseturilor candidate
procedure apriori gen(Lk , minsup)
1: Ck = ∅
2: for all (k − 1)-itemset X = {x1 , . . . , xk−1 } ∈ Lk−1 do
3: for all (k − 1)-itemset Y = {y1 , . . . , yk−1 } ∈ Lk−1 do
4: if x1 = y1 ∧ · · · ∧ xk−2 = yk−2 ∧ xk−1 < yk−1 then
5: //pasul de unire
6: Z = {x1 , . . . , xk−1 , yk−1 }
7: //pasul de reducere
8: has infrequent subset = false
9: for all (k − 1)-itemset Z 0 ⊂ Z do
10: if (Z 0 ∈
/ Lk−1 ) then
11: has infrequent subset = true
12: break
13: end if
14: end for
15: if not has infrequent subset then
16: Ck = Ck ∪ Z
17: end if
18: end if
19: end for
20: end for
21: return Ck
Mihai Gabroveanu Reguli de Asociere
 Concepte de bază
Introducere
Determinarea itemseturilor frecvente
Clasificarea regulilor de asociere
Algoritmul Apriori
Reguli de asociere boolene
Generarea regulilor de asociere

Algoritmul Apriori - Exemplu

TID Lista ID-urilor itemilor

T1 I1 , I2 , I3 , I5
T2 I2 , I3
T3 I1 , I2 , I4
T4 I3 , I4 , I5
T5 I1 , I2 , I3
T6 I1 , I3
T7 I1 , I3 , I4
T8 I3 , I4

Tabela: Exemplu de bază de date cu tranzacţiile dintr-un magazin

Consideram pragul de suport minim 25%.

Itemset Frecvenţa Itemset Frecvenţa

{I1 } 5 {I1 } 6
{I2 } 4 comparam frecventa
{I2 } 7
DB
−−−−→ {I3 } 7 −
−−−−−−−−−−−
→ {I3 } 6
Scanam cu suportul minim=2
{I4 } 4 {I4 } 2
{I5 } 2 {I5 } 2
(a) C1 (b) L1

Mihai Gabroveanu Reguli de Asociere

 Concepte de bază
Introducere
Determinarea itemseturilor frecvente
Clasificarea regulilor de asociere
Algoritmul Apriori
Reguli de asociere boolene
Generarea regulilor de asociere

Algoritmul Apriori - Exemplu

Itemset Frecvenţa
{I1 , I2 } 3
{I1 , I3 } 4 Itemset Frecvenţa
{I1 , I4 } 2 {I1 , I2 } 3
{I1 , I5 } 1 {I1 , I3 } 4
Generam C2 {I2 , I3 } 3 comparam frecventa cu {I1 , I4 } 2
−−−−−−−→ −
−−−−−−−−−−−−
→
din L1 {I2 , I4 } 1 suportul minim=2 {I2 , I3 } 3
{I2 , I5 } 1 {I3 , I4 } 3
{I3 , I4 } 3 {I3 , I5 } 2
{I3 , I5 } 2 (d) L2
{I4 , I5 } 1
(c) C2

Itemset Frecvenţa
Generam C3
Itemset Frecvenţa
{I1 , I2 , I3 } 2 comparam frecventa cu
−−−−−−−→ −
−−−−−−−−−−−−
→ {I1 , I2 , I3 } 2
din L2 {I1 , I3 , I4 } 1 suportul minim=2
(f) L3
(e) C3

Mihai Gabroveanu Reguli de Asociere

 Concepte de bază
Introducere
Determinarea itemseturilor frecvente
Clasificarea regulilor de asociere
Algoritmul Apriori
Reguli de asociere boolene
Generarea regulilor de asociere

Algoritmul Apriori vs. Brute-force

Numărul de candidaţi
Lungimea itemseturilor candidate
Brute-force Apriori (suport absolut minim=2)
1 5 5
2 10 10
3 10 2
4 5 0
5 1 0

Tabela: Comparaţie ı̂ntre numărului de itemseturi candidate

Mihai Gabroveanu Reguli de Asociere

 Concepte de bază
Introducere
Determinarea itemseturilor frecvente
Clasificarea regulilor de asociere
Algoritmul Apriori
Reguli de asociere boolene
Generarea regulilor de asociere

Generarea regulilor de asociere

Având determinată mulţimea itemseturilor frecvente din DB,
putem trece la generarea regulilor de asociere tari.
Dacă generarea regulilor de asociere se realizează numai pe
baza itemseturilor frecvente, atunci pragul de suport minim
este deja asigurat.
Fiecare itemset frecvent Z este partiţionat ı̂n două submulţimi
nevide, X şi Z \X , iar din acestea se generează regula
X ⇒ Z \X . Această regulă satisface pragul de suport minim
deoarece:
support(X ⇒ Z \ X , DB) = support(Z , DB) ≥ minsup
Mai rămâne să testăm doar confidenţa regulii. Dacă aceasta
este mai mare sau egală decât pragul de confidenţă minim
(minconf ), atunci regula este păstrată ca regulă de asociere
tare.
Mihai Gabroveanu Reguli de Asociere
 Concepte de bază
Introducere
Determinarea itemseturilor frecvente
Clasificarea regulilor de asociere
Algoritmul Apriori
Reguli de asociere boolene
Generarea regulilor de asociere

Generarea regulilor de asociere

INPUT:
DB - baza de date cu tranzacţiile.
L - mulţimea itemseturilor frecvente.
minconf - pragul de confidenţă minim.
OUTPUT:
R - mulţimea regulilor de asociere tari din DB.
METHOD:
procedure generate rules(DB,L,minconf )
1: R = ∅
2: for all large itemset Z ∈ L do
3: for all X ⊆ Z , X 6= ∅ do
4: if confidence(X ⇒ Z \ X ) ≥ minconf then
5: R = R ∪ {X ⇒ Z \ X }
6: return R
Mihai Gabroveanu Reguli de Asociere
 Concepte de bază
Introducere
Determinarea itemseturilor frecvente
Clasificarea regulilor de asociere
Algoritmul Apriori
Reguli de asociere boolene
Generarea regulilor de asociere

Generarea regulilor de asociere - Exemplu

Considerăm itemsetul frecvent Z = {I1 , I2 , I3 } generat pentru baza de date considerata in exemplul anterior. În
tabelul urmator sunt prezentate toate regulile de asociere care pot fi generate din itemsetul frecvent Z . Însă, nu
toate sunt reguli de asociere tari.

Regula Confidenţa Confidenţa (%)

{I 1, I 2} ⇒ {I 3} 2/3 66.66%
{I 1, I 3} ⇒ {I 2} 2/4 50.00%
{I 2, I 3} ⇒ {I 1} 2/3 66.66%
{I 1} ⇒ {I 2, I 3} 2/5 40.00%
{I 2} ⇒ {I 1, I 3} 2/4 50.00%
{I 3} ⇒ {I 1, I 2} 2/7 28.57%

Tabela: Regulile de asociere generate din itemsetul {I1 , I2 , I3 }

Dacă stabilim pragul de confidenţă minim la 50%, atunci regulile de asociere tari obţinute din Z sunt următoarele:

{I1 , I2 } ⇒ {I 3}, {I1 , I3 } ⇒ {I2 }, {I2 , I3 } ⇒ {I1 }, {I2 } ⇒ {I1 , I3 }.

Mihai Gabroveanu Reguli de Asociere

Reguli de Asociere Fuzzy

Mihai Gabroveanu
Cuprins

1 Reguli de asociere cantitative

2 Reguli de asociere fuzzy

Determinarea fuzzy itemset-urilor frecvente
Generarea regulilor de asociere fuzzy

3 Concluzii
Reguli de asociere cantitative Reguli de asociere fuzzy Concluzii

Reguli de Asociere Cantitative

Intr-o bază de date atributele nu au numai valori binare, ele pot fi şi
numerice sau nominale
Regulile de asociere cantitative au fost introduse in 1996 de
Agrawal, R. and Srikant, R. ı̂n articolul Mining quantitative
association rules in large relational tables
Problema determinării regulilor cantitative se reduce la determinarea
regulilor de asociere boolene prin partitionarea valorilor fiecărui
atribut ı̂n intervale si maparea ı̂n intervalul corespunzător.

TID Varsta Venit Greutate Casatorit

1 25 1200 55 nu
2 31 4000 80 da
3 40 4850 96 da
4 48 6000 90 da
5 60 3000 80 nu
6 65 1900 95 da
Reguli de asociere cantitative Reguli de asociere fuzzy Concluzii

Maparea atributelor cantitative ı̂n intervale

Varsta Venit Greutate Casatorit

TID
0...29 30...45 46...90 0...3000 3001...10000 0...80 81...200 nu da
1 1 0 0 1 0 1 0 1 0
2 0 1 0 0 1 1 0 0 1
3 0 1 0 0 1 0 1 0 1
4 0 0 1 0 1 0 1 0 1
5 0 0 1 1 0 1 0 1 0
6 0 0 1 1 0 0 1 0 1

Tabela: Maparea atributelor cantitative ı̂n intervale

Regulă de Asociere Cantitativă

hVarsta, ”30...40”i ⇒ hVenit, ”3001...10000”i

Reguli de asociere cantitative Reguli de asociere fuzzy Concluzii

Reguli de Asociere Fuzzy

Regulile de Asociere Fuzzy: Au fost propuse de C. M.

Kuok, A. W. Fu, and M. H. Wong, ı̂n:
Mining fuzzy association rules in databases, in SIGMOD
Rec., 27(1):41–46, 1998.
oferă suport atât pentru date caracterizate prin atribute
cantitative cât şi pentru cele caracterizate prin atribute
nominale.

Regulă de Asociere Fuzzy

vasta(X , tanar ) ∧ venit(X , mare) ⇒ masini(X , multe) (1)

Reguli de asociere cantitative Reguli de asociere fuzzy Concluzii

Ce este o multime fuzzy?

O mulţime clasică este definită ca o colecţie de elemente

x ∈ X . Un element poate fie să aparţină, fie să nu aparţină
mulţimii.
O mulţime fuzzy este definită printr-o funcţie de apartenenţă
care asignează valorii unui atribut o valoare cuprinsă ı̂ntre 0 şi
1 care indică gradul de apartenenţă la mulţimea fuzzy.

Multime Fuzzy
Fie U o mulţime de obiecte. O multime fuzzy F ı̂n universul U
este o mulţime de perechi ordonate F = {(u, µF (u))/u ∈ U}, unde
µF (u) : U → [0, 1] iar µF (u) este gradul de apartenenţă a lui u la
F.
Reguli de asociere cantitative Reguli de asociere fuzzy Concluzii

Exemplu de multime fuzzy

Dacă considerăm că o persoană este

”grasă” dacă greutatea sa este mai
mare de 90 de kilograme, funcţia de
apartenenţă pentru mulţimea fuzzy
”gras” o putem definii astfel:

µgras : [0, 200] → [0, 1],


0,
 daca x < 70
(x−70)
µgras (x) = , daca 70 ≤ x ≤ 90
 (90−70)
1, daca x > 90

Figura: Funcţiile de apartenenţă
pentru mulţimile fuzzy asociate
atributului Greutate
Reguli de asociere cantitative Reguli de asociere fuzzy Concluzii

Reguli de Asociere Fuzzy. Definiţia Formală(I)

Fie: DB = {t1 , . . . , tn } o bază de date.

I = {i1 , . . . , im } mulţime de atribute.
n(k)
Fik = {Fi1k , . . . , Fik } mulţimi fuzzy asociate atributului ik .
µF j : dom(ik ) → [0, 1] funcţia de apartenenţă pentru mulţimea fuzzy Fijk .
ik

Fuzzy Itemset
Numim fuzzy itemset perechea hX , FX i , unde X ⊆ I, iar FX este o
mulţime de mulţimi fuzzy asociate atributelor/itemilor din X .

k-Fuzzy Itemset
Un fuzzy itemset hX , FX i ı̂n care numărul de atribute din X este k se
numeşte k-fuzzy itemset.
Reguli de asociere cantitative Reguli de asociere fuzzy Concluzii

Reguli de Asociere Fuzzy. Definiţia Formală(II)

Regulă de Asociere Fuzzy

O regulă de asociere fuzzy este o implicaţie de forma
X ∈ FX ⇒ Y ∈ FY
unde X , Y ⊂ I, X ∩ Y = ∅, X = {x1 , . . . , xp }, Y = {y1 , . . . , yq }.
FX = {a1 , . . . , ap } şi FY = {b1 , . . . , bq } sunt mulţimi de mulţimi
fuzzy asociate atributelor din X respectiv Y . Vom nota acesta
regulă astfel:
hX , FX i ⇒ hY , FY i

Semnificaţia intuitivă
Dacă o tranzacţie (tuplu) satisface proprietatea X ∈ FX atunci
sunt şanse mari ca ea să satisfacă şi Y ∈ FY .
Reguli de asociere cantitative Reguli de asociere fuzzy Concluzii

Reguli de Asociere Fuzzy. Exemple

1 DB = {t1 , t2 , t3 , t4 , t5 , t6 },
2 I = {Varsta, Venit, Greutate}
TID Varsta Venit Greutate
1 25 2000 68 3 FVarsta =
2 31 4000 80
3 40 5000 96
{tanar , varsta − medie, batran}
4 50 6000 90
5 60 3000 80 4 FVenit = {mic, mediu, mare}
6 58 2000 70
Baza de date 5 FGreutate = {slab, mediu, gras}

Exemplu
Dacă Vârsta este medie şi Venit-ul este mare atunci conform
Greutăţii este gras

h{Varsta, Venit}, {medie, mare}i ⇒ h{Greutate}, {gras}i

Reguli de asociere cantitative Reguli de asociere fuzzy Concluzii

Măsura Suport

Itemset Fuzzy Support

Fuzzy suportul fuzzy itemset-ului hX , FX i ı̂n DB se defineşte astfel:
P Q
ti ∈DB xj ∈X αaj (ti [xj ])
FShX ,FX i = (2)
|DB|

unde 
µaj (ti [xj ]), if µaj (ti [xj ]) ≥ ω
αaj (ti [xj ]) =
0, altfel
iar ω un prag minim dat pentru funcţia de apartenenţă.

Rule Fuzzy Support

FShX ,FX i⇒hY ,FY i = FSh{X ,Y },{FX ,FY }i (3)

Reguli de asociere cantitative Reguli de asociere fuzzy Concluzii

Măsura Suport

Fuzzy Itemset Frecvent

Un fuzzy itemset hX , FX i se numeşte fuzzy itemset frecvent (large
fuzzy itemset) dacă valoarea fuzzy suportului său este mai mare sau
decât un prag minim specificat (minsup), adică:

FShX ,FX i ≥ minsup

Regula de Asociere Fuzzy Frecventă

O regulă de asociere fuzzy, hX , FX i ⇒ hY , FY i , se numeste frecventă
dacă fuzzy suportul ei este mai mare sau egal decât pragul de suport
minim (minsup), adică

FShX ,FX i⇒hY ,FY i ≥ minsup

.
Reguli de asociere cantitative Reguli de asociere fuzzy Concluzii

Masura de Confidenţă

Fuzzy confidenţa unei reguli de asociere fuzzy

Fie hX , FX i ⇒ hY , FY i , o regulă de asociere fuzzy. Fuzzy
confidenţa regulii se defineste astfel:
FShZ ,FZ i
FChX ,FX i⇒hY ,FY i = (4)
FShX ,FX i

unde Z = {X , Y } şi FZ = {X , Y }.

Regula de Asociere Fuzzy Tare

O regulă de asociere fuzzy este considerată interesantă sau tare
dacă are fuzzy suportul şi fuzzy confidenţă mai mari decât un prag
dat.
Reguli de asociere cantitative Reguli de asociere fuzzy Concluzii

Exemplu: Suportul si Confidenţa unei Reguli Fuzzy

Varsta Venit Greutate Casatorit
TID
tanar medie batran mic mediu mare slab normal gras nu da
1 1.00 0.00 0.00 0.60 0.20 0.00 0.25 0.75 0.00 1 0
2 0.40 0.60 0.00 0.00 1.00 0.00 0.00 0.50 0.50 0 1
3 0.00 1.00 0.00 0.00 0.15 0.85 0.00 0.00 1.00 0 1
4 0.00 0.70 0.60 0.00 0.00 1.00 0.00 0.00 1.00 0 1
5 0.00 0.00 1.00 0.00 1.00 0.00 0.00 0.50 0.50 1 0
6 0.00 0.00 1.00 0.00 0.90 0.00 0.00 0.00 1.00 0 1

Tabela: Valorile funcţiilor de apartenenţă

Pentru ω = 0.1, fuzzy suportul regulii h{Varsta, Venit}, {batran, mediu}i ⇒ h{Greutate}, {gras}i este:

0.00 × 0.20 × 0.00 + 0.00 × 1.00 × 0.50

FSh{Varsta,Venit},{batran,mediu}i⇒h{Greutate},{gras}i = +
6
0.00 × 0.15 × 1.00 + 0.60 × 0.00 × 1.00 + 1.00 × 1.00 × 0.50 + 1.00 × 0.90 × 1.00
+ = 0.23
6
iar confidenta este:
FSh{Varsta,Venit,Greutate},{batran,mediu,gras}i
FCh{Varsta,Venit},{batran,mediu}i⇒h{Greutate},{gras}i =
FSh{Varsta,Venit},{batran,mediu}i
0.23
= = 0.73
0.32
Reguli de asociere cantitative Reguli de asociere fuzzy Concluzii

Problema Minării Regulilor de Asociere Fuzzy

Problema Minării Regulilor de Asociere Fuzzy

Fiind date: o bază de date DB caracterizată de o mulţime de
atribute I, mulţimile fuzzy asociate atributelor din I, ω pragul de
suport minim pentru funcţia de apartenenţă, minsup pragul de
suport minim şi minconf pragul de confidenţă minim, să se
determine toate regulile fuzzy de asociere puternice

Problema se descompune ı̂n două subprobleme:

1 determinarea tuturor fuzzy itemseturilor frecvente
2 generarea regulilor de asociere fuzzy din fuzzy itemseturile
frecvente.
Reguli de asociere cantitative Reguli de asociere fuzzy Concluzii

Determinarea fuzzy itemset-urilor frecvente

Determinarea fuzzy itemset-urilor frecvente

Lemma (Proprietarea Fuzzy Apriori)

Dacă un fuzzy itemset hX , FX i este un fuzzy itemset frecvent ı̂n

DB şi Y ⊆ X , FY ⊆ FX , atunci fuzzy itemsetul hY , FY i este de
asemenea frecvent ı̂n DB.
Din lema precedentă putem trage următoarea concluzie: orice
fuzzy subitemset al unui fuzzy itemset frecvent este de asemenea
frecvent.
Corollary

Dacă un k-fuzzy itemset conţine un (k − 1)-fuzzy itemset care nu

este frecvent, atunci nici el nu este frecvent.
Reguli de asociere cantitative Reguli de asociere fuzzy Concluzii

Determinarea fuzzy itemset-urilor frecvente

Algoritmul FuzzyApriori
INPUT:
DB: baza de date
I: mulţimea de atribute
Fi1 , . . . , Fim : mulţimile de mulţimi fuzzy asociate atributelor din I
minsup: pragul de suport minim
ω: pragul minim pentru funcţia de apartenenţă
OUTPUT:
L: mulţimea fuzzy itemseturilor frecvente din DB.
METHOD:
1: L = ∅
2: C1 = {h{ik }, {Fijk }i|ik ∈ I, Fijk ∈ Fik }
3: k = 1
4: while Ck 6= ∅ do
5: //calculăm fuzzy suport count-ul pentru fiecare fuzzy itemset candidat
6: for all transaction t ∈ D do
7: for all candidate hX , Ai ∈ Ck , X = {x1 , . . . , xk }, A = {a1 , . . . , ak } do
8:
Q
FShX ,Ai += x ∈X αaj (ti [xj ])
j
9: end for
10: end for
11: Lk ={hX , Ai ∈ Ck |FShX ,Ai ≥ minsup × |D|}
12: L = L ∪ Lk
13: k++
14: Ck = fuzzy apriori gen(Lk−1 )
15: end while
16: return L
Reguli de asociere cantitative Reguli de asociere fuzzy Concluzii

Determinarea fuzzy itemset-urilor frecvente

Algoritmul FuzzyApriori - Pasul de unire

Algoritmul de generare a mulţimii k-fuzzy itemseturilor frecvente Lk din
Lk−1 , k ≥ 2, constă ı̂n următorii doi paşi:

1) (Pasul de unire) În acest pas, pentru determinarea lui Lk ,

mulţimea k-fuzzy itemseturilor frecvente, se generează o mulţime
Ck de k-fuzzy itemseturi candidate, supramulţime a lui Lk , prin
unirea mulţimi Lk−1 cu ea ı̂nsăşi.
Prin convenţie, presupunem că itemi din cadrul fuzzy itemseturilor
sunt ordonaţi lexicografic. Mulţimea Ck se construieşte astfel:
Ck = Lk−1 BC Lk−1 = {hZ , C i|hX , Ai ∈ Lk−1 , hY , Bi ∈ Lk−1 ,
hZ , C i = h{x1 , . . . , xk−2 , xk−1 , yk−1 }, {a1 , . . . , ak−2 , ak−1 , bk−1 }i,
hX , Ai = h{x1 , . . . , xk−2 , xk−1 }, {a1 , . . . , ak−2 , ak−1 }i,
hY , Bi = h{x1 , . . . , xk−2 , yk−1 }, {a1 , . . . , ak−2 , bk−1 }i,
xk−1 < yk−1 }
Reguli de asociere cantitative Reguli de asociere fuzzy Concluzii

Determinarea fuzzy itemset-urilor frecvente

Algoritmul FuzzyApriori - Pasul de reducere

2) (Pasul de reducere) În acest pas din mulţimea Ck generată

anterior se elimină ı̂n baza Corolarului 2 acele fuzzy itemseturi care
conţin (k − 1)-fuzzy subitemseturi care nu sunt ı̂n Lk−1 . Acest test
se poate realiza rapid prin reţinerea unui hashtree cu toate fuzzy
itemseturile frecvente. În acest fel, mulţimea candidaţilor, Ck , este
redusă. Mulţimea obţinută este ı̂nsă o supramulţime a lui Lk .
Reguli de asociere cantitative Reguli de asociere fuzzy Concluzii

Determinarea fuzzy itemset-urilor frecvente

Algoritmul FuzzyApriori - Generarea itemseturilor candidate

INPUT:
Lk−1 : mulţimea (k − 1)-fuzzy itemseturilor frecvente
OUTPUT:
Ck : mulţimea k-fuzzy itemseturilor candidate.
function fuzzy apriori gen(Lk−1 )
1: Ck = ∅
2: for all (k − 1)-itemset hX , Ai ∈ Lk−1 , X = {x1 , . . . , xk−1 }, A = {a1 , . . . , ak−1 } do
3: for all (k − 1)-itemset hY , Bi ∈ Lk−1 , Y = {y1 , . . . , xy −1 }, B = {b1 , . . . , bk−1 } do
4: if ((x1 = y1 ) ∧ (a1 = b1 )) ∧ · · · ∧ ((xk−2 = yk−2 ) ∧ (ak−2 = bk−2 )) ∧ (xk−1 < yk−1 ) then
5: //pasul de unire
6: hZ , C i = h{x1 , . . . , xk−2 , xk−1 , yk−1 }, {a1 , . . . , ak−2 , ak−1 , bk−1 }i
7: //pasul de reducere
8: has infrequent subset = true
9: for all (k − 1)-fuzzy subitemset hZ 0 , C 0 i of hZ , C i do
10: if hZ 0 , C 0 i ∈
/ Lk−1 then
11: has infrequent subset = false
12: break
13: end if
14: end for
15: if not has infrequent subset then
16: Ck = Ck ∪ {hZ , C i}
17: end if
18: end if
19: end for
20: end for
21: return(Ck )
Reguli de asociere cantitative Reguli de asociere fuzzy Concluzii

Determinarea fuzzy itemset-urilor frecvente

Exemplu: Generarea fuzzy itemseturilor candidate

Să presupunem că mulţimea L2 este formată din următoarele fuzzy

itemseturi:
h{Greutate, Varsta}, {gras, batran}i,
h{Greutate, Varsta}, {normala, batran}i,
h{Greutate, Venit}, {gras, mediu}i,
h{Greutate, Venit}, {normala, mare}i,
h{Varsta, Venit}, {batran, mare}i.
Atunci mulţimea C3 a 3-fuzzy itemseturilor candidate obţinută prin
unirea lui L2 cu L2 constă din următoarele fuzzy itemseturi:
h{Greutate, Varsta, Venit}, {gras, batran, mediu}i,
h{Greutate, Varsta, Venit}, {normala, batran, mare}i.
Din această multime eliminăm primul 3-fuzzy itemset
h{Greutate, Varsta, Venit}, {gras, batran, mediu}i deoarece contine
2-fuzzy itemsetul h{Varsta, Venit}, {batran, mediu}i care nu este in L2
Reguli de asociere cantitative Reguli de asociere fuzzy Concluzii

Generarea regulilor de asociere fuzzy

Generarea regulilor de asociere fuzzy

INPUT:
DB: baza de date cu tranzacţiile
minconf : pragul de confidenţă minim
L: mulţimea fuzzy itemseturilor frecvente din DB
OUTPUT:
<: mulţimea regulilor de asociere fuzzy tari din DB.
function generate strong fuzzy rules(L,minconf ;<)
1: <=∅
2: for all frequent fuzzy itemset hZ , FZ i ∈ L do
3: for all subset X ⊂ Z , X 6= ∅ do
4: if FShX ,F i⇒hZ \X ,F
X Z \X i ≥ minconf then

5: < = < ∪ {hX , FX i ⇒ hZ \X , FZ \X i}

6: end if
7: end for
8: end for
9: return <
Reguli de asociere cantitative Reguli de asociere fuzzy Concluzii

Concluzii

Extragerea regulilor de asociere constituie una din provocările

domeniului data mining, elaborarea de modele si algoritmi pentru
extragerea acestora a făcut şi face obiectul de studiu a numeroşi
cercetători. Scopul acestui capitol a fost acela de a expune
conceptele legate de extragerea regulilor de asociere, prezentarea
pricipalelor măsuri care exprimă calitatea regulilor de asociere.
Pentru extragerea regulilor de asociere au fost propusi de-a lungul
timpului numeroşi algoritmi: Apriori, DHP, PARTITION, DIC,
FP-growth. Am prezentat aici pe unul dintre cei mai cunoscuţi,
Apriori, precum şi o extensie a acestuia Fuzzy Apriori ce permite
extragerea regulilor de asociere fuzzy.
Regulile de asociere au aplicaţii ı̂n diverse domenii precum:
marketing, GIS, baze de date multimedia, detecţia fraudelor,
clasificarea documentelor web, etc.
 Clasificare vs. Predicţie numerică
n Clasificarea:
¨ Asignarea de obiecte unei anumite categorii (clase) dintr-o mulţime de
Clasificare şi Predicţie ¨
categorii fixă.
Construirea unui model pe baza unei mulţimi date de antrenament pre-
încadrate în anumite clase (atributul de clasa) si utilizarea acestui
model pentru a clasifica date noi.
¨ Etichetele claselor sunt valori ale unui atribut discret sau nominal
n Predicţia numerică:
¨ Modelează valori continue ale unei funcţii, adică, predicţia de valori
necunoscute sau lipsă

Clasificare şi Predicţie 3

Învăţare supervizată vs. nesupervizată Aplicaţii

n Învăţare supervizată (clasificare) n aprobarea creditelor
¨ supervizare: mulţimea de antrenament (observaţiile, măsurătorile, etc.)
n identificarea claselor de clienţi
sunt însoţite de etichetele ce indică clasele în care sunt încadrate
¨ Datele noi sunt clasificate pe baza modelului obţinut din multimea de n diagnoză medicală: o tumoare este malignă
antrenament sau belignă
n Învăţare nesupervizată (clustering)
n clasificarea paginilor web
¨ Etichetele datelor de antrenament sunt necunoscute
¨ Dându-se o mulţime de măsurători, observaţii, etc. cu scopul de a n detectarea fraudelor
stabili existenta de clase sau clustere in care pot fi incadrate.

Clasificare şi Predicţie 2 Clasificare şi Predicţie 4

Clasificarea - Construirea modelului Exemplu: Construirea Modelului
Algoritm de clasificare
1. Construirea modelului ce descrie o mulţime de clase
Mulţime de
predeterminate antrenament
¨ Fiecare tuplu (exemplu) este presupus ca aparţinând unei
clase predefinite, clasă indicată de valoarea unui atribut
numit atributul de etichetare a clasei
¨ Mulţimea de tupluri utilizate pentru construirea modelului Nume Functie Vechime Titular
Clasificator
formeaza mulţimea de antrenament Mihai Conferentiar 3 nu (Model)
¨ Modelul este reprezentat prin reguli de clasificare, arbore Maria Conferentiar 7 da
de decizie , formule matematice
Mircea Profesor 2 da
George Conferentiar 7 da
IF functia = ‘profesor’
David Conferentiar 6 nu
Ana Conferentiar 3 nu
OR vechime > 6
THEN titular = ‘da’
Clasificare şi Predicţie 5 Clasificare şi Predicţie 7

Clasificarea - Utilizarea modelului Exemplu: Utilizarea Modelului

2. Utilizarea modelului pentru clasificarea tuplurilor noi sau
necunoscute
¨ Estimarea acurateței modelului
n Eticheta cunoscută a tuplurilor de test este comparată cu clasa
Clasificator
asignată de modelul de clasificare
n Acurateţea unui model pe o multime de test este dată de procentul Date de Date Noi
de tupluri clasificate corect de model test
n Mulțimea de test se recomandă a fi o mulțime independentă de
date de test pentru a evita procesul de “over-fitting” (Irina, Profesor, 4)
¨ Dacă acurateţea este acceptabilă atunci modelul poate fi utilizat pentru
a clasifica tupluri sau obiecte noi a căror clasă nu este cunoscută NUME FUNCTIE VECHIME TITULAR
Toni Conferentiar 2 nu Titular?
Marina Conferentiar 7 nu
George Profesor 5 da
Noe Conferentiar 7 da

Clasificare şi Predicţie 6 Clasificare şi Predicţie 8

Pregătirea datelor pentru clasificare și predicție Clasificare prin Arbori de Decizie
n Curaţirea datelor:
¨ Preprocesarea in vederea eliminări/reduceri zgometelor (ex: aplicarea de n Un arbore de decizie este o structură
tehnici de uniformizare), tratarea valorilor lipsă
n Analiza relevanței (selecția caracteristicilor)
arborescenta în care:
¨ Eliminarea atributelor irelevante sau redundante ¨ fiecare nod intern reprezintă un test asupra unui
¨ Conduce la îmbunătăţirea eficienţei şi scalabilităţii atribut
n Transformarea datelor
¨ fiecare ramură reprezintă un rezultat al testului
¨ Generalizarea datelor la nivele de conceptualizare de nivel înalt
n Ex: atributul ‘oras’ poate fi generalitat la ‘judeţ’ ¨ fiecare nod frunză reprezintă clase sau distributii
¨ Normalizarea datelor: scalarea tuturor valorilor unui atribut astfel încat să ia de clase
valori într-un interval mai mic specificat

Clasificare şi Predicţie 9 Clasificare şi Predicţie 11

Evaluarea algoritmilor de clasificare Exmplu: Arbore de decizie

clasa
ag e income studen t credit_rating buys_computer
<=30 hig h no fair no
n Acurateţea predicţiei: abilitatea modelului de a prezice corect etichetele <=30 hig h no excellent no
claselor pentru date noi 31…40 hig h no fair yes
n Viteza: timpul necesar generării şi utilizării modelului >40 medium no fair yes
>40 low yes fair yes age?
n Robusteţea: abilitatea modelului de a realiza predicții corecte dându-se >40 low yes excellent no
date cu zgomote sau valori incomplete 31…40 low yes excellent yes
Inductie
<=30 medium no fair no
n Scalabilitatea: abilitatea de a construi eficient modelul atunci când <=30 low yes fair yes
<=30 31..40
mulțimea de antrenament este mare >40 medium yes fair yes >40
<=30 medium yes excellent yes
n Interpretabilitatea: nivelul de înțelegere și pătrundere furnizat de model 31…40 medium no excellent yes
n Calitatea regulilor: 31…40
>40
hig h
medium
yes fair
no excellent
yes
no student? yes credit rating?
¨ dimensiunea arborilor de decizie Multime de antrenament:
¨ compactitatea regulilor de clasificare buy-computer
no yes excellent fair

no yes no yes

Clasificare şi Predicţie 10 Clasificare şi Predicţie Arbore de decizie 12

Agoritmul Hunt -Inducerea Arborelui de Decizie Exemplu: Selectia atributului - Age
5 4
 Class P: buys_computer = “yes”
Info age ( D ) = I ( 2 ,3 ) + I ( 4,0 )
n Algoritmul de baza (algoritm greedy) 14 14
 Class N: buys_computer = “no”
¨ Arborele este construit recursiv de sus în jos utilizand tehnica divide-and- 9 9 5 5 5
conquer: Info ( D ) = I ( 9 ,5 ) = − log 2 ( ) − log 2 ( ) = 0 . 940 + I ( 3, 2 ) = 0 . 694
¨ Initial, toate instantele (exemplele) multimii de antrenament vor fi asignate 14 14 14 14 14
nodului radacină
¨ Atributele sunt considerate categoriale (daca au valori continue atunci ele
age pi ni I(p i, ni) 5 insemana ca 5 din 14 exemple au “age <=30”,
<=30 2 3 0.971 I ( 2 ,3 )
trebuie discretizate înainte) 14 dintre care 2 sunt clasificate ‘yes’ si 3 ‘nu’.
¨ Exemplele sunt partitionate recursiv pe baza testarii unor atribute de selectie 31…40 4 0 0
Astfel,
¨ Atributele de test sunt selectate pe baza unor masuri euristice sau statistice >40 3 2 0.971
(ex., entropie, information gain) ag e income student credit_rating buys_computer
Gain ( age ) = Info ( D ) − Info age ( D ) = 0 . 246
n Conditia de oprire a partitionarii <=30 hig h no fair no
¨ Toate exemplele asignate unui nod apartin aceleiasi clase <=30 hig h no excellent no
¨ Nu mai exista atribute de test pentru continua partitionarea – in acest caz clasa 31… 40 hig h no fair yes Similar,
>40 mediu m no fair yes
asignata noului funza este dictata de votul majoritar (cea mai frecventa clasa)
) = 0 . 029
>40 low yes fair yes
¨ Nu mai exista exemple de procesat >40 low yes excellent no Gain ( income
31… 40
<=30
low
mediu m
yes
no
excellent
fair
yes
no
Gain ( student ) = 0 . 151
<=30 low yes fair yes Gain ( credit _ rating ) = 0 . 048
>40 mediu m yes fair yes
<=30 mediu m yes excellent yes
31… 40 mediu m no excellent yes
Deoarece pentru atributul Age masura Gain
Clasificare şi Predicţie 13 31… 40 hig h yes fair yes este maxima acesta va fi selectat
Clasificare şi Predicţie 15
>40 mediu m no excellent no

Măsuri de selectie a atributelor Algoritmi de inducere a Arborilor

n Pentru a selecta atributul de test în cadrul unui nod din arbore se utilizeaza de
regula o masura ce cuantifică câştigul informational (informatia dobandintă). n Algoritmul ID3
n Atributul ce aduce cel mai mare câștig (maximizează sau minimizează masura) este
selectat ca atribut de test pentru nodul curent. n Algoritmul C4.5 succesor al lui ID3
n Fie si numarul de tupuri ce apartin clasei Ci si pi probabilitatea ca un tuplu
din D sa aparțină clasei Ci, estimat prin si /|D|.
n Algoritmul CART- Classification and
n Informatia asteptata (entropia) necesara pentru a clasifica un tuplu din D:
m
Regression Trees
Info( D ) = I ( s1 ,L , s m ) = − ∑ p log
i =1
i 2 ( pi )

n Informatia necesara (dupa utilizarea lui A pentru partitionarea lui D in v

partitii) pentru a clasifica D:

n Informatia dobandita prin partitionarea pe baza atributului A

Gain(A)= Info(D)− InfoA(D)
Clasificare şi Predicţie 14 Clasificare şi Predicţie 16
 Aplicatii ale Analzei Clusterelor
n Recunoasterea Paternurilor (eng. Pattern
Recognition)
Analiza Clusterelor n Analiza datelor spatiale
¨ Crearea de hărţi tematice in GIS
n Procesarea Imaginilor
n Economie (in special in prospectarea pieței)
n WWW
¨ Gruparea paginilor Web
¨ Analiza log-urilor pentru a descoperi grupuri de paternuri
de acces

Analiza Clusterelor 3

Ce este Analiza Clusterelor? Exemple de Aplicatii

n Cluster: o colectie (grupare, clasa) de obiecte n Marketing: Identificarea grupurilor de clienti, identificarea paternurilor de
¨ ce au proprietati similare cumparare cu scopul dezvoltării stategiilor de promovare pentru fiecare
¨ sunt diferite (disimilare) de obiectele ce apartin altor clustere categorie in parte
n Analiza clusterelor (eng. Cluster Analysis) n Geodezie: Identificarea de zone de pamant ce au caracteristici similare
¨ Este procesul de grupare a obiectelor în clustere sau clase
n Asigurări: Identificarea categoriilor de detinatori de polițe de asigurari auto
n Clustering-ul este o metoda nesupervizata de clasificare in
care nu exista un set de clase predefinit ce au un grad ridicat de accident
n Aplicatii în Data Mining n Planificarea dezvoltarii oraşelor: Identificarea grupurilor de case în functie
¨ Poate fi utilizata ca un instrument stand-alone pentru analiza de tipul, valoarea si locatia acestora
distributiei datelor n Studierea cutremurelor: Observarea epicentrelor cutremurelor poate
¨ Poate servi ca pas pentru preprocesarea datelor utilizate de către alti
algoritmi conduce la identificarea faliilor continentelor

Analiza Clusterelor 2 Analiza Clusterelor 4

Evaluarea Metodelor de Clustering Structuri de date
n O metoda de clustering bună va identifica clustere de calitate înaltă dacă: n Algoritmi de clustering bazati pe memorie
¨ Obiectele ce apartin aceluiași cluster sunt foarte similare (memory-based clustering algorithms)
¨ Intre obiectele ce fac parte din clustere diferile exista foarte putine similitudini
utilizeaza de regula doua structuri de date:
n Calitatea clustering-ului depinde atat de masura de similaritate utilizata
¨ Matricea datelor sau two-mode matrix
precum si de metoda (tehnica) prin care este realizata si modul de
implementare. ¨ Matrice de disimilaritate sau one-mode matrix
n Calitatea unei metode de clustering este masurata si prin abilitatea n Vom considera ca multimea de date ce
acesteia de a descoperi o parte sau toate paternurile ascunse.
urmeaza a fi impartita in clustere contine n
obiecte (ex: persoane, documente, etc.)

Analiza Clusterelor 5 Analiza Clusterelor 7

Cerinte in Data Mining pentru Clustering Structuri de date - Matricea datelor

n Scalabilitatea – abilitatea de a lucra cu cantitati mari de date n Matricea datelor (eng. data
n Abilitatea de lucra cu tipuri de atribute diverse matrix) sau structura object-
n Descoperirea de clustere cu forme arbitrare by-variable reprezinta cele n  x11 ... x1f ... x1p 
¨ De regula sunt extrase clustere de forma sferica cu aceiasi dimensiune si densitate
obiecte caracterizate prin p  
n Parametri de intrare sa necesite cat mai putine cunostinte in domeniu  ... ... ... ... ... 
atribute sub forma unei x ... x if ... x ip 
¨ Ex: nr de clustere dorite
tabele relationale sau  i1 
n Abilitatea de a lucra cu date ce contin ‘zgomote’ sau anomalii
matrice de dimensiune nxp  ... ... ... ... ... 
n Sa fie insenzitiv la ordinea datelor de intrare x ... x nf ... x np 
n Sa poata prelucra date ce contin un numar mare de dimensiuni n Fiecare linie i va retine  n1 
n Sa poata sa incorporeze constrangeri ale utilizatorului valorile atibutelor obiectului i
n Rezultatele obtinute sa fie usor de utilizat si interpretat.

Analiza Clusterelor 6 Analiza Clusterelor 8

Structuri de date - Matricea de Disimilaritate Tipuri de date in analiza clusterelor
n Matricea de disimilaritate (eng
Dissimilarity matrix) sau structura n Variabile Interval-scaled
object-by-object este o matrice de
dimesiune nxn ce cuprinde  0 
multimea disimilaritatilor dintre  d(2,1) 0  n Variabile Binare
oricare doua obiecte  
n d(i,j) = masura ce exprima
 d(3,1) d ( 3,2) 0 
disimilaritatea dintre obiectul i si j
  n Variabile nominale, ordinale, si proportii (ratio)
(nr pozitiv ce tinde la 0 cand  : : : 
obiectele i si j sunt foarte similare d ( n,1) d ( n,2) ... ... 0
si tinde catre valori mari cand
n Variabile de tipuri mixte
obiectele difera foarte mult)

Analiza Clusterelor 9 Analiza Clusterelor 11

Masurarea calitatii clusterelor Variabile Interval-scaled

n Metricile de disimilarite/similarite: similaritea este exprimata in n Sunt variabile ce iau valori continue pe o scala aproximativ liniara (ex:
temenii unei functii de tip distanta: d(i, j) temperatuta, inaltimea, latitudinea, etc.)
n Exista o functie de “calitate” distincta ce masoara “cat de n Unitatile de masura pot afecata procesul de clustering
bun” este un cluster.
n Functiile distanta au definitii diferinte in functie de valorile n Standardizarea datelor (masuratorilor)
atributelor interval-scaled, booleane, categoriale, ordinale si ¨ Se calculeaza abaterea medie liniara:
proportii s f = 1n (| x1 f − m f | + | x 2 f − m f | + ...+ | xnf − m f |)
n Se pot asocia ponderi atributelor in functie de aplicatie sau m f = 1n (x1 f + x 2 f + ... + xnf )
unde .
este media valorilor atributului f
semnificatia datelor.
¨ Se calculeaza valoarea standardizata (z-score)
n Este dificil de definit “suficient de similar” sau “suficient de x if − m f
bun” z if = sf
¨ Raspunsul este subiectiv
n Utilizarea abaterii medii liniare este mult mai robusta la anomali decat dispersia

Analiza Clusterelor 10 Analiza Clusterelor 12

Similaritatea/Disimilaritarea dintre obiecte Variabile binare
n Pentru a calcula similaritatea variabilelor binare se utilizeaza Tabela de contingenţă
n Se calculeaza cu ajutorul distantelor in cazul pentru date binare
Obiectul j
obiectelor caracterizate prin valori interval-scaled 1 0 sum
n Distanta Minkowski: 1 a b a+b
d (i, j ) = q (| x − x | + | x − x | + ...+ | x − x | )
q q q
Obiectul i 0 c d c+d
i1 j1 i2 j2 ip jp
sum a+c b+d p
unde i = (xi1, xi2, …, xip) si j = (xj1, xj2, …, xjp) sunt obiecte n Coeficientul de portivire simplu (similatitate invarianta, daca variabila binara este
p-dimensionale, si q este un intreg pozitiv simetrica):
b+c
d (i, j ) =
a+b+c+d
n Pentru q = 1, obtinem distanta Manhattan
n Coeficientul Jaccard (similatitate noninvarianta, daca variabila binara este asimetrica):

d(i, j) =| x − x | + | x − x | +...+ | x − x | b+c

i1 j1 i2 j 2 ip jp d (i, j ) =
a+b+c
Analiza Clusterelor 13 Analiza Clusterelor 15

Exemplu
Similaritatea/Disimilaritarea dintre obiecte (cont.)

n Daca q = 2, obtinem distanta Euclideana:

d (i, j ) = (| x − x | 2 + | x − x | 2 + ...+ | x − x | 2 ) Nume Sex Febra Tuse Test-1 Test-2 Test-3 Test-4
i1 j1 i2 j2 ip jp
Jack M Y N P N N N
n Proprietati ale unei distante Mary F Y N P N P N
Jim M Y P N N N N
n d(i,j) ≥ 0 ne-negativitate
¨ ‘Sex’ este un atribut simetric
n d(i,i) = 0 ¨ Restul atributelor nesimetrice
n d(i,j) = d(j,i) simetrie ¨ Consideram Y si P ca fiind 1, si N ca fiind 0 atunci distantele Jaccard sunt

n d(i,j) ≤ d(i,k) + d(k,j) inegalitatea triunghiului 0 + 1

d ( jack , mary ) = = 0 . 33
2 + 0 + 1
1 + 1
d ( jack , jim ) = = 0 . 67
1 + 1 + 1
1 + 2
d ( jim , mary ) = = 0 . 75
1 + 1 + 2
Analiza Clusterelor 14 Analiza Clusterelor 16
 Variabilele nominale Variablile Ratio-Scaled

n Sunt generalizari ale variabilelor boolene ce iau mai mult de 2 n Variabilele Ratio-scaled: masuratoare pe o scala
stari, ex., rosu, galben, albastru, verde nonlineara, similara cu o scala exponentiala,
n Metoda 1: Potrivirea simpla precum AeBt sau Ae-Bt
¨ p: nr total de variabile, m: nr de protriviri (cele 2 obiecte au aceiasi stare)
n Metode:
d ( i , j ) = p −p m
¨ Tratarea precum variabilele interval—nu este o alegere
buna! (de ce? – scala poate fi distorsionata)
n Metoda 2: Trasformarea in variabile binare simetrice
¨ Aplicarea unei transformari logaritmice
¨ Crearea unei variabile binare pentru fiecare din valorile unui atributul
nominal yif = log(xif)
¨ Tratarea lor ca valori ordinale continue tratand rangul lor cao
17 19
Analiza Clusterelor
valoare interval-scaled
Analiza Clusterelor

Variabile Ordinale Variabile mixte

n O variabila (atribut) ordinala poate avea valori discrete (un set stari) sau continuee
n O baza de date poate contine toate cele 6 tipuri
n Este importanta ordinea, ex: gradele didactice
¨ Binare simetrice, binare asimimetrice, nominale, ordinale, interval si ratio scaled
n Valorile pot fi mapate in ranguri
n O abordare ar fi utilizara unei formule de ponderare ce combina efectul tuturor atributelor
n Pot fi tratate similar cu valorile interval-scaled Σ p
δ
( f ) ( f )
d
¨ Se inlocuie valoarea x if cu rangul ei r if ∈ {1 ,..., M } d (i, j) = f = 1 ij ij

¨
f
Domeniul de valori al fiecarei variabile se mapeaza in [0, 1] inlocuind variabila f a obiectului
Σ p
f = 1
( f )
ij
δ
I cu r if − 1 ¨ Daca f este atribut binar sau ordinal:
z = d ij(f) = 0 daca x if = xjf , altfel dij(f) = 1 o.w.
if
M f
− 1
¨ Daca f este un atribut interval-based atunci acestea vor fi normalizate
¨ Se calculeaza disimilaritatea dintre obiecte utilizand metodele pentru variablele interval-
¨ Daca f este un atribut ordinal sau ratio-scaled
scaled
n Se calculeaza ragul rif si

n Se va inlocui cu z if se se va trata ca interval-scaled

z if =
r if −1
M f −1

Analiza Clusterelor 18 Analiza Clusterelor 20

Bibliografie
n Jiawei Han and Micheline Kamber, Data
Mining: Concepts and Techniques, Chapter 8

Analiza Clusterelor 21
 Algoritmi de Partitionare

n Metoda de partitionare: Construirea unei partitii a bazei de date D formata

din n obiecte intr-o multime de k clustere
Algoritmi de Clustering n Dandu-se k, se cauta o partitie de k clustere care optimizeaza criteriul de
partitionare ales:
¨ Optimul Global: presupune generarea tuturor partitiilor si evaluarea acestora
¨ Metode euristice:
n Algoritmul k-means (MacQueen’67): fiecare cluster este reprezentat de centrul
clusterului (centroid)
n Algoritmul k-medoids sau PAM (Partition Around Medoids) (Kaufman &
Rousseeuw’87): Fiecare cluster este reprezentat de unul din obiecte (numit
medoid), aflat cel mai aproape de centrul clusterului

Algoritmi de Clustering 3

Tipuri de Algoritmi de Clustering Algoritmul k-means

n Algoritmi de Partitionare: presupun construirea de partitii ale multimii de obiecte, evaluarea n Input: k nr. de clustere si baza de date cu n obiecte
acestora si realocarea obiectelor pentru a imbunatati partitionarea n Output: O multime de k clustere ce minimizeaza eroarea patratica
n Algoritmi ierarhici: se realizeaza o descompunere ierarhica a obiectelor din baza de date n Metoda
utilizand diverse criterii
1. Se aleg arbitrar k obiecte (centroizi) din spatiul definit de obiecte - centre ale clusterelor
n Algoritmi bazati pe densitate: se realizeaza clusterizarea utilizand functii de densitate; un initiale
cluster se mareste continuu atat timp cat densitatea este mai mare decat un prag dat 2. REPETA
n Algoritmi bazati pe Grid: spatiul obiectelor este impartit intr-o multime de celule sub forma 3. partitioneaza multimea de obiecte (re)asignand fiecare obiect centroidului cel mai apropiat
unei grile (retele) iar operatiile de clustering se vor efectua pe aceasta structura 4. centroizi initiali sunt inlocuiti de altii obtinuti prin calcularea mediilor obiectelor din fiecare cluster
(centrele de greutate)
n Algoritmi bazati pe model: Se considera un model pentru fiecare cluster si se cauta cele mai
potrivite date cu modelul dat 5. PANA CAND nu se mai modifica clusterele

Algoritmi de Clustering 2 Algoritmi de Clustering 4

 Algoritmul k-means (cont.) Algoritmul k-medoids
n Algoritmul are ca obiectiv minimizarea sumei patratelor n Algorimi K-Medoids: Cauta obiecte reprezentative (medoids) in clustere
erorilor ¨ PAM (Partitioning Around Medoids, Kaufmann & Rousseeuw 1987)
E = Σ ik=1Σ p∈C (dist ( p, mi )) 2 i n Porneste de la o multime de medoizi si iterativ inlocuie unul dintre acestia cu un non-medoid daca este

¨ p este un obiect din clusterul Ci imbunatatita distanta totala a clusterului rezultat

¨ mi este media clusterului Ci n PAM functioneaza cu date de dimensiuni mici deoarece are o complexitate mare

n Partitionarea se face incercand minimizarea sumei disimilaritatilor dintre fiecare obiect al unui cluster si
n Algoritmul poate fi aplicat numai pentru obiecte caracterizate medoidul corespunzator
de atribute numerice E = Σ ik=1Σ p∈Ci dist ( p, oi )
n Este sensibil la “outliers” care influenteaza mediile n Variante imbunatatite PAM
n Complexitate O(t·k·n), unde n =nr de obiecte, k =nr clustere, si ¨ CLARA (Kaufmann & Rousseeuw, 1990): PAM pe esationane
t este numarul de iteratii. In mod normal, k, t << n ¨ CLARANS (Ng & Han, 1994)

Algoritmi de Clustering 5 Algoritmi de Clustering 7

Exemplu: K-Means Algoritmul k-medoids

10 10
10
9 9
n Input: k nr. de clustere si baza de date cu n obiecte
9
8 8
8

7
7 7 n Output: O multime de k clustere ce minimizeaza suma disimilaritatilor tuturor
6 6
6

5
5 5 obiectelor fata de medoidul asociat fiecarui cluster
4 4
4
Asignam Recalculam
3
3

centroizi
3
n Metoda
fiecare
2 2
2
1 1
1
obiect 0
(mediile 0
1. Se aleg arbritrar k obiecte reprezentative ale clusterelor – medoizi initiali
0
centroid
0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10
0 1 2 3 4 5 6 7 8 9 10
clusterelor) 2. REPETA
ului cel
mai Repetam reasignam 3. asigneaza fiecare obiect ramas clusterului cu medoidul cel mai apropiat
apropiat 10 10
4. selecteaza aleator un obiect non-medoid Orandom
K=2 9 9

8 8
5. calculeaza costul total S al schimbarii obiectului medoid Oj cu Orandom
Se aleg arbritar K 7 7

obiecte centre ale IF S<0 THEN inlocuie medoidul Oj cu Orandom

6 6
6.
5 5

clusterelor 4 Recalculam 4

3 centroizi 3
7. PANA CAND nu se mai modifica clusterele
2
(mediile 2

1 1

0
clusterelor) 0
0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10

Algoritmi de Clustering 6 Algoritmi de Clustering 8

 Exemplu: PAM: Agloritm K-Medoids
Metode de clustering bazate pe ierarhii
Total Cost = 20
10 10 10

9 9 9

7
Se aleg
8

7
Asigneaza
8

7
n Metode bazate pe ierarhii de divizare
6 6 6

arbritar k fiecare
5

4 obiecte –
5

4 obiect
5

4
¨ Strategia top-down: initial toate obiectele
medoizi ramas
formeaza un singur cluster si apoi acesta e divizat
3 3 3

2
initiali 2
medoidului 2

1 1 1
celui mai
0
0 1 2 3 4 5 6 7 8 9 10
0
0 1 2 3 4 5 6 7 8 9 10 apropriat
0
0 1 2 3 4 5 6 7 8 9 10 in clustere din ce in ce mai mici pana cand fiecare
Se selecteaza aleator
K=2
un nonmedoid,Oramdom
obiect formeaza un singur cluster sau s-a ajuns la
Total Cost = 26
10 10
numarul de clustere dorit
REPETA 9

8 Calculeaza
9

8
Schimba O cu
Oramdom
7
costul 7

PANA nu se 6

5 schimbari
6

5
Daca calitatea 4 4

mai schimba se 3

2
3

2
imbunatateste 1 1

0 0

9 11
0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10
Algoritmi de Clustering Algoritmi de Clustering
9

Metode de clustering bazate pe ierarhii Metode de clustering bazate pe ierarhii

Step 0 Step 1 Step 2 Step 3 Step 4

n Metode bazate pe ierarhii de aglomerare agglomerative
(AGNES)
¨ Strategia bottom-up: initial fiecare obiect formeaza a
ab
un cluster si apoi aceste clustere sunt unite in b abcde
clustere din ce in ce mai mari pana cand toate c
obiectele sunt grupate intr-un singur cluster sau o cde
d
anumita conditie de terminare e indeplinita de
e
divisive
Step 4 Step 3 Step 2 Step 1 Step 0 (DIANA)

Algoritmi de Clustering 10 Algoritmi de Clustering 12

Bibliografie
n Jiawei Han and Micheline Kamber, Data
Mining: Concepts and Techniques, Chapter 8

Algoritmi de Clustering 13
 Descrierea Problemei
n Se considera o baza de date D cu tranzactiile
Minarea Paternurilor clienţilor
n Fiecare tranzactie e caracterizata prin:
Secvenţiale ¨ Customer-ID = identificatorul clientului
¨ Transaction-Time = momentul de timp la care a fost efectuata tranzactia
¨ Multimea de produse din acea tranzactie
n Cantitatile produselor cumparate sunt considerate neimportante
n Un client cu acelasi ID nu poate efectua in acelasi timp mai multe
tranzactii
n Se pune problema identificarii paternurilor secventiale din
baza de date considerata

Minarea Paternurilor Secvenţiale 3

Ce sunt paternurile secventiale? Descrierea Formala a Problemei

¨ Regulile de Asociere: se referă la produse ce sunt n Rakesh Agrawal, Ramakrishnan Srikant, 1995
cumparate împreună (în acelasi timp, în aceeaşi tranzacţie) n Itemset : O multime nevida de itemi: i=(i1, i2 … )
n Paternuri intra-tranzactie ¨ Putem presupune ca acesti itemi pot fi mapati într-o multime de
¨ Paternurile Secventiale: se refera la produse cumparate numere intregi contiguă.
într-o anumita ordine la momente de timp diferite n Secventa : O lista ordonata de itemseturi s=< s1 s2 … sn>
n Paternuri inter-trazactie ¨ Secventa Inclusa : O secventa <a1 a2 … an> este inclusa in secventa
<b1 b2 … bm> daca exista i1 < i2 < … < in astfel incat a1⊆ bi1, a2 ⊆ bi2
n Exemplu: o persoană care a cumpărat filmul Star Wars, a cumparat
… an ⊆ bi .
apoi Empire Strikes Back, apoi Return of the Jedi; între aceste n
cumparaturi persoana respectiva e posibil sa mai fi cumparat si alte n Ex: secventa <(3) (4,5) (8)> ⊆<(7)(3,8)(9)(4,5,6) (8)>
filme, iar în cadrul tranzacţiilor respective este posibil sa mai fi n Lungimea unei secvente: numarul de itemseturi din secventa
cumpărat şi alte produse.
n k-secventa: secventa de lungime k.

Minarea Paternurilor Secvenţiale 2 Minarea Paternurilor Secvenţiale 4

Descrierea Formala a Problemei (cont.) Exemplu
Customer Transaction Produse
n Secventa cumparator: lista de tranzactiilor unui cumparator ordonate crescator ID Time cumparate Customer ID Secventa Cumparator
dupa momentul tranzactiei.
1 June 25 '93 30 1 < (30) (90) >
¨ Spunem ca un cumparator suporta o secventa s daca secventa s este continuta in
secventa cumparator asociata acestuia. 1 June 30 '93 90 2 < (10 20) (30) (40 60 70) >
n Suportul unei secvente: Procentul cumparatorilor ce suporta secventa respectiva din 2 June 10 '93 10,20 3 < (30 50 70) >
numarul total al cumparatorilor.
2 June 15 '93 30 4 < (30) (40 70) (90) >
n Large secventa (secventa frecventa): O secventa al carei suport depaseste un prag
minim dat: minsup. 2 June 20 '93 40,60,70 5 < (90) >
n Secventa Maximala: Intr-o multime de secvente, o secventa s este maximala daca s 3 June 25 '93 30,50,70
nu este continuta de nici o alta secventa
4 June 25 '93 30 Secvente Maximale cu suport >= 40%
n Suportul unui itemset: Procentul cumparatorilor ce au cumparat produsele din
itemsetul i intr-o singura tranzactie din numarul total al cumparatorilor. Itemsetul si 4 June 30 '93 40,70 < (30) (90) > suportata de 1 si 4
1-secventa <(i)> vor avea acelasi suport. 4 July 25 '93 90 < (30) (40 70) > suportata de 2 si 4
n Large Itemset (litemset): itemset cu suportul mai mare decat un prag minim dat.
5 June 12 '93 90
Obs: Daca consideram minsup = 40%, atunci o secventa frecventa trebuie sa fie suportata
de cel putin doi cumparatori (2=0.40*5)
Suportul < (10 20) (30) > = 1/5 =20% < minsup (suportata decat de cumparatorul 2)
< (30) >, < (70) >, < (30) (40) > sunt secvente frecvente, insa nu sunt maximale.
Minarea Paternurilor Secvenţiale 5 Minarea Paternurilor Secvenţiale 7

Algoritm de extragere a paternurilor

Problema Minarii Paternurilor Secventiale
secventiale
n Dandu-se o baza de date D ce contine 1. Faza de Sortare
tranzactiile clientilor, problema minarii paternurilor 2. Faza Litemset
secventiale consta in gasirea secventelor
maximale din multimea tuturor secventelor ce au 3. Faza deTransformare
suportul mai mare sau egal decat un prag minim 4. Faza Secventa
dat. 5. Faza Maximala

Minarea Paternurilor Secvenţiale 6 Minarea Paternurilor Secvenţiale 8

1. Faza de sortare 3. Faza de Transformare
o Fiecare tranzactie (itemset) este inlocuita cu multimea tuturor
n Se sorteaza baza de date: Customer Transaction Produsele large itemseturilor continute in acea tranzactie.
ID Time cumparate
¨ Customer ID - cheia o Tranzactiile cu niciun litemset sunt eliminate. (totusi secventele
1 June 25 '93 30
principala. vide vor contribui la numararea nr. total de cumparatori)
1 June 30 '93 90
Cust ID Secventa [Link] Secventa [Link] Dupa Mapare
¨ Transaction-Time - 2 June 10 '93 10,20
1 < (30) (90) > <{(30)} {(90)}> <{1} {5}>
cheia secundara. 2 June 15 '93 30
2 < (10 20) (30) (40 60 70) > <{(30)} {(40),(70),(40 70)}> <{1} {2,3,4}>
n Baza de date cu tranzactii 2 June 20 '93 40,60,70
3 < (30 50 70) > <{(30),(70)}> <{1,3}>
D este convertita într-o 3 June 25 '93 30,50,70
4 < (30) (40 70) (90) > <{(30)} {(40),(70),(40 70)} {(90)}> <{1} {2,3,4} {5}>
baza de date cu secvente 4 June 25 '93 30

cumparator. 4 June 30 '93 40,70 5 < (90) > <{(90)}> <{5}>

4 July 25 '93 90 Obs: (10 20) a fost eliminata neindeplinind pragul de suport minim.
(40 60 70) este inlocuita cu multimea de litemseturi {(40),(70),(40 70)} (60 nu are minsup)
5 June 12 '93 90
11
Minarea Paternurilor Secvenţiale 9 Minarea Paternurilor Secvenţiale 11

2. Faza Litemset Customer Transaction Produse Faza Secvență

ID Time cumparate
n Se determina multimea L a litemset-urilor (large 1 June 25 '93 30
itemseturilor – Alg. Apriori). Suportul absolut al unui
itemset este incrementat o singura dată chiar dacă 1 June 30 '93 90
n Se determina Large Secventele utilizand unul
clientul cumpară acelasi set de produse in doua
tranzactii diferite
2 June 10 '93 10,20 din algoritmi:
n Se determina simultan multimea large 1-secventelor: 2 June 15 '93 30
{<(l)>, l ∊ L } 2 June 20 '93 40,60,70
¨ AprioriAll
n Litemset-urile se mapeaza la o multime de nr. intregi 3 June 25 '93 30,50,70 ¨ AprioriSome
Large Itemseturi Mapat La 4 June 25 '93 30
(30) 1 4 June 30 '93 40,70 ¨ DynamicSome
(40) 2 4 July 25 '93 90
(70) 3 5 June 12 '93 90
(40 70) 4
n Vom reveni asupra acestui pas
(90) 5
*Motivul maparii: tratarea litemseturilor ca entitati singulare
- in acest fel compararea a doua itemseturi necesita un timp constant
- reducerea timpului necesar verificarii ca o secventa este continuta de o secventa cumparator
Minarea Paternurilor Secvenţiale 10 Minarea Paternurilor Secvenţiale 12
Faza maximala AprioriAll
n Din large secventele determinate se extrag n Are la baza algoritmul Apriori clasic utilizat
secventele maximale. pentru determinarea regulilor de asociere
¨ S: multimea tuturor large secventelor
¨ n: lungimea celei mai lungi secvente
n Determina toate large secventele
for (k=n; k>1; k--) do n Secventele non-maximale sunt eliminate in
for each k-sequence sk do “Faza Maximala"
Delete from S all subsequences of sk

Minarea Paternurilor Secvenţiale 13 Minarea Paternurilor Secvenţiale 15

Schema Fazei Secvență AprioriAll

L1 = {large 1-sequences}
n In aceasta faza se determina toate large secventele. for (k = 2; Lk-1 ≠ {}; k++) do
begin
Ck = New candidates generated from Lk-1
multimea de secvente sămânță foreach customer-sequence c in the database do
Increment the count of all candidates in Ck
Secvente candidat that are contained in c.
Lk = Candidates in Ck with minimum support.
end
Se parcurge baza de date Answer = Maximal Sequences in UkLk
pentru a calcula suportul

Notatie:
Large Secvente Lk: Multimea large k-secventelor
Ck: Multimea k-secventelor candidate

Minarea Paternurilor Secvenţiale 14 Minarea Paternurilor Secvenţiale 16

 Bibliografie
AprioriAll (Exemplu)
n Generarea secventelor candidate
¨ Uneşte Lk-1 cu ea insusi pentru a forma Ck
insert into Ck
n Rakesh Agrawal,Ramakrishnan Srikant,
select [Link] 1 ,[Link] k-1 ,[Link] etk-1
from L k-1 p, Lk -1 q
where [Link] 1 =[Link] 1 …
Mining Sequential Patterns, Proc. of the Int’l
¨
[Link] k-2 =[Link] set k-2

Sterge c daca Ck contine o (k-1)-sub secventa ce nu este in Lk-1

Conference on Data Engineering (ICDE)
L3
C4: dupa unire
March 1995
3-Seq
<1 2 3>
4-Seq
C4: dupa reducere
[Link]
<1 2 3 4>
<1 2 4> 4-Seq
<1 2 4 3>
<1 3 4> <1 2 3 4>
<1 3 4 5>
<1 3 5>
<2 3 4> <1 3 5 4>

Minarea Paternurilor Secvenţiale 17 Minarea Paternurilor Secvenţiale 19

AprioriAll (Exemplu)
Minisup = 40%
L1 L2 L3
Secentele cumparator
1-Seq Sup 2-Seq Sup 3-Seq Sup
<{1 5} {2} {3} {4} > <1> 4 <1 2> 2 <1 2 3> 2
<{1} {3} {4} {3 5}> <2> 2 <1 3> 4 <1 2 4> 2
<3> 4 <1 4> 3 <1 3 4> 3
<{1} {2} {3} {4}>
<4> 4 <1 5> 3 <1 3 5> 2
<{1} {3} {5}>
<5> 4 <2 3> 2 <2 3 4> 2
<{4} {5}> <2 4> 2 <3 4 5> 1
<3 4> 3 L4
<3 5> 2 4-Seq Sup
<4 5> 2 <1 2 3 4> 2
Answer: <1 2 3 4>, <1 3 5>, <4 5>
<2 5> 0

Minarea Paternurilor Secvenţiale 18