pattern discovery in python con Apriori Method

Parlerò in questo post di uno script python per effettuare la pattern discovery: voglio cioè estrarre i pattern più frequenti da una lista di transazioni.

Lo script utilizza l'”Apriori Method” come algoritmo per la determinazione dei Frequent Pattern e al momento non si occupa della determinazione delle “association rules”.

L'”apriori method” è uno dei più semplici algoritmi non Brute Force per la Pattern Discovery e si basa sulla considerazione che se una data sequenza ha una certa frequenza nelle transazioni, tutte le sue sottosequenza devono avere una frequenza uguale o periore. E’ quindi possibile partire dalla sequenza più corte, selezionare quelle frequenti secondo una soglia predeterminata e costruire le sequenze più lunghe a partire da quelle selezionate in precedenza.

L’algoritmo è quindi costituito da un ciclo di due step che continua fino a che è possibile generare potenziali sequenze frequenti. Gli step sono

  1. generazione della lista di potenziali sequenze a partire dalla combinazione delle sequenze prodotte dal ciclo precedente
  2. puliza (pruning) della lista basata sul calcolo dell’effettiva frequenza.

Lo script ricalca questa metologia e presenta un ciclo e due funzioni.

Iniziamo quindi ad esaminare lo script:

from pprint import pprint

debug = False;
file = 'elenco.txt';
sep= ',';
minSup = 0.07;

a = open(file, 'r')
itemList = a.readlines()
a.close()

# used sorted for simplicity, so that same 2 items but in different order
# won't be added to 2-itemsets (i.e. Beer,Diaper and Diaper,Beed)
itemList = [sorted(item.rstrip('\n').split(sep)) for item in itemList]

Lo script legge i dati da un file denominato elenco.txt in cui ogni riga rappresenta una transazione e contiene una lista separata da virgole di elementi. Ad es:

farina,uova,latte,banana,patata,biscotto,cioccolatino
farina,uova,latte,biscotto,tavolino,cioccolatino
farina,uova,latte,patata,carne,cavolfiore

I dati sono inseriti, ordinati, in una lista di liste per le successive elaborazioni.

Prima di entrare nel ciclo vero e proprio eseguo separatamente i due step per il primo run; questo è infatti anomalo perché la lista di elementi da esaminare viene generata in modo speciale: si prendono tutte le sequenze di lunghezza uno non essendoci una sequenza precedente da cui partire.

elementList = generateNextItemsetList( [], itemList );

frequencies = FrequentElements( elementList, itemList , minSup );
pprint( frequencies );

Le due due funzioni che qui compaiono corrispondono esattamente ai due step dell’algoritmo:

generateNextItemsetList()

        : genera la lista di elementi da esaminare

FrequentElements( elementList, itemList , minSup )

      : verifica la frequenza degli elementi della lista

La prima funzione restituisce una lista di liste ognuna contenente una data sequenza

[
 ['latte', 'uova'],
 ['farina', 'latte'],
 ['codetta', 'farina']
]

mentre la seconda un dizionario che ha per chiave una stringa costruita con gli elementi della sequenza e per valore una lista con le frequenze assoluta e relativa della sequenza stessa

{
 'banana,biscotto': [2, 0.08333333333333333],
 'biscotto,cioccolatino': [2, 0.08333333333333333],
 'biscotto,farina': [3, 0.125]
}

Questa parte si conclude con la stampa della frequenza degli elementi interessanti. Per la stampa ho utilizzato la funzione pprint che restituisce un output un poco più leggibile per liste e dizionari.

Inizia poi il ciclo vero e proprio che non fa nulla di realmente differente:

while ( True ):
    elementList = [];
    for a in frequencies.keys():
        elementList.append( a.split(',') );
    if debug : print ( elementList );

    elementList = generateNextItemsetList( elementList, itemList, debug );
    if debug : print ( elementList );

    frequencies = FrequentElements( elementList, itemList , minSup );
    pprint( frequencies );
 
    if len( frequencies ) == 0:
        break;

Per prima cosa costruisco la lista degli elementi a partire dalle chiavi del dizionario generato nel ciclo precedente, genero poi la nuova lista di elementi da esaminare ed esamino infine la nuova lista.

Come accennato nella premessa, se la lista generata è vuota il ciclo is interrompe.

Esaminiamo ora in maggior dettaglio le due funzioni iniziando da def generateNextItemsetList( previousList = [], transactions = [] , debug = False ).

def generateNextItemsetList( previousList = [], transactions = [] , debug = False ):
    """ This function generates (k+1)-itemset candidates starting from k-itemset
        if the previousList is empty the function generates the 1-itemset
        The function requires a sorted list as input and generate a sorted list for a new call of this function
    """
    if debug: print( previousList );
    k = len(previousList);
    elements = [];
    # if the list is empty i generate all the possible 1-itemset
    if ( k == 0 ):
        for transaction in transactions:
            for element in transaction:
               try:
                   elements.index( [element] );
                   break;
               except:
                   elements.append( [element] );
    # if the itemset is not empty join as for apriori
    # yes else is part of the for cicle
    else:
        count = 0;
        for i in range( 0, k ):
            for j in range ( 0, i ):
                if (i != j):
                    for l in range ( 0, len(previousList[i])-1 ):
                        if ( previousList[i][l] != previousList[j][l] ):
                            break;
                    else:
                        elements.append( [] );
                        if debug : print( elements[count] );
                        if debug : print( previousList[i][0] );
                        for l in range ( 0, len(previousList[i])-1 ):
                            elements[count].append( previousList[i][l] );
                        elements[count].append( previousList[i][len(previousList[i])-1] );
                        elements[count].append( previousList[j][len(previousList[j])-1] );
                        elements[count] = sorted( elements[count] ); 
                        if debug : print( elements[count] );
                        count += 1;

    if debug : print( sorted(elements) );
    return sorted(elements);

Come già detto, questa funzione si occupa di generare la lista degli elementi che è utile esaminare. Lo fa in due modi differenti: se la lista delle sequenze del ciclo precedente è vuota, esamina la lista delle transazioni ed estrae tutti gli elementi singoli. Altrimenti accoppia tutte le sequenze che differiscono per un solo elemento e genera la sequenza che contiene l’unione degli elementi di queste due sottosequenze.

Ho usato qui il costrutto for … else…: in questo modo i comandi nel blocco dell’else vengono eseguiti se il ciclo for non viene interrotto. Ovvero solo se i primi n-1 elemnti sono uguali costruisco la stringa di lunghezza n+1.

La seconda funzione è def FrequentElements( elements = [], transactions = [], minSup = 0.5, debug = False ).

def FrequentElements( elements = [], transactions = [], minSup = 0.5, debug = False ):
    """ This function get as input the list of the element to be tested, the list of transactions and the values of minimun support.
        The function returns a dictionary that has as keys the frequent elements and values a list with the count and the support
    """
    frequencies = {};
    allFrequencies = {};
    label = '';
    numTransactions = len(transactions);

    # calculate frequencies
    for element in elements:
        if isinstance( element, str ):
            for transaction in transactions:
                try:
                    allFrequencies[ element ] += transaction.count( element );
                except:
                    allFrequencies[ element ] = transaction.count( element );
        else:
            label = '';
            for a in element:
                label += ','+a;

            label=label.lstrip(',');

            for transaction in transactions:
                flag = 0;
                for field in element:
                    if ( transaction.count( field ) == 0 ):
                        flag -= 1;
                        break;

                if flag >= 0:
                    try:
                        allFrequencies[ label ] += 1;
                    except:
                        allFrequencies[ label ] = 1;

    # purging dictionary
    for element in elements:
        if isinstance( element, str ):
            if allFrequencies[ element ] / numTransactions >= minSup:
                frequencies[ element ] = [ allFrequencies[ element ], allFrequencies[ element ] / numTransactions ];
        else:
            label = '';
            for a in element:
                label += ','+a;

            label=label.lstrip(',');

            if label in allFrequencies and allFrequencies[ label ] / numTransactions >= minSup:
                frequencies[ label ] = [ allFrequencies[ label ], allFrequencies[ label ] / numTransactions ];

    return frequencies;

In questa funzione ci sono due parti: per prima cosa vengono contate le occorrenze delle sequenze in esame e come secondo step vengono selezionate le sequenze sufficientemente frequenti.

In entrambi gli step vengono considerati due casi: un primo passaggio in cui l’elemento della lista è una stringa ed i cicli successivi in cui l’elemento della lista esterna è anch’esso una lista.

E’ interessante notare che la frequenza viene determinata confrontando ogni elemento della lista di sequenze con ogni elemento della lista delle transazioni. Io ho eseguito i cicli in questo ordine: nel caso la lista delle transazioni fosse stata così grande da non poter essere mantenuta in memoria sarebbe stato conveniente invertire i due cicli in modo da dover leggere le transazioni da disco una volta sola (per una data lunghezza delle sequenze). In altre parole sarebbe convenuto prendere una transazione alla volta e incrementare dei contatori associati alle sequenze presenti.

Questa considerazione mette in evidenza uno dei limiti più importanti dell’ apriori method: richiede inevitabilmente molti “sequential scan” della lista delle transazioni: operazione che può essere molto costosa nel caso sia necessario mantenere la lista su disco.

Altro limite importante che deriva dall’effettuare la Pattern Discovery con l’Apriori Method è che la lista delle sequenze da esaminare, può essere, in determinate condizioni, estremamente lunga. Si pensi ad esempio al caso in cui esistono sequenze interessanti di centinaia o migliaia di elementi: ogni sottosequenza è potenzialmente interessante e il numero di sottosequenze non ordinate di una sequnza di lunghezza m è (2^m-1); un numero che diventa presto enorme.

Il codice di questo script può essere recuperato all’indirizzo https://github.com/grimli/pattern_discovery.

Gestione dei Log con syslog

Una necessità primaria dei sistemi di produzione è la raccolta e la gestione dei log.

Sempre di più i log vengono generati in enorme quantità e quando l’infrastruttura cresce oltre un certo livello diventa fondamentale passare ad un sistema che ne gestisca la centralizzazione.

Su Linux generalmente si usa una qualche versione del demone syslog (su ubuntu ad esempio ci sono tre opzioni dsyslog, rsyslog, syslog-ng) a questo scopo. Questi sistemi si occupano sia della gestione locale dei log sia della loro eventuale centralizzazione e mettono a disposizione strumenti per filtrare le informazioni più importanti o per integrarsi con sistemi di monitoraggio come nagios o con sistemi di reportistica come logstash. La scelta di un file come repository finale dei dati non è obbligata ma questi sistemi permettono di passare i dati a molti altri tipi di repository.

Farò riferimento per i dettagli a syslog-ng.

Conviene immaginare questi sistemi come a gestori di flussi di informazioni nei quali ci sono dei punti di entrata (un server apache ad esempio), delle regole di elaborazione più o meno complesse e dei punti di uscita (tipicamente un file, altri server syslog nei sistemi centralizzati, database etc..). La configurazione rispecchia questa prospettiva.

Una volta definiti delle opzioni generali si definisco le sorgenti dei log. Questa ad esempio raccoglie le informazioni che tipicamente finiscono sui log standard di sistema.

source s_src { unix-dgram("/dev/log"); internal();
             file("/proc/kmsg" program_override("kernel"));
};

Altre tipiche sorgenti di dati saranno delle porte in ascolto su protocolli udp o tcp

source s_udp_apache {
        udp(ip(0.0.0.0) port(8515));
};
source s_tcp_apache {
        tcp(ip(0.0.0.0) port(8515));
};

utili sia per la costruzione di sistemi gerarchici che permettano la centralizzazione dei log sia come sistema semplice per separare su molti canali i log.
Tra le possibili sorgenti ci sono anche i file

source s_apache_access {file("/var/log/apache2/access.log" log_fetch_limit(100) log_iw_size(1000)); };

utili ad esempio per raccogliere i log anche di sistemi che hanno solo questa.

Il secondo elemento chiave della configurazione sono le destinazioni dei flussi di log. Anche in questo caso è possibile inviare i log su di un file locale, su un canale tcp o udp nel caso di sistemi gerarchici per la gestione di log.

destination d_auth { file("/var/log/auth.log"); };
destination d_udp_system { udp(vip-syslog.de.prod port(8514));};
destination d_tcp_system { tcp(vip-syslog.de.prod port(8514));};

Ci sono molte possibili altre destinazioni tra cui stream unix, o mongodb.

Il terzo elemento della configurazione è filter. Come il nome lascia intuire questo elemento serve a definire delle regole per selezionare un sottoinsieme dellerighe in arrivo. L’elemento tradizionale per suddividere i log è la selezione della facility, ma filter permette di agire su svariati elementi tra cui l’host di invio, il livello del messggio (notice, warn, error…) appositi tag assegnati alla riga di log o anche regular expression sul contenuto.

filter f_err { level(err); };
filter f_mail { facility(mail) and not filter(f_debug); };

I vari elementi della configurazione devono essere poi combinati con un’ultimo elemento della configurazione:

log { source(s_src); filter(f_auth); destination(d_auth); };
log { source(s_apache_extranet); destination(d_apache_extranet); flags(flow_control); };

La combinazione di questi elementi permette una grande flessibilità nella gestione del log. Tornerò su questo tema per approfondirne il filtraggio ed altre opzioni.