Data Mining e Text Mining - Riassunti

SPADE

Approcci basati sul principio Pattern-Growth

1. FreeSpan
2. PrefixSpan
3. GSP

1. Individua tutte le 1-sequenze

2. Ripeti fino a che sono scoperte nuove sequenze frequenti

• Generazione candidati (fusione delle k-1 sequenze)
• Caso base (k=2) → , producono 2 sequenze candidate ,< i < i > < i i > < i , i >1 2 1 2 1 2
• Case generale (k>2) → Una (k-1)-sequenza frequente è fusa con un’altra (k-1)-sequenza frequente
• w1w_2 per produrre una k-sequenza candidata se rimuovendo il primo evento in e rimuovendo l’ultimow1evento in si ottiene la stessa sottosequenzaw2
• La k-sequenza ottenuta corrisponde a estesa con l’ultimo evento inw w1 2
• pruning candidati (elimina le k-sequenze che contengono k-1 sequenze non freq.)
• conteggio supporto delle candidate
• eliminazione candidati

Vincoli temporali

La ricerca di pattern sequenziali significativi può essere resa più efficace imponendo vincoli temporali sulla strutturadelle sequenze/sottosequenze

MaxSpan:

Specifica il massimo intervallo temporale tra il primo e l'ultimo evento nella sequenza

17 / 43Riassunti.md 1/20/2020

MinGap: specifica il minimo intervallo temporale che deve trascorrere tra il verificarsi di eventi contenuti in due elementi diversi

MaxGap: specifica il massimo intervallo temporale entro il quale gli eventi contenuti in un elemento devono svolgersi rispetto a quelli contenuti nell'evento precedente

Time Window Size (ws): intervallo temporale entro il quale due eventi avvenuti in tempi diversi devono essere considerati contemporanei

I vincoli temporali incidono sul supporto dei pattern riducendolo

Sono possibili due soluzioni

Approccio 1:

Calcolare le sottosequenze frequenti senza considerare i vincoli temporali applicando i vincoli a posteriori

Approccio 2:

Modificare GSP per eliminare direttamente i candidati che violano i vincoli temporali

può portare alla violazione del principio APriori per il vincolo MaxGap

Clustering

Ricerca di gruppi di oggetti tali che

è un insieme di punti che ha un punto centrale, chiamato centroide, che rappresenta il clustercome un tutto. I punti nel cluster sono più simili al centroide rispetto ai punti fuori dal clusterdensity basedUn cluster è un insieme di punti che sono densamente collegati tra loro, separati da aree di bassa densità. I punti nel cluster sono più simili tra loro rispetto ai punti fuori dal clustergrid basedUn cluster è un insieme di punti che sono allineati lungo una griglia o una struttura regolare. I punti nel cluster sono più simili tra loro rispetto ai punti fuori dal clustermodel basedUn cluster è un insieme di punti che possono essere descritti da un modello matematico o statistico. I punti nel cluster sono più simili al modello rispetto ai punti fuori dal clusterÈ un insieme di punti tali che un punto nel cluster è più vicino (o più simile a) al "centro" (può essere centroide o medioide) del cluster, piuttosto che al centro di ogni altro cluster contigui. Un cluster è un insieme di punti tali che un punto nel cluster è più vicino (o più simile) ad almeno uno dei punti del cluster rispetto a ogni punto che non appartenga al cluster. Un cluster è una regione densa di punti, che è separata da regioni a bassa densità, dalle altre regioni a elevata densità. Cluster con proprietà condivise o in cui la proprietà condivisa deriva dall'intero insieme di punti. K-means Clustering: Tecnica di clustering partizionante. Ogni cluster è associato ad un centroide (tipicamente la media dei punti del cluster) e i punti vengono assegnati al cluster il cui centroide è più.vicino(distanza euclidea, similarità coseno, correlazione...). Converge velocemente. Può trovare soluzioni sub-ottime (dipende molto da come vengono scelti i centroidi iniziali). Complessità O(nKId), dove: - n -> numero di punti - K -> numero di cluster (va specificato a priori) - I -> numero di iterazioni - d -> numero di attributi Risultati non buoni quando i cluster hanno: - Diverse dimensioni: k-means tende sempre a generare cluster della stessa dimensione - Diversa densità: le zone poco dense tendono ad includere più centroidi visto che le distanze sono al quadrato - Forma non globulare: la distanza euclidea trova cluster ipersferici - Molti outlier Possibili soluzioni: - Usare inizialmente più centroidi e poi trovare un modo per aggregarli - Valutazione bontà dei cluster: scarto quadratico medio (SSE) = ∑ ∑ dist(m, x)^2, dove i=1 e x∈Ci. L'errore è la distanza dal centroide assegnatomi. - Scelta dei centroidi iniziali: bisogna cercare di scegliere bene.centroidi iniziali - eseguire più volte l'algoritmo sperando di trovare una configurazione migliore
Eseguire un campionamento dei punti e una tecnica di clustering gerarchico per individuare i k centroidi
selezionare più di k centroidi e selezionare poi quelli più separati
utilizzare tecniche di post-processing
bisecting K-means
Gestione cluster vuoti 19 / 43
Riassunti.md 1/20/2020
L'algoritmo può determinare cluster vuoti → Comporta un SSE elevato perché un cluster non viene utilizzato
Individuare un centroide alternativo:
- Scegliere il punto che maggiormente contribuisce al valore di SSE
- Scegliere un elemento del cluster con il maggior SSE
Gestione Outlier
La bontà del clustering può essere negativamente influenzata dalla presenza di outlier (spostano il centroide).
Clustering Gerarchico
Produce un insieme di cluster organizzati come un albero gerarchico.
Può essere visualizzato come un dendrogramma
Pro: Non richiede un numero

iniziale di cluster (il numero desiderato si può ottenere tagliando il dendrogramma)

Può identificare una tassonomia

Contro:

• Le fusioni non possono essere annullate
• Sensibile a rumore e outlier
• Non c'è una funzione di ottimizzazione globale

2 Approcci:

1. Agglomerativo
• Un cluster per ogni elemento poi ad ogni passo fusione dei cluster più vicini.
2. Divisivo
• Cluster unico iniziale che si separa ad ogni passo.

Normalmente gli algoritmi gerarchici utilizzano una matrice di similarità o delle distanze (proximity matrix)

Algoritmo:

1. Crea un cluster per ogni elemento
2. Calcola la proximity matrix
3. Repeat
4. Fondi i due cluster più vicini
5. Aggiorna la proximity matrix
6. Until rimane un solo cluster

Complessità → Spazio O(), Tempo O()

Fondamentale → calcolo della similarità tra 2 cluster:

• MIN o Single link: Minima distanza tra 2 elementi dei cluster
• MAX o Complete: Massima distanza tra 2 elementi dei cluster

linkMassima distanza tra 2 punti del cluster 20 / 43Riassunti.md 1/20/2020Meno suscettibile al rumoreSepara cluster grandiPrivilegia cluster globulariGroup Averagemedia delle distanze tra tutti i punti dei clusterCompromesso tra MIN e MAXMeno suscettibile al rumoreorientato a cluster sfericiDistanza tra centroidiWard's MethodLa similarità tra due cluster è data dall'aumento di errore quadratico quando due cluster sono fusiMeno suscettibile al rumoreOrientato a cluster sfericiStessa funzione obiettivo del k-means (può essere utilizzato per inizializzare k nel k-means)DBSCANClustering basato su densità.Densità = numero di punti all'interno di un raggio Eps specificatoDefinizioni Fondamentali:Core Point: Punti la cui densità è superiore a una soglia MinPts (sono interni ad un cluster)Border Point: densità minore di MinPts, ma nelle loro vicinanze (ossia a distanza < Eps) è presente un corepointNoise Point:

Tutti i punti che non sono Core point e Border point

Algoritmo:

1. Input: Dataset D, MinPts, Eps
2. Insieme dei cluster C
3. Classifica i punti in D come core, border o noise
4. Elimina tutti i punti di tipo noise
5. Assegna al cluster i punti core che abbiano distanza < di Eps da almeno uno degli altri punti assegnato al cluster
6. Assegna i punti border a uno dei cluster a cui sono associati i corrispondenti punti core

Pro:

• Resistente al rumore
• Può generare cluster di qualsiasi forma

Contro:

• Dati con elevata sparsità
• Dataset con densità variabile
• Scegliere EPS e MinPts
• Per i core point i k-esimi nearest neighbor devono essere circa alla stessa distanza e piuttosto vicini
• I noise point avranno il k-esimo nearest neighbor più lontano

21 / 43

Riassunti.md 1/20/2020

Oridniamo i punti p in base alla distanza del loro k-esimo vicino (normalmente 4). Il punto p in cui si verifica un repentino cambio della distanza misurata segnala la separazione tra core point e noise

point.Eps = ordinata di pMinPts = k

Validità dei cluster

Motivazioni per la valutazione di un clustering:

1. Valutare, senza informazioni esterne, come il risultato del clustering modella i dati
2. Determinare che si sia determinato il "corretto" numero di cluster
3. Verificare la clustering tendency di un insieme di dati, ossia la presenza di strutture non-randomiche
4. Valutare, utilizzando informazioni esterne (etichette di classe), come il risultato del clustering modella i dati
5. Comparare le caratteristiche di due insiemi di cluster per valutare quale è il migliore
6. Comparare le caratteristiche di due algoritmi di clustering per valutare quale è il migliore

Misure di validità:

Misure esterne o supervisionate: calcolano in che misura le label dei cluster corrispondono alle label delle classi (possono essere orientate alla classificazione - valutano in che misura i cluster contengono oggetti appartenenti alla stessa classe; orientati alla

similarità → misurano con che frequenza 2 oggetti che sono nello stesso cluster appartengono alla stessa classe)

mijPer ogni cluster i si ha la prob. che un membro del cluster i appartenga a j ( num. oggetti nel p = mij imi cluster; num oggetti di classe j nel cluster i; L classi; K cluster)

mijentropia: Entropia per un cluster i Le = − ∑ p log pi ij ij2j=1mPer l'intero clustering iKe