Post on 01-Jul-2015
1. Tipuri de atribute
Procesul de Data Mining este influenţat de tipul atributelor obiectelor analizate.
De exemplu, atunci când se procedează la o vizualizare a datelor, reprezentarea grafică a
acestora depinde de natura observaţiilor: există procedee diferite atunci când se
analizează status-ul marital al unor persoane în comparaţie cu analizarea contului în
bancă sau al investigării măsurii în care aceştia fumează sau consumă alcool etc. Din
acest motiv este absolut necesar să detaliem problema naturii datelor cu care operează
Data Mining.
Datele pot fi împărţite, în principiu, în două tipuri importante: date numerice
(cantitative) şi date categoriale (calitative). Sunt folosite, mai rar, şi alte tipuri de date.
Vom prezenta, pe scurt, caracteristicile principale pentru fiecare tip de date.
Datele numerice, cantitative, sunt la rândul lor de două feluri: date discrete şi date
continue. Datele discrete apar atunci când este vorba de observaţii numerice întregi
privitoare la un anumit proces de numărare ca, de exemplu, numărul de copii ai unei
familii, pulsul, numărul de consultaţii pe an la care a fost supus un pacient, codul zip,
codul numeric, codul PIN, numărul anumitor cuvinte apărute în documente, atribute
binare etc. Spre deosebire de datele numerice discrete, obţinute de regulă în urma unui
proces de numărare, datele numerice continue se obţin în urma unor măsurători, de
exemplu înălţimea, greutatea, tensiunea arterială, colesterolul unei anumite persoane,
temperatura, presiunea atmosferică, viteza vântului, valoarea contului din bancă sau
valoarea acţiunilor tranzacţionate la bursă etc. Aceste date sunt, de regulă, exprimate prin
numere reale, spre deosebire de cele discrete care sunt restricţionate la numerele întregi.
Vom menţiona aici că, în multe analize, datele discrete sunt tratate ca date continue, de
exemplu numărul de bătăi pe minut ale inimii. Pentru ca analiza unor asemenea date
(discrete, dar considerate continue) să nu aibă de suferit, trebuie dispus de un număr
suficient de mare de valori diferite posibile ale acestora care să creeze premisele
ipoteticei naturi continue a lor. Menţionăm în acest context datele continue (cu virgulă
mobilă) care pot fi stocate: (a) float - numere cuprinse între 1.4E-45 şi 3.4E+38; (b)
double - numere cuprinse între 4.9E-324 şi 1.7E+308.
Date categoriale - spre deosebire de datele numerice, datele categoriale sau
calitative sunt acele date care, aşa cum le spune şi numele, împart instanţele în diferite
categorii, ca de exemplu:
1. bărbat/femeie
2. căsătorit/necăsătorit/văduv/divorţat
3. fumător/nefumător
4. hipertensiv/hipotensiv
5. stadii în anumite boli (e.g. cancer): I, II, III, IV
6. existenţă simptoame: DA, NU
7. tip diagnostic: A, B, C, D etc.
Datele numerice discrete sunt câteodată tratate ca date categoriale, de exemplu
numărul de copii născuţi de o femeie, e.g. 0, 1, 2, 3, 4, împart mamele în categoriile
corespunzătoare numărului de copii. Este important ca în această situaţie să se ignore
noţiunile de ordine sau de parametri numerici ca, de exemplu, media. Invers, nu este
corect să interpretăm datele categoriale ordonate ca date numerice, de exemplu, la stadiile
în anumite boli, stadiul IV nu este de două ori mai rău decât stadiul II, ş.a.m.d. Vom
menţiona că, în cadrul datelor categoriale, putem vorbi de date nominale ca, de exemplu:
grupa sanguină (A/B/AB/0), culoarea ochilor, sexul etc. şi de date ordinale ca, de
exemplu: gradul fumatului (e.g. nefumător, fost fumător, fumător “amator”, fumător
“înrăit”), ierarhizarea durerii (e.g. mică, medie, mare), ierarhizarea înălţimii (e.g. scund,
mediu, înalt), duritatea mineralelor etc, în principiu, atunci când avem de a face cu o
ierarhizare a “intensităţii” atributului respectiv.
Alte tipuri de date. În afară de cele două mari tipuri de date menţionate mai sus, în
Data Minig se mai operează câteodată şi cu alte tipuri de date. Enumerăm mai jos tipurile
cele mai cunoscute de astfel de date.
- Rangul reprezintă locul pe care îl ocupă un obiect într-o ierarhie (e.g. competiţie
sportivă, examinare, preferinţa medicului pentru un anumit tratament, preferinţa clienţilor
pentru un anumit produs etc).
- Procentajul, aşa cum arată şi numele, descrie o anumită proporţie (raport) intre
două cantităţi (e.g. procentajul de bărbaţi dintr-o populaţie, greutatea corporală relativă
(raportul dintre greutatea observată şi greutatea ideală), procentajul de stângaci dintr-o
populaţie, procentajul clienţilor fideli, procentajul obiectelor clasificate corect,
procentajul datelor lipsă etc).
- Rate şi rapoarte referitoare la frecvenţa observată a unui fenomen sau rapoartele
dintre două mărimi, altele decât procentajele (e.g. mortalitatea raportată la mia de
locuitori, rata de apariţie a unei boli pe sexe sau arii geografice, rata de schimb monetară,
raportul preţ/calitate etc).
- Scorul este folosit atunci când nu este posibilă o măsurătoare directă şi neambiguă şi
trebuie totuşi cuantificată o anumită mărime (e.g. scorul Apgar la nou-născuţi, gravitatea
unei boli cuantificată ca uşoară, moderată, severă, coloraţia pielii în anumite maladii,
etc).
- Scale vizuale analogice folosite mai ales în studiile medicale atunci când subiectul
este rugat să indice pe o scală punctul care este considerat a ilustra cel mai bine gradul de
durere, de exemplu. Cu toate că este o reprezentare foarte subiectivă, aproape imposibil
de cuantificat numeric, reprezintă totuşi un mijloc de a măsura un anumit fenomen.
În contextul utilizării metodelor statistice de Data Mining este util să discutăm, pe
scurt, atât despre variabilitatea datelor cât şi despre modelul probabilist al datelor, cu
referire mai ales la termenul de variabilă care este de multe ori echivalent cu cel de
atribut al unui obiect/instanţe.
Astfel, atunci când procesăm datele în cursul analizelor statistice incluse în
procesul DM, este absolut necesar să existe aşa numita variabilitate a lor. Prin
variabilitate înţelegem orice fel de modificare care are loc într-o mulţime de date.
indiferent de tipul lor, cu alte cuvinte variabilitatea este opusul constanţei datelor. Trebuie
ştiut faptul că nu se poate face analiză statistică pe variabile care sunt constante. O bună
parte a analizelor statistice clasice (e.g. regresia) face apel la legăturile care există între
diferite date referitoare la aceiaşi subiecţi, studiind modul cum variaţia unora influenţează
variaţia altora (e.g. legătura dintre înălţime şi greutate, între factorii de risc şi
probabilitatea declanşării unei maladii etc). Ori, dacă un factor din analiza statistică nu
are variabilitate atunci el este ca şi inexistent în analiză. Cu cât variabilitatea datelor este
mai mare cu atât analiza statistică este mai bogată în rezultate consistente.
2. Definiţii ale noţiunii de clustering
Clusteringul reprezintă procesul de organizare a obiectelor (datelor) în grupuri
de elemente asemănătoare într-un anumit sens, cu proprietăţi similare. Un cluster este o
colecţie de date/obiecte asemanătoare între ele şi diferite (disimilare) de altele, situate în
celelalte clustere. Clusteringul este o metodă de învăţare nesupervizată, folosită în
diverse domenii: Data Mining, Machine Learning, Bioinformatică, Analiza statistică a
datelor, Recunoaşterea formelor – Pattern recognition, etc.
În figura de mai jos este prezentat un set de date bidimensional; putem observa
trei grupuri de date.
Fiercare grup este un cluster. Sarcina clusterului este de a găsi cei trei clusteri
ascunsi in seturile de date .Cu toate că este uşor ca o persoană să observe clusterele într-
un spaţiu bidimensional sau tridimensional, devine foarte greu, dacă nu chiar imposibil,
să detectăm clusterele doar vizual, când dimensiunea creşte. Mai mult decât atât, în
multe aplicaţii, clusterele nu sunt atât de bine definite sau bine delimitate ca în figura de
mai sus. Prin urmare, trebuie utilizate tehnici matematice pentru gruparea în clustere.
Pentru a ilustra necesitatea procesului de clusterizare, vom enumera nişte aplicaţii
din diverse domenii.
Exemplul 1. O companie vrea să conducă o campanie de marketing pentru a
promova câteva produse. Cea mai buna strategie este aceea de a desemna un set de
materiale de marketing personalizate pentru fiecare client, în funcţie de profilul şi situaţia
sa financiară. Cu toate acestea, un asemenea procedeu este prea scump pentru a fi aplicat
unui număr de clienţi. Pe de altă parte compania proiectează un singur set de materiale de
marketing care să fie utilizate pentru toţi clienţii. Acestă abordare comună tuturor
clienţilor poate totuşi să nu fie eficace . Cea mai eficace metodă din punct de vedere al
costului constă în segmentarea clienţilor într-un număr mic de grupuri în funcţie de
asemanările dintre ei şi desemnarea unor materiale de marketing specifice fiecărui grup.
Sarcina de segmentare se realizează de obicei utilizând algoritmi clustering, care
grupează clienţii în funcţie de asemănările existente între ei. În cercetările de marketing,
procesul de clusterizare este adesea numit segmentare.
Exemplul 2. O companie vrea să producă şi să comercializeze tricouri. Ca şi în
exemplul prezentat mai sus, pe de o parte se poate crea un model de tricou în
conformitate cu dimensiunile fiecărei persoane. În mod evident, un astfel de tricou ar fi
foarte scump. Pe de altă parte, o singură mărime universală poate fi produsă. Din
moment ce această masură nu se potriveşte tuturor clienţilor, compania nu va putea vinde
un număr mare de tricouri. Din nou, cea mai eficace metodă din punctul de vedere al
costurilor, este gruparea persoanelor în funcţie de mărimea pe care o poartă fiecare şi
confecţionarea unei mărimi specifice pentru fiecare grup. De aceea putem întâlni
mărimile: mică, medie şi mare pentru tricouri în centrele comerciale şi rareori întâlnim
tricouri de mărime universală. Metoda prin care se grupează oamenii în funcţie de
mărimea pe care o poartă este denumită clustering. Procedeul decurge astfel:
producătorul de tricouri alege un număr mai mare de persoane, le masoară dimensiunile
pentru a forma o bază de date a măsurilor. Grupează apoi datele în clustere. Pentru
fiecare cluster, se calculează media mărimilor, iar media rezultată se foloseşte pentru a
produce tricouri de aceeaşi dimensiune pentru toate persoanele care au mărime apropiată.
Exemplul 3. În fiecare zi, agenţiile de ştiri din jurul lumii transmit un număr mare
de articole de ştiri. Dacă un site web doreşte să adune aceste articole de ştiri pentru a
asigura un serviciu integrat de ştiri, trebuie să organizeze articolele adunate în funcţie de
subiectul pe care îl tratează. Întrebarea este: ce subiecte trebuie să aiba şi cum trebuie
organizate? O posibilitate ar fi angajarea unui grup de editori care să îndeplinească
misiunea. Cu toate acestea, organizarea manuală este costisitoare şi necesită mult timp,
ceea ce face misiunea imposibilă şi nepotrivită pentru ştiri sau alte informaţii care sunt
dependente de timp. A prezenta ştirile cititorilor fără o organizare clară, nu constituie o
opţiune. Cu toate că o clasificare poate organiza articolele de ştiri în funcţie de anumite
subiecte predefinite, această metodă nu poate fi aplicată în acest caz, deoarece
clasificarea necesită date de antrenare, care trebuie să fie organizate manual prin
ierarhizarea subiectelor. Din moment ce subiectele de ştiri se schimbă în mod constant şi
rapid, seturile de date de antrenare vor trebui, de asemenea, să se modifice constant, ceea
ce nu este fezabil prin etichetarea manuala. Gruparea în clustere este soluţia ideală pentru
această problemă pentru că vor fi grupate în mod automat o serie de articole de ştiri
bazate pe asemanările de conţinut. Algoritmii de grupare ierarhică în clustere pot, de
asemenea, organiza şi grupa documente (de exemplu, fiecare subiect poate conţine sub-
subiecte şi aşa mai departe). Ierarhizările în funcţie de subiect sunt în special folositoare
pentru texte .
Cele trei exemple menţionate mai sus indică doua tipuri de grupare în clustere:
partiţională şi ierarhică. În continuare vom studia câţiva algoritmi specifici pentru
aceste două tipuri de clusterizare.
Exemplele de mai sus indică faptul că procesul de grupare în clustere necesită o
funcţie care măsoară gradul de asemănare dintre două obiecte. Adeseori se foloseşte
metrica euclidiană, sau mai general, metrica lui Minkowski
ppn
kjkikjip xxxxd
1
1),( ⎟
⎟⎠
⎞⎜⎜⎝
⎛−= ∑
=,
unde n este dimensiunea obiectului (lungimea vectorului, etc). Distanţa euclidiană se
obţine penttru p=2, iar distanţa Manhattan pentru p=1. Există o mulţime de alte
distanţe utilizate:
3. Clustering ierarhic
Odată aleasă o distanţă de similaritate, pe baza căreia putem compara obiectele,
mulţimea acestora poate fi partiţionată, utilizând o anumită metodologie.
Modelul de clustering ierarhic rezidă în gruparea obiectelor în mod iterativ,
generând o ierarhizare a clusterelor, ce poate fi reprezentată printr-o structură
arborescentă, numită dendogramă. Se utilizează o anumită metodă de
„comasare/articulare" (linkage) ca, de exemplu:
• single linkage - distanţa dintre clustere este determinată de distanţa între cele
mai apropiate obiecte (nearest neighbor);
• complete linkage - distanţa dintre clustere este determinată de distanţa între cele
mai îndepărtate obiecte (furthest neighbor);
• average linkage (unweighted pair-group average) - distanţa dintre clustere
reprezintă media distanţelor (neponderată) între orice două perechi de obiecte din clustere
diferite. Să notăm şi varianta weighted pair-group average care, spre deosebire de cea
neponderată, ia în consideraţie mărimea clusterelor (numărul obiectelor din fiecare
cluster) ca ponderi în calcularea distanţelor;
• centroid method (unweighted pair-group centroid) - distanţa între clustere este
determinată de distanţa între centroizii lor (centrele de greutate
• Ward's method - această metodă, diferită de cele de mai sus, utilizează analiza
varianţelor (dispersiilor) în evaluarea distanţelor între clustere;
Există două metode principale de clustering ierarhic, diferenţa dintre ele constând în
direcţia de construcţie a arborelui: de jos în sus - clusteringul aglomerativ - şi de sus în
jos - clusteringul diviziv. Clustering ierarhic divizibil se aplică mai rar în practică.
Ilustrăm în figurile următoare, schematic, metoda clusteringului ierarhic:
Datele iniţiale
Schematic, dendograma generată de clusterizarea ierarhică este reprezentată mai jos:
Algoritmnul de clusterizare ierarhică (S.C. Johnson, 1967) are următorii paşi.
Se da o mulţime de N elemente ce urmează a fi clusterizate (grupate), şi o
matrice distanţă (sau matrice de similaritate) de dimensiune N*N .:
1. Se atribuie fiecărui element un cluster, aşadar dacă avem N elemente, vom avea la
acest nivel N clustere, fiecare conţinând câte un unic element. Vom presupune că
distanţele dintre clustere sunt aceleşi ca şi distanţele dintre elementele pe care
acestea le conţin.
2. Se determină cea mai apropiată (cea mai similară) pereche de clustere şi le vom
combina (uni) într-un singur cluster, având aşadar cu un cluster mai puţin.
3. Se calculează distanţa (similaritatea) dintre noul cluster şi fiecare dintre vechile
clustere.
4. Se repetă paşii 2 şi 3 până când toate elementele sunt grupate într-un singur
cluster de dimensiune N.
Pasul 3 se poate realiza în diverse moduri: single-linkage, complete-linkage şi
average-linkage. Asă cum am mai spus, în metoda single-linkage (denumită şi metoda
de minim), se consideră distanţă dintre două clustere ca fiind egală cu cea mai scurtă
distanţă dintre orice element al unui cluster şi orice element al celuilalt cluster. Dacă
datele constau din similarităţi, se consideră că similaritea dintre un cluster şi altul este
egală cu cea mai mare similariate dintre orice membru al unui cluster şi orice element al
celuilalt cluster.
În metoda complete-linkage (denumită şi metoda de maxim sau metoda diametru), se
consideră distanţă dintre două clustere ca fiind egală cu cea mai mare distanţă dintre
orice element al unui cluster şi orice element al celuilalt cluster.
În metoda average-linkage, se consideră distanţă dintre două clustere ca fiind egală
cu valoarea medie a distanţei dintre orice element al unui cluster şi orice element al
celuilalt cluster.
Algoritmul de clusterizare Single-Linkage.
Algoritmul este de tip aglomerativ, ştergând linii şi coloane din matricea iniţială
şi unind vechile clustere în unele noi.
Se noteaza matricea de proximitate (de similaritate), de dimensiune N*N, prin
D = [d(i,j)]. Procesului de clusterizare i se atribuite un şir de numere 0,1,......, n-1 şi se
notează prin L(k) nivelul de clusterizare de ordin k. Un cluster cu numărul de ordine m se
notează prin (m), proximitatea (distanţa/similaritatea) dintre clusterele (r) şi (s)
notându-se prin d[(r),(s)]. Algoritmul are următorii paşi:
1. Se începe cu clusterul vid, având nivelul L(0) = 0 şi numărul de ordine m = 0.
2. Se determină cele mai similare perechi de clustere la nivelul curent de clusterizare, de exemplu perechea (r), (s); se notează d[(r),(s)] = min d[(i),(j)]
3. Se incrementează m = m +1. Se unesc clusterele (r) şi (s) într-un singur cluster clustering m. Nivelul de clusterizare va fi L(m) = d[(r),(s)]
4. Se modifică matricea de proximitate D, ştergând liniile şi coloanele corespunzătoare clusterelor (r) şi (s) şi se adaugă o nouă linie şi o nouă coloană corespunzătoare noului cluster format. Proximitatea (distanţa) dintre noul cluster, notat (r,s) şi vechiul cluster (k) se defineştew prin relaţia: d[(k), (r,s)] = min d[(k),(r)], d[(k),(s)]
5. Dacă toate obiectele sunt în acelaşi cluster, STOP. Altfel, se merge la pasul 2.
Vom considera urmatorul exemplu: un clustering ierarhic al distanţelor în
kilometri între câteva oraşe din Italia . Metoda folosită este single-linkage. Vom folosi
următoarele prescurtări: BA= Bari, FI=Firenze (Florenţa), NA=Napoli, RM=Roma,
TO=Torino.
Considerăm matricea distanţă de intrare (L = 0 pentru toate clusterele):
Oraşele cele mai apropiate sunt Milano şi Torino, la distanţă 138. Acestea vor fi
grupate într-un singur cluster denumit "MI/TO". Nivelul noului cluster va fi L(MI/TO)=
138 şi numărul de ordine este m = 1. Apoi se calculează distanţa dintre acest nou obiect
şi toate celelate. În metoda single-linkage regula este că distanţa dintre noul obiect
(compus) şi un alt obiect este egală cu cea mai scurtă distanţă dintre orice element al
clusterului şi obiectul din exterior. Deci distanţa dintre "MI/TO" şi RM se alege 564,
care reprezintă distanţă dintre MI şi RM, şi aşa mai departe.
După construirea clusterului “MI/TO” se obţine matricea:
BA FI MI NA RO TO
BA 0 662 877 255 412 996
FI 662 0 295 468 268 400
MI 877 295 0 754 564 138
NA 255 468 754 0 219 869
RM 412 268 564 219 0 669
TO 996 400 138 869 669 0
BA FI MI/TO NA RM
BA 0 662 877 255 412
FI 662 0 295 468 268
MI/TO 877 295 0 754 564
NA 255 468 754 0 219
RM 412 268 564 219 0
Deoarece min d(i,j) = d(NA,RM) = 219, vom grupa NA şi RM într-un nou
cluster numit NA/RM, cu nivelul L(NA/RM) = 219 şi numărul de ordine m = 2.
Cum min d(i,j) = d(BA,NA/RM) = 255 , vom grupa BA şi NA/RM într-un nou
cluster, cu numele BA/NA/RM, având L(BA/NA/RM) = 255 şi m = 3.
La nivelul următor se observă că min d(i,j) = d(BA/NA/RM,FI) = 268, şi deci
vom grupa BA/NA/RM şi într-un nou cluster numit BA/FI/NA/RM, cu
L(BA/FI/NA/RM) = 268 şi m = 4.
BA FI MI/TO NA/RM
BA 0 662 877 255
FI 0 295 268
MI/TO 877 295 0 564
NA/RM 255 268 564 0
BA/NA/RM FI MI/TO
BA/NA/RM 0 268 564
FI 268 0 295
MI/TO 564 295 0
In final vom grupa cele 2 clustere la nivelul 295.
Procesul de clusterizare ierarchică va fi reprezentat prin următoarea dendogramă
verticală:
Implementarea în Matlab a clusterizării ierarhice pentru exemplul de mai sus este
reprezentată în cele ce urmează:
A =
662 877 255 412 996 295 468 268 400 754 564 138 219 869 669
>> B=squareform(A)
B =
0 662 877 255 412 996
662 0 295 468 268 400
BA/FI/NA/RM MI/TO
BA/FI/NA/RM 0 295
MI/TO 295 0
877 295 0 754 564 138
255 468 754 0 219 869
412 268 564 219 0 669
996 400 138 869 669 0
>> C=linkage(A,'single')
C =
3 6 138
4 5 219
1 8 255
2 9 268
7 10 295
>> [H,T] = dendrogram(C,'colorthreshold');
3 6 1 4 5 2
140
160
180
200
220
240
260
280
300
4. Clustering partiţional (algoritmul k-Means)
Clusteringul partiţional(neierahic) este cunoscut şi sub denumirea de clustering
de tip k-Means. Acest model este total diferit de cel ierarhic, metoda presupunând
cunoaşterea a priori a numărului de clustere. Problema care se pune este aceea de a crea
un algoritm pe baza căruia să se poată forma exact atâtea clustere cât s-a decis iniţial, cât
mai distincte cu putinţă. Acesta a fost iniţiat in 1967, de către J. MacQueen şi reluat apoi
de J. A. Hartigan şi M. A. Wong în 1975. Algoritmul k-Means începe cu alegerea aleatoare a k clustere (k este un număr
întreg), după care aranjează obiectele în cele k clustere, având două obiective de
îndeplinit: minimizarea variabilităţii intra-cluster şi maximizarea variabilităţii inter-
clustere. Modul de grupare este dat de minimizarea sumei pătratelor distanţelor dintre
fiecare dată şi centroidul clusterului corespunzător. Fiecare cluster are un centru,
denumit centroid. Centroidul, utilizat pentru a reprezenta clusterul, se calculează ca fiind
media tuturor punctelor de date din cluster, (de unde şi numele algoritmului).
In cele ce urmeză sunt prezentaţi pasii algoritmului k-Means
1. Selectează aleator k puncte ca şi centre de clustere.
2. Se determină distanţa dintre fiecare obiect şi centroizi.
3. Atribuie instanţele/obiectele acelor clustere care au cel mai apropiat centru faţă de
acestea, în raport cu o anumită măsură de similaritate.
4. Dupa ce toate obiectele au fost atribuite, recalculează poziţia fiecăruia din cei k -
centroizi (media tuturor instanţelor din fiecare cluster).
5. Se repetă paşii 2 şi 3, până când un anumit criteriul de oprire este satisfăcut.
Criteriul de oprire (de convergenţă) poate fi unul din urmatoarele:
- nicio reatribuire (minimum de reatribuiri) ale punctelor de date pentru diferite clustere
- nicio schimbare (sau minimum de schimbari) de centroizi
Remarca 1: Cu toate că, în principiu, metoda k-means clustering produce exact k clustere
care divizează mulţimea iniţială de obiecte cât mai distinct posibil, rămâne deschisă
problema estimării numărului optim de clustere care să conducă la separarea cea mai
bună a obiectelor.
Remarca 2: O problemă majoră în utilizarea metodei k-Means este rezidă din necesitatea
definirii mediei, ceea ce implică faptul că este neaplicabilă la date nenumerice (e.g.
categoriale).
Remarca 3: Menţionăm, în context, încă trei modele de clustering, mai elaborate
• EM (Expectation Maximizatioon) clustering;
• QT (Quality Threshold) clustering;
• Fuzzy c-means clustering.
În încheiere vom enumera “plusurile” şi “minusurile” celor două mari tipuri de
clustering descrise mai sus.
Cluster ierarhic
• (+) Intuitiv, uşor de înţeles;
• (-) Persistenţa nedorită a clusterelor de la început;
• (-) Sensibil la valori extreme (outliers) şi la atribute irelevante;
• (-) Neaplicabil la mulţimi mari de date.
Cluster partiţional
• (+) Mai puţin sensibil la valori extreme (outliers) şi la atribute irelevante;
• (+) Aplicabil la mulţimi mari şi foarte mari de date;
• (-) Are nevoie de alegerea prealabilă a numărului de clustere, ceea ce se dovedeşte a
fi uneori greu de stabilit.
Judecând aspectele prezentate mai sus, ajungem la concluzia că optim ar fi utili-
zarea, dacă este posibil, a ambelor variante de clustering. De exemplu, putem utiliza
clusteringul ierarhic pentru stabilirea unui număr convenabil de clustere, după care
utilizarea celui neierarhic va îmbunătăţii rezultatele prin reconfigurarea clusterelor
irelevante.
Exemplu. Vom considera 4 obiecte (4 tipuri de medicamente diferite), fiecare din ele
având 2 caracteristice (atribute), aşa cum rezultă din tabelul de mai jos. Scopul nostru
este de a grupa aceste objects în k=2 clustere (grupuri de medicamente) bazate pe cele 2
caracteristici (pH şi indexul de greutate - weight index).
Obiectele Atribut 1 (X): weight index Atribut 2 (Y): pH Medicament A 1 1 Medicament B 2 1 Medicament C 4 3 Medicament D 5 4
Fiecare medicament este reprezentat printr-un punct, cu cele 2 atribute (X, Y), evidenţiate mai jos:
1. Alegerea iniţială a centroizilor : Presupunem că medicamentele A şi B vor fi primii
centroizi. Vom nota cu 1c şi 2c coordonatele centroizilor, deci )1,1(1c şi )1,2(2c
2. Vom calcula distanţa dintre fiecare centroidul si fiecare obiect. Vom folosi distanţa
euclidiană, si vom obţine matricea distanţă la iteraţia 0
Fiecare coloană în matricea distanţă 0D simbolizează obiectul (A, B, C, D).Prima linie în
matricea 0D corespunde distanţei dintre fiecare obiect şi primul centroid, în timp ce a
doua linie reprezintă distanţa dintre fiecare obiect şi al doilea centroid. De exemplu, dis-
tanţa dintre medicam. C = (4, 3) şi centroidul )1,1(1c este 61.3)13()14( 22 =−+− , iar
distanţa dintre C = (4, 3) şi centroidul )1,2(2c este 83.2)13()24( 22 =−+− .
3. Vom atribui fiecare obiect clusterului corespunzător, dupa regula distanţei minime.
Medicamentul A este asignat clusterului 1, medicamentul B clusterului 2, C lui 2 iar
medicamentul D tot lui 2. Elementul matricii grup G, de mai jos este 1 dacă şi numai
dacă obiectul este asignat acelui cluster.
4. Determinarea centroizilor : Cunoscand membrii fiecărui cluster, putem determina noii
centroizi ai fiecarui grup. Clusterul 1 are un singur membru, deci centroiul rămâne în
)1,1(1c . Clusterul 2 are acum 3 membri, deci centroidul este media coordonatelor celor 3:
.
5. Iteraţia 1: La acest pas determinăm distanţa dintre toate obiectele şi noii centroizi.
Similar pasului 2, construim matricea distanţa corespunzătoare iteraţiei 1:
6. Ca şi la pasul 3, vom atribui fiecare obiect clusterului corespunzător, dupa regula
distanţei minime. Din matricea distanţă, rezultă că trebuie să mutăm medicamentul B în
clusterul 1, restul rămânând nemodificate. Matricea grup de nivel 1 este:
7. Iteraţia 3 - determinăm noii centroizi, repetând pasul 4. Ambele clustere au câte 2
membri, deci noii centroizi sunt
8. Repetăm pasul 2, obţinând noua matrice distanţa la iteraţia 2:
9. Din nou atribuim fiecare obiect clusterului corespunzător, dupa regula distanţei minime.
Se observă că GG =2 , aşadar obiectele nu-şi mai modifică poziţiile. Deci
algoritmul de clusterizare k-means a condus către un rezultat de stabilitate şi procesul
iterativ se opreşte.
Obţinem, aşadar, următoarea grupare (clusterizare):
Obiect Atribut 1 (X): weight index Atribut 2 (Y): pH
Clusterizarea Rezultat
Medicament A 1 1 1 Medicament B 2 1 1 Medicament C 4 3 2 Medicament D 5 4 2
Implementarea în Matlab este relativ simplă:
m = [ 1 1; 2 1; 4 3; 5 4]
m =
1 1
2 1
4 3
5 4
k=2;
[IDX,C] = kmeans(m,k)
IDX =
1
1
2
2
C =
1.5000 1.0000
4.5000 3.5000
Matricea C conţine coordonatele celor 2 centroizi, iar vectorul coloană IDX
conţine informaţii privitoare la apartenenţa obiectelor la clusterele corespunzătoare:
primele 2 (A şi B) aparţin primului cluiter, ultimele 2 (B şi C), celui de-al doilea cluster.