1 PANORAMICA SUL CLUSTERING... 1

(1)

i

SOMMARIO

1 PANORAMICA SUL CLUSTERING... 1

1.1 Descrizione generale... 1

1.2 Definizioni e concetti rilevanti... 3

1.2.1 Strutture per la rappresentazione degli oggetti ... 3

1.2.2 Tipi di variabili... 4

1.3 Principali metodi di clustering... 9

1.3.1 Algoritmi di Partizionamento... 9

1.3.2 Algoritmi Gerarchici... 15

1.3.3 BIRCH... 18

1.3.4 CURE... 20

1.3.5 CHAMELEON... 22

2 L’ALGORITMO ORCLUS - PRESENTAZIONE... 24

2.1 Introduzione ... 24

2.1.1 Problematiche legate alla multi-dimensionalità... 24

2.1.2 L’approccio di ORCLUS... 27

2.2 Descrizione dell’algoritmo... 32

2.2.1 La procedura Assign ... 34

2.2.2 La procedura FindVectors ... 34

2.2.3 La procedura Merge... 34

2.3 Evoluzione dell’algoritmo... 36

2.3.1 Scelta della dimensionalità di proiezione ... 36

2.3.2 Trattamento degli Outlier ... 37

2.3.3 Scalabilità ... 38

2.4 Requisiti... 40

2.4.1 Requisiti temporali ... 40

2.4.2 Requisiti spaziali ... 41

2.5 Campionamento Progressivo (Progressive Random Sampling) ... 42

3 L’ALGORITMO ORCLUS - REALIZZAZIONE ... 43

3.1 Scheda del software ... 43

3.1.1 File disponibili ...43

3.1.2 Input... 44

3.1.3 Output... 44

3.1.4 Il file di configurazione ... 46

3.1.5 Significato dei parametri di configurazione e fine tuning... 46

(2)

ii

4 L’ALGORITMO ORCLUS - VALUTAZIONE... 49

4.1 Generazione di dati artificiali ... 49

4.1.1 Principio di funzionamento di Datagen... 49

4.1.2 Scheda del software... 50

4.1.3 Esempio di applicazione di Datagen... 52

4.2 Applicazione di ORCLUS a dati artificiali ... 56

4.2.1 Prestazioni temporali ... 56

4.2.2 Prestazioni qualitative... 61

5 L’ALGORITMO ORCLUS APPLICATO AI BASKET DATASET ... 62

5.1 Osservazioni preliminari ... 62

5.1.1 Un esempio teorico... 62

5.1.2 Interpretazione dei risultati... 64

5.1.3 Riduzione delle caratteristiche... 65

5.2 Prove su dati artificiali... 68

5.2.1 Generazione di un dataset del tipo “basket data” ... 68

5.2.2 Applicazione di ORCLUS... 70

5.2.3 Applicazione di ORCLUS “modificato” ... 75

5.3 Esperienza su dati reali... 80

5.3.1 Caratteristiche del dataset utilizzato ... 80

5.3.2 Applicazione della versione standard dell’algoritmo... 80

5.3.3 Applicazione della versione modificata dell’algoritmo ... 81

6 L’ALGORITMO B-FREM... 85

6.1 Presentazione... 85

6.1.1 Limitazioni dell’algoritmo EM ... 85

6.1.2 L’approccio di B-FREM ... 86

6.1.3 Miglioramenti ad EM... 88

6.2 Descrizione dell’algoritmo... 90

6.2.1 Pseudo-codice dell’algoritmo ... 90

6.2.2 Spiegazione e significato dei parametri ... 91

6.3 Realizzazione dell’algoritmo... 93

6.3.1 Scheda del software... 93

6.3.2 File disponibili ... 93

6.3.3 Input... 94

6.3.4 Output... 94

6.3.5 Il file di configurazione ... 95

6.3.6 Significato dei parametri di configurazione e fine tuning... 96

6.4 Valutazione dell’algoritmo... 97

6.4.1 Dati artificiali... 97

6.4.2 Esperienza su dati reali... 97

7 CONCLUSIONI ... 100

(3)

iii

INDICE DELLE FIGURE

Numero Pagina Numero Pagina

Figura 1 ... 1

Figura 2 ... 10

Figura 3 ... 11

Figura 4 ... 13

Figura 5 ... 15

Figura 6 ... 17

Figura 7 ... 17

Figura 8 ... 18

Figura 9 ... 19

Figura 10 ... 21

Figura 11 ... 22

Figura 12 ... 25

Figura 13 ... 26

Figura 14 ... 29

Figura 15 ... 54

Figura 16 ... 54

Figura 17 ... 54

Figura 18 ... 55

Figura 19 ... 55

Figura 20 ... 57

Figura 21 ... 57

Figura 22 ... 59

Figura 23 ... 59

Figura 24 ... 60

Figura 25...63

Figura 26...66

Figura 27...68

Figura 28...69

Figura 29...69

Figura 30...71

Figura 31...72

Figura 32...72

Figura 33...73

Figura 34...74

Figura 35...74

Figura 36...77

Figura 37...77

Figura 38...81

Figura 39...82

Figura 40...82

Figura 41...83

Figura 42...84

Figura 43...90

Figura 44...98

Figura 45...98

Figura 46...98

Figura 47... 100

(4)

iv

RINGRAZIAMENTI

Desidero ringraziare sentitamente tutti coloro che hanno permesso la realizzazione di questo lavoro.

In primis i relatori, sempre disponibili e pazienti.

Poi i colleghi Manuele Piastra e Giuseppe Calabrese, con i quali ho condiviso la passione per l’argomento, e tutti i miei compagni di corso.

Ringrazio inoltre gli amici di Polartechnics, per la potente iniezione di fiducia.