Data Mining

13 Jan 2007

Perché il Data Mining?
- Tutte le organizzazioni accumulano quantità sempre crescenti di dati, a cui spesso non si possono applicare le tecniche di analisi tradizionali:
  - grosse dimensioni dei datasets
  - natura non tradizionale dei dati
  - nuovi problemi non formulabili con approcci tradizionali
- In ambito aziendale/commerciale:
  - Vengono raccolti quotidianamente volumi enormi di dati relativi ad acquisti/vendite, transazioni con bancomat/carte di credito, attività di e-commerce, etc.
  - C'è la necessità di "interpretare" questi dati per anticipare le tendenze del mercato e fornire ai clienti servizi sempre più specializzati e personalizzati.
- In ambito scientifico:
  - Nuove sorgenti di dati (es.: satelliti, telescopi) ed esperimenti "data-intensive" (es.: in biologia molecolare) producono datasets estremamente complessi (elevata dimensionalità, rumore, dati spazio-temporali).
  - C'è la necessità di "filtrare" i dati e di individuare opportuni modelli di rappresentazione.
- Il volume e la complessità dei dati raccolti rende praticamente impossibile un'analisi "manuale" dei dati stessi.
- Spesso ci sono nei dati informazioni "nascoste", che non sarebbero facilmente individuabili da un analista umano.
Data Mining
- "Non-trivial extraction of implicit, previously unknown and potentially useful information from data"
- "Exploration and analysis, by automatic or semi-automatic means, of large quantities of data in order to discover meaningful patterns"
- Processo di analisi, automatico o semi-automatico, che permette di:
  - estrarre informazioni/conoscenze da grossi repository di dati
  - formulare modelli previsionali
- Non tutte le operazioni di analisi/ricerca sui dati vengono considerate attività di data mining
  - La ricerca di specifici record attraverso un DBMS o il recupero di pagine Web tramite un motore di ricerca, ad esempio, sono attività di "information retrieval"
  - Un processo di data mining è orientato non al recupero di specifiche informazioni ma all'individuazione di regolarità o "patterns" nei dati
- Il Data Mining è parte integrante del processo di Knowledge Discovery in Databases (KDD) - (conversione di "raw data" in informazione utile)
Data Mining e Knowledge Discovery
- Input Data
  - diversi formati (file, tabelle relazionali), repository centralizzato o distribuito
  - Data Pre-processing
    - trasformazione dei raw input data in un formato appropriato per la successiva analisi (es: fusione di più sorgenti di dati, eliminazione rumore, selezione di records e/o features)
  - Data Mining
    - applicazione di specifici algoritmi e tecniche di analisi
  - Data Post-processing
    - validazione e interpretazione dei risultati, al fine di permetterne l'integrazione nei sistemi di supporto alle decisioni ("Closing the loop")
Origini del Data Mining
- Il Data Mining fa ricorso a idee, tecniche e metodologie sviluppate in svariati settori:
  - AI, Machine Learning, Pattern Recognition, Statistics, Database systems, Parallel Computing, Distributed Computing
Campi di applicazione
- Marketing
- Finanza/Banche
- Discipline scientifiche:
  - Astronomia/Astrofisica
  - Ricerca chimico/farmaceutica
  - Biologia molecolare
  - Telerilevamento e metereologia
"Sfide" del Data Mining
- Il Data Mining non mira a rimpiazzare le tradizionali tecniche di analisi ma a superare le limitazioni che esse incontrano nell'elaborazione dei nuovi datasets generati dalle moderne applicazioni
- Algoritmi scalabili
  - dimensioni dei datasets: gigabytes, terabytes o addirittura petabytes!
  - specifiche strutture dati e strategie di ricerca
  - computazione parallela e distribuita
- Elevata dimensionalità
  - datasets con centinaia o migliaia di attributi ("features")
  - correlazione tra le features
  - problema della complessità computazionale
- Dati eterogenei e "complessi"
  - attributi eterogenei in uno stesso dataset
  - dati complessi (dati semi-strutturati, spazio-temporali, etc)
  - relazioni complesse tra i dati
- Dati distribuiti
  - ottimizzazione della computazione distribuita
  - problematiche connesse alla sicurezza ed alla proprietà dei dati
- Analisi "non tradizionale"
- analisi non guidata da un'ipotesi formulata a priori
- necessità di automatizzare la generazione e la verifica di molteplici ipotesi
- distribuzione dei dati non casuale
Data Mining Tasks
- Tasks predittivi
  - descrizione
    - l'obiettivo è predire il valore di un particolare attributo (variabile dipendente o target) sulla base dei valori assunti dagli altri attributi (variabili indipendenti)
    - sono basati sulla costruzione di un modello che esprime il target in funzione delle variabili indipendenti:
      - target discreto
        
        modello/regola di classificazione
      - target continuo
        
        modello/regola di regressione
    - Il modello viene indotto, con metodi statistici o tecniche di apprendimento automatico (machine learning), da un training set in cui la variabile target ha valori noti. (Data Mining Supervisionato)
  - Classificazione
    - Problema:
      - data una collezione di records (training set), ciascuno descritto da un insieme di attributi, uno dei quali rappresenta il target o classe, occorre trovare un modello che esprima la classe in funzione dei valori assunti dagli altri attributi
    - Obiettivo:
      - il modello deve essere in grado di classificare nuovi records (ovvero di predirne la classe di appartenenza) il più accuratamente possibile
        
        le prestazioni del modello vengono valutate su un test dataset
  - Regressione
  - Anomaly Detection
- Tasks descrittivi
  - descrizione
    - l'obiettivo è derivare patterns (regolarità, correlazioni, clusters) che esprimano le relazioni presenti tra i dati
    - Non esiste un training set da cui indurre un modello che descriva i dati.
    - I dati vengono esplorati senza ipotesi preventive, lasciando che siano i dati stessi a "suggerire" la loro struttura (pattern). (Data Mining Non Supervisionato)
- Data Mining Tasks
  - Clustering
    - Problema:
      - dato un insieme di oggetti/eventi, ciascuno caratterizzato da un insieme di attributi e data una misura di similarità tra gli oggetti in esame, occorre partizionare gli oggetti in clusters, tali che i membri di ciascun cluster siano il più possibile simili tra loro e dissimili da quelli degli altri clusters
    - Esempio
      - Per i records rappresentati come punti in uno spazio tridimensionale una misura di similarità è rappresentata dalla distanza euclidea (distanze intra-cluster minimizzate e distanze inter-cluster massimizzate).
  - Regole di associazione
    - Problema:
      - dato un insieme di records, ciascuno dei quali contiene un certo numero di items tratti da una determinata collezione, occorre individuare delle regole di dipendenza che predicano l'occorrenza di un item in base all'occorrenza di altri items
    - Esempio
      - Regole per Market Basket:
        
        {Milk} --> {Coke}
        
        {Diaper, Milk} --> {Beer}
  - Ricerca di pattern sequenziali
Dataset
- Collezione di data objects (records, points, vectors, etc) ciascuno descritto da un insieme di attributi (features, variables, fields, etc)
- In una tabella nelle colonne si hanno Attributes/Features e nelle righe Objects/Records
- Attributo
  - Proprietà/caratteristica di un oggetto
  - può variare da oggetto ad oggetto (es: il colore degli occhi varia da persona a persona)
  - può variare nel tempo (es: la temperatura di un oggetto assume valori diversi in diversi istanti)
  - Valori di un attributo
    - Ad un attributo si assegnano valori (numeri o simboli) definiti attraverso una scala di misura
      - ad uno stesso attributo possono essere associati insiemi di valori differenti (a seconda della scala di misura applicata)
      - uno stesso insieme di valori, viceversa, può essere associato ad attributi differenti
    - i valori usati per rappresentare un attributo possono avere proprietà che non si applicano all'attributo stesso
    - o, viceversa, un attributo può avere delle proprietà che non sono espresse dai valori che lo rappresentano
    - Esempio
      - Possiamo usare dei valori interi per rappresentare matricola ed età degli studenti, ma sugli interi sono definite operazioni (somma, media, etc) che non si applicano alle matricole
      - sugli interi non è definito un limite superiore, che invece è proprio dell'età
  - Tipo di un attributo
    - Esprime le proprietà intrinseche dell'attributo, indipendentemente dai valori che lo rappresentano.
    - Ci permette di verificare quali proprietà dei valori misurati sono consistenti con le proprietà dell'attributo.
    - Può essere definito in base alle operazioni ammesse sull'attributo:
      - tipi categorici o qualitativi (rappresentazione tramite simboli) - discreti
        
        Nominal
        
        valori distinguibili (=, ≠)
        
        es: colore occhi, sesso, codice avviamento postale, codici identificativi in genere
        
        Ordinal
        
        valori distinguibili (=, ≠) e ordinabili (<, ≤, >, ≥)
        
        es: numero civico, taglia abiti (small, medium, large), voti (sufficiente, buono, etc)
      - tipi numerici o quantitativi (rappresentazione numerica) - continui
        
        Interval
        
        valori distinguibili (=, ≠) e ordinabili (<, ≤, >, ≥)
        
        è inoltre definibile un'unità di misura, rispetto alla quale calcolare somme o differenze (+, -)
        
        es: temperatura in gradi Celsius o Fahrenheit, data (anno)
        
        Ratio
        
        valori distinguibili (=, ≠) e ordinabili (<, ≤, >, ≥)
        
        si possono definire le operazioni di somma/differenza (+, -) e di moltiplicazione/divisione (*, /)
        
        es: temperature in Kelvin, età, valori monetari, lunghezze, etc.
    - Può anche essere descritto in termini di trasformazioni che non cambiano il significato dell'attributo (permissible transformations)
    - Gli attributi si distinguono inoltre per il numero di valori che possono assumere:
      - attributi discreti
        
        numero finito o infinità numerabile di valori
        
        Sono generalmente rappresentati tramite valori interi.
        
        Esempi: codici identificativi, conteggi, etc.
        
        Caso particolare: attributi binari (due soli valori: 0/1, yes/no, true/false)
      - attributi continui
        
        i valori sono numeri reali
        
        Sono generalmente rappresentati da variabili floating-point.
        
        In pratica, possono essere misurati con precisione limitata.
        
        Esempi: temperature, lunghezze, etc.
    - Gli attributi categorici (nominal e ordinal) sono tipicamente discreti, mentre gli attributi numerici (interval e ratio) sono continui. Fanno eccezione gli attributi count, di tipo ratio, che sono sono discreti
  - Attributi asimmetrici
    - La maggior parte dei valori è uguale a zero (o è nulla).
    - Ai fini dell'analisi dei dati, si considerano significativi solo i valori diversi da zero.
    - Caso particolare: attributi binari asimmetrici
- Caratteristiche di un dataset
  - Dimensionality (numero di attributi)
    - Al crescere del numero di attributi, aumentano le difficoltà nell'analisi dei dati ("curse of dimensionality")
    - Spesso si rende necessaria, in fase di pre-processing, una riduzione del numero di attributi (dimensionality reduction / feature selection)
  - Sparsity (presenza di attributi asimmetrici)
    - Prevalenza di valori nulli.
    - Solo i valori non nulli sono significativi ai fini dell'analisi:
      - analisi semplificata
      - risparmio di spazio e tempo
  - Resolution (risoluzione dei valori misurati)
    - Spesso le proprietà dei dati risultano differenti a diverse risoluzioni.
    - A seconda della risoluzione, un determinato pattern può essere visibile o meno.
    - Esempi: misure geografiche, climatiche, etc.
- Tipi di datasets
  - Principali categorie:
    - Record data
      - Collezione di records descritti dallo stesso insieme di attributi
      - Memorizzazione in files o tabelle relazionali
      - Particolari tipologie:
        
        Transaction Data
        
        Ogni record (transaction) contiene un insieme di items
        
        Il dataset può essere visto come una collezione di records descritti da attributi asimmetrici.
        
        Es: attributi binari che indicano se un certo prodotto è stato acquistato o meno
        
        Data Matrix
        
        Ciascun record:
        
        è descritto da uno stesso insieme di attributi numerici
        
        può essere visto come un punto (vettore) in uno spazio multi-dimensionale
        
        Il dataset può essere interpretato come una matrice M x N ("pattern matrix")
        
        Document-term Matrix
        
        Ogni documento è rappresentato come un "vettore di termini"
    - Graph-based data
      - Due casi:
        
        le relazioni tra gli oggetti sono rappresentate tramite un grafo
        
        gli oggetti stessi sono rappresentati come grafi
      - Relazioni tra gli oggetti
        
        Oggetti: nodi del grafo
        
        Relazioni tra gli oggetti: archi del grafo(direzione, peso)
        
        Esempio: pagine Web (contenuto + links ad altre pagine)
      - Oggetti rappresentati come grafi
        
        Gli oggetti con una struttura interna (insieme di componenti collegati fra loro), possono essere rappresentati sotto forma di grafo.
        
        Esempio: composti chimici
    - Ordered data
      - Esiste un ordinamento tra gli attributi.
      - Diverse tipologie:
        
        Sequential Data
        
        Una misura temporale è associata ad ogni record, oppure ad ogni attributo del record
        
        Sequence Data
        
        Il dataset consiste di una sequenza di entità (es: una sequenza di parole o lettere)
        
        Simili ai Sequential Data, ma non è annotata alcuna misura temporale: l'ordinamento è determinato dalla posizione nella sequenza
        
        Esempio: sequenze genetiche (GGTTCCGCCTTCAGC...)
        
        Time Series Data
        
        Ogni record è una serie temporale, ovvero una serie di misure prese in istanti differenti.
        
        Esempio: un dataset finanziario può contenere serie temporali che registrano l'andamento dei prezzi di vari prodotti.
        
        Autocorrelazione temporale delle misure
        
        Spatial Data
        
        Gli oggetti del dataset sono caratterizzati da attributi spaziali (es: posizione, area)
        
        Esempio: misure climatiche (temperatura, precipitazioni, pressione) in diverse località.
        
        Autocorrelazione spaziale delle misure
        
        Spatio-Temporal Data
        
        Gli oggetti del dataset sono caretterizzati da attributi spaziali e temporali
        
        Esempio: Temperatura media mensile a seconda delle aree geografiche
Record e Non-Record Data
- La maggior parte degli algoritmi di Data Mining sono record-oriented.
- Non-Record Data possono essere rappresentati come Record Data (estraendo da ciascun oggetto opportune features), ma non sempre si riescono riprodurre tutte le informazioni contenute nei dati originali
Qualità dei dati
- Spesso i dati da analizzare sono affetti da problemi quali: rumore, valori mancanti, valori inconsistenti, duplicazioni
- Si ha la necessità di migliorare la qualità dei dati ("data cleaning") e mettere a punto algoritmi che possano "tollerare" una scarsa qualità dei dati
- La qualità dei dati può essere compromessa da errori di misura o errori nel processo di raccolta dei dati. Entrambi i tipi di errori possono essere sistematici o casuali.
  - Errori di misura
    - In statistica e nelle scienze sperimentali, la qualità delle misure è stimata attraverso i parametri:
      - precisione
        
        vicinanza di una serie di misure ripetute (relative a una stessa quantità)
      - bias
        
        deviazione sistematica delle misure dal valore reale
    - Più in generale, si utilizza il termine accuratezza per indicare il grado di prossimità tra valore misurato e valore reale.
    - Dall'accuratezza dipende il numero di cifre significative che si devono utilizzare per rappresentare le misure.
    - Rumore
      - Componente casuale di un errore di misura.
      - Implica:
        
        modifica/distorsione dei valori originali
        
        aggiunta di misure spurie
      - Nell'analisi di dati con componenti temporali o spaziali, si applicano specifiche tecniche di elaborazione dei segnali o delle immagini per ridurre il rumore o estrarre patterns significativi anche in presenza di rumore.
      - In generale, il rumore è difficile da eliminare e occorre impiegare algoritmi capaci di "tollerarlo".
    - Outliers
      - Oggetti o valori "anomali" (da non confondere col rumore)
    - Valori mancanti
      - Talvolta non si dispone dei valori di alcuni attributi:
        
        valori non raccolti (es: non tutte le persone dichiarano la loro età)
        
        attributi non applicabili a tutti gli oggetti (es: ad alcune persone, come i bambini, non è applicabile l'attributo "reddito")
      - Gestione valori mancanti
        
        Eliminazione oggetti con valori mancanti
        
        strategia applicabile solo se gli oggetti con valori mancanti sono pochi
        
        Eliminazione attributi con valori mancanti
        
        richiede cautela: gli attributi eliminati potrebbero essere critici per l'analisi
        
        Stima valori mancanti
        
        i valori mancanti vengono stimati in base ai valori assunti dagli oggetti più vicini
        
        es: media valori oggetti vicini (per attributi numerici), valore più frequente tra i vicini (per attributi categorici)
        
        Ignorare valori mancanti durante l'analisi
        
        molte tecniche di data mining possono essere adattate per trascurare gli attributi con valori mancanti
        
        es: negli algoritmi di clustering, si può calcolare la similarità tra due oggetti non considerando gli attributi con valori mancanti
    - Valori inconsistenti
      - Dovuti ad errori in fase di raccolta dei dati o, talvolta, ad errori di interpretazione/trascrizione.
      - La correzione di eventuali inconsistenze richiede, spesso, il confronto con una sorgente indipendente di informazione.
    - Dati duplicati
      - Un dataset può contenere più data objects che rappresentano lo stesso oggetto reale.
      - Data objects identici, tuttavia, possono rappresentare oggetti differenti e in questo caso la loro presenza è legittima.
      - La gestione dei duplicati è cruciale soprattutto quando si mettono insieme dati provenienti da sorgenti diverse.
    - Altre problematiche
      - Altre problematiche relative alla qualità dei dati sono legate al particolare dominio applicativo.
      - In alcuni ambiti, ad esempio, i dati "invecchiano" molto rapidamente.
      - In generale, è sempre importante verificare la rilevanza dei dati rispetto agli scopi dell'analisi da effettuare (omissione di informazioni, "sampling bias") - (occorre un esperto del dominio).
Data Pre-processing
- Aggregazione
  - Combinazione di due o più attributi/oggetti in un singolo attributo/oggetto.
  - aggregazione lungo una o più dimensioni
  - Obiettivo:
    - riduzione dimensioni dataset
    - cambiamento di scala
    - "stabilizzazione" dei dati
  - possibile perdita di dettagli interessanti
- Campionamento
  - Selezione di un sotto-insieme di data objects.
  - Il sotto-insieme selezionato (campione) deve essere rappresentativo, ovvero deve avere approssimativamente le stesse proprietà (di interesse) del dataset originale.
  - Tecniche di campionamento
    - Simple random sampling
      - stessa probabilità di selezionare un qualunque oggetto del dataset
    - Due varianti:
      - sampling without replacement
        
        quando un oggetto è selezionato, viene rimosso dal dataset originale
      - sampling with replacement
        
        gli oggetti selezionati non vengono rimossi dal dataset e possono quindi essere selezionati di nuovo
    - Se le dimensioni del campione sono piccole rispetto a quelle del dataset originale, i due metodi producono campioni grosso modo equivalenti.
    - Il campionamento with replacement è più semplice da analizzare perché la probabilità di selezionare un oggetto rimane costante durante l'intero processo di campionamento.
    - Quando il dataset contiene diversi tipi (classi) di oggetti, occorre adottare una tecnica di campionamento che permetta di rappresentare adeguatamente anche i tipi meno frequenti:
      - Stratified sampling
        
        il dataset è suddiviso in tante partizioni quanti sono i tipi da rappresentare
        
        da ciascuna partizione è estratto casualmente:
        
        un numero fisso di oggetti
        
        un numero di oggetti proporzionale alla dimensione della partizione
  - Dimensione del campione
    - Al diminuire della dimensione del campione, dimuinuisce l'informazione estraibile dai dati
    - almeno un punto di ogni cluster deve appartenere al campione
    - La dimensione ottimale del campione:
      - spesso è difficilmente calcolabile a priori
      - può essere determinata con un approccio incrementale
    - Es: Costruiamo un modello previsionale su un campione di dati:
      - l'accuratezza del modello aumenta al crescere della dimensione del campione
      - quando la dimensione è ottimale, l'accuratezza non aumenta più
- Riduzione della dimensionalità
  - Alcuni tipi di dataset sono caratterizzati da centinaia o migliaia di attributi (es: micro-array data, document-term matrices)
  - Per poter estrarre pattern significativi dai dati, spesso è indispensabile ridurre il numero di attributi (dimensionality).
  - Curse of Dimensionality
    - All'aumentare del numero di attributi, i dati diventano sempre più "sparsi":
      - classificazione: pochi esempi per l'induzione del modello
      - clustering: densità e distanza tra i punti risultano meno significative
  - Riducendo il numero di attributi:
    - diminuiscono rumore e features irrilevanti
    - si ottengono modelli più facilmente interpretabili
    - si riducono occupazione di memoria e tempi di calcolo
  - Il numero degli attributi può essere ridotto:
    - creando nuovi attributi che sono una combinazione di quelli originali (dimensionality reduction)
    - selezionando un sotto-insieme degli attributi originali (feature selection)
  - Le tecniche più comunemente adottate derivano dall'algebra lineare
  - Idea di base: proiettare i dati in un nuovo spazio con un numero più basso di dimensioni
  - Principal Components Analysis (PCA)
    - Costruzione di nuovi attributi (componenti principali) che:
      - sono combinazioni lineari degli attributi originali
      - sono ortogonali tra loro
      - "catturano" la massima variazione nei dati
      - è applicabile ad attributi continui
- Selezione degli attributi
  - Mira a ridurre la dimensionalità eliminando:
    - attributi ridondanti (rappresentano informazioni derivabili da altri attributi)
    - attributi irrilevanti (nessuna informazione utile ai fini dell'analisi)
  - Approccio "ideale":
    - testare tutti i possibili sotto-insiemi di attributi, usandoli come input dell'algoritmo di data mining di interesse, e selezionare il sotto-insieme che permette di ottenere i risultati migliori
    - nella maggior parte dei casi ciò non è praticabile
  - Approcci più comuni:
    - Embedded methods
      - selezione interna all'algoritmo di data mining
      - es: algoritmi per l'induzione di alberi decisionali
    - Filter methods
      - selezione effettuata a priori, con un metodo indipendente dall'algoritmo di data mining che verrà applicato successivamente (scheme-independent selection)
    - Wrapper methods
      - confronto tra diversi sotto-insiemi di attributi
      - la "bontà" di ciascun sotto-insieme è valutata usando lo stesso algoritmo di data mining scelto per l'analisi (scheme-specific selection)
  - Il processo di selezione, in generale, implica:
    - 1) Una strategia per l'esplorazione dello spazio degli attributi
      - greedy search
        
        forward selection
        
        backward elimination
    - 2) Un criterio per valutare la "bontà" di ciascun sotto-insieme di attributi ("scheme-independent", "scheme-specific")
    - 3) Un criterio per l'interruzione della ricerca (ottimizzazione locale)
- Creazione di nuovi attributi
  - Spesso è possibile creare, a partire dagli attributi originali, nuovi attributi che "catturano" meglio le informazioni più importanti.
  - Metodologie:
    - estrazione di features
      - Creazione di un nuovo insieme di features a partire dai raw data originali.
      - Es: Estrazione di features di alto livello per un insieme di immagini codificate in termini di pixels.
      - Tecniche fortemente dipendenti dal dominio.
    - "mapping"dei dati in un nuovo spazio
      - Talvolta le informazioni "nascoste" nei dati diventano visibili sotto una nuova rappresentazione dei dati stessi.
      - Es: le serie temporali spesso contengono patterns periodici che possono essere individuati applicando ai dati opportune trasformazioni (Fourier, wavelet)
    - costruzione di features
      - Talvolta le features originali vengono combinate per ottenere nuove features, più adatte all'applicazione di una specifica tecnica di data mining.
      - La combinazione, nella maggior parte dei casi, è effettuata da un esperto del dominio.
- Discretizzazione e Binarizzazione di attributi continui
  - Alcune tecniche di data mining (es: algoritmi di classificazione) richiedono attributi categorici (discretizzazione).
  - Altre tecniche (es: regole di associazione) richiedono attributi binari (binarizzazione).
  - Scelta del numero e la posizione degli split points (xi):
    - approcci non supervisionati
      - Non sfruttano l'informazione sulla classe.
      - Approcci più comuni:
        
        intervalli di uguale ampiezza
        
        intervalli di uguale frequenza
        
        clustering (K-means)
    - approcci supervisionati
      - Sfruttano l'informazione della classe.
      - Idea di base:
        
        massimizzare la "purezza" di ciascun intervallo (Entropy-based discretization)
  - Entropia
    - L'entropia di un intervallo è una misura della purezza dell'intervallo stesso:
      - se un intervallo contiene solo valori di una classe, la sua entropia è zero
      - se tutte le classi sono equamente distribuite nell'intervallo, l'entropia è massima
    - entropia dell'intervallo i-esimo
      - e_i = - Σ_j=1,k (p_ij log₂ p_ij)
        
        k : numero di classi
        
        p_ij = m_ij / m_i : probabilità della classe j-esima nell'intervallo i-esimo
    - entropia totale
      - e = - Σ_i=1,n (w_i e_i)
        
        n : numero di intervalli
        
        w_i = m_i / m : la frazione di valori nell'intervallo i-esimo
  - Entropy-based discretization
    - Si creano inizialmente due intervalli tali da minimizzare l'entropia.
    - L'intervallo con entropia maggiore viene poi ulteriormente partizionato.
    - Il processo è ripetuto fino a raggiungere il numero desiderato di intervalli (o fino a soddisfare un determinato criterio di stop).
- Trasformazione degli attributi
  - Trasformazione applicata a tutti i valori dell'attributo.
  - Due tipi di trasformazione:
    - trasformazioni funzionali semplici
      - Esempi:
        
        la trasformazione x → |x| può essere applicata se non si è interessati al segno di una variabile
        
        la trasformazione x → log₁₀(x) può essere applicata per ridurre il range di una variabile
      - N.B. Occorre valutare attentamente tutte le implicazioni di una trasformazione!
        
        Ad esempio:
        
        La trasformazione conserva l'ordinamento dei valori?
        
        Qual'è l'effetto della trasformazione sullo zero? etc...
    - normalizzazione
      - L'obiettivo è far sì che l'intero insieme dei valori assunti da una variabile soddisfi una determinata proprietà
      - Esempio: x' = (x - AVG(x)) / S_x
        
        si ottiene una nuova variabile con valor medio pari a 0 e deviazione standard pari a 1
Misure di similarità/dissimilarità
- Le misure di similarità/dissimilarità sono alla base di numerose tecniche di data mining (concetto di "prossimità")
- Similarità
  - Misura numerica della "somiglianza/vicinanza" tra due oggetti.
  - È tanto più alta quanto più gli oggetti sono vicini/simili.
  - È solitamente compresa tra 0 (nessuna similarità) e 1 (similarità completa).
- Dissimilarità (o distanza)
  - Misura numerica che esprime quanto due oggetti sono differenti/distanti tra loro.
  - È tanto più bassa quanto più gli oggetti sono simili.
  - È solitamente compresa nell'intervallo [0,1] o nell'intervallo [0, ∞].
- Trasformazioni
  - Talvolta può essere utile convertire una misura di similarità in una misura di dissimilarità, o viceversa.
  - Inoltre, le misure di similarità/dissimilarità vengono spesso ridefinite/trasformate perché assumano valori compresi in un certo intervallo (es: [0,1]).
  - Es: per portare i valori di una misura di prossimità nell'intervallo [0, 1]:
    - p' = (p - min_p) / (max_p - min_p)
    - (quando il range originale è finito)
  - Es: per convertire una misura di dissimilarità (d) in una misura di similarità (s):
    - (in generale, si può usare una funzione monotona decrescente)
    - s = 1 - d, d ∈ [0, 1]
    - s = -d
    - s = 1/(1+d)
    - s = e^-d
  - N.B. Quando si applica una determinata trasformazione occorre tener conto di possibili complicazioni, quali:
    - distorsione della scala (in caso di trasformazioni non lineari)
    - alterazione del significato originale della misura
- Il grado di similarità/dissimilarità (prossimità) tra due oggetti è misurato sulla base della similarità/dissimilarità tra attributi corrispondenti degli oggetti stessi.
  - Due casi:
    - prossimità tra singoli attributi
      - Attributi di tipo nominal:
        
        Similarità:
        
        s(x,y) = 1, se x = y ; 0, se x ≠ y
        
        Dissimilarità:
        
        d(x,y) = 0, se x = y ; 1, se x ≠ y
      - Attributi di tipo ordinal:
        
        occorre tener conto dell'ordinamento
        
        {scarso, mediocre, sufficiente, buono, ottimo}
        
        {scarso = 0, mediocre = 1, sufficiente = 2, buono = 3, ottimo = 4}
        
        d(x,y) = | x -y |
        
        d(x,y) = | x -y | / (n -1) ; nel range [0, 1]
        
        s(x,y) = 1 - d(x,y)
        
        n : numero dei valori
      - Attributi di tipo interval/ratio:
        
        (tipicamente il range è [0, ∞])
        
        d(x,y) = | x - y |
        
        s = -d
        
        s = 1 / (d+1)
        
        s = e^-d
        
        s = 1 - ((d - min_d) / (max_d - min_d))
    - prossimità tra oggetti con più attributi
      - La similarità/dissimilarità tra due oggetti con più attributi è tipicamente definita combinando opportunamente le similarità/dissimilarità tra le coppie di attributi corrispondenti
      - Distanza Euclidea
        
        d(x,y) = SQRT(Σ_k=1,n(x_k - y_k)²)
        
        x e y sono punti (vettori) in uno spazio n-dimensionale
        
        x_k e y_k rappresentano la k-esima componente (attributo) di x e y
      - Distanza di Minkowski
        
        Generalizzazione della distanza Euclidea
        
        d(x,y) = (Σ_k=1,n|x_k - y_k|^r)^1/r
        
        r = 1 (L1 norm)
        
        Es: distanza di Hamming
        
        r = 2 (L2 norm)
        
        Distanza Euclidea
        
        r → ∞ (Lmax o L∞ norm)
        
        Massima differenza tra le componenti
      - Proprietà di una distanza (metrica)
        
        d(x,y) ≥ 0, per ogni x e y
        
        d(x,y) = 0, solo se x = y
        
        d(x,y) = d(y,x), per ogni x e y
        
        d(x,z) ≤ d(x,y) + d(y,z), per ogni x, y e z
      - Proprietà di una misura di similarità
        
        s(x,y) = 1, se x= y (0 ≤ s ≤ 1)
        
        s(x,y) = s(y,x), per ogni x e y
        
        una misura di similarità può talvolta essere convertita in una metrica
      - Coefficienti di similarità
        
        misure di similarità per dati binari
        
        f00 : numero di attributi con valore 0 sia in x che in y
        
        f01 : numero di attributi con valore 0 in x e 1 in y
        
        f10 : numero di attributi con valore 1 in x e 0 in y
        
        f11 : numero di attributi con valore 1 sia in x che in y
        
        Simple Matching Coefficient (SMC)
        
        SMC = (f11 + f00) / (f01 + f10 + f11 + f00)
        
        Jaccard Coefficient
        
        J = f11 / (f01 + f10 + f11)
        
        misure di similarità per vettori generici
        
        Cosine Similarity
        
        Ignora gli attributi che valgono 0 in entrambi gli oggetti (come Jaccard), ma può essere applicata anche a vettori non binari
        
        è utilizzata per confrontare documenti
        
        non tiene conto della lunghezza dei vettori
        
        vale 1 quando l'angolo tra i due vettori è zero
        
        cos(x,y) = (x · y) / (||x|| · ||y||) = (x / ||x||) · (y / ||y||)) = x' · y'
        
        x · y = Σ_k=1,n(x_k,y_k)
        
        ||x|| = SQRT(Σ_k=1,n x_k²)
        
        Pearson's correlation
        
        Esprime l'esistenza di una relazione lineare tra gli attributi dei due oggetti:
        
        corr(x,y) = cov(x,y) / (dev_stand(x) · dev_stand(y) = Sxy / (Sx · Sy)
        
        Sx = SQRT((1/n-1) · Σ_k=1,n(x_k - AVG(x))²)
        
        Sy = SQRT((1/n-1) · Σ_k=1,n(y_k - AVG(y))²)
        
        Sxy = (1/n-1) · Σ_k=1,n(x_k - AVG(x))²)(y_k - AVG(y))
        
        Calcolo della prossimità
        
        Problematiche:
        
        attributi con scale differenti
        
        la variabile con il range di valori più grande può "dominare" il risultato del calcolo
        
        normalizzazione : x' = (x - AVG(x)) / Sx
        
        oggetti con diversi tipi di attributi
        
        le misure finora descritte non sono applicabili perché assumono che gli attributi siano omogenei
        
        possiamo calcolare separatamente la prossimità tra i singoli attributi e poi combinare i risultati parziali (ad esempio, calcolando la media delle prossimità tra i singoli attributi)
        
        s(x,y) = (Σ_k=1,n δ_kS_k(x,y)) / (Σ_k=1,nδ_k)
        
        s_k è la silimarità rispetto al k -esimo attributo (range [0,1])
        
        δ_k =
        
        0 se il k -esimo attributo è asimmetrico e ha valore 0 in entrambi gli oggetti
        
        0 se in corrispondenza del k -esimo attributo c'è un valore mancante
        
        1 altrimenti
        
        attributi con pesi differenti
        
        s(x,y) = (Σ_k=1,n w_kδ_kS_k(x,y)) / (Σ_k=1,n δ_k)
        
        w_k : peso del k -esimo attributo
        
        la somma dei pesi è pari ad 1:
        
        d(x,y) = (Σ_k=1,n w_k|x_k - y_k|^r)^1/r
Alberi
- Formulazione del problema
  - Input:
    - collezione di records, ciascuno caratterizzato da un insieme di attributi o features(x) e da una label di classe(y)
    - N.B. y deve essere un attributo discreto
  - L'obiettivo è definire una funzione (modello di classificazione) che associa ad ogni insieme di valori degli attributi (x) un valore della label di classe (y)
    - attribute set (x) → classification model → class label (y)
  - Un modello di classificazione rappresenta uno strumento per:
    - descrivere i dati di uno specifico dominio
    - classificare nuovi dati nell'ambito dello stesso dominio
    - N.B. Le tecniche di classificazione si prestano bene a descrivere/prevedere classi binarie o di tipo nominal
      - non tengono conto dell'ordinamento fra le classi né di altre relazioni (es: super-classe/sotto-classe)
- Induzione del modello
  - Si utilizza un dataset di addrestramento (training set) in cui i valori della label di classe sono noti
  - il Learning Algorithm genera il modello analizzando il training set ed identificando le relazioni tra attributi e label di classe
  - Il modello così generato deve essere in grado non soltanto di descrivere il training set ma anche di predire correttamente la classe di nuovi records non "etichettati" (generalization capability)
- Valutazione del modello
  - Le prestazioni del modello sono valutate sulla base della percentuale di records correttamente classificati nel test set:
    - Accuratezza = num predizioni corrette / num predizioni
    - Error rate = num predizioni sbagliate / num predizioni
  - Matrice di confusione:
    - Nelle colonne si indicano le classi previste dal modello
    - Nelle righe si indicano le classi reali
    - Le previsioni corrette rimangono tutte nella diagonale principale
Tecniche di classificazione
- Alberi decisionali
- Classificatori a regole
- Nearest-Neighbor
- Classificatori Bayesiani
- Reti neurali
- Support Vector Machines (SVM)
Alberi decisionali
- È una delle tecniche di classificazione maggiormente utilizzate.
- Permette di rappresentare con un albero un insieme di regole di classificazione.
- Struttura gerarchica che consiste di un insieme di nodi, correlati da archi (rami) orientati ed "etichettati".
  - Si hanno tre tipi di nodi:
    - nodo radice (attributo)
      - nessun ramo entrante, due o più rami uscenti etichettati con i possibili valori dell'attributo
    - nodi interni (attributi)
      - un ramo entrante, due o più rami uscenti etichettati con i possibili valori dell'attributo
    - nodi terminali - foglie (class labels)
      - un ramo entrante, nessun ramo uscente
- Ciascun percorso radice-foglia rappresenta una regola di classificazione
  - (if-then-else o switch-case annidati)
- Induzione dell'albero
  - Più alberi possono descrivere gli stessi dati (aumentano esponenzialmente con il numero di attributi).
  - La ricerca dell'albero ottimale è un problema intrattabile.
  - Esistono euristiche (basate su criteri di ottimizzazione locale) che permettono di indurre un albero sufficientemente "piccolo" e accurato.
    - L'idea alla base di tali euristiche è quella di scegliere come radice dell'albero l'attributo capace di discriminare meglio le classi.
    - I sotto-alberi sono costruiti applicando ricorsivamente lo stesso criterio
  - Algoritmi:
    - Hunt's Algorithm
    - CART
    - ID3, C4.5
    - SLIQ,SPRINT
  - Hunt's Algorithm
    - Sia D un training set di records con struttura (x,y), dove x è un insieme di attributi e y = {y1, y2, ..., yc} è la label di classe.
    - Indichiamo con Dt l'insieme di training records che "raggiungono" il t-esimo nodo dell'albero.
    - Etichettiamo provvisoriamente il nodo t con una label uguale alla classe predominante in Dt e distinguiamo due casi:
      - Se tutti i records in Dt appartengono alla stessa classe yt, allora il nodo t è una foglia (nodo puro) con etichetta yt.
      - Se invece Dt contiene records appartenenti a più classi, si sceglie una condizione di test, definita sui valori di un attributo xi, per partizionare Dt in sottoinsiemi più piccoli.
    - Un nodo figlio è creato per ogni risultato della condizione di test, ed i records in Dt sono distribuiti nei figli a seconda del risultato del test.
    - N.B. Può capitare che ad un nodo figlio non sia associato nessun record ("nodo vuoto"), in questo caso il nodo figlio diventa una foglia con label uguale alla classe predominante tra i records associati al nodo padre
    - N.B. Può anche capitare che tutti i records in Dt abbiano gli stessi valori degli attributi e non possano quindi essere partizionati, in questo caso il nodo t diventa una foglia con label uguale alla classe predominante in Dt
  - Strategia greedy:
    - ad ogni passo dell'algoritmo, i records sono partizionati sulla base di un determinato criterio di ottimizzazione
  - Punti chiave:
    - Come partizionare i records? (Come specificare la condizione di test per lo split e come scegliere lo split migliore?)
    - Quando interrompere la procedura?
  - Specifica della condizione di test
    - Attributi binari
      - due sotto-insiemi
    - Attributi non binari:
      - la formulazione della condizione di test dipende del tipo di attributo:
        
        attributi di tipo nominal
        
        Multi-way split: tanti sotto-insiemi quanti sono i valori dell'attributo
        
        Binary split: si partiziona sempre in due parti (2^k-1 possibilità)
        
        attributi di tipo ordinal
        
        Multi-way split: tanti sotto-insiemi quanti sono i valori dell'attributo
        
        Binary split: si partiziona sempre in due parti e occorre tener conto dell'ordinamento
        
        attributi continui
        
        Binary split: (A < v) OR (A ≥ v)
        
        Multi-way split: v_i ≤ A ≤ v_i+1 ; i=1,...,K
  - Scelta dello split migliore
    - La "bontà" di uno split può essere valutata con diverse misure, definite in termini della distribuzione delle classi prima e dopo lo split.
    - L'obiettivo è massimizzare il grado di "purezza" di ciascun nodo
      - Massima purezza di un nodo
        
        tutti i records appartengono alla stessa classe
      - Massima impurezza di un nodo
        
        records equamente distribuiti nelle due classi
    - Misure di impurezza
      - Indice di Gini
        
        GINI(t) = 1 - Σ_j(p(j|t))²
        
        p(j|t) è la frazione di records associati al nodo t che appartengono alla classe j
        
        Massimo: 1 -1/n_c (records equamente distribuiti tra le classi)
        
        Minimo: 0 (tutti i records appartengono alla stessa classe)
      - Entropia
        
        Entropy(t) = -Σ_j(p(j|t)log₂p(j|t))
        
        Massimo: log₂n_c (records equamente distribuiti tra le classi)
        
        Minimo: 0 (tutti i records appartengono alla stessa classe)
      - Errore di classificazione
        
        Error(t) = 1 - max_jp(j|t)
        
        Massimo: 1 -1/n_c(records equamente distribuiti tra le classi)
        
        Minimo: 0 (tutti i records appartengono alla stessa classe)
    - Il concetto di guadagno (gain)
      - Per valutare la "bontà" di uno split, occorre confrontare il grado di impurezza del nodo padre (I_parent) con il grado di impurezza dei nodi figli (I_i, i =1,...,k):
        
        Δ = I_parent - Σ_i=1,k (N_i/N) I_i
        
        N : record associati al padre
        
        N_i : record associati al figlio i-esimo
        
        Tanto maggiore è il guadagno (Δ), tanto più alto è il livello di separazione delle classi in seguito allo split.
        
        Nell'induzione di un albero decisionale (vedi algoritmo di Hunt), ad ogni passo, i records vengono partizionati in modo da massimizzare il guadagno
        
        N.B. Il guadagno (Δ) varia a seconda di come viene misurata l'impurezza (I) dei nodi.
        
        Se la misura di impurezza è l'entropia, il guadagno è anche detto information gain (Δ_info)
    - Information Gain
      - Usato in ID3 e C4.5
      - Δ_info = E_parent - Σ_i=1,k (N_i/N) E_i
    - Guadagno basato su GINI
      - Usato in CART, SLIQ, SPRINT
      - Δ = GINI_parent - Σ_i=1,k (N_i/N) GINI_i
    - Per gli split binari è semplice calcolare i vari indici di GINI e scegliere quello più basso relativo allo split migliore.
    - Per gli split di attributi continui occorre invece scegliere lo split point v che minimizza l'indice di GINI ma, provando tutte le varie combinazioni avremmo una complessità di O(N²), quindi vediamo un'altro approccio:
      - per ridurre la complessità, i records del training set vengono ordinati in base ai valori di un attributo O(NlogN), il punto medio tra due valori ordinati adiacenti è assunto come possibile split point (v)
      - si calcolano quindi gli indici di GINI relativi ad ogni split-point e si sceglie quello minimo.
  - Misure di impurezza: osservazioni
    - Misure come l'entropia e l'indice di GINI tendono a favorire gli splits con un alto numero di valori distinti
    - Per evitare questo problema, alcuni algoritmi (es: CART) esprimono sempre le condizioni di test sugli attributi in forma binaria.
    - In altri algoritmi (es: C4.5), invece, la definizione del guadagno (Δ) è modificata per tener conto del numero di nodi generati in seguito allo split (gain ratio)
  - Gain Ratio
    - GainRatio = Δ_info / SplitInfo
      - SplitInfo = - Σ_i=1,k p_i log₂p_i
      - p_i = N_i / N
      - N : record associati al padre
      - N_i : record associati al figlio i-esimo
    - Se i records del nodo padre sono equamente distribuiti tra i figli:
      - p_i = 1 / k ; SplitInfo = log₂k
      - sono penalizzate le partizioni con k grande
  - Criteri di stop (quando interrompere la procedura)
    - Un nodo non può essere partizionato quando tutti i records ad esso associati:
      - appartengono alla stessa classe
      - hanno gli stessi valori degli attributi
    - talvolta, tuttavia, può essere conveniente interrompere il partizionamento prima ("early termination")
- Induzione di un albero decisionale
  - Skeleton algorithm:
    - Input: Training set (E), Attribute set (F)
    - Divide-and-Conquer
    - TreeGrowth(Ev,F)
      - 01. if stopping_cond(E,F) = true then
      - 02. leaf = createNode()
      - 03. leaf.label = Classify(E)
      - 04. return leaf
      - 05. else
      - 06. root = createNode()
      - 07. root.test_cond = find_best_split(E,F)
      - 08. let V = {v | v is a possible outcome of root.test_cond}
      - 09. for each v ∈ V do
      - 10. Ev= {e | root.test_cond(e)= vand e ∈ E}
      - 11. child= TreeGrowth(Ev,F)
      - 12. add child as descendent of root and label the edge (root → child) as v
      - 13. end for
      - 14. end if
      - 15. return root
  - Vantaggi:
    - costruzione poco costosa anche su training sets di dimensioni considerevoli
    - classificazione di nuovi records molto rapida
    - facili da interpretare
    - nel caso di semplici datasets, l'accuratezza è comparabile con quella di altre tecniche di classificazione più complesse
  - Problematiche:
    - Gestione valori mancanti
      - Eventuali valori mancanti incidono:
        
        nel partizionamento dei records (durante l'induzione dell'albero)
        
        nella classificazione di nuove istanze
    - Frammentazione dei dati
      - Attraversando l'albero dall'alto verso il basso (dalla radice alle foglie), diminuisce il numero di records associati a ciascun nodo.
      - In corrispondenza delle foglie, il numero di records può risultare troppo basso per una rappresentazionestatisticamente significativa della classe.
      - Per evitare questo problema, si può interrompere il processo di partizionamento quando il numero di records associati a un nodo diventa inferiore a una certa soglia
    - Replicazione sotto-alberi
      - Uno stesso sotto-albero può comparire in diversi rami
    - "Decision boundary" (confine tra regioni relative a classi differenti)
      - La costruzione dell'albero implica un partizionamento dello spazio degli attributi in regioni distinte, ciascuna contenente oggetti della stessa classe.
      - Se le condizioni di test associate ai nodi sono espresse in termini di un solo attributo, i confini tra le diverse regioni risultano paralleli agli assi (limitata espressività)
      - Le classi non possono essere separate usando condizioni di test definite in termini di un solo attributo
Underfitting/Overfitting
- Training errors:
  - errori commessi sul training set
- Generalization errors:
  - errori attesi su nuovi records
- Underfitting
  - alta percentuale sia di training errors che di generalization errors
- Overfitting
  - ottime prestazioni sul training set ma scarsa capacità di generalizzazione
  - alta percentuale di generalization errors
  - può essere dovuto al rumore o ad un training set non abbastanza rappresentativo
  - È in generale legato alla complessità del modello.
  - Nel caso degli alberi decisionali, si traduce in un numero eccessivo di nodi.
- Stima dell'errore di generalizzazione
  - L'obiettivo è minimizzare gli errori di generalizzazione.
  - N.B. Nella fase di costruzione del modello, gli unici records disponibili sono quelli del training set
  - gli errori di generalizzazione possono solo essere stimati
  - Approccio "ottimistico"
    - Resubstitution Estimate:
      - si assume che gli errori ottenuti sul training set forniscano una buona stima degli errori di generalizzazione
      - solitamente, tuttavia, questa assunzione non si rivela corretta
  - Approccio "pessimistico"
    - Gli errori di generalizzazione sono stimati come: errori ottenuti sul training set + termine di penalizzazione che tiene conto della complessità del modello
    - Nel caso di un albero decisionale (T) con n nodi foglia:
    - e_g(T) = (training_errors + n · penalty_term) / N_training
      - N_training : numero di records nel training set
  - Uso di un validation set
    - Il training set originale viene suddiviso in due sotto-insiemi:
      - uno è utilizzato per addestrare il modello
      - l'altro (validation set) è utilizzato per stimare gli errori di generalizzazione
    - Questo approccio è tipicamente adottato quando è richiesta l'ottimizzazione di uno o più parametri dell'algoritmo usato per indurre il modello.
    - Si riduce il numero di records disponibili per l'addestramento del modello.
  - Occam's Razor (rasoio di Occam)
    - La teoria migliore è la più semplice teoria in grado di descrivere i fatti.
    - Dati due modelli con errori di generalizzazione confrontabili, è da preferire il modello meno complesso.
  - Minimum Description Length (MDL)
    - La teoria migliore è la teoria più "piccola"
    - Cost(Model,Data) = Cost(Model) + Cost(Data|Model)
      - Cost= costo di trasmissione (numero di bits)
    - L'obiettivo è individuare il modello che permette di minimizzare la funzione di costo totale
    - Esempio
      - Sia A che B conoscono i valori di x
      - A conosce anche i valori di y e deve trasmetterli a B
      - A può trasmettere tutti i valori di y sequenzialmente oppure un modello che codifica la relazione tra x ed y
      - Se il modello ha un'accuratezza del 100%, B è in grado di risalire alla corretta classificazione di tutti i records.
      - In caso contrario, oltre al modello, A deve comunicare a B, quali records non vengono classificati correttamente dal modello.
- Overfitting e Alberi decisionali
  - Pre-pruning:
    - interruzione anticipata del processo di partizionamento ("early termination")
    - Criteri per l'interruzione anticipata del processo di partizionamento:
      - soglia sul numero di records associati al nodo
      - soglia sul guadagno (Δ) associato allo split
      - soglia sulla riduzione errori di generalizzazione
  - Post-pruning:
    - costruzione di un albero completo ("fully grown tree") e successiva "potatura" dei suoi rami
    - Sostituzione di un sotto-albero con
      - un nodo foglia con label di classe uguale alla classe prevalente nel sotto-albero
      - il ramo più frequentemente usato nel sotto-albero
      - la "potatura" è finalizzata a minimizzare gli errori di generalizzazione
Valutazione dei modelli
- Errori di generalizzazione
  - Sono stimati in fase di addestramento al fine di selezionare la "giusta" complessità del modello e ridurre il rischio di overfitting (model selection)
  - Vengono poi misurati su un insieme indipendente di dati per valutare l'effettiva capacità di generalizzazione del modello (model evaluation)
- Valutazione dei modelli
  - Metodi di valutazione
    - N.B. Le prestazioni di un modello possono dipendere, oltre che dal tipo di algoritmo utilizzato per l'induzione del modello, anche da altri fattori:
      - dimensioni del training/test set
      - distribuzione delle classi nel training/test set
    - In particolare, al diminuire delle dimensioni del training/test set, le prestazioni del modello:
      - dipendono maggiormente dalla specifica composizione del training/test set (bias)
      - sono caratterizzate da una varianza più elevata
    - Ci sono diversi metodi per ricavare, dai dati disponibili, un test set su cui valutare le prestazioni del modello:
      - Holdout
        
        Una parte degli esempi disponibili è utilizzata per l'addestramento del modello (training set) e una parte per la sua valutazione (test set):
        
        meno esempi disponibili per il training
        
        dipendenza dalla specifica partizione training/test
        
        Per far sì che il training set e il test set siano ugualmente rappresentativi (stessa distribuzione delle classi), si può partizionare il dataset iniziale utilizzando un processo di campionamento stratificato
      - Repeated Holdout
        
        ll metodo holdout viene iterato k volte:
        
        error_rate = Σ_i=1,k error_rate_i / k
        
        nessun controllo sul numero di volte in cui ogni record è usato per il training/test
      - Cross-Validation
        
        Gli esempi disponibili sono suddivisi in k sotto-insiemi di uguale dimensione.
        
        Il processo di addestramento/valutazione del modello viene ripetuto k volte, utilizzando ogni volta:
        
        k-1 sotto-insiemi per il training
        
        1 sotto-insieme per il test
        
        N.B. Ciascuno dei k sotto-insiemi viene utilizzato per il test una sola volta
        
        l'errore totale è dato dalla somma degli errori registrati ad ogni iterazione
        
        A differenza di quanto accade nel Repeated Holdout, in questo caso i test sets sono mutuamente esclusivi e coprono l'intero dataset iniziale.
        
        Anche nella cross-validation si può effettuare un campionamento stratificato.
        
        Approccio standard: stratified ten-fold cross-validation
        
        Ancora meglio: repeated stratified cross-validation
      - Leave-one-out
        
        Caso particolare di cross-validation in cui k = n (numero records)
        
        in fase di training si utilizza il maggior numero possibile di esempi (ogni test set contiene un solo record)
        
        Approccio computazionalmente molto costoso
      - Bootstrap
        
        Si effettua un campionamento with replacement:
        
        se n è la dimensione del dataset originale, un campione (bootstrap sample) di dimensione n conterrà, in media, il 63.2% dei records originali
        
        il campione così formato viene usato per il training e i restanti records per il test
        
        La procedura viene ripetuta k volte:
        
        accuracy = (1/k) Σ_i=1,k (0.632·a_test + 0.368·a_{resubstitution})
        
        a_test è l'accuratezza calcolata sul test set (stima pessimistica)
        
        a_{resubstitution} è l'accuratezza calcolata sul dataset originale (stima ottimistica)
  - Metriche per la valutazione
    - Matrice di confusione
      - Il generico elemento f_ij rappresenta il numero di records della classe i-esima che il modello assegna alla classe j-esima
    - Accuratezza
      - È la metrica maggiormente utilizzata per la valutazione dei modelli:
      - Accuratezza = (TP + TN) / (TP + TN + FP + FN)
        
        TP : True Positive
        
        TN : True Negative
        
        FN : False Negative
        
        TN : True Negative
      - Ogni classe è considerata ugualmente importante
    - "Class Imbalance Problem"
      - In presenza di classi rare (che sono spesso le più interessanti), l'accuratezza non è una buona misura delle prestazioni del modello.
      - Esempio: 9990 oggetti della classe C0 e 10 oggetti della classe C1; se il modello classificasse tutti gli oggetti come appartenenti alla classe C0, la sua accuratezza sarebbe pari a 9990/10000 = 99.9%
      - N.B. Nei problemi binari, la classe rara è generalmente considerata come classe positiva (Class = 'Yes' o Class = '+').
    - Altre metriche
      - True Positive Rate (sensitivity):
        
        TPR = TP / (TP + FN)
      - True Negative Rate (specificity):
        
        TNR = TN / (TN + FP)
      - False Positive Rate:
        
        FPR = FP / (TN + FP)
      - False Negative Rate:
        
        FNR = FN / (TP + FN)
      - Precision:
        
        p = TP / (TP + FP)
        
        è massimo in assenza di falsi positivi
      - Recall (equivalente a TPR):
        
        r = TP / (TP + FN)
        
        è massimo in assenza di falsi negativi
      - Precision e Recall sono utilizzate quando si considera più importante/interessante la corretta classificazione delle istanze positive, un modello ideale dovrebbe massimizzare entrambi questi parametri
      - F-measure:
        
        F = 2rp / (r + p)
        
        il valore di F è alto quando sono alti sia il valore di r che il valore di p
    - Matrice dei costi
      - Associa un costo (C) alle misclassificazioni (errate classificazioni)
    - Costo di un modello
      - C(Model) = TP · C(Yes|Yes) + FP · C(No|Yes) + FN · C(Yes|No) + TN · C(No|No)
      - Si riduce al numero complessivo di misclassificazioni se:
        
        C(Yes|Yes) = C(No|No) = 0
        
        C(Yes|No) = C(No|Yes) = 1
    - Cost-Sensitive Learning
      - È possibile tener conto della matrice dei costi non soltanto in fase di valutazione ma anche in fase di induzione del modello (cost-sensitive learning)
    - l'algoritmo di apprendimento è modificato in modo da minimizzare il costo (e non l'errore di generalizzazione atteso)
  - Confronto fra modelli
    - Curva ROC (Receiver Operating Characteristic)
      - si ottiene riportando:
        
        in ascissa, la frazione di falsi positivi (FPR)
        
        in ordinata, la frazione di istanze positive correttamente classificate (TPR)
      - Ogni punto lungo la curva corrisponde ad un modello indotto con un determinato algoritimo di classificazione.
      - Variando un parametro dell'algoritmo (oppure la distribuzione delle istanze o la matrice dei costi) cambia la posizione del punto.
      - Punti critici di una curva ROC:
        
        (FPR=0, TPR=0) tutte le istanze sono classificate come negative
        
        (FPR=1, TPR=1) tutte le istanze sono classificate come positive
        
        (FPR=0, TPR=1) modello ideale
      - Un buon modello di classificazione si avvicina il più possibile all'angolo superiore sinistro del diagramma
      - Sotto la diagonale che passa per i punti (0,0) (1,1) si ha la predizione opposta alla classe reale
      - La curva ROC è utile per confrontare diversi classificatori
        
        L'area sottesa dalla curva (AUC):
        
        è pari a 1, se il modello è perfetto
        
        è pari a 0.5, in caso di predizioni casuali
        
        Se il modello M1 ha mediamente prestazioni superiori al modello M2, AUC(M1) > AUC(M2)
      - Generazione di una curva ROC
        
        Secondo il modello, un'istanza descritta da un insieme di attributi A appartiene alla classe positiva con probabilità P(+|A)
        
        Le istanze sono ordinate in base al valore di P(+|A)
        
        Ogni valore di P(+|A) èutilizzato come threshold (t)
        
        Tutte le istanze con P(+|A) = t sono classificate come +
        
        Per ogni valore di t, calcoliamo:
        
        TPR = TP/(TP+FN) e FPR = FP/(FP + TN)
  - Confronto fra classificatori
    - quanto sono attendibili le accuratezze misurate per i modelli M1 e M2?
    - la differenza tra le accuratezze di M1 e M2 può essere spiegata in termini di fluttuazioni casuali nella composizione del test set?
  - Intervallo di confidenza
    - Qual'è l'intervallo di confidenza associato all'accuratezza (acc) misurata su un test set di dimensione N?
      - Se N è abbastanza grande (N > 30), acc ha una distribuzione normale
    - P(-Z_α/2 < (acc - p) / SQRT(p(1-p)/N) < Z_α/2) = 1 - α
      - p è il valor medio
      - p(1-p)/N èlavarianza
    - L'accuratezza reale del modello è compresa nell'intervallo:
      - p_upper,lower = (2Nacc + Z²_α/2 ± Z_α/2 SQRT(Z²_α/2 + 4Nacc - 4Nacc²)) / 2(N + Z²_α/2)
    - Esempio
      - Se acc = 80% e N = 100, ad un livello di confidenza di 1-a = 95 (ovvero Z_α/2 = 1.96), risulta:
        
        p_lower = 0.711 , p_upper = 0.867
        
        L'accuratezza reale del modello è compresa in questo intervallo con una probabilità del 95%
      - All'aumentare di N, l'intervallo (p_lower, p_upper) si riduce
  - Confronto prestazioni
    - Dati due modelli M1 e M2:
      - con error rate e1 ed e2
      - valutati sui test sets indipendenti D1 e D2 (n1 e n2 records rispettivamente)
      - la differenza d = e1-e2 è statisticamente significativa?
    - Se n1 e n2 sono sufficientemente grandi, le distribuzioni di e1 ed e2 tendono alla distribuzione normale
    - Anche la differenza d = e1-e2 ha una distribuzione normale (con valor medio d_t e varianza σ_d²)
    - La varianza σ_d² può essere approssimata dalla somma delle varianze di e1 ed e2:
      - σ_d² = e1(1-e1)/n1 + e2(1-e2)/n2
    - Ad un livello di confidenza di (1-α)%:
      - d_t = d ± Z_α/2 σ_d
      - intervallo di confidenza per la vera differenza d_t
Classificatori a regole
- Il modello di classificazione è espresso attraverso un insieme di regole (if-then...)
- caratteristiche
  - Facili da interpretare
  - Espressività e prestazioni confrontabili con quelle degli alberi decisionali
  - Classificazione nuovi records rapida
  - Adatti alla classificazione di classi rare
- Ogni regola ha la forma:
  - ri (Condition_i) → y_i
    - Condition_i = (A1 op v1) AND ... AND (Ak op vk)
    - y_i : classe predetta
  - Una regola (ri) "copre" un'istanza x se gli attributi di x soddisfano la condizione (Condition_i) della regola.
- Qualità di una regola
  - La qualità di una regola di classificazione può essere valutata attraverso le misure:
    - Coverage(ri) = records che soddisfano Condition_i / numero totale di records
    - Accuracy(ri) = records che soddisfano Condition_i e la cui classe è uguale a yi / records che soddisfano Condition_i
- Classificazione di nuovi records
  - Ogni record è classificato in base alla regola o alle regole che "coprono" il record stesso.
  - Proprietà di un insieme di regole
    - Regole mutuamente esclusive:
      - due regole non possono coprire uno stesso record
      - ogni record è coperto al più da una regola
    - Regole esaustive:
      - esiste una regola per ogni possibile combinazione dei valori degli attributi
      - ogni record è coperto da almeno una regola
  - Regole non esaustive
    - Se un insieme di regole non è esaustivo, occorre aggiungere una regola di default (classe più frequente tra i training records scoperti) da applicare nei casi "scoperti": rd:{} → yd
  - Gestione dei conflitti
    - Se invece le regole non sono mutuamente esclusive, gli eventuali conflitti (due regole predicono classi diverse per lo stesso record) possono essere risolti con diversi approcci:
      - Regole Ordinate
        
        È definito un ordine di priorità (es: in base all'accuratezza di ciascuna regola)
        
        ogni nuovo record è classificato applicando la regola con priorità più alta che copre il record
        
        decision list
        
        Schemi di ordinamento
        
        Rule-Based Ordering
        
        le singole regole sono ordinate in base alla loro qualità
        
        Class-Based Ordering:
        
        le regole relative alla stessa classe vengono raggruppate (appaiono insieme nella decision list)
      - Non Ordinate
        
        Se più regole coprono uno stesso record, la predizione di ciascuna di esse è considerata come un "voto" per una determinata classe
        
        si assegna al record la classe più votata (eventualmente pesando i voti in base all'accuratezza delle regole)
    - Estrazione delle regole
      - Metodi diretti
        
        le regole sono estratte direttamente dai dati
        
        Sequential covering algorithm
        
        regole estratte una classe per volta
        
        per ogni classe yj:
        
        l'ordine in cui vengono considerate le classi può dipendere da diversi fattori (es: frequenza della classe, costo della misclassificazione)
        
        1) Decision list (R) inizialmente vuota
        
        2) La funzione Learn-One-Rule è usata per estrarre la regola migliore per la classe yj
        
        3) I records coperti dalla regola sono rimossi dal training set
        
        4)Si ripetono i passi 2) e 3) finché non è soddisfatto un certo criterio di stop
        
        Learn-One-Rule Function
        
        Durante l'estrazione di una regola per la classe y:
        
        tutti i training records appartenenti alla classe y sono considerati esempi positivi
        
        tutti i training records appartenenti alle altre classi sono considerati esempi negativi
        
        L'obiettivo è estrarre una regola che copra il maggior numero possibile di esempi positivi e il minor numero possibile di esempi negativi.
        
        Strategia greedy: si sceglie una regola iniziale che viene progressivamente raffinata
        
        Costruzione della regola
        
        Dal generale al particolare:
        
        regola iniziale: r:{} → y
        
        al primo membro vengono aggiunti, uno dopo l'altro, i predicati Aj op vj che permettono di ottenere la regola migliore
        
        Dal particolare al generale:
        
        uno qualunque degli esempi positivi è scelto come "seme" per la regola iniziale
        
        la condizione della regola è definita in base ai valori assunti dagli attributi nell'esempio scelto
        
        la condizione viene poi "sfoltita" in modo da rendere la regola più generale
        
        (applicabile al maggior numero possibile di esempi positivi)
        
        Valutazione della regola
        
        Accuratezza = n+ / n
        
        n = numero di esempi coperti dalla regola
        
        n+ = numero di esempi positivi coperti dalla regola
        
        non tiene conto della copertura
        
        Laplace = (n+ + 1) / (n + k)
        
        k = numero di classi
        
        se la regola non copre alcun esempio, si riduce a 1/k (probabilità a priori della classe +, assumendo una distribuzione delle classi uniforme)
        
        se la copertura è grande, tende all'accuratezza
        
        m-estimate = (n+ + kp+) / (n + k)
        
        p+ = probabilità a priori della classe +
        
        se n = 0, si riduce a p+
        
        se la copertura è grande, tende all'accuratezza
        
        equivalente a Laplace se p+ = 1/k
        
        FOIL = p1 (log₂(p1/(p1 + n1)) - log₂(p0/(p0 + n0)))
        
        p0 /n0 : num. esempi +/- coperti dalla regola iniziale r: {} → +
        
        p1 /n1 : num. esempi +/- coperti dalla regola r': (A op v) → +
        
        Sono preferite le regole con alti valori di p1 (support count) e p1/(p1+n1) (accuracy)
        
        Pruning
        
        Una regola può essere "potata" per ridurre il rischio di overfitting (calcolo degli errori di generalizzazione)
        
        Come il post-pruning negli alberi decisionali.
        
        Eliminazione delle istanze
        
        Una volta estratta la regola, i records da essa coperti devono essere rimossi dal training set:
        
        la rimozione degli esempi + assicura che le regole successive siano diverse
        
        la rimozione degli esempi - evita che l'accuratezza delle regole successive sia sottostimata
        
        Criteri di stop
        
        Quando interrompere l'induzione delle regole per la classe y?
        
        Copertura/qualità della nuova regola inferiore a una certa soglia
        
        Valutazione del costo di trasmissione complessivo del modello (principio MDL)
        
        Esempio: RIPPER
        
        Problemi binari:
        
        la classe più frequente è scelta come classe di default
        
        sono estratte le regole per la classe meno frequente (che è considerata come classe +)
        
        Problemi multi-classe:
        
        vengono estratte prima le regole per la classe meno frequente e poi, in ordine di frequenza, per le altre classi (la più frequente è considerata come classe di default)
        
        Costruzione delle regole:
        
        r:{} → y
        
        il guadagno di FOIL è usato per scegliere i predicati da aggiungere al primo membro (dal generale al particolare)
        
        Pruning:
        
        si misurano le prestazioni della regola su un validation set:
        
        v = (p-n)/(p+n), p/n: num. esempi +/- coperti dalla regola
        
        si effettua la "potatura" (partendo dall'ultimo predicato aggiunto) in modo da massimizzare v
        
        Criterio di stop:
        
        basato sul principio MDL
        
        la nuova regola è aggiunta alla decision list (R) se non comporta un incremento della description lenght superiore a d bits
      - Metodi indiretti
        
        le regole sono ricavate da altri modelli di classificazione (es: alberi decisionali)
        
        Le regole così ottenute possono essere semplificate
        
        Esempio: regole C4.5
        
        Una regola per ogni cammino radice-foglia.
        
        "Potatura" delle regole
        
        minimizzazione errore pessimistico
        
        Class-based Ordering
        
        regole raggruppate per classe
        
        classi ordinate per description lenght crescente
Nearest-Neighbor
- Instance-based Classifiers
  - I records da classificare sono confrontati con i records del training set
  - Rote Classifier
    - memorizza l'intero training set
    - classifica una nuova istanza solo se i valori dei suoi attributi coincidono con quelli di un record del training set
    - alcune istanze potrebbero non essere classificabili
  - Nearest Neighbor Classifier
    - una nuova istanza è classificata in base agli esempi del training set che sono più simili ad essa (concetto di prossimità)
    - Ogni esempio del training set è rappresentato come un punto in uno spazio n-dimensionale (dove n è il numero degli attributi).
    - Dato un nuovo record da classificare:
      - viene calcolata la sua distanza da ciascun esempio del training set
      - si individuano i k esempi più vicini (k-nearest neighbors)
    - Al nuovo record è assegnata la classe prevalente tra i k primi vicini
    - Scelta di k:
      - k troppo piccolo:
        
        alta sensibilità al rumore
      - k troppo grande:
        
        tra i k primi vicini ci possono essere esempi non abbastanza simili al record da classificare
    - Un modo per ridurre l'influenza del parametro k è "pesare" ciascuno dei primi vicini (xi) in base alla sua distanza dal record da classificare (x'):
      - wi = 1 / d(x', xi)²
    - la classe prevalente tra i vicini è determinata tenendo conto del peso associato a ciascuno di essi
- Osservazioni
  - Questo tipo di classificatore non richiede l'induzione di un modello dal training set (lazy learner).
  - Il training set è usato, piuttosto, in fase di classificazione per "confrontare" i nuovi records con gli esempi noti.
  - A fronte delle risorse risparmiate per la costruzione del modello, la classificazione di un nuovo record è, tuttavia, piuttosto costosa
  - ogni volta, infatti, occorre calcolare la prossimità tra il nuovo record e gli esempi del training set
  - N.B. A seconda delle caratteristiche dei dati, è cruciale scegliere la misura di prossimità più adatta.
  - Talvolta, può essere utile normalizzare gli attributi per evitare che il confronto tra i records sia "dominato" dall'attributo con il range più ampio.
Classificatori Bayesiani
- Introduzione
  - In moltissimi problemi di classificazione, il legame tra la label di classe e i valori assunti dagli altri attributi non è deterministico
    - la classe di un nuovo record non può essere predetta con certezza anche se i valori dei suoi attributi coincidono con quelli di un record del training set
  - Probabilità condizionale
    - modella le relazioni probabilistiche tra la label di classe e i valori assunti dagli altri attributi
    - Date due variabili casuali X e Y, la probabilità che Y assuma un particolare valore, noto il valore assunto da X, è data da:
      - P(Y=y|X=x) = P(X=x, Y=y) / P(X=x)
    - N.B. Se X e Y sono indipendenti:
      - P(X,Y)=P(X)P(Y) ⇒ P(Y|X)=P(Y)
- Teorema di Bayes
  - Mette in relazione le probabilità P(Y|X) e P(X|Y)
  - P(X,Y) = P(Y|X)PX = P(X|Y)P(Y)
  - P(Y|X) = P(X|Y)P(Y) / P(X)
- Rete Bayesiana
  - Formalismo che permette di rappresentare graficamente le relazioni di dipendenza condizionale tra un insieme di variabili casuali.
  - una Rete Bayesiana è un grafo diretto e aciclico (DAG) in cui:
    - i nodi rappresentano delle variabili casuali
    - gli archi rappresentano relazioni di dipendenza tra le variabili
  - Ad ogni nodo X della rete è associata una tabella di probabilità contenente:
    - la probabilità a priori P(X), se X non ha genitori
    - la probabilità condizionata P(X | Y1,...,Yk ), se X ha un insieme di genitori Y1,...,Yk
  - Proprietà di indipendenza condizionale:
    - in una Rete Bayesiana ogni nodo è condizionalmente indipendente dai suoi non-discendenti, dati i suoi genitori
  - La probabilità congiunta relativa a tutti i nodi della rete può essere calcolata come:
    - p(x1,...,xn) = Π_i=1,n P(xi | parents(xi))
    - parents(xi) : insieme dei genitori del nodo xi
  - Una Rete Bayesiana può essere utilizzata per formalizzare un problema di classificazione.
- Gli attributi (A1, ..., An) e la label di classe (C) sono trattati come variabili casuali.
- Dato un training set D, si cerca la rete Bayesiana che meglio descrive le relazioni di dipendenza condizionale tra le variabili in gioco.
- Una volta definita la rete, si può calcolare la probabilità che un nuovo record, descritto da A1 = a1, ..., An = an , appartenga alla classe C = ci:
  - P(C=ci| A1=a1, ..., An=an)
  - probabilità a posteriori per C
- Per ogni nuovo record, il processo di classificazione comporta:
  - il calcolo della probabilità: Pi = P(C=ci | A1=a1,..., An=an)
  - la selezione della classe ci per cui Pi è massima
- Induzione del modello
  - L'induzione della rete che meglio descrive un dato training set implica:
    - la definizione della struttura della rete
    - la stima dei valori della tabella di probabilità associata a ciascun nodo della rete
      - In un caso del tutto generale è un problema intrattabile
  - Spesso, la conoscenza del dominio è sfruttata per definire a priori la struttura della rete.
  - Dopo di che, i valori della tabella di probabilità associata a ciascun nodo della rete possono essere facilmente stimati dal training set.
  - Esistono algoritmi che inducono dei modelli di classificazione Bayesiani introducendo opportune ipotesi semplificative sulla topologia della rete.
  - Il più semplice tra i classificatori Bayesiani è il cosiddetto Naive Bayes (NB).
- Naive Bayes (NB)
  - Basato sull'assunzione che gli attributi A1, A2, ..., An siano condizionalmente indipendenti, dato il valore della classe con C padre e Ai figli
  - La probabilità a posteriori per la classe viene stimata applicando il teorema di Bayes:
    - P(C|A1,...,An) = P(A1,...,An|C)P(C) / P(A1,...,An)
  - In virtù dell'assunzione di indipendenza condizionale tra gli attributi:
    - P(A1,...,An|C) = Π_j=1,n P(Aj|C)
    - (probabilità condizionata alla classe)
  - La probabilità a posteriori può quindi essere riscritta nella forma:
    - P(C|A1,...,An) = (Π_j=1,n P(Aj|C) · P(C)) / P(A1,...,An)
    - N.B. Il denominatore è lo stesso per tutti i valori C = ci
      - può essere trascurato quando si confrontano le probabilità a posteriori per diversi valori di C
  - Per classificare un nuovo record, occorre quindi determinare il valore della classe (ci) che massimizza l'espressione:
    - Π_j=1,n P(Aj|C=ci) · P(C=ci)
    - La probabilitàa priori della classe, P(C), e le probabilità condizionate P(Aj|C) possono essere facilmente stimate dal training set
  - Stima della probabilità
    - La probabilità a priori della classe può essere stimata come:
      - P(C=ci) = Ni / N
        
        N : num. training records
        
        Ni : num. training records in cui C=ci
    - Nel caso di attributi discreti, P(Aj|C) può essere stimata come:
      - P(Aj=aj|C=ci) = Nji / Ni
        
        Nji: training records in cui C= cie Aj= aj
        
        Ni: training records in cui C=ci
    - Nel caso di attributi continui, P(Aj|C) può essere stimata in due modi:
      - "discretizzando" l'attributo
      - assumendo per l'attributo una certa distribuzione di probabilità (i cui parametri possono essere stimati dal training set)
    - Tipicamente:
      - P(Aj=aj|C=ci) = (1 / SQRT(2π)σji)e^(-(aj - μji)² / 2σji²)
      - μji e σji² sono approssimati rispettivamente dalla media campionaria dei valori assunti da Aj nei records della classe ci e dalla relativa varianza
  - Osservazioni
    - Il modello non è influenzato in modo sensibile dal rumore ("mediato" nel calcolo delle probabilità).
    - Il modello non è influenzato da eventuali attributi irrilevanti (per i quali le probabilità P(Aj|C) sono distribuite in modo pressoché uniforme).
    - L'assunzione su cui si basa il Naive Bayes, ovvero l'indipendenza condizionale degli attributi, dato il valore della classe, è piuttosto restrittiva e non è applicabile in molti problemi reali
    - Tuttavia, non di rado il Naive Bayes ha delle prestazioni buone anche in domini caratterizzati da attributi correlati.
    - In generale, per tener conto di eventuali correlazioni tra gli attributi, occorre utilizzare classificatori Bayesiani più sofisticati.
- Augmented Naive Bayes Classifiers
  - Sono state proposte diverse estensioni del Naive Bayes che, pur mantenendo una serie di vincoli sulla topologia della rete, permettono di modellare (almeno in parte) eventuali dipendenze tra gli attributi.
Reti neurali - Rete Neurale Artificiale
- Sistema di calcolo concepito per simulare artificialmente il comportamento del cervello umano:
  - insieme di unità o nodi (neuroni)
  - interconnessi da links a cui è associata un'intensità o peso (connessioni sinaptiche)
- Le proprietà funzionali di una particolare area cerebrale dipendono dal pattern delle connessioni sinaptiche e dall'intensità di tali connessioni
  - Mutuando questa metafora biologica, sono stati investigati diversi modelli architetturali per le reti neurali artificiali.
- In una rete neurale artificiale, come nei sistemi biologici, "apprendere" corrisponde a modificare il valore dei pesi delle connessioni sinaptiche.
- Esempio - Percettrone
  - Il valore in output è ottenuto:
    - calcolando la media pesata dei valori in input(Σ wi xi)
    - sottraendo da essa un fattore di bias (t)
    - valutando il segno del risultato
  - ϒ = sign( w_dx_d + w_d-1x_d-1+ ... + w₁x₁ - t)
  - ϒ = sign( w_dx_d + w_d-1x_d-1+ ... + w₁x₁ + w₀x₀)
    - sign : funzione di attivazione
    - w₀= -t e x₀= 1
    - ϒ = sign(w·· x)
  - Addestramento del percettrone
    - Dato un training set D = {(xi,yi) | i = 1, ..., N}, i pesi del modello (w)
      - sono inizializzati in modo casuale
      - vengono regolati, iterativamente, in modo che l'output del modello risulti consistente con i valori della label di classe in D
    - w_j^k+1 = w_j^k + λ(y_i - ϒ_i^k)x_ij
      - w_j^k : peso della j-esima variabile di input alla k-esima iterazione
      - x_ij : valore assunto dalla j-esima variabile di input nell'istanza i-esima
      - y_i : valore reale della label di classe
      - ϒ_i : predizione del modello
      - Ad ogni iterazione, l'aggiustamento dei pesi èproporzionale all'errore commesso dal modello.
      - Il parametro λ, che regola l'aggiustamento, è detto learning rate (compreso tra 0 e 1)
    - L'algoritmo converge solo nel caso in cui le classi siano linearmente separabili.
    - La "decision boundary" è un iperpiano (y = 0) che separa gli oggetti della classe y = 1 dagli oggetti della classe y = -1
- Topologia MLP (Multi-Layer Perceptron)
  - Struttura multi-layer:
    - feed-forward
    - recurrent
  - Diverse funzioni di attivazione (anche non lineari)
- Definizione della struttura
  - Input layer:
    - un nodo per ogni variabile numerica o binaria
    - (una variabile categorica con k valori può essere trasformata in k variabili binarie)
  - Output layer:
    - un solo nodo, se il problema di classificazione è binario
    - k nodi se la label di classe assume k valori (k > 2)
  - Hidden layers:
    - la "giusta" topologia è spesso determinata per tentativi ...
    - si parte da una rete con un numero sufficientemente alto di layers e nodi e si diminuisce progressivamente la complessità del modello
- Addestramento della rete
  - Implica la ricerca dei pesi che minimizzano la funzione d'errore:
    - E(w) = (1/2)Σ_i=1,N(y_i - ϒ_i)²
- Osservazioni
  - Addestramento costoso (specie se la topologia della rete è complessa), classificazione rapida.
  - Alta sensibilità al rumore (i pesi sono regolati per ogni istanza del training set).
  - Gli attributi irrilevanti/ridondanti non influenzano in modo sensibile il modello (i corrispondenti pesi risultano tipicamente molto piccoli).
Support Vector Machine (SVM)
- Tecnica di classificazione che sta guadagnando crescente attenzione nell'ambito della comunità del Data Mining.
- Concepita per problemi di classificazione binari (due sole classi), ma estendibile anche a problemi multi-classe.
- Linear SVM (Classi linearmente separabili)
  - Idea di base:
    - trovare l'iperpiano ("decision boundary") che separa meglio le classi
    - Dato l'iperpiano Bi, consideriamo gli iperpiani bi1 e bi2, paralleli a Bi, che "toccano" gli elementi delle due classi più vicini ("support vectors")
    - La distanza tra gli iperpiani bi1 e bi2 è detta "margine" del classificatore.
    - Il classificatore col margine più grande avrà, tendenzialmente, un errore di generalizzazione più basso.
    - Fra tutti gli iperpiani in grado di separare le classi, viene quindi selezionato quello con il margine più grande (maximum margin hyperplane)
  - Induzione del modello
    - Dato un training set con:
      - N istanze (xi, yi), i = 1, 2, ..., N
      - due classi: yi . {-1, 1}
    - la "decision boundary"può essere scritta nella forma:
      - w · x + b = 0
    - Se xa e xb sono situati lungo la "decision boundary":
      - w · xa + b = 0
      - w · xb + b = 0
        
        w · (xb - xa) = 0
      - w è perpendicolare alla "decision boundary"
    - I parametri w e b possono essere scelti in modo tale che i due iperpiani bi1 e bi2 abbiano equazione:
      - bi1 : w · x + b = 1
      - bi2 : w · x + b = -1
      - margine = 2 / ||w||
    - I valori dei parametri w e b devono essere stimati dal training set imponendo le seguenti condizioni:
      - w · xi + b ≥ 1 , se yi=1
      - w · xi + b ≤ -1 , se yi=-1
        
        yi(w · xi + b) ≥ 1
    - In aggiunta, occorre imporre che il margine del classificatore sia massimo
      - problema di ottimizzazione in cui si va a minimizzare la funzione obiettivo: f(w) = ||w||² / 2
    - Due formulazioni equivalenti:
      - minimo di L_P = (||w||² / 2) - Σ_i=1,Nλi(yi(w · xi + b)-1)
      - massimo di L_D = Σ_i=1,Nλi - (1/2)Σ_i,j λi λj yi yj xi xj
  - Classificazione nuove istanze
    - Una volta stimati i parametri w e b della "decision boundary", una nuova istanza z sarà classificata semplicemente come:
      - y=1 , se w · z + b > 0
      - y=-1 , se w · z + b < 0
  - "Soft Margin"
    - L'approccio visto finora può essere adattato per definire classificatori con una "decision boundary" che non necessariamente separa in modo perfetto gli esempi del training set (garantendo così un certo grado di tollerenza rispetto al rumore)
    - Possiamo ancora tracciare una "decision boundary" lineare tollerando una certa percentuale di training errors
    - Induciamo il modello, imponendo le condizioni:
      - w · xi + b ≥ 1 - ξi , se yi=1
      - w · xi + b ≤ -1 + ξi , se yi=-1
        
        ξi > 0 (slack variable)
    - Questa volta la funzione obiettivo da minimizzare assume la forma:
      - f(w) = ||w||²/2 + C(Σ_i=1,N ξi)^k
      - cerchiamo ancora il classificatore col margine più grande, penalizzando nel contempo gli eventuali errori
- Non-linear SVM (Classi non linearmente separabili)
  - "decision boundary" non lineare
  - Idea di base:
    - trasformare lo spazio di rappresentazione dei dati (definito dagli attributi x) in un nuovo spazio Φ(x) in cui le classi sono linearmente separabili
    - In generale, il nuovo spazio è definito da una trasformazione non lineare Φ
  - Kernel trick
    - Nel nuovo spazio, i parametri w e b della "decision boundary" (wΦ(x) + b = 0) possono essere ricavati risolvendo il problema di ottimizzazione:
      - min_w ||w||² / 2
      - yi(w · Φ(xi) + b) ≥ 1
    - Il problema può essere riformulato in termini del solo prodotto scalare Φ(xi)Φ(xj):
      - L_D = Σ_i=1,Nλi - (1/2)Σ_i,j λi λj yi yj Φ(xi) Φ(xj)
    - N.B. È possibile trovare una funzione K (kernel function) tale che:
      - K(xi,xj) = Φ(xi) Φ(xj)
      - I parametri del modello possono essere indotti senza un mapping esplicito dei dati
    - Anche la classificazione di una nuova istanza z può essere effettuata senza un mapping esplicito dei dati.
    - Si può infatti dimostrare che:
      - sign(w·Φ(z) + b) = sign(Σ_i=1,N λi yi Φ(xi) Φ(z) + b)
    - Funzioni che godono della proprietà K(x,y) = Φ(x)Φ(y) :
      - K(x,y) = (x y + 1)^p (kernel polinomiale di grado p)
      - K(x,y) = e^-||x-y||² / 2σ² (kernel gaussiano)
- Osservazioni
  - L'induzione del modello è formulabile come un problema di ottimizzazione convesso (in cui si può trovare, in modo piuttosto efficiente, un minimo globale per la funzione obiettivo).
  - Estrema flessibilità:
    - "soft margin"
    - diverse tipologie di kernel
- Multi-class SVM
  - One-versus-rest (1-r):
    - si addestrano k classificatori binari (dove k è il numero delle classi)
    - ogni classificatore binario discrimina le istanze di una determinata classe (ci vs non ci)
    - la predizione finale scaturisce dal confronto delle predizioni dei singoli classificatori binari (gestione dei conflitti)
  - One-versus-one (1-1):
    - si addestrano k(k-1)/2 classificatori binari (dove k è il numero delle classi)
    - ogni classificatore binario discrimina una coppia di classi(ci vs cj)
    - diverse strategie per determinare la predizione finale in base alle predizioni dei singoli classificatori binari (maggior numero di "voti", probabilità più alta)
Regole di associazione
- Formulazione del problema
  - Input:
    - insieme di transazioni (transaction data), ciascuna delle quali contiene un certo numero di items tratti da una determinata collezione
  - Obiettivo dell'analisi:
    - individuare delle regole di dipendenza che predicano l'occorrenza di un item in base all'occorrenza di altri items
- Transaction Data
  - Il dataset può essere visto come una collezione di records descritti da attributi asimmetrici.
    - Es: attributi binari che indicano se un certo prodotto è stato acquistato o meno
- Notazione
  - I = {i1, i2, ..., id}
    - insieme di tutti gli items presenti nel dataset
  - T = {t1, t2, ..., tN}
    - insieme di tutte le transazioni che compongono il dataset
  - Ogni transazione ti ∈ T è costituita da un insieme di items tratti da I
- Definizioni
  - Itemset
    - collezione di zero o più items
    - un itemset di k items è detto k-itemset
    - Una transazione ti ∈ T contiene l'itemset X se X ⊆ ti
  - Dato un itemset X:
    - il numero di transazioni che contengono X è detto support count:
      - σ(X) = |{ti | X ⊆ ti, ti ⊆ T}|
    - la frazione di transazioni che contengono X è detta support:
      - s(X) = σ(X) / N
        
        N = |T|
- Regola di associazione
  - Esprime un'implicazione X → Y dove X e Y sono due itemset disgiunti (X ∩ Y = ∅)
  - Se un cliente acquista X, allora è probabile che acquisti anche Y
- Supporto di una regola
  - Rappresenta la frazione di transazioni a cui la regola può essere applicata:
    - S(X → Y) = σ(X ∪ Y) / N
      - N = |T|
- Confidenza di una regola
  - Misura la "forza" dell'implicazione espressa dalla regola:
    - c(X → Y) = σ(X ∪ Y) / σ(X)
  - Può essere interpretata come P(Y|X)
- Ricerca delle regole
  - Dato un insieme di transazioni T, l'obiettivo dell'analisi è trovare tutte le regole con:
    - supporto superiore o uguale a una certa soglia (minsup)
    - confidenza superiore o uguale a una certa soglia (minconf)
  - Possibile approccio:
    - si individuano tutte le possibili regole
    - si calcola il supporto e la confidenza di ciascuna regola
    - si eliminano tutte le regole con supporto/confidenza inferiori alla soglia
    - Computazionalmente proibitivo (spazio di ricerca esponenziale)
  - Un sensibile miglioramento in termini di efficienza può essere ottenuto verificando i requisiti di supporto e confidenza in due fasi separate.
  - In particolare, tutte le regole con basso supporto possono essere scartate senza procedere al calcolo della confidenza (support-based pruning).
  - Il supporto di una regola X → Y dipende solo dal supporto dell'itemset X ∪ Y.
  - Se l'itemset è poco frequente (basso supporto), tutte le corrispondenti regole (partizioni binarie di tale itemset) possono essere scartate senza calcolare la confidenza.
- Decomposizione del problema
  - Generazione degli itemsets frequenti:
    - ricerca di tutti gli itemsets con supporto ≥ minsup
    - Il calcolo del supporto per tutti i possibili itemsets è computazionalmente molto oneroso, occorre confrontare ogni itemset candidato con ogni singola transazione
    - Si può ridurre la complessità:
      - riducendo il numero di itemsets candidati (Principio Apriori)
      - riducendo il numero di confronti (grazie all'uso di opportune strutture dati)
    - Principio Apriori
      - Se un itemset è frequente, tutti i suoi sotto-insiemi devono a loro volta essere frequenti:
        
        ∀ X,Y : (X ⊆ Y) ⇒ s(X) ≥ s(Y)
        
        (proprietà di anti-monotonicità)
        
        Viceversa, se un itemset è infrequente, tutti i suoi sovra-insiemi sono a loro volta infrequenti.
      - Viene inizialmente determinato il supporto di tutti gli itemsets di dimensione k=1, ovvero di ogni singolo item:
      - da tutti gli 1-itemsets candidati, si selezionano quelli frequenti (supporto ≥ minsup)
      - Iterativamente, vengono generati i k-itemsets candidati dai (k-1)-itemsets frequenti ottenuti nell'iterazione precedente:
        
        i k-itemsets candidati che contengono almeno un sotto-insieme infrequente vengono eliminati (support-based pruning)
      - Il supporto dei k-itemsets candidati rimasti viene determinato scandendo l'intero dataset, ovvero confrontando i k-itemsets candidati con i k-itemsets contenuti in ogni transazione.
        
        Il numero dei confronti può essere ridotto organizzando i k-itemsets candidati in opportune strutture dati (alberi hash)
      - Calcolato il supporto di ogni k-itemset candidato, vengono eliminati i k-itemsets infrequenti cioè con supporto inferiore alla soglia.
      - L'algoritmo termina quando nessun altro itemset frequente può essere identificato.
      - È influenzata da diversi fattori:
        
        Supporto minimo (minsup)
        
        Dimensionalità (numero di items)
        
        Numero di transazioni
        
        Ampiezza media delle transazioni
  - Generazione delle regole:
    - estrazione, dagli itemsets frequenti, di tutte le regole con confidenza ≥ minconf
    - Dato un itemset frequente Y, occorre individuare tutti i sotto-insiemi non vuoti X ⊂ Y tali che la regola X → Y-X abbia confidenza superiore alla soglia fissata.
    - Da un itemset di dimensione k, possono essere estratte 2^k-2 regole candidate.
    - Esempio
      - Se {A,B,C,D}èun itemset frequente, le regole candidate da esso estraibili sono: ABC→D, ABD→C, ACD→B, BCD→A, A→BCD, B→ACD, C→ABD, D→ABC, AB→CD, AC→BD, AD→BC, BC→AD, BD→AC, CD→AB
    - Per determinare la confidenza di una regola, non sono necessarie ulteriori scansioni del dataset.
    - Infatti: c(ABC→D) = σ(ABCD) / σ(ABC)
    - Se {A,B,C,D} è frequente, anche {A,B,C} è frequente (il supporto è già noto)
  - Confidence-based pruning
    - N.B. Se la regola X → Y-X ha confidenza inferiore alla soglia, allora una qualunque regola X' → Y-X', tale che X' ⊂ X, deve avere a sua volta una confidenza inferiore alla soglia
    - Infatti:
      - c(X → Y-X) = σ(Y) / σ(X)
      - c(X' → Y-X') = σ(Y) / σ(X')
    - Se X' ⊂ X, σ(X') ≥ σ(X) ⇒ c(X' → Y-X') ≤ c(X → Y-X) ⇒ pruning
- Algoritmo Apriori
  - Vengono prima generate le regole candidate aventi un solo item al secondo membro.
    - Tra queste, si selezionano quelle con confidenza ≥ minconf
  - Le regole ottenute vengono quindi usate per generare le regole candidate con due items al secondo membro, etc.
- Valutazione delle regole
  - Gli algoritmi per l'estrazione di regole di associazione tendono a generare un numero molto elevato di regole, alcune delle quali possono essere ridondanti o poco interessanti.
  - È importante valutare, a posteriori, la qualità delle regole ottenute.
  - In fase di estrazione, infatti, le regole sono valutate solo in termini di supporto e confidenza.
  - Valori elevati del supporto e della confidenza, tuttavia, non sono sufficienti, di per sé, a garantire la qualità delle regole estratte.
  - indipendenza statistica: P(A AND B) = P(A)*P(B)
  - correlazione positiva: P(A AND B) > P(A)*P(B)
  - correlazione negativa: P(A AND B) < P(A)*P(B)
  - Misure che tengono conto della dipedenza statistica tra le variabili:
    - Lift = c(X→Y)/s(Y) = P(X|Y)/P(Y)
    - I(X,Y) = s(X,Y)/(s(X)*s(Y)) = P(X,Y)/(P(X)*P(Y)) = (N f11) / (f1+ * f+1)
    - PS = P(X,Y)-P(X)P(Y) = (f11/N) - ((f1+ f+1)/N²)
    - Φ = (P(X,Y)-P(X)P(Y)) / SQRT(P(X)(1-P(X))P(Y)(1-P(Y))) = (f11 f00 - f01 f10) / SQRT(f1+ f+1 f0+ f+0)
  - In letteratura, sono state proposte decine di misure diverse.
  - La stessa regola può risultare piùo meno rilevante a seconda della misura applicata
  - Come scegliere la misura più adatta per uno specifico problema?
  - Una misura invariante rispetto all'operazione di inversione (che dà cioè lo stesso peso alle coppie 1-1 e alle coppie 0-0) è tipicamente poco adatta per l'analisi di datasets asimmetrici.
    - Es: Φ è invariante, I, PS e confidenza non sono invarianti
  - Tipicamente, ci si aspetta che la relazione tra due items non sia influenzata dall'aggiunta di dati irrilevanti (transazioni che non contengono nessuno dei due items).
  - Criteri oggettivi:
    - basati su misure di carattere statistico (supporto, confidenza, lift, correlazione, etc...)
  - Criteri soggettivi:
    - basati sulla conoscenza del dominio (es: una regola può fornire informazioni inattese e/o potenzialmente utili per specifiche applicazioni)
  - Una regola rilevante dal punto di vista statistico, può tuttavia essere poco interessante se esprime implicazioni ovvie o già note (es: Butter → Bread )
  - Viceversa, una regola che esprime implicazioni non ovvie o inattese può essere interessante pur risultando statisticamente meno rilevante (es: Diapers → Beer )
  - In pratica, l'integrazione di criteri soggettivi nel processo di estrazione/valutazione delle regole è tutt'altro che banale.
CLUSTERING
- Formulazione del problema
  - Input:
    - collezione di oggetti/eventi, ciascuno caratterizzato da un insieme di attributi
    - definizione di una misura di similarità/dissimilarità tra gli oggetti in esame
  - Obiettivo dell'analisi:
    - individuare gruppi di oggetti o clusters, tali che i membri di ciascun cluster siano il più possibile simili tra loro e dissimili da quelli degli altri clusters
- Cluster
  - Uno stesso dataset può essere modellato in modi diversi, individuando cioè diversi insiemi di clusters.
  - La miglior definizione dei clusters dipende dalla natura dei dati e dalla tipologia di applicazione.
- Tipi di clusters
  - Clusters ben separati:
    - ogni oggetto è più simile/vicino ad ogni altro oggetto del suo cluster che a un qualunque oggetto di un altro cluster
  - Center-based clusters:
    - ogni oggetto è più simile/vicino al centro del suo cluster che al centro di un qualunque altro cluster
  - Contiguity-based clusters:
    - ogni oggetto è più simile/vicino ad almeno un oggetto del suo cluster che a un qualunque oggetto di un altro cluster
  - Density-based clusters:
    - i clusters sono regioni ad alta densità, separate da regioni a bassa densità
  - Clusters "concettuali":
    - gli oggetti di un cluster condividono una determinata proprietà ovvero rappresentano uno stesso concetto
  - Clustering partitivo
    - dataset partizionato in sotto-insiemi disgiunti
  - Clustering gerarchico
    - clusters nidificati, con un'organizzazione ad albero
    - Un clustering gerarchico può essere visto come una sequenza di clustering partitivi, ovvero un qualunque livello di una gerarchia di clusters nidificati può essere interpretata come un clustering partitivo
- Algoritmi di clustering
  - Clustering partitivo
    - K-means e sue varianti
  - Clustering gerarchico
    - Agglomerative Hierarchical Clustering
    - Divisive Hierarchical Clustering
  - Density-based clustering
    - DBSCAN
- K-means
  - Il dataset è partizionato in un numero pre-derminato (K) di sotto-insiemi disgiunti.
  - I clusters generati sono di tipo center-based
  - K-means vs K-medoid
    - K-means:
      - il "centro" di ogni cluster (centroide) è tipicamente la media dei punti appartenenti al cluster (attributi numerici).
    - K-medoid:
      - il "centro" di ogni cluster (medoide) è il punto più rappresentativo del cluster (attributi categorici)
  - Idea di base:
    - 1) Si scelgono K centroidi iniziali (dove K è un parametro specificato dall'utente)
    - 2) Si formano K clusters assegnando ogni punto al centroide più vicino.
    - 3) Si aggiorna il centroide di ciascun cluster sulla base dei punti ad esso assegnati.
    - 4) Si ripetono i passi 2) e 3) finché i centroidi non cambiano più (ovvero non cambia più la composizione dei clusters).
  - Scelte implementative:
    - i centroidi iniziali sono spesso scelti in modo casuale
    - il centroide di ciascun cluster è tipicamente calcolato come media dei punti assegnati al cluster
    - la similarità/dissilimarità tra i punti è misurata con funzioni diverse (distanza euclidea, coseno, correlazione, etc) a seconda delle caratteristiche dei dati
  - La convergenza dell'algoritmo è garantita per determinate combinazioni di funzioni di prossimità e tipologie di centroidi.
  - Poiché la convergenza viene in gran parte raggiunta nelle prime iterazioni, la condizione di stop dell'algoritmo può essere resa meno restrittiva
    - es: si continua a iterare finché la percentuale di punti che cambiano cluster diventa inferiore all'1%)
  - Funzione obiettivo
    - L'algoritmo K-means mira a minimizzare una funzione obiettivo che esprime l'errore ovvero la qualità del clustering.
    - Se la misura di prossimità scelta è la distanza euclidea, la funzione obiettivo è tipicamente la somma degli errori quadratici (SSE).
    - SSE = Σ_i=1,KΣ_x∈Ci dist(ci,x)²
      - x : oggetto del dataset
      - Ci : cluster i-esimo
      - ci : centroide del cluster i-esimo
    - I centroidi che minimizzano la funzione SSE corrispondono ai punti medi dei clusters:
      - ci = (1/mi) Σ_x∈Cix
        
        mi : numero di oggetti nel cluster i-esimo
    - Si può ridurre l'errore complessivo (SSE) aumentando K.
    - Per un dato valore di K e per una data configurazione dei centroidi iniziali, l'algoritmo è in grado di trovare un minimo locale della funzione SSE (non necessariamente un minimo globale!)
  - Limiti dell'inizializzazione casuale
    - A seconda di come sono scelti i centroidi iniziali, può cambiare l'insieme di clusters generati dall'algoritmo.
    - Se i centroidi sono inizializzati in modo casuale, il risultato può quindi essere diverso ad ogni esecuzione dell'algoritmo.
    - Possibile approccio:
      - l'algoritmo viene eseguito più volte, inizializzando ogni volta in modo casuale i centroidi iniziali
      - si seleziona, a posteriori, il clustering che permette di minimizzare l'errore complessivo (SSE)
      - (non sempre i risultati sono buoni)
  - Scelta dei centroidi iniziali
    - Strategie:
      - Massimizzare la distanza tra i centroidi iniziali
      - Post-processing
      - Bisecting K-means
  - Complessità
    - O(I · K · m · n)
      - I : numero di iterazioni
      - K : numero di clusters
      - m : numero di punti
      - n : numero di attributi
- Gestione clusters vuoti
  - L'algoritmo K-means può generare uno o più clusters vuoti, ovvero può capitare che ad un centroide non sia assegnato nessun punto (sostituzione del centroide)
  - Possibili strategie (per ogni cluster vuoto):
    - scelta del punto che contribuisce di più al valore di SSE(il punto più lontano dagli attuali centroidi)
    - scelta di un punto appartenente al cluster che contribuisce di più al valore di SSE
- Gestione outliers
  - Eventuali outliers possono influenzare troppo i clusters generati dall'algoritmo.
  - In particolare, in presenza di outliers, i centroidi dei clusters possono risultare meno rappresentativi (incremento di SSE).
  - Gli outliers possono essere eliminati:
    - preventivamente ("anomaly detection")
    - in fase di post-processing (individuando i punti che danno un contributo molto alto al valore di SSE)
- Post-processing
  - Strategie che permettono di ridurre il valore di SSE aumentando il numero di clusters:
    - split
    - introduzione nuovo cluster
  - Strategie per diminuire il numero di clusters minimizzando l'aumento di SSE:
    - merge
    - dispersione di un cluster
  - Le precedenti strategie vengono spesso combinate, ad esempio alternando le fasi di split/merge
    - Si può così ridurre il valore complessivo di SSE senza cambiare il numero di clusters
- Bisecting K-means
  - Variante di K-means:
    - può produrre un clustering partitivo o un clustering gerarchico
    - è meno sensibile ai problemi di inizializzazione
  - Idea di base:
    - si partiziona il dataset originale in due clusters (usando l'algoritmo K-means, con K=2)
    - uno dei due clusters viene a sua volta partizionato in due sotto-insiemi, e si ottengono così tre clusters
    - i clusters vengono ripartizionati fino ad ottenere K clusters
  - Criteri per la scelta del cluster da partizionare:
    - cluster più grande
    - cluster col più alto valore di SSE
    - criteri misti
    - (criteri differenti producono risultati differenti)
  - N.B. Ad ogni iterazione, individuato il cluster da partizionare, l'algoritmo valuta diverse partizioni binarie e sceglie quella a cui è associato il più basso valore di SSE
  - Raffinamento del risultato:
    - i centroidi dei K clusters così ottenuti vengono utilizzati come centroidi iniziali dell'algoritmo K-means
  - osservazioni
    - La sequenza dei clustering partitivi ottenuti nelle singole iterazioni può essere interpretata come un clustering gerarchico (insieme di clusters nidificati)
    - Questo algoritmo è meno sensibile ai problemi di inizializzazione perché
      - effettuta solo partizioni binarie (due centroidi)
      - ad ogni iterazione, valuta diverse partizioni e sceglie quella migliore
- K-means e varianti:limitazioni
  - Difficoltà ad individuare clusters
    - non sferici
    - con diverse dimensioni
    - con diverse densità
  - Una possibile soluzione consiste nell'aumentare K:
    - i clusters "naturali" sono frammentati in più sotto-clusters (aggregazione)
- Valutazione dei clusters
  - Diversi aspetti:
    - discriminare l'esistenza o meno di clusters "naturali" ovvero di una struttura non casuale nei dati (clustering tendency)
    - determinare il numero corretto di clusters
    - valutare in che misura i clusters individuati descrivono bene i dati
      - senza far riferimento a sorgenti esterne di informazione
      - facendo riferimento a sorgenti esterne di informazione
    - confrontare i risultati di diversi algoritmi/tecniche di clustering
      - senza far riferimento a sorgenti esterne di informazione
      - facendo riferimento a sorgenti esterne di informazione
    - Misure:
      - non supervisionate o interne (misure di coesione, misure di separazione)
      - supervisionate o esterne (es: entropia)
- Misure interne
  - Misure di coesione:
    - misurano il grado di correlazione/vicinanza tra gli oggetti di un cluster
  - Misure di separazione:
    - misurano quanto un cluster è distinto/separato dagli altri clusters
  - La scelta della misura di coesione/separazione dipende dal tipo di cluster.
  - Ovvero:
    - la coesione di un cluster è definita come la somma delle prossimità tra i singoli punti e il centro del cluster (centroide o medoide)
    - la separazione tra due cluster è data dalla prossimità tra i rispettivi centri
  - cohesion(Ci) = Σ_x∈Ci proximity(x,ci)
    - ci : centro del cluster Ci
    - Coincide con SSE(Ci) se la funzione di prossimità è L₂²
  - separation(Ci,Cj) = proximity(ci,cj)
  - separation(Ci) = proximity(ci,c)
    - ci : centro del cluster Ci
    - c : centro dell'intero dataset
  - overall_validity = Σ_i=1,K wi·validity(Ci)
    - validity : misura di coesione o separazione (o una combinazione delle due)
    - i pesi wi dipendono dalla misura utilizzata
  - Esempi:
    - Σ_i=1,KΣ_x∈Ciproximity(x,ci) ⇒ wi=1
    - Σ_i=1,K mi proximity(ci,c) ⇒ wi=mi (numero di oggetti nel cluster)
    - Σ_i=1,KΣ_x∈Ciproximity(x,ci) ⇒ SSE , (se proximity=L₂²)
    - Σ_i=1,K mi proximity(ci,c) ⇒ SSB , (se proximity=L₂²)
  - Si può dimostrare che:
    - TSS = SSE + SSb = Σ_i=1,KΣ_x∈Ci dist(x,c)² = costante
    - TSS = Total Sum of Squares
  - Minimizzare SSE (coesione) equivale a massimizzare SSB (separazione)
  - N.B. Ogni misura interna di validità potrebbe essere usata come funzione obiettivo in fase di clustering e viceversa.
    - La funzione obiettivo tipicamente utilizzata dall'algoritmo K-means è la misura di coesione SSE.
- Numero corretto di clusters
  - Può essere stimato studiando l'andamento di una misura interna (SSE) in funzione di K
- Misure esterne
  - Talvolta sono disponibili informazioni esterne sui dati (es: labels di classe fornite da un esperto del dominio)
    - Può essere interessante confrontare tali informazioni con il risultato del clustering
  - A questo scopo è possibile usare le stesse misure (es: entropia, precisione, recall, etc).che vengono tipicamente utilizzate per valutare la bontà di un modello di classificazione

Appunti di Data Mining