Analisi dei dati ed estrazione della conoscenza Gianluca Amato 27 Maggio 2005

Analisi dei dati ed estrazione della conoscenza

Gianluca Amato 27 Maggio 2005

Parte teorica

Rispondere alle seguenti domande sui fogli forniti dal docente. Scrivere su ogni foglio utilizzato cognome e nome (in modo leggibile).

1. Descrivi le principali differenze tra i database tradizionali e i data warehouse.

2. Con riferimento al calcolo delle misure in un data cube:

(a) Quali sono i vantaggi delle misure algebriche o distributive rispetto a quelle olistiche?

(b) Considera come misura la media aritmetica. Si verifica facilmente che ` e una misura algebrica. A partire da quali misure distributive ` e possibile calcolarla?

3. Data una relazione generalizzata R derivata dal database DB, supponi che un insieme ∆DB di tuple debba essere cancellato da DB. Delinea una procedura incrementale per applicare le cancellazioni necessarie in R.

4. Un database ha 4 transazioni. Sia min supp=60% e min conf =80%.

ID cliente TID oggetti acquistati nel formato marca-categoria

01 T100 King-granchio, Tramonto-latte, Brughiera-formaggio, Best-pane

02 T200 Best-formaggio, Brughiera-latte, Fattoriaoro-mela, Gustosa-torta, Meraviglia-pane 03 T300 Costaovest-mela, Brughiera-latte, Meraviglia-pane, Gustosa-torta

04 T400 Meraviglia-pane, Tramonto-latte, Brughiera-formaggio

(a) al livello di granularit` a categoria, elenca tutti gli itemset frequenti, e tutte le regole associative forti ricavate dal seguente schema:

∀X ∈ Transazioni, compra(X, oggetto

) ∧ compra(X, oggetto

) ⇒ compra(X, oggetto

) ; (b) al livello di granularit` a marca-categoria, elenca tutti gli itemset frequenti;

(c) in che modo conoscere gli itemset frequenti al livello di granularit` a categoria pu` o aiutare a calcolare quelli al livello di granularit` a marca-categoria?

5. Si consideri il seguente insieme di dati, dove tipo ` e da considerarsi l’attributo classe.

nome numero zampe vola tipo

corvo 2 Y uccello

tirannosauro 2 N dinosauro

cane 4 N mammifero

pegaso 4 Y animale leggendario

(a) Costruire un albero di classificazione basato sull’algoritmo ID3. Qual ` e l’errore di sostituzione che si ottiene?

(b) Quale tasso di errore si ottiene col metodo del leave-one-out cross validation?

1

6. Supponiamo di eliminare l’attributo nome dall’insieme di dati di cui sopra, e di addestrare in questo modo un classificatore Bayesiano naive.

(a) Data una generica istanza “numero zampe = n, vola = v”, qual ` e la probabilit` a che la classe predetta sia mammifero

(b) Poich` e probabilit` a nulle sono spesso indesiderate, quale metodo pu` o essere utilizzato per eliminare questo inconveniente?

7. Si considerino i valori  = 1 e MinPts = 2, e l’insieme di dati che segue:

id x y

A 0 0

B 0 0.5

C 2 1

D 0.2 0.5

E 0 -0.8

F 2 2

(a) descrivere brevemente il funzionamento di un algoritmo di raggruppamento basato sulle densit` a (b) nel caso specifico di questo insieme di dati, quali sono i core object?

(c) nel caso specifico di questo insieme di dati, quali cluster verrebbero individuati da un algoritmo basato sulle densit` a?

Parte sperimentale

Rispondere alle seguenti domande preparando un file di testo. Questo dovr` a contenere, oltre a quanto espressamente chiesto dall’esercizio, la descrizione dei passi compiuti nella sua risoluzione, e i risultati delle varie analisi. Alla fine dell’esame, salvare il file di testo nel dischetto fornito dal docente. I file necessari allo svolgimento degli esercizi sono disponibili nel sito web del corso.

1. Usa i seguenti algoritmi in Weka per analizzare il set di dati zoo.arff: OneR, ID3, J48 (che ` e la versione implementata in Weka di C4.5). Scrivi una breve relazione sui risultati ottenuti. In particolare,

(a) qual ` e l’errore di sostituzione di questi tre modelli?

(b) cosa puoi dire sul tasso di errore di questi modelli, quando si trovano di fronte a una istanza diversa da quelle usate per l’addestramento?

(c) perch´ e l’algoritmo J48 si comporta meglio (e di tanto) rispetto agli altri altri due?

2