Domande in preparazione all'esame finale di Metodi per la gestione dei progetti complessi

Regole associative e algoritmo apriori

Dato un insieme di item I, una regola associativa è un’implicazione con forma X→Y



(X implica Y), con X, Y I e XY=. Esistono due parametri fondamentali relativi alle

regole associative: supporto e confidenza:

• Supporto s: rapporto tra le transazioni che contengono XY e tutte le

transazioni;

• Confidenza c: rapporto tra le transazioni che contengono XY e le transazioni

contenenti X. SCIE

c

In base alle definizioni di supporto e confidenza si possono fare alcune osservazioni

generali: le regole con elevato supporto e bassa confidenza sono poco interessanti

perché non indicano nulla di specifico, mentre elevata confidenza e basso supporto

possono suggerire l’esistenza di nicchie; chiaramente quando entrambi i valori sono

bassi la regola non risulta interessante.

Per poter generare delle regole valide bisogna impostare un MINSUPP e una

MINCONF; ovviamente non esistono dei valori universalmente corretti, vengono

impostati a discrezione del responsabile.

Il lavoro svolto in questo campo ha dimostrato che supporto e confidenza sono

legati dalla relazione: c=s(XY)/s(X); quindi il processo può essere diviso in due

1

parti: la prima riguarda la generazione dei frequent itemset (FI), ovvero gli itemset

che hanno supporto superiore o uguale a MINSUPP, mentre la seconda è la

a

generazione delle regole, selezionando, avendo a disposizione i supporti, quelle che

soddisfano la soglia di confidenza MINCONF.

Una classificazione fondamentale delle regole associative riguarda la dimensionalità

di queste: nelle regole monodimensionali i soggetti delle implicazioni sono valori

intra attributo, mentre in quelle multidimensionali vengono messi in relazione valori

inter-attributo.

Quando si lavora con una gerarchia di concetti si parla anche di regole associative

multilivello, ovvero che riguardano livelli diversi della gerarchia. Solitamente viene

fatto girare un algoritmo (apriori) per individuare i FI e poi, a seconda che si utilizzi

un approccio top down o bottom up si ricercano le regole rispettivamente dal

generale allo specializzato o dallo specializzato al generale, regolando i parametri di

MINSUPP e MINCONF a seconda dei livelli.

Uno strumento che può risultare utile per la validazione delle regole è la

correlazione, definita come corr (a, b) =P(ab)/(P(a) P(b)) (in questo caso ci si

riferisce alle frequenze più che alle probabilità).

Quando due eventi sono indipendenti la probabilità della loro unione è la stessa del

prodotto delle loro singole probabilità (corr=1). Altrimenti, se corr<1 si parla di

influenza negativa, se corr>1 influenza positiva. Chiaramente se una regola è forte

avrà correlazione tra antecedente e conseguente maggiore di 1.

La ricerca di regole può essere automatizzata con l’algoritmo Apriori che è in grado,

a partire dai valori prefissati di MINSUPP e MINCONF, di scansionare

automaticamente un database transazionale e generare delle regole. L’algoritmo si

basa sul principio Apriori: se un itemset è frequente, allora anche ogni suo

sottoinsieme lo è (proprietà anti-monotona del supporto). La conseguenza di ciò è

che se un itemset non è frequente, nemmeno quelli che lo contengono lo sono,

perciò non c’è bisogno di considerare i superset.

Questo permette un grande risparmio computazionale considerando che per d

items si possono generare 2^d itemset.

Il punto di partenza dell’algoritmo è la scansione del database per individuare gli

item frequenti; una volta trovati, essi costituiscono il punto di partenza per

l’identificazione degli itemset frequenti di cardinalità crescente.

Ad ogni passo viene generato un insieme C di itemset candidati (ad essere frequenti)

e viene scansionato il database transazionale, aumentando il conteggio dei soli

candidati di C che siano compresi nella transazione t; una volta scansionate tutte le

transazioni, l’insieme di itemset frequenti (indicato con L) è dato dagli elementi di C

che superino o eguaglino MINSUPP. Si reitera il processo fino al passo in cui il nuovo

insieme L di FI non risulta vuoto. Tuttavia, bisogna ancora far luce sulla generazione

dei candidati: gli insiemi C di cardinalità k vengono generati con dei self-join degli

insiemi L di cardinalità k-1, ovvero i FI dell’iterazione precedente. Per ogni itemset

generato di cardinalità k vengono considerati tutti i subset di ordine k-1: se tutti i

subset sono presenti in L(k-1), ovvero sono frequenti, allora anche l’itemset appena

creato lo sarà (principio apriori), ed entrerà a far parte dell’insieme dei candidati

C(k).

La seconda parte consiste nella vera e propria generazione di regole: per ogni FI f

vengono generati tutti i subset non vuoti s, se s(f)/s(s)>= MINCONF allora verrà

If f

S

creata la regola s→(f-s). MINCONF S

D

L’algoritmo è estremamente semplice ed intuitivo ma per come è strutturato soffre

molto il carico computazionale, perciò sono stati fatti alcuni miglioramenti nel

tempo. Una soluzione prevede l’utilizzo di bucket per raccogliere i candidati che

vengono etichettati con una funzione di hash, che nel qual caso non dovessero

superare la soglia del supporto minimo verrebbero eliminati; è un metodo

particolarmente efficace con k=2.

Un’alternativa prevede il partizionamento del database ed è strutturata in due fasi

consecutive. La prima consiste nel dividere il db in n partizioni, a seconda dello

spazio di memoria che si desidera occupare; moltiplicando il MINSUPP per la

frazione di transazioni di quella partizione si ottiene il supporto minimo relativo alla

partizione, e in base a quella si ricercano gli itemset frequenti localmente. Nella

seconda fase si selezionano quelli frequenti in almeno una partizione e vengono

combinati per valutare se lo sono anche globalmente.

Clustering e algoritmo k-means

Dato un insieme di N oggetti d-dimensionali, il clustering è l’operazione di

raggruppamento di tali oggetti in k cluster che massimizza la similarità intra cluster e

la minimizza inter-cluster, in modo da avere dei gruppi che siano il più possibile

omogenei. Si tratta di un apprendimento non supervisionato, per cui non si hanno a

disposizione delle classi di output a priori, il cui obiettivo è la ricerca di un pattern

tra i dati o la validazione di un altro metodo di classificazione. Esistono vari tipi di

approcci al problema, tra cui metodi partitivi, gerarchici, probabilistici, basati sulla

densità etc.

Per l’approccio partitivo l’algoritmo di riferimento è K-means. L’unico input di cui ha

bisogno è il numero di cluster in cui si desidera partizionare l’insieme dato, poi

agisce iterativamente fino alla fine. Il funzionamento è il seguente:

1. Si imposta il numero k di cluster desiderati;

2. Si scelgono a caso k punti di partenza che rappresenteranno i riferimenti

iniziali dei cluster;

3. Ogni oggetto trova il suo centro più vicino (solitamente viene utilizzata la

distanza euclidea) e si unisce al cluster;

4. Una volta assegnati tutti gli oggetti si calcola il centroide di ogni cluster, che

diventa automaticamente il nuovo centro;

5. Il processo iterativo riparte dal punto 3 e continua finché i centroidi non si

spostano più.

La funzione da minimizzare è la distorsione, data dalla sommatoria dei quadrati delle

distanze tra i punti e i centri assegnati.

(formule a parte)

In breve, per minimizzare la distorsione bisogna assegnare i punti al centro più

vicino e questo deve essere il centroide del cluster.

K-means è un algoritmo di tipo greedy, ovvero cerca un ottimo globale scegliendo,

ad ogni iterazione, la soluzione ottima locale; quindi, la configurazione dei cluster

può arrestarsi anche senza aver raggiunto la minima distorsione perché ha trovato

un minimo locale. Perciò, per ottenere una soluzione soddisfacente bisogna mettere

in atto alcuni accorgimenti: innanzitutto bisogna porre attenzione alla scelta dei

punti iniziali, che siano lontani il più possibile uno dall’altro; inoltre, è

raccomandabile far girare l’algoritmo più volte scegliendo sempre differenti punti di

partenza, confrontando i risultati nella fase finale. È scontato dire che una delle

scelte più importanti riguarda il numero di cluster; spesso la scelta è influenzata

dall’esperienza, ma in ogni caso la cosa migliore da fare è sperimentare più valori e

scegliere il più appropriato.

Inoltre, è un algoritmo che non si presta all’individuazione di cluster di forma non

convessa e non tratta adeguatamente il rumore. Oltre a questo, è inadatto al

trattamento di dati categorici, anche in questo caso si può utilizzare la sua variante

k-modes, che basa il concetto di similarità sulle frequenze.

Tuttavia, ha il vantaggio di essere particolarmente semplice e relativamente

efficiente in termini di complessità computazionale: O(ktn), dove k è il numero di

cluster, t il numero di iterazioni e n il numero di oggetti (solitamente il più grande).

Metodi di clustering gerarchici

Come suggerito dal nome, il clustering gerarchico ha come obiettivo la costruzione

di una gerarchia tra i cluster, rappresentabile con un dendogramma (1D) o un

diagramma innestato (2D). I metodi di clustering gerarchici si dividono in

agglomerativi (i più comuni) e divisivi, a seconda che l’approccio sia rispettivamente

bottom up o top down. I primi cominciano considerando ogni punto come cluster e

ad ogni iterazione uniscono la coppia di cluster più simili, mentre gli ultimi

considerano tutti i punti in un unico cluster che viene a mano a mano frammentato

in più cluster. Per definire il grado di similarità/dissimilarità tra i cluster questi

metodi necessitano di una metrica per la distanza (solitamente quella euclidea) e un

criterio di collegamento. Di seguito i più comuni:

• Minimum (o single) linkage: D (Ci, Cj) =min (x, y), con x e y appartenenti

rispettivamente al cluster Ci e Cj;

• Complete linkage: D (Ci, Cj) =max (x, y);

• Average linkage: la distanza tra due cluster è la media tra le distanze delle

coppie di elementi dei cluster (troppo lungo scrivere questa formula);

Per chiarezza, si illustra il procedimento step by step del clustering gerarchico

agglomerativo per n oggetti:

1. All’inizio ci sono tanti cluster quanti elementi. In questo primo passo si calcola

la matrice di prossimità;

2. Trovata la coppia di cluster più simili, essi vengono fusi e diventano un nuovo

cluster;

3. Si aggiorna la matrice di prossimità ricalcolando i valori rispetto al nuovo

cluster;

4. Si reitera il procedimento ripartendo dal punto 2;

La condizione di terminazione naturale è quella in cui tutti i punti fanno parte di un

unico cluster; ovviamente questa configurazione finale, esattamente come quella

speculare del clustering divisivo in cui tutti i punti sono cluster, non è mai

interessante ai fini dell’attività svolta, perciò è necessario scegliere un livello in cui

terminare la costruzione (o divisione) della gerarchia.

Il clustering gerarchico è un metodo abbastanza efficace e il risultato che fornisce

(dendogramma o diagramma innestato) può essere particolarmente interessante

per l’utente, tuttavia non è molto diffuso perché non scala bene all’aumentare dei

dati e gli errori commessi nei passi precedenti non possono essere eliminati. Inoltre,

non essendoci un numero prefissato di cluster da costruire non esiste una funzione

globale da perseguire. Due esempi di algoritmi che seguono questo metodo sono

AGNES (agglomerative nesting) e DIANA (divisive analysis).

Fortunatamente alcuni algoritmi più recenti implementano delle altre tecniche

rispetto alla semplice logica gerarchica, si parla di clustering multifase.

L’algoritmo BIRCH utilizza delle clustering features (CF) per costruire un CF-tree, in

questo modo si possono sintetizzare le informazioni di rappresentazione a vantaggio

dell’efficienza. Le CF sono tre:

• N: numero degli oggetti;

• LS: linear sum, somma lineare degli oggetti (considerando gli oggetti come

vettori, LS a sua volta è un vettore);

• SS: square sum, somma quadratica degli oggetti.

Il risultato è un albero che memorizza le CF di ogni cluster ai vari livelli e in ogni

nodo sono sintetizzate le informazioni dei nodi sottostanti.

N.B. le CF hanno la proprietà di potersi sommare linearmente, perciò per ottenere la

CF del padre basta sommare quelle dei figli.

I parametri di cui tenere conto durante la costruzione del CF tree sono due:

• Branching factor b: numero massimo di figli di un nodo intermedio;

• Diametro soglia: diametro massimo dei sottocluster dei nodi foglia.

Detto questo, l’algoritmo BIRCH è relativamente semplice: il primo passo consiste

nello scan del DB per costruire il CF-tree, dopodiché si applica un altro algoritmo di

clustering (è indifferente quale) ai nodi foglia. Per come è strutturato riesce a scalare

abbastanza bene e soprattutto può essere aggiornato agevolmente volta per volta,

permettendo un inserimento del data set incrementale (molto comodo quando non

si dispone di tutti i dati in anticipo. Purtroppo, neanche questo algoritmo non

funziona con dati categorici e non è adatto a forme non sferiche.

Quando bisogna trattare cluster dalla forma non sferica una valida soluzione è CURE

(Clustering Using REpresentatives). È un algoritmo agglomerativo che sostituisce la

nozione di centroide con quella di punti rappresentativi: in ogni cluster viene

selezionato un numero predefinito di elementi rappresentativi che siano abbastanza

sparsi; essi vengono condensati verso il centro di un determinato fattore, dopodiché

si confrontano i punti rappresentativi di ogni cluster per valutare la prossima

fusione.

Una volta scelti il fattore di compattamento e il numero di oggetti rappresentativi

l’algoritmo si comporta molto bene, riesce a scalare, riconosce cluster di forme

particolari e grazie alla condensazione verso il centro limita la presenza di rumore.

Nel caso in cui fosse necessario trattare dati categorici si può usare ROCK, che,

appoggiandosi al concetto di interconnettività aggregata, valuta la similarità di due

cluster in base ai punti che hanno dei vicini in comune.

Il passo avanti è Chamaleon, che supera i limiti di ROCK e CURE: prima costruisce un

gran numero di piccoli cluster con un algoritmo partitivo, poi determina la

configurazione finale con un algoritmo agglomerativo, fondendo i cluster sia in base

all’interconnettività che alla distanza.

Classificazione con alberi di decisione

La classificazione è una disciplina del data mining che si occupa di costruire modelli

per l’identificazione e la descrizione di classi di dati. Un’applicazione emblematica è

nel settore bancario dove, in base ad alcune caratteristiche del cliente, si cerca di

predire il suo grado di solvibilità. Il primo step è l’apprendimento del modello, che si

distingue in supervisionato e non: nel primo caso l’algoritmo dispone degli input con

i relativi output desiderati, con lo scopo di mapparli con delle regole, mentre nel

secondo si ricercano semplicemente dei pattern naturali nei dati, o si cerca di

validare un altro strumento di classificazione. In questa fase iniziale di

apprendimento viene analizzato un insieme di dati che prende appunto il nome di

training set, e l’output sarà proprio il modello, espresso in forma di regole o formule

matematiche. La seconda parte consiste nella verifica del modello applicandolo ad

un test set (necessariamente diverso dal training set), così da poterne stimare anche

l’accuratezza reale. In alcuni casi si impiega anche un validation set tra quello di

training e di test, per sistemare i parametri.

Nel data mining si sono affermati vari tipi di classificatori, tra cui SVM, reti neurali,

Bayesiani e alberi di decisione. Questi ultimi, in particolare, sono degli alberi che

predicono un attributo non noto a partire da input categorici e/o continui. I rami

dell’albero individuano una successione di test su vari attributi noti, con lo scopo di

individuare delle regole per classificare l’output. In poche parole, l’albero viene

costruito applicando ricorsivamente ad ogni nodo un test su un attributo di split, che

viene selezionato di volta in volta in base alla sua predittività (esistono vari criteri di

split). La ricorsione termina quando tutti i record appartenenti a quel nodo hanno la

stessa classe di output, che sarà la classe predetta, o quando essi hanno gli stessi

valori per gli attributi di input, perciò non esistono più attributi rispetto ai quali fare

lo split. Un algoritmo frequentemente usato per gli alberi di decisione è quello di

Hunt:

• Se il nodo t contiene un insieme di record Dt appartenenti alla stessa classe Yt

(in output) allora è un nodo foglia e viene predetta la classe Yt;

• Se il nodo t non contiene record (Dt vuoto) allora è un nodo foglia e va

etichettato con la classe di default Yd;

• Se t contiene record di più classi bisogna individuare un test su un attributo

per dividere t in ulteriori sottoinsiemi, applicando la procedura in maniera

ricorsiva per ogni sottoinsieme.

Gli alberi di decisione utilizzano una strategia Greedy, ovvero cercano un ottimo

globale scegliendo, ad ogni iterazione, la soluzione ottima locale che ottimizzi un

determinato criterio di split dell’albero. Perciò, è necessario stabilire la condizione di

test sull’attributo e un metodo che guidi la scelta degli split. Solitamente negli alberi

di decisione si ha a che fare con attributi categorici, per cui al momento dello split

verranno create tante partizioni quanti valori dell’attributo. Quando si hanno degli

attributi continui questa soluzione è spesso impraticabile; è molto meglio effettuare

una discretizzazione in intervalli (binning) che abbiano la stessa ampiezza,

profondità e siano caratterizzati da una certa omogeneità, altrimenti si può stabilire

una soglia ricorrendo ad uno split binario. Fatto questo è necessario scegliere un

metodo di valutazione dell’impurezza dei nodi per poter selezionare l’attributo di

split ad ogni passo. I più comuni sono i seguenti.

Information gain IG

Prima di definire questo concetto è necessario introdurre quello di entropia: data

una variabile X che può assumere n valori, ognuno con relativa probabilità pj,

l’entropia di X è il minimo numero medio di bit necessari per trasmettere X

=1

∑

() = −

2

Perciò quando E è alta significa che la variabile ha una distribuzione uniforme,

mentre quando E è bassa la distribuzione varia molto.

Data una seconda variabile Y che assume m valori, si può definire l’entropia rispetto

a questa, in particolare si parla di entropia specifica condizionale H(X|Y=yi) come

l’entropia di X tra gli elementi che assumono il valore i-esimo di Y, e di entropia

condizionale media H(X|Y) come il minimo numero di bit necessari a trasmettere X

conoscendo Y

=1

∑ )(|

(|) = ( = = )

Ora si può definire il concetto di information gain, che è il numero di bit che

risparmierei per trasmettere X ipotizzando di conoscere Y

(|) = () − (|)

Utilizzando questo criterio, bisogna semplicemente calcolare l’info gain

dell’attributo di output rispetto a quelli noti: l’IG più alto determinerà l’attributo di

split. Questo metodo viene utilizzato anche per determinare il valore da scegliere

come soglia negli split binari di attributi continui. Si calcola IG* che è il massimo info

gain ottenibile dal dominio