D2I - Tema 3: Data Mining
Stato di avanzamento
Roma 13/11/2001
Argomenti

D3R3
 Ricerche di similarità e approssimate


Clustering di dati metrici


Stefano Lodi, Claudio Sartori
Rule learning


Paolo Ciaccia, Marco Patella
Giovambattista Ianni, Luigi Palopoli
D3R2
 Architettura e Tecniche di visualizzazione

Tiziana Catarci, Giuseppe Santucci
D2I - Tema 3
2
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
3
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
4
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) ≤ (1+)P1-1 ()
D2I - Tema 3
5
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
6
Clustering di dati metrici


con stime di densità
con dati dinamici
D2I - Tema 3
7
Stime di densità





Funzione di influenza
y
 Uniforme: f (x) = 1, se d(x,y), 0 altrimenti
y
2
2
 Gaussiana: f (x) = exp[- d(x,y) /(2 )]
Stimatore puntuale della densità come somma delle funzioni
di influenza di ciascun punto: f D (x) = yD f y (x)
Lo stimatore è immediatamente utilizzabile nel caso metrico.
Costruzione di una foresta orientata.
D (x) < f D (y)}).
 (x,y)E  y = NN(x,{yD : f
Le componenti connesse della foresta sono i cluster della
soluzione.
D2I - Tema 3
8
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:
•

Rango dei vicini:
•

 (x,y) = ran(x,y,D) + ran(y,x,D).
Media di densità stimate:
•

 (x,y) = k-| NNQk(x,D)  NNQk(y,D) |.
 (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
9
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
10
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
11
Ongoing work - Università della Calabria

Rule Learning
 Metaquerying
 Association rules
D2I - Tema 3
12
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
13
Metaquerying
Risultati 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
14
Metaquerying
Ricerche in Corso/Sviluppi futuri

Association rules
Es. 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
15
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
16
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
17
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
D2I - Tema 3
18
USER INTERFACE:INTRODUCTION
Metaqueries
Association Rules
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
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
19
METAQUERIES
Target Data
UsCa
User
Carrier
John K.
Omnitel
John K.
Tim
Anastasia A.
Omnitel
Carrier
Tim
Omnitel
Wind
CaTe
Technology
GSM 1800
GSM 900
GSM 1800
UsPT
Phone_Type
User
John K.
John K.
Anastasia A.
GSM 900
GSM 1800
GSM 900
Focus
The provision of a user-centered
interface eg drag-drop, intuitive
interaction using hooks, chains, etc
Idea
Exploit Joins to design Metaqueries
Example
UsPT.User and UsCa.User
UsPT.Phone_Type and CaTe.Technology
UsCa.Carrier and CaTe.Carrier
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
Goal
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
20
METAQUERIES
Target Data
UsCa
User
Carrier
John K.
Omnitel
John K.
Tim
Anastasia A.
Omnitel
Carrier
Tim
Omnitel
Wind
CaTe
Technology
GSM 1800
GSM 900
GSM 1800
UsPT
Phone_Type
User
John K.
John K.
Anastasia A.
GSM 900
GSM 1800
GSM 900
Focus
The provision of effective
visualizations: scatter plot + related
tuples, dedicated view of rules
More rule parameters are displayed through a
DEDICATED VISUALIZATION
21
ASSOCIATION RULES
Target Data
Order
OrdPro
Products
121
Socks, Shoes
122
123
Sweater
Shirt, Sweater
124
125
126
Socks
Shirt
Tie, Shirt
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?
Focus
The provision of a user-centered
interface eg drag-drop, intuitive
construction using baskets, etc
22
ASSOCIATION RULES
Target Data
Order
OrdPro
Products
121
Socks, Shoes
122
123
Sweater
Shirt, Sweater
124
125
126
Socks
Shirt
Tie, Shirt
Focus
The provision of effective
visualizations: scatter plot + related
tuples, dedicated view of rules
More rule parameters are displayed through a
DEDICATED VISUALIZATION (cf Metaqueries)
23