D2I - Tema 3: Data Mining

Stato di avanzamento

Roma 13/11/2001

D2I - Tema 3 2

Argomenti

D3R3 Ricerche di similarità e approssimate

Paolo Ciaccia, Marco Patella

Clustering di dati metrici Stefano Lodi, Claudio Sartori

Rule learning Giovambattista Ianni, Luigi Palopoli

D3R2 Architettura e Tecniche di visualizzazione

Tiziana Catarci, Giuseppe Santucci

D2I - Tema 3 3

Ricerche di similarità approssimate

Problema di base: trovare efficientemente oggetti “simili” a uno dato Essenziale per DM interattivo/esplorativo

ricerche esatte spesso troppo costose …e/o non necessarie (qual è la “giusta” query?)

Idea generale: rilassare uno o più vincoli del problema 3 Approcci generali (rif. D3.R1):

Trasformare lo spazio (eg: dimensionality reduction) Non è una generalizzazione delle ricerche esatte (ancora utili!)

“Scartare” alcuni oggetti sulla base di euristiche e/o bound sull’errore ammesso

Utile anche per scartare sotto-alberi se si usano indici Bound deterministici: si dimostra che sono inefficaci in “spazi complessi”

(intrinseca elevata dimensionalità)

D2I - Tema 3 4

L’approccio PAC

Originariamente proposto per 1-NN queries (Ciaccia, Patella ICDE 2000) Usa un bound con garanzie probabilistiche Generalizzazione:

Sia q una v.a. le cui realizzazioni sono specifici query point q, e Res(q) il risultato esatto di q

Sia A un algoritmo che per una query q restituisce il risultato (approssimato) appr-Res(q)

Sia ERR una funzione (errore) di Res(q) e appr-Res(q) E.g.: ERR = d(q,appr-nn1(q))/d(q,nn1(q)) - 1 ≥ 0

dove nn1(q) è il NN di q, e appr-nn1(q) il NN restituito da A per q

A è un algoritmo PAC (Probably Approximately Correct) sse per ogni ≥ 0 e [0,1) risulta

Pr{ERR > } ≤

D2I - Tema 3 5

Come garantire la qualità del risultato

Scenario generale: spazi metrici Informazione di base: distribuzione delle distanze dei query point:

F(x) = Pr{d(q,p) ≤ x} Tipicamente, query point distribuiti come i data point (ma non sempre)

Informazioni derivate: distribuzioni delle distanze dei NN:

Pi(x) = Pr{d(q,nni(q)) ≤ x}

E.g.: per ERR definito precedentemente:

A è PAC sse per ogni query q A si ferma quando trova un punto p tale che

d(q,p) ≤ (1P1-1

D2I - Tema 3 6

Risultati ottenuti

Generalizzazione (modificando ERR) a query k-NN e di range Definizione degli algoritmi PAC sequenziali e per M-tree (validi anche per

altri indici ad albero) e parziale implementazione Estensione al caso in cui informazione “locale” su statistiche di q viene

mantenuta per un subset dei nodi dell’albero

Risultati formali: Determinazione dello schedule ottimale (in media) per la lettura dei

nodi dell’albero Dimostrazione che tale schedule coincide con quello ottimale

(MinDist) per ricerche NN esatte (= = 0)

Attività in corso Implementazione e analisi sperimentale Sviluppo di un modello di costo per la predizione delle prestazioni

(costo vs errore)

D2I - Tema 3 7

Clustering di dati metrici

con stime di densità con dati dinamici

D2I - Tema 3 8

Stime di densità

Funzione di influenza Uniforme: f y (x) = 1, se d(x,y), 0 altrimenti Gaussiana: f y (x) = exp[- d(x,y)2/(22)]

Stimatore puntuale della densità come somma delle funzioni di influenza di ciascun punto: f D (x) = yD f y (x)

Lo stimatore è immediatamente utilizzabile nel caso metrico. Costruzione di una foresta orientata.

(x,y)E y = NN(x,{yD : f D (x) < f D (y)}). Le componenti connesse della foresta sono i cluster della

soluzione.

D2I - Tema 3 9

Clustering statico di dati metrici/categorici

Trasformazione della funzione similarità/dissimilarità originaria. La trasformazione considera solo l’intorno di ogni coppia di punti. Vicini condivisi:

• (x,y) = k-| NNQk(x,D) NNQk(y,D) |. Rango dei vicini:

• (x,y) = ran(x,y,D) + ran(y,x,D). Media di densità stimate:

• (x,y) = 0.5 [dk(x) + dk(y)] Clustering sulle dissimilarità trasformate secondo funzioni

obiettivo (soluzione esatta o approssimata, secondo la complessità del problema)

D2I - Tema 3 10

Clustering dinamico di dati metrici/categorici

Algoritmi fully dynamic (inserimenti e cancellazioni) INPUT: insiemi +, - di oggetti inseriti e cancellazione di oggetti

nel data set D, clustering di D. OUTPUT: nuovo clustering di D \ - +. Tecnica:

Generazione di un insieme di operazioni di inserimento, cancellazione, aggiornamento dei pesi nel grafo delle dissimilarità trasformate

Aggiornamento del clustering secondo la funzione obiettivo scelta

Massimizzazione del peggiore (minimo) split: Aggiornamento componenti connesse/MST del grafo (Frederickson, 1985).

Minimizzazione del peggiore (maggiore) diametro (Charikar et al., 1997).

Massimizzazione del peggiore (minimo) cut. ...

D2I - Tema 3 11

Stato di avanzamento

Clustering di dati metrici con stima di densità prototipo in fase di test di qualità (implem.

memoria centrale) Clustering statico con trasformazione funzione

implementata versione memoria esterna con campionamento

Clustering dinamico algoritmi proposti + implementazione in corso

D2I - Tema 3 12

Ongoing work - Università della Calabria

Rule Learning Metaquerying Association rules

D2I - Tema 3 13

Metaquerying

Ricerca di correlazioni relazionali in basi dati Usi: genetica, telecomunicazioni, ecc.

Esempio patente_sospesa(X) P(X,Y),Q(X,Z)

Possibile risposta:patente_sospesa(X) assicurato(X,classe > 14),auto(X,km > 50000).

Confidenza = 70% : Il 70% dei guidatori che soddisfano le due condizioni sulla parte destra

della regola fanno parte della tabella patente_sospesa.

D2I - Tema 3 14

MetaqueryingRisultati Ottenuti

Formalizzazione del problema (Report D3.R1) Analisi di complessitàEs. Il problema di stimare se esistono risposte ad una

metaquery con una confidenza superiore ad una data soglia è NPPP completo.

La struttura dell’alg. risolutore deve essere specifica per un problema di questo tipo.

Casi trattabili: metaqueries acicliche o fissate (data complexity)

Nel secondo caso il problema è altamente parallelizzabile (TC0)

D2I - Tema 3 15

MetaqueryingRicerche in Corso/Sviluppi futuri

Association rulesEs. Esiste un certo prodotto venduto molto spesso insieme ad

altri due?

Possibile risposta:

Ketchup Hamburger,Patatine

Confidenza 80%: l’80% degli acquisti che contengono Hamburger e Patatine, comprendono anche il Ketchup

Prototipazione e sperimentazione sul metaquerying

D2I - Tema 3 16

Pubblicazioni

Computational Properties of Metaquerying Problems. F. Angiulli, R. Ben-Eliyahu-Zohary, G.B. Ianni, L. Palopoli. Atti del Symposium on Principle of Databases (PODS 2000), Dallas, Texas. Versione estesa sottomessa per la pubblicazione su Theory of Computational Logic.

Towards efficient metaquerying, R. Ben-Eliyahu-Zohary, E. Gudes, G. Ianni. IJCAI 1999. Versione estesa sottomessa per la pubblicazione su Artificial Intelligence.

On the complexity of mining association rules, F. Angiulli, G. Ianni, L. Palopoli. SEBD 2001. Versione estesa in preparazione.

D2I - Tema 3 17

Attivita' del DIS - La Sapienza relativa al DM

Attività scientifica attualmente in corso presso l'unità del DIS - “La Sapienza”:- analisi delle tecniche di data mining e dei requisiti

utente ad esse associate;- analisi delle tecniche di visualizzazione e/o

interazione da utilizzarsi per la costruzione dell'interfaccia utente;

- analisi di una architettura di riferimento per la implementazione del prototipo del sistema.

D2I - Tema 3 18

Stato di avanzamento

Il prossimo prodotto in cui il Dis e' coinvolto e' D3.R2:

Architettura del sistema integrato di data mining e visualizzazione (RM,BO,CS)

Una prima versione dell'architettura e' disponibile e verra' fatta circolare in occasione del meeting del 13. Nella stessa occasione verra' fatta una presentazione dell'architettura e della proposta di interfaccia utente.

Le trasparenze seguenti sono una sintesi della parte relativa alla interazione con l'utente

Association RulesMetaqueries

USER INTERFACE:INTRODUCTION

We aim at providing effective rule visualizations. For the mining of metarules or association rules, the proposed interface offers two main visualization mechanisms:• Scatter Plot of Rules + Related Tuples – a kind of “Overview + Detail” visualization• Dedicated View – through which more rule parameters can be visualized

The Metaquery Interface relies on an interesting relationship between joins and metaqueries.

Consequently, our goal is centered on the provision of a user-centered interface for the exploitation of joins in formulating and mining metaqueries.

We propose an interface that enables the user to interact with both the schema and the actual data. The interface supports various interactive and intuitive mechanisms (eg drag and drop, joining and construction using hooks and chains, etc).

The Association Rule Interface aims at supporting the user to directly interact with data, with a view to constructing / designing and discovering association rules.

Based on the foregoing, our goal is to provide the user with an interface that intuitively and effectively supports him/her in discovering association rule-based knowledge.

The proposed interface employs intuitive tools (eg baskets for constructing association rules) and mechanisms(eg drag-drop mechanisms).

Visualization

19

The provision of a user-centered interface for the exploitation of the idea eg drag and drop mechanisms, intuitive joining and construction using hooks and chains, etc

Goal

Exploit Joins to design Metaqueries

Example

UsPT.User and UsCa.UserUsPT.Phone_Type and CaTe.TechnologyUsCa.Carrier and CaTe.Carrier

Idea

UsPT(u, p), UsCa(u, c), CaTe(c, p) (i)where u=User, p=Phone_Type/Technology, c=Carrier

Expression (i) resembles:

r1(x, z), r2(x, y), r3(y, z) (ii)

From (ii), there appears to be a transitive pattern ie:

r1(x, z) <= r2(x, y), r3(y, z)

which is a metaquery

UsCaUser CarrierJohn K. OmnitelJohn K. TimAnastasia A. Omnitel

CaTeCarrier Technology

Tim GSM 1800

Omnitel GSM 900

Wind GSM 1800

Target Data

METAQUERIES

UsPTUser Phone_Type

John K. GSM 900

John K. GSM 1800

Anastasia A. GSM 900

The provision of a user-centered interface eg drag-drop, intuitive interaction using hooks, chains, etc

Focus

20

Target Data

METAQUERIES

More rule parameters are displayed through aDEDICATED VISUALIZATION

UsCaUser CarrierJohn K. OmnitelJohn K. TimAnastasia A. Omnitel

CaTeCarrier Technology

Tim GSM 1800

Omnitel GSM 900

Wind GSM 1800

UsPTUser Phone_Type

John K. GSM 900

John K. GSM 1800

Anastasia A. GSM 900

The provision of effective visualizations: scatter plot + related tuples, dedicated view of rules

Focus

21

ASSOCIATION RULES

OrdProOrder Products

121 Socks, Shoes

122 Sweater123 Shirt, Sweater

124 Socks125 Shirt126 Tie, Shirt

Target Data

The provision of a user-centered interface eg drag-drop, intuitive construction using baskets, etc

Focus

How true is it that when• a pair of ``Shirt'' is ordered, then a pair of ``Tie'' is also in the same order? • a pair of ``Shoes'' is ordered, then a pair of ``Socks'' is also in the same order?

22

OrdProOrder Products

121 Socks, Shoes

122 Sweater123 Shirt, Sweater

124 Socks125 Shirt126 Tie, Shirt

Target Data

More rule parameters are displayed through aDEDICATED VISUALIZATION (cf Metaqueries)

ASSOCIATION RULES

The provision of effective visualizations: scatter plot + related tuples, dedicated view of rules

Focus

23