Regole di associazione

Da Wikipedia, l'enciclopedia libera.

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 \{\mathrm{cipolle, patate}\} \Rightarrow \{\mathrm{hamburger}\} 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.

Storia[modifica | modifica wikitesto]

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 | modifica wikitesto]

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 n attributi binari (oggetti o item) I=\{i_1, i_2,\ldots,i_n\} e l'insieme di transazioni (database)D = \{t_1, t_2, \ldots, t_m\}. Ciascuna transazione appartenente a D possiede un codice identificativo (ID) e contiene un sottoinsieme degli oggetti contenuti in I. Una regola è definita come un'implicazione nella forma X \Rightarrow Y dove X, Y \subseteq I e X \cap Y = \emptyset. L'insieme di oggetti (o itemsets) X e Y vengono chiamati rispettivamente antecendente e conseguente della regola.

Per illustrare questo concetto, è possibile usare un esempio giocattolo riguardante un supermercato. L'insieme di oggetti è I= \{\mathrm{latte, pane, burro, birra}\} 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: \{\mathrm{burro, pane}\} \Rightarrow \{\mathrm{latte}\}. 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.

Note[modifica | modifica wikitesto]

  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
informatica Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica