Babeş-bolyai university of cluj-napoca

UNIVERSITATEA BABEŞ-BOLYAI CLUJ-NAPOCA

FACULTATEA DE MATEMATICǍ ŞI INFORMATICǍ

SPECIALIZAREA INFORMATICĂ

LUCRARE DE DIPLOMǍ

Sisteme de recomandare multi-agent

Conducător științific

Prof. univ. dr. Gabriela Czibula

Absolvent

Paul Colcer

2014

CUPRINS

INTRODUCERE 5

CAPITOLUL I 9

Sisteme de recomandare 9

1.1 Ce sunt sistemele de recomandare? 9

1.2 Avantajele sistemelor de recomandare 10

1.3 Principalele componente 14

CAPITOLUL II 17

Agenți inteligenți și sisteme multi-agent 17

2.1 Ce sunt agenții? 17

2.1.1 Structura unui agent 18

2.1.2 Agenți inteligenți 19

2.1.3 Utilizări ale agenților 21

2.2 Sisteme multi-agent 22

2.2.1 Comunicarea în sistemele multi-agent 23

2.2.1.1 Performative 24

2.2.1.2 Ontologii 24

2.2.1.3 Knowledge Query and Manipulation Language (KQML) 24

2.2.1.4 Foundation for Intelligent Physical Agents (FIPA) 25

2.2.1.5 Sisteme Blackboard 26

2.3 Limbaje de programare pentru agenți 27

2.3.1 Programarea orientă agent (POA) 27

2.3.2 Limbaje de programare orientate agent 28

2.3.2.1 Agent0 28

2.3.2.2 Jack Intelligent Agent 29

2.3.2.3 Open Agent Architecture 30

2.3.3 Java Agent Development Framework (JADE) 31

2.3.3.1 Arhitectura JADE 31

2.3.3.2 Instrumente JADE 32

2.3.3.2.1 Remote Monitoring Agent 32

2.3.3.2.2 The Dummy Agent 32

2.3.3.2.3 The Sniffer Agent 33

2.3.3.2.4 The Introspector Agent 33

2.3.3.3 Funcționalități JADE 34

2.3.3.3.1 Crearea agenților 34

2.3.3.3.2 Comportamentul agenților 34

2.3.3.3.3 Comunicarea agenților 36

2.3.3.3.4 Serviciul ”Pagini Aurii” 36

CAPITOLUL III 37

Tehnici utilizate în dezvoltarea sistemelor de recomandare 37

3.1 Tehnici de recomandare 37

3.2 Algoritmi și clasificări 39

3.2.1 Algoritmul aleatoriu (Random Algorithm) 40

3.2.2. Mean Algorithm 40

3.2.3 User-based Nearest Neighbors Algorithm 40

3.2.3 Item-based Nearest Neighbors Algorithm 42

3.4 Evaluarea sistemelor de recomandare 42

3.4.1 Abordări de evaluare 43

3.4.1.1 Metoda off-line 43

3.4.1.2 Evaluarea on-line 43

3.4.2 Metrici de acuratețe 43

3.4.3 Acoperirea 44

3.4.4 Satisfacția utilizatorilor 44

3.5 Sisteme de recomandare existente 45

3.5.1 Amazon.com 45

3.5.2 MeeVee 47

3.5.3 TiVo 47

3.5.4 Alte sisteme de recomandare 48

3.5.5 Biblioteci software open-source 48

CAPITOLUL IV 50

MovieRightAway – Un sistem de recomandare al filmelor si serialelor 50

4.1 Enunțul problemei 50

4.2 Abordarea propusă. Arhitectura sistemului și rolul agenților 51

4.3 Analiză și proiectare 54

4.3.1 Tehnologi utilizate 54

4.3.2 Diagramă de clase 56

58

4.3.3 Diagrama cazurilor de utilizare 61

4.4 Manual de utilizare 61

4.5 Rezultate experimentale și extinderi posibile 64

Concluzie 67

BIBLIOGRAFIE 68

INTRODUCERE

În prezent, cantitatea informației disponibilă utilizatorilor este nelimitată fiind într-o continuă creștere. Navigarea prin toate elementele pentru a decide dacă acestea sunt utile sau nu este aproape imposibil, astfel depistarea elementelor relevante devine o sarcină din ce în ce mai dificilă. Există o multitudine de situații în care sunt prea multe opțiuni de alegere. Să presupunem că doriți să achiziționați o carte de la o librărie on-line care vinde milioane de titluri. Deoarece nu sunteți familiarizat cu majoritatea titlurilor, nu puteți decide dacă un articol v-ar plăcea sau nu, dar cu siguranță dintre toate aceste cărți trebuie să existe o copie de care să vă bucurați. Găsirea acestui articol prin navigarea a milioane de titluri oferite de librărie este aproape irealizabil, cu atât mai mult din moment ce, probabil, nu puteți judeca relevanța elementului fără al examina mai întâi. Această problemă este similară cu găsirea produselor relevante precum: CD-uri, programe TV, fișiere MP3, filme, articole de știri, documente, rezultate din interogări de căutare și multe altele. Popularitatea tot mai mare a conținutului introdus de utilizator cum ar fi video-clipurile de pe YouTube, fotografii pe Facebook și înregistrările blogurilor, se adaugă la o creștere continuă a conținutului disponibil în rețeaua Internet.

În scopul de a depăși această așa-numită problemă ”information overload”, în mijlocul anilor 1990, cercetătorii au început investigarea sistemelor de recomandare. Un sistem de recomandare folosește cunoștințele despre preferințele utilizatorului (și ale altora), cu scopul de a recomanda un produs pe placul acestuia. Utilizatorii pot oferi un feedback pentru obiectele cu care aceștia sunt familiarizați, și sistemul de recomandare va utiliza aceste informații în scopul de a prezice preferința acestora pentru elementele încă nevăzute, ulterior recomandând elemente cu relevanță ridicată.

Multe aplicații comerciale on-line, precum și alte aplicații includ sisteme de recomandare în scopul de a oferi servicii personalizate și pentru a impulsiona vânzările lor. Câteva exemple populare includ Amazon.com, Netflix, Last.fm, MyStrands și iTunes.

Din moment ce fiecare utilizator are preferințe și criterii specifice referitoare la proprietățile care determină relevanța unei entități, sistemele de recomandare ar trebui să ofere recomandări personalizate. De obicei, preferințele pot fi privite ca un complex, un amestec de criterii în continuă schimbare (de exemplu, influențe din partea prietenilor sau experiențe noi). Mai mult decât atât, noi surse de date, furnizând informații relevante, pot deveni disponibile. Astfel design-ul sistemului de recomandare ar trebui să sprijine integrarea de noi strategii și sa fie capabil să se adapteze în mod constant pentru a schimba preferințele utilizatorului.

Problema adaptării web-ului nu este nouă. Sistemele de recomandare au suferit o serie de îmbunătățiri în ultimul deceniu. Una dintre soluțiile actuale care sunt propuse pentru această problemă este utilizarea agenților autonomi. Sistemele multi-agent sunt un domeniu de cercetare care a fost dezvoltat, în mare, pe parcursul ultimului deceniu, și deține anumite caracteristici speciale care se potrivesc acestei probleme. De fapt, utilizarea unei abordări multi-agent a fost deja propusă, datorită flexibilității sale și capacității de a se adapta dinamic la nevoile aplicațiilor web. Mai mult decât atât, sistemele multi-agent sunt deja utilizate pentru extragerea și actualizarea automată a informațiilor din website-uri. O propunere arhitecturală al unui astfel de sistem de recomandare folosind această abordare a fost deja propusă în [28].

În această lucrare vom prezenta un sistem de recomandare multi-agent pentru filme și seriale TV, unde diferiți algoritmi de recomandare au fost utilizați pentru a crește probabilitatea de a oferi recomandări calitative pentru utilizatori. O tehnică bazată pe filtrarea prin colaborare este aplicată regăsind astfel cei mai populari algoritmi în acest sens: user-base nearest neighbors algorithm și item-base nearest neighbors algorithm. De asemenea, pentru așa cunoscuta problemă de ”cold start” un algoritm hibrid a fost dezvoltat utilizând la bază algoritmii Random și Mean (Average). Rolul agenților în acest sistem este de a asista acest întreg proces. Pornind de la agentul personal al utilizatorului, care preia cererile acestuia, informațiile circulă spre un agent global numit coordonator, care mai apoi interoghează agentul sistemului de recomandare cu scopul de a oferi recomandări înapoi. În acest sens mai mulți agenți care preiau informații de pe Internet au fost adăugați acestei arhitecturi, aceștia ocupându-se strict de căutarea informațiilor despre seriale și filme. Acest proces al căutării și preluării informației utilizând așa numitele web crawler-re este cunoscut sub numele de data mining.

Spre o mai bună înțelegere a tehnicilor și algoritmilor utilizați, capitolele următoare vor introduce o scurtă descriere în acest domeniu. Lucrarea este structurată în patru capitole, două dintre acestea fiind orientate spre sistemele de recomandare, unul pentru agenți inteligenți și sisteme multi-agent, iar cel de-al patrulea reprezintă descrierea aplicației MovieRightAway – un sistem de recomandare pentru filme și seriale TV. Vom oferi în cele ce urmează o scurtă descriere pe capitole.

Capitolul unu prezintă o scurtă istorie și descriere a sistemelor de recomandare, ce sunt acestea, care este scopul și motivul abordării acestor de sisteme în aplicații. Se prezintă câteva avantaje ale utilizării, atât din punct de vedere al celor care oferă aceste servicii cât și din punct de vedere al celor care le utilizează. Ultimul subcapitol pune accentul pe principalele elemente fără de care un astfel de sistem nu ar putea fi conceput.

În capitolul doi este oferită o descriere a structurii și utilizării agenților inteligenți. O scurtă prezentare a sistemelor multi-agent și câteva aspecte ale comunicării agenților sunt abordate în subcapitolul ce urmează. Spre finalul acestui capitol sunt descrise câteva dintre cele mai populare limbaje de programare orientate agent, paradigma programării orientate pe agent și un framework pentru agenți care este utilizat la implementarea aplicației descrise în capitolul patru.

Capitolul trei pune în evidență câteva tehnici utilizate în dezvoltarea sistemelor de recomandare, un mod de evaluare a acestor sisteme și o scurtă prezentare a câtorva sisteme de recomandare existente.

În ultimul capitol al acestei lucrări vom aborda aplicația propusă. Acesta prezintă tema problemei, decizii de implementare, câteva dintre cele mai importante tool-uri utilizate în dezvoltare cât și viitoare îmbunătățiri ce pot fi aduse acestei aplicații.

CAPITOLUL I