Regole di associazione

metodi per estrarre relazioni nascoste tra i dati

Nel data mining, le regole di associazione sono uno dei metodi per estrarre relazioni nascoste tra i dati.

Agrawal et al.[1] introdussero le regole di associazione per la scoperta di regolarità all'interno delle transazioni registrate nelle vendite dei supermercati. Per esempio, la regola individuata nell'analisi degli scontrini di un supermercato indica che il se il cliente compra insieme cipolle e patate è probabile che acquisti anche della carne per hamburger. Tale informazione può essere utilizzata come base per le decisioni riguardanti le attività di marketing, come ad esempio le offerte promozionali o il posizionamento dei prodotti negli scaffali. Le regole di associazione sono anche usate in molte altre aree, quali il Web mining, la scoperta di anomalie e la bioinformatica.

Il concetto di regola di associazione divenne popolare a causa di un articolo del 1993 di Agrawal et al.[1]. Secondo Google Scholar esso possiede più di 9500 citazioni (Settembre 2010) ed è uno degli articoli più citati nel campo del data mining. Tuttavia è possibile che quella che viene chiamata come regola di associazione sia simile a un approccio di data mining presentato nel 1966[2] e sviluppato da Hájek et al.[3].

Definizione

modifica
Esempio di base di dati con 4 oggetti e 5 transazioni
ID latte pane burro birra
1 1 1 0 0
2 0 0 1 0
3 0 0 0 1
4 1 1 1 0
5 0 1 0 0

Seguendo la definizione originale di Agrawal et al.[1] il problema della scoperta di regole di associazione è rappresentato come segue. Consideriamo l'insieme di   attributi binari (oggetti o item)   e l'insieme di transazioni (database) . Ciascuna transazione appartenente a   possiede un codice identificativo (ID) e contiene un sottoinsieme degli oggetti contenuti in  . Una regola è definita come un'implicazione nella forma   dove   e  . L'insieme di oggetti (o itemsets)   e   vengono chiamati rispettivamente antecedente e conseguente della regola.

Per illustrare questo concetto, è possibile usare un esempio giocattolo riguardante un supermercato. L'insieme di oggetti è   e il database contenente gli oggetti è rappresentato nella tabella a destra, dove 1 indica la presenza di un oggetto in una transazione e 0 l'assenza. Un esempio di regola di associazione potrebbe essere:  . Essa indica che se il cliente acquista pane e burro, comprerà anche il latte.

Attenzione: questo esempio è estremamente piccolo. In un'applicazione reale una regola necessita di un supporto di diverse centinaia di transazioni perché sia considerata statisticamente significativa e il database deve contenere migliaia (o milioni) di transazioni.

  1. ^ a b c R. Agrawal; T. Imielinski; A. Swami: Mining Association Rules Between Sets of Items in Large Databases, SIGMOD Conference 1993: 207-216
  2. ^ Hajek P., Havel I., Chytil M.: The GUHA method of automatic hypotheses determination, Computing 1(1966) 293-308.
  3. ^ Petr Hajek, Tomas Feglar, Jan Rauch, David Coufal. The GUHA method, data preprocessing and mining. Database Support for Data Mining Applications, ISBN 978-3-540-22479-2, Springer, 2004

Altri progetti

modifica
  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica