Indice I
Indice
INTRODUZIONE... VII
CAPITOLO 1 DATA MINING & KNOWLEDGE DISCOVERY IN DATABASES... 1
1.1 INTRODUZIONE... 1
1.2 LA CONOSCENZA... 2
1.3 KNOWLEDGE DISCOVERY IN DATABASES ... 6
1.3.1 FASI DEL KDD ... 8
1.3.2 CICLO VIRTUOSO ... 12
1.3.3 ARCHITETTURA TIPICA DI UN SISTEMA KDD... 15
1.3.4 SETTORI APPLICATIVI DEL KDD ... 17
1.4 DATA MINING ... 19
1.4.1 REGOLE DI ASSOCIAZIONE... 21
1.4.2 CLASSIFICAZIONE... 26
1.4.3 CLUSTERING... 40
1.4.4 ASPETTI TEMPORALI NEL DATA MINING ... 44
1.5 IL FUTURO DEL KDD ... 45 CAPITOLO 2 KDDML... 49 2.1 INTRODUZIONE... 49 2.2 XML... 50 2.2.1 DOCUMENTI XML... 51 2.2.2 ELABORAZIONE DI DOCUMENTI XML ... 53 2.3 PMML... 54 2.4 KDDML... 56 2.4.1 IL LINGUAGGIO ... 57 2.4.2 L’ARCHITETTURA ... 65 2.4.3 ESEMPIO DI APPLICAZIONE DI KDDML ... 71 2.4.4 LA GUI ATTUALE... 75
CAPITOLO 3 SISTEMI DI KNOWLEDGE DISCOVERY E LORO ASPETTI VISUALI 79 3.1 INTRODUZIONE... 79
3.1.1 PARAMETRI GENERALI DI VALUTAZIONE ... 81
3.2 WEKA... 83
3.2.1 WEKA GUI ... 85
3.2.2 ESEMPIO DI UTILIZZO DI WEKA ... 92
Indice
II
3.3.1 YALE GUI... 99
3.3.2 ESEMPIO DI UTILIZZO DI YALE ... 105
3.4 ORANGE... 109
3.4.1 ORANGE CANVAS ... 111
3.4.2 ESEMPIO DI UTILIZZO DI ORANGE CANVAS ... 116
3.5 GHOSTMINER ... 120
3.5.1 GHOSTMINER DEVELOPER ... 123
3.5.2 ESEMPIO DI UTILIZZO DI GHOSTMINER DEVELOPER... 127
3.6 TANAGRA ... 132
3.6.1 TANAGRA GUI... 134
3.6.2 ESEMPIO DI UTILIZZO DI TANAGRA... 139
CAPITOLO 4 COMPARAZIONE... 145
4.1 INTRODUZIONE... 145
4.2 MODALITÀ DI ACCESSO A DATI E MODELLI ... 146
4.3 COSTRUZIONE E RAPPRESENTAZIONE DI UNA QUERY... 149
4.3.1 RAPPRESENTAZIONE DEL FLUSSO DI DATI: ALBERO vs GRAFO... 150
4.3.2 PRESENZA DI UN WIZARD ... 152
4.3.3 IMMISSIONE DEI PARAMETRI ... 153
4.3.4 LIMITAZIONI E POTENZIALITÀ DEI VARI TOOL ... 154
4.3.5 RAPPRESENTAZIONE DELLA QUERY: ALCUNI ESEMPI... 155
4.3.6 RAPPRESENTAZIONE DI COSTRUTTI COMPLESSI... 158
4.3.7 ESPRESSIVITÀ ED IMMEDIATEZZA DELLE RAPPRESENTAZIONI ... 162
4.4 ESECUZIONE E VALIDAZIONE ... 163
4.5 VISUALIZZAZIONE DEI DATI E DEI RISULTATI ... 166
4.6 ESTENDIBILITÀ DEI SISTEMI ... 168
4.7 SUPPORTO ALL’UTENTE... 169
4.8 REQUISITI ... 170
4.8.1 ACCESSO AI DATI... 171
4.8.2 LA METAFORA GRAFICA... 171
4.8.3 SEMPLICE E COMPLETA ESPANSIONE DEL SISTEMA ... 172
4.8.4 ESECUZIONE E META-ESECUZIONE ... 173
4.8.5 IMMISSIONE DEI PARAMETRI ... 176
4.8.6 VISUALIZZAZIONE INPUT/OUTPUT ... 177
4.8.7 MODELLI ESTRATTI E UTILIZZO DI PMML ... 178
4.8.8 POSSIBILITÀ DI SALVATAGGIO DEL KNOWLEDGE FLOW... 178
4.8.9 DOCUMENTAZIONE FORNITA ... 179
4.9 CONSIDERAZIONI FINALI... 179
CAPITOLO 5 STUDIO DEI REQUISITI DEL LINGUAGGIO VISUALE PER KDDML181 5.1 INTRODUZIONE... 181
Indice III
5.2 KDDML & ACCESSO AI DATI... 182
5.3 KDDML & METAFORA GRAFICA ... 185
5.4 KDDML & ESPANDIBILITÀ ... 193
5.5 KDDML & META-ESECUZIONE ... 199
5.6 KDDML & IMMISSIONE PARAMETRI ... 203
5.7 KDDML & VISUALIZZAZIONE ... 205
5.8 KDDML & MODELLI ... 207
5.9 KDDML & SALVATAGGI ... 208
5.10 KDDML & DOCUMENTAZIONE FORNITA ... 210
CONCLUSIONI ... 211
Indice
IV
Indice delle figure
Figura 1.1 Conoscenza e Metaconoscenza... 3
Figura 1.2 Fasi del processo KDD. ... 8
Figura 1.3 Ciclo virtuoso... 13
Figura 1.4 Architettura di un sistema per KDD. ... 16
Figura 1.5 Fasi tipiche della classificazione... 28
Figura 1.6 Albero di decisione estratto dal training set di Tabella 1.3. ... 30
Figura 1.7 Algoritmo greedy per la costruzione di un albero di decisione. ... 31
Figura 1.8 Esempio di matrice di confusione... 34
Figura 2.1 Possibile rappresentazione in XML delle RdA di Tabella 2.1. ... 52
Figura 2.2 DTD relative ai dati di Figura 2.1... 52
Figura 2.3 Albero DOM del file XML di Figura 2.1. ... 53
Figura 2.4 Un esempio di modello PMML. ... 56
Figura 2.5 Architettura del sistema KDDML... 67
Figura 2.6 Codice dell'interprete KDDML. ... 70
Figura 2.7 Esempio di meta-dati utilizzati da KDDML... 71
Figura 2.8 File XML rappresentante una query KDDML. ... 72
Figura 2.9 Albero DOM per la query di Figura 2.8. ... 74
Figura 2.10 Gerarchia degli oggetti del sistema KDDML. ... 75
Figura 2.11 Risultato della query di Figura 2.8... 75
Figura 2.12 La GUI attuale del sistema KDDML. ... 76
Figura 3.1 WEKA GUI Chooser. ... 87
Figura 3.2 Ambiente Knowledge Flow di WEKA. ... 89
Figura 3.3 Scelta del data set da utilizzare come training set. ... 93
Figura 3.4 Inserimento e collegamento degli operatori per caricare e visualizzare il data set... 94
Figura 3.5 Visualizzazione dei dati scelti come training set. ... 95
Figura 3.6 Inserimento degli operatori per la costruzione dell'albero di classificazione. ... 96
Figura 3.7 Flusso finale dei dati. ... 97
Figura 3.8 Albero di classificazione estratto... 97
Figura 3.9 YALE GUI... 102
Figura 3.10 Welcome screen di YALE. ... 105
Figura 3.11 Caricamento e visualizzazione del training set... 106
Figura 3.12 Inserimento di operatori per la costruzione dell'albero di classificazione... 107
Figura 3.13 Vista finale del nostro esperimento. ... 108
Figura 3.14 Versione XML del nostro esperimento e del diagramma di nesting degli operatori presenti... 108
Figura 3.15 Statistiche sul test set. ... 109
Figura 3.16 Ambiente ORANGE Canvas. ... 112
Figura 3.17 Finestra di visualizzazione del collegamento attivo tra due widget. ... 113
Figura 3.18 Dialog Box per la scelta del file contenente il training set. ... 116
Figura 3.19 Inserimento del nodo per la costruzione dell'albero di classificazione... 117
Figura 3.20 Schema finale per la costruzione di un albero di classificazione. ... 118
Indice V
Figura 3.22 Visualizzazione dell'applicazione prodotta dallo schema di Figura 3.20... 120
Figura 3.23 GhostMiner Developer. ... 125
Figura 3.24 Import wizard di GhostMiner Developer. ... 128
Figura 3.25 Grafico rappresentante la distribuzione dei dati in input... 128
Figura 3.26 Inserimento e configurazione dell'operatore SSV Tree... 130
Figura 3.27 Treeview del sistema per la generazione dell'albero di classificazione.... 130
Figura 3.28 Albero di classificazione estratto... 131
Figura 3.29 Albero finale del progetto e matrice di confusione sul test set... 132
Figura 3.30 TANAGRA GUI... 136
Figura 3.31 Introduzione dell'attributo status nel data set. ... 139
Figura 3.32 Dialog Box per la scelta del data set, titolo e path per il salvataggio del diagramma... 140
Figura 3.33 Dialog Box per la configurazione del nodo Select Example e Define Status. ... 141
Figura 3.34 Insieme di statistiche ed albero di classificazione prodotti dal sistema... 142
Figura 3.35 Treeview degli operatori del nostro progetto. ... 142
Figura 3.36 Risultato della classificazione... 143
Figura 4.1 Treeview rispettivamente di YALE (1.a), TANAGRA (1.b) e GhostMiner Developer (1.c)... 148
Figura 4.2 Wizard di YALE. ... 153
Figura 4.3 Catena di operatori YALE per la lettura e l’applicazione di un modello e rispettiva versione in XML. ... 155
Figura 4.4 Albero degli operatori per l’estrazione di due modelli in YALE. ... 156
Figura 4.5 Albero degli operatori per l’estrazione di due modelli in TANAGRA. 156 Figura 4.6 Estrazione di due modelli dallo stesso data set... 157
Figura 4.7 Meta-classificatore costruito con GhostMiner Developer. ... 160
Figura 4.8 Comparazione tra metafora grafica, file XML risultante e disegno del nesting degli operatori in YALE. ... 161
Figura 4.9 Validazione di una query in YALE. ... 164
Figura 4.10 Esempio di finestra di Log di WEKA... 165
Figura 4.11 Esempio di meta-dati tipici dei file arff utilizzati da WEKA. ... 174
Figura 5.1 Query KDDML per estrarre due modelli diversi da dati diversi. ... 184
Figura 5.2 Query KDDML e corrispondente albero DOM... 185
Figura 5.3 Grafo rappresentante la query di Figura 5.2. ... 186
Figura 5.4 Estrazione di due modelli dallo stesso data set... 189
Figura 5.5 Albero DOM per la query di Figura 5.1. ... 189
Figura 5.6 Pseudo-Albero DOM per la query di Figura 5.4.b). ... 190
Figura 5.7 Schema riassuntivo sull’espansione di KDDML... 195
Figura 5.8 Esempio di processo KDD con utilizzo di meta-dati... 202
Figura 6.1 Architettura ad alto livello del sistema KDDML con l’introduzione del livello GUI. ... 211
Indice
VI
Indice delle tabelle
Tabella 1.1 Gruppo di transazioni di acquisto... 23
Tabella 1.2 Itemset frequenti relativi alle transazioni di Tabella 1.1. ... 24
Tabella 1.3 Training set per l’estrazione di un albero di decisione... 29
Tabella 2.1 Insieme di regole di associazione... 51
