metode de organizare a informaţiei pe web

Metode de organizare a informaţiei pe WEB

Referat de doctorat nr.1

as. univ. ing. Daniel MORARIU

coordonator: prof. univ. dr. ing. Lucian VINŢAN

Sibiu, 2005

Cuprinsul prezentării Mineritul datelor

Mineritul bazelor de date Mineritul fişierelor text Mineritul pe Web

Sisteme de descoperire şi reprezentare a informaţiilor relevante de pe Web Categorii Web (Web Directories) Reprezentarea rezultatelor căutării Monitorizarea unor pagini specificate Monitorizarea comportamentului utilizatorului Rafinarea căutării Profilul utilizator

Data mining ca o etapă (fază) în procesul de extragere de cunoştinţe

Mineritul bazelor de date Preprocesarea datelor

Ştergerea zgomotului din date Înlocuirea valorilor lipsă Filtrarea Clusterarea

Integrarea şi transformarea datelor Eliminarea redundanţelor în date Generalizarea datelor Normalizarea datelor

Selecţia şi reducerea datelor Agregarea Compresia Discretizarea şi generarea conceptului ierarhic

Mineritul bazelor de date – etape preliminare

Selecţia datelor relevante Tipul de cunoştinţe care vor fi minerite Cunoştinţele de fundal

Măsurarea gradului de interes Încrederea (local)

Susţinerea (global)

Prezentarea şi vizualizarea regulilor găsite

taining_Atuples_con_#

Both_A_and_ntaining_b_tuples_co#B)(Aconfidence

_of_tuplestotal_#

Both_A_and_ntaining_b_tuples_co#B)support(A

Mineritul bazelor de date - metode

Extragerea regulilor de asociere Algoritmul Apriori Algoritmul FP-tree

Clasificarea şi predicţia datelor Construirea modelului

Arbori de decizie Reţele neuronale

Testarea modelului Utilizarea modelului

Clusterizarea datelor Metode de partiţionare Metode ierarhice

Algoritmul Apriori

Compare the count for each items with

the threshold Scan D for count each candidate

C2 Items Sup.count

{I1,I2} 4 {I1,I3} 4 {I1,I4} 1 {I1,I5} 2 {I2,I3} 4 {I2,I4} 2 {I2,I5} 2 {I3,I4} 0 {I3,I5} 1 {I4,I5} 0

C2 Items

{I1,I2} {I1,I3} {I1,I4} {I1,I5} {I2,I3} {I2,I4} {I2,I5} {I3,I4} {I3,I5} {I4,I5}

Generate C2

Scan D for count each candidate

Compare the count for

each items with the threshold

C3 Items Sup.count

{I1,I2,I3} 2 {I1,I2,I5} 2

C3 Items

{I1,I2,I3} {I1,I2,I5}

Generate C3

Scan D for each candidate

Compare the count for each items with the

threshold

C1 Items Sup.count {I1} 6 {I2} 7 {I3} 6 {I4} 2 {I5} 2

L1 Items Sup.count {I1} 6 {I2} 7 {I3} 6 {I4} 2 {I5} 2

L3 Items Sup.count

{I1,I2,I3} 2 {I1,I2,I5} 2

L2 Items Sup.count

{I1,I2} 4 {I1,I3} 4 {I1,I5} 2 {I2,I3} 4 {I2,I4} 2 {I2,I5} 2

Algoritmul FP-Tree

Item Support Node link I2 7 I1 6 I3 6 I4 2 I5 2

I3:2

I1:2 I2:7

I4:1 I3:2 I1:4

I4:1 I3:2 I5:1

I5:1

Null{}

Mineritul bazelor de date - metode

Extragerea regulilor de asociere Algoritmul Apriori Algoritmul FP-tree

Clasificarea şi predicţia datelor Construirea modelului

Arbori de decizie Reţele neuronale

Testarea modelului Utilizarea modelului

Clusterizarea datelor Metode de partiţionare Metode ierarhice

Evaluarea metodelor de data mining

Criterii Acurateţea Viteza de procesare Robusteţea Scalabilitatea Interpretabilitatea

Mineritul fişierelor text - etape preliminare

Mineritul bazelor de date – date structurate Mineritul fişierelor text – date ne/semi-structurate

Măsuri folosite Precizie regăsite – proporţia de documente

relevante găsite din documentele găsite

Precizie relevante - proporţia de documente relevante găsite din total de documente relevante

Retrieved

RetrievedRelevant precision

Relevant

RetrievedRelevant recall

Mineritul fişierelor text - metode

Similarităţi bazate pe cuvinte cheie Probleme: sinonime, polisemie Crearea vectorului ataşat documentului

Extragerea rădăcinii cuvântului Eliminarea cuvintelor de legătură

Determinarea similarităţii

Asocieri bazate pe cuvinte cheie Găsire de reguli de asociere Asociere între termeni şi cuvinte cheie

21

2121

,),(

vv

vvvvsim

Mineritul pe Web

Mineritul conţinutului Mineritul textului şi al tagurilor

(metainformaţii) Mineritul structurii

Mineritul link-urilor web Paginile web autoritare şi hub-urile

Mineritul utilizării Mineritul fişierelor log

Mineritul structurii web – metrici utilizate

PageRank

HITS – Hyperlink induced topic search

p)q such that (q

qp ha

p)q such that (q

qp ah

vu uOutDegree

uPageRankp

N

pvPageRank

)(

)()1()(

Sisteme de descoperire şi reprezentare a informaţiilor

Necesitate Imensitatea informaţiilor de pe Web Incapacitatea utilizatorului de a formula

interogări corecte Organizarea nesatisfăcătoare a

rezultatelor Accesibilitatea greoaie a interfeţelor

Sisteme de descoperire şi reprezentare a informaţiilor(2)

Criterii de evaluare

Aranjarea componentelor

Numărul de elemente Gradul de expresivitate Funcţionalitate Gruparea rezultatelor

Naturaleţe

Cantitate Atracţie Comoditate Intuitivitate

Categorii Web (Web Directories)

Reprezentare ierarhică creată static

Organizare după domenii de interes (topicuri)

Uşor de înţeles pentru utilizator Structură fixă Actualizare

Manuală Semi-automată

Reprezentarea ierarhică a rezultatelor

Reprezentarea ierarhică creată dinamic Algoritm monothetic – foloseşte o singură

trăsătură Algoritm polythetic – foloseşte trăsături multiple

Evaluarea ierarhiei (taxonomiei) Acoperirea documentelor (acurateţea

taxonomiei) Integritatea şi disjunctivitatea claselor Etichetarea sugestivă a nodurilor Timpul mediu de localizare a informaţiei Organizare de la general la specific

Reprezentare grafică a rezultatelor

Tendinţă de trecere la reprezentarea 3D

Avantaje Lărgirea dimensiunii de reprezentare Naturaleţea utilizării Intuitivitatea

Cerinţe Mod natural, intuitiv de reprezentare Posibilitatea de navigare Posibilitatea de interacţiune cu conţinutul

Monitorizarea unei pagini specificate

Agentul DICA – “Do-I-Care” Periodic analizează pagina Identifică modificările Evaluează relevanţa modificărilor Notifică utilizatorul Utilizează feedback-ul Permite schimb de informaţii între

agenţi

Agentul “GrantLearner”

Monitorizarea unei pagini specificate (2)

Agentul “Syskill & Webert” Crearea profilului utilizator Crearea interogării

Cuvinte care apar în documentele interesante

Cuvinte care diferenţiază documentele interesante de cele neinteresante

Analizarea paginilor Efectuarea de recomandări

Monitorizarea comportamentului utilizatorului

Creare profilului utilizator

Detectarea documentelor relevante Analiza textului fişierului HTML Numărare de hyperlinkuri utilizate Activitatea utilizatorului pe acea

pagină (scrolling şi mouse)

Găsirea de noi documente posibil relevante

Rafinarea căutării Îngustarea domeniului de căutare

Sinonime Manual Automat

Domenii posibile Tipuri de pagini

Detecţia de noi cuvinte posibile

Ex: Agentul “WebMate” Învăţarea incrementală a intereselor Ajută utilizatorul în rafinarea căutării

Profilul utilizatorului

Profil static – neactualizat la timp Profil dinamic – reactualizat continuu

în mod automat Crearea profilului – ţine cont de:

Profilul iniţial Acţiunile utilizatorului Interpretarea semantică a interogării

Actualizarea profilului – în raport cu: Interesul curent al utilizatorului Decăderea interesului în timp

Profilul utilizatorului (2)

Creare de grupuri de utilizatori pe baza documentelor utilizate

Metode Filtru bazat pe context – clasifică documente

noi (nevizitate) pe baza asemănării Filtru colaborativ – clasifică pe baza

specificaţiilor făcute de ceilalţi utilizatori Învăţarea colaborativă de ansamblu – hibrid

CBF – crearea profilului utilizator CF – gruparea preferinţele utilizatorilor

Direcţii actuale de cercetare

Reorganizarea Web-ului Web-ul semantic - trecerea de la orientarea

pe documente la orientarea pe date relevante

Reorganizarea vizualizării Web-ului din punctul de vedere al utilizatorului

Găsirea informaţiilor relevante Reprezentarea rezultatelor Ghidarea utilizatorului în găsirea

informaţiilor

Intenţii de viitor

Extragerea trăsăturilor caracteristice folosind frecvenţa cuvintelor

Selecţia trăsăturilor caracteristice Clasificare utilizând tehnici bazate

pe vectori suport (SVM) Clusterare utilizând tehnici bazate

pe vectori suport (c-SVM)

metode de organizare a informaţiei pe web

Documents