Come visto nel capitolo di introduzione ai sistemi di CBR, la strategia classica di retrieval è costituita dal KNN, che prevede il confronto, cioè il calcolo della similarità, tra il caso query in input e tutti i casi presenti nella base di conoscenza. Questa soluzione può non essere molto efficiente quando il numero di casi da confrontare è molto elevato; in tali situazioni è possibile utilizzare una strategia di Pivoting.
Un meccanismo di questo tipo prevede sostanzialmente le seguenti azioni:
- Si estrae, secondo un opportuno criterio, un caso rappresentativo, o caso medio, dalla base di casi
- Si calcola la distanza tra il caso medio e tutti gli altri casi
- Si calcola la distanza tra il caso medio e il nuovo caso in input
- Si effettua una stima della distanza tra il caso in input e tutti gli altri casi
utilizzando il concetto di disuguaglianza triangolare, e si trovano in questo modo un limite inferiore (lower bound) e un limite superiore (upper bound) per il valore effettivo della distanza
A questo punto gli intervalli che hanno il lower bound più alto del minimo degli upper bound vengono tagliati (pruned), cioè esclusi a priori dalla ricerca e viene poi eseguito il seguente processo iterativo:
- Inizializzazione: BESTp = ∞ e SOL = {}
- Si sceglie il caso Pivot, prendendo quello che ha il valore più basso come
punto di mezzo dell’intervallo di valore di distanza calcolato precedentemente; si calcola la distanza effettiva tra il caso Pivot e il caso in input (DIST) e si pone BEST = DIST; - Se BESTp > BEST si pone SOL = PIVOT e BESTp = BEST
- Se BESTp = BEST si pone SOL = {PIVOT, SOL}
- Si “tagliano” tutti gli intervalli per i quali il lower bound è maggiore del
valore BEST e si toglie il Pivot dalla base di casi. - Si ritorna al punto 2
La scelta del caso rappresentativo più adatto, nella fase di inizializzazione, è un’azione cruciale per la velocità dell’algoritmo, perché scelto opportunamente indirizza subito l’algoritmo stesso verso i casi che hanno una maggiore probabilità di essere recuperati.
Implementazione in jCOLIBRI
In questo paragrafo e in quelli successivi si illustra come è stata implementata la strategia di Pivoting Retrieval all’interno del framework jCOLIBRI.
Lo sviluppo di questa soluzione alternativa per il retrieval dei casi è stato fatto seguendo la filosofia con cui il framework è stato costruito e cercando di utilizzare al massimo i componenti già presenti al suo interno. Inoltre si era interessati anche al comportamento di tale algoritmo di retrieval, e alla sua efficacia, per questo si sono aggiunte delle funzionalità di “diagnostica” dell’algoritmo e di raccolta dei suoi dati di esecuzione. Tale aspetto verrà analizzato in seguito nell’apposito paragrafo.
Scelta del caso rappresentativo o “caso medio”
La prima operazione da eseguire per implementare la strategia, come visto, è l’estrazione dalla base di casi di un caso medio tra quelli presenti e da utilizzare per il calcolo delle distanze di riferimento da tutti gli altri casi.
jCOLIBRI prevedeva già una funzionalità di questo genere che veniva usata in un’altra metodologia di retrieval chiamata Expert Clerk Retrieval, quindi ci si è limitati nell’integrare tale metodo di calcolo del caso medio all’interno della soluzione che si voleva realizzare. Il criterio con cui viene scelto il caso medio, detto anche a volte “caso mediano” è piuttosto semplice: per gli attributi numerici viene fatta la media tra i valori dell’attributo in tutti i casi della base, mentre per attributi nominali viene impostato il valore dell’attributo al valore di quello che risulta presente nel maggior numero di casi all’interno della base.
Calcolo della distanza tra il caso mediano e gli altri casi
Dopo aver calcolato il caso mediano occorre andare a calcolare la distanza esatta tra esso e tutti i casi memorizzati nella case base. Per fare si è definito un metodo distanceFromCasesToMedian che prende come parametri la collection di casi, il caso mediano e l’oggetto NNConfig che contiene le definizioni delle funzioni di similarità locali e globali e restituisce un Arraylist di coppie
A livello di codice, questa operazione viene fatta con un ciclo in cui si scorrono tutti i casi e per ognuno si invoca il metodo compute dell’oggetto che definisce la funzione di similarità globale e poi si aggiunge tale valore, insieme al caso, sotto forma di RetreivalResult all’arraylist che verrà ritornato dal metodo che si sta descrivendo.
Ecco la breve routine che ci permette di ottenere una struttura contenente per ogni caso il valore della sua distanza dal caso rappresentativo:
public static CollectiondistanceFromCasesToMedian (Collection cases, CBRQuery median, NNConfig simConfig){ List distToMedian = new ArrayList (); GlobalSimilarityFunction gsf = simConfig.getDescriptionSimFunction(); // Lista di coppie (Caso , distanzaDalMediano) for(CBRCase _case: cases) { distToMedian.add(new RetrievalResult(_case, 1 - gsf.compute(_case.getDescription(), median.getDescription(), _case, median, simConfig))); } return distToMedian; }
Questa operazione viene eseguita solo una volta al lancio dell’applicazione per caricare in memoria la struttura sopra descritta. Oltre a questo si è pensato al caso in cui siano già disponibili i valori di distanza tra il caso mediano e gli altri casi, ad esempio sotto forma di file di testo, e nel quale quindi non sia necessario andare a calcolare le funzioni di similarità ma basti semplicemente andare a leggere tali valori dal file e utilizzarlo per riempire la struttura contenente le coppie
Journey1,0.9330024813895782 Journey2,0.7965260545905708 Journey3,0.6228287841191067 ........ ........ Journey1022,0.47146401985111663 Journey1023,0.6228287841191067 Journey1024,0.46898263027295284
Come detto il formato previsto è costituito dall’id del caso, separato da virgola dal suo valore di distanza dal caso mediano.
Il metodo che permette di realizzare questo caricamento prende come parametri la collection di casi e una stringa che rappresenta il nome del file in cui sono salvati i valori delle distanze; quello che fa è leggere riga per riga, separare i 2 token della stringa e scorrere i casi fino a trovare quello con il giusto ID. A quel punto viene recuperato il caso con quel ID e viene creato l’oggetto RetrievalResult contente anche il valore di distanza rappresentato dal token successivo.
public static CollectionloadDistances (Collection cases, String filename)
Oltre al metodo per il caricamento, è stato previsto ovviamente un metodo per il salvataggio dei valori di distanza, sotto forma di scrittura su file, nel formato indicato precedentemente nella descrizione della funzione di caricamento. Il metodo prende come parametro una collezione di oggetti di tipo RetrievalResult, con quindi un CBRCase e un double che indica la distanza, e una stringa che indica il nome del file su cui andare a salvare i dati; a questo punto estrae l’ID dall’oggetto CBRCase e stampa su file, separati da virgola, l’ID e la distanza stessi.
public static void saveDistances(Collectioncases, String s){ try{ FileWriter fw = new FileWriter(s); PrintWriter file = new PrintWriter(fw); for (RetrievalResult _c : cases) file.println(_c.get_case().getID() + "," + _c.getEval()); file.close(); fw.close(); } catch (IOException e) { System.out.println("Errore nel salvataggio degli intervalli di distanza"); }
Distanza tra il caso input e i casi memorizzati
Una volta che si hanno a disposizione tutte le distanze tra il caso mediano e i casi della base occorre, come visto, andare a calcolare gli intervalli di stima della distanza tra il caso in input e i casi in memoria, sfruttando il concetto di disuguaglianza triangolare.
Il teorema della disuguaglianza triangolare ci dice che la distanza esatta tra il caso in input e un caso della nostra base di casi sarà compreso nell’intervallo che ha come estremi:
- la differenza tra la distanza tra caso mediano e query e la distanza tra mediano e caso della base di casi che si sta considerando
- la somma tra la distanza tra caso mediano e query e la distanza tra mediano e caso della base di casi che si sta considerando
Ovvero, per un ipotetico caso della nostra base di casi Xi, la sua distanza dal caso query sarà compresa nell’intervallo:
|d(Q,M)-d(M,Xi)| <= d(Q,Xi) <= |d(Q,M)+d(M,Xi)|
Nel paragrafo successivo viene illustrato il modo in cui sono stati effettuati la gestione, e la creazione di questi intervalli, utilizzati poi in seguito per decidere quali casi prendere in considerazione nel processo di retrieval e quali scartare a priori.
Gestione degli intervalli di distanza
Per la gestione degli intervalli di distanza tra caso input e casi memorizzati è stata definita una nuova classe di oggetti, chiamata IntervalBound, e definita come segue:
class IntervalBound {
CBRCase _case;
double loverBound;
double upperBound;
double intervalMedian;
public IntervalBound (CBRCase _pcase, double lb, double ub, double med){
_case = _pcase;
loverBound = lb;
upperBound = ub;
intervalMedian = med;
}
public String toString(){
return "CaseID: " + _case.getID() + " LBound: " + loverBound + ", UBound: " +
upperBound + ", Middle: " + intervalMedian;
}
}
Ogni oggetto di questo tipo ha un campo CBRCase che contiene il caso in questione e 3 campi di tipo double che conterranno il lower bound, l’upper bound e il punto medio dell’intervallo di distanza stimato tra il caso in esame e il caso query.
Calcolo degli intervalli di distanza
E’ stato definito un metodo, calculateIntervals, che prende come parametri la lista di oggetti RetrievalResult, contenenti per ogni caso la sua distanza dal mediano e un double che rappresenta la distanza tra il caso mediano e il caso query. Tale metodo restituisce un arraylist di oggetti IntervalBound, definiti sopra, contenenti gli estremi dell’intervallo di distanza stimato mediante la disuguaglianza triangolare descritta in precedenza e il punto medio di tale intervallo. Nel caso in cui l’estremo superiore risulti essere un valore superiore a 1, si tronca proprio ad 1, perché essendo tutte le distanze normalizzate nell’intervallo [0,1], 1 è rappresenta proprio il valore massimo di distanza possibile.
Di seguito il metodo che effettua questo calcolo degli intervalli:
public static CollectioncalculateIntervals (Collection cases, double med ){ List intervals = new ArrayList (); for(RetrievalResult _case: cases) { double lb = Math.abs(_case.getEval()- med); double ub = Math.abs(_case.getEval()+ med); if (ub > 1) ub = 1; intervals.add(new IntervalBound(_case.get_case(), lb, ub, (lb + ub)/2 )); } return intervals; }
Pruning dei casi da non considerare
Una volta “costruiti” gli intervalli di stima di distanza si effettua una prima operazione di pruning, cioè di taglio, di quei casi per cui il lower bound è maggiore del minimo degli upper bound, che quindi non vengono presi in considerazione e non necessitano dell’operazione di calcolo esatto della loro distanza dal caso query.
Per fare questo è stato sviluppato un metodo statico che prende in input la lista di oggetti IntervalBound e un valore double che rappresenta la “soglia” di taglio; tutti i casi per cui il lower bound è superiore a tale valore vengono rimossi.
Il metodo ritorna un valore intero che indica, ad ogni chiamata, il numero di casi “tagliati” e ci permette quindi di sapere quanti di essi sono stati scartati da ogni pivot che di volta in volta viene scelto.
public static int pruneIntervals (Listintervals, double best) { int n = 0; for(int i = 0; i < intervals.size(); i++) { if (intervals.get(i).loverBound > best) { if (logging) file.println("Pruned Case: " + intervals.get(i)._case.getID()); //System.out.println("Pruned Case: " + intervals.get(i)._case.getID()); intervals.remove(i); n++; i--; } } return n; }
Come si vedrà in seguito il processo di retrieval può essere eseguito in una modalità per cosi dire verbosa, dove vengono tracciate tutte le operazioni effettuate e vengono raccolti dei dati significativi per analizzare il modo di operare dell’algoritmo. Una di queste operazioni consiste nel tenere traccia di quali sono i casi tagliati da ciascun pivot, andando a scrivere sul file di log l’ID del caso che di volta in volta viene rimosso.
Come detto, la prima esecuzione di tale metodo viene effettuata non appena creati gli intervalli, senza aver ancora quindi effettuato la scelta del pivot. In questo primo caso il parametro double che fa da “soglia” nella routine di prouning, come si è detto, assume il valore del minimo tra gli UpperBound dei vari casi. Questo è il metodo che si preoccupa di rendere disponibile tale valore alla funzione di pruning:
public static double getMinUB(Listintervals) { double min = 1; for (IntervalBound _int: intervals) if (_int.upperBound < min) min = _int.upperBound; //System.out.println("MINIMO: " + min); return min; }
Il ciclo di esecuzione
Come visto in fase di introduzione ad inizio capitolo, una volta che l’algoritmo ha a disposizione tutti i dati che gli servono per “partire”, esegue un ciclo iterativo che parte con la scelta di un caso Pivot per guidare la ricerca, del quale viene calcolata la distanza esatta dal caso query e a seconda di tale valore viene dapprima aggiornato il valore corrente della soluzione e poi effettuata l’operazione di “taglio” dei casi che dopo tale esecuzione non sono più significativi ai fini della ricerca perché aventi un lower bound che è già più alto del valore di distanza del caso che rappresenta la soluzione al momento.
Per aggiornamento della soluzione corrente, l’algoritmo originale intende, l’assegnazione del solo Pivot corrente alla soluzione se il suo valore di distanza è il minore fino a quel momento, e l’aggiunta del pivot alla soluzione se la sua distanza è uguale a quella di qualche altro caso precedentemente scelto come Pivot e analizzato. Cioè quello che prima era stato indicato con
Se BESTp > BEST si pone SOL = PIVOT e BESTp = BEST
Se BESTp = BEST si pone SOL = {PIVOT, SOL}
Nell’implementazione pratica in realtà, utilizzando un arraylist come struttura per mantenere i casi da recuperare, cioè la soluzione, in entrambi i casi si effettua l’inserimento del nuovo pivot nella lista che verrà poi comunque ordinata da un opportuno metodo.
Di seguito è riportato l’estratto principale di codice del ciclo di esecuzione dell’algoritmo implementato:
// INIZIALIZZAZIONE
double BESTp = 1;
double BEST = 0;
double dFromQtoPivot = 0;
// CICLO
while ((pivot = choosePivot(intervals)) != null)
{
dFromQtoPivot = 1 - gsf.compute(pivot._case.getDescription(), query.getDescription(),
pivot._case, query, simConfig);
BEST = dFromQtoPivot;
if (BESTp > BEST)
{
res.add(new RetrievalResult(pivot._case,1-dFromQtoPivot));
BESTp = BEST;
}
else if (BESTp == BEST)
res.add(new RetrievalResult(pivot._case,1-dFromQtoPivot));
n = pruneIntervals(intervals, BEST);
intervals.remove(pivot); // RIMUOVO IL PIVOT }
La scelta del Pivot
Ad ogni iterazione occorre effettuare la scelta del pivot, andando a prendere il caso il cui punto medio dell’intervallo di stima della distanza della query risulta essere il minore tra tutti. Per fare questo si lavora sulla struttura contenente la lista di oggetti IntervalBound, scorrendola e aggiornando di volta in volta il valore del minimo punto di mezzo del segmento e selezionando il relativo caso:
public static IntervalBound choosePivot(Listintervals) { double min = 1; IntervalBound pivot = null; for(IntervalBound _case: intervals) { if (_case.intervalMedian < min) { min = _case.intervalMedian; pivot = _case; } } return pivot; }
Modalità di esecuzione
L’algoritmo di Pivoting Retrieval implementato è stato sviluppato per poter essere eseguito in 2 modalità di funzionamento: una modalità di funzionamento classica con il solo retrieval dei casi più simili secondo la metodologia illustrata, e una modalità per cosi dire di diagnostica dell’algoritmo che raccoglie i log di tutte le operazione che vengono eseguite. Questo perché oltre al fatto di integrare l’algoritmo nel framework si aveva la necessità di avere anche dei dati per poter effettuare uno studio del suo comportamento. La scelta della modalità di esecuzione viene effettuata tramite una flag al momento della chiamata del metodo; dal punto di vista pratico uno dei parametri in ingresso del metodo è un valore booleano che sta ad indicare se raccogliere o meno tutte le informazioni di esecuzione.
Tale parametro è il boolean verbose che si vede nel prototipo del metodo di Retrieval
public static CollectionPivotingScoringMethod (Collection cases, CBRCase median, CBRQuery query, NNConfig simConfig, List distToMedian, boolean verbose)
Modalità di esecuzione con log
Nel caso in cui si voglia eseguire l’algoritmo con la funzionalità di log attivata occorrerà passargli true come valore dell’apposito parametro. Ecco un esempio di come deve essere fatta la chiamata al metodo di Retrieval, utilizzato nella creazione di un sistema di prova che sfruttasse l’algoritmo sviluppato:
Collectioneval = PivotingScoringMethod.PivotingScoringMethod(_caseBase.getCases(), median, query, simConfig, distToMedian, true);
Ora andiamo ad analizzare in cosa consistono queste funzionalità di analisi di esecuzione e di logging che sono state previste.
Abilitando tale funzione vengono scritti, ad ogni esecuzione dell’algoritmo di Retrieval 2 file di testo:
Il primo di questi 2 files è un files di logging generale che raccoglie tutte le informazioni che riguardano l’intero ciclo di esecuzione e più precisamente:
- indicazione del numero della run
- la descrizione del caso mediano e della query
- la distanza tra il caso query e il caso mediano
- gli intervalli di stima della distanza tra il caso query e tutti i casi della base che
sono stati calcolati - Ad ogni scelta del pivot, viene registrato il suo ID, la sua distanza dal caso
mediano, e qualora ve ne siano, la lista dei casi che “tagliati” da tale Pivot.
Di seguito viene riportato l’estratto di un file di questo tipo, creato durante l’esecuzione di un ciclo di Retrieval in una applicazione sviluppata in fase di testing:
Run: 4 ----------------------------- MEDIAN: (null;Recreation;3;Tyrol;Car;10;July;HolidayFlat) QUERY: (null;Skiing;1;GiantMountains;Car;7;December;TwoStars) Distance from Query to Median: 0.6146837720714345 ----------------------------- Distance Intervals: CaseID: Journey1 LBound: 0.141695970605, UBound: 1.0, Middle: 0.57084798530 CaseID: Journey2 LBound: 0.013065934156, UBound: 1.0, Middle: 0.50653296707 CaseID: Journey3 LBound: 0.117886446795, UBound: 1.0, Middle: 0.55894322339 CaseID: Journey4 LBound: 0.060684981775, UBound: 1.0, Middle: 0.53034249088 CaseID: Journey5 LBound: 0.105981684891, UBound: 1.0, Middle: 0.55299084244 CaseID: Journey6 LBound: 0.117886446795, UBound: 1.0, Middle: 0.55894322339 CaseID: Journey7 LBound: 0.094076922986, UBound: 1.0, Middle: 0.54703846149 .... .... CaseID: Journey1021 LBound: 0.1971623819, UBound: 1.0, Middle: 0.5985811909 CaseID: Journey1022 LBound: 0.0662100010, UBound: 1.0, Middle: 0.5331050005 CaseID: Journey1023 LBound: 0.0543052390, UBound: 1.0, Middle: 0.5271526195 CaseID: Journey1024 LBound: 0.2090671438, UBound: 1.0, Middle: 0.6045335719 .... .... Current Pivot: Journey715 Distance from current Pivot and Query: 0.7738095238095238 Number of Cases pruned: 0 ----------------------------- Current Pivot: Journey949 Distance from current Pivot and Query: 0.48750184858334233 Pruned Case: Journey894 Number of Cases pruned: 1 ----------------------------- Current Pivot: Journey961 Distance from current Pivot and Query: 0.3765885339761965 Pruned Case: Journey23 Pruned Case: Journey49 Pruned Case: Journey68 Pruned Case: Journey71 Pruned Case: Journey111 Pruned Case: Journey203 Pruned Case: Journey406 Pruned Case: Journey437 Pruned Case: Journey450 Pruned Case: Journey452 Pruned Case: Journey462 Pruned Case: Journey471 Pruned Case: Journey478 Pruned Case: Journey499 Pruned Case: Journey505 Pruned Case: Journey517 Pruned Case: Journey579 Pruned Case: Journey584 Pruned Case: Journey966 Number of Cases pruned: 19 ----------------------------- Current Pivot: Journey935 Distance from current Pivot and Query: 0.36190476190476184 Number of Cases pruned: 0 ----------------------------- .... ....
Il secondo dei files generati durante l’esecuzione in modalità verbosa è invece concentrato esclusivamente sull’operazione di pruning e raccoglie per ogni caso scelto come pivot il numero di casi che vengono “tagliati” e alla fine elabora alcuni dati di interesse ai fini di studiare il comportamento dell’algoritmo.
Anche in questo caso viene illustrato un estratto di uno di questi files generato durante una run di test:
InitialPruning,0 Journey129,0 Journey715,0 Journey949,1 Journey961,19 Journey864,163 Journey816,0 Journey819,0 .... .... Journey859,0 Journey863,0 Journey814,65 Journey817,0 Journey820,0 .... .... Journey704,0 Journey935,0 ----------------------------- STATS: Total pruned cases: 272 Max number of cases pruned by a pivot: 163 Pivot with 0 pruned cases: 747
Tali files vengono creati in automatico, ad ogni esecuzione di un ciclo di CBR, quindi sostanzialmente ad ogni query che viene sottoposta al sistema.
E’ stato previsto quindi un meccanismo per assegnare a questi files un nome al quale viene aggiunto il numero di run, in modo da poter raccogliere i dati sulle run di una certa esecuzione del sistema. Inizialmente si è pensato di costruire i files di testo prendendo la data dal sistema e aggiungendo ad essa il numero di run per il primo file di log generale; al file specifico sulle operazioni di pruning è stata aggiunta in coda al nome del file la stringa PruningStats.
Quindi in seguito al lancio dell’applicazione e all’esecuzione di alcuni cicli di retrieval su alcune query verranno generati ad esempio i files:
23-06-2008_run1.txt 23-06-2008_run1_pruningStats.txt 23-06-2008_run2.txt 23-06-2008_run2_pruningStats.txt 23-06-2008_run3.txt 23-06-2008_run3_pruningStats.txt
e cosi via.
Successivamente è stata prevista la possibilità di specificare una stringa con il quale salvare i files di log relativi ad una determinata sessione di esecuzioni; a tale nome verrà sempre aggiunta la stringa che indica il numero di run e, per il “file di pruning” la dicitura PruningStats.
Questo approccio è stato scelto per poter avere un modo per raggruppare i dati provenienti da determinate esecuzioni che, per cosi dire fanno parte della stessa sessione. In seguito è stato poi previsto un modo per analizzare tali risultati, prevedendo un metodo che va ad estrarre i dati delle run da tutti i files che hanno la prima parte del nome uguale.
Analisi dell’efficacia dell’operazione di pruning
Come si diceva è possibile raccogliere i dati relativi a determinate esecuzioni del ciclo di retrieval appartenenti ad una carta “sessione” identificata da una particolare stringa che da la parte iniziale ai nomi dei files che loggano le informazioni. Come si è visto, tali nomi posso essere ad esempio costituiti dalla data in cui si sono effettuati i test.
Vediamo un esempio:
Si sono eseguite 9 run, cioè sono state sottoposte al sistema 9 casi query sui quali effettuare il retrieval, ed avendo ordinato l’esecuzione in modalità “verbosa” sono stati creati i 2 files di log per ognuna delle 9 run; si sono ottenuti quindi i files:
24-06-2008_run1.txt 24-06-2008_run1_pruningStats.txt 24-06-2008_run2.txt 24-06-2008_run2_pruningStats.txt .... .... 24-06-2008_run9.txt 24-06-2008_run9_pruningStats.txt
A questo punto è possibile chiamare il metodo di valutazione, per andare ad estrarre i dati da questi file, passandogli come parametro la stringa che da la parte iniziale ai loro nomi, e cioè in questo caso “24-06-2008”.
Inoltre è possibile specificare quanti di questi file relativi alle run effettuate prendere in considerazione; questo viene fatto specificando tale valore attraverso il secondo parametro del metodo che ha quindi questo prototipo:
public static void evaluate(String s, int runs)
Quindi se si vogliono prendere in considerazione tutte e nove le runs effettuate per la
sessione del “24-06-2008” occorrerà chiamare il metodo nel modo seguente:
PivotingScoringMethod.evaluate("24-06-2008", 9);
Nel caso in cui non si vogliano prendere in considerazione tutte, ma si ritenga che solo le prime N siano significative basterà impostare opportunamente il parametro runs da passare la metodo.
Una volta invocato il metodo, esso va a prendere, per ogni run, il dato relativo al numero di casi che sono stati “tagliati” nelle varie fasi di pruning, e quindi non sono stati considerati nel processo di retrieval, nel senso che non sono stati confrontati esplicitamente con il caso query e mostra poi in modo grafico.
Tornando all’esempio che si stava considerando si può mostrare il risultato ottenuto:
La figura mostra per ogni run il numero di casi che sono stati “tagliati”.
Se si vanno ad aprire il files di log generati, dai quali sono stati presi tali valori, si vede che essi erano:
Test
Il test precedente, come molti altri di quelli effettuati, è stato realizzato integrando l’algoritmo di Pivoting-Based Retrieval all’interno del sistema di CBR completo, fornito come esempio con il framework, Travel Recommender, nel quale si è appunto sostituito questa metodologia di retrieval sviluppata a quella classica di KNN con cui il sistema di esempio era stato creato. Il database utilizzato è stato quindi quello già presente come esempio e col quale lavorava il sistema, che conta una base di casi costituita da 1024 casi.
Analisi dell’algoritmo
Per effettuare uno studio statistico del comportamento dell’algoritmo occorrerebbero dei test incrociati su diversi database, ed occorrerebbe che i casi memorizzati, cosi come anche le query da sottoporre al sistema, fossero il più reale possibile.
Comportamento
Nonostante ciò, dai test effettuati, il comportamento dell’algoritmo è risultato essere, indicativamente, quello che ci si aspettava con pochi “tagli”, ma netti, in corrispondenza di casi vicini alla query.
Si può avere un’idea di questa “relazione” analizzando l’output di una esecuzione del ciclo di retrieval ed andando a mettere in relazione tra loro, grazie ai meccanismi di logging previsti, il numero di “tagli” effettuati dai casi man mano scelti come pivot, con il risultato dei casi recuperati dal sistema.
Un esempio di analisi di questo tipo è riportato qui di seguito, dove si illustra dapprima un estratto del contenuto del “file di pruning“ generato dall’esecuzione e poi l’elenco dei casi recuperati in ordine di similarità rispetto alla query.
InitialPruning,0 Journey714,39 Journey721,0 Journey717,0 Journey720,34 Journey724,0 Journey725,0 Journey1,0 Journey666,0 Journey19,350 .... .... Journey352,0 Journey864,43 Journey129,0 .... .... Journey861,0 Journey871,126 Journey990,0 .... .... Journey1022,0 Journey982,0 ----------------------------- STATS: Total pruned cases: 592 Max number of cases pruned by a pivot: 350 Pivot with 0 pruned cases: 427
I casi recuperati, dal ciclo di retrieval che ha prodotto questo file di log, sono stati i seguenti, ordinati dal più simile al più distante dalla query:
Journey871 Journey864 Journey19 Journey720 Journey666 Journey714 Journey721
Dai dati riportati in questo esempio, emergono le conferme alle considerazione espresse qualche riga sopra.
Si può aggiungere che, avendo a disposizione diverse basi di dati, come detto, più “reali” possibili, test specifici sull’efficienza dell’algoritmo sviluppato sarebbero di facile realizzazione avendo previsto, proprio a questo scopo, la possibilità di eseguirlo in modalità “verbosa”, cioè con la creazione, ad ogni ciclo, dei 2 files di log descritti in precedenza; basterebbe, a questo punto, estrarre i dati da essi ed effettuarne l’analisi secondo i criteri che si ritengono più opportuni.
Prestazioni
Anche per quanto riguarda le prestazioni del nuovo algoritmo si può fare un discorso analogo e piuttosto intuitivo: in un ciclo di retrieval in cui il numero di casi che subiscono il pruning, e che quindi non vengono confrontati in modo esplicito con il caso query, è molto alto, le performance migliorano in modo significativo, mentre al contrario se l’attività di pruning di una determinata esecuzione è molto limitata le performance rischiano anche di peggiorare.
In questo senso sono stati eseguiti dei test introducendo nel sistema un meccanismo per misurare il tempo impiegato dai diversi algoritmi per soddisfare le richieste. Per fare questo si è utilizzata la classe Date di JAVA, andando a “prendere il tempo” subito prima della chiamata dell’algoritmo e poi al termine della sua esecuzione e facendo la differenza dei valori in millisecondi ritornati dal metodo getTime().
Date start = new Date(); Collectioneval = PivotingScoringMethod.PivotingScoringMethod(_caseBase.getCa ses(), median, query, simConfig, distToMedian, true); // Select k cases Collection selectedcases = SelectCases.selectAll(eval); Date end = new Date(); System.out.println("TEMPO ESECUZIONE: " + (end.getTime() - start.getTime()));
Con questo criterio si sono recuperati i tempi di esecuzione su alcune query dei 3 algoritmi
- KNN “classico”
- Pivoting-Based Retrieval in modalità “normale”
- Pivoting-Based Retrieval in modalità con logging
I risultati di alcune di queste esecuzioni sono riportati nella tabella sottostante, e danno una conferma delle considerazioni espresse finora.
Per quanto riguarda i tempi relativi all’esecuzione dell’algoritmo di Pivoting-Based retrieval, si è preso in considerazione il solo tempo di retrieval, senza considerare il costo di costruzione delle strutture dati e i costi di calcoli di cui necessita, come ad esempio l’estrazione del caso mediano o il calcolo/caricamento delle distanze del caso mediano stesso da tutti i casi della case base.