Data Mining e Scoperta di Conoscenza
Seminario
Data Mining with
Evolutionary Algorithms
Andrea Terlizzi
L’evoluzione biologica e…
La teoria Darwiniana
I principi
dell’evoluzione:


Variazione genetica
Selezione naturale
Solo i migliori
sopravvivono…
2
… i problemi computazionali
La metafora di fondo
Problemi complessi in svariati settori, difficili
da affrontare con mezzi analitici:





Pianificazione
Progettazione
Simulazione
Machine learning
…
3
Gli algoritmi evolutivi
Il flusso di esecuzione di un tipico algoritmo evolutivo
Gli algoritmi evolutivi comprendono:
 Algoritmi genetici
 Programmazione genetica
 Strategie evolutive
 Programmazione evolutiva
4
Gli algoritmi genetici (GA)
J. Holland (1975)
La principale differenza tra gli algoritmi
genetici e la programmazione genetica è nelle
strutture dati utilizzate.
Negli algoritmi genetici gli individui vengono
rappresentati tramite stringhe (generalmente
di bit)
1000111110000100 0011011010011010
0001110010111001 1110001000010111
5
La programmazione genetica (GP)
J. Koza (1992)
Nella
programmazione
genetica
la
popolazione è costituita da programmi
(rappresentati da alberi di parsing)
Funzioni
Terminali
6
La funzione fitness
La funzione fitness definisce i criteri per
la classificazione, la selezione e
l’inclusione nelle prossime generazioni
degli individui
Metodi di selezione:
Roulette wheel
selection
Tournament selection
Rank selection
…

7
Gli operatori genetici
8
Variazioni all’algoritmo di base
Nel modello classico tutta la popolazione
viene sostituita ad ogni generazione. Esistono
altri modelli:
Steady State: solo alcuni individui vengono
sostituiti ad ogni generazione
Elitismo: ai migliori individui viene garantita
la permanenza nella successiva generazione
Modello a isole: si ha un insieme di
popolazioni, soggette a fenomeni migratori,
che evolvono in maniera autonoma
9
Data Mining Tasks
Nel Data Mining sono state studiate e
sperimentate tecniche genetiche per la
risoluzione di problemi quali:
 Classificazione
 Clustering
 Scoperta di regole associative
10
Cosa vedremo…
GA (GP) e Classification Rules

Valutazione della qualità predittiva di regole del
tipo IF-THEN
GP e Classificazione

Analisi e confronto di 5 classificatori
GA e Clustering

L’algoritmo K-means “geneticamente” modificato
GA e Association Rules

Un metodo per la ricerca di itemsets frequenti
11
GA & Classification Rules
Una regola di classificazione è una formula
logica del tipo:
IF cond1 AND… AND condn THEN class=ci
Antecedente
Conseguente
Idee base:


Le regole candidate sono rappresentate come
individui di una popolazione
La qualità delle regole è calcolata da una funzione
fitness
12
GA & Classification Rules
Tre problematiche principali:



Come
definire
un
individuo
per
rappresentare una regola IF-THEN
Come adattare gli operatori genetici alla
gestione delle regole
Come progettare la funzione fitness
13
Rappresentazione degli individui
Due approcci:

Michigan
1 individuo  1 regola
 Sintassi semplice
 Problemi nel valutare insiemi di regole

Pittsburgh
1 individuo  più regole
 Sintassi complessa
 Calcolo della fitness più complicato
14
Rappresentazione degli individui
Per la parte antecedente (congiunzione di
condizioni)


Supponendo che un attributo possa assumere k
valori discreti, una condizione sul valore
dell’attributo si codifica con k bit
Es. L’attributo Stato_civile può assumere 4 valori:
single, sposato, divorziato, vedovo. Occorre,
quindi, una stringa di 4 bit. Il valore 0110, ad
esempio, rappresenta la seguente regola:
IF (Stato_civile=“sposato” OR “divorziato”)
15
Rappresentazione degli individui
Per la parte conseguente
predetta)
 Almeno due varianti:
(classe
 Inserire
la classe nella
dell’individuo
 Scegliere
la
classe
in
deterministica
codifica
maniera
La più predetta
 Quella che massimizza la fitness

16
Gli operatori genetici
Poiché non si è in grado di sapere a priori
quante condizioni producano una “buona”
regola bisogna trattare individui di lunghezza
variabile
L’operatore di crossover deve essere
modificato, anche per evitare di generare
regole illegali
Applicando il crossover ai seguenti individui:
1:(Età>25) AND (Stato_civile=“sposato”)
2:(Lavora=“Si”) AND (Età<21)
17
Gli operatori genetici
Potrebbe essere generata la seguente regola,
chiaramente non valida:
IF (Età>25) AND (Età<21)
Per ovviare a questo inconveniente si possono
codificare gli attributi nello stesso ordine in cui
essi appaiono nel data set, inserendo
condizioni “vuote” se necessario
1:(Età>25) AND (Stato_civile=“sposato”) AND empty condition
2:(Età<21) AND
empty condition
AND (Lavora=“Si”)
18
Gli operatori genetici
Mutazione generalizzata/specializzata
(Età>25) AND (Stato_civile=“single”)
Generalizzazione
(Età>21) AND (Stato_civile=“single”)
Specializzazione
(Età>30) AND (Stato_civile=“single”)
19
La funzione fitness
Requisiti:



Accuratezza predittiva
Comprensibilità
Interesse
Per una regola (IF A THEN C):
CF (Fattore di confidenza)=|A&C| / |A|


|A|=numero di esempi che soddisfano A
|A&C|=numero di esempi che soddisfano A ed
hanno come classe predetta C
20
La funzione fitness
La qualità di una regola può essere
espressa più accuratamente utilizzando
una matrice 2x2, detta matrice di
confusione
Classe attuale
Classe
Predetta
C
Not C
C
TP
FN
Not C
FP
TN
21
La funzione fitness
Le etichette nei quadranti hanno i seguenti
significati:




TP (True Positives) = gli esempi che soddisfano sia
A che C
FP (False Positives) = gli esempi che soddisfano A
ma non C
FN (False Negatives) = gli esempi che non
soddisfano A ma soddisfano C
TN (True Negatives) = gli esempi che non
soddisfano né A né C
Il fattore di confidenza diventa:
CF=TP / (TP+FP)
22
La funzione fitness
La completezza di una regola:
Comp=TP / (TP+FN)
La comprensibilità varia in base al dominio
applicativo. In generale:


–condizioni
+chiarezza
L’interesse è una misura che richiede
l’interazione con l’utente
La funzione fitness può essere definita come
la somma pesata di queste caratteristiche
23
GP & Classification Rules
Si considera ora l’approccio Pittsburgh
Ogni individuo corrisponde ad un insieme di
regole antecedenti codificate in DNF
L’insieme dei nodi funzione contiene gli
operatori logici: AND, OR e NOT
L’insieme dei nodi terminali consiste di tutte
le possibili condizioni della forma Attri=Valij
24
GP & Classification Rules
Vengono introdotte alcune restrizioni nella
struttura dell’albero:
1) Il nodo radice è sempre un nodo OR
2) Ad eccezione della radice, ogni nodo OR ha come
genitore un altro nodo OR e può avere figli di ogni tipo
3) Ogni nodo AND ha come genitore un nodo AND o un
nodo OR e può avere come figli AND, NOT o nodi
terminali
4) Un nodo NOT può avere come unico figlio un nodo
NOT o un nodo terminale
5) Non possono esserci 2 o più nodi terminali riferiti ad
uno stesso attributo nella stessa regola (per evitare
regole invalide)
25
GP & Classification Rules
26
Gli operatori genetici
Vengono utilizzati gli operatori genetici
convenzionali, condizionati dall’impossibilità di
generare individui che rappresentino regole
illegali
Es. GP Crossover
27
La funzione fitness
Si utilizza come in
matrice di confusione
precedenza
la
Se due individui hanno la stessa fitness
viene preferito quello con minore
complessità
Complessità=2*(N° regole + N° condizioni)
28
Rule pruning
Un apposito operatore rimuove alcune
condizioni dall’albero (semplifica e
generalizza le regole)
Meno una condizione è rilevante e
maggiore è la probabilità che venga
rimossa
29
GP & Classificazione
La classificazione è un processo a due
fasi:


Costruzione di un modello a partire da un
insieme di esempi (training set)
Utilizzo del modello
 Stima dell’accuratezza (mediante test set)
 Classificazione delle istanze ignote
30
GP & Classificazione
6 datasets dall’UCI Machine Learning
Repository, differenti per dominio, taglia e
complessità
5 metodi alternativi di classificazione:





Binary Decomposition
Static Range Selection
Dynamic Range Selection
Class Enumeration
Evidence Accumulation
31
GP & Classificazione
Gli insiemi delle funzioni e dei terminali vengono standardizzati
per avere omogeneità nella costruzione della soluzione in
ognuno dei 5 metodi
32
GP & Classificazione
Un esempio di programma
33
Binary Decomposition
La programmazione genetica è efficiente per
problemi di classificazione binaria
Se la classificazione è multiclasse diventa
difficile trovare punti di divisione significativi
tra le classi
In questo metodo il problema multiclasse
viene decomposto in un insieme di
sottoproblemi binari
34
Static Range Selection
Dividere le classi in base ad un’analisi
intuitiva del problema
Caso binario: uguale al precedente
(split tra valori positivi e negativi)
Caso multiclasse: non c’è ottimalità
35
Dynamic Range Selection
Per ogni individuo (programma) vengono
determinati dinamicamente gli intervalli di
classe
Un sottoinsieme del training set viene
utilizzato per ottenere la segmentazione
dell’output
Per praticità è opportuno fissare un range
principale [-X,X] nel quale debbano entrare
tutte le classi
36
Class Enumeration
Vengono apportate
alcune modifiche agli
insiemi base
37
Evidence Accumulation
Anche in questo modello vengono
introdotti dei cambiamenti
Si utilizza un vettore ausiliario che
contiene un elemento per ogni classe
38
Evidence Accumulation
Appositi nodi terminali modificano il valore
delle classi
La classificazione viene decisa considerando la
classe che ha ottenuto il valore più alto
39
Analisi dei risultati
Datasets Binari
Datasets Multiclasse
40
Analisi dei risultati
I 5 metodi sono stati confrontati con altri 33
classificatori
E’ stato ottenuto un ranking mostrato in
tabella (viene indicato il “piazzamento” in
classifica da 1 a 34)
41
GA & Clustering
Un cluster è una collezione di istanze
tali che:


le istanze dello stesso cluster sono simili tra
loro (alta somiglianza intra-classe)
le istanze di cluster diversi sono dissimili
(bassa somiglianza inter-classe)
42
GA & Clustering
Un algoritmo di partizionamento, date n
istanze e un numero k, divide le istanze in k
partizioni
Obiettivo: massimizzare la qualità del
clustering
Soluzione ottimale: può essere ottenuta
enumerando tutte le possibili partizioni.. non
è praticabile
Soluzione euristica: basata sulla ricerca di
minimi locali
43
GA & Clustering
Il metodo K-means
Input: k (numero di clusters), n (oggetti)
 Scegli k oggetti come centri dei cluster
 Ripeti
 Assegna ogni oggetto al cluster il cui centro è
più vicino
 Ricalcola i nuovi centri dei cluster

Finchè non c’è nessun cambiamento
44
Genetic K-means Algorithm (GKA)
Combina la semplicità dell’algoritmo kmeans e la robustezza degli algoritmi
genetici
Utilizza due operatori appositi:


L’operatore K-means (invece del crossover)
La mutazione distance-based
45
Genetic K-means Algorithm
Sia {xi, i=1,…,n} l’insieme degli n pattern
(vettori di dimensione d) da partizionare in k
cluster
Si possono definire i e k delle variabili
binarie:
1
se l’i-esimo pattern appartiene al k-esimo cluster
wik=
0 altrimenti
46
Genetic K-means Algorithm
Quindi, la matrice W=[wij] ha le seguenti
proprietà:
wij  {0,1}
k
 w =1
j=1
ij
Per codificare W in una stringa, si considera
un individuo di lunghezza n, i cui geni
possono assumere valori compresi tra 1 e k.
Ogni gene corrisponde ad un pattern e il suo
valore rappresenta il numero del cluster al
quale esso appartiene
47
Genetic K-means Algorithm
La popolazione iniziale è selezionata
casualmente
L’operatore
selezione
sceglie
un
individuo dalla popolazione secondo la
strategia roulette wheel
P(s i ) 
stringa
fitness
F(s i )
n
 F(s )
j=1
j
48
Genetic K-means Algorithm
In questo contesto il valore di fitness di
una stringa dipende dalla variazione
totale all’interno del cluster TWCV
(detta anche square error)
Più lo square error è basso e più il
valore di fitness è alto
49
Genetic K-means Algorithm
Ogni gene subisce una mutazione con
probabilità Pm
Questa probabilità dipende da quanto il dato
sia vicino ad un cluster center
L’operatore K-means non è altro che
l’applicazione di un unico passo dell’algoritmo
classico
I risultati sperimentali hanno dimostrato che:


La mutazione è indispensabile per raggiungere
l’ottimo globale
L’operatore K-means aumenta considerevolmente
50
la velocità di convergenza dell’algoritmo
Genetic K-means Algorithm
Input: Mutation Probability Pm; Population size N;
Maximum number of generation MAX_GEN;
Output: Solution string s*;
{ Initialize P;
gen=MAX_GEN;
s*=P1; (Pi is the i th string in P)
while (gen>0)
{
Calculate Fitness values of strings in P;
P’=Selection(P);
for i=1 to N, Pi=Mutation(P’i);
for i=1 to N, K-means(Pi)
s=string in P such that the corresponding weight matrix Ws has
the minimum SE measure;
if(S(Ws*)>S(Ws)), s*=s;
gen=gen-1;
}
output s*;
51
}
Genetic K-means Algorithm
All’aumentare del numero dei cluster,
cresce anche il tempo richiesto per
raggiungere la partizione ottimale
Ciò e dovuto ad uno spazio di ricerca
più ampio
Il GKA
globale
raggiunge
sempre
l’ottimo
52
Fast Genetic K-means Algorithm
Successivi studi hanno generato dei
miglioramenti
all’algoritmo.
In
particolare:



Calcolo più efficiente della TWCV
No overhead per l’eliminazione delle
stringhe illegali
Semplificazione dell’operatore di mutazione
Il nuovo algoritmo raggiunge l’ottimo
globale 20 volte più velocemente del
GKA
53
GA & Association Rules
Le regole associative sono uno degli
strumenti più utilizzati per scoprire
relazioni tra gli attributi di un database
Una regola associativa è un’implicazione
della forma AB dove AI, BI e
AB= (I insieme di items)
54
GA & Association Rules
Misure che valutano l’interesse di una regola
A  B:


Supporto
support(A  B) = Prob {AB}
Confidenza
confidence(A  B) = Prob {B|A}
Obiettivo: determinare le regole con supporto
e confidenza superiori ad una soglia data
55
GA & Association Rules
Itemset: un insieme di attributi appartenenti
al database
La frequenza di un itemset è il numero di
transazioni in cui sono presenti tutti gli
elementi di un itemset
Frequent Itemset: un itemset la cui frequenza
supera la soglia minima di supporto
Obiettivo:

Ricerca degli itemsets frequenti
56
GA & Association Rules
Database numerici  Regole associative
quantitative
I valori degli attributi variano all’interno
di un intervallo, anziché assumere valori
discreti
Occorre
discretizzare
gli
attributi,
oppure… si può utilizzare un algoritmo
57
genetico!
Rappresentazione degli individui
Un individuo è un k-itemset
li e ui limitano l’intervallo a cui può
appartenere ai
Il numero di attributi di ogni itemset è
scelto casualmente tra 2 e il numero di
attributi presenti nel database
58
Gli operatori genetici
L’operatore selezione si basa su una strategia
elitarista
Il crossover ha l’effetto di generare dei nuovi
individui aventi attributi e intervalli presi da
entrambi gli itemsets genitori:
La mutazione consiste nell’alterare uno o più
intervalli all’interno di un itemset
59
La funzione fitness
F(i)=cov - (mark*) – (ampl*) + (nAttr*)
Contiene 4 misure:
Covered (cov): indica il numero di records coperti
dall’itemset che rappresenta l’individuo
Marked (mark): indica che è un record è stato già
coperto da un itemset. Il fattore di penalizzazione
 controlla l’overlapping tra gli itemsets
Amplitude (ampl): serve a controllare la crescita
degli intervalli tramite il fattore 
Number of Attributes (nAttr): tramite il fattore 
permette di regolare la quantità degli attributi
contenuti in un itemset
60
Algoritmo GAR
Algoritmo GAR (Genetic Association Rules)
nItemset = 0
while (nItemset < N) do
nGen = 0
generate first population P(nGen)
while (nGen < NGENERATIONS) do
process P(nGen)
P(nGen+1) = select individuals of P(nGen)
complete P(nGen+1) by crossover
make mutations in P(nGen+1)
nGen++
end_while
I[nItemset] = choose the best of P(nGen)
penalize records covered by I[nItemset]
nItemset++
end_while
61
Analisi dei risultati
Sono stati utilizzati i seguenti parametri:




MinSupport=20%
=0,4
=0,7
=0,5
62
63
Bibliografia
1.
2.
3.
T. Mitchell, Machine Learning.
J. Han & M. Kamber, Data Mining Techniques.
A. Freitas, A Survey of Evolutionary Algorithms for Data
4.
R. Mendes & F. Voznika & A. Freitas & J. Nievola, Discovering
5.
6.
7.
8.
Mining and Knowledge Discovery.
Fuzzy Classification Rules with Genetic Programming and CoEvolution.
T. Loveard & V. Ciesielski, Representing Classification
Problems in Genetic Programming.
K. Krishna & M. Narashima Murty, Genetic K-means Algorithm.
Y. Lu & S. Lu & F. Fotouhi & Y. Deng & S. J. Brown, Fast
Genetic K-means Algorithm and its Application in Gene
Expression Data Analysis.
J. Mata & J.L. Alvarez & J.C. Riquelme, An Evolutionary
Algorithm to Discover Numeric Association Rules.
64