Proces ări Hadoop folosind multiple tipuri de informație Coordonator Student Dorin Cârstoiu Mocanu Mihai 2017 2 Cuprins 1. Introducere… [623140]

1

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

LUCRARE DE DIZERTAȚIE
Proces ări Hadoop folosind multiple tipuri de
informație

Coordonator Student: [anonimizat]

2017

2
Cuprins
1. Introducere ………………………….. ………………………….. ………………………….. ………………………….. ………….. 3
2. Scopul lucrării ………………………….. ………………………….. ………………………….. ………………………….. ……….. 4
3. Motivare ………………………….. ………………………….. ………………………….. ………………………….. ………………. 4
4. Obiective ………………………….. ………………………….. ………………………….. ………………………….. ……………… 6
5. MongoDb ………………………….. ………………………….. ………………………….. ………………………….. …………….. 6
6. Analiza sentimentala si subiectivitatea ………………………….. ………………………….. ………………………….. …. 9
6.1 Problema analizei sentimentului ………………………….. ………………………….. ………………………….. 10
6.2 Evaluarea sentimentului și a subiectivității ………………………….. ………………………….. ……………. 10
6.3 Analiza sentimentului bazată pe elemente ………………………….. ………………………….. …………….. 10
6.4 Analiza sentimentului propozițiilor comparative ………………………….. ………………………….. …….. 10
7. Sisteme de recomandare ………………………….. ………………………….. ………………………….. ………………….. 11
7.1 Caracteristici ale sistemelor de recomandare ………………………….. ………………………….. …………….. 11
7.2 Probleme clasice ale sistemelor de recomandare ………………………….. ………………………….. ……….. 12
7.3 Evaluarea sistemelor de recomandare ………………………….. ………………………….. ………………………. 13
8. Algor itmi de clusterizare – Invatarea nesupervizata ………………………….. ………………………….. ………….. 14
8.1 Clusterizarea partițională ………………………….. ………………………….. ………………………….. …………….. 15
8.2 Clusterizarea ierharhică ………………………….. ………………………….. ………………………….. ………………. 15
9. Recomandari Amazon.com: Item -to-Item Collaborative Filtering ………………………….. ……………………. 22
10. Analiza comentariilor ………………………….. ………………………….. ………………………….. ……………………… 26
10.1 Sistemul de ordonare ………………………….. ………………………….. ………………………….. ………………… 26
10.2 Regul i de ordonare ………………………….. ………………………….. ………………………….. ……………………. 27
11. Descrierea aplicatiei ………………………….. ………………………….. ………………………….. ………………………… 31
Concluzii ………………………….. ………………………….. ………………………….. ………………………….. …………………. 31
Bibliografie ………………………….. ………………………….. ………………………….. ………………………….. ……………… 37
Anexe ………………………….. ………………………….. ………………………….. ………………………….. …………………….. 39

3
1. Introducere

Bazele de date relaționale sau RDMBS (Relațional database management systems) fac
parte din tehnologia predominantă care este fol osită la ora actuală pentru a stoca și păstra date
atât pentru aplicațiile web cât și pentru aplicațiile din companii. Chiar dacă pe parcursul timpului
s-a mai încercat adoptarea unor alte tehnologii cum ar fi baze de date bazate pe obiecte sau
stocarea su b formă de XML nu au reușit să fie atât de populare ca bazele de date relaționale,
acestea chiar fiind absorbite ajungându -se să se poată stoca direct un XML și apoi să fie folosit
pentru indexare de text.
Recent conceptul de a avea o singură bază de date care poate acoperi absolut orice nevoie de
stocare a început să fie analizat de către cei care lucrează în domeniu și astfel s -au lovit de
probleme de eficiență și consistență a datelor lucru ce a făcut posibilă apariția unei varietăți mari
de alternative ale bazelor de date relaționale.
Acest lucru a dus la apariția de baze de date numite NOSQL (not only SQL), utilizat pentru a
specifica creșterea bazelor de date non relaționale care devin din ce în ce mai folosite de către
dezvoltatorii Web.
Conceptele de bază, tehnicile și modelele de programare folosite la implementarea
bazelor de date NoSql sunt următoarele: Consistența datelor care spune dacă un sistem de date
este consistent sau nu după execuția unor operații. Se poate spune că într -un sistem distr ibuit de
obicei atunci când cineva efectuează o operație de scriere în baza de date, toți ceilalți clienți care
vor să efectueze o operație de citire trebuie să aibă disponibile toate datele care au fost scrise
anterior.
Disponibilitatea datelor înseamnă că datele trebuie să fie stocate într -un sistem care
permite citirea și scrierea continuă chiar și atunci când unul dintre computerele din sistemul
distribuit are o problemă hardware sau software. Toleranța la partiții se referă la faptul că atunci
când c omunicația se face în rețea, datele trebuie să fie disponibile chiar dacă între două noduri
din rețea nu se poate realiza o conexiune la momentul în care se face cererea. Astfel sistemul
trebuie să reușească să gestioneze acest tip de problemă iar una din rezolvări ar fi multiplicarea
datelor astfel încât atunci când un nod nu este disponibil, datele necesare să fie accesate dintr -o
altă locație.
Stocarea datelor se realizează sub formă de cheie -valoare, având un model simplu în
comun: un dicționar, o mapa re care ajută clienții să pună sau să extragă valori pentru diferite
chei. Pe lângă faptul că ne oferă un API (interfețe ce pot fi implementate în funcție de nevoia de
business), stocările moderne sub formă de cheie valoare favorizează scalabilitatea cresc ută și
consistentă iar multe dintre ele omit cererile ad -hoc și în special join -urile și operațiile agregate.
De obicei lungimea cheilor stocare are o dimensiune limitată la un număr de octeți pe când la
valoare sunt mai puține limitări de dimensiune pentr u date.

4

Cum se poate vedea în poza de mai sus sunt patru tipuri de baze de date.
Pentru fiecare tip, se va alege o bază de date și va fi analizată pentru a putea stabili cum se
comportă fiecare bază de date atunci când este vorba de o cantitate mare de informație.
2. Scopul lucr ării

Cercetarea se bazează pe folosirea de multiple baze de date, în vederea alegerii celei mai
potrivite pentru proiectul actual. Se vor studia timpii de răspuns de scriere și citire dar și
stabilitatea de care dau dovadă. De asemenea este foarte importantă utilizarea lor în rețea pentru
a putea fi distribuite pe întreg cluster -ul de computere. Obiectivul general este de a crea o
aplicație cu ajutorul căreia firmele de Business Intelligence (BI) care vor analiza datele provenit e
dintr -un lanț de magazine de tip supermarket să poată scoate rapoarte în ceea ce privește
vânzările acestora. De asemenea vor putea să precizeze care vor fi vânzările în anumite zile cheie
și cu ce anume trebuie să alimenteze stocul de produse într -un mo d eficient. Un obiectiv
secundar al proiectului este învățarea de tehnologii noi și implementarea lor în aplicații care vor
putea fi folosite pe piață pentru a ușura munca oamenilor.

3. Motivare

Având la bază un sistem de analiză a facturilor și crear ea de statistici pe baza rapoartelor
și datorită creșterii cu o viteză foarte mare a datelor efectuate de către utilizator îmi doresc a crea
un sistem de recomandare pe baza review -urilor date de către utilizator pentru a putea sugera
produce ce pot fi cum părate în viitor de către utilizator, sau pentru a -I oferi o mai bună
perspectivă asupra varietății produselor din cadrul unui magazin online. Evoluția continuă a
dimensiunii și utilizării Web -ului a avut drept consecință directă apariția diferitelor provo că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 info rmațiile disponibile pe Web, precum și
tratarea intereselor și nevoilor utilizatorilor prin personalizarea informațiilor și serviciilor oferite.

5
Termenul de Web mining a fost introdus odată cu explozia Web -ului de la mijlocul anilor 1990,
pentru a confirm a 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 intermediul regăsirii automate a paginilor și serviciilor web, ext ragerea
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
cercetare deja consacrate cum ar fi bazele de date, regăsirea informației (Text REtrieval
Conference, TREC), inteligența artificială, învățarea automată, text mining, etc. Principiile lor
sunt abordate și adaptate în Web mining pentru a face față noilor provocări. Cel mai evident
domeniu care a trebuit să se adaptate ze 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
activitate a 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 cuno scute. 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 actualitate 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 finali este imposibilă deoarece noi idei și subiecte sunt pro puse în
mod continuu, fiind acceptate sau respinse de comunitatea virtuală. Un alt motiv este acela că
există tendința puternică de a prezenta subiecte strâns legate de trecutul autorului lor, astfel
acordând -se importanață subiectelor și legăturilor de ca re 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 inter -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 tag -uri sau etichete folosite la formatare, astfel
aplicați ile 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 caracteristicilo r 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 prezen tate 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 cerce tării
acestui domeniu și are un rol cheie în îndeplinirea scopului final. Cel mai important instrument al

6
evaluării îl reprezintă colecția de test: o colecție de documente cu un set de subiecte și judecăți
care indică ce document este relevant relativ la u n 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 investigată în mod oficial. Deși au mai fost create
colecții de te st 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 tehnicilor curente de Web mining și a unora noi având ca s uport 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ă lucrare
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.
4. Obiective

Obiectivul general al acestei cercetări este acela de a îmbunătăți sistemul de recomandare a
produselor încercând astfel folosirea datelor primite ca și feedback de la utilizator și nu doar
descrierea produsului dar și luarea în condiserare a factorului uman cum ar fi “ironia” sau
“entuziasmul” din moment ul adăugării evaluării dar și în 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 regăsire a informației. Datorită diverselor abordări a tunci
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;

5. MongoDb

MongoDB este o baza de date opensource care foloseste un model de date ce vizeaza
documentele. Aceasta este unul dintre tipurile de baze de date care au avut o ascensiune la
mijlocul anilor 2000 sub bannerul NoSQL. MongoDB este construit pe baza unei arhitecturi a
colectiilor si a documentelor, nefiind folosite tabele si randuri ca in bazele de date relationale.
Documentele cuprind seturi de perechi cheie -valoare si sunt unitatea de baza de date in
MongoDB. Colectiile contin seturi de documente si functioneaza ca echivalentul tabelelor de
baze de date relationale.

7
Ca si alte baze de date NoSQL, MongoDB sustine designul dinamic al
schemelor,permitand documentelor dintr -o colectie sa aiba campuri s i structuri diferite. Baza de
date foloseste un format de stocare a documentelor si de schimb de date numit BSON, care
furnizeaza o reprezentare binara a documentelor de tipul JSON. Impartirea automata permite
distribuirea datelor dintr -o colectie pe mai m ulte sisteme pentru scalabilitate orizontala, pe
masura ce volumul de date creste.
Acest tip de baze de date accepta campuri, interogari de intercal precum si cautari ale
expresiilor regulate. Interogarile pot returna campuri specifice ale documentelor si de asemenea
include functii JavaScript definite de catre utilizator. De asemenea, interogarile pot fi
configurate sa returneze o monstra aleatorie de rezultate dintr -o anumita dimensiune. Campurile
dintr -un document MongoDB pot fi indexate cu indici prima ri si secundari.
MongoDB confera disponibilitate ridicata cu seturi de replici. Un set de replici consta din
doua sau mai multe copii ale datelor. Fiecare membru al setului de replici poate actiona in rolul
replicii primare sau secundare in orice moment. Toate scrierile si citirile sunt realizate in replica
primara in mod implicit. Replicile secundare pot contine o copie a datelor primare folosind
replicare incorporate. Atunci cand o replica primara esueaza, setul de replica conduce automat un
process de a legere pentru a determina ce secundara trebuie sa devina primara. Secundarele pot
servi optional operatii de citire, dar acea informatie este in cele din urma consistente in mod
implicit.
MapReduce este un model de programare si o implementare asociata pen tru procesarea si
generarea seturilor mari de date cu un algoritm paralel, distribuit pe un cluster. Acesta poate fi
folosit pentru pentru procesarea in serie a operatiunilor de date si agregare. Cadrul de agregare
permite utilizatorilor sa obtina tipul de rezultate pentru care clauza SQL GROUP BY este
folosita. Operatorii de agregare pot fi stransi impreuna pentru a forma o conducta – analog cu
tevile Unix. Cadrul de agregare include operatorul $lookup care poate uni documente din mai
multe documente, prec um si operatori de statistica, cum ar fi abaterea standard.
MongoDB scaleaza orizontal folosind impartirea datelor. O impartire a bazei de date este
o partitie orizonatala a datelor intr -o baza de date sau un motor de cautare. Fiecare partitie
individual a este denumita un shard (impartire) sau un shard de baza de date. Acesta este pe o
instanta separata a serverului, pentru a distribui sarcinile. Utilizatorul alege o cheie shard(de
impartire) ce determina modul in care datele dintr -o colectie vor fi distri buite. Datele sunt
impartite in interval (bazate pe cheia shard) si distribuite pe mai multe fragmente. MongoDB
poate rula pe mai multe severe, echilibrand datele de incarcare sau duplicare pentru a mentine
sistemul in functiune in cazul unei defectiuni hardware.
Atunci cand vine vorba de arhitecura, MongoDB confera driver oficiale pentru o varietate
de limbaje de programare populare si medii de dezvoltare. De asemenea, exista un numar mare

8
de drivere neoficiale sau incurajate de catre comunitate si pent ru cadre sau alte limbaje de
programare.

Instalarea bazei de date Mongo:

1. Descărcarea ultimei versiuni de bază de date accesând:
https://www.mongodb.org/downloads#production
2. Crearea locației de stocare a bazei de date ( pentru windows locația prestabilită este
C:\data\db
3. Pornirea procesului mongod.exe
4. Accesarea bazei de date folosind Robomongo, utilitar de management al bazei de date
(portul pe care este pornită baza de date este 27017 inițial)

Pentru pornirea securizată a bazei de d ate se folosesc următorii pași:

1. Se deschide Shell -ul folosind mongo.exe
2. Se folosește comanda : use admin pentru a accesa baza de date cu configurări
3. Se adaugă un utilizator cu acces de root
db.createUser(
{
user: "accountUser",
pwd: "password",
roles: [ "readWrite", "dbAdmin" ]
}
)
Pentru a face un user să fie root este nevoie ca el să fie în următoarele grupuri :
readWriteAnyDatabase,
dbAdminAnyDatabase,
userAdminAnyDatabase

9
4. Se pornește procesul mongod.exe cu comanda –auth sau se adaugă următoarea linie în
fișierul config.properties “auth=true”

6. Analiza s entimentala si subiectivitatea

Informațiile textuale din lume pot fi în mare parte clasificate în două tipuri principale: fapte și
opinii. Faptele sunt expresii obie ctive 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ățile lor. Conceptul de opinie este foarte larg. Î n
cele ce urmează, ne concentrăm doar pe expresiile de opinie care transmit sentimentele pozitive
sau negative ale oamenilor. O mare parte din cercetările existente asupra textului și procesarea
informațiilor a fost axată pe extragerea și regăsirea informa țiilor factuale, de exemplu informații.
Regăsirea, căutarea pe Web, clasificarea 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 opiniilor decât până de
curând. Opiniile 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 opiniei e ste 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 utiliz atiorilor despre produsele și serviciile sale, realiza sondaje de
opinie. Cu toate acestea, cu Web -ul, în special cu creșterea explozivă a datelor generate de către
utilizatori, lumea a fost transformată.
Web -ul a schimbat în mod dramatic modul în care oam enii își exprimă opiniile. Acum utilizatorii
pot crea recenzii de produse la site -urile comercianților și să -și exprime opiniile despre aproape
orice în forumurile de pe Internet. Grupuri de discuții și bloguri, denumite colectiv conținutul
generat de util izatori. 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 limitează la a -și întreba
prietenii deoarece există multe recenzii despre produse pe Web care oferă opinii ale utilizatorilor
existenți ai produsului. Pentru o companie, nu mai este necesar să se efectueze sondaje, să
angajeze consultanți externi pentru a găsi opinii ale consumatorilor cu privire la produsele sale,
deoarece conținutul generat de utilizat ori 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 există un număr mare de surse diverse și fiecare sursă poate avea,
de asem enea, 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 facă un rezumat ș i să le organizeze în forme
utile. Astfel, pentru descoperirea automată a opiniei sunt necesare sisteme de sumare. Analiza
sentimentului este o problemă dificilă de prelucrare a limbajului natural sau de analiză a textului.
Datorită valorii sale extraordin are 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 de analiză a sentimentului
Numai în SUA acest domeniu de cercetare se concentre ază pe următoarele subiecte:

10
6.1 Problema analizei sentimentului

Ca orice problemă științifică, înainte de a o rezolva, trebuie să o definim pentru a forma
problema. Formularea va introduce definițiile de bază, conceptele de bază și problemele, sub –
proble mele și obiectivele -ț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ă.

6.2 Evaluarea sentimentului și a subiectivității

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

6.3 Analiza sentimentului bazată pe elemente

Acest model descoperă mai întâi obiectivele pe care au opiniile au fost exprimate într -o
propoziție și apoi determină dacă opiniile sunt pozitive, negative sau negative neutru. Obiectivele
sunt obi ecte și componentele, atributele și caracteristicile acestora. Un obiect poate fi un produs,
serviciu, individ, organizație, eveniment, subiect, etc. De exemplu, într -o propoziție de revizuire
a produsului, se identifică caracteristicile produsului care au fost comentate de către recenzor și
se determină dacă comentariile sunt pozitive sau negative. De exemplu, "Durata de viață a
bateriei este prea scurtă ", comentariul se referă la" durata de viață a bateriei " a camerei și opinia
este negativă. Multe exem ple 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 caracteristici ale
produsului sunt plăcute sau nu de către consumatori. Aceste informații nu sunt desc operite prin
clasificarea sentimentului și subiectivității

6.4 Analiza sentimentului propozițiilor comparative

Evaluarea unui obiect se poate face în două moduri principale, evaluarea directă și compararea.
Aprecierea directă, numită opinie directă, dă r ezultate pozitive sau negative și o opinie despre
obiect fără a menționa alte obiecte similare. Compararea înseamnă a compara obiectul cu alte

11
obiecte similare (de exemplu, produse concurente). De exemplu, "Calitatea imaginii acestei
camere este slabă ", e xprimă o opinie directă, î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 determi nă ce obiecte
sunt preferate.
7. Sisteme de recomandare

Sistemele de recomandare sunt sisteme care oferă facilități de predicție a preferințelor
utilizatorilor într -un spațiu de articole dat, pentru a -i ajuta în procesul de selecție a articolelor
(Resnic k și Varian, 1997). După algoritmii utilizați, aceste sisteme se împart în două mari
categorii. Primul tip de sisteme de recomandare utilizează recomandarea bazată pe conținutul
articolului. Acești algoritmi se axează pe conținutul efectiv al articolului ș i oferă ca recomandări
articole similare unui articol inițial pe baza unor metrici specifice (de pildă: tag -uri, tema
articolului, etc). Această abordare este cuprinsă în aplicația noastră prin recomandările făcute pe
bază de etichete (tag -uri) și pe baza trăsăturilor din imagine. Punctul slab al acestei abordări este
că nu ia în considerare și partea socială, ce constă în modele de similaritate între profilurile de
preferințe ale utilizatorilor.
Cea de -a doua modalitate de abordare, filtrarea colaborativă, utilizează entitățile din aplicație
(utilizatori, articole, preferințe, acțiuni șamd) și recomandă articole pe baza preferințelor
utilizatorilor. Preferințele utilizatorilor pot fi obținute prin exprimarea lor explicită, prin vot, sau
implicită, prin stud iul comportamentului utilizatorilor. Metodele de filtrare colaborativă se pot
clasifica la rândul lor în două categorii: (1) metode bazate pe utilizator: se folosesc preferințele
utilizatorilor similari pentru un articol dat pentru a descoperi recomandări de articole,
similaritatea între utilizatori determinându -se pe baza preferințelor exprimate în sistem
(utilizatorii similari având, informal spus, „aceleași gusturi”) ; precum și (2) metode bazate pe
articol: se găsesc articolele similare unui articol dat prin cuantificarea anumitor aspecte sociale,
de pildă faptul că mulți dintre utilizatorii care au preferat articolul dat, au votat pozitiv și un alt
articol.

7.1 Caracteristici ale sistemelor de recomandare

Sistemele de recomandare sunt caracterizate prin multiple criterii, iar unele dintre cele mai
importante dintre acestea sunt detaliate în continuare (Riedl, Beaupre, Sanders, 2009).
Transparența recomandării reprezintă o calitate prin care sistemul oferă o motivație pentru
recomandarea unui anumit a rticol (de ex: „Pentru că v -a plăcut filmul Nașul, vă recomandăm și
Lista lui Schindler”), iar astfel poate crește încrederea unui utilizator în calitatea algoritmului de
recomandare utilizat. Un alt aspect este legat de explorare versus exploatare. Presup unem situația
în care există două articole care pot fi expuse (recomandate) unui grup de utilizatori și se poate
înregistra activitatea pentru un articol inițial expus.

12
Problema la care trebuie să se răspundă este când și dacă ar trebui să fie expus și al doilea articol,
așa încât impactul dorit asupra utilizatorului să fie maxim (ex: număr de vizualizări, volum de
vânzări etc), și este cunoscută în inteligența artificială ca și problema „multi -armed bandit” (mai
multe detalii despre ea în Vermorel și Mohr i, 2004). Problema constă în faptul că un jucător are
la dispoziție un joc mecanic de tip slotmachine cu mai multe variante (manete), iar el dorește o
strategie de tragere a manetelor astfel încât să -și maximizeze profitul total. Ghidarea navigării
reprezi ntă problema oferirii unei interfețe adecvate utilizatorului, atunci când există un conținut
foarte vast în cadrul aplicației, pe baza unor tehnici de interacțiune om -calculator, a unor
algoritmi inteligenți, a prezicerii intenției sau dispoziției utilizat orului șamd.
Prin valorificarea corectă a momentului de timp, un sistem de recomandare ține cont de
schimbările pe care trecerea timpului le aduce asupra relevanței unui articol, precum: creșterea
interesului pentru articole ce privesc evenimente recente, posibilitatea ca sistemul de
recomandare să asimileze rapid informație nouă etc. Scalabilitatea sistemului este deosebit de
importantă în contextul gestiunii de volume mari de date și în continuă creștere. În plus,
algoritmii de recomandare sunt în gener al iterativi, bazați pe procesarea extensivă a datelor. Sunt
de dorit timpi de răspuns mici pentru utilizatorul final, iar în acest sens sunt folosite procesări
offline, și în mică parte procesări online, la momentul cererii formulate de utilizator. Divers itatea
constituie, potrivit lui (Linden, 2009), un aspect de dorit în unele cazuri de recomandare, atunci
când recomandarea de elemente aproape duplicate minimizează impactul său utilizabilitatea
sistemului pentru utilizator.

7.2 Probleme clasice ale sis temelor de recomandare

Problema „cold start” apare în cazul utilizatorilor noi ai sistemului, atunci când nu există
informație explicită despre preferințele acestora pentru a produce recomandări. Printre soluțiile
posibile se numără: completarea de chesti onare legate de preferințe – nerecomandat întrucât un
sistem de recomandare inteligent ar trebui să ceară explicit cât mai puține informații din partea
utilizatorului – sau utilizarea de agenți de învățare care să descopere profilul utilizatorului pe
baza acțiunilor realizate de acesta. Problema „first rater” este problema echivalentă în cazul
articolelor nou intrate în sistem, pentru care nu există încă preferințe exprimate. O soluție viabilă
în acest caz este realizarea unui mecanism hibrid de recomandare , care poate face recomandări
bazate și pe conținutul efectiv al unui articol pentru a descoperi articole similare.
În ce privește utilizatorul însuși, apare problema manipulării (influențării) sistemului de
recomandare de către un grup mic de utilizatori , de exemplu prin comentarii negative la adresa
unui articol oferit de competitori. În acest sens, trebuie ca sistemul să discearnă și să elimine
aceste tentative de manipulare. Trebuie evaluat de asemenea și impactul recomandării, constând
în costul furni zării unei recomandări proaste sau omiterii unei recomandări bune, atunci când
alegerea unui articol are impact important asupra utilizatorului. Problema confidențialității apare
în condițiile în care trebuie ca un utilizator să poată evalua recomandările primite, dar nu se
dorește ca preferințele utilizatorilor care au condus la elaborarea recomandării să fie publice sau
să poată fi determinate prin manipularea datelor de intrare ale sistemului.

13
7.3 Evaluarea sistemelor de recomandare

Evaluarea perfo rmanțelor algoritmilor de recomandare se poate realiza prin utilizarea
unui spectru larg de metode și metrici (Shani și Gunawardana, 2011). O măsură a erorii foarte
folosită este root mean square error (RMSE), care se calculează pentru preferințele utiliza torilor
prin următoarea formulă:

Altă măsurătoare a erorii constă în realizarea mediei diferenței absolute între valoarea reală a
preferinței și valoarea estimată de sistemul de recomandare. Evaluarea sistemelor de
recomandare se mai poate realiza și p rin împărțirea datelor într -un set de antrenare și un set de
testare în maniera în care se face și evaluarea clasificatorilor, deși este o metodă mai puțin
frecventă. Sistemului îi este prezentat setul de antrenare și apoi trebuie să calculeze preferințele
pentru instanțele din setul de testare. Aceste preferințe sunt comparate cu cele reale și se obține
astfel un scor de eroare pentru acest algoritm. Însă nu corectitudinea în întreg setul contează
(Linden, 2009), măsurată prin RMSE, de exemplu, ci uneori este de dorit minimizarea erorii doar
în recomandările care intră în „Top N”. Cu alte cuvinte, sistemul de recomandare dorește să aibă
precizie maximă în determinarea celor mai probabile preferințe și nu a articolelor mai puțin
probabil să fie preferate.

StumbleUpon
• comunitate Web
• facilitează descoperirea de site -uri
• sistem de recomandare bazat pe utilizator
• peers (utilizatori cu "gusturi" similare)
• friends (aleși de utilizator)
• filtrare colabora tivă (eng. "colaborative filtering")
• automatizează "word of mouth"
Principiile sistemului

14

8. Algoritmi de clusterizare – Invatarea nesupervizata

Învățarea nesupervizată (unsupervised learning) nu necesită prezența setului de antrenament
cu date preclasificate apriori. Scopul învățării nesupervizate este definit de necesitatea de
explorare a datelor pentru descoperirea unor structuri intrinseci. Utilizatorul explorează datele cu
scopul de a găsi structuri noi, interesante și folositoare. Printre cele mai importante metode ale
învățării nesupervizate este clusterizarea, care organizează datele în grupuri similare numite
clustere în așa fel încât instanțele dintr -un grup sunt similare dintr -un anumit punct de vedere și
total diferite față de datele din celelalte grupuri. Conceptual, procesul de clusterizare poate fi
definit astfel:
Clusterizarea reprezintă procesul de organizare a datelor dintr -o colecție nestructurată în
grupuri numite clustere ale căror membrii sunt similari într -un anumit fel. Calitatea diferitelor
metode de clusterizare se diferențiază prin folosirea funcțiilor obiectiv.
Calitatea clusterizării se referă în primul rând la omogenitatea în cadrul grupurilorși
separabilitatea între grupurile rezultate în urma procesului de cl usterizare. Procesul de învățare
nesupervizată este unul iterativ și este ilustrat în figură de mai jos.
Similaritatea este, în mod teoretic, metrica care reflectă potrivirea sau puterea de relație
între două date, două șiruri text sau caracteristici.
Clusterizarea are nevoie de o funcție de similitudine pentru a măsura cât de similare sunt
două date, sau alternativ, o funcție depărtare (disimilaritate) pentru a măsura distanța dintre două
date.

15
În domeniul informatic un număr din ce în ce mai mare de aplic ații aplică metodele de
clusterizare pentru a obține rezultate superioare. Este cazul clusterizării documentelor (Li &
Chung, 2005) și a sistemelor de regăsire a informației (Grossman & Frieder, 2004). Principala
problemă a clusterizării o constituie volum ul mare de date care trebuie procesat, algoritmii de
clusterizare fiind în general cu timp de răspuns mare.

Procesul de învățare nesupervizată

8.1 Clusterizarea partițională
Algoritmii de clusterizare ierarhici au ca rezultat o ierarhie de clustere numită dendrogramă,
adică un arbore care reflectă strucura clusterelelor de date la diferite niveluri de similaritate.
Datele nu sunt atribuite unui anumit cluster într -un singur pas, clusterele atomice găsindu -se la
baza arborelui, iar toate clusterele in termediare fiind cuprinse într -un cluster rădăcină care
conține tot data setul. Clusterele de pe fiecare nivel al ierarhiei se obțin prin gruparea clusterelor
situate pe nivelul imediat inferior, criteriul de grupare făcându -se pe baza calculului distanței
dintre datele clusterelor.
Există două metode de clusterizare ierarhică (Hastie, et al., 2009):
· Clusterizare aglomerativă (bottom up): dendrograma se construiește de jos în sus prin
combinarea celor mai similare perechi de clustere de pe fiecare nive l pentru a merge apoi pe un
nivel mai sus. Procesul continuă până când toate clusterele sunt grupate într -un singur cluster,
clusterul rădăcină. Pseudocodul algoritmului aglomerativ este prezentat în figură de mai jos.
· Clusterizarea divizivă (top down ): pornește de la un singur cluster care cuprinde toate datele,
clusterul rădăcină și se împarte într -un set de clustere, fiecare cluster fiind apoi divizat recursiv
până se obține clustere atomice care conțin o singură dată.
8.2 Clusterizarea ierharhică

16
Algoritmii de clusterizare ierarhici au ca rezultat o ierarhie de clustere numită dendrogramă,
adică un arbore care reflectă strucura clusterelelor de date la diferite niveluri de similaritate.
Datele nu sunt atribuite unui anumit cluster într -un singur pa s, clusterele atomice găsindu -se la
baza arborelui, iar toate clusterele intermediare fiind cuprinse într -un cluster rădăcină care
conține tot data setul. Clusterele de pe fiecare nivel al ierarhiei se obțin prin gruparea clusterelor
situate pe nivelul ime diat inferior, criteriul de grupare făcându -se pe baza calculului distanței
dintre datele clusterelor.
Există două metode de clusterizare ierarhică (Hastie, et al., 2009):
· Clusterizare aglomerativă (bottom up): dendrograma se construiește de jos în su s prin
combinarea celor mai similare perechi de clustere de pe fiecare nivel pentru a merge apoi pe un
nivel mai sus. Procesul continuă până când toate clusterele sunt grupate într -un singur cluster,
clusterul rădăcină. Pseudocodul algoritmului aglomerativ este prezentat în figură de mai jos.
· Clusterizarea divizivă (top down): pornește de la un singur cluster care cuprinde toate datele,
clusterul rădăcină și se împarte într -un set de clustere, fiecare cluster fiind apoi divizat recursiv
până se obține clustere atomice care conțin o singură dată.

Algoritmul de clusterizare ierarhică aglomerativ

Avantaje și dezavantaje
Clusterizarea ierarhică are posibilitatea să utilizeze orice funcție distanță sau similaritate.
Un avantaj al acestei t ehnici îl reprezintă posibilitatea de a explora datele la diferite niveluri de
granularitate, deoarece se reține toată ierarhia de clustere și utilizatorul poate alege să vizualizeze
clusterele la orice nivel al arborelui. Unele studii au demonstrat că clu sterizarea ierarhică
aglomerativă produce rezultate mai bune decât metoda k -means, putând detecta clustere de
forme arbitrare.
Ca puncte slabe, calitatea clustrizării ierarhice poate fi afectată de efectul de lanț și de
datele marginale. Principalele neaju nsuri al metodelor de mai sus sunt date de complexitatea de
calcul și cerințele de spațiu, ceea ce le face foarte neeficiente și nepractice pentru seturi mari de
date, cum este Web -ul. O posibilă soluție pentru această problemă ar fi extragerea de eșantioa ne
asupra cărora se aplică clusterizarea și apoi distribuția datelor la clustere fie pe baza distanței, fie
prin învățare supervizată.

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
două faze. Prima fază este dată de clusterizarea unui site, în care toți termenii din colecție,

17
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 f orma 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, a nume luând în calcul lista de legături (in -site-links) din
interiorul site -ului pentru fiecare document. În figură de mai jos sunt ilustrați grafic pașii
algoritmului.

Inițial, se aplică procesul de clusterizare asupra unui site prin intermediul matric ei 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 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 din tr-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ăru i
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 docume nte. 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 aci clic. Î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 c el 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 “n odul 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ă ușor de
către utilizator.

18
Deoarece normalizarea documentului este făcută 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 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ă punctele într -un număr 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
marcatlocalizarea cazurilor pe o hartă, obținând un desen. 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 probleme i. 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 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 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.

19

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 punctele gruparea devine mult mai
dificilă. Iată câteva exemple în care are sens o măsu ră 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 mar e. 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 s unt egale cu rădăcinile pătrate ale
sumelor pătratelor numerelor de apariție ale fiecărui cuvânt. Suma produselor numerelor de
apariție ale fiecărui cuvânt în fiecare document se împarte la produsul lungimilor pentru a obține
un produs scalar normalizat. S că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 sc alar 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 cl uster. 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ți e 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 lungă 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.

7.3 Abordări pentru grupare (clustering)

La nivel înalt, putem împărți algoritmii de grupare în d ouă mari clase:
1. Abordarea tip centroid.

20
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 clus ter.
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 clusterul rezultat (e.g.
distanța medie de la punctele din cluster la noul centroid re zultat).

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 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.

7.4 Algoritmul k -means
Aces t 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 pun ctele 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 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.

21

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 progresează putem decide să spargem un cluster și să unim două
dintre ele pentru a păstra totalul de k. Testul pentr u a decide asta poate fi să ne întrebăm 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 încerca 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 următor ilustrează acest lucru.
Să considerăm datele din figura următoare. În mod clar k=3 este numărul corect de
clustere dar să presupunem că î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.

22
Presupunem că apoi încercăm k=2. Unul dintre cele trei clustere va fi un cluster ia r
celelalte două vor fi forțate să creeze un singur cluster, așa cum arată linia punctată. Distanța
medie a punctelor la centroid de va micșora astfel considerabil.
Dacă luăm k=3 atunci fiecare dintre clusterele vizibile va forma un cluster iar
distanța m edie 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 .

9. Recomandari Amazon.com: Item -to-Item Collaborativ e Filtering

Sistemele de recomandare sunt cel mai întâlnite pentru scopul lor în cadrul site -urilor de
e-commerce, unde sunt introduse date despre interesele clienților pentru a genera o listă de
produse recomandate.

Algoritmii de recomandare E -commerce operează de cele mai multe ori în medii dificile.
De exemplu:
• O companie de vânzări este posibil să aibă o cantitate uriașă de date, zeci
demilioane de clienți și milioane de produse din categorii diferite.
• Multe aplicații necesita că rezultatele să fie returnate în timp real, în nu mai mult
de jumătate de secundă, cu recomandări la cel mai înalt nivel
• Clienții noi au de obicei informații extrem de limitate, bazate numai pe câteva
cumpărări sau rating -uri de produse
• Clienții mai vechi pot avea o supraabundență de informații, bazate pe mii de
cumpărări și rating -uri
• Datele clienților sunt volatile : Fiecare intractiune produce date folositoare legate
de client, și algoritmul trebuie să răspundă imediat acestor noi informații
În acest moment, e xistă trei modalități pentru a rezolva problema recomandărilor :
tradițional collaborative filtering, cluster models, și metode search -based. Diferită este însă
soluția celor de la Amazon care propun algoritmul item -to-item collaborative filtering. Spre
deosebire de metodele tradiționale, calculele online ale algoritmului lor scalează independent de
numarulde clienți și de numărul de produse regăsite în catalog. Acest algoritm produce
recomandări de o calitate superioară în timp real, fiind eficient chiar și pentru seturi de date
masive.
Algoritmi de Recomandare
Majoritatea algoritmilor de recomandare încep prin a găsi un set de clienți ale căror
produse cumpărate sau clasificate coincid cu produsele cumpărate sau clasificate ale
utilizatorului. Algoritmu l agrega produsele de la acești clienți similari, elimina produsele deja
cumpărate sau clasificate și recomandă produsele rămase utilizatorului. Două verssiuni populare

23
ale acestor algoritmi sunt collaborative filtering și cluster models. Alți algoritmi – inclusive
metodele search -based și item -to-item collaborative filtering – se axează pe găsirea produselor
similar, nu a clienților similari. Pentru fiecare produs cumpărat sau clasificat al utilizatorului,
algoritmul încearcă să găsească produse similar. A poi acesta agrega produsele similare și le
recomanda.
Tradițional Collaborative Filtering
Un algoritm de Tradițional Collaborative Filtering reprezintă un client ca un vector N –
dimensional de produse, unde N este numărul de produse distincte din calatog. Componentele
vectorului sunt pozitive pentru cumpărare sau produse clasificate pozitiv și negativ pentru
produsele clasificate negativ. Pentru a compensa pentru produsele cele mai vândute, algortimul
tipic multiplica componentele vectorului cu inversă frec venței (inversul numărului de clienți care
au cumpărat sau clasificat un produs), făcând astfel produsele mai puțin cunoscute mult mai
relevante. Pentru aproape toți clienții acest vector este extrem de rar. Algoritmul genereaz
recomandări bazate pe câțiva clienți care sunt similari cu utilizatorul. Poate să măsoare
similaritatea dintre doi clienți, A și B, pe diferite căi : o metodă des întâlnită este aceea de a
măsura cosinusul unghiului dintre doi vectori :

Algoritmul poate selecta recomandări de la pro dusele similare ale clienților folosind metode de
asemenea, o tehnică des întâlnită este aceea de a clasifica fiecare produs în funcție de câți clienți
similari l -au achiziționat.
Folosirea collaborative filtering pentru a genera recomandări este scump com putațional.
Valoarea este de O(MN) în cel mai rău caz, unde M este numărul de clienți iar N este numărul
produselor din catalog , din moment ce examinează M clienți și până la N produse pentru fiecare
cumpărător. Cu toate acestea, deoarece vectorul clientu lui mediu este extrem de rar, performanta
algoritmului tinde să fie mai apropiată de O(M + N). Scanarea fiecărui client este aproximativ
O(M), nu O(MN), deoarece aproape toți vectorii de client conțin un număr mic de produse,
indiferent de mărimea catalgul ui. Dar există clienți care au achiziționat și clasificat un procent
semnificativ din catalog, necesitând un timp de procesare de O(N). Prin urmare, performanta
finală a algoritmului este aproximativ O(M + N). Chiar și așa, pentru seturi de date foare mari
precum cele su 10 milionae sau chiar mai mulți clienți și 1 million sau mai multe produse din
catalog – algoritmul întâmpina probelme severe de performanță și scalabilitate.
Este posibil să rezolvăm parțial aceste probleme de scalabilitate prin reducerea mărimea
datelor. Este posibilă reducerea valorării M prin selectarea aleatorie a clienților sau eliminarea
clienților ce prezintă doar câteva achiziții și reducerea valorii N prin eliminarea produselor foarte
sau deloc populare. Este de asemenea posibilă reducerea numărului de produse analizate de un
mic, constant factor prin partiționarea spațiului produsului bazat pe categroria produsului său
clasificarea subiectului. Tehnicile de reducere dimensională precum clustering și analiza
componentelor princip ale pot reduce M sau N cu un factor mare.
Din păcate, toate aceste metode reduc de asemena calitatea recoamndarilor din mai multe
privințe. În primul rând, dacă algoritmul examinează doar un mic eșantion de clienți, clienții
selectați vor fi mai puțin simi lari utilizatorului. În al doilea rând, partiționarea produs -spatiu
restictioneaza recomandările către o arie de produs sau subiect specifică. În al treilea rând, dacă
algoritmul elimina cele mai populare sau deloc populare produse, acestea nu vor apărea n iciodată
că recomandări iar clienții ce au cumpărat doar acele produse nu vor primi recomandări.
Tehnicile de reducere dimensională aplicate spațiului produsului tind să aibă același efect prin

24
eliminarea produselor cu frecvența redusă. Reducerea dimension ală aplicată spațiului clientului
grupează eficient clienți similari în clusters, care pot de asemea degrada calitatea recomandărilor.
Modele Cluster
Pentru a găsi clienți care sunt asemenatori utilizatorului, modelele cluster divid baza
clienților în mult e segmente și tratează sarcina că o problemă de clasificare. Scopul algoritmului
este acela de a atribui utilizatorul segmentului care conține clienții cei mai similari. Apoi acesta
folosește cumpărăturile și clasificările clienților prezente în segment pe ntru a genera
recomandări.
Segmentele în general sunt create folosind o grupare sau alți algoritmi de învățare nesupervizata,
deși unele aplicații folosesc segmente determinate manual. Folosind un metric de similaritate, un
algoritm de clustering grupează cei mai similari clienți împreună pentru a forma clusters sau
segmente. Deoarece gruparea optimă pe seturi de date mari este nepractică, majoritatea
aplicațiilor folosesc variate forme de generare de grupare greedy.
Acești algoritmi pornesc de obicei cu u n set inițial de segemnte, care de cele mai multe
ori conțin un client selectat aleatoriu fiecare. Apoi aceștia potrivesc clienții în mod repetat cu
segmentele existente, de obicei cu ceva prevedere pentru crearea unor noi segmente sau
îmbinarea unor segme nte existente. Pentru seturi de date foarte mari – în special acelea cu
dimensiune mare – eșantionarea sau reducerea dimensională este de asemenea necesară. Odată
ce algoritmul generează segmentele, acesta calculează similaritatea clientului cu vectorii c are
rezuma fiecare segment, apoi alege segmentul cu cea mai mare similaritate și clasifică
utilizatorul în consecință. Unii algoritmi clasifica utilizatorii în segmente multiple și descrie
puterea fiecărei relații.
Modelele cluster au o mai bună scalabili ate și performanță online față de collaborative
filtering deoarece acestea compara utilizatorul cu un număr controlat de segmente decât cu o
întreagă bază de clienți. Gruparea computațională complexă și scumpă este rulata offline. Cu
toate acestea, calita tea recomandărilor este joasă.
Modelele cluster grupează numeroși clienți împreună într -un segment, potrivesc un
utilizator cu un segment, și apoi considera toți clienții aflați în segmentul clienților similari cu
scopul de a face recomandări. Deoarece cli enții similari pe care modelele cluster le găsesc nu
sunt cei mai similari clienți, recomandările pe care le produc sunt mai puțin relevante.
Este posibil să se mărească calitatea prin folosirea a numeroase segmente cu granulație
fină, dar apoi clasificar e online utilizator – segment devine aproape la fel de scumpă ca găsirea
clienților similari folosinnd collaborative filtering.
Metode Search -Based
Metodele Search – sau content -based tratează problema recomandărilor că o căutare
pentru produsele înrudite. Fiind date produsele cumpărate de către client și clasificate de acesta,
algoritmul construiește o interogare de căutare pentru a găsi alte produse populare de la același
autor, artist, sau regizor, sau cu subiecte sau cuvinte -cheie similare. Dacă un clie nt cumpăra, spre
exemplu collectia de DVD -uri ale filmului Godfather, sistemul s -ar putea să recomande alte
titluri de film din categoria de crima -drama, alte filme în care apare Marlon Brando, sau alte
filme regizate de către Francis Ford Coppola.
Dacă ut ilizatorul are câteva achiziții sau clasificări, algoritmii search -based de
recomandare scalează și execută bine. Pentru utilizatorii cu mii de achiziții, pe de altă parte, nu
este practic să se bazeze o interogare pe toate articolele. Algoritmul trebuie s ă folosească un
subset sau rezumat al datelor, reducând calitatea. În toate cazurile, calitatea recomandărilor este
relativ slabă. Recomandările sunt adeseori prea generale (precum cele mai bine vândute titluri ale

25
DVD -urilor din categoria dramă) sau prea înguste(precum toate cărțile scrise de același autor).
Recomandările ar trebui să ajute un client să găsească și să descopere produse noi, relevante și
nu în ultimul rând interesante. Produsele populare aparținând aceluiași autor sau în aceleiași
categorii nu reușesc să îndeplinească acest scop.
Item-to-Item Collaborative Filtering
Spre deosebire de alte site -uri, Amazon.com folosește recomandările ca un instrument
ținta de marketing în multe campanii de e -mail și pe majoritatea paginilor site -urilor ale sa le,
inclusiv pagina de pornire cu trafic intens Amazon.com. Compania utilizează extensiv algoritmi
de recomandare în vederea personalizării web site -ul sau pentru interesele fiecărui client.
Deoarece algoritmii de recomandare existenți nu pot fi aplicate p entru zecile de milioane de
clienți și produse, aceștia și -au dezvoltat propriul algoritm. Acesta, denumit item -to-item
collaborative filtering, scalează seturi de date masive și produce recomandări de o calitate
superioară în timp real.În continuare vom v orbi despre cum funcționează acesta: în loc să
potrivească utilizatorul cu diferiți clienți similari, filtrarea colaborativa item -to-item potrivește
fiecare dintre achizițiile și produsele clasificate cu produse similare, apoi combina acele produse
simila re într -o listă de recomandare. Pentru a determina ce mai similară potrivire pentru un
produs dat, algoritmul construiește un tabel cu produse similare prin folosirea produselor pe care
clienții tind să le achiziționeze împreună. Am putea construi a matric e de product -to-product
iterând prin toate perechile de produse și computând un metric de similaritate pentru fiecare
pereche. Cu toate acestea, multe perechi de produse nu au niciun client comun, și prin urmare
această abordare este ineficientă din punct de vedere al timpului de procesare și folosire a
memoriei. Următorul algoritm iterativ furnizează o mai bună abordare prin calcularea
similarității dintre un singur produs s toate produsele înrudite:

Este posibil să se calculeze similaritatea dintre două produse în variate cai, dar o metodă des
folosită este aceea de a folosi măsură cosinusul, în care fiecare vector corespunde unui produs,
mai degrabă decât unui client, iar dimensiunile M ale vectorului corespund cu clienții care au
achiziționat acel produ s.
Aceasta computație offline a tabelului cu produse similare este extrem de intensiv, avem
valoarea de O(N2M) că cel mai rău caz. În practică însă, este mai aproape de O(NM), din
moment ce majoritatea clienților au doar câteva achiziții. Eșantionarea clie nților care
achiziționează titlurile cel mai bine vândute reduce timpul de exectuie chiar mai mult, cu doar
puțină reducere a calității. Fiind dat un tabel cu produse similare, algoritmul găsește produse
similare cu fiecare dintre achizițiile și clasificăr ile utilizatorului, agrega acele produse, și apoi
recomanda cele mai populare și corelate produse. Aceasta computație este foare
rapidă,depinzând numai de numărul de produse pe care utilizatorul l -a achiziționat sau clasificat.
Pentru seturi de date foarte mari, un algoritm de recomandare scalabil trebuie să
efectueze cele mai solicitante calculte offline. După cum arată o scurtă comparație, metodele
existente sunt insuficiente:
• Tradițional collaborative filtering realizează computație offline puțină sau chiar
deloc, iar computația online sclaeaza cu numărul de clienți și produsele din catalog. Algoritmul
este nepractic atunci când vine vorba de seturi de date mari, doar dacă acesta nu folosește
reducere dimensională, eșalonare sau partiționare – toate ca re reduc din calitatea recomandării
• Modelele cluster pot efectua o mare parte din calcul offline, dar calitatea
recomandării este relativ săraca. Pentru a o imbuntatii, este posibil să se crească numărul de
segmente, dar asta face ca și clasificarea uti lizator -segment să fie scumpă

26
• Modelele search -based creează cuvinte -cheie, categorii și indexele autorilor
offline, dar nu reușește să furnizeze recomandări cu titluri vizate, interesante. Acestea de
asemenea scalează slab pentru clienții cu achiziții ș i clasificări numeroase.
Cheia către scalabilitatea și performanță filtrării colaborativa item -to-item este că
generează tabelul articolelor scumpe similare offline. Componenta online a algoritmului –
căutarea produselor similare pentru achizițiile și rat ingurile clientului – scalează independent de
mărimea catalogului sau de numărul total de client; este dependenta numai de numărul de titluri
pe care utilizatorul le -a achiziționat sau clasificat. Prin urmare, algoritmul este rapid chiar și
pentru seturi de date extrem de mari. Deoarece algoritmul recomanda produse similare extrem de
corelate, calitatea recoandarilor este excelentă. Spre deosebire de tradițional collaborative
filtering, algoritmul de asemenea se comporta bine cu date limitate legate de ut ilizator,
producând recomandări de o calitate superioară bazate doar pe câteva elemente, mergând până la
două sau trei produse.
În concluzie, algoritmii de recomandare furnizează o formă eficientă de marketing
orientat prin crearea unei experiențe de cumpă rături personalizata pentru fiecare client. Pentru
marii comercianți precum Amazon.com, un bun algoritm de recomandare este scalabil pentru
baze de clienți și cataloage de produse foarte mari , necesita numai timp de procesare secundară
pentru generarea re comandărilor online, este capabil să reacționeze imediat la modificări legate
de datele unui utilizator și realizează recomandări convingătoare pentru toți utilizatorii indiferent
de numărul de achiziții și ratinguri. Spre deosebire de alți algoritmi, fil trarea colaborativa item –
to-item este capabilă să facă față acestei provocări.
În viitor este așteptat ca industria de retail să folosească în mare algoritmi de
recomandare pentru marketing orientat, atât online cât și offline. În timp ce întreprinderile de e-
commerce au cele mai ușoare vehicule pentru personalizare , ratele de conversie crescute ale
tehnologiei comparată cu abordările tradiționale pe scară largă va face de asemenea
convingătoare pentru comercianții offline folosirea în trimiterile poștal e, cupoane și alte forme
de comunicare cu clienții.

10. Analiza comentariilor
10.1 Sistemul de ordonare
Așa cum motoarele de căutare folosesc algoritmi pentru a clasifica paginile în funcție de
importanță, se va folosi un concept similar pentru a ordona comentariile. În cazul comentariilor,
relevanța se va calcula pe baza unor criterii clar definite, care vor avea o pondere proporțională
cu aportul de relevanță pe care îl aduce criteriul respectiv. În (Sierdorfer, et al., 2010) se
abordează un sistem de modelare global, la nivel de domeniu, unde pe baza unui set mare de
date se calculează o listă cu comentariile “cele mai pozitive” și „cele mai negative”, iar
comentariile nou adăugate sunt încadrate în una dintre aceste două categorii. Desigur, este un
criteriu de ordonare care reflectă reacția comunității în fața diverselor cuvinte, însă nu este o
măsură suficientă pentru sortare. O abordare mai complexă și în același timp mai promițătoare
este prezentată în (Hsu, et al., 2009), unde modelarea se face în funcție de un număr mult mai
mare de criterii care sunt atât orientate către utilizator, cum ar fi analiza autorității utilizatorului
în comunitate, analiza activității utilizatorului într -o anumită categorie, cât și criterii orientate

27
către conținut, cum ar fi lungimea, complexitatea, informativitatea, subiectivitatea și unicitatea
comentariilor. Aceste criterii sunt concentrate pe anumite subiecte, iar combinația lor creează
un criteriu general mai puternic și mai apropiat de modelul de filtrare al comuni tății
utilizatorilor. Analizând cele două clase de criterii se observă faptul că ambele dau rezultate, iar
dacă ar fi folosite simultan s -ar putea realiza o filtrare cu precizie ridicată ce poate permite
modelarea datelor într -un mod complex și apropiat de modul de gândire și filtrare al
utilizatorilor.
10.2 Reguli de ordonare
În cadrul sistemului de față ordonarea comentariilor relevante se va face în funcție de
două clase de criterii. O clasă globală care analizează un set de date arbitrar, general și
furnizează informații la nivel de comunitate despre preferințele utilizatorilor în ceea ce privește
comentariile și o clasă locală, ce ține cont de informațiile individuale ale unui produs. Pentru
clasa locală, se colectează informații privind detaliile film ărilor, cum ar fi titlul, descrierea, tag –
urile, sau numărul de vizualizări. În urma analizări gradului de acceptanță al comentariilor
(Sierdorfer, et al., 2010) s -au realizat două tabele, cu “cele mai acceptate”, respectiv “cele mai
respinse” cuvinte chei e, în funcție de voturile pe care aceastea le -au primit de la comunitate.
Criteriul principal în clasificarea globală se realizează prin filtrarea comentariilor în funcție de
reacția comunității la diferite cuvinte, ținând cont de gradul de acceptare sau d e respingere al
acestora (Sierdorfer, et al., 2010).
Ordonarea comentariilor în funcție de relevanță se calculează în două etape. În faza
inițială se aplică clasa de filtre globale care generează o ordonare rudimentară, brută, după care
intervin criteriil e locale care rafinează rezultatele. Filtrele globale funcționează similar cu
algoritmii pentru identificarea comentariilor de tip spam, pentru blog -uri, însă la o scară
simplificată (Anon., 2005). Compoziția ranking -ului general se face modularizat pentru
criteriile locale, iar în urma aplicării algoritmului pentru ranking -ul global acesta este alterat
secvențial atunci când se aplică criteriile locale. Fiecare criteriu local este caracterizat printr -un
“Coeficient de importanță”, o pondere reprezentată de o valoare numeric subunitară. În
implementarea curentă a modului de agregare a clasificării furnizate de fiecare comentariu,
ponderea fiecărui filtru este ajustată manual, însă implementarea unui calcul automat al ponderii
fiecărui filtru ar putea îmbunăt ăți semnificativ precizia rezultatelor.

28

Criteriile locale sunt modularizate, sunt adăugate sub forma unor componente (plugin –
uri) și li se poate măsura performanța în mod independent. Pe lângă “Coeficientul de
Importanță” al fiecărui criteriu acesta calc ulează pentru fiecare comentariu asociat unei filmări
propriul grad de relevanță. Așasar la nivel de comentariu, atunci când criteriul este aplicat
acesta influențează ranking -ul curent, fiind o funcție de parametrii (Coeficient de Importanță,
CommentBoost ), unde parametrul CommentBoost reprezintă ranking -ul local al criteriului, care
se aplică în ranking -ul general. Pentru ordonarea comentariilor se folosește un indicator de
relevanță, calculat de fiecare filtru și normalizat în intervalul [0,1], iar pentr u calcularea
rezultatelor agregate pentru mai multe filtre activate simultan se calculează o medie ponderată.

Rezultatele obținute pe baza aplicării criteriilor de ordonare sunt analizate la nivel de
categorie de produse, întrucât o analiză gl obală nu este la fel de relevantă deoarece intervin
aspecte sociale și culturale în funcție de categorie și zona demografică. În ceea ce privește
adaptabilitatea sistemului, au fost analizate modalități pentru a ajusta coeficientul de importanță
a fiecărui filtru individual în funcție de performanța obțiuntă prin indicatorul de Average
Precision (Manning, et al., 2008). Inițial vor fi agreate doar criterii locale, urmând ca în funcție
de performanța acestora să fie adăugate altele noi. Aceastea sunt clasifi cate în funcție de tipul
datelor pe baza cărora se face analiza. Pot fi criterii bazate pe activitatea utilizatorilor (Hsu, et
al., 2009), criterii bazate pe conținut (Sierdorfer, et al., 2010) și criterii generale care pot
combina mai multe tipuri de date , inclusiv statistici referitoare la interacțiunea generală și
informații colectate pe baza criteriilor globale.
10.3 Criterii dependente de autoritatea utilizatorului
Se presupune că relevanța comentariilor este dependentă de utilizator, de autoritatea p e
care acesta o are în cadrul comunității și de modul în care comunitatea primește sau respinge
comentariile acestuia. Așadar se poate crea un model al utilizatorului pe baza căruia putem
aplica criterii locale:
• Numărul de comentarii postate – se analizează numărul de comentarii postate de către
utilizator la nivel global cât și la nivel de categorie;
• Vechimea utilizatorului – acest criteriu ține cont de vechimea contului de utilizator;

29
• Activitatea pe categorie – se calculează procen tul de comentarii publicate la filmări din
aceiași categorie în raport cu numărul total de comentarii publicate de către utilizator. Cu cât
acesta a publicat mai multe comentarii într -un anumit domeniu se consideră că expertiza sa în
domeniul respectiv est e mai relevantă;
• Nivelul de acceptanță în comunitate – pentru fiecare utilizator se analizează modul în
care comentariile sale sunt votate de către ceilalți utilizatori. Dacă media de acceptare se
apropie de una dintre extreme (acceptat sau respin s), probabilitatea ca și comentariile care nu au
primit voturi să se îndrepte către una dintre cele două extreme este ridicată;
10.4 Criterii dependente de conținut
Această categorie de criterii locale analizează în mod exclusiv conținutul comentari ilor,
calitatea acestora și încearcă să imite modul în care utilizatori clasează comentariile din punct
de vedere cognitiv. Este cea mai importantă categorie de criterii, întrucât tratează în mod direct
aspectele emoționale, sociale care îi fac pe utilizat ori să decidă dacă un comentariu este relevant
sau nu.
• Lungimea comentariului – criteriul măsoară numărul de cuvinte conținute în comentariu;
• Complexitatea comentariului – se calculează pe baza entropiei cuvintelor din
comentariu. Pe baz a formulei de mai jos (Hsu, et al., 2009) unde pentru componenta cj cu un
număr de fiecare cuvânt are frecvența pi.

• Unicitatea conținutului – se calculează unicitatea textului unui comentariu în comparație
cu celelalte comentarii ale unui produs . Unicitatea unui comentariu ci se calculează folosind o
variație standard TFIDF (Sierdorfer, et al., 2010) (term frequency – inverse document
frequency) pentru colectarea datelor, iar gradul de unicitate al unui comentariu este dat de suma
tuturor coefici enților pentru fiecare cuvânt unic în cadrul unui comentariu, astfel:

• Gradul de apartenență la categorie – acest criteriu calculează similitudinea între alte
comentarii postate de același utilizator în alte categorii;
• Badwords – identific area comentariilor ce conțin cuvinte neadecvate folosind liste
identificate în diverse surse online.

10.5 Sistem comparativ
Sistemul comparativ are rolul de a evalua performanța fiecărui criteriu de filtrare în parte,
astfel încât, acesta permite vizuali zarea în paralel a rezultatelor pentru criteriile de filtrare
aplicate unei liste de comentarii, plus criteriul ce necesită analiza. De exemplu, dacă avem trei
criterii de filtrare deja testate și dorim adăugarea unuia nou, vom compara rezultate le după ce
au fost aplicate criteriile 1, 2 și 3, cu rezultatele pentru care s -au aplicat toate cele 4 criterii.

30
În acest mod, exista posibilitatea de a compara clar rezultatele obținute de criteriul numărul
4, iar dacă este nevoie se pot ajusta valori constante car e au fost folosite în aplicație, care, în cel
mai frecvent caz, depind de natura socială și categoria comentariilor.

31
11. Descrierea aplicației

1. Desc ărcarea de review -uri ale produselor din Amazon

Rezult ă un fișier text de 2 gb care con ține un array de fi șiere json de lungime total ă: 1.697.533.
Fiecare produs se identific ă prin ASIN , iar acesta din urm ă poate avea mai multe reviewerID -uri.
2. Inserarea înregistr ărilor în baza de date:

32

3. Crearea unui program care une ște review -urile tuturor produselor într-un singur fi șier pentru c a
acesta din urm ă să poat ă fi analizat.

Fiecare fi șier arat ă de form ă:

33

4. Găsirea unui dic ționar de cuvinte positive/negative
Pe site -ul universit ății University of Illinois at Chicago, College of Engineering am g ăsit o list ă de cuvinte
positive și negative.
5. Configurare cluster hadoop pentru procesarea datelor:

6. Rulare job hadoop

34

Output job:

7. Calculare lungime fiec ărui fi șier de output și apoi distan țele și salvarea celor mai apropiate 5 distan țe
cu formula de la pagina 19.

35

8. Creare cont pe Amazon Product Advertising API pentru a primi
AWS_ACCESS_KEY_ID
AWS_SECRET_KEY
Interogare a și salvarea informa țiilor despre fiecare produs:

9. Creare UI și afișare rezultate.
Concluzii

Proiectul combină un set de criterii pentru filtrarea comentariilor pentru a obține rezultate cât
mai relevante. Comentariile sunt slabe în metadate și din acest motiv este dificilă manipularea și
clasificarea lor. Din acest motiv este nevoie de o abordare dinamică, unde criteriile de relevanță
sunt adaptabile la o serie întreagă de parametri, cum ar fi modelul semi -local al utilizatorului,
factorii social și adaptivitatea în funcție de interacțiunea în timp.

36
Pe lângă analiza datelor interne colectate la nivel de aplicație este necesară relaționarea
datelor cu surse externe, maparea acestora cu concepte relaționate din domenii diferite, pentru a
ne putea asigura că într -adevăr recoman dările de comentarii pot fi utile pentru utilizator.
Se va efectua o analiză a comentariilor pe baza unui grup heterogen de criterii și factori
pentru a obține un grad de relevanță cât mai apropiat de rezultatele obținute prin adnotarea
manuală. În general , comentariile nu sunt documente bogate în metadate, iar pentru o obține
rezultate cât mai relevante este utilă integrarea cu servicii externe de analiză a textului, ce pot fi
folosite pentru obținerea de informații suplimentare. Totodată, utilizarea unor astfel de servicii
este consumatoare de resurse și de timp și nu este fezabilă pentru analizarea unui număr foarte
mare de comentarii atunci când există o constrângere de timp. Analiza relevanței comentariilor
presupune testarea intensivă a criteriilor/atr ibutelor de filtrare pentru un set cât mai mare și cât
mai variat de produse, iar în funcție de rezultatele obținute, trebuie să se ajusteze automat sau
manual ponderea fiecărui criteriu în calculul total al indexului de căutare.
De asemenea, pentru analiz a preliminară a comentariilor, direct din modulul de indexare și
prelucare a datelor, pentru identificarea comentariilor de tip spam, se pot folosi tehnici deja
studiate și dezvoltate pentru analiza comentariilor spam publicate pe bloguri (Kamaliha, 2008).
Ținând cont de analiza efectuată la nivel de produs, rezultatele obținute sunt relevante, iar
implementarea unei astfel de soluții în orice aplicație poate rezolva problema afișării
comentariilor relevante în cazul în care numărul de comentarii publicate depășește o anumită
limită.
În concluzie, extragerea comentariilor relevante dintr -un set foarte mare de date se poate
face folosind o gamă largă de criterii, iar performanța acestora este dependentă în mod direct de
domeniu, categoria produselor și profil ul utilizatorilor. Ținând cont de aceste aspecte, este
dificilă propunerea unei soluții general valabile pentru identificarea comentariilor relevante, însă
performanța rezultatelor poate fi maximizată selectând criteriile potrivite contextului în care se
face analiza.

Î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 na tural 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ă
și pe algoritmi de învățare. Unii dintre cei mai eficienți algoritmi de învățare a mașinilor, nu
produc rezu ltate umane de înțeles, și, deși, ele pot obține o precizie îmbunătățită, știm puține
despre cum și de ce. Cu toate 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
consumatorii produsele și servicii le 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
utilizatorilor existenți. Nevoile și provocările tehnice vor menține câmpul vibrant și plin de viață
pentru anii următori.

37

Bibliografie

http://cifr.cs.pub.ro/ullman/cluster1 -ro.pdf
http://www.ace.tuiasi.ro/users/103/2012_Agavriloaei_Ioan__PhD%20rez.pdf

38
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
http://jmcauley.ucsd.edu/data/amazon/links.html
R. He, J. McAuley. Modeling the visual evolution of fashion trends with one -class collaborative
filtering. WWW, 2016
J. McAuley, C. Targett, J. Shi, A. van den Hengel. Image -based recommendations on sty les and
substitutes. SIGIR, 2015
http://todaysoftmag.ro/article/384/neo4j -graph -database -modelarea -datelor -interconectate
http://app.robomongo.org/
https://en.wikipedia.org/wiki/MongoDB
http://db -engines.com /en/ranking
https://github.com/neo4j -examples/movies -java-spring -data-neo4j -4
http://www.tutorialspoint.com/neo4j
http://searchdatamanagement.techtarget.com/definition/MongoDB
https://en.wikipedia.org/wiki/MongoDB
https://en.wikipedia.org/wiki/Shard_(da tabase_architecture)
https://en.wikipedia.org/wiki/MapReduce
Minqing Hu and Bing Liu. "Mining and Summarizing Customer Reviews." Proceedings of the
ACM SIGKDD Interna tional Conference on Knowledge Discovery and Data Mining (KDD –
2004), Aug 22 -25, 2004, Seattle, Washington, USA .
Bing Liu, Minqing Hu and Junsheng Cheng. "Opinion Observer: Analyzing and Comparing
Opinions on the Web." Proceedings of the 14th International World Wide Web con ference
(WWW -2005), May 10 -14, 2005, Chiba, Japan.

39
Anexe

//Hadoop Map Reduce

package com.licenta.com.licenta.test;

import java.io.IOException;
import java.util.ArrayList;
import java.u til.List;
import java.util.StringTokenizer;

import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.fs.FileStatus;
import org.apache.hadoop.fs.FileSystem;
import org.apache.hadoop.fs.Path ;
import org.apache.hadoop.io.IntWritable;
import org.apache.hadoop.io.Text;
import org.apache.hadoop.mapreduce.Job;
import org.apache.hadoop.mapreduce.Mapper;
import org.apache.hadoop.mapreduce.Reducer;
import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
import org.apache.hadoop.mapreduce.lib.outpu t.FileOutputFormat;

public class WordCountMihai {

public static List<String> positiveWords = new ArrayList<String>();
public static final String OUTPUT = "/output_movies1000/" ;
public static final String INPUT = "/movies1000/" ;
//static int test = 0;

public static class TokenizerMapper extends Mapper<Object, Text, Text, IntWritable> {

private static final IntWritable ONE = new IntWritable(1);
private final Text word = new Text();

@Override
public void map( final Object key, final Text value, final Context context )
throws IOException, InterruptedException {

final StringTokenizer itr = new StringTokenizer( value .toString());

while (itr.hasMoreTokens()) {
word .set(itr.nextToken());
if(Utils. getListOfPositiveWords ().contains( word .toString().trim())){
context .write( word , ONE );
}
}
}
}

public static class IntSumReducer extends Reducer<Text, IntWritable, Text, IntWritable> {

private final IntWritable result = new IntWritable();

40
@Override
public void
reduce( final Text key, final Iterable<IntWritable> values , final Context context )
throws IOException, InterruptedException {
int sum = 0;
for (final IntWritable val : values ) {
sum += val.get();
}

//test += sum;
result .set(sum);
context .write( key, result );

}

}

public static void main( final String[] args) throws Exception {

final Configuration conf = new Configuration();

conf.set("fs.default.name" , "hdfs://192.168.0.120:10001" );
conf.set("yarn.resourcemanager .resource -tracker.address" , "192.168.0.120:8025" );
conf.set("yarn.nodemanager.localizer.address" , "192.168.0.120:10200" );
conf.set("yarn.resourcemanager.scheduler.address" , "192.168.0.120:8030" );
conf.set("yarn.resourcemanager.address" , "192.168.0.12 0:8040" );
conf.set("mapreduce.framework.name" , "yarn" );

FileSystem fs = FileSystem. get(conf);

FileStatus[] status = fs.listStatus( new Path(INPUT ));
fs.listFiles( new Path(INPUT ), false );
System. out.println( status .length );
for (int i = 0; i < status .length ; i++) {
FileStatus fileStatus = status [i];
System. out.println( fileStatus .getPath());
System. out.println( fileStatus .getPath().getName());
runJobForEveryFile (fileStatus .getPath().getName(), fs, conf);
}
}

public static void runJobForEveryFile(String fileName , FileSystem fs, Configuration conf)
throws IllegalArgumentException, IOException, ClassNotFoundException, InterruptedException{
String parts [] = fileName .split( ".txt");
fs.delete( new Path(OUTPUT + parts [0] + "/"), true);

final Job job = Job. getInstance (conf, "job");

job.setJar( "wordcount.jar" );

job.setMapperClass(TokenizerMapper. class );
job.setCombinerClass(IntSumReducer. class );
job.setReducerClass(IntSumReducer. class );
job.setOutputKeyClass(Text. class);

41
job.setOutputValueClass(IntWritable. class );
job.setJobName( "disertatie" );

FileInputFormat. addInputPath (job, new Path(INPUT + fileName ));
FileOutputFormat. setOutputPath (job, new Path(OUTPUT + parts [0] + "/"));

job.waitForCompletion( true);
}
}

// Split big file with jsons into smaller json files
import org.json.simple.JSONObject;
import org.json.simple.parser.JSONParser;
import org.json.simple.parser.ParseException;

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Stream;

/**
* Created by mmocanu on 6/1/2017.
*/
public class Main {
final static String location = "E:\\backup 04 \\Mihai_facultate \\master
an2\\disertatie \\amazon reviews \\reviews_Movies_and_TV_5.json \\";

public static void main(String[] args) {
JSONParser parser = new JSONParser();

AtomicInteger lineNo = new AtomicInteger();

try (Stream<String> stream = Files. lines(Paths.get(location +
"\\Movies_and_TV_5.json" ))) {
stream.forEach(line -> {
try {
Object obj = parser.parse(line);
JSONObject jsonObject = (JSONObj ect) obj;

String reviewText = (String) jsonObject.get( "reviewText" );
System.out.println( "reviewText: " + reviewText);
String reviewerID = (String) jsonObject.get( "reviewerID" );
System.out.println( "reviewerID: " + reviewerID);
//System.out.println(lineNo.getAndIncrement());
writeContentToFile (reviewText, reviewerID, location );

} catch (ParseException e) {
e.printStackTrace();
}
});

} catch (IOException e) {

42
e.printStackTrace();
}
}

public static void writeContentToFile(String content, String fileName, String
location) {
BufferedWr iter bw = null;
FileWriter fw = null;
try {

fw = new FileWriter(location + "\\reviewsTexts \\" + fileName + ".txt");
bw = new BufferedWriter(fw);
bw.write(content);

System.out.println( "Done");

} catch (IOException e) {

e.printStackTrace();

} finally {

try {

if (bw != null)
bw.close();

if (fw != null)
fw.close();

} catch (IOException ex) {

ex.printStackTrace();

}

}

}
}
// Distance calculator
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;
import java.util.stream.Collectors;

/**
* Created by Mihai on 6/17/2017.
*/
public class DistanceCalculator {
final static String location = "E:\\backup 04 \\Mihai_facultate \\master
an2\\disertatie \\amazon reviews \\reviews_Video_Games_5.json \\output_positi ve";
static Map<String, Float> reviewsWithLentgh = new HashMap<>();
static String review;
static float reviewLength ;

public static void main(String[] args) {
long startTime = System. currentTimeMillis ();

43

//do work
final File folder = new File(location );
listFilesForFolder (folder);
Map<String, Map<String, Float>> allDistances =
calculateDistanceForEveryFile (reviewsWithLentgh );
Map<String, Map<String, Float>> firstFiveDistances =
calculateFirs tFiveDistances (allDistances);

long stopTime = System. currentTimeMillis ();
long elapsedTime = stopTime – startTime;

int seconds = ( int) (elapsedTime / 1000) % 60 ;
int minutes = ( int) ((elapsedTime / ( 1000*60)) % 60);
System.out.println( "seconds: " + seconds);
System.out.println( "minutes: " + minutes);

}

private static Map<String,Map<String,Float>>
calculateFirstFiveDistances(Map<String, Map<String, Float>> allDistances) {

Map<String,Map<S tring,Float>> firstFiveForAll = new HashMap<>();

for (Map.Entry<String, Map<String, Float>> entry : allDistances.entrySet()) {

//order by values
Map<String, Float> result = entry.getValue().entrySet().stream()
.sorted(Map.Entry. comparingByValue (Comparator. naturalOrder ()))
.collect(Collectors. toMap(Map.Entry::getKey, Map.Entry::getValue,
(oldValue, newValue) -> oldValue, LinkedHashMap:: new));

//fetch first five
Map<String,Float> firstFiveForEach = new LinkedHashMap<>();
for (Map.Entry<String, Float> resultEntry : result.entrySet()) {
if(firstFiveForEach.size() < 5){
firstFiveForEach.put (resultEntry.getKey(),
resultEntry.getValue());
}else {
break;
}
}

firstFiveForAll .put(entry.getKey(), firstFiveForEach);

}

return firstFiveForAll ;

}

public static void listFilesForFolder( final File folder) {
for (final File fileEntry : folder.listFiles()) {
if (fileEntry.isDirectory()) {
review = fileEntry.getName();
listFilesForFolder (fileEntry);
} else {
if("part-r-00000".equals(fileEntry.getName()))
reviewLength =
readFileAndCalculateLenght (fileEntry.getAbsolutePath());
reviewsWithLentgh .put(review, reviewLength );

44
}

}
}

public static float readFileAndCalculateLenght(String fileName){
float length = 0;
try (BufferedReader br = new BufferedReader( new FileReader(fileName))) {

String sCurrentLine;

while ((sCurrentLin e = br.readLine()) != null) {
length += Integer. parseInt (sCurrentLine.split( "\t")[1]);
}

} catch (IOException e) {
e.printStackTrace();
}

return length;
}

public static Map<String, Integer> readFile(String filePath){
Map<String, Integer> values = new HashMap<>();
try (BufferedReader br = new BufferedReader( new FileReader(filePath))) {

String sCurrentLine;

while ((sCurrentLine = br.readLine()) != null) {
values.put(sCurrentLine.split( "\t")[0],
Integer. parseInt (sCurrentLine.split( "\t")[1]));
}

} catch (IOException e) {
e.printStackTrace();
}
return values;
}

public static Map<String, Integer> readFolder(File folder){
Map<String, Integer> values = new HashMap<>();
for (final File fileEntry : folder.listFiles()) {
if (fileEntry.isDirectory()) {
readFolder (fileEntry);
} else {
if("part-r-00000".equals(fileEntry.getName()))
values = readFile (fileEntry.getAbsolutePath());
}
}

return values;
}

public static float calculateScalarProduct(String firstFile , String secondFile){
float scalarProduct = 0;
final String locationFirst = "E:\\backup 04 \\Mihai_facultate \\master
an2\\disertatie \\amazon reviews \\reviews_Video_Games_5.json \\output_positive \\" +
firstFile + "\\part-r-00000";
final String locationSecond = "E:\\backup 04 \\Mihai_facultate \\master
an2\\disertatie \\amazon reviews \\reviews_Video_Games_5.json \\output_positive \\" +
secondFile + "\\part-r-00000";

Map<String, Integer> firstFileValues = readFile (locationFirst);

45
Map<String, Integer> secondFileValues = readFile (locationSecond);

for (Map.Entry<String, Integer> entry : firstFileValues.entrySet())
{
if(secondFileValues.containsKey(entry.getKey())){
scalarProduct += (entry.getValue() *
secondFileValues.get(entry.getKey()));
}
}
return scalarProduct;
}

public static Map<String, Map<String, Float>>
calculateDistanceForEveryFile(Map<String, Float> map){
Map<String, Map<String, Float>> distanceForEveryFile = new HashMap<>();
for(Map.Entry<String, Float> entry1: map.entrySet()) {
Map<String, Float> distance = new HashMap<>();
String key1 = entry1.getKey();
int hash1 = System. identityHashCode (key1);
Float value1 = entry1.getValue();
for(Map.Entry<String, Float> entry2: map.entrySet()) {
String key2 = entry2.getKey();
if (hash1 == System. identityHashCode (key2)) continue ;

Float value2 = entry2.getValue();
// compare value1 and value2;
final String locationFirst = "E:\\backup 04 \\Mihai_facultate \\master
an2\\disertatie \\amazon reviews \\reviews_Video_Games_5.json \\output_positive \\" +
key1 + "\\part-r-00000";
final String locationSecond = "E:\\backup 04 \\Mihai_facultate \\master
an2\\disertatie \\amazon reviews \\reviews_Video_Games_5.json \\output_positive \\" +
key2 + "\\part-r-00000";

float distanceInteger = 1;
if(calculateScalarProduct (key1, key2) != 0){
distanceInteger = 1 – (calculateScalarProduct (key1, key2) /
(readFileA ndCalculateLenght (locationFirst) *
readFileAndCalculateLenght (locationSecond)));

}
distance.put(key2, distanceInteger);

}
distanceForEveryFile.put(key1, distance);
}

return distanceForEveryFile;
}
}