3.4 Invocazione dinamica di servizi in relazione alla granularit` a
3.5.2 Adattivit` a proattiva
Viene effettuata anche un’analisi proattiva del contesto, allo scopo di met- tere in atto meccanismi correttivi prima che si verifichi l’anomalia vera e propria. Le previsioni sul comportamento dell’applicazione sono effettuate analizzando serie di dati storici e i servizi concreti da invocare saranno scelti in accordo. Ovviamente l’adattivit`a proattiva non `e basata su dati certi, ma su stime. Nel framework per modellizzare il comportamento dell’applicazione in maniera verosimile `e utilizzato un tool di machine learning.
Con machine learning si intende un ramo dell’intelligenza artificiale legata alla progettazione e allo sviluppo di algoritmi che permettano alle macchine di evolvere il loro comportamento (migliorando le proprie performance) sulla base di serie di dati storici.
Nel framework viene utilizzato un algoritmo di classificazione per effet- tuare l’analisi proattiva del contesto allo scopo di rilevare e gestire eventuali anomalie o cambiamenti.
Negli algoritmi di classificazione i dati in input consistono in record aven- ti attributi o caratteristiche multiple. Ogni record appartenente al dataset `e etichettato con una classe. L’obiettivo della classificazione `e quello di ana- lizzare i dati in input e sviluppare un modello per ogni classe, utilizzando le caratteristiche presenti nei dati. Gli algoritmi di classificazione portano all’identificazione di schemi che definiscono la classe a cui appartiene un da- to record. In genere, partendo dall’utilizzo di insiemi di dati esistenti e gi`a classificati, si cercano di definire alcune regolarit`a che caratterizzano le varie classi. Le descrizioni delle classi vengono usate per classificare nuovi record, di cui non si conosce la classe di appartenenza.
Sulla base di dati storici e utilizzando tecniche di classificazione, viene fornito un modello del sistema ed effettuata una previsione di eventuali ano- malie sulla base dei parametri contestuali attuali. A seconda di dati raccolti in esecuzioni precedenti dell’applicazione, viene creato un modello dell’ap- plicazione ed `e stimato l’effetto dell’esecuzione del programma con i dati monitorati a runtime. L’analisi `e effettuata in punti prestabiliti e signifi-
cativi per l’applicazione, detti checkpoint, utilizzando i dati disponibili al checkpoint e delle stime dei dati non ancora disponibili.
Il processo di analisi proattiva del contesto e di scelta del sottoprocesso da eseguire avviene attraverso le seguenti fasi:
1. Estrazione dati storici dall’apposito DB;
2. Scelta dell’algoritmo di classificazione;
3. Monitoraggio o stima dei parametri contestuali attuali;
4. Previsione di eventuali anomalie/cambiamenti;
5. Scelta del sottoprocesso da invocare.
Estrazione dati storici dal DB
A questo scopo viene configurato un dataset che descriva in forma strutturata i dati storici relativi ad esecuzioni precedenti dell’applicazione. In partico- lare sono determinati gli attributi rilevanti per lo specifico parametro su cui si vogliono effettuare previsioni e vengono salvati in correlazione ad un’eti- chetta che descriva le caratteristiche del parametro da stimare. Una prima sezione del dataset descrive la struttura del file: quali sono gli attributi da considerare, la classe da stimare e i valori che possono assumere. Nella se- zione successiva vengono salvate le specifiche istanze che descrivano i valori dei parametri rilevati in invocazioni precedenti dell’applicazione in relazione alla classe a cui apparteneva il parametro da stimare. Una parte del dataset `
e utilizzata come training set allo scopo di modellizzare il comportamento dell’applicazione, e la restante parte come test set per la valutazione delle performance della classificazione.
Scelta dell’algoritmo di classificazione
Nel framework vengono applicati in fase di design alcuni dei pi`u noti algo- ritmi di classificazione al dataset. L’output dell’esecuzione dell’algoritmo di
classificazione ad uno specifico dataset fornisce alcune misure sulla qualit`a della classificazione. Queste verranno confrontate ed analizzate allo scopo di individuare il migliore algoritmo per il dataset di riferimento.
Gli algoritmi di classificazione considerati all’interno del framework sono descritti in seguito:
Alberi decisionali: algoritmo J48
Gli alberi di decisione [13] costituiscono il modo pi`u semplice di classificare degli oggetti in un numero finito di classi. Essi vengono costruiti suddividen- do ripetutamente i records in sottoinsiemi omogenei rispetto alla variabile risposta. La suddivisione produce una gerarchia ad albero, dove i sottoinsie- mi (di records) vengono chiamati nodi e, quelli finali, foglie. In particolare, i nodi sono etichettati con il nome degli attributi, gli archi (i rami dell’albero) sono etichettati con i possibili valori dell’attributo soprastante, mentre le fo- glie dell’albero sono etichettate con le differenti modalit`a dell’attributo classe che descrivono le classi di appartenenza. Un oggetto `e classificato seguendo un percorso lungo l’albero che porti dalla radice ad una foglia. I percorsi sono rappresentati dai rami dell’albero che forniscono una serie di regole.
La struttura di un albero di decisione pu`o diventare molto complicata, soprattutto nei casi derivati da database contenenti centinaia di attributi ed una variabile risposta con differenti classi. In situazioni del genere, lasciar “crescere” l’albero senza stabilire un limite di qualsiasi natura pu`o far si che l’albero ottenuto diventi non interpretabile e crei un numero elevato di regole, sovraadattando i dati. Esistono, quindi, dei criteri di controllo che limitano la crescita degli alberi, basati o sul massimo numero di regole otteni- bili dalla classificazione o sulla massima profondit`a raggiungibile dall’albero o ancora sul numero minimo di records che devono essere presenti in ogni nodo per poter effettuare la divisione (splitting) in quel nodo. In tale ambito rientra anche la fase di pruning dell’albero che consiste nell’ottenere da un albero il pi`u piccolo sottoalbero, che non comprometta l’accuratezza della classificazione/previsione resa possibile dall’albero madre.
Gli alberi decisionali offrono numerosi vantaggi :
• sono facili da capire;
• sono veloci;
• possono essere trasformati in regole;
• hanno dimostrato di ottenere buoni risultati, se messi a confronto con altre tecniche di gestione della conoscenza.
Per quanto riguarda i punti deboli nell’utilizzo degli alberi di decisione la critica sostiene che l’attributo divisore viene scelto quasi sempre da un algoritmo “greedy”, che non tiene assolutamente conto dell’influenza che la scelta di un attributo divisore potrebbe avere sui futuri divisori. In altre parole, la decisione dell’attributo (o campo) divisore avviene ad ogni nodo dell’albero, in un preciso momento durante l’esecuzione dell’algoritmo, e non `
e mai pi`u riconsiderata in seguito. Conseguenza di ci`o `e che tutti i campi di- visori vengono scelti sequenzialmente e ogni campo divisore `e dipendente dai predecedenti. Ci`o implica che tutti i futuri campi divisori sono dipendenti dal nodo radice dell’albero, a tal punto che una modifica del campo divisore del nodo radice potrebbe portare alla costruzione di un albero completamente differente. Questa critica, di per s`e, potrebbe portare ad una forte limitazio- ne nell’uso di tali strumenti, tuttavia la bont`a dei risultati spesso ottenuti utilizzando questa tecnica fanno parzialmente dimenticare la correttezza di tale critica.
Reti Bayesiane: approccio Naive Bayes
Una rete bayesiana `e un grafo aciclico orientato (DAG) in cui:
• i nodi rappresentano le variabili;
• gli archi rappresentano le relazioni di dipendenza statistica tra le va- riabile e le distribuzioni locali di probabilit`a dei nodi foglia rispetto ai valori dei nodi padre.
Si basano sulla regola di Bayes ed esprimono relazioni di dipendenza con- dizionale (archi) tra le variabili in gioco (nodi). Ad ogni nodo `e associata una tabella di probabilit`a condizionata che quantifica gli effetti che i genitori hanno sul nodo, dove per genitori si intendono tutti quei nodi che hanno archi che puntano al nodo.
Una rete bayesiana rappresenta la distribuzione della probabilit`a congiun- ta di un insieme di variabili. Supponiamo di voler classificare un insieme di elementi che sono descritti da un vettore di feature A1,A2,..,An ovvero dei
valori numerici/letterali ricavati da determinate caratteristiche di ognuno di tali elementi, avendo a disposizione un training set con elementi gi`a catego- rizzati. La probabilit`a che un certo elemento con determinati valori delle sue feature A1 = a1 ; A2 = a2;.. An= an appartenga alla classe c `e data da:
P r(C = c|A1 = a1, A2 = a2, .., An = an)
Ora il teorema di Bayes (detto anche regola di Bayes) afferma che l’espres- sione qui sopra equivale a:
P r(A1 = a1, A2 = a2, .., An = an|C = c)
P r(A1 = a1, A2 = a2, .., An = an)
.P r(C = c)
P r(C = c) pu`o essere facilmente calcolato: `e la probabilit`a che un generi- co elemento di cui non si sa nulla appartenga a c, ricavata dalla percentuale di elementi del training set che appartiene a quella classe.
La probabilit`a al denominatore P r(A1 = a1, A2 = a2, .., An = an) `e ir-
rilevante per la classificazione perch`e `e la stessa per tutte le classi in cui si prova a inserire l’elemento. Quindi si tratta di calcolare P r(A1 = a1, A2 =
a2, .., An= an|C = c).
Ipotesi Naive di Bayes:Ogni feature `e indipendente da ogni altra feature
P r(A1 = a1, .., An= an|C = c) = P r(A1 = a1|C = c). · · · .P r(An= an|C = c)
Le probabilit`a moltiplicate tra loro alla destra dell’equazione, possono essere calcolate a partire dal training set, calcolando la percentuale di istanze
in cui una certa classe ha quel determinato valore di features rispetto al numero totale di istanze appartenenti a quella classe.
I vantaggi dell’utilizzo di una rete Naive Bayes sono:
• la classificazione `e veloce;
• considera i valori assunti da molti attributi;
• `e robusta rispetto alle alternative irrilevanti;
• i classificatori ottenuti sono facili da interpretare.
Gli svantaggi sono i seguenti:
• il dataset deve essere sufficientemente grande;
• gli attributi che descrivono le istanze devono essere condizionalmente indipendenti data la classificazione
NBTree
Rappresenta un approccio ibrido tra le reti Bayesiane di tipo Naive e gli alberi di decisione. E’ un albero di decisione che utilizza dei classificatori Naive Bayes sui nodi.
L’algoritmo per la costruzione di un NBTree `e il seguente: Input: un dataset, composto da istanze classificate
Output: un albero di decisione con classificatori Naive Bayes sulle foglie
1. Per ogni attributo Xi se Xi `e reale applica una soglia a Xi, poi valuta
l’utilit`a u(Xi) di uno split su Xi.
2. Sia j = argmaxi(ui) l’attributo con l’utilit`a maggiore.
3. Se uj non `e significativamente migliore dell’utilit`a del nodo corren-
te crea un classificatore Naive Bayes semplice per il nodo corrente e ritorna.
4. Altrimenti partiziona T a seconda dell’esito del test su Xj , se Xj `e
continuo applica una soglia a Xj . Effettua uno split su Xj per tutti i
possibili valori.
5. Per ogni figlio richiama l’algoritmo ricorsivamente sulla porzione di T che corrisponde al test che porta a quel figlio.
I vantaggi dell’utilizzo di questo tipo di tecnica di apprendimento sono:
• le variabili considerate non devono essere necessariamente indipendenti;
• i database possono essere grandi;
• considera i valori assunti da molti attributi.
In breve, gli NBTree sembrano aumentare le performance degli alberi decisionali e dei classificatori bayesiani utilizzati singolarmente.
Ogni algoritmo di classificazione `e applicato al dataset utilizzando come tecnica di suddivisione tra training set e test set la cross-validation. Essa `e una tecnica statistica utilizzabile in presenza di una buona numerosit`a del training set. In particolare la k-fold cross-validation consiste nella suddivisio- ne del dataset totale in k parti (si chiama anche k-fold validation) e, ad ogni passo, la parte (1/k)-esima del dataset viene ad essere il validation dataset, mentre la restante parte costituisce il training dataset. Cos`ı, per ognuna delle k parti (di solito k = 10) si allena il modello, evitando quindi problemi di overfitting, ma anche di campionamento asimmetrico (e quindi affetto da bias) del training dataset, tipico della suddivisione del dataset in due sole parti (ovvero training e validation dataset).
Valutazione dei risultati
In questa sezione sono descritte le principali metriche utilizzate in questo ambito per la valutazione delle performance e la conseguente scelta dell’algo- ritmo di classificazione con prestazioni migliori in relazione ad uno specifico dataset.
• Percentuale di istanze classificate correttamente
E’ la misura pi`u semplice per la valutazione delle performance del- la classificazione. E’calcolata come la semplice percentuale di istanze classificate correttamente, rispetto all’intero test set.
• Matrice di confusione
La matrice di confusione per un modello con classe binaria (matrice 2x2) `e:
--- Confusion Matrix --- a b <-- classified as VP FN | a = yes
FP VN | b = no
Gli elementi della matrice sono di seguito definiti:
– Veri Positivi: numero di record positivi correttamente classificati come positivi;
– Falsi Negativi: numero di record positivi erroneamente classificati come negativi;
– Veri Negativi: numero di record negativi correttamente classificati come negativi;
– Falsi Positivi: numero di record negativi erroneamente classificati come positivi.
• Curva ROC
Altra importante misura di prestazione `e la curva ROC, che costituisce un metodo grafico di valutazione dei risultati. La curva ha:
– per ascisse il FPr (False Positive rate), ossia la frazione di casi negativi erroneamente classificati come positivi (Falsi Positivi) ri- spetto al numero totale di casi negativi presenti nel dataset (Falsi Positivi+Veri Negativi);
– per ordinate il TPr (True Positive rate), ossia la frazione di casi positivi correttamente classificati come positivi (Veri Positivi) ri- spetto al numero totale di casi positivi presenti nel dataset (Veri Positivi+Falsi Negativi).
Quanto pi`u la curva ROC si avvicina all’angolo in alto a sinistra del sistema di riferimento (ossia per alto TPr e basso FPr), migliore `e la prestazione del corrispondente modello. Altra interessante misura di prestazione `e l’AUC (Area Under Curve), ossia la superficie sottesa dalla curva ROC.
• Precision e Recall
Precisione e Recall sono due classificazioni statistiche molto usate. La precisione pu`o essere vista come una misura di correttezza o fedelt`a, mentre la recall `e una misura di completezza. In un processo di clas- sificazione, i termini vero positivo, vero negativo, falso positivo e fal- so negativo sono usati per confrontare la classificazione di un oggetto (l’etichetta di classe assegnata all’oggetto da un classificatore) con la corretta classificazione desiderata (la classe a cui in realt`a appartiene l’oggetto). Precisione e recall sono definite come:
Precisione: V eriP ositivi+F alsiP ositiviV eriP ositivi , Recall: V eriP ositivi+F asiN egativiV eriP ositivi
Previsione di eventuali anomalie/cambiamenti
Sulla base dell’applicazione al dataset dell’algoritmo di classificazione scelto nella fase precedente viene modellizzato il comportamento dell’applicazione in relazione ai parametri contestuali considerati. Vengono poi monitorati o stimati a runtime i dati contestuali attuali ed effettuata una previsione sul comportamento del sistema rilevando eventuali anomalie o cambiamenti e uti- lizzando il modello ottenuto dall’applicazione dell’algoritmo di classificazione scelto.
Scelta del sottoprocesso da eseguire
A seconda di ci`o che `e stato predetto nella fase precedente viene invocato dinamicamente il sottoprocesso pi`u idoneo.
Riassumendo, i dati storici estratti dal database vengono utilizzati co- me dataset, una parte come training set, per modellizzare il comportamento della rete ed una parte come test set, per verificare la bont`a del modello creato. La scelta dell’algoritmo di classificazione viene effettuata sulla base del confronto tra le misure di qualit`a del modello ottenute utilizzando di- versi meccanismi di classificazione. Dopo aver scelto l’algoritmo pi`u idoneo vengono monitorati o stimati i parametri contestuali attuali, effettuata una previsione sul comportamento dell’applicazione in questa situazione e scelto in accordo il sottoprocesso da svolgere.