Appunti di Data Mining

Data Mining 2022-2023

Indice

• 1 Introduzione 1
• 2 Data Warehouse 4
• 3 Frequent Itemset 9
• 3.1 Hash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
• 3.2 Modello Market-Basket . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
• 3.2.1 Frequent Itemset . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
• 3.2.2 Association rules . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
• 3.3 Frequent Itemset Generation . . . . . . . . . . . . . . . . . . . . . . . . . 13
• 3.3.1 Dettagli sull’implementazione . . . . . . . . . . . . . . . . . . . . 17
• 3.4 Rule Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
• 3.4.1 Algoritmo A-Priori . . . . . . . . . . . . . . . . . . . . . . . . . . 19
• 3.4.2 Algoritmo Park-Chen-Yu . . . . . . . . . . . . . . . . . . . . . . 22
• 3.4.3 Algoritmo Multistage . . . . . . . . . . . . . . . . . . . . . . . . 26
• 3.4.4 Algoritmo Multihash . . . . . . . . . . . . . . . . . . . . . . . . 27
• 3.4.5 Algoritmi a passaggio limitato . . . . . . . . . . . . . . . . . . . 28
• 3.4.6 Frequent Itemset nei flussi di dati . . . . . . . . . . . . . . . . . . 29
• 4 Riduzione della dimensionalità 31
• 4.1 Algebra lineare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
• 4.2 Riduzione della dimensionalità . . . . . . . . . . . . . . . . . . . . . . . . 33
• 4.2.1 Principal Component Analysis . . . . . . . . . . . . . . . . . . . 34
• 4.2.2 Singular Value Decomposition . . . . . . . . . . . . . . . . . . . . 35
• 5 Clustering 42
• 5.1 Distanze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
• 5.1.1 Distanza Euclidea . . . . . . . . . . . . . . . . . . . . . . . . . . 45
• 5.1.2 Norma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
• 5.1.3 Distanza di Jaccard . . . . . . . . . . . . . . . . . . . . . . . . 45
• 5.1.4 Distanza di Hamming . . . . . . . . . . . . . . . . . . . . . . . 46
• 5.1.5 Distanza coseno . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
• 5.1.6 Edit Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
• 5.2 Algoritmi di Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
• 5.2.1 Hierarchical Clustering . . . . . . . . . . . . . . . . . . . . . . . . 48
• 5.2.2 k-means Clustering . . . . . . . . . . . . . . . . . . . . . . . . . 56
• 5.2.3 Self Organizing Map . . . . . . . . . . . . . . . . . . . . . . . . 59
• 5.2.4 Bradley-Fayyad-Reina . . . . . . . . . . . . . . . . . . . . . . . 62
• 5.2.5 Density Based Clustering . . . . . . . . . . . . . . . . . . . . . 64
• i Indice ii
• 5.2.6 Graph Based Clustering . . . . . . . . . . . . . . . . . . . . . . . 65
• 5.3 Cluster Validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
• 5.3.1 Unsupervised Measure . . . . . . . . . . . . . . . . . . . . . . . . 69
• 5.3.2 Supervised Measure . . . . . . . . . . . . . . . . . . . . . . . . 73
• 5.3.3 Caratteristiche di dati, cluster e algoritmi di Clustering . . . . . . 73
• 6 Locality Sensitive Hashing 75
• 6.1 Ricerca di documenti simili . . . . . . . . . . . . . . . . . . . . . . . . . 75
• 6.1.1 Shingling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
• 6.1.2 Min-Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
• 6.1.3 Locality Sensitive Hashing . . . . . . . . . . . . . . . . . . . . . . 85
• 7 Text Mining 90
• 7.1 Information Retrieval . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
• 7.1.1 Indicizzazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
• 7.1.2 Queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
• 8 Neural Language Models 112
• 8.1 Artificial Neural Networks . . . . . . . . . . . . . . . . . . . . . . . . . . 112
• 8.1.1 Convolutional Neural Networks . . . . . . . . . . . . . . . . . . . 118
• 8.1.2 Recurrent Neural Networks . . . . . . . . . . . . . . . . . . . . . 122
• 8.2 Natural Language Processing . . . . . . . . . . . . . . . . . . . . . . . . 125
• 8.2.1 Language Models . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
• 8.2.2 Word Meaning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
• 8.2.3 Neural Language Models . . . . . . . . . . . . . . . . . . . . . . . 134
• 8.2.4 Machine Translation . . . . . . . . . . . . . . . . . . . . . . . . 140
• 8.2.5 Transformers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
• 8.2.6 Contextual embeddings . . . . . . . . . . . . . . . . . . . . . . 147
• 9 Text Classification 150
• 9.1 Part-Of-Speech Tagging . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
• 9.2 Named Entity Recognition . . . . . . . . . . . . . . . . . . . . . . . . . . 154
• 9.3 Misure per un motore di ricerca . . . . . . . . . . . . . . . . . . . . . . . 155
• 10 Document Image Analysis and Recognition 158
• 10.1 Metodi bottom-up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
• 10.2 Metodi top-down . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
• 10.3 Functional labeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

Capitolo 1 introduzione

Big Data

I Big Data rappresentano raccolte di grandi quantità di dati eterogenei e complessi, difficili da elaborare con gli strumenti di gestione dei database o con le tradizionali applicazioni di elaborazione dei dati.

I Big Data possono essere classificati in tre diverse tipologie:

• Dati strutturati, ovvero dati che hanno una lunghezza e un formato definiti (come numeri, stringhe, date, ecc...). Generalmente questi dati vengono memorizzati in database (solitamente database relazionali) e la struttura di un dato è rappresentata dallo schema del database. Su questi dati possiamo effettuare interrogazioni (query) attraverso un linguaggio di interrogazione strutturato (come SQL). Possiamo rappresentare questi dati attraverso una matrice di grandi dimensioni, generalmente sparsa (ovvero con molti campi vuoti).
• Dati non strutturati, ovvero dati che non seguono un formato specifico (ad esempio un documento di testo).
• Dati semi strutturati, ovvero dati non conformi ad uno schema (struttura) fissato (ovvero non hanno un formato tipico). In particolare, la struttura di questi dati viene integrata nel dato stesso (ad esempio dati in formato XML).

Data Mining

Il Data Mining rappresenta l’utilizzo di tecniche efficienti per l’analisi di numerose raccolte di dati e l’estrazione di modelli (pattern) utili e possibilmente inaspettati nei dati.

Perciò, a partire da un insieme di una grande quantità di dati, vogliamo individuare dei pattern che siano:

• Validi, ovvero applicabili su nuovi dati con una certa sicurezza.
• Utili, ovvero che permettono di operare sui dati.
• Inaspettati, ovvero non ovvi per il sistema.
• Comprensibili, ovvero gli esseri umani dovrebbero essere in grado di interpretare il modello.

Le principali attività di Data Mining riguardano:

• Metodi descrittivi, ovvero trovare modelli interpretabili dall’uomo che descrivano i dati (ad esempio il clustering, cioè raggruppare entità simili).
• Metodi predittivi, ovvero utilizzare alcune variabili per prevedere i valori sconosciuti o futuri di altre variabili (ad esempio i recommender systems).

1

Capitolo 1. Introduzione 2

In particolare, gli argomenti che riguardano il Data Mining sono:

• Data Warehouse, ovvero realizzare collezioni di dati eterogenei (cioè mettere insieme informazioni che fanno riferimento ad uno stesso argomento, provenienti da sistemi diversi). Il Data Warehouse è un archivio di informazioni raccolte da più fonti, memorizzate secondo uno schema unificato e di solito residenti in un unico sito. I Data Warehouse sono costruiti attraverso un processo di pulizia, integrazione, trasformazione, caricamento e aggiornamento periodico dei dati. Un Data Warehouse è solitamente modellato da una struttura di dati multidimensionale, chiamata data cube, in cui ogni dimensione corrisponde ad un attributo (oppure ad un insieme di attributi dello schema) ed ogni cella memorizza il valore di una misura aggregata (come il conteggio o la somma delle vendite). Un data cube fornisce una visione multidimensionale dei dati e consente di precompilare e accedere rapidamente ai dati sintetizzati.

I sistemi di Data Warehouse possono fornire un supporto per l’OLAP. Esempi di operazioni OLAP sono il drill-down e il roll-up, che consentono all’utente di visualizzare i dati a diversi livelli di sintesi.

• Trovare elementi simili (attraverso opportune misure di distanza).
• Trovare insiemi di elementi frequenti. Dato un insieme di record, ognuno dei quali contiene un certo numero di elementi di una determinata collezione, vogliamo identificare gli insiemi di elementi (itemset) che ricorrono frequentemente e produrre delle regole di dipendenza, dette regole di associazione (association rules), che prevedano l’occorrenza di un elemento in base alle occorrenze di altri elementi.

ES (Market-Basket Analysis): Ipotizziamo di voler analizzare i prodotti acquistati dai clienti in un supermercato per poter prevedere le associazioni più frequenti di prodotti, in modo da offrire promozioni e sconti (ad esempio, se due oggetti sono comprati spesso insieme allora potremmo fare una promozione su uno dei due oggetti per incentivarne l’acquisto).

Consideriamo la seguente tabella che mostra cinque differenti carrelli di prodotti acquistati da clienti diversi:

Capitolo 1. Introduzione 3

Allora possiamo vedere che:

• Gli itemset più frequenti sono: {milk, coke} {diaper, milk}
• Le regole di associazione sono: {milk} −→ {coke} {diaper, milk} −→ {beer}

N.B: generalmente vogliamo trovare gli itemset con cardinalità più grande.

• Clustering, ovvero raggruppare elementi simili. Considerando un insieme di punti dati (ciascuno dei quali possiede un insieme di attributi) ed una misura di somiglianza tra essi, vogliamo trovare dei cluster tali che i punti dati appartenenti ad un cluster siano più simili tra loro ed i punti dati appartenenti a cluster diversi siano meno simili tra loro. Perciò sarà necessario definire delle misure di somiglianza.
• Filtraggio dei flussi di dati, ovvero filtrare i dati interessati provenienti da un flusso di dati continuo (tale flusso non può essere memorizzato, poiché troppo peso e continuo).
• Riduzione della dimensionalità (per ridurre lo spazio di memorizzazione).
• Somiglianza dei documenti.

L’Information Retrieval (IR) è una tecnica che si occupa dell’archiviazione, della rappresentazione e della ricerca di documenti o di informazioni contenute in essi. I documenti possono essere testuali o multimediali. L’IR deve essere efficiente ed efficace, poiché deve operare con una grande quantità di dati.

Un sistema di database, chiamato anche Database Management System (DBMS), consiste in una raccolta di dati correlati, nota come database, ed un insieme di programmi software per gestire e accedere a questi dati.

Un database relazionale è un insieme di tabelle, a ciascuna delle quali viene assegnato un nome univoco. Ogni tabella è costituita da un insieme di attributi (colonne o campi) e di solito memorizza un ampio insieme di tuple (record o righe). Ogni tupla di una tabella relazionale rappresenta un oggetto identificato da una chiave univoca e descritto da un insieme di valori e di attributi. L’accesso ai dati relazionali può avvenire tramite query, scritte in un linguaggio di interrogazione relazionale (ad esempio SQL). Una determinata query viene trasformata in un insieme di operazioni relazionali (come join, selezione e proiezione) e quindi ottimizzata per un’elaborazione efficiente. Una query consente di recuperare sottoinsiemi specifici di dati.

Capitolo 2 Data Warehouse

Il Data Warehouse è una raccolta di dati orientata ai soggetti, integrata, variabile nel tempo e non volatile che permette l’aggregazione e la sintesi dei dati e aiuta l’utente a trovare pattern nei dati senza conoscerne l’organizzazione nei dettagli.

Questa definizione presenta le caratteristiche principali di un Data Warehouse che lo distingue dagli altri sistemi di repository di dati (come i sistemi di database relazionali). Diamo un’occhiata più da vicino a ciascuna di queste caratteristiche chiave:

• Orientato ai soggetti: un Data Warehouse è organizzato intorno a temi importanti (come clienti, fornitori, prodotti e vendite). Piuttosto che concentrarsi sulle operazioni quotidiane e sull’elaborazione delle transazioni di un’organizzazione, un Data Warehouse si concentra sulla modellazione e sull’analisi dei dati per i responsabili delle decisioni. Per questo motivo, i Data Warehouse forniscono in genere una visione semplice e concisa di particolari argomenti, escludendo i dati che non sono utili nel processo di supporto alle decisioni.
• Integrato: un Data Warehouse viene solitamente costruito integrando più fonti eterogenee (come database relazionali, file piatti e record di transazioni online).
• Variabile nel tempo: i dati sono archiviati per fornire informazioni da una prospettiva storica (ad esempio, gli ultimi 5−10 anni). Ogni struttura chiave del Data Warehouse contiene, implicitamente o esplicitamente, un elemento temporale.
• Non volatile: un Data Warehouse è un archivio di dati trasformati fisicamente separato dai dati applicativi presenti nell’ambiente operativo. Grazie a questa separazione, un Data Warehouse non richiede meccanismi di elaborazione delle transazioni, di recupero e di controllo della concorrenza. Di solito richiede solo due operazioni di accesso ai dati, ovvero il caricamento iniziale dei dati e l’accesso ai dati per la lettura.

Un Data Warehouse può essere visto anche come un’architettura, costruita integrando dati provenienti da più fonti eterogenee per supportare query. Il Data Warehouse è molto utile dal punto di vista dell’integrazione di database eterogenei. Infatti, le organizzazioni raccolgono tipicamente diversi tipi di dati da fonti di informazione multiple, eterogenee, autonome e distribuite. Perciò risulta utile integrare tali dati e fornire un accesso facile ed efficiente ad essi.

A tale scopo (cioè per integrare database eterogenei) si prevedono due differenti approcci di architettura:

4

Capitolo 2. Data Warehouse 5

• Query-Driven, rappresenta l’approccio tradizionale per integrare database eterogenei. Questo approccio consiste nel costruire wrapper e mediatori su più database eterogenei (che rappresentano le sorgenti delle informazioni). Il mediatore fornisce le risposte alle query effettuate dai Client (si interrogano direttamente i database).

Questo approccio ha il vantaggio di non richiedere la copia delle informazioni contenute nei database che devono essere interrogati. Per questo motivo è richiesto un minore spazio di archiviazione. Inoltre i dati risultano essere sempre aggiornati, permettendo soluzioni real-time (poiché i dati non devono essere copiati e quindi immediatamente disponibili).

Di contro, però, tale approccio richiede complessi processi di filtraggio e integrazione delle informazioni ed inoltre risulta essere inefficiente e costoso per query frequenti.

• Warehouse, rappresenta un’alternativa all’approccio tradizionale. In questa soluzione le informazioni provenienti da più fonti eterogenee vengono prima integrate e memorizzate in un archivio (detto warehouse). Quindi queste informazioni risultano disponibili per l’interrogazione e l’analisi diretta.

Questo approccio ha il vantaggio di eseguire query ad alte prestazioni, poiché si interroga l’archivio contenente i dati copiati e aggregati (non si deve interfacciare con le singole sorgenti). Inoltre, l’elaborazione delle query nei Data Warehouse non interferisce con l’elaborazione delle sorgenti. Un altro vantaggio è quello di consentire operazioni anche quando le sorgenti non sono disponibili.

Di contro, però, i Data Warehouse non contengono le informazioni più aggiornate.

Capitolo 2. Data Warehouse 6

Analizziamo la differenza tra i DBMS (sistemi di database) e i Data Warehouse.

Il compito principale dei DBMS è quello di eseguire l’elaborazione delle transazioni e delle query online. Questi sistemi sono chiamati On Line Transaction Processing (OLTP) e prevedono maggiormente operazioni di aggiornamento dei database e transazioni di pochi dati grezzi (la transazione rappresenta l’unità atomica del cambiamento di stato in un database relazionale, come l’inserimento, la cancellazione, ecc...).

I sistemi di Data Warehouse, invece, sono in grado di organizzare e presentare i dati in vari formati per soddisfare le diverse esigenze degli utenti. Questi sistemi sono noti come On Line Analytical Processing (OLAP) e prevedono maggiormente operazioni di lettura dei dati contenuti nei database ed un numero elevato di dati (aggregati e consolidati).

Un Data Warehouse richiede uno schema orientato all’argomento, che faciliti l’analisi dei dati. A tale scopo possiamo distinguere due differenti rappresentazioni relazionali del Data Warehouse:

• Modello a stella. Il paradigma di modellazione più comune è lo schema a stella, in cui il Data Warehouse contiene una grande tabella centrale (detta tabella dei fatti), che comprende la maggior parte dei dati, ed una serie di tabelle secondarie più piccole (dette tabelle delle dimensioni), una per ogni dimensione. La tabella dei fatti è collegata alle tabelle delle dimensioni attraverso una chiave uni-