Correlation rules: analisi di una tecnica di data mining e sua applicazione ai sistemi di telecomunicazione

  
9 
Una correlazione positiva vuol dire che latte e zucchero vengono spesso 
venduti assieme, pi� di quanto ci si aspetterebbe se la vendita di uno dei due 
prodotti fosse indipendente da quella dell�altro. 
Usando il concetto di correlazione si pu� evitare la generazione di regole 
ingannevoli: se la presenza dello zucchero nei carrelli della spesa non venisse 
influenzata dalla presenza del latte e viceversa, allora latte e zucchero avrebbero 
una correlazione nulla, e non verrebbe quindi mai proposta all�utente una regola 
composta da questi due prodotti. 
Per un�efficace applicazione di questa tecnica viene messa in evidenza 
l�importanza di utilizzare un�adeguata misura della correlazione presente tra gli 
elementi della regola; queste misure vengono dette di interesse, perch� pi� alto � il 
loro valore, maggiore � l�interesse dell�utente per quella regola. 
Tali misure servono per fare una classifica dei pattern estratti e per permettere 
di mostrare all�utente solo quelli pi� interessanti. 
In questa tesi verranno presentate ed analizzate le misure di interesse pi� note 
in letteratura; il loro confronto, nella prima parte di questo lavoro, avverr� per 
semplicit� applicandole a pattern composti da due soli elementi. Verr� prima fatta 
una analisi teorica del loro comportamento in alcuni casi limite e successivamente 
verranno invece utilizzati dei dataset sintetici per permettere di valutarne il 
comportamento in situazioni pi� realistiche. 
Una volta messi in luce vantaggi e svantaggi di ciascuna di queste misure, ne 
verr� sviluppata una di nuova, con l�obiettivo di superare i limiti di quelle 
analizzate. 
Lo studio procede poi generalizzando queste misure per renderle applicabili a 
pattern di dimensione arbitraria, ed introducendo successivamente il concetto di 
confrontabilità fra pattern di dimensione diversa. Non deve infatti venir dato per 
scontato il poter confrontare ad esempio l�interesse di una regola composta da due 
elementi con quello di una regola da tre per stabilire quale delle due � la pi� 
interessante: il risultato potrebbe essere ingannevole. Per rendere le misure 
consistenti con questo concetto, vengono in questo lavoro proposte e valutate 
alcune nuove normalizzazioni da applicare alle misure tradizionali. 
Nella parte conclusiva dello studio si discute un�applicazione concreta del 
framework appena sviluppato per contribuire alla risoluzione di un problema 
molto sentito dai gestori delle reti di telecomunicazioni: il fenomeno dell�alarm 
storm. 
L�azienda in cui la tesi � stata svolta, la Tektronix, sta sviluppando un sistema 
di diagnostica per la parte terrestre della rete cellulare GSM. 
  
10 
Quando sorge qualche anomalia, il sistema di rilevazione genera degli allarmi, 
che l�operatore che tiene sotto controllo la rete deve esaminare e cercare di 
interpretare per poter prendere i provvedimenti ritenuti eventualmente necessari. 
Purtroppo, gli allarmi segnalati da queste reti, a causa della loro eccessiva 
quantit�, sono spesso di scarso aiuto nella diagnosi dei problemi di network che ne 
sono la causa, e l�operatore finisce spesso per ignorarli, tralasciando 
l�informazione in essi contenuta perch� la loro analisi richiederebbe troppo tempo. 
Per attenuare questo problema si vogliono allora estrarre delle correlation 
rules dai log degli allarmi dei giorni o dei mesi precedenti, per scoprire quali 
allarmi occorrono spesso contemporaneamente; in seguito, questa conoscenza 
potr� essere applicata in tempo reale agli allarmi che via via giungono alla 
consolle di amministrazione per raggrupparli: allarmi che occorrono spesso 
contemporaneamente rappresentano in genere i diversi sintomi di uno stesso 
problema. 
Questa tecnica non permette di risalire direttamente alla causa del problema, 
ma � comunque un importante aiuto per l�operatore, che potrebbe cos� vedere 
sullo schermo della sua consolle di amministrazione non pi� un lungo elenco di 
allarmi, ma una nuova sequenza, pi� breve e facilmente interpretabile, di allarmi 
gi� raggruppati secondo il problema comune che li ha generati. 
  
11 
2 Cos’è il Data Mining 
2.1 Introduzione 
Nelle ultime decadi alcuni fattori hanno permesso di aumentare notevolmente 
la nostra capacit� sia di produrre che di archiviare dati; i fattori che hanno 
maggiormente contribuito a questo fenomeno includono l�informatizzazione di 
molte attivit� aziendali, l�ampio utilizzo di codici a barre nella maggioranza dei 
prodotti commerciali, la possibilit� di archiviare in maniera economica grosse 
moli di dati. In aggiunta, l�utilizzo diffuso del World Wide Web come un sistema 
informativo globale ci ha sommersi di una enorme quantit� di informazioni. 
Questa crescita esplosiva di dati memorizzati ha generato un urgente bisogno di 
nuove tecniche e di strumenti automatici di analisi per evitare che questi database, 
proprio a causa della loro mole e dell�impossibilit� di esaminarli con strumenti 
convenzionali, si trasformino in �cimiteri dei dati�, dove questi vengono �sepolti� 
senza poi poterne ricavare alcuna informazione utilizzabile. 
Il Data Mining, una nuova e promettente disciplina nell�ambito dell�analisi dei 
dati, si pone come obiettivo proprio l�estrazione di conoscenza utile 
implicitamente contenuta in database, data-warehouse ed altri grossi depositi di 
dati. 
L�applicazione delle tecniche di Data Mining � solo una delle fasi richieste nel 
processo di �estrazione� della conoscenza; tipicamente, l�intero processo � 
composto dalle seguenti fasi: 
  
12 
Pulizia
Integrazione
Selezione
Trasformazione
Data Mining
Val utazi one
Presentazione
Pulizia dei dati, per rimuovere il rumore
di  fondo o i  dati  i rri l evanti
Integrazione dei dati, in cui sorgenti
di dati multiple vengono unite
Selezione dei dati, per mantenere solo quelli
rilevanti ai fini dell'analisi da effettuare
Trasformazione dei  dati , dove i  dati  vengono
consolidati o normalizzati per predisporli
all'analisi con tools di Data Mining
Data Mining vero e proprio
Valutazione dei pattern estratti, per identificare
i pattern veramente interessanti che rappresentano
conoscenza, basandosi su qualche misura di interesse
Presentazione della conoscenza estratta in forme
facilmente comprensibili ed interpretabili dall'utente,
(eventualmente impiegando tools grafici di visualizzazione)
 
Figura 1: Il processo di Knowledge Discovery 
 
� importante evidenziare come, secondo questo punto di vista, il Data Mining 
� solo una fase di tutto il processo di knowledge discovery (anche se spesso i 
termini Data Mining e KDD, Knowledge Discovery in Databases, vengono 
confusi), bench� sia una fase essenziale, quella in cui viene fatta �venire a galla� 
l�informazione nascosta nei dati. 
I prossimi paragrafi verranno dedicati ad una introduzione alle principali 
tecniche di Data Mining e ai principali tipi di pattern che da queste tecniche 
possono essere estratti. 
  
13 
2.2 Classificazione 
Dato un insieme di oggetti, ciascuno dei quali � composto da un certo numero 
di attributi di cui uno viene detto classe, la classificazione � il processo di ricerca 
di un insieme di modelli che, esaminando il valore degli attributi di ciascun 
oggetto, ne stabiliscono la classe. Tali modelli vengono creati basandosi 
sull�analisi di un training-set, cio� di un insieme di oggetti la cui classe � gi� nota, 
e vengono poi applicati su insiemi di oggetti la cui classe � invece sconosciuta. 
Il modello derivato pu� essere rappresentato in varie forme, come regole di 
classificazione (se... allora...), alberi di decisione, formule matematiche o reti 
neurali. 
Un albero di decisione � una struttura ad albero simile ad un flow-chart, dove 
ciascun nodo denota un test sul valore di un attributo, ciascuna biforcazione 
rappresenta un possibile esito del test, e le foglie dell�albero rappresentano le 
classi; gli alberi di decisione possono essere facilmente convertiti in regole di 
classificazione. 
Una rete neurale, quando viene utilizzata per scopi di classificazione, � 
tipicamente una collezione di unit� di elaborazione analoghe ai neuroni, con 
connessioni pesate tra le unit�. 
Le possibili applicazioni delle tecniche di classificazione sono molto ampie: 
ad esempio, la riduzione del costo di operazioni di mailing selezionando le 
persone pi� probabilmente interessate all�acquisto del prodotto da pubblicizzare 
tramite l�utilizzo di un modello creato a partire dall�analisi dei clienti che hanno 
acquistato precedentemente un prodotto analogo. 
Un�altro tipico esempio � la rilevazione delle frodi nell�utilizzo delle carte di 
credito, esaminando le passate transazioni (ora, luogo, importo, bene acquistato...) 
di cui si conosce gi� l�esito per cercare di capire le tipologie di transazioni a 
rischio. 
 
  
14 
Esempio: 
 
Oggetti in cui la classe � gi� nota (Training-set), utilizzati per creare un 
modello: 
 
Età Stato civile Reddito Acquirente 
(CLASSE)
18-30 Singolo 125.000 Euro No
30-50 Sposato 100.000 Euro No
18-30 Singolo 70.000 Euro No
18-30 Sposato 120.000 Euro No
30-50 Divorziato 95.000 Euro Sì
30-50 Sposato 60.000 Euro No
> 50 Divorziato 220.000 Euro Sì
18-30 Singolo 85.000 Euro No
30-50 Sposato 75.000 Euro No
> 50 Singolo 90.000 Euro Sì
 
Oggetti la cui classe non � nota, su cui applicare il modello creato: 
 
Età Stato civile Reddito Acquirente 
(CLASSE)
18-30 Singolo 75.000 Euro ?
30-50 Sposato 50.000 Euro ?
> 50 Sposato 150.000 Euro ?
30-50 Divorziato 90.000 Euro ?
18-30 Singolo 40.000 Euro ?
> 50 Sposato 80.000 Euro ?
 
  
15 
2.3 Clustering 
Diversamente dalla classificazione e dalla predizione, il cui obiettivo � 
principalmente decidere a quale classe appartiene un oggetto, le tecniche di 
clustering si pongono come obiettivo principale lo stabilire quali siano le classi 
(che vengono qui chiamate cluster) in cui suddividere gli oggetti. 
Gli oggetti del training-set sono raggruppati seguendo il principio di 
massimizzare le similarità intra-classe e di minimizzare le similarità inter-classe; 
i cluster di oggetti sono cio� formati in modo tale che due oggetti entro uno stesso 
cluster presentino un elevato livello di somiglianza rispetto a due oggetti 
appartenenti a due cluster differenti. 
In genere per raggiungere questo obiettivo � necessario sviluppare una misura 
di similarità, che pu� essere la distanza euclidea se gli attributi sono continui, 
altrimenti una qualche altra misura �ad hoc� specifica per il problema che si sta 
affrontando. 
 
Figura 2: Insieme di oggetti  prima e dopo l’operazione di Clustering 
Ambiti di applicazione di queste tecniche possono essere la segmentazione di 
un mercato in diverse tipologie di clientela, per poter applicare a ciascuna 
tipologia un�opportuna campagna di marketing. 
  
16 
2.4 Analisi degli outlier 
Un database pu� contenere oggetti che non corrispondono al comportamento 
generale o al modello dei dati: questi oggetti sono detti outlier. La maggioranza 
dei metodi di Data Mining scartano gli outlier considerandoli eccezioni o rumore, 
ma in alcune applicazioni (ad esempio l�identificazione delle frodi) gli eventi rari 
possono essere pi� interessanti di quelli che occorrono con maggior regolarit�. 
L�analisi degli outlier � generalmente indicata come outlier mining. 
Nell�immagine precedente, ad esempio, i quattro punti che non sono racchiusi 
nei cluster possono essere considerati degli outlier. 
Gli outlier possono essere individuati utilizzando test statistici che assumono 
una certa distribuzione o un certo modello di probabilit� per i dati, o che 
utilizzano misure di distanza dove gli oggetti che hanno pochi altri elementi nella 
prossimit� vengono considerati outlier. 
I metodi basati sulla devianza, invece di utilizzare misure statistiche o di 
distanza, identificano gli outlier esaminando le differenze nelle caratteristiche 
principali degli oggetti in un gruppo, prendendo normalmente come riferimento i 
valori degli oggetti esaminati precedentemente. 
2.5 Analisi delle associazioni 
L�analisi delle associazioni ha come obiettivo la scoperta di regole associative 
(o association rules), regole cio� che evidenziano condizioni sui valori degli 
attributi che occorrono frequentemente in un certo insieme di dati. 
Un�association rule � una regola che esprime il concetto �se si verifica la 
condizione X allora � probabile che si verifichi anche la condizione Y�, dove X e 
Y rappresentano i valori assunti da insiemi di attributi. 
 
  
17 
Esempio: 
 
Esaminando i seguenti carrelli della spesa di un supermercato: 
 
Num. Carrello Oggetti contenuti 
1 Pane, Coca-Cola, latte 
2 Birra, pane 
3 Birra, Coca-Cola, pannolini, latte 
4 Birra, pane, pannolini, latte 
5 Coca-Cola, pannolini, latte 
 
Si scoprono le seguenti regole: 
 
• {latte} ⇒ {Coca-Cola} 
• { latte , pannolini} ⇒ {birra} 
 
Cio�, analizzando questi carrelli della spesa si nota come chi acquista latte 
acquista spesso anche Coca-Cola, e chi acquista latte e pannolini acquista spesso 
anche birra. 
Non approfondiamo ulteriormente l�argomento in questa sezione, poich� alle 
association rules verr� interamente dedicato uno dei prossimi capitoli. 
2.6 Sequential patterns 
Questa tecnica di Data Mining � utilizzabile quando gli oggetti appartenenti 
all�insieme da esaminare sono disposti in ordine cronologico (li chiameremo 
eventi), e ci si pone l�obiettivo di analizzare se esistono eventi che, quando 
accadono in una certa sequenza, ed entro determinati lassi di tempo, causano il 
probabile accadere di qualche altro evento. 
Frequenti utilizzi di queste tecniche si hanno nell�ambito dell�analisi degli 
acquisti (alla ricerca di sequenze di acquisti frequenti) e nell�ambito dell�analisi 
dei log dei Web-Server (per comprendere quali siano i �percorsi� tipici che 
l�utente segue per raggiungere determinate pagine).