Ministerul Educaţie din Republica MoldovaUniversitatea Tehnică a Moldovei

Facultatea Calculatoare Informatică şi MicroelectronicăCatedra Informatică Aplicată

Raport Lucrarea de laborator nr.2

la disciplina : Data Mining

Tema: Clusterizarea textelor. Algoritmii de clusterizare.

A executat: Ursu Ion studentul gr MAI-131M

A verificat: Objelean N. Conf. univ.

Chişinău 2014

Sarcina lucrării :

1. De studiat şi analizat algoritmii de clusterizare:

- Naive Bayes

- K-means

- Clusterizarea ierarhică

Rezolvare sarcinilor:

Descrierea algoritmilor în raport.

- Naive Bayes

- K-means

- Clusterizarea ierarhică

Algoritmul Naive Bayes

Formele sunt atât obiectele fizice observabile dar şi modele matematice relativ la celule, particule,

forme de undă, spectre de frecvenţă (imagini TV, semnale radar, zgomote, EKG-uri), aplicaţiile de

recunoaşterea formelor fiind prezente în medicină, imageria satelitară, meteorologie, criminalistică sau

aplicaţii militare.

O formă dată poate fi descrisă printr-un set de entităţi caracteristice exprimate prin numere reale

(biţi) XF=(x1,….xn), unde N depinde de precizia urmărită (de exemplu rezoluţia unei imagini). Algoritmii

de clasificare Bayes fac parte din metodele statistice de clasificare şi recunoastere a formelor.

1.1. Algoritmi de clasificare Bayes (cazul a două clase)

Fie Ω = Μ=∪i 1ω1 (M clase disjuncte de forme de acelaşi tip ω1, ..., ωM, M ≥ 2) şi se consideră cunoscute

din determinări statistice probabilităţile apriori P ( ωi ) ale claselor ωi (pentru i=1…M), şi se presupune că

P( ωi ) > 0 şi ∑=Mi 1P( ωi ) = 1

1.1.1. Regula lui Bayes de clasificare (ipoteza binară)

În cazul a două clase de forme ω1, ω2 (M=2), o formă nouă de intrare X (vector aleator n-

dimensional de caracteristici) poate fi clasificată (teoretic) prin compararea probabilităţilor aposteriori după

regula :

P ( ω1 | X ) >< P ( ω2 | X ) => X ∈2 ω 1ω (1) unde:

– i=1,2:

– P ( ωi | X ) este probabilitatea aposteriori (probabilitatea ca după ce X a fost clasificat, forma X să

aparţină clasei ωi );

– P ( ωi ) este probabilitatea apriori a clasei ωi, i=1,2 (probabilitatea ca o formă să aparţină clasei ωi )

Algoritmul K-means

Clusterizarea de documente partiționala încearcă partiționarea netedă a unei colecții de documente

într-un număr predefinit de clustere disjuncte. Algoritmii de clusterizare partiționali sunt împărtiți în

algoritmi cu metode iterative sau de realocare și în algoritmi cu metode cu un singur pas. Cei mai cunoscuți

algoritmi de clusterizare partitională sunt k-means, care se bazează pe ideea ca centrul clusterului, numit

centroid, este o bună reprezentare a clusterului. In prima fază se aleg n centroizi; apoi se calculează distanța

cosinus dintre fiecare document din colecție și centroizi, iar documentul este asignat clusterului cu

centroidul cel mai apropiat. In cea de-a doua etapă sunt recalculați centroizii noului cluster și procedura

continuă până este atins un anumit prag. Un alt algoritm de clusterizare partiționala este algoritmul celei

mai apropiate vecinatati care va fi detaliat in capitolul următor

* Este o metoda de clusterizare iterativa

* Metoda K-means alcatuieste clustere pe atribute cu valori numerice.

* Ea imparte instantele in grupe disjuncte folosind o marime numita „distanta”.

* In functie de implementari aceasta „distanta” poate fi calculata folosind mai multe formule.

Algoritmul K-means este urmatorul:

Pas1: Se precizeaza cate clustere va avea impartirea:

n acesta este parametrul k

Pas2: Sunt alese aleator k puncte:

n care vor fi desemnate „centrele clusterelor”: C1, ,Ck

Pas3: Instantele sunt repartizate in clusterul de a carui centru este cel mai aproape corespunzator distantei

folosite.

Pas4: Pentru fiecare cluster format dupa repartizarea tuturor instantelor se va calcula „centroid-ul” care este

media instantelor din acel cluster

Pas5: Centru clusterului va fi inlocuit cu „centroid”-ul calculat la pas 4.

Pas6: Algoritmul este reluat de la pasul 2.

Etapele algoritmului k-means

* In functie de implementare parametrul k este predefinit sau este introdus de utilizator.

* Deoarece instantele sunt repartizate in clusterul de a carui centru este mai aproape centrele se vor

stabiliza pe un minim. Principala problema de implementare este ca minimul poate fi unul local si nu

global ceea ce poate duce la o clasificare incorecta a instantelor.

* De-a lungul anilor au existat mai multe implementari si perfectionari a acestui algoritm. Cea mai des

folosita implementare este cea in care se produce o clusterizare ierarhica astfel:

n Pas1: Se aplica algoritmul k-means pe intregul set de date pentru k = 2.

n Pas2: Pentru fiecare dintre clusterele formate se aplica algoritmul k-means (k = 2).

n Astfel algoritmul k-means este reluat recursiv formand o clasificare ierarhica.

Clusterizarea ierarhic ă .

Algoritmii de clusterizare ierarhică produc o secvență de partiții de

același fel. Similaritatea dintre fiecare pereche de documente este stocată într-o matrice de

similaritate n x n. La fiecare pas, algoritmul fie unește două clustere, fie împarte un cluster în

două. Rezultatul unei clusterizari poate fi văzut sub forma unei structurii arborescente cu un

cluster rădăcină care conține toate documentele colecției și multe clustere la bază, fiecare

continând un singur document.

Folosind un algoritm de mai sus să se dezvolte o aplicație care să permită determinarea celui mai

apropiat grup de documente pentru un document ce conține date similare și care este specificat ca intrare.

(Utilizați textele de la lab.1)

Fig1. Determinarea celui mai apropiat grup de documente pentru un document ce conține date similare

Fig2.Clasificarea dupa algoritmul Naïve Bayes

Codul sursă

@relation determina_grup

@attribute salient-fragment-Ostrovul numeric@attribute salient-fragment-clanuril numeric@attribute salient-fragment-labirint numeric@attribute salient-fragment-împărăţi numeric@attribute salient-fragment-fotbalul numeric@attribute salient-fragment-portarul numeric@attribute salient-fragment-Regulili numeric@attribute salient-fragment-jucători numeric

@attribute 'Class-determina_grup' 'opera', 'sport'

@data

1, 0, 1, 2, 0, 0, 0, 0, 'opera'1, 1, 0, 0, 0, 1, 0, 0, 'opera'0, 0, 0, 0, 1, 3, 0, 4, 'sport'0, 0, 0, 0, 3, 3, 2, 1, 'sport'0, 0, 0, 0, 4, 3, 0, 0, 'sport'

Concluzii :

În urma efectuării acestui laborator am studiat şi analizat algoritmii de clusterizare Naive Bayes,

K-means Clusterizarea ierarhică. Am descris algoritmii în raport.Folosind algoritmul Naive Bayes am

dezvoltat o aplicație in weka care ne permite determinarea celui mai apropiat grup de documente pentru

un document ce conține date similare și care este specificat ca intrare. În urma clsificării dupa Algoritmul

Naive Bayes am opservat că argumentul clanuril apartine cateogorii opera cu un coeficient de 0.43 si

argumentul fotbalul cu un coeficient de 0.57.