VALUTAZIONE DELLA QUALITA’ DI UN DATASET

SPERIMENTANDO TRE DIVERSI METODI DI SIMILARITA’

RELATORE: CANDIDATO:SONIA BERGAMASCHI FRANCESCO RIZZO

10/12/2014

&

Sviluppo sistema iTag

1

Descrizione del progetto

Studio del sistemaImplementazione similarità

Valutazione qualità

OVERVIEW Per cominciare: Cos’è un tag? Cosa si intende per similarità? Perchè la pulizia dei dati?

Presentazione del sistema iTag Ricerca effettuata Breve descrizione del dataset Implementazione dell’algoritmo di qualità

Pulizia del dataset Calcolo delle frequenze e del punto di

stabilità Implementazione della strategia ottima

Risultati sperimentali Conclusioni Sviluppi futuri

Cos’è un tag?PER COMINCIARE

Un tag è un’etichetta. Può essere assegnata a una risorsa qualsiasi:

IMMAGINI

VIDEO

SITI WEB

2

OVERVIEW Per cominciare: Cos’è un tag? Cosa si intende per similarità? Perchè la pulizia dei dati?

Presentazione del sistema iTag Ricerca effettuata Breve descrizione del dataset Implementazione dell’algoritmo di qualità

Pulizia del dataset Calcolo delle frequenze e del punto di

stabilità Implementazione della strategia ottima

Risultati sperimentali Conclusioni Sviluppi futuri

Cosa si intende per similarità?

PER COMINCIARE

“Affinità di natura, struttura o composizione.”

(De Mauro “Il dizionario della lingua italiana”)In informatica, la similarità viene implementata

attraverso il concetto matematico di DISTANZA

3

OVERVIEW Per cominciare: Cos’è un tag? Cosa si intende per similarità? Perchè la pulizia dei dati?

Presentazione del sistema iTag Ricerca effettuata Breve descrizione del dataset Implementazione dell’algoritmo di qualità

Pulizia del dataset Calcolo delle frequenze e del punto di

stabilità Implementazione della strategia ottima

Risultati sperimentali Conclusioni Sviluppi futuri

Perchè la pulizia dei dati?PER COMINCIARE

PERCHÈ si effettua la pulizia? Molto spesso i dati sono

INCOMPLETI

INCONSISTENTI

RUMOROSI

Passi principali:

• Pulizia: levigare il rumore nei dati, risolvere le inconsistenze• Integrazione: più fonti eterogenee vengono unite• Riduzione: diminuire il volume del dataset

FONTI ETEROGENEE

4

OVERVIEW Per cominciare: Cos’è un tag? Cosa si intende per similarità? Perchè la pulizia dei dati?

Presentazione del sistema iTag Ricerca effettuata Breve descrizione del dataset Implementazione dell’algoritmo di qualità

Pulizia del dataset Calcolo delle frequenze e del punto di

stabilità Implementazione della strategia ottima

Risultati sperimentali Conclusioni Sviluppi futuri

piattaforma online che favorisce il contributo degli utenti dietro incentivo economico

sistema di social bookmarking

Concetti di base di iTagiTAG

RISORSA

DATASET

POST

DELICIOUS

CROWDSOURCING

insieme di tag dati di una risorsa

elemento taggato (foto, video, sito web)

insieme di risorse, ognuna con i suoi post

5

Scopo di iTagiTAG

Ogni risorsa alla quale è possibile applicare tag può risultare:

• Sovrataggata (per le più popolari)

• Sottotaggata

In questo modo quando unutente effettua una ricerca

Non tutte le risorse vengonomostrate ricerca inefficiente

6

Aumentare la QUALITA’ del dataset

Sistema iTagiTAG

DATASET

iTAG CREA I LAVORI

VIENE CONSEGNATO L’INCENTIVO

LAVORO COMPLETATO

CROWDSOURCING

i-Tag

MOTORE DI INCENTIVI 7

OVERVIEW Per cominciare: Cos’è un tag? Cosa si intende per similarità? Perchè la pulizia dei dati?

Presentazione del sistema iTag Ricerca effettuata Breve descrizione del dataset Implementazione dell’algoritmo di qualità

Pulizia del dataset Calcolo delle frequenze e del punto di

stabilità Implementazione della strategia ottima

Risultati sperimentali Conclusioni Sviluppi futuri

Scopo della ricercaRICERCA

I passi sono stati:

• Analizzare iTag

• Cercare aspetti da migliorare

• Ho fatto alcune proposte:

Similarità

Feedback

Differenziazione incentivi

8

Argomento approvato:

Il mio contributoRICERCA

Le tre misure di similarità che ho scelto sono state:

Similarità del Coseno

Coefficiente di Dice

Similarità di Jacquard

9

OVERVIEW Per cominciare: Cos’è un tag? Cosa si intende per similarità? Perchè la pulizia dei dati?

Presentazione del sistema iTag Ricerca effettuata Breve descrizione del dataset Implementazione dell’algoritmo di qualità

Pulizia del dataset Calcolo delle frequenze e del punto di

stabilità Implementazione della strategia ottima

Risultati sperimentali Conclusioni Sviluppi futuri

Informazioni sul datasetDATASET

Fonte: Delicious

Inizialmente i files, relativi ad 1 mese di utilizzo,

erano 4 da circa 10 GB ciascuno (40GB totali)

Dopo le operazioni di pulizia e filtraggio del dataset,

le dimensioni si sono ridotte a 100MB10

Struttura del dataset (Delicious)

DATASET

Per ogni risorsa, la prima cifra

rappresenta il numero di post

Le cifre dentro al post rappresentano l’ID

del tagPer ogni post, la prima cifra rappresenta il

numero di tag dentro al post

Ogni linea è una risorsa

129

8

7

6 5

4

3

“viaggi”11

OVERVIEW Per cominciare: Cos’è un tag? Cosa si intende per similarità? Perchè la pulizia dei dati?

Presentazione del sistema iTag Ricerca effettuata Breve descrizione del dataset Implementazione dell’algoritmo di qualità

Pulizia del dataset Calcolo delle frequenze e del punto di

stabilità Implementazione della strategia ottima

Risultati sperimentali Conclusioni Sviluppi futuri

finestra (quantità di post) utilizzata per valutare la stabilità

vettore di frequenze relative di ogni tag

Concetti di base del mio contributo

ALGORITMO

STABILITÀ

w

QUALITÀ

RFD

DP

B

si ha quando il livello di informazioni per la risorsa è sufficiente

si ha quando le informazioni della risorsa superano la soglia di stabilità

algoritmo ottimo per generare gli assegnamenti delle risorse

Budget stanziato dal provider per l’incremento della qualità12

Circa 1TBspaghettispaghetti

Guardiamo i seguenti tag:

1) Pulizia del datasetALGORITMO

4 X 10GB 100 MB

RUMOROSO

RIDONDANTE

TROPPO GRANDE

PULITOFORMATTATO

RIDOTTO

DATASET ORIGINALE

RUMORE: DATI SPORCHI

Circa 40GB 1 mese2 anni

Guardiamo i seguenti tag:

QUESTO E’ IL RUMORE

RIDONDANZA: DATI RIPETUTIr4sa334

sidofhbdjnopf

3dfasgg5

pasta

cucina

ricetta

cucina

cucina

pasta

pasta

spaghetti

QUESTA E’ LA RIDONDANZA

RIDUZIONE RUMORE

RIDUZIONE RIDONDANZA

13

CARATTERISTICHE:

OVERVIEW Per cominciare: Cos’è un tag? Cosa si intende per similarità? Perchè la pulizia dei dati?

Presentazione del sistema iTag Ricerca effettuata Breve descrizione del dataset Implementazione dell’algoritmo di qualità

Pulizia del dataset Calcolo delle frequenze e del punto di

stabilità Implementazione della strategia ottima

Risultati sperimentali Conclusioni Sviluppi futuri

2) Calcolo rfd e punti di stabilità

ALGORITMO

APPLICAZIONE

FORMULE STATISTICH

E

DATASET PULITO

RFD

INPUTOUTPUT

Punto di

stabilità

14

OVERVIEW Per cominciare: Cos’è un tag? Cosa si intende per similarità? Perchè la pulizia dei dati?

Presentazione del sistema iTag Ricerca effettuata Breve descrizione del dataset Implementazione dell’algoritmo di qualità

Pulizia del dataset Calcolo delle frequenze e del punto di

stabilità Implementazione della strategia ottima

Risultati sperimentali Conclusioni Sviluppi futuri

3) L’algoritmo DPALGORITMO

DP

RFD

Punto di

stabilità

INPUT OUTPUT

Qualità del

dataset

ASSIGNMENTASSIGNMENTASSEGNAMEN

TO OTTIMO

BUDGET

STATO INIZIALE (RANDOM)

15

OVERVIEW Per cominciare: Cos’è un tag? Cosa si intende per similarità? Perchè la pulizia dei dati?

Presentazione del sistema iTag Ricerca effettuata Breve descrizione del dataset Implementazione dell’algoritmo di qualità

Pulizia del dataset Calcolo delle frequenze e del punto di

stabilità Implementazione della strategia ottima

Risultati sperimentali Conclusioni Sviluppi futuri

Analisi assegnamentiRISULTATI

COSINE DICE JACQUARD

COME POSSIAMO VEDERE, GLI ASSEGNAMENTI SONO DIVERSI...

... COME VARIA QUINDI IL COMPORTAMENTO DEI GRAFICI?

16

Punto di stabilità al variare di w

RISULTATI

17

Qualità vs Budget (w = 4)RISULTATI

18

Qualità vs Budget (w = 6)RISULTATI

19

Qualità vs Budget (w = 10)RISULTATI

20

Qualità vs Budget (w = 15)RISULTATI

21

Qualità vs finestra (B = 200)

RISULTATI

22

Qualità vs finestra (B = 500)

RISULTATI

23

Andamento qualità per Budget piccoli

RISULTATI

24

OVERVIEW Per cominciare: Cos’è un tag? Cosa si intende per similarità? Perchè la pulizia dei dati?

Presentazione del sistema iTag Ricerca effettuata Breve descrizione del dataset Implementazione dell’algoritmo di qualità

Pulizia del dataset Calcolo delle frequenze e del punto di

stabilità Implementazione della strategia ottima

Risultati sperimentali Conclusioni Sviluppi futuri

ConclusioniOsservando i risultati sperimentali è possibile vedere

come i risultati in valore assoluto siano simili per quanto riguarda Coseno e Dice, mentre siano diversi per la Jacquard.

Dopo aver analizzato i risultati sperimentali, è possibile affermare che per il sistema analizzato non è presente una misura di similarità migliore delle altre, ma sono tutte e tre equivalenti.

Infatti è interessante notare come, nonostante gli assegnamenti varino da misura a misura, le curve abbiano esattamente lo stesso comportamento, ottenendo alla fine gli stessi valori di qualità.

Il mio contributo è stato apprezzato, verrà introdotto in un’estensione del paper “On incentive-based tagging” (ICDE 2013).

25

OVERVIEW Per cominciare: Cos’è un tag? Cosa si intende per similarità? Perchè la pulizia dei dati?

Presentazione del sistema iTag Ricerca effettuata Breve descrizione del dataset Implementazione dell’algoritmo di qualità

Pulizia del dataset Calcolo delle frequenze e del punto di

stabilità Implementazione della strategia ottima

Risultati sperimentali Conclusioni Sviluppi futuri

Sviluppi futuri Effettuare i test anche con le altre strategie di assegnamento

Scelta libera Round Robin Less Posts first Most Unstable first Ibrida

Indirizzare l’utente verso le risorse che più si addicono al suo profilo

Implementare un sistema di feedback

Generare un sistema di riconoscimento semantico dei tag

26

GRAZIE - THANK YOU - 謝謝