Paniere Svolto di Data Mining (2025) - Risposte aperte

PRO:

1. Non richiede di definire a priori il numero dei cluster Il numero desiderato di cluster puoì essere

ottenuto ‘tagliando’ il dendrogramma al livello opportuno

Può̀

2. identificare una tassonomia (classificazione gerarchica) di concetti Gli elementi più simili

saranno fusi prima di elementi meno simili

Contro:

1. Una volta che una decisione è presa (fusione) non piò più essere annullata

2. In molte configurazioni è sensibile a rumore e outlier

3. Manca una funzione di ottimizzazione globale

10. Quale è la principale differenza fra gli algoritmi AGNES e DIANA?

L’Algoritmo AGNES utilizza un approccio agglomerativo ovvero inizia considerando che ogni oggetto formi

un cluster separato. Quindi, unisce i cluster più vicini fino a quando tutti i cluster sono raggruppati in un

solo cluster oppure una condizione di terminazione è verificata,l’algoritmo DIANA utilizza l’approccio

divisivo ovvero inizia considerando tutti gli oggetti in un unico cluster. Ad ogni iterazione successiva, un

cluster è diviso in cluster più piccoli, finché ogni oggetto formi un cluster oppure una condizione di

terminazione è verificata 17

Lez. 0020

05. Discutere i pro e i contro dell'algoritmo di clustering DBSCAN.

Uno degli algoritmi più importanti di clustering che utilizzano il concetto di densità è DBSCAN.

Questo algoritmo si basa sull’idea che ogni cluster deve avere nelle sue vicinanze almeno un certo numero

di punti.

La quantità di punti nei pressi di un cluster è la cosiddetta densità, che deve essere superiore ad una certa

soglia.

Di seguito i pro e i contro dell’algoritmo:

Pro: 1. Non è necessario fissare il numero di cluster apriori

2. Può trovare cluster di forme arbitrarie

3. Consente di rilevare il rumore e gli outliers

4. E’ insensibile all'ordine dei punti nel database

Contro:

1. Non è in grado di generare cluster di qualità quando i dati da gestire sono descritti da

troppi attributi (le classiche misure di distanza potrebbero perdere di significato).

2. Gestisce difficilmente dati caratterizzati da differenti densità, in quanto risulta difficile

trovare la coppia corretta di parametri Eps-MinPts.

06. Mostrare una implementazione del DBSCAN usando uno pseudocodice o un linguaggio di programmazione.

07. Discutere l'idea di base dell'algoritmo di clustering DBSCAN

Uno degli algoritmi più importanti di clustering che utilizzano il concetto di densità è DBSCAN.

Questo algoritmo si basa sull’idea che ogni cluster deve avere nelle sue vicinanze almeno un certo numero

di punti.

La quantità di punti nei pressi di un cluster è la cosiddetta densità, che deve essere superiore ad una certa

soglia.

Sarà fondamentale scegliere quanti punti ci devono essere e in quale raggio questi punti devono essere

considerati. 18

08. Definire e mostrare graficamente cosa sono i Core point, Border Point e Noise Point nel contesto dell'algoritmo DBSCAN.

 Core point: i punti la cui densità (numero di punti) è superiore a MinPts Questi punti sono interni a

un cluster;

 Borderpoint: hanno una densità minore di MinPts, ma nelle loro vicinanze (ossia a distanza < Eps) è

presente un core point;

 Noisepoint: tutti i punti che non sono ne Core point ne Border point.

Lez. 0021

08.Quando una regola associativa si dice forte?

⇒

Si definisce forte, una regola associativa X Y che soddisfa un supporto minimo suppmin ed una confidenza minima confmin,

ossia se:

09. Quale è la differenza fra supporto di un itemset e supporto di una regola associativa?

Si definisce supporto dell’itemset X nel database D il numero di transazioni di D che contengono X:

Il supporto di una regola denota la frequenza della regola all’interno delle transazioni.

⇒

Si definisce supporto della regola X Y , la frequenza relativa delle transazioni di D che verificano la regola:

10.Cosa è una regola associativa? 19

Una regola di associativa è un’implicazione della forma

⇒

X Y ⊆ ⊆ ∅

dove X e Y sono due itemset disgiunti: X I, Y I e X ∩ Y = . X rappresenta l’antecedente della regola e

Y il conseguente. ⇒

Si dice che la regola associativa X Y è verificata nella transazione

11 Definire i concetti di Item, itemset e transazioni.

1. Item Sia I = {i1,i2,...,in} un insieme di elementi chiamati item (o articoli).

2. ItemsetUn sottoinsieme di I è detto itemset (o insieme di articoli).

∈

3. Si definisce la transazione T come la coppia < Tid, I >, con Tid N codice identificativo della

⊆

transazione e I un itemset, tale che I I.

05. Su quali basi teoriche si fonda l'algoritmo Apriori?

Il presupposto teorico su cui si basa l’algoritmo Apriori sono le seguenti proprietà:

 Se un insieme di itemset è frequente, allora anche tutti i suoi sottoinsiemi sono frequenti.

 Se un itemset non è frequente, allora neanche gli insiemi che lo contengono sono

frequenti.

06. Cosa si intende per association rule mining?

Dato un database contenente un insieme di transizioni, si definisce problema di estrazione di regole

associative o association rule mining il processo che consente di estrarre tutte le regole forti in relazione a

due parametri di ingresso specificati dall’utente.

07. Discutere brevemente i passi dell'algoritmo Apriori per la generazione di itemset frequenti.

L’algoritmo Apriori affronta la fase di generazione degli itemset frequenti per approssimazioni successive, a

partire dagli itemsetcon un solo elemento.

Posto che Il numero delle iterazioni è kmax+1, dove kmaxi ndica la cardinalità massima (numero di item

dell’insieme) di un itemsetfrequente e kmaxspecifica anche il livello di taglio dell’albero di ricerca.

Gli step previsti sono:

1. Si calcola il supporto di ciascun oggetto e si scartano quelli con supporto minore della soglia di

supporto supmin.

2. Si pone k = 2. 2. Si generano Fk, l’insieme di itemset di ordine k (k-itemset) a partire da quelli di

ordine k – 1.

3. Si calcola il supporto di ciascun itemset e si scartano quelli con supporto inferiore a supmin. 4.

L’algoritmo si arresta se non è stato generato alcun k-itemset, altrimenti si pone k = k + 1 e si

procede al passo 2.

Lez. 0023

04. Mostrare un esempio di traliccio delle regole associative contenente regole potate. 20

05. Cosa è la proprietà di antimonotinicità? Vale per il supporto, per la confidenza o per entrambi?

La procedura per generare l’insieme delle regole associative forti, a partire da un generico itemset Y è la

seguente:

1) Si individuano tutte le possibili coppie di sottoinsiemi X e Y – X; 1)

⇒

2) Si generano le regole X Y – X; 1) ⇒

3) Si marca come valida la regola che soddisfa la condizione sulla confidenza: confidenza(X Y – X) >=

confmin ⇒

Per la regola X Y – X il rispetto del supporto minimo è già rispettato in quanto Y è già un itemset

frequente ⊂

Mentre per il supporto vale che se Y è un itemset frequente, anche X Y è un itemset frequente, SI

PARLA DI proprietà di antimonotinicità, per la confidenza di una regola bisogna stare attenti Infatti, la

⇒

confidenza di X Y è completamente indipendente dalla confidenza di X’

06. Riportare e discutere lo pseudocodice dell'algoritmo Apriori per la generazione di regole associative forti (si consideri di

avere già gli itemset frequenti).

07. Come si può migliorare l'efficienza dell'algoritmo Apriori?

L’efficienza può essere migliorata:

• riducendo la dimensione della base di dati da considerare nei passaggi successivi. Per esempio, una

transazione che non contiene nessun k-itemset frequente può essere trascurata nei passaggi successivi.

• riducendo il numero di candidati da considerare, usando tecniche di indirizzamento e partizionamento

• riducendo il numero di “scan” dell'intera base di dati 21

08. Quale è l'idea di base per la generazione di regole associative forti in Apriori?

Lez. 0024

06. Quale è l'idea di base di FP-growth?

Si tratta di un algoritmo introdotto nel 2000 e si basa su due passi principali:

• Creazione dell’FP-tree (albero dei pattern frequenti): il database viene scansionato solo due volte.

• Estrazione ricorsiva degli itemsetfrequenti direttamente dall’FP-tree.

Si effettua una ricerca in profondità dell’albero dei pattern frequenti (ricerca ricorsiva).

Prima di tutto si comprime il database considerando solo gli item frequenti e organizzandoli in un albero

che mantiene tutte le informazioni relative all’associazione degli item fra loro.

Successivamente, il database compresso viene diviso in un insieme di database condizionali. Ogni database

o albero condizionale viene associato con un item frequente e viene analizzato separatamente.

Utilizzando questo approccio, si riesce a ridurre in maniera sostanziale la quantità di dati da analizzare e da

tenere in memoria centrale. Infatti, per ogni pezzo di albero, viene utilizzata solo la porzione di transazioni

corrispondenti.

07. Quali sono i due passi principali dell'algoritmo FP-growth?

I due passi principali sono:

• Creazione dell’FP-tree (albero dei pattern frequenti): il database viene scansionato solo due volte.

• Estrazione ricorsiva degli itemsetfrequenti direttamente dall’FP-tree.

08. Discutere le principali differenze fra Apriori ed FP-growth

09. Che cosa è un FP-tree e come si crea?

L’albero dei pattern frequenti è la rappresentazione compressa delle transizioni del database (considerando

un supporto minimo). Esso viene creato secondo i seguenti passi:

1) Si identificano tutti gli 1-temset frequenti dal database

2) Si crea una lista L degli 1-itemset frequenti ordinati secondo il loro supporto o frequenza

3) Si scandisce il database una seconda volta, analizzando ogni transazione (non considerando gli item

non frequenti) e ordinandola seguendo l’ordine specificato nella lista L. Da ogni transazione si crea

un percorso nell’albero o porzioni di percorso. Per la creazione dell’albero, il nodo radice viene

sempre etichettato come null{}.

10. Cosa sono e a cosa servono la header table e i node-links?

L’albero dei pattern frequenti è la rappresentazione compressa delle transizioni del database. Per facilitare

l’attraversamento dell’albero, si crea una header table di item.

La prima colonna di questa tabella contiene l’item (o il suo ID), la seconda colonna contiene il supporto o il

numero di occorrenze dell’item, la terza col