6. L’ALGORITMO
B-FREM
6.1 Presentazione
B-FREM (C. Ordonez, E. Omiecinski, N. Ezquerra - 2001) è basato sul ben noto algoritmo di clustering Expectation-Maximization (EM), un metodo statistico generale di stima della massima verosimiglianza, che può essere usato per eseguire clustering.
6.1.1 Limitazioni dell’algoritmo EM
L’algoritmo EM ha molte caratteristiche vantaggiose: una solida base statistica, garanzie dimostrate di ottimalità, robustezza nei confronti del rumore e dei dati fortemente asimmetrici.
Purtroppo, almeno nella sua versione classica, EM presenta anche diversi svantaggi:
– in generale è difficile da inizializzare e la qualità della soluzione finale dipende da quella dell’inizializzazione;
– può convergere ad un ottimo locale, restituendo una soluzione lontana dalla migliore anche se pur sempre accettabile;
– necessita di un numero di iterazioni ignoto per convergere a una buona soluzione; – è difficile stabilire una soglia valida in generale per fissare il massimo numero di
iterazioni, quindi è difficile garantire le prestazioni dell’algoritmo;
– solitamente sono necessarie molte passate sui dati, ne sono richieste due per ciascuna iterazione;
– i calcoli soffrono di instabilità quando le varianze si avvicinano a zero; questo problema comunemente si verifica in presenza di dataset con attributi nominali o in caso di perdita di informazione;
– la presenza di outlier porta a probabilità nulle, rendendo i calcoli non definiti o instabili e producendo risultati non accurati per dati ad elevata dimensionalità.
6.1.2 L’approccio di B-FREM
L’algoritmo B-FREM è un metodo veloce per eseguire clustering di grandi dataset binari sparsi, per i quali cioè i punti-dato appartengono a spazi multi-dimensionali e hanno molte coordinate nulle. Il caso tipico è quello delle transazioni con “carrello della spesa” (basket data), cioè collezioni di pochi oggetti selezionati fra migliaia, che possono essere rappresentate come vettori binari, sparsi e ad elevata dimensionalità.
L’idea di base è di raggruppare transazioni simili, ottenendo cluster di transazioni che possono avere diverse interpretazioni:
– ogni cluster può indicare un certo tipo di transazione, attraverso il valor medio (la media delle transazioni per cluster);
– ogni cluster può indicare quali oggetti compaiono insieme nelle transazioni che rappresenta. Infatti, poiché i centroidi dei cluster sono medie di numeri binari, il valor medio di una certa dimensione può essere interpretato come la probabilità che quell’oggetto compaia nella transazione-tipo.
Questo permette di considerare l’algoritmo B-FREM come una tecnica alternativa di data mining per la scoperta di regole di associazione.
L’algoritmo si basa sul metodo EM per adattare una combinazione di distribuzioni normali a un dataset binario sparso. B-FREM non richiede strutture dati complesse per memorizzare pattern o parametri-modello, ma solo matrici che generalmente possono risiedere in memoria.
6.1.2.1 Notazioni e definizioni rilevanti
– Sia n la dimensione del dataset, cioè il numero di punti-dato; sia d la dimensionalità dei dati.
– La funzione densità normale multivariata per un vettore d-dimensionale x=
[
x1xd]
è data da:( )
2 ) ( ) ( 1 2 1 ) , , ( µ µ π µ − − Σ − − Σ = Σ x x d T e xP (densità normale multivariata),
dove µ è un vettore d-dimensionale detto vettore valor medio e Σ è la matrice di covarianza d×d. L’algoritmo usa matrici di covarianza diagonali.
– Gli input di EM sono:
o il numero di punti d-dimensionali, indicato con n ; o il numero desiderato di cluster, indicato con k.
– Gli n punti sono modellati secondo una combinazione di distribuzioni normali multivariate. La combinazione ha 3 parametri:
o i valori medi, o le covarianze, o i pesi.
Tali parametri sono immagazzinati nelle matrici descritte in Tabella 4. Nella letteratura statistica questi parametri vengono normalmente raggruppati in un unico insieme Θ, quindi si ha Θ=
{
C ,,RW}
. Per indicare una colonna di C o di R si usa il pedice j .Matrice Dimensioni Contenuto
C d×k valori medi
R d×k covarianze
W k×1 pesi
Tabella 4
La probabilità della combinazione è calcolata come
(
)
∑
(
)
= ⋅ = k j j j j P x C R W W R C x P 1 , , , , ,– EM utilizza la distanza di Mahalanobis: essa differisce dalla distanza Euclidea in quanto sfrutta la matrice di covarianza per scalare ogni dimensione; questo è particolarmente utile per dati asimmetrici e dimensioni aventi scale diverse. La distanza di Mahalanobis dell’ i -esimo punto x dal j -esimo cluster è i
(
)
(
) (
j i j)
T j i ij j j i C R x C R x C x , , =δ = − −1 − δ .6.1.2.2 Mappare le transazioni su dimensioni binarie
Nell’algoritmo B-FREM gli oggetti vengono mappati in dimensioni binarie e le transazioni sono quindi mappate in punti-dato binari.
– Sia D=
{
T1,T2,,Tn}
un insieme di n transazioni contenenti oggetti.– Sia I =
{
i1,i2,id}
l’insieme dei d oggetti disponibili per la scelta, dove{
d}
il ∈ 1 , , .
– Sia Ti =
{
i1,i2,,iK}
una transazione, vista come un insieme di K numeri interi (oggetti).– Sia D1,D2,,Dk un gruppo di k sottoinsiemi di D disgiunti due a due, che formano una partizione di D indotta dai cluster. Ciascun sottoinsieme D j
rappresenta un cluster.
– Per ogni oggetto si introduce una corrispondente dimensione b in uno spazio l d -dimensionale. La transazione T sarà mappata in un vettore binario i t , ciascun i
elemento del quale corrisponde ad una coordinata lungo una dimensione del nuovo spazio: = = altrimenti i i i l per t K l i 0 ,... , 1 ) ( 1 2 .
Ciascuna transazione diventa così un vettore binario sparso a d elementi, solo K dei quali diversi da zero. In questo modo si ottiene che D può essere considerato una grossa matrice d×n sparsa.
6.1.3 Miglioramenti ad EM
B-FREM propone diversi cambiamenti ad EM per poter trattare l’elevata dimensionalità dei dati, la dispersione, le covarianze nulle, dataset estesi e convergenza lenta. Questi miglioramenti comprendono:
– Inizializzazione appropriata per affrontare alta dimensionalità
Si basa sulle statistiche globali del dataset, cioè il valor medio globale e la covarianza globale. Esse sono calcolate con una singola passata sul dataset e sono rese
disponibili immediatamente. I centroidi vengono inizializzati in base al valor medio globale e alla deviazione standard dei dati.
– Uso delle sufficient statistics
Sono usate per mantenere informazioni di riepilogo dei cluster (Tabella 5). Questo riduce il tempo di I/O evitando passate ripetute sui dati e permettendo di fare stime periodiche dei parametri via via che le transazioni vengono lette.
– Tecniche di regolarizzazione della matrice di covarianza
Vengono usate per affrontare le covarianze nulle, situazione comune quando si trattano dati sparsi e specialmente basket data.
– Calcolo delle distanze sparse
Usato, insieme con addizioni di matrici sparse, per rendere più veloce il passo E dell’algoritmo EM.
L’esecuzione dell’algoritmo richiede due passate sui dati. Lo step E dell’algoritmo EM è eseguito per ogni transazione letta, mentre lo step M è eseguito un numero fissato di volte, accelerando in tal modo la convergenza verso la soluzione.
Matrice Dimensioni Contenuto
N k×1 D j M d×k
∑
= = j N i i j t M 1 Tabella 56.2 Descrizione
dell’algoritmo
6.2.1 Pseudo-codice dell’algoritmo
6.2.2 Spiegazione e significato dei parametri
– L’algoritmo richiede come input:
o D=
{
T1,T2,,Tn}
, un set di transazioni;o k, il numero desiderato di cluster; – L’algoritmo restituisce come output:
o Θ=
{
C ,,RW}
, che descrive il modello combinato; o L(Θ), valore che misura la qualità del modello; o una partizione di D in k sottoinsiemi.– La costante α è usata per inizializzare i cluster di partenza in base a d e k. Il valore assegnato alla costante nel codice di Figura 43 è sempre ragionevolmente corretto, ma si possono scegliere valori tra k e −1
(
10dk)
−1.– Il passo E determina l’appartenenza dei punti ai cluster, quindi viene eseguito per ciascuna transazione, cioè n volte.
– Il passo M costituisce la fase di apprendimento dell’algoritmo, durante la quale vengono aggiornate le sufficient statistics. L’esecuzione periodica del passo M, che avviene ogni Ln letture di transazioni (cioè L volte), accelera la convergenza. Se il passo M fosse eseguito per ogni transazione letta, potrebbe verificarsi una indesiderata sensibilità all’ordine delle transazioni nel dataset; peggio ancora, si potrebbe raggiungere una soluzione non ottima.
Se invece il passo M fosse eseguito dopo la lettura di tutte le transazioni, l’algoritmo sarebbe ridotto alla versione standard di EM; tuttavia non ci sarebbe sensibilità all’ordine delle transazioni e sarebbe garantito il raggiungimento della soluzione ottima.
Di conseguenza è necessaria una regolazione intermedia, ma più vicina al secondo scenario: cioè l’esecuzione del passo M il minor numero possibile di volte.
– Valori generalmente buoni per il parametro di frequenza L variano tra 10 e 100, ma per grandi database conviene attenersi alla regola seguente:
( )
≥ = altrimenti k dk n per dk L 2– Le sufficient statistics M ed N sono la versione multi-dimensionale delle sufficient statistics univariate quando i punti hanno valori binari. Vengono resettate alla fine del primo scan.
– L’obiettivo del primo scan è di ottenere accurati centroidi C per i cluster e accurate j
covarianze R . L’obiettivo del secondo scan è di regolare j Θ e ricalcolare L(Θ). – Il Quality Coefficient L(Θ) è derivato dal coefficiente noto come average log-likelyhood,
adattato al caso specifico per punti a coordinate binarie. Il valore del Quality coefficient, sempre negativo, tende a zero all’aumentare del numero di passi di apprendimento eseguiti. La soglia che indica una buona segmentazione ottenuta è individuata nel valore −50.
6.3 Realizzazione
dell’algoritmo
6.3.1 Scheda del software
Il programma è scritto in linguaggio C++. Si appoggia alla libreria matematica di libero utilizzo e distribuzione “Newmat 10” (http://www.robertnz.net).
È stato compilato utilizzando l’ambiente Microsoft Visual C++ 6.0.
Il file eseguibile gira in modalità W32 console (finestra DOS) e richiede parametri attraverso la linea di comando.
Il test del programma è stato eseguito in ambiente Microsoft Windows 98, su un PC dotato di processore Athlon 1700+ e 512 MB di memoria DDR.
6.3.2 File disponibili – Sorgenti: o algoritmo.h o algoritmo.cpp o datafile.h o datafile.cpp o ooe_partition.h o ooe_partition.cpp o ooecluster.h o ooecluster.cpp o my_utils.h – Libreria Newmat 10 o sorgenti: newmat10\*.*
– Programma eseguibile: bfrem10.exe – Utility di lancio: bfrem.bat
6.3.3 Input
Il programma richiede sei parametri:
1. il nome del file di configurazione (testo)
2. il nome del file contenente il dataset (binario o testo)
3. il nome del file destinato a contenere la tabella punti-cluster (testo) 4. il nome del file destinato a contenere i dati dei cluster (binario) 5. il nome del file destinato a contenere i centroidi dei cluster (testo)
6. il nome del file destinato a contenere i dati di riepilogo della segmentazione (testo)
Esempi di linee di comando valide:
– bfrem config.txt dati.bin tabella.txt cluster.bin cluster.txt summary.txt
– orclus32.exe config.txt dati.txt tabella.txt cluster.bin cluster.txt summary.txt 6.3.4 Output
I file prodotti sono:
1. Un file testo contenente la tabella punti-cluster
La tabella ha due campi: il primo è il numero d’ordine del punto nel dataset; il secondo è il numero d’ordine del cluster cui il punto è stato assegnato. I record della tabella occupano linee consecutive e i campi sono separati da una tabulazione. I dati prodotti risultano così un database in formato testo, pronto per essere importato (ad esempio in Microsoft Excel) per l’analisi.
2. Un file binario contenente i dati dei cluster
Il file è destinato ad essere utilizzato da futuri moduli aggiuntivi per l’esecuzione di eventuali analisi dei cluster prodotti (calcolo del diametro, analisi del modello, ecc.). 3. Un file testo contenente la tabella dei centroidi dei cluster
I centroidi sono calcolati come media aritmetica dei punti appartenenti ai cluster. La tabella, priva di intestazione, ha un numero di campi dipendente ovviamente dalla dimensionalità dello spazio-origine: il primo campo è l’identificativo del centroide (“S_” seguito dal numero d’ordine del cluster relativo); i campi successivi sono le coordinate, valori double precision a 10 cifre complessive. I record della tabella occupano linee consecutive e i campi sono separati da una tabulazione. I dati prodotti
risultano così un database in formato testo, disponibile per eventuali programmi classificatori che utilizzino i soli centroidi.
4. Un file testo contenente i dati di riepilogo del partizionamento, cioè la tabella cluster-cardinalità e il Quality Coefficient.
La tabella ha due campi: il primo è il numero d’ordine del cluster; il secondo è il numero di punti del dataset che sono stati assegnati al cluster. I record della tabella occupano linee consecutive e i campi sono separati da una tabulazione. I dati prodotti risultano così un database in formato testo, pronto per essere importato (ad esempio in Microsoft Excel) per l’analisi. Il Quality Coefficient viene calcolato sempre.
5. Il file di testo “stato.txt”
Contiene i parametri di configurazione dell’esecuzione corrente.
6.3.5 Il file di configurazione
Per impostare i valori desiderati si può editare il prototipo del file di configurazione fornito insieme al programma. Si raccomanda di mantenere la struttura del contenuto del file, limitando le modifiche ai soli valori dei parametri.
Esempio di file di configurazione:
Dimensionalità dello spazio binario: 427
Numero desiderato di cluster: 7
Fattore di inizializzazione: 0.0
Frequenza di esecuzione del “passo M”: 10
Tipo del file dataset: testo
Numero di punti del dataset: 42956
Tipo dei punti del dataset: integer
Dimensione in byte delle coordinate dei punti del dataset: 4
6.3.6 Significato dei parametri di configurazione e fine tuning
1. Dimensionalità dello spazio binario ( D ) Intero positivo.
2. Numero desiderato di cluster ( K ) Intero positivo.
3. Fattore di inizializzazione (α )
Reale nell’intervallo
[ [
0 . Si tratta di un coefficiente per l’inizializzazione casuale ,1 corretta dei cluster di partenza. Valore consigliato:( )
DK −1. Inserendo il valore “0.0” il programma si incaricherà del calcolo automaticamente.4. Frequenza di esecuzione del “passo M” Intero positivo. Valore consigliato: 50. 5. Tipo del file dataset
Testuale: “binario” o “testo”. 6. Numero di punti del dataset (N)
Intero lungo positivo. Teoricamente sono ammessi valori fino a 231 − . 1 7. Tipo dei punti del dataset:
Testuale: “double” o “integer”.
8. Dimensione in byte delle coordinate dei punti del dataset Intero positivo.
9. Tipo del dataset
Testuale: “transazioni” o “matrice”. L’algoritmo è pensato per lavorare con transazioni, che vengono automaticamente convertite in matrici. Il programma accetta anche direttamente un dataset a matrice.
6.4 Valutazione
dell’algoritmo
6.4.1 Dati artificiali
L’implementazione di B-FREM realizzata è stata provata sugli stessi dataset, prodotti con il software Basketgen, sui quali è stato valutato l’algoritmo ORCLUS. Lo svolgimento dei test non ha dato origine a problemi di comportamento dell’algoritmo, né ha fornito indicazioni notevoli sui parametri di configurazione. I valori ottenuti mediamente per il Quality Coefficient non sono mai stati inferiori alla soglia di −50, indicando che l’algoritmo si comporta bene in presenza di basket dataset.
6.4.2 Esperienza su dati reali
Le prove sono state effettuate applicando ripetutamente l’algoritmo con differenti combinazioni dei parametri di input. In particolare sono state eseguite prove con numero di cluster richiesti crescente e frequenza del passo M variabile, a partire da valori di 5 cluster. Le segmentazioni ottenute sono state sempre di qualità scadente:
– i coefficienti di qualità restituiti sono stati mediamente pari a -394, dunque notevolmente al di fuori della soglia di buona segmentazione;
– in tutti i casi un alto numero di record (fra 78% e 88%) è stato classificato appartenente a un unico grande cluster e alcuni cluster sono risultati vuoti o formati da un numero trascurabile di punti (addirittura fino a un solo punto).
Dati reali (filtrati, 42956, 61) confronto diretto -397.00 -396.50 -396.00 -395.50 -395.00 -394.50 99 50 10 step M frequency (L) QC clusters: 5 clusters: 7 clusters: 10 clusters: 15 Figura 44
Dati reali (filtrati, 42956, 61)
-396.22 -396.20 -396.18 -396.16 -396.14 -396.12 -396.10 -396.08 -396.06 -396.04 10 50 99 2989 10000 42956 step M frequency (L) QC clusters: 7 Figura 45
Dati reali (filtrati, 42956, 61)
-397.00 -396.00 -395.00 -394.00 -393.00 -392.00 -391.00 5 7 10 15 17 18 30 50 k QC L: 10 Figura 46
