Torna alla pagina principale
Vai alla pagina del codice commentato


L'analisi



Lo scopo del progetto é quello di sviluppare un software capace, seguendo l'algoritmo Apriori, di calcolare le regole di associazione tra sottoinsiemi di item immagazzinati in una base di dati, ma anche quello di fare in modo che il suddetto software dialoghi con un database di tipo PostgreSQL.
Per cercare di analizzare meglio i problemi dovuti allo scambio di informazioni fra software e DBMS, abbiamo sviluppato "in parallelo" due programmi, che differiscono unicamente per numero di comandi e quantità di informazioni raccolte ad ogni richiesta al DBMS.

I due codici sono stati chiamati apriori_all.c e apriori_next.c .
Qual'é esattamente la differenza?
L'unica diversità é il comando che il programma comunica a PostgreSQL per entrare in possesso delle informazioni riguardanti le transazioni.
Nel codice di apriori_all.c, leggiamo infatti:
res=PQexec(conn,"DECLARE tr CURSOR FOR SELECT * FROM TRANSAZIONI ORDER BY ID,N");
if(PQresultStatus(res)!=PGRES_COMMAND_OK)
	{fprintf(stderr,"Comando CURSOR fallito: %s\n",PQerrorMessage(conn));
	 PQclear(res);
	 PQfinish(conn);
	 return 0;
	}

PQclear(res);
res=PQexec(conn,"FETCH ALL in tr");
if(PQresultStatus(res)!=PGRES_TUPLES_OK)
	{fprintf(stderr,"Comando FETCH ALL fallito: %s\n",PQerrorMessage(conn));
	 PQclear(res);
	 PQfinish(conn);
	 return 0;
	}


In questo caso il programma richiederà in una sola volta tutti i dati presenti nella tabella transazioni.
L'operazione equivalente nel codice di apriori_next.c (come già puó far sospettare il nome), é invece effettuata per mezzo di queste richieste:
res=PQexec(conn,"DECLARE tr CURSOR FOR SELECT * FROM TRANSAZIONI ORDER BY ID,N");
if(PQresultStatus(res)!=PGRES_COMMAND_OK)
	{fprintf(stderr,"Comando CURSOR fallito: %s\n",PQerrorMessage(conn));
	 PQclear(res);
	 PQfinish(conn);
	 return 0;
	}

PQclear(res);
res=PQexec(conn,"FETCH NEXT in tr");
if(PQresultStatus(res)!=PGRES_TUPLES_OK)
	{fprintf(stderr,"Comando FETCH NEXT fallito: %s\n",PQerrorMessage(conn));
	 PQclear(res);
	 PQfinish(conn);
	 return 0;
	}


Questo significa che ogni volta che il software dovrà analizzare una nuova riga della tabella "transazioni", ci sarà una richiesta verso il DBMS del tipo "FETCH NEXT ... " che provocherà una perdita di tempo nell'esecuzione del programma.

Passiamo ora all'analisi vera e propria, basata sui tempi di cpu registrati in varie prove.

Come prima prova abbiamo analizzato le differenze dei tempi all'aumentare delle transazioni nella tabella; in particolare abbiamo testato il programma dopo aver inserito i seguenti dati:


Si può notare come abbia cercato di mantenere costante (in rapporto) la quantità dei vari prodotti, per ottenere un'analisi il piú possibile indipendente da altri fattori oltre alla quantità di transazioni.
Abbiamo dunque analizzato i dati con l'aiuto del software statistico R (riportiamo qui sotto il codice).

#################
# Inizio codice R
#################

all1<-c(9,0.080,0.190,0.390,0.440,0.480,0.490,0.490)
next1<-c(9,2.460,4.720,7.380,9.490,11.520,11.530,11.530)
all2<-c(18,0.230,0.460,0.850,0.940,1.020,1.020,1.030)
next2<-c(18,5.000,10.060,15.030,19.880,24.490,24.490,24.490)
all3<-c(54,0.600,1.280,2.460,2.720,2.970,2.970,2.980)
next3<-c(54,15.240,30.570,45.730,59.720,74.390,74.400,74.400)
all4<-c(180,1.850,4.140,8.120,9.040,9.880,9.890,9.890)
next4<-c(180,50.000,100.320,153.060,203.110,251.350,251.350,251.360)
all5<-c(1000,11.000,23.760,45.850,51.120,55.890,55.890,55.900)
next5<-c(1000,278.760,561.020,846.280,1117.870,1390.260,1390.260,1390.270)

all<-matrix(data=c(all1,all2,all3,all4,all5),nrow=5,ncol=8,byrow=TRUE)
nex<-matrix(data=c(next1,next2,next3,next4,next5),nrow=5,ncol=8,byrow=TRUE)

#################
# Fine codice R
#################

Abbiamo cosí ottenuto due matrici di dati:


É da notare come ogni riga corrisponda ad un differente test.
Inoltre la prima colonna di entrambe le matrici identifica il numero di transazioni (in migliaia) presenti nel database, mentre le successive colonne sono i tempi registrati ai diversi intervalli.

Ho quindi eseguito alcune analisi grafiche:

#################
# Inizio codice R
#################

# Confronto fra nex e all
# all vs nex sul primo tempo 
plot(nex[,1],nex[,2],type='l',col='red',ylab="Secondi",xlab="Numero Transazioni",
	main="Confronto tra next e all all'aumentare delle transazioni\nPrimo Tempo")
points(nex[,1],nex[,2],col='red')
lines(all[,1],all[,2],type='l')
points(all[,1],all[,2])
# all vs nex sull'ultimo tempo 
plot(nex[,1],nex[,8],type='l',col='red',ylab="Secondi",xlab="Numero Transazioni",
	main="Confronto tra next e all all'aumentare delle transazioni\nUltimo Tempo")
points(nex[,1],nex[,8],col='red')
lines(all[,1],all[,8],type='l')
points(all[,1],all[,8])
Primo Tempo Ultimo Tempo




# crescita dei tempi del nex 
plot(nex[,1],nex[,8],type='l',col='red',ylab="Secondi",xlab="Numero Transazioni (in migliaia)",
	main="Crescita dei tempi nel next",lwd=2)
points(nex[,1],nex[,8],col='red',lwd=2)
lines(nex[,1],nex[,2],type='l',col=1,lwd=2)
points(nex[,1],nex[,2],col=1,lwd=2)
lines(nex[,1],nex[,3],type='l',col='orange',lwd=2)
points(nex[,1],nex[,3],col='orange',lwd=2)
lines(nex[,1],nex[,4],type='l',col=3,lwd=2)
points(nex[,1],nex[,4],col=3,lwd=2)
lines(nex[,1],nex[,5],type='l',col=4,lwd=2)
points(nex[,1],nex[,5],col=4,lwd=2)

legenda<- c(expression(paste("Ultimo Tempo"),paste("Quarto Tempo"),
	paste("Terzo Tempo"),paste("Secondo Tempo"),paste("Primo Tempo")))
legend(2,1300,legend=legenda,lty=1,lwd=3,col=c('red',4,3,'orange',1))
# crescita dei tempi dell'all 
plot(all[,1],all[,8],type='l',col='red',ylab="Secondi",xlab="Numero Transazioni (in migliaia)",
	main="Crescita dei tempi nell'all",lwd=2)
points(all[,1],all[,8],col='red',lwd=2)
lines(all[,1],all[,2],type='l',col=1,lwd=2)
points(all[,1],all[,2],col=1,lwd=2)
lines(all[,1],all[,3],type='l',col='orange',lwd=2)
points(all[,1],all[,3],col='orange',lwd=2)
lines(all[,1],all[,4],type='l',col=3,lwd=2)
points(all[,1],all[,4],col=3,lwd=2)
lines(all[,1],all[,5],type='l',col=4,lwd=2)
points(all[,1],all[,5],col=4,lwd=2)

legenda<- c(expression(paste("Ultimo Tempo"),paste("Quarto Tempo"),
	paste("Terzo Tempo"),paste("Secondo Tempo"),paste("Primo Tempo")))
legend(2,55,legend=legenda,lty=1,lwd=3,col=c('red',4,3,'orange',1))
Tempi nel next Tempi nell'all


#################
# Fine codice R
#################

I tempi considerati nei grafici sono i primi 4 calcolati (corrispondenti al termine dell'analisi a livello 1,2,3 e 4) e l'ultimo (prima di terminare il programma).
Notiamo innanzi tutto che l'aumento del tempo di utilizzo di cpu sembra crescere in modo lineare al crescere del numero delle transazioni.
Se confrontiamo i due programmi (prima coppia di immagini), vediamo però che la retta rossa (quella che rappresenta i tempi del codice "next") ha una forte inclinazione, mentre la retta nera (che rappresenta i tempi del codice "all") ne é quasi priva.
Dalla seconda coppia di grafici possiamo invece renderci conto dell'effettivo peso (dal punto di vista dell'utilizzo della cpu) del "colloquio" programma-DBMS: nel grafico a sinistra (relativo a "next") la differenza di tempo fra i livelli considerati sembra essere uguale (o quasi); nel grafico di destra (relativo ad "all") notiamo invece come il salto fra il secondo e il terzo tempo (quindi il tempo utilizzato per l'analisi a livello 3) sia decisamente maggiore degli altri e, al contrario, il tempo utilizzato per la conta a livello 4 e quella successiva (che comprende la conta a livello 5, l'ordinamento delle regole trovate e la scrittura dell'output) sia notevolmente ridotto.
Questo significa che nel next la maggior parte del tempo (più del 95% !!!) é utilizzato per scaricare i dati dal server (cosa che va fatta ad ogni livello), mentre l'all deve occuparsene una sola volta (e in maniera più rapida).



Come secondo banco di prova, abbiamo fatto variare il numero di prodotti che é possibile trovare nella tabella e abbiamo analizzato i tempi dei programmi:

Abbiamo quindi caricato i dati e svolto le analisi grafiche.

N.B.: Il codice che riporteremo d'ora in poi sarà relativo unicamente al caricamento dei dati in R, poiché i grafici saranno generati con gli stessi comandi riportati sopra (con le opportune modifiche).

#################
# Inizio codice R
#################

all1<-c(20,0.080,0.190,0.390,0.440,0.480,0.490,0.490)
nex1<-c(20,2.460,4.720,7.380,9.490,11.520,11.530,11.530)
all2<-c(10,0.110,0.170,0.250,0.330,0.390,0.410,0.410)
nex2<-c(10,2.660,5.260,7.910,10.720,13.280,13.290,13.300)
all3<-c(5,0.120,0.170,0.210,0.260,0.300,0.300,0.300)
nex3<-c(5,2.650,5.210,7.600,9.700,12.060,12.060,12.060)

all<-matrix(data=c(all1,all2,all3),nrow=3,ncol=8,byrow=TRUE)
nex<-matrix(data=c(nex1,nex2,nex3),nrow=3,ncol=8,byrow=TRUE)

#################
# Fine codice R
#################

Primo Tempo Ultimo Tempo
Tempi nel next Tempi nell'all

Dai grafici precedenti possiamo affermare che un aumento dei possibili prodotti non porta necessariamente ad un aumento del tempo utilizzato per l'analisi. Per quel che riguarda il codice "next" sembra infatti esserci un picco quando i prodotti presenti in tabella sono 10. Nel nostro test questo può avere un senso soprattutto considerando che abbiamo impostato come lunghezza massima di una transazione proprio 10! Se avessimo aumentato questo valore, avremmo avuto probabilmente un aumento di tempo utilizzato all'aumentare del numero dei prodotti, ma in misura nettamente inferiore agli incrementi visti nei precedenti test.



Ho poi considerato dei dataset creati in modo seguente:

Ho quindi caricato i dati:

#################
# Inizio codice R
#################

all1<-c(20,0.130,0.260,0.520,0.900,0.940,0.940,0.960) # il secondo 0.940 aggiunto per completare la matrice
nex1<-c(20,2.570,5.150,7.800,10.750,10.790,10.790,10.810) # il secondo 10.790 aggiunto per completare la matrice
all2<-c(15,0.120,0.220,0.370,0.560,0.700,0.770,0.800)
nex2<-c(15,2.250,4.810,7.380,10.050,12.670,12.740,12.770)
all3<-c(5,0.120,0.170,0.210,0.260,0.300,0.300,0.300)
nex3<-c(5,2.650,5.210,7.600,9.700,12.060,12.060,12.060)

all<-matrix(data=c(all1,all2,all3),nrow=3,ncol=8,byrow=TRUE)
nex<-matrix(data=c(nex1,nex2,nex3),nrow=3,ncol=8,byrow=TRUE)

#################
# Fine codice R
#################


Ed eseguito le principali analisi grafiche:


Primo Tempo Ultimo Tempo
Tempi nel next Tempi nell'all

Notiamo innanzi tutto che per effettuare un'analisi (con R) senza eccessivi problemi, ho arbitrariamente aggiunto un valore al vettore dei tempi relativo al test con 20 prodotti, che ,contrariamente agli altri test, terminava l'analisi a livello 4.
Questo, nei nostri grafici, porta ad un evidente crollo dell'ultimo tempo registrato. L'analisi mostra comunque un incremento del tempo piuttosto moderato all'aumentare del numero dei prodotti.


La terza serie di test a cui ho sottoposto i due codici riguarda principalmente il confronto tra lunghezza della transazione e tempo di calcolo:

Carico i dati:

#################
# Inizio codice R
#################

all1<-c(20,0.190,0.390,0.860,1.800,3.570,3.950,4.040)
nex1<-c(20,4.910,9.710,14.790,20.520,26.770,27.160,27.260)
all2<-c(15,0.110,0.270,0.610,1.120,1.180,1.220,1.240)
nex2<-c(15,3.810,7.620,11.580,15.720,19.050,19.090,19.110)
all3<-c(10,0.080,0.190,0.390,0.440,0.480,0.490,0.490)
nex3<-c(10,2.460,4.720,7.380,9.490,11.520,11.530,11.530)
all4<-c(5,0.040,0.100,0.130,0.150,0.170,0.170,0.170)
nex4<-c(5,1.550,2.890,4.420,5.710,6.970,6.980,6.980)

all<-matrix(data=c(all1,all2,all3,all4),nrow=4,ncol=8,byrow=TRUE)
nex<-matrix(data=c(nex1,nex2,nex3,nex4),nrow=4,ncol=8,byrow=TRUE)

#################
# Fine codice R
#################


Ed eseguo le analisi grafiche:


Primo Tempo Ultimo Tempo
Tempi nel next Tempi nell'all

Dai grafici si nota come l'aumento della lunghezza massima delle transazioni provochi un'impennata nel "consumo" di tempo. Particolarmente evidente é il salto nell'ultimo tempo del codice "all" quando si passa da una lunghezza di 15 a una di 20. Questo picco puó essere dovuto al considerevole aumento del numero di item-set che superano la soglia di supporto e confidenza, che porta il programma ad un calcolo piú pesante nella ricerca di regole da presentare in output.
É inoltre da notare che aumentando la lunghezza delle transazioni, si aumenta anche il numero di righe presenti nel database, facendo in modo che il codice "next" ci metta più tempo sia per l'aumento di calcoli nell'analisi che per il tempo utilizzato nello scaricare i dati dal server.


L'ultima serie di test a cui ho sottoposto i due codici riguarda una piccola quantità di dati sempre uguale, ma con una soglia di supporto di volta in volta differente: