Regole di associazione

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

Agrawal et al. introdussero le regole di associazione per la scoperta di regolarità all'interno delle transazioni registrate nelle vendite dei supermercati. Per esempio, la regola $\{\mathrm{c}\mathrm{i}\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{l}\mathrm{e},\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{e}\}\Rightarrow \{\mathrm{h}\mathrm{a}\mathrm{m}\mathrm{b}\mathrm{u}\mathrm{r}\mathrm{g}\mathrm{e}\mathrm{r}\}$ 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

Il concetto di regola di associazione divenne popolare a causa di un articolo del 1993 di Agrawal et al.. 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 e sviluppato da Hájek et al..

Definizione

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. 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,\dots ,i_n\}$ e l'insieme di transazioni (database)$D=\{t_1,t_2,\dots ,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=\mathrm{\varnothing }$. L'insieme di oggetti (o itemsets) $X$ e $Y$ vengono chiamati rispettivamente antecedente e conseguente della regola.

Per illustrare questo concetto, è possibile usare un esempio giocattolo riguardante un supermercato. L'insieme di oggetti è $I=\{\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e},\mathrm{p}\mathrm{a}\mathrm{n}\mathrm{e},\mathrm{b}\mathrm{u}\mathrm{r}\mathrm{r}\mathrm{o},\mathrm{b}\mathrm{i}\mathrm{r}\mathrm{r}\mathrm{a}\}$ 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{b}\mathrm{u}\mathrm{r}\mathrm{r}\mathrm{o},\mathrm{p}\mathrm{a}\mathrm{n}\mathrm{e}\}\Rightarrow \{\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\}$. 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.