Universitatea Lucian Blaga, Sibiu
Facultatea de Stiinte
Proiect Practic
Machine Learning
Contents
1. Introducere..................................................................................................................3
2. Aspecte teoretice.........................................................................................................3
3. Algoritmul de clasificare Naive Bayes........................................................................4
3.1.
Algoritmul Naive Bayes.......................................................................................5
4. Algoritmul de clustering COBWEB............................................................................6
4.1.
Clasificarea algoritmilor de clustering..................................................................6
4.2.
Clustering conceptual...........................................................................................7
4.3.
Algoritmul COBWEB..............................................................................................8
4.3.1.
Prezentare generala............................................................................................8
4.3.2
Modul de functionare.........................................................................................8
5. Testare si analiza rezultatelor.......................................................................................9
6. Concluzii...................................................................................................................14
1. Introducere
Exploatarea datelor, cunoscuta mai degraba ca data mining, este procesul de sortare
a unor cantitati mari de date si de extragere a informatiilor relevante din acestea.
Termenul este utilizat de obicei de organizatiile ce se ocupa cu prelucrarea informatiilor
companiilor si de analistii financiari, dar este folosit din ce n ce mai mult si n domeniul
stiintific cu referire la extragerea informatiilor din volumuri mari de date generate de
metode experimentale moderne. In relatie cu planificarea resurselor economice, termenul
se identifica cu analiza statistica si logica a unor mari volume de date despre tranzactii, n
cautarea unor sabloane care pot ajuta procesul de luare a deciziilor
Procesul de data mining implica in general patru clase distincte de actiuni:
Clasificarea aranjarea datelor in grupuri predefinite; exemple de algoritmi:
invatarea prin arbori de decizie, retele neuronale, clasificare bayesiana, etc.
Gruparea (clustering) similara cu clasificarea, insa fara grupuri predefinite;
algoritmul va incerca sa grupeze la un loc articole similare.
Regresia cautarea unei functii care modeleaza cat mai fidel datele.
2. Aspecte teoretice
Weka este o colectie de algoritmi de invatare pentru data mining. Algoritmii pot fi
aplicati fie direct pe un set de date sau folositi chiar din codul Java. Weka contine
instrumente pentru preprocesarea datelor, clasificare, regresie, reguli de asociere si pentru
vizualizare. De asemenea, este potrivit pentru dezvoltarea de noi scheme de invatare.
Weka este utilizat in cercetare, educatie si in cadrul aplicatiilor. Aplicatia insumeaza un
set vast de instrumente de preprocesare a datelor, algoritmi de invatare si metode de
evaluare, interfete grafice utilizator (incluzand vizualizarea datelor) si un mediu pentru
compararea algoritmilor de invatare.
Weka este un software open source, sub licenta generala publica GNU. "WEKA" provine
de la Mediul Waikato pentru Analiza Cunostiintelor (Waikato Environment for
Knowledge Analysis), si a fost dezvoltat la Universitatea Waikato din Noua Zeelanda.
WEKA este extensibil si a devenit o colectie de algoritmi pentru invatare in scopul
rezolvarii problemelor de data mining din lumea reala. A fost implementat in limbajul
Java si ruleaza aproape pe orice platforma.
WEKA este usor de folosit si usor de aplicat pe mai multe nivele diferite. Libraria WEKA
poate fi accesata de propriul program Java, si poate implementa noi algoritmi pentru
invatare.
Exista trei scheme majore implementate in WEKA. (1) Scheme implementate pentru
clasificare. (2) Scheme implementate pentru previziunea numerica. (3) Meta-scheme
implementate.
In afara schemelor actuale de invatare, WEKA contine, de asemenea, o varietate mare de
instrumente care pot fi folosite pentru preprocesarea seturilor de date, astfel incat este
posibila concentrarea pe propriul algoritm fara a se tine cont de detalii precum citirea
datelor din fisier, implementarea algoritmilor de filtrare si oferirea de code sursa pentru
evaluarea rezultatelor.
3. Algoritmul de clasificare Naive Bayes
Definiie: Fiind date dou evenimente A si B, se numeste probabilitatea
evenimentului A condiionat de evenimentul B si se noteaz
probabilitatea ca evenimentul A s fie ndeplinit atunci cnd se stie c evenimentul B a
avut loc. n relaia de mai sus, valoarea Pr(AB) reprezint probabilitatea ca evenimentele
A si B s aib loc simultan.
Teorema: Fiind date evenimentele A1, A2, , Ak, mutual exclusive, si evenimentul B
dependent de acestea, se poate demonstra expresia
Teorema lui Bayes reprezint un prim mijloc de a determina probabilitatea unui
eveniment Ai (component a unei repartiii) n situaia n care se stie c apariia acestuia
este influenat de ndeplinirea unui alt eveniment independent B.
Prin mulime de evenimente mutual exclusive si exhaustive se neleg acele evenimente
care satisfac urmtoarele condiii:
oricare ar fi dou evenimente din mulimea respectiv, acestea nu pot avea loc
simultan (exclusivitate);
cu evenimentele din mulime se pot descrie toate strile n care se afl sistemul la
care aceste evenimente fac referire (exhaustivitate).
n aceasta relaie, expresia nu trebuie considerat n sensul probabilitii de apariie a
evenimentului B atunci cnd se cunoaste c evenimentul Ai a avut loc, deoarece
estimarea evenimentului B este anterioar estimrii lui Ai. Interpretarea corect a acestei
expresii din cadrul teoremei lui Bayes este de probabilitate ca evenimentul B s fi avut
deja loc stiind c apariia sa a fost urmat de apariia evenimentului Ai.
Teorema lui Bayes pentru funcia de probabilitate posterioar a unui parametru
Dac parametrul W poate lua valorile w1, w2, , wk, cu repartiia
si X este o variabil aleatoare observabil, atunci.
unde f (x|wi ) reprezint repartiia variabilei aleatoare X atunci cnd W = w1 .
3.1.
Algoritmul Naive Bayes
Se foloseste pentru a clasifica date neetichetate cu ajutorul unor estimari folosind date
de antrenare etichetate. Conform cu teorema Bayes se poate obtine probabilitatea
posterioara cunoscand probabilitatea anterioara probabilitatea ca un document sa apartina
la un subiect.
Probabilitatile pentru noile date de antrenare ale unui clasificator (evidence)
P(D|T)/(P(D| T ) unde: D document, T topic.
Estimarea acestor probabilitati se face prin masurarea frecventei de aparitie a cuvintelor
intrun set de documente de antrenare.
wk este cuvantul k din cele n cuvinte ale documententului D.
Documentele neetichetate se folosesc pentru a imbunatati setul de documente de
antrenare.
Clasificarea _aive Bayes - clasificarea binara
5
;date de intrare:
;X: set-ul de antrenare (atribute cu valori discrete)
;Y: clasele set-ului de antrenare (clasa p si clasa n)
;z: sablonul nou (care se doreste a fi clasificat)
;date de iesire
;prob_p, prob_n: probabilitatea ca z sa fie in clasa p, respectiv in clasa n
;c: clasa in care se va regasi z
n = dimensiunea lui Y
n_p = numarul de elemente din Y care apartin clasei p
n_n = numarul de elemente din Y care apartin clasei n
;probabilitatile apriori estimate pentru clasele p si n
prior_p = n_p / n
prior_n = n_n / n
; se presupune ca z are m-atribute (z1,...zm)
;se determina toate probabilitatile conditionate P(zi|p) si P(zi|n)
;corespunzatoare fiecarui atribut zi din z
p_zi = procentul pentru care zi ori apare ca valoare de atribut i in modele din clasa X cu
eticheta p
n_zi = procentul pentru care zi ori apare ca valoare de atribut i in modele din clasa X cu
eticheta n
end
prob_p = prior_p*p_z1*...*p_zm;
prob_n = prior_n*n_z1*...*n_zm;
daca prob_p > prob_n atunci
c <- p altfel c <- n .
4. Algoritmul de clustering COBWEB
4.1. Clasificarea algoritmilor de clustering
Majoritatea algoritmilor de clustering se clasitica in doua mari categorii: algoritmi
ierarhici si algoritmi partitionali. In cazul algoritmilor ierarhici, clusterele sunt
determinate succesiv, utilizand clusterele formate la pasii anteriori. Algoritmii partitionali
determina toate clusterele in paralel. Exista si alte metode de clustering, ce nu se
incadreaza in aceste clase, dintre care amintim clasa algoritmilor de clustering spectral,
ce utilizeaza o matrice de similaritate pentru a reduce numarul de dimensiuni (variabile)
din problema.
6
In clasa algoritmilor ierarhici de clustering se idetifica doua tipuri de strategii:
Clustering algomerativ aceasta este o strategie de tip bottom-up, ce porneste
de la o stare in care toate elementele reprezinta clustere individuale si fuzioneaza
succesiv aceste clustere pana obtine schema finala.
Clustering diviziv aceasta este o strategie de tip top-down, cu o stare initiala
caracterizata de un singur cluster, format din multimea tuturor elementelor si
progresand prin divizarea sa in clustere dn ce in ce mai restranse.
Clusteringul ierarhic construieste (in cazul strategiilor aglomerative) sau segmenteaza
(in cazul strategiilor divizive) o ierarhie de clustere. Reprezentarea clasica a unei astfel de
ierarhii este in forma de arbore si poarta numele de dendrograma. Radacina dendrogramei
consta dintr-un singur cluster continand toate elementele, iar frunzele corespund
elementelor individuale. Algoritmii aglomerativi vor incepe la nivelul frunzelor,
fuzionand treptat clustere, in timp ce algoritmii divizivi pornesc explorarea arborelui de
la radacina si segmenteaza recursiv clustere.
Similaritatea intre elemente se poate determina pe baza oricaror criterii valide, iar pe baza
acestor criterii algoritmul poate lua decizia fuzionarii sau divizarii de clustere.
4.2. Clustering conceptual
Clusteringul conceptual reprezinta o paradigma de invatare pentru clasificare
nesupervizata dezvoltata in principal in anii 80. Acesta se remarca fata de procedeele
obisnuite de clustering de date prin generarea unei descrieri conceptuale pentru fiecare
categorie obtinuta. Printre paradigmele inrudite clusteringului conceptual amintim:
invatarea prin arbori de decizie, analiza conceptelor formale si invatarea cu modele de
amestec (mixture model).
Majoritatea metodelor conceptuale sunt capabile sa genereze structuri ierarhice de
clase. Se porneste de la o multime de obiecte neclasificata, insotita de o modalitate de a
determina daca exista sau nu similitudini intre ele, numita limbaj de descriere.
Clusteringul conceptual este strans legat de clusteringul de date, insa formarea clusterelor
nu este, in cazul sau, conditionata exclusiv de structura inerenta a datelor. In clusteringul
conceptual, limbajul de descriere de care beneficiaza agentul de invatare este direct
responsabil de modul in care se formeaza clusterele: o multime de date care formeaza o
grupare evidenta in statistica poate scapa nedetectata daca limbajul de descriere a
conceptelor este incapabil sa semnaleze respectivul criteriu de grupare.
In majoritatea implementarilor, limbajul de descriere se limiteaza la utilizarea vectorilor
de caracteristici (taxonomie numerica), insa algoritmul COBWEB introduce un limbaj de
descriere a caracteristicilor probabilistic.
4.3.
Algoritmul COBWEB
4.3.1. Prezentare generala
Publicat de Fisher in 1987, algoritmul COBWEB vine in intampinarea unor probleme ce
afectau algoritmii de clustering dezvoltati pana la acea data. Acesti algoritmi utilizau o
taxonomie numerica drept limbaj de descriere: obiectele erau reprezentate ca o colectie
de trasaturi, fiecareia fiindu-i asociata o valoare numerica.
Prin utilizarea taxonomiei numerice, compararea obiectelor se rezuma la aplicarea unei
functii de distanta construita pe baza unui vector cu n trasaturi. Conform acestui sistem
putem avea urmatoarele definitii: pasare = {zboara, canta, este ovipara, cuibareste in
copaci, mananca insecte}; liliac = {zboara, este vivipar, mananca insecte} etc. Astfel de
definitii nu sunt bune in orice situatie: ele vor respinge, de exemplu, apartenenta gainii la
specia pasare. Spre deosebire de acest sistem inflexibil, omul distinge grade diferite de
apartenenta la categorii. De pilda, mierla poate fi considerata un exemplu mai bun de
pasare decat gaina, deoarece caracteristicile particulare ale acesteia se intalnesc la un
numar mai mare de pasari.
Categoriile se definesc printr-un sistem complex de similaritati intre membri si exista si
posibilitatea ca anumite proprietati sa difere intre elemente din aceeasi clasa. Vectorii de
trasaturi sau arborii de decizie nu pot realiza clasificari de calitate in astfel de situatii.
Algoritmul COBWEB introduce o noua metoda de descriere a categoriilor, ce include si
grade de apartenenta. Acesta reprezinta categoriile in mod probalistic, in loc sa defineasca
membrii printr-o multime de valori ce trebuie sa fie mereu prezente.
Algoritmul COBWEB va calcula probabilitatea cu care fiecare valoare a unei trasaturi
este prezenta la un anumit obiect: p(fi = vij| ck) reprezinta probabilitatea conditionata cu
care fiecare trasatura fi va avea valoarea vij daca obiectul este membru al categoriei ck.
La intalnirea unui nou exemplu, COBWEB ia in considerare calitatea deciziei de a plasa
obiectul intr-o categorie existenta sau de a modifica ierarhia. Pentru a evalua calitatea
clasificarii, algoritmul propus de Fisher utilizeaza un criteriu numit utilitatea categoriilor
(CU).
4.3.2 Modul de functionare
Algoritmul COBWEB organizeaza onservatiile in mod incremental intr-un arbore
de clasificare. Fiecare nod din dendrograma reprezinta o clasa (un concept), fiind
etichetat de un concept exprimat probabilistic, ce reliefeaza distributia valorilor
trasaturilor tuturor obiectelor clasificate in acel nod. Arborele de clasificare se poate
utiliza pentru a prezice atribute absente sau pentru a stabili clasa unui nou obiect.
Inserarea de obiecte in arbore se realizeaza succesiv. La inserarea unui nou obiect,
algoritmul COBWEB realizeaza o parcurgere de sus in jos (top-down) a arborelui,
avand ca punct de start radacina acestuia. Pentru fiecare nod, algoritmul trebuie sa
selecteze ce operatie va executa asupra arborelui. Exista patru operatii posibile, iar
COBWEB va executa operatia ce produce o valoare maxima pentru functia de utilitate a
categoriilor.
Cele patru operatii posibile sunt:
Inserarea
Crearea
Fuziunea
Diviziunea
5. Testare si analiza rezultatelor
Pentru testare s-a utilizat aplicatia open-source de data mining si invatare automata
WEKA (Waikato Environment for Knowledge Analysis), dezvoltata de University of
Waikato din Noua Zeelanda. Aplicatia, scrisa in JAVA, este distribuita printr-o licenta
GNU
General
Public
License
si
poate
fi
descarcata
la
adresa
[Link] . Versiunea utilizata in cadrul acestui experiment
este Weka 3.6.1.
Pentru testare s-a considerat un fisier de intrare standard oferit de catre program,
[Link]. Fisierul contine 57 de inregistrari de clasificat, reprezentand dosare ale unui
centru de analiza a fortei de munca.
Attributes: 5
Se doreste clasificarea dosarelor in doua clase:
@attribute 'class' {'bad','good'}
Fiind vorba despre un algoritm de clustering, invatarea exemplelor este nesupervizata. Se
va cere clasificatorului sa ignore atributul class la operatia de invatare. Acesta va fi
utilizat doar la finalul operatiei de clustering, pentru a lega clusterele gasite de clasele
dorite.
Figura 1: Preprocesarea datelor de intrare in Weka
In figura 1 am prezentat un screenshot cu etapa de preprocesare a datelor de intrare, iar in
figura 2 un screen shot reprezentand rezultatele afisate de aplicatie in urma rularii
algoritmului COBWEB.
10
Figura 2: Aplicarea algoritmului de clustering COBWEB in WEKA
In urma rularii algoritmului COBWEB se obtine urmatoarea ierarhie de concepte:
11
Figura 7: Ierarhia de concepte generata de Weka
Rezultatele clasificarii sunt prezentate mai jos.
Numar total de concepte din arbore : 12.
Numar de clustere (noduri frunza) obtinute : 8
Distributia inregisrarilor per cluster:
Clasa
obiectul
ui
Cluster Cluster Cluster Cluster Cluster Cluster Cluster
2
3
4
6
7
9
10
Cluster1
1
Da
Nu
Total
obiecte
1
1
2
0
1
1
1
0
1
0
1
1
1
0
1
1
0
1
12
1
0
1
1
0
1
Cluster
Numar de obiecte
Procent din total
2
3
4
6
7
9
10 -> da
2
1
1
1
1
1
1
22%
11%
11%
11%
11%
11%
11%
11 -> nu
11%
Clusterele de la 0 ,1,5 si 8 reprezinta noduri interne in arbore (au fost divizate, a se vedea
figura 7).
Figura 8: Distributia inregistrarilor per cluster; cu x sunt marcate inregistrarile
incadrate in clusterele cluster10 (asociat clasei da) si cluster11 (asociat clasei nu)
Utilizand optiunea Classes to clusters evaluation, Weka evalueaza ca cel mai aporpiat
cluster de clasa dorita da este clusterul 10, iar cel mai apropiat de clasa dorita nu este
clusterul 11.
Numarul de inregistrari clasificate gresit: 7
Eroarea = 7/8 = 77.77 %
13
6. Concluzii
Algoritmul COBWEB este eificient in producerea de arbori cu un numar restrans
de clase. Datorita faptului ca permite o analiza probabilistica a apartenentei, categoriile
create de el sunt flexibile si robuste. Principalul dezavantaj il reprezinta faptul ca
generarea conceptelor este afectata de ordinea in care sunt introduse datele de intrare.
14