Cercetare4 Mihai Mocanu [623139]

Universitatea POLITEHNICA Bucure ști
Facultatea Automatică și Calculatoare
Departamentul Automatică și Informatică Industrială

LUCRARE DE DIZERTAȚIE
Procesari Hadoop folosind multiple tipuri de
informa ție

Coordonator Absolvent: [anonimizat]

2017

Cuprins
Motivare ………………………….. ………………………….. ………………………….. ………………………….. …………………… 3
Obiective ………………………….. ………………………….. ………………………….. ………………………….. ………………….. 4
Analiza sentimentala si subiectivitatea ………………………….. ………………………….. ………………………….. ……… 5
Algoritmi de clusterizare ………………………….. ………………………….. ………………………….. …………………………. 7
Măsuri ale distanței ………………………….. ………………………….. ………………………….. ………………………….. …… 9
Abordări pentru grupare (clustering) ………………………….. ………………………….. ………………………….. ………. 10
Algoritmi prezentați ………………………….. ………………………….. ………………………….. ………………………….. 10
Algoritmul k -means ………………………….. ………………………….. ………………………….. ………………………….. . 11
Concluzii ………………………….. ………………………….. ………………………….. ………………………….. …………………. 13
Bibliografie ………………………….. ………………………….. ………………………….. ………………………….. …………….. 14

Motivare

Avand la baza un sistem de analiza a facturilor si crearea de statistici pe baza rapoartelor
si datorita cresterii cu o viteza foarte mare a datelor efectuate de catre utilizator imi doresc a crea
un sistem de recomandare pe baza review -urilor date de catr e utilizator pentru a putea sugera
produce ce pot fi cumparate in viitor de catre utilizator, sau pentru a -I oferi o mai buna perspectiva
asupra varietatii produselor din cadrul unui magazin online. Evoluția continuă a dimensiunii și
utilizării Web -ului a avut drept consecință directă apariția diferitelor provocări, precum stocarea
informației sau dificultatea extragerii cunoștințelor utile. Problemele care au trebui să fie
soluționate sunt regăsirea informației relevante, care implică căutarea și indexarea conținutului
web, crearea unor meta cunoștințe din informațiile disponibile pe Web, precum și tratarea
intereselor și nevoilor utilizatorilor prin personalizarea informațiilor și serviciilor oferite.
Termenul de Web mining a fost introdus odată cu exploz ia Web -ului de la mijlocul anilor
1990, pentru a confirma aplicarea tehnicilor de data mining pentru extragerea de cunoștințe din
conținutul (Web content mining), structura (Web structure mining) și utilizarea (Web usage
mining) datelor web prin intermediu l regăsirii automate a paginilor și serviciilor web, extragerea
de informații din resursele web și descoperirii de modele în cadrul Web -ului. Așadar, Web mining
este un domeniu convergent de cercetare, care cuprinde diferite aspecte ale unor arii de cercet are
deja consacrate cum ar fi bazele de date, regăsirea informației (Text REtrieval Conference, TREC),
inteligența artificială, învățărea automată, text mining, etc. Principiile lor sunt abordate și adaptate
în Web mining pentru a face față noilor provocăr i. Cel mai evident domeniu care a trebuit să se
adaptateze noilor condiții a fost regăsirea informației, luând astfel naștere regăsirea informației pe
Web (Web information retrieval). Cercetările din acest domeniu au dus la crearea unui nou
instrument web, anume motorul de căutare, care a transformat activitatea de regăsire a informației
într-o activitate zilnică pentru orice persoană care utilizează un calculator.
Creșterea volumului de informație a generat noi provocări în prelucrarea eficientă a
informa ției noi descoperite sau reactualizarea datelor deja cunoscute. A discuta despre Web este o
sarcină dificilă din mai multe motive. În primul rând, datorită conținutului dinamic, se poate spune
că subiectul și conținutul unei pagini web nu vor mai fi de act ualitate până când ajung la utilizatorul
final, deoarece adresa URL care face referire la informația în sine poate fi rescrisă sau chiar
redirectată între timp. Apoi, o abordare realistă și acoperirea tuturor subiectelor de interes pentru
utilizatorii fina li este imposibilă deoarece noi idei și subiecte sunt propuse în mod continuu, fiind
acceptate sau respinse de comunitatea virtuală. Un alt motiv este acela că există tendința puternică
de a prezenta subiecte strans legate de trecutul autorului lor, astfel acordând -se importanață
subiectelor și legaturilor de care acestea sunt conectate.
Ceea ce diferențiază Web -ul de alte colecții de documente este faptul că, în afară de documentele
pe care le conține, este puternic caracterizat de hiper -legăturile care in ter-conectează aceste
documente. Informațiile furnizate către utilizatori sunt de tip text, imagini, date audio sau video
precum și date structurate (tabele și liste). Majoritatea documentelor web sunt în format HTML

(HyperText Markup Language) conținâd ta g-uri sau etichete folosite la formatare, astfel aplicațiile
de Web mining trebuie să parseze documentele HTML eliminând părțile care nu prezintă interes
din punct de vedere informațional. O problemă comună a sistemelor de regăsire o reprezintă 2
modelarea documentelor. De regulă, un document necesită prelucrări preliminare pentru a extrage
din el informații relevante într -un format eficient și util, astfel încât documentul să fie procesat în
mod automat de către sistemul de regăsire. O problemă deschisă în acest domeniu o reprezintă
descoperirea caracteristicilor esențiale și definitorii care dau importanța și greutatea informației
furnizate de o pagină web. De asemenea, datorită caracterului dinamic a conținutului web, se
impune o structurare și o analiză prealabilă a documentelor web, astfel încât datele prezentate
utilizatorului fie să ofere un răspuns rapid și concludent la o anumită interogare, fie să ofere o
varietate de răspunsuri relevante pentru o interogare ambiguă. Importanța evaluării sistemelor de
regăsire a fost recunoscută încă de la începutul cercetării acestui domeniu și are un rol cheie în
îndeplinirea scopului final. Cel mai important instrument al evaluării îl reprezintă colecția de test:
o colecție de documente cu un set de subiecte și ju decăți care indică ce document este relevant
relativ la un subiect. Evaluarea prin această metodă și -a dovedit utilitatea în urmă cu zece ani,
odată cu explozia volumului informațional, când eficiența și fiabilitatea rezultatelor a început să
fie investiga tă în mod oficial. Deși au mai fost create colecții de test pentru Web, datorită lipsei
puterii de calcul, o colecție reprezentativă și reală pentru Web nu a fost creată decât în 2009, anume
colecția ClueWeb09. Astfel, a apărut posibilitatea investigării t ehnicilor curente de Web mining și
a unora noi având ca suport o colecție de test care reprezintă o bună parte din contextul actual al
Web -ului. Existând atâtea provocări ale Web -ului și cerințe diverse din partea consumatorilor de
informație, această lucr are se concentrează pe metodele care duc la o creștere a eficienței de
modelare, organizare și regăsire a informației utile în contextul Web, pentru a satisface, în final,
nevoia tot mai crescută și diversificată, de informație a utilizatorilor.
Obiective

Obiectivul general al acestei cercetări este acela de a imbunatati sistemul de recomandare
a produselor incercand astfel folosirea datelor primite ca si feedback de la utilizator si nu doar
descrierea produsului dar si luarea in condiserare a factorului uman cum ar fi “ironia” sau
“entuziasmul” din momentul adaugarii evaluarii dar si in a contribui la îmbunătățirea tehnicilor
actuale de Web mining prin modelarea și structurarea conținutului web, precum și analiza,
modelarea și optimizarea sistemelor de r egăsire a informației. Datorită diverselor abordări atunci
când vine vorba de modelarea documentelor web, precum și din cauza multitudinii de scopuri
pentru care se inițiază un proces de regăsire, această lucrare a abordat următoarele direcții de
cercetare :

 principalelor tehnici de învățare utilizate: învățarea supervizată (clasificarea) și învățarea
nesupervizată (clusterizarea);
 tehnicilor fundamentale de modelare a termenilor, documentelor și interogărilor web, precum și
a modalității de calcul al relevanței acestora: modele non -lingvistice și modele lingvistice;
 metodelor și metricilor de evaluare;

Analiza sentimentala si subiectivitatea

Informațiile textuale din lume pot fi în mare parte clasificate în două tipu ri principale: fapte
și opinii. Faptele sunt expresii obiective despre entități, evenimente și proprietățile lor. Opiniile
sunt de obicei expresii subiective care descriu sentimentele, aprecierile sau sentimentele oamenilor
față de entități, evenimente și proprietăți le lor . Conceptul de opinie este foarte larg. În cele ce
urmeaza , ne concentr ăm doar pe expresiile de opinie c are transmit sntimentele pozitive sau
negative ale oamenilor. O mare parte din cercetările existente asupra textului si procesarea
informațiilor a fost axată pe extragerea și regăsirea informațiilor factuale, de exemplu informații .
Regăsirea, căutarea pe Web, cl asificarea textului, gruparea de texte și multe alte analize de text și
limbajul natural . S-au făcut prea puține lucruri cu privire la procesarea opini ilor decât până de
curând. O piniile sunt atât de importante încât ori de c âte ori avem nevoie să luăm o decizie, dorim
să auzim opiniile altora. Acest lucru nu este valabil numai pentru indivizi, ci și pentru organizații.
Unul dintre principalele motive ale lipsei studiului asupra o piniei este faptul că nu exista
un text avizat disponibil înainte de World Wide Web. Înainte de Web, când o persoană trebuia să
ia o decizie, cerea în mod tipic opinii de la prieteni și familii. Când o organizație dorea să găsească
opinii sau sentimente ale utilizatiorilor despre produs ele și serviciile sale, realiza sondaje de opinie .
Cu toate acestea, cu Web -ul, în special cu creșterea explozivă a datelor generate de catre utilizatori,
lumea a fost transformată.
Web -ul a schimbat în mod dramatic modul în care oamenii își exprimă op iniile. Acum
utilizatorii pot crea recenzii de produse la site -urile comercianților și să -și exprime opiniile pe
aproape ori ce în forumurile de pe Internet. Grupuri de discuții și bloguri, denumite colectiv
conținutul generat de utilizato ri. Acestea reprezintă surse noi și măsurabile de informații cu multe
aplicații practice . Acum, dacă cineva dorește să cumpere un produs, el nu se mai limite ază la a -și
întreba prietenii deoarece există multe recenzii despre produse pe Web care oferă opinii ale
utilizatorilor existenți ai produs ului. Pentru o companie, nu mai este necesa r să se efectueze
sondaje, să angajeze consultanți externi pentru a găsi opinii ale consumato rilor cu privire la
produsele sale , deoarece conținutul generat de utilizatori de pe Web le poate oferi deja astfel de
informații.
Cu toate acestea, găsirea surselor de opinie și monitorizarea acestora pe Web poate fi încă
o sarcină destul de grea deoarece e xistă un număr mare de surse diverse și fiecare sursă poate avea,
de asemenea, un volum imens de opinii . În multe cazuri, opiniile sunt ascunse în posturile și
blogurile pe forumuri lungi. Este dificil pentru cititorul uman să găsească surse relevante, să extragă
propoziții înrudite cu opinii, să citească să le faca un r ezumat și să le organizeze în form e utile.
Astfel, pentru descoperirea automată a opiniei su nt necesare sisteme de sumare. Ana liza
sentimentului e ste o problemă dificilă de prelucrare a limbajului natural sau de analiza a textului.
Datorită valorii sale extraordinare pentru aplicații practice, a existat o creștere explozivă a ambelor
cercetări în mediul academic și universitar . Există acum cel puțin 20 -30 de companii care oferă
servicii d e analiză a sentimentului
Numai în SUA acest domeniu de cercetare se concentrează pe următoarele subiecte:

1. Problema analizei sentimentului

Ca orice problemă științifică, înainte de a o rezolva, trebuie să o definim pentru a fo rma
problema. Formularea va introduce definițiile de bază, conceptele de bază și
probleme le, sub -probleme le și obiective le-țintă. De asemenea, servește ca un cadru
comun pentru unificarea diferitelor direcțiile de cercetare. Din punct de vedere al
aplicației , acesta spune practicanților care sunt sarcinile principale, intrările și ieșirile
acestora și modul în care rezultatele pot fi utilizate în practică.

2. Evaluarea sentimentului și a subiectivității

Aceasta este zona care a fost studiată cel mai mult inmediul academic. Tratează analiza
sentimentului ca o problemă de clasificare a textului.
Primul subiect, cunoscut sub numele de clasificarea sentimentului sau clasificarea
sentimentului la nivel de document, iși propune să găsească sentimentul general al
autorului într -un te xt avizat. De exemplu, pentru un produs , determină dacă recenzorul
este pozitiv sau negativ cu privire la produs. Al doilea subiect merge la propoziții
individuale pentru a determina dacă o propozitie exprimă o opinie sau nu (deseori
numită subiect ivitate ) și, dacă da, dacă opinia este pozitivă sau negativă (numită nivel
de propoziție sentiment).

3. Analiza se ntimentului bazată pe elemente

Acest model descoperă mai întâi obiectivele pe care au opiniile au fost exprimat e într-
o propoziție și apoi determ ină dacă opiniile sunt pozitive, negative sau negative neutru.
Obiectivele sunt obiecte și componentele, atributele și caracteristicile acestora. Un
obiect poate fi un produs, serviciu, individ, organizație, eveniment, subiect, etc. De
exemplu, într -o propo ziție de revizuire a produsului, se identifică caracteristicile
produsului care au fost comentate de către recenzor și se determină dacă comentariile
sunt pozitive s au negative. De exemplu , "Durata de viață a bateriei este prea scurtă ",
comentariu l se referă la" durata de viață a bateriei " a camerei și opinia este negativă.
Multe exemple ale vieți reale solicită acest nivel de analiză detaliată, deoarece pentru
a face îmbunătățiri ale produselor trebuie să știm ce componente și / sau caract eristici
ale produsului sunt plăcute sau nu de catre consumatori. Aceste informații nu sunt
descoperite prin clasificarea sentimentului și subiectivității.

4. Analiza sentimen tului propozițiilor comparative

Evaluarea unui obiect se poate face în două moduri principale, evaluarea directă și
compararea. Aprecierea directă, numită opinie directă, dă rezultate pozi tive sau
negative si o o pinie despre obiect fără a menționa alte obiecte similare. Compararea
înseamnă a compara obiectul cu alte obiecte similare (de exemplu, produse
concurente). De exemplu, " Calitatea imaginii acestei camere este slabă ", exprimă o
opinie di rectă, în timp ce" Calitatea imaginii acestei camere este mai bună decât cea a
aparatului Camera -x ", exprimă o comparație. În mod evident, este util să identificăm

astfel de fraze, extrage opiniile comparative exprimate în ele și determină ce obiecte
sunt preferate.

Algoritmi de clusterizare

Implementarea eficientă a unui algoritm de clusterizare constă în găsirea unor relații
intrinseci, precum asemănările și deosebirile dintre documentele web (Hou & Zhang, 2003).
Având modelul de document web propusși ținând cont că paginile web sunt grupate sub forma
unui site, putem proiecta un algoritm de clusterizare specific. Algoritmul de clusterizare propus
constă în do uă faze. Prima fază este dată de clusterizarea unui site, în care toți termenii din colecție,
respectiv matricea , sunt clusterizați pe același nivel fără, nici o ierarhie între documentele aceluiași
cluster. În acest punct un site este reprezentat sub for ma unei colecții de clustere, fiecare cluster
fiind compus dintr -un grup de termeni, care la rândul lor provin dintr -o mulțime de pagini 25 web.
Faza a doua a algoritmului constă într -o sortare topologică a tuturor documentelor web din fiecare
cluster, anu me luând în calcul lista de legături (in -site-links) din interiorul site -ului pentru fiecare
document. În figura de mai jos sunt ilustrați grafic pașii algoritmului.

Inițial, se aplică procesul de clusterizare asupra unui site prin intermediul matricei d e
termeni . Prin urmare, se poate observa că fiecare cluster poate fi reprezentat sub forma unui grup
de documente care conțin toți termenii din clusterul respectiv. Această abordare are un mare
avantaj și anume poate produce clustere care se suprapun, un singur document putând să aparțină
mai multor clustere. Prima fază a algoritmului de clusterizare are la bază algoritmul K -Means în
care site -ul este reprezentat sub forma unei colecții de clustere de bază (CL), fiecare cluster de
bază fiind compus dintr -un grup de termeni care aparțin unor pagini din site. Faza a doua a
algoritmului constă în sortarea topologică a tuturor documentelor dintr -un cluster. În mod obișnuit
documentele web sunt ordonate conform unei funcții de similaritate, dar rolul fiecărui do cument
în cadrul clusterului poate fi pus în evidență și de legăturile pe care le are un document cu
documentele din același cluster, cu documentele din celelalte clustere sau cu documentele din afara
colecției. Luând în considerare lista in -site-links de legături a fiecărui document dintr -un cluster și
faptul că un document este mai important cu cât are mai multe legături cu documentele din același
cluster sau cu documentele din site, fiecare cluster de bază poate fi reprezentat ca o ierarhie de

documente. Procesul de ordonare a documentelor dintr -un cluster este descris în etapa a doua a
algoritmului de clusterizare.
Provocare majoră a celei de a doua faze este dată de eliminarea unui număr de muchii din
digraful care contrazic proprietatea de a fi acicli c. În mod intuitiv, pentru a nu pierde o cantitate
mare din informația potențial folositoare, numărul de muchii care trebuie eliminat trebuie să fie
minim. Pentru fiecare nod al gradului orientat se disting două tipuri de arce:  arce in -cluster,
arcele unui nod, cu excepția nodului out, care nu referă sau nu este referit de nodul out,  muchii
out-cluster, arcele care fac legătura dintre nodul outși celelalte noduri ale digrafului. Odată ce
ciclul este rupt, putem sorta nodurile după criteriul “nodul cu cel mai mic număr de muchii in –
cluster primul”, adică o pagină care are cel mai mic număr de legături spre documentele din 26
același cluster este prima în listă. Când avem două noduri cu același număr de arce in -cluster,
definim u n alt criteriu și anume “nodul cu cel mai mic număr de muchii out -cluster primul”. În
acest mod obținem o listă ordonată descrescător de documente web care poate fi accesată usor de
către utilizator.
Deoarece normalizarea documentului este facută odată cu ponderea termenilor, prin
factorul de normalizare cosinus sau pivot, putem observa faptul că algoritmul de clusterizare este
independent de ordinea documentelor obținută în urma sortării topologice. Nu este dificil de a
demonstra că algoritmul are complex itatea O(l*p*logp) + O(m +n), unde l este numărul de
clustere, p este numărul de documente supuse clusterizării, n este numărul de noduri și m este
numărul de muchii pentru toate digrafurile
Dându -se puncte într -un spațiu oarecare – deseori un spațiu cu foarte multe dimensiuni –
grupează punctele într -un numar mic de clustere, fiecare cluster constând din puncte care sunt
"apropiate" într -un anume sens. Câteva aplicații:
1. Cu mulți ani în urmă, în timpul unei izbucniri a holerei în Londra, un medic a marca t
localizarea cazurilor pe o hartă, obținând un desen care arăta ca în Fig. 14. Vizualizate
corespunzător, datele au indicat că aparițiile cazurilor se grupează în jurul unor
intersecții, unde existau puțuri infestate, arătând nu numai cauza holerei ci ind icând și
ce e de făcut pentru rezolvarea problemei. Din păcate nu toate problemele de data
mining sunt atât de simple, deseori deoarece clusterele sunt în atât de multe dimensiuni
încât vizualizarea este foarte dificilă.

2. Skycat a grupat în clustere 2 x 109 obiecte cerești în stele, galaxii, quasari, etc. Fiecare
obiect era un punct într -un spațiu cu 7 dimensiuni, unde fiecare dimensiune reprezenta
nivelul radiației într -o bandă a spectrului. Proiectul Sloan Sky Survey este o încercare
mult mai ambițioasă de a cataloga și grupa întregul univers vizibil.

3. Documentele pot fi percepute ca puncte într -un spațiu multi -dimensional în care fiecare
dimensiune corespunde unui cuvânt posibil. Poziția documentului într -o dimensiune
este dată de numărul de ori în care cuvântul apare în document (sau doar 1 dacă apare,
0 dacă nu). Clusterele de documente în acest spațiu corespund deseori cu grupuri de
documente din același domeniu.

Măsuri ale distanței

Pentru a discuta dacă o mulțime d e puncte sunt suficient de apropiate pentru a fi considerate
un cluster avem nevoie de o măsură a distanței D(x, y) care spune cât de depărtate sunt punctele x
și y. Axiomele uzuale pentru o măsură a distanței D sunt:
1. D(x, x) = 0. Un punct este la dist anță 0 de el însuși.
2. D(x, y) = D(y, x). Distanța e simetrică.
3. D(x, y) ≤ D(x, z) + D(z, y). Inegalitatea triunghiului.
Deseori punctele pot fi percepute ca existând într -un spațiu euclidian k -dimensional și
distanța între orice două puncte, x = [x1 , x2, …, xk] și y = [y1, y2, …, yk] este dată într -una din
manierele uzuale:
1. Distanța comună ("norma L2"):
2. Distanța Manhattan ("norma L1"):
3. Maximul pe o dimensiune ("norma L∞"):
Unde nu există un spațiu euclidian în care să plasăm punct ele gruparea devine mult mai
dificilă. Iată câteva exemple în care are sens o măsură a distanței în lipsa unui spațiu euclidian.
Exemplul : Putem privi paginile web ca puncte într -un spațiu generic 108 -dimensional
unde fiecare dimensiune corespunde unui c uvânt. Totuși, calcularea distanțelor ar fi prohibitivă
într-un spațiu atât de mare. O abordare mai bună este să legăm distanța D(x, y) de produsul scalar
al vectorilor corespunzând lui x și y, din moment ce apoi vom lucra doar cu cuvinte care se află
atât în x cât și în y.

Trebuie să calculăm lungimile vectorilor implicați și acesta sunt egale cu rădăcinile pătrate
ale sumelor pătrătelor numerelor de apariție ale fiecărui cuvânt. Suma produselor numerelor de
apariție ale fiecărui cuvânt în fiecare docum ent se împarte la produsul lungimilor pentru a obține
un produs scalar normalizat. Scădem această cantitate din 1 pentru a afla distanța dintre x și y.
De exemplu, să presupunem că sunt doar patru cuvinte de interes și vectorii x = [2, 0, 3, 1]
și y = [5, 3, 2, 0] reprezintă numărul de apariții al acestora în două documente. Produsul scalar este
2  5 + 0  3 + 3  2 + 1  0 = 16, lungimea primului vector este , iar lungimea
celui de -al doilea este . Astfel,

Asta înseamnă că x și y sunt esențialmente același document; în mod sigur sunt despre
același subiect și vor fi grupate în același cluster. Exemplul 7.2: Șirurile de caractere, cum sunt
secvențele ADN, pot fi similare chiar și dacă există unele inserări și ștergeri precum și modificări
ale unor caractere. De exemplu, abcde și bcdxye sunt destul de similare chiar dacă nu au nici o
poziție comună și nu au nici chiar aceeași lungime. Astfel, în loc să construim un spațiu euclidian
cu câte o dimensiune pentru f iecare poziție, putem defini funcția distanță D (x, y) = | x | + | y | –
2|LCS(x, y)| unde LCS este cea mai lunga subsecvență comună lui x și y. În exemplul nostru
LCS(abcde, bcdxye) este bcde de lungime 4, deci D(abcde, bcdxye) = 5 + 6 – 2  4 = 3; i.e. ș irurile
sunt destul de apropiate.

Abordări pentru grupare (clustering)

La nivel înalt, putem împărți algoritmii de grupare în două mari clase:
1. Abordarea tip centroid. Ghicim centriozii sau punctele centrale pentru fiecare cluster și
asignăm punctele la clusterul având cel mai apropiat centroid.
2. Abordarea ierarhică. Începem prin a considera că fiecare punct formează un cluster.
Comasăm repetat clusterele apropiate prin folosirea unei măsuri pentru apropierea a două clustere
(e.g. distanța dintre ce ntroizii lor), sau pentru cât de bun va fi clusterul rezultat (e.g. distanța medie
de la punctele din cluster la noul centroid rezultat).
Algoritmi prezentați

Vom considera următorii algoritmi de grupare; ei se diferențiază după cum utilizează sau
nu o dis tanță euclidiană și după abordarea folosită, de tip centroid sau ierarhică.

1. BFR [Bradley -Fayyad -Reina]: De tip centroid; utilizează o măsură euclidiană, cu
clustere formate în jurul centroidului printr -un proces gaussian în fiecare dimensiune.
2. Fast map: Nu e realmente un algoritm de grupare ci un mod de a construi un spațiu
euclidian cu puține dimensiuni pornind de la o măsură a distanței.
3. GRGPF: [Ganti et al.]: De tip centroid dar utilizează doar o măsură a distanței și nu un
spațiu euclidian.
4. CURE: Ierarhic și euclidian, acest algoritm se ocupă de clustere având forme
neobișnuite.
Algoritmul k -means

Acest algoritm este un algoritm popular care ține datele în memoria centrală și pe care se
bazează algoritmul BFR.. k -means alege k centroizi de cluster și asignează punctele la acestea
alegând centroidul cel mai apropiat de punctul respectiv. Pe măsură ce punctele sunt asignate la
un cluster, centroidul acestuia poate migra.
Exemplu: Pentru un exemplu foarte simplu cu cinci puncte în două dimensi uni să privim
Fig. 15. Presupunem că asignăm punctele 1, 2, 3, 4 și 5 în această ordine, cu k=2. Atunci punctele
1 și 2 sunt asignate celor două clustere și devin centroidul lor pentru moment.

Când considerăm punctul 3, să presupunem că este mai apropiat de 1, deci 3 se adaugă
clusterului conținând 1 iar centroidul acestuia se mută în punctul marcat ca a. Presupunem că atunci
când asignăm 4 găsim că 4 este mai aproape de 2 decât de a, deci 4 se alătură lui 2 în clusterul
acestuia iar centrul se mută în b. În final, 5 este mai aproape de a decât de b, deci el se adaugă la
clusterul {1, 3} al cărui centroid se mută în c.
 Putem inițializa cei k centroizi alegând puncte suficient de depărtate de orice alt centroid
până obținem k.

 Pe măsură ce calculul pr ogresează putem decide să spargem un cluster și să unim două
dintre ele pentru a păstra totalul de k. Testul pentru a decide asta poate fi să ne întrebam dacă
făcând operația respectivă se reduce distanța medie de la puncte la centroidul lor. 1 5 c 2 a b 3 4
 După localizarea centroizilor celor k clustere putem reasigna toate punctele deoarece
unele puncte care au fost asignate la început pot acum să fie mai aproape de un alt centroid care s –
a mutat.
 Dacă nu suntem siguri de valoarea lui k putem încerc a valori diferite pentru k până când
găsim cel mai mic k astfel încât mărirea lui k nu micșorează prea mult distanța medie a punctelor
față de centroidul lor.
Exemplu urmator ilustrează acest lucru.
Să considerăm datele din figura urmatoare. În mod cla r k=3 este numărul corect de clustere
dar să presupunem ca întâi încercăm k=1. În acest caz toate punctele sunt într -un singur cluster și
distanța medie la centroid va fi mare.

Presupunem că apoi încercăm k=2. Unul dintre cele trei clustere va fi un cluster iar celelalte
două vor fi forțate să creeze un singur cluster, asa cum arată linia punctată. Distanța medie a
punctelor la centroid de va micșora astfel considerabil.
Daca luăm k=3 atunci fiecare dintre clusterele vizibile va forma un clus ter iar distanța
medie de la puncte la centroizi se va micșora din nou, așa cum arată graficul din Fig. 16. Totuși,
dacă mărim k la 4 unul dintre adevăratele clustere va fi partiționat artificial în două clustere
apropiate, așa cum arata liniile continui. Distanța medie la centroid va scădea puțin dar nu mult.
Acest eșec de a merge mai departe ne arată că valoarea k=3 este corectă chiar dacă datele sunt în
atât de multe dimensiuni încât nu putem vizualiza clusterele.

Concluzii

În final, se poate spune că toate sarcinile de analiză a sentimentului sunt foarte
provocatoare. Înțelegerea și cunoașterea problemei și soluționarea acesteia sunt încă limitate.
Motivul principal este că sarcina de prelucrare a limbajului natural nu are probleme ușoare. Un alt
motiv se poate datora modurilor noastre populare de a face cercetare. Probabil ne -am bazat prea
mult pe mașină si pe algoritmi de învățare. Unii dintre cei mai efic ienți algoritmi de învățare a
mașinilor , nu produc rezultate umane de înțeles, si, deși, ele pot obține o precizie îmbunătățită,
știm puține despre cum și de ce. Cu toa te acestea, acest lucru a făcut progrese semnificative în
ultimii ani. Acest lucru este evident din numărul mare de start -upuri ale companiilor care oferă
servicii de analiză sentimentală sau servicii de consultanță de analiza de text . Există o nevoie reală
și imensă în industrie pentru astfel de servicii, deoarece fiecare companie dorește să știe cum îș i
percep consumator ii produsele și serviciile dar și ale concurenților lor. Același lucru se poate spune
și despre consumatori pentru că ori de câte ori cineva vrea să cumpere ceva, vrea să știe opiniile
utilizator ilor existenți. Nevoile și provocările tehnice vor men ține câmpul vibrant și plin de viață
pentru anii următori.

Bibliografie

http://cifr.cs.pub.ro/ullman/cluster1 -ro.pdf
http://www.ace.tuiasi.ro/users/103/2012_Agavril oaei_Ioan__PhD%20rez.pdf
http://rochi.utcluj.ro/rrioc/articole/RRIOC -8-3-Radu.pdf
https://github.com/jeffreybreen/twitter -sentiment -analysis -tutorial –
201107/tree/master/data/opinion -lexicon -English
https://github.com/jeffreybreen/twitter -sentiment -analysis -tutorial –
201107/tree/master/data/opinion -lexicon -English