Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

- funzione di transizione: X ≥

S(t + 1) = 1 SSE W S (G) θ

i i

θ vettore soglie.

W pesi.

i,j nj=1

P −

n (t) = W X (t) θ input netto a i al tempo t.

i i,j j j

X (t + 1) = g(n (t)) funzione di transizione.

i i 1

→ −

Da cui ricavo le reti neurali artificiali 1

−x

1+e

ˆ Caratteristiche strutturali:

- grande numero di unità.

- operazioni elementari.

- alto livello interconnessione.

ˆ Caratteristiche dinamiche:

- funzione uscita per ogni unità.

- modifica schema connessione per apprendimento.

- cambiamento di stato in funzione dello stato dei neuroni collegati.

22

6.1 Percettrone

Una rete in cui tutti gli input sono collegati direttamente agli output è chia-

mata rete neurale a strato singolo o rete di percettroni. Dato che ogni unità

di output è indipendente dalle altre, possiamo limitare il nostro esame ai

percettroni con una sola unità di output.

Esamino lo spazio delle ipotesi che un percettrone può rappresentare. Con

una funzione di attivazione a soglia, si può pensare che il percettrone può

rappresentare una funzione booleana.

Il percettrone a soglia è anche chiamato separatore lineare.

Considerando un iperpiano che a 2 dimensioni è una retta (and e or) con

punti neri (+) che indicano un punto nello spazio dove il valore della funzione

è 1 e quelli bianchi (-) in cui il valore è 0. Il percettrone può rappresentare

queste funzioni perchè esiste una linea che separa tutti i punti bianchi da

quelli neri, in questo caso sono funzioni linearmente separabili.

23

6.1.1 Apprendimento del percettrone

ˆ i pesi vengono fissati a caso e poi modificati.

ˆ apprendimento guidato da un insegnante.

ˆ procedura:

- classificazione vettori di input in 2 classi (A e B).

- numero infinito sia in A che in B di X (sequenza infinita).

t

- per ogni X la rete calcola la risposta Y .

k k

- con risposta errata, modifico i pesi, incrementando i pesi delle unità di

input attive se si è risposto 0 anzichè 1.

6.1.2 Teorema di Minsky-Papert e discesa del gradiente

La classe delle forme discriminabili da un percettrone semplice è limitata alle

forme linearmente separabili.

Un’analisi importante riguarda l’apprendimento nei percettroni a sigmoide

(che possono rappresentare solo separatori lineari ”morbidi”).

L’idea alla base di questo algoritmo e più in generale per le reti neurali è

di calibrare i pesi nella rete in modo da minimizzare una qualche misura di

errore sull’insieme di training. Una misura di errore ”classico” è la somma

dei quadrati degli errori.

Caso in cui ho un vero output y e un input x:

1

1 2 2

ERR = (y h (x))

E = w

2 2

Al fine di minimizzarlo, utilizzo il metodo della discesa del gradiente:

δE δERR

= ERR ( )

δw δw

j j

Derivata parziale di E rispetto ad ogni peso.

α= tasso di apprendimento.

Se ERR = (y h (x)) è positivo, l’output della rete deve essere piccolo e i

w

pesi aumentano per gli input positivi e diminuiscono per gli input negativi.

Se l’errore è negativo, avviene l’opposto.

Percettrone VS discesa del gradiente:

- nel primo caso è garantito il successo se gli esempi di training sono linear-

mente separabili e il tasso di apprendimento è sufficientemente piccolo.

è garantita la convergenza alle ipotesi con errore qua-

- nel secondo caso

dratico minimo e tasso di apprendimento sufficientemente piccolo. Inoltre

è garantita la convergenza quando i dati di training contengono rumore e

anche quando non sono separabili H.

24

6.1.3 Teorema di convergenza

Comunque si scelgano i pesi iniziali, se le classi A e B sono discriminabili, la

procedura di apprendimento termina dopo un numero finito di passi.

Il teorema di convergenza del percettrone (Rosenblatt, 1962) assicura che il

percettrone riuscirà a delimitare le 2 classi in un sistema linearmente sepa-

rabile.

In altre parole, nell’ottimizzazione non esistono minimi locali.

Problema: come ci si comporta in caso di situazioni non linearmente sepa-

rabili?

Nei casi non linearmente separabili si usano più percettroni disposti su più

livelli (o multistrato).

6.2 Reti neurali multistrato e retropropagazione

Il percettrone multistrato risolve il problema della rappresentazione della co-

noscenza ma introduce il problema dell’apprendimento:

- il teorema di convergenza non si estende ai percettroni multistrato.

- è necessario determinare un metodo per far apprendere anche i percettroni

multistrato back propagation

Obiettivi back propagation:

– partire da un insieme di percettroni con pesi casuali.

– insegnare in modo veloce.

– avere capacità di generalizzazione.

– avere insiemi di percettroni su larga scala.

Come saranno le reti? 2 strati? 4 strati?

Per l’apprendimento non c’è bisogno di passi iterativi, ma è sufficiente un

procedimento a ritroso, partendo dalle uscite, fino a giungere agli ingressi.

La rete viene addestrata con un insieme di coppie ingresso-uscita. E’ auspi-

cabile che riesca ad avere anche buona capacità di generalizzazione.

Per poter procedere all’indietro, tutte le funzioni devono essere invertibi-

li:

- Purtroppo la funzione soglia non lo è, quindi è necessario sostituirla con

una funzione simile, ma invertibile.

La scelta cade quindi sulla sigmoide, che ha buone caratteristiche di deriva-

bilità e continuità: 25 1

uscita = −k

1 + e

- Il Percettrone Multistrato, con almeno uno strato nascosto, è in grado di

approssimare qualsiasi tipo di funzione (Teorema di Kolmogorov).

26

7 Apprendimento statistico

Obbiettivo: imparare una teoria probabilistica del mondo per decisioni con

incertezza, apprendere come un processo di inferenza probabilistica.

Il Bayesian learning fornisce algoritmi di apprendimento pratici (Naive

Bayes learning, approccio bayesiano nella rete di apprendimento, combina

la conoscenza a priori con i dati osservati, richiede probabilità a priori) e

fornisce un utile contesto concettuale (gold standard per valutare gli altri

algoritmi di apprendimento, intuizione del rasoio di Occam).

Vantaggi:

- Nessuna ipotesi viene eliminata, anche se è inconsistente rispetto ai dati.

- Per ogni ipotesi h è data una probabilità P (h) che deve essere quella cor-

retta.

- P (h) viene man mano modificata.

- Sono consentite ipotesi che fanno previsioni probabilistiche.

Svantaggi:

- Non è facile stimare le probabilità a priori.

- Enorme costo computazionale nel caso generale.

Il Bayesian learning è visto come un aggiornamento della distribuzione di

probabilità oltre lo spazio delle ipotesi H = (h , h , . . . ), sono necessarie le

1 2

probabilità a priori, la j-esima osservazione ha come risultato d che deriva

j

dalla variabile D (training data D = d , d , . . . ), per calcolare le probabilità

j 1 2 P (D|h)P (h) .

a posteriori di ogni ipotesi si usa il teorema di Bayes: P (h|D) = P (D)

- P (h|D) =probabilità a posteriori di h dato D.

- P (h) =probabilità a priori dell’ipotesi h.

- P (D) =probabilità del training set.

Il Bayesian Learning calcola le probabilità condizionate di ciascuna ipotesi

con riguardo ai dati osservati, la previsione del prossimo valore di x è basata

sulla media pesata della verosimiglianza con riguardo a tutte le probabilità

delle ipotesi (non c’è bisogno di scegliere la ”miglior ipotesi”):

X X

|D) |D)

P (X|D) = P (X|D, h )P (h = P (X|h )P (h

i i i i

i i

La previsione bayesiana è ottimale, risulta corretta più frequentemente rispet-

to ad altre previsioni, però ha un alto costo dal punto di vista computazionale

(servono metodi di approssimazione).

27

Il MAP (maximum a posterior) learning sceglie l’ipotesi più probabile ri-

spetto ai dati (sceglie la più semplice e consistente):

P (D|h)P (h)

hMAP = argmaxP (h|D) = arg max =

P (D)

arg max P (D|h)P (h) = arg max [log(P (D|h) + log(P (h)]

Nel caso di ipotesi deterministica P (D|h) = 1 se è consistente, 0 altrimen-

ti. Con questo metodo per ogni h H viene calcolata una probabilità a

posteriori: P (D|h)P (h)

P (h|D) = P (D)

e hM AP è l’ipotesi con la maggiore P (D|h). A questo punto ho lo spazio

delle istanze X, lo spazio delle ipotesi H e gli esempi training D, se considero

l’algoritmo find S, la regola di Bayes quale ipotesi MAP mi darebbe? Find S

restituisce un’ipotesi MAP? Sia P (D|h) = 1 o 0, scegliamo P (h) in modo che

1

1 , allora P (h|D) =

la distribuzione sia uniforme, cioè P (h) = |H| |V SH,D|

se h è consistente, 0 altrimenti.

Per l’approssimazione ML si sceglie h che massimizza la verosimiglianza di

D (si ottiene il fit migliore sui dati).

hML = arg max P (D|h)

Se le probabilità a priori sono uniformi (tutte uguali tra loro) allora

hM AP = hM L

per data set molto grandi le prior diventano irrilevanti, ML è il metodo di

apprendimento statistico standard (non Bayesiano).

Data una funzione a valori reali f e gli esempi training hanno una parte di

rumore casuale (dato da una variabile casuale Gaussiana con media nulla),

l’ipotesi ML è quella che minimizza la somma del quadrato degli errori.

Il principio della minima lunghezza di descrizione:

hMAP = arg max P (D|h)P (h) = arg max (logP (D|h) + logP (h)) =

arg min (−logP (D|h) logP (h))

−log −log

Il codice ottimale per un evento p è (p) bit, quindi P (h) è la lun-

2 2

−log

ghezza di h con codice di ottimizzazione e P (D|h) è la lunghezza di D

2

dato h con codice di ottimizzazione. 28

Il rasoio di Occam preferisce l’ipotesi più corta mentre MDL preferisce

l’ipotesi h che minimizza hM DL = argmin(Lc (h), Lc (D|h)), dove LC(x)

1 2

è la lunghezza di descrizione di x con codifica c.

Fino ad ora abbiamo ricercato la probabilità maggiore dati i dati D, da-

ta la nuova istanza x qual è la classificazione più probabile? Non è hM AP ,

bisogna usare il classificatore Bayesiano ottimo:

X |h |D)

argmax P (v )P (h

j i i

Questo classificatore restituisce il risultato migliore, ma risulta dispendioso

nel caso ci siano molte ipotesi. L’algoritmo di Gibbs sceglie un’ipotesi a caso

(rispetto a P (h|D)) e usa questa per classificare la nuova istanza; inoltre i

concetti di assunzione del target risultano tracciati a caso da H rispetto alle

prior su H, quindi ≤ ∗

E(errorGibbs) 2 E(errorBayesOpt)

Se si suppone che la distribuzione delle prior su H è corretta e uniforme allora

scegliendo qualunque ipotesi da VS con probabilità uniforme, il suo errore

atteso è inferiore rispetto a 2 volte quello del classificatore ottimo di Bayes.

7.1 Il classificatore Naive Bayes

Il classificatore Naive Bayes è uno dei più pratici insieme agli alberi, reti e

nearest neighbour, si utilizza quando sono disponibili training set discre-

tamente grandi e gli attributi sono condizionatamente indipendenti

data la classificazione (applicazioni: diagnosi, classificazione di documen-

ti di testo). Data la funzione obbiettivo f : X V dove ogni istanza x è

descritta dagli attributi < a1, a2, ..., an >, il valore più probabile di f (X) è

|v

P (a , a , ..., a )P (vj)

1 2 n j

|a =

vMAP = arg max P (v , a , ..., a ) = arg max

j 1 2 n P (a , a , ..., a )

1 2 n

|v

arg max P (a , a , ..., a )P (v )

1 2 n j j

Si assume Y

|v |v

P (a , a , ..., a ) = P (a )

1 2 n j i j

i

e quindi il classificatore è Y |v

vNB = arg max P (v ) P (a )

j i j

i

29

Sottigliezze su NB: spesso l’assunzione di indipendenza condizionata è vio-

lata ma il classificatore funziona comunque, non c’è bisogno che le probabilità

a posteriori siano corrette, anzi spesso queste sono (poco realisticamente) vi-

cino a 0 o 1; se nessuna delle istanze del training con target v ha attributo

j

a la soluzione è la stima Bayesiana

j |v

P (a ) = (nc + mp)/(n + m)

i j

n è il numero di esempi nel training in cui v = v .

j

nc è il numero di esempi in cui v = v e a = a .

j i

|v

p è la stima della prior di P (a ).

i j

m è il peso dato alle prior.

NB è uno degli algoritmi più efficienti per la classificazione testuale (per

trovare articoli di interesse o classificare le pagine web per argomenti), quali

attributi usare? Concetto obbiettivo:

interessante: +, -, i documenti sono vettori di parole e ho un attributo per

ogni parola, per l’apprendimento si usano esempi training, le assunzioni sono

quelle di indipendenza condizionata e

|v |v ∀i,

P (a = w ) = P (a = w ) m

i k j m k j

Il classificatore ottimale di Bayes non fa assunzioni di indipendenza tra va-

riabili ed è computazionalmente pesante, il NB è efficiente grazie all’ipotesi

molto restrittiva di indipendenza condizionale di tutti gli attributi dato il va-

lore obiettivo v, le reti Bayesiane descrivono l’indipendenza condizionale tra

sottoinsiemi di variabili. Rappresentazione tramite grafico aciclico orientato:

i nodi sono variabili casuali, gli archi rappresentano la dipendenza condizio-

nale (ogni variabile è condizionalmente indipendente dai suoi non discendenti,

dati i suoi genitori). 30

8 Support Vector Machines (metodi kernel)

Si usano i Support Vector Machines perchè hanno un algoritmo di appren-

dimento efficiente e sono in grado di imparare funzioni di separazione non

lineari complesse (il percettrone semplice è efficiente solo dal punto di vista

dell’algoritmo di apprendimento mentre il percettrone multistrato impara

funzioni di separazione non lineari complesse).

I vettori sono caratterizzati da direzione, verso e lunghezza; Essi possono

essere sommati oppure moltiplicati per uno scalare.

I Support Vector Machines sono metodi che attraverso argomentazioni teo-

riche sulla teoria statistica dell’apprendimento e per mezzo di un problema

di programmazione matematica, trovano l’iperpiano separatore che permette

di classificare un insieme di punti (linearmente separabili). Per capire quale

separatore è migliore si prolunga parallelamente il separatore fino a tocca-

re un punto della prima classe, si fa lo stesso per la seconda; tanto più ampio

è lo spazio racchiuso tra questi due nuovi iperpiani tanto più il separatore è

”robusto” (l’iperpiano generalizza).

Scrivo l’algoritmo:

Dati i punti di training S = < x , y >, ..., < x , y >, se ogni vettore ap-

1 1 n n

{+1, −1},

partiene a una delle 2 classi i punti sono linearmente separabili

y (< w, x > +b) > 0; si cerca l’iperpiano o le funzioni lineari associate che

i i

meglio separa i punti delle 2 classi. Il margine funzionale di un punto rispetto

all’iperpiano (w, b) è y (< w, x > +b), il margine funzionale dell’iperpiano

i i

rispetto al training set è uguale al minimo (a seconda che il punto appartie-

ne alla prima o alla seconda classe, perché il margine funzionale sia grande

è necessario che abbia un grande valore positivo/negativo). Se il margine

funzionale è maggiore di 0, la classificazione va bene e quindi tanto più è

grande questo valore tanto più sono sicuro sulle previsioni che faccio, però

possono esserci dei problemi perché il margine funzionale è invariante rispet-

to a un iperpiano riscalato. Nel caso in cui ho a che fare con questi problemi,

utilizzo il margine geometrico, il quale rappresenta la distanza geometrica

dall’iperpiano:

- il margine geometrico di un punto (x , y ) rispetto all’iperpiano (w, b) è

i i

(<w,x >+b)

i .

y = y

i i kwk

- il margine geometrico dell’iperpiano rispetto al training set è ρ = min y−i.

t=1,...,n

Note sul margine geometrico:

Ancora è necessario y > 0 per avere una buona classificazione, se il punto non

i

è correttamente classificato otteniamo un margine che eguaglia la distanza

31

negativa dall’iperpiano, anche questo margine è invariante (si può riscalare);

questa misura da meglio l’idea di distanza di un punto in R .

n

k< k=

Un iperpiano canonico min w, x > +b 1, quindi il margi-

i

t=1,...,n 1 k k=

; se w 1 i due margini

ne funzionale è 1 mentre quello geometrico kwk

coincidono, cioè il margine funzionale è uguale al margine geometrico.

Si cercherà quindi di estendere il più possibile il margine geometrico, cioè

min f (x) s.t. g(x) 0 e h(x) = 0 si deve trovare x che rende minima la

funzione obiettivo f sotto i 2 vincoli, però non sempre esiste una soluzione

e, se esiste, difficilmente si può trovarla per via analitica, a volte si può ap-

prossimare con metodi iterativi.

Dunque si utilizzano i Support Vector Machines per la capacità di sepa-

razione di massimo margine dell’iperpiano e perché esiste un’unica soluzione.

- Formulazione del programma precedente: la soluzione si può scrivere,

cioè in termini di un sottoinsieme di esempi del training set che giacciono sul

margine dell’iperpiano.

- Formulazione della funzione di decisione associata alla soluzione:

nella funzione di decisione si può scrivere in termini di prodotto interno tra

x e x.

i

- Se i punti non sono linearmente separabili bisogna ricorrere a

metodi kernel: lo spazio iniziale viene rimappato in uno spazio in cui i

punti sono linearmente separabili, poi si utilizza una funzione kernel (ad

esempio lineare o polinomiale). 32

9 Reinforcement Learning

a a a

0 1 2

−→ −→ −→

s s s s

0 1 2 3

r r r

0 1 2

Partendo dallo stato s si arriva a s attraverso l’azione a e si ha la ricompen-

0 1 0

sa r , si passa a s con l’azione a e la ricompensa è r , cosı̀ via. L’obbiettivo

0 2 1 1

è imparare a scegliere le azioni a che massimizzano la ricompensa futura

t

r + γ r + γ r + ... dove 0 < γ < 1 è un fattore di sconto.

0 1 2 2 3

Alcune applicazioni:

- apprendimento di robot nell’attraccare alla stazione di batteria.

- apprendere come scegliere le azioni che ottimizzano l’output di u’industria.

- apprendere a giocare a Backgammon.

Caratteristiche:

- Ricompensa ritardata.

- Non c’è un feedback diretto (segnale di errore) per azioni buone e cattive.

33

- Opportunità per un’esplorazione attiva.

- Possibilità che lo stato sia solo parzialmente osservabile.

9.0.1 Processo di decisione di Markov

C’è un set finito di stati S e azioni A, ad ogni istante l’agente osserva lo stato

∈ ∈

s S e sceglie l’azione a A(s ), osserva subito la ricompensa r e lo stato

t t t t

cambia in s + 1. L’assunzione di Markov è r = r(s , a ) e s + 1 = δ(s , a ), si

t t t t t t t

osserva che la ricompensa e lo stato futuro dipendono solo da stato

e azione correnti, le due funzioni δ e r possono essere non deterministiche

e non necessariamente l’agente le conosce.

Il compito dell’apprendimento è eseguire azioni, osservare i risultati e impa-

rare un metodo π : S A che associa ad ogni stato un’azione in modo da

ottimizzare la ricompensa attesa E[r + γ r + γ r + ...] a partire da qualun-

0 1 2 2 3

que stato s. La funzione obbiettivo è π ma non ci sono esempi diretti della

forma < s, π(s) > ma sono per la forma << s, a >, r >. Se si considera

un ambiente deterministico, r e δ sono funzioni deterministiche di s e a, per

valutare il metodo π adottato dall’agente si osserva la ricompensa cumulativa

P

scontata per il tempo V π(s) = r + γ r + γ r + ... = = 0...∞ r γ ;

0 1 1 2 2 i i

i

dunque l’obbiettivo è individuare il metodo π che massimizza V π(s).

Definizioni alternative:

- Orizzonte finito della ricompensa:

X = 0, ..., h r

i

i

- Ricompensa media: X

lim = 0, ..., h r

i

h→∞ i

- Funzione del valore di stato: indica la ricompensa che si ottiene par-

tendo dallo stato s con il metodo π: X

V π(s) = r + γ r + γ r + ... = = 0 γ r

0 1 1 2 2 i i

i

- Funzione del valore dell’azione: indica la ricompensa che si ottiene

partendo da s, usando l’azione a e seguendo il metodo pi:

Qπ(s, a) = r(s, a) + γ r + γ r + ... = r(s, a) + γV π(δ(s, a))

1 1 2 2

34

- L’approcio dinamico di programmazione è:

∗ ∗

π (s) = arg max a(r(s, a) + γV (δ(s, a))

Si potrebbe cercare di far apprendere all’agente la funzione di valutazione

V , poi si potrebbe fare una ricerca per scegliere l’azione migliore da ogni

∗ ∗

stato s perchè π (s) = arg max a(r(s, a) + γV (δ(s, a)):

- questo funziona se l’agente conosce le funzioni r e δ, altrimenti non può

decidere le azioni in questo modo, poichè π (s) = arg max a Q(s, a).

- se l’agente conosce Q allora può scegliere le azioni ottimali anche senza

conoscere δ. ∗ ∗

Le funzioni Q e V sono strettamente legate V (s) = max a Q(s, a), questo

ci permette di scrivere ricorsivamente:

∗ 0 0

Q(s , a ) = r(s , a ) + γV (δ(s , a ))) = r(s , a ) + γmax a Q(s + 1, a )

t t t t t t t t t

Indichiamo con Q̂ l’approssimazione di Q fatta dall’agente e la formula è:

0 0 0

Q̂ = r + max a Q̂(s , a )

0

Dove s è lo stato che si ottiene applicando l’azione a allo stato s. Per ogni

s, a fa Q̂ := 0, si osserva lo stato s, si ripetono continuamente le azioni: sele-

ziono l’azione a e la eseguo, ricevo immediatamente la ricompensa r, osservo

0 0 0 0

il nuovo stato s , aggiorno Q̂(s, a) = r + γmaxQ̂(s , a ), s = s .

Metodo iterativo di valutazione: l’equazione di Bellman si usa come

regola di aggiornamento della funzione di azione-valutazione

X 0 0 0

Q + 1π(s, a) = r(s, a) + γ a π(δ(s, a), a )Q π(δ(s, a), a )

k k

Miglioramenti del metodo: Supponiamo di avere determinato la fun-

zione di valutazione V π, per un metodo arbitrariamente deterministico π.

6

Vorremmo sapere se per alcuni stati s è meglio scegliere un’azione a = π(s).

Selezionare a e seguire il metodo π ci restituisce la ricompensa Qπ(s, a).

Se Qπ(s, a) > V π allora a è migliore di π(s).

0 0

Quindi si sceglie il nuovo metodo π tale che p (s) = arg max a Qπ(s, a) =

arg max a r(s, a) + γV π(δ(s, a)).

L’idea del valore iterato è non attendere che il metodo di valutazione converga

ma migliorare il metodo dopo ogni iterazione

V + 1π(s) = max a(r(s, a) + γV π(δ(s, a)))

k k

35

oppure 0 0

Q + 1π(s, a) = r(s, a) + γmax a Q π(δ(s, a), a )

k k

36

10 Apprendimento non supervisionato

(Clustering)

Diversamente dall’apprendimento supervisionato, la clusterizzazione non su-

pervisionata (clustering) costruisce modelli a partire da dati non appartenenti

a classi predefinite (non esiste attributo target).

Il clustering è un procedimento che si pone come obiettivo la suddivisio-

ne di un insieme di elementi in sottoinsiemi.

Gli elementi di ogni sottoinsieme sono accomunati da caratteristiche simi-

li.

Sebbene la classificazione è un mezzo efficace per distinguere gruppi o classi

di oggetti essa richiede una costruzione e un’etichettatura del training set

che risultano spesso costose.

Spesso può essere desiderabile procedere in senso inverso partizionando pri-

ma i dati in gruppi sulla base della loro similarità (ovvero, utilizzando il

clustering) e, successivamente, assegnando le etichette al numero relativa-

mente piccolo di gruppi cosı̀ ottenuto.

Ulteriori vantaggi di tale processo di clustering riguardano il fatto che esso è

adattabile ai cambiamenti e consente di scegliere quali sono le caratteristiche

di interesse per distinguere i vari gruppi.

Come funzionalità del data mining, il clustering può essere uti-

lizzato per esaminare le distribuzioni dei dati, per osservare le ca-

ratteristiche di ciascuna distribuzione e per focalizzarsi su quelle

di maggiore interesse. Alternativamente, esso può essere utilizzato come

un passo di pre-processing per altri algoritmi, quali la classificazione e la ca-

ratterizzazione, che operano sui cluster individuati.

Il clustering dei dati è una disciplina scientifica giovane che sta attraver-

sando un enorme sviluppo. In esso convergono aree di ricerca quali il data

mining, la statistica, il machine learning, la tecnologia dei database spaziali,

la biologia e il marketing.

Il clustering è un esempio di learning non supervisionato; a differenza della

classificazione (che è una forma di learning supervisionato), il clustering non

si basa su classi predefinite e su campioni di training etichettati. Per tale

ragione, il clustering è una forma di learning per osservazione piuttosto che

di learning per esempio. 37

10.1 Tipi di dati nel Clustering

Si supponga che un insieme di dati da clusterizzare contenga n oggetti che

possono rappresentare persone, cose, documenti, nazioni, ecc.

Gli algoritmi di clustering tipicamente operano su una delle seguenti strut-

ture dati:

- Una matrice di dati: questa rappresenta n oggetti, come ad esempio

persone, con p variabili (chiamate anche misure o attributi), quali l’età, l’al-

tezza, il peso, la razza, e cosı̀ via. La struttura è nella forma di una tabella

×

relazionale, o matrice n p (n oggetti per p variabili):

 

x ... x ... x

1,1 1,f 1,p

... ... ... ... ...

 

 

x ... x ... x

i,1 i,f i,p

 

 

... ... ... ... ...

 

x ... x ... x

n,1 n,f n,p

- Una matrice di dissimilarità: questa memorizza il grado di dissimilarità

di ciascuna coppia degli oggetti coinvolti. Essa è spesso rappresentata da una

×

tabella n n, come di seguito specificato:

 

0 0 0 0 0

d(2, 1) 0 0 0 0

 

 

d(3, 1) d(3, 2) 0 0 0

 

 

... ... ... ... ...

 

d(n, 1) d(n, 2) d(n, 3) ... 0

dove d(i, j) è la differenza o dissimilarità misurata tra gli oggetti i e j. Si

noti che d(i, j) = d(j, i) e che d(i, i) = 0.

10.2 I metodi di partizionamento

Dato un database di n oggetti, e k, il numero di cluster da costruire, un

algoritmo di partizionamento organizza gli oggetti in k partizioni (k n),

dove ciascuna partizione rappresenta un cluster.

I cluster sono costruiti con il fine di ottimizzare un criterio di partizionamen-

to oggettivo, spesso denominato funzione di similarità, come la distanza, in

38

modo tale che gli oggetti all’interno di un cluster siano ”simili” mentre gli

oggetti di cluster differenti siano ”dissimili”.

10.2.1 Il metodo di partizionamento k-Means

L’algoritmo k-means riceve in input un parametro k e partiziona un insieme

di n oggetti in k cluster in modo tale che la similarità intra-cluster risultante

sia alta mentre la similarità inter-cluster sia bassa.

La similarità dei cluster è misurata rispetto al valore medio degli oggetti in

un cluster; tale valore può essere visto come il centro di gravità del cluster.

L’algoritmo k-means procede nel seguente modo.

Innanzitutto, seleziona in modo casuale k degli oggetti, ciascuno dei quali

rappresenta inizialmente la media o il centro di un cluster.

Ciascuno degli oggetti rimanenti viene associato al cluster più simile basan-

dosi sulla distanza tra l’oggetto e la media del cluster.

Esso, quindi, calcola la nuova media per ciascun cluster.

Tale processo viene iterato fino a quando non si raggiunge la convergenza di

una determinata funzione criterio. Tipicamente viene utilizzato come criterio

l’errore quadratico, definito come:

X X 2

|p − |

m

E = i

p∈C

i=1,...,k i

dove E è la somma dell’errore quadratico per tutti gli oggetti del database,

p è il punto nello spazio che rappresenta il dato oggetto ed mi è la media del

cluster C (sia p che mi sono multidimensionali).

i

Questo criterio cerca di rendere i k cluster risultanti quanto più compatti e

separati possibili.

L’algoritmo tenta di determinare k partizioni che minimizzano la funzione

errore quadratico. Esso si comporta bene quando i cluster sono compatti e

piuttosto ben separati uno dall’altro.

Il metodo è relativamente scalabile ed efficiente nel processare grandi insiemi

di dati perchè la complessità computazionale dell’algoritmo è O(nkt), dove

n è il numero totale di oggetti, k è il numero di cluster e t è il numero di

iterazioni. Normalmente, k n e t n.

Il metodo spesso termina in un ottimo locale.

Il metodo, tuttavia, può essere applicato soltanto quando è definita la media

di un cluster. Questo può non accadere in molte applicazioni, ad esempio

quando sono coinvolti dati con attributi categorici.

La necessità per gli utenti di specificare all’inizio k, ovvero il numero dei

39


ACQUISTATO

1 volte

PAGINE

41

PESO

401.99 KB

AUTORE

Pagani21

PUBBLICATO

+1 anno fa


DETTAGLI
Corso di laurea: Corso di laurea in scienze statistiche ed economiche
SSD:
A.A.: 2017-2018

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher Pagani21 di informazioni apprese con la frequenza delle lezioni di Apprendimento automatico (machine learning) e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Milano Bicocca - Unimib o del prof Mauri Giancarlo.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Corso di laurea in scienze statistiche ed economiche

Appunti Algebra lineare
Appunto
Appunti di Calcolo delle Probabilità
Appunto
Analisi matematica 1
Appunto
Appunti Informatica
Appunto