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.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *