complearn - Dipartimento di Informatica

UNIVERSITA’ DEGLI STUDI DI SALERNO
FACOLTA’ DI SCIENZE MATEMATICHE, FISICHE E NATURALI
CORSO DI LAUREA IN INFORMATICA
CompLearn Toolkit
Prof.
Bruno Carpentieri
Gruppo Mapag:
Pietro Albano
Arcangelo Castiglione
Marialuisa Bevilacqua
Gianluca Zaccagnino
Antonio Ingenito
Outline

Che cos’è CompLearn
Richiami su Normalized Compression Distance
Istallazione del toolkit CompLearn
Descrizione di CompLearn

Comandi ncd e maketree
Un esempio di funzionamento in ambiente
Windows
CompLearn

E’ un sistema software di facile utilizzo costruito per
applicare tecniche di compressione al processo di
identificazione e apprendimento di pattern
Fornisce questo supporto sotto forma di una libreria
scritta in C che può essere eseguita nei più moderni
ambienti di sviluppo
Fornisce inoltre un piccolo insieme di utilities da linea di
comando come semplici applicazioni che usano tale
libreria
Approccio basato sulla compressione

Tale approccio è potente in quanto possono essere
identificati pattern in diversi domini di applicazione:

Classificazione di stili musicali
Identificazione del linguaggio di insiemi di testo
Rilevamento delle relazioni tra diverse specie e anche l’inizio di
nuovi virus sconosciuti come la SARS
E’ un metodo generale che non richiede nessuna
conoscenza di base su particolari classificazioni
Normalized Compression Distance

NCD è una famiglia di funzioni che prende come
argomenti due oggetti (literal files) e valuta una formula
fissata in termini di versioni compresse di tali oggetti,
combinate e non.
Siano x e y due oggetti e C(x) la lunghezza della versione
compressa di x usando il compressore C, allora:
NCD ( x, y ) =

C ( x, y ) − min{C ( x), C ( y )}
max{C ( x), C ( y )}
Tale metodo è il risultato di sviluppi matematici teoretici
basati sulla complessità di Kolmogorov
Famiglia delle NCD
Include:

NID (Normalized Information Distance): il compressore raggiunge la
complessità di Kolmogorov dei dati, cioè
C ( x ) = K ( x ) dove
K ( x ) è la complessità di Kolmogorov di x; in questo caso parliamo
di Compressore a complessità di Kolmogorov
NGD (Normalized Google Distance): la distanza di Google misura la
correlazione semantica derivata dal numero di entry restituita dal
motore Google per un dato set di keyword. Parole con significato
simile tendono ad essere vicine in termini di distanza di Google,
mentre parole con significato diverso tendono ad essere lontane.
La NGD di due termini di ricerca x e y sarà:
dove M è il numero totale di pagine web ricercate da Google
Istallazione

In ambiente Linux, dopo aver scaricato il sorgente (www.complearn.org) bisogna
controllare che sia istallata GSL (GNU Scientific Library) usata per generare matrici,
tramite il comando
gsl-config --libs
se viene visualizzato qualcosa come –L o –l significa che GSL è presente nel sistema
altrimenti bisogna provvedere alla sua istallazione.
Dopo esserci posizionati nella directory di CompLearn si procede con i seguenti passi di
istallazione:
./configure
make
make install

In ambiente Windows, per il funzionamento di CompLearn è necessario copiare le dll nella
stessa directory in cui sono presenti gli eseguibili di ncd e maketree precedentemente
scaricati ed eseguiti e infine procedere con i comandi base del software dal prompt dei
comandi.
Descrizione del sistema CompLearn

Il toolkit CompLearn come abbiamo detto in precedenza è un
insieme di utilities per analizzare tipi di dati anche eterogenei tra
loro
I comandi principali di CompLearn ncd e maketree in ambiente
Linux usano il file di configurazione config.yml
In primo luogo, nella home dell’utente viene cercata la directory
.complearn.
In tale directory, CompLearn legge il file di configurazione
config.yml, un file di testo strutturato nel formato YAML
Qualora CompLearn non potesse localizzare questo file, vengono
usati valori di default
Formato del file config.yml

<NomeVariabile>: <valore>
Sono ammessi spazi bianchi e i commenti vengono
contrassegnati dal simbolo #
Le variabili possono essere di tre tipi: boolean, integer,
oppure string
Nomi di variabili (1)
I nomi di variabili valide sono:
compressor: string (ncd)
Indica il compressore che deve essere usato. Valori validi sono:
bzip, zlib, e google.

GoogleKey: string (ncd, google
compressor)
Chiave necessaria per effettuare query nel database Google.

blocksize: int (ncd, bzip compressor)
Un intero da 1 a 9. 9 dà la migliore compressione ma occupa
maggior memoria. Default 9.
Nomi di variabili (2)

workfactor: int (ncd, bzip compressor)
Un intero da 0 a 250 e controlla i comportamenti della fase di compressione
nel caso di input peggiore, cioè molto ripetitivo.

bzverbosity: int (ncd, bzip compressor)
Un intero tra 0 e 4. 0 è silente e valori maggiori danno la verbosità
dell’output in modo crescente. Default 0.

zliblevel: int (ncd, zlib compressor)
Un intero da 1 a 9. 1 è il più veloce e produce la minima compressione. 9 è il
più lento e produce la massima compressione. Default 9.
Nomi di variabili (3)

selfAgreementTermination: bool (maketree)
Indica se k numeri di alberi raggiungono o meno uno score accettato prima
che il programma termini. Default 1.

maxFailCount: int (maketree)
Un intero che specifica il numero massimo di alberi ‘failed’ che occorrono
in successione prima che il programma termini. E’ usato solo quando
selfAgreementTermination è off. Default 100000.

isOrdered: bool (maketree)
Indica se i nodi sono ordinati o meno. Default 0.

isRooted: bool (maketree)
Indica se creare o meno un albero binario con radice. Default 0.
Esempio di file config.yml
#
# comments are written like this
#
GoogleKey: A/OGsJTQFHSpufko/rRS/KLA7NAT8UNf
compressor: bzip
blocksize: 5
workfactor: 100
isRooted: 1
selfAgreementTermination: 0
maxFailCount: 50000
# etc
Il comando ncd

Calcola Normalized Compression Distance
ncd di default usa il compressore bzlib.Vengono passati come argomento due nomi di file da linea di
comando. I contenuti dei file vengono compressi e viene restituita la distanza di compressione
normalizzata tra i due file.
Esempio:
ncd filename1 filename2

Con l’opzione –b, sarà creato di default un file binario chiamato distmatrix.clb.
Opzioni:

-c --compressor [bzlib | zlib | blocksort
-f, --file-mode=FILE
-l, --literal-mode=STRING
-p, --plainlist-mode=FILE
-t, --termlist-mode=FILE
-d, --directory-mode=DIR
]
In ambiente Windows:

l’unica opzione funzionante è –d, e l’unico compressore che da risultati positivi è zlib!!!!
Il file creato da tale comando è in formato testo (.txt)
Il comando maketree

maketree di default prende in input la matrice di
distanza quadrata creata con il comando ncd (con
l’opzione –b) e genera un albero binario unrooted. Il
risultato è inserito in un file chiamato treefile.dot
Affinchè maketree funzioni correttamente, la matrice
di distanza deve avere i seguenti requisiti :

deve essere una matrice quadrata, cioè gli argomenti in input al
comando ncd devono essere dello stesso tipo
la sua dimensione deve essere almeno 4x4
Il comando neato

Crea un file (in formato ps o png) in cui vi è il
layout dell’ albero contenuto in treefile.dot
Esempio:
neato -Tps -Gsize=7,7 treefile.dot >tree.ps

Può essere usato dopo aver istallato GraphViz, un
software open-source per la visualizzazione grafica.
CompLearn: Step 1

Il seguente esempio mostra il funzionamento di CompLearn in
ambiente Windows
Sono stati usati file di natura eterogenea, quali immagini (di alcuni
minerali in formato .bmp), file audio (generi musicali diversi in
formato .midi) e file di testo ( sequenze di genomi animali e non in
formato .txt).
Step 1: Creare una matrice di distanza
ncd -d dir1 dir2 >distmatrix.txt
Questo comando prende come argomenti due directory e crea una matrice di distanza
quadrata nel file distmatrix.txt.
Distmatrix.txt
calcite.bmp 0,934233 1,149052 1,098256 1,060244 1,080970 1,045553 1,075150 1,043821 1,075150 1,081193 1,022481 1,066902 1,150569 1,151024 1,151175 0,927521 1,150872 1,149204
0,937593 1,020835 1,034836 1,016128 1,007979
cat.txt 1,144170 0,917191 1,125316 1,053324 1,113079 1,041678 1,060008 1,048584 1,060008 1,099375 1,029737 1,109000 0,932927 0,929976 0,892211 1,171322 0,913061 0,915224
1,139872 1,051721 1,043036 1,019799 1,007735
dog.txt 1,145032 0,906627 1,125704 1,054003 1,113604 1,042619 1,061042 1,047873 1,061042 1,099375 1,029975 1,109683 0,928783 0,934520 0,896538 1,173492 0,911968 0,907418
1,140551 1,052635 1,043196 1,020005 1,007948
dolomite.bmp 0,934233 1,142974 1,083350 1,037246 1,058906 1,033874 1,045241 1,065509 1,045241 1,050505 1,014908 1,041415 1,139697 1,142713 1,142199 0,904350 1,139972
1,141753 0,937593 1,021261 1,031084 1,010807 1,007903
elephant.txt 1,146324 0,932062 1,126287 1,053731 1,112728 1,042453 1,061418 1,049662 1,061418 1,100241 1,030015 1,110365 0,941398 0,939213 0,928486 1,175407 0,933281 0,934247
1,142043 1,052696 1,043571 1,020294 1,007811
Gente come noi.mid 1,048402 1,078737 1,021447 1,014111 1,017481 1,019870 1,028131 1,007124 1,028131 1,017554 1,017248 1,007639 1,078884 1,080353 1,080499 1,040323 1,079838
1,078810 1,047962 1,000914 1,010504 1,007878 1,002893
gorilla.txt 1,142447 0,930153 1,124150 1,051696 1,111501 1,041401 1,059725 1,049517 1,059725 1,096777 1,029103 1,107635 0,944998 0,824074 0,922091 1,173510 0,923382 0,927335
1,138787 1,052757 1,041642 1,019469 1,007720
hippopotamus.txt 1,143739 0,916433 1,125704 1,052510 1,112202 1,041844 1,060290 1,048697 1,060290 1,098509 1,029499 1,108659 0,938023 0,927856 0,888043 1,173747 0,920610
0,914028 1,139465 1,052330 1,042500 1,019922 1,007903
horse.txt 1,143452 0,917786 1,124150 1,052714 1,111851 1,041180 1,059819 1,047724 1,059819 1,098413 1,029261 1,108545 0,934436 0,928013 0,892249 1,172649 0,912889 0,906156
1,139330 1,053061 1,042339 1,019964 1,007857
human.txt 1,145606 0,937463 1,126093 1,053596 1,112728 1,042066 1,060854 1,049990 1,060854 1,099567 1,029579 1,109569 0,943039 0,823541 0,921928 1,174069 0,930311 0,934874
1,140958 1,052208 1,043357 1,020170 1,007903
manic.mid 1,061172 1,111564 1,021566 1,019403 1,013850 1,010461 1,011757 1,006146 1,011757 1,031842 1,010230 1,019684 1,107413 1,113888 1,111756 1,076923 1,109285 1,111043
1,061457 1,006397 1,012755 1,004620 1,002649
mops1m1.mid 1,082137 1,076527 1,017748 1,013636 1,012973 1,006199 1,002069 0,995038 1,002069 1,032804 1,011816 1,025600 1,075954 1,079389 1,078435 1,095420 1,076718
1,076145 1,081264 1,017789 1,006860 1,005073 1,004857
mops2m3.mid 1,083860 1,088109 1,019817 1,020014 1,021213 1,008690 1,010064 0,998166 1,010064 1,030784 1,012053 1,028217 1,086887 1,090708 1,088924 1,103101 1,086122
1,087655 1,082757 1,016083 1,012326 1,004950 1,005147
mozar.mid 1,065192 1,082806 1,017097 1,015197 1,014727 1,007085 1,007054 0,997421 1,007054 1,026166 1,009635 1,019911 1,081905 1,084660 1,083917 1,081957 1,082162 1,082571
1,065527 1,011940 1,010451 1,004207 1,004659
mozart.mid 1,081562 1,070161 1,017486 1,015807 1,024544 1,005314 1,006490 0,995198 1,006490 1,032131 1,010705 1,029127 1,068752 1,072364 1,072301 1,101893 1,069689 1,070978
1,080043 1,019312 1,007771 1,005692 1,004888
zaffiro.bmp 0,935825 1,143018 1,093230 1,059159 1,077010 1,044888 1,076749 1,041467 1,076749 1,081866 1,022917 1,068153 1,143865 1,144852 1,144570 0,933709 1,144570 1,142313
0,937593 1,020469 1,034139 1,015839 1,007796
CompLearn: Step 2
Step 2: Creare un albero
maketree distmatrix.txt
Qui usiamo la matrice di distanza creata precedentemente per creare un albero
binario senza radice. L’albero risultante viene dato in output come file .dot
chiamato di default treefile.dot. Tale file .dot descrive come sono connessi i
nodi dell’albero e quali sono le loro label.
Se la matrice è piuttosto grande, maketree potrebbe impiegare diverso tempo
prima di completare.
Treefile.dot
graph "tree" {
label="S(T)=0.954771";
0 [label="calcite.bmp"];
1 [label="cat.txt"];
2 [label="dog.txt"];
3 [label="dolomite.bmp"];
4 [label="elephant.txt"];
5 [label="Gente"];
6 [label="gorilla.txt"];
7 [label="hippopotamus.txt"];
8 [label="horse.txt"];
9 [label="human.txt"];
10 [label="manic.mid"];
11 [label="mops1m1.mid"];
12 [label="mops2m3.mid"];
13 [label="mozar.mid"];
14 [label="mozart.mid"];
15 [label="zaffiro.bmp"];
16 [label=""];
17 [label=""];
18 [label=""];
19 [label=""];
20 [label=""];
21 [label=""];
22 [label=""];
23 [label=""];
24 [label=""];
25 [label=""];
26 [label=""];
27 [label=""];
28 [label=""];
29 [label=""];
0 -- 19 [weight="2"];
1 -- 29 [weight="2"];
2 -- 24 [weight="2"];
3 -- 27 [weight="2"];
4 -- 17 [weight="2"];
5 -- 27 [weight="2"];
6 -- 16 [weight="2"];
7 -- 29 [weight="2"];
8 -- 18 [weight="2"];
9 -- 21 [weight="2"];
10 -- 22 [weight="2"];
11 -- 20 [weight="2"];
------------------------
CompLearn: Step 3
Step 3: Lay Out dell’albero
C:\Programmi\Graphviz2.18\bin\neato –Tpng
treefile.dot >mytree.png
Questo comando neato creerà il file mytree.png che contiene una
rappresentazione a video dell’albero. Tale comando è messo a disposizione dal
software open-source GraphViz.
Step 4: Analisi dei risultati

Download Report