Avand la baza un sistem de analiza a facturilor si crearea de statistici pe baza [623141]

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
catre 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 re gă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;

Algoritmi de clusterizare
Implementa rea 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 două 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 n ivel fără, nici o ierarhie între documentele aceluiași cluster. În
acest punct un site este reprezentat sub forma 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, anume 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
de 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 doc ument 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

document î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 aciclic. Î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
un 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 d e 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 complexitatea 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ă pu nctele î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
marcat 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 indicâ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 de puncte sunt sufic ient 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 distanță 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, …, x k] ș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 punctele 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 cuvâ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 document se împar te 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] re prezintă 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
fiecare 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 centroizii lor), sau pentru cât de bun va
fi clusteru l 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 distanță 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. Fastmap: Nu e realmente un algoritm de grupare ci un mo d 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ă dimensiuni
să privim Fig. 15. Presupunem că asignăm punc tele 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 i ar 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, de ci 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 progresează 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 clust ere 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 încerca valori diferite pentru k
până când găsim cel ma i 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 clar 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.

Bibliografie

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