Assosiasjonsregler

**Assosiasjonsregler** er en populær og grundig analysert metode for å oppdage interessante relasjoner mellom variabler i store databaser. Hensikten er å identifisere sterke regler oppdaget i databaser ved å bruke forskjellige kriter for grader av interesse. Basert på konseptet om sterke regler, introduserte Rakesh Agrawal et al. assosiasjonsregler for å oppdage sammenhenger mellom produkter i storstilte transaksjonsdata registrert i “point-of-sale” (POS)-systemer i dagligvarebutikker. For eksempel, regelen \{\mathrm{salat, poteter}\} \Rightarrow \{\mathrm{hamburger}\} funnet i salgsdataene til en dagligvarebutikk ville indikere at hvis en kunde kjøper både salat og poteter, vil kunden sannsynligvis også kjøpe hamburgerkjøtt. Slik informasjon kan bli brukt som et grunnlag for avgjørelser innen markedføringsaktiviteter som for eksempel, kampanjepriser eller produktplassering. I tillegg til eksempelet fra markedsanalyser så er assosiasjonsregler benyttet i mange applikasjonsområder som Web Usage Mining, intrusion detection, Continuous production og bioinformatikk. I kontrast til sequence mining, tar ikke assosiasjonsregellæring hensyn til rekkefølgen til elementer enten innenfor transaksjoner eller på tvers av transaksjoner.

## Definisjon

I den opprinnelige definisjonen til Agrawal et al., defineres problemet i assosiasjonsregellæring slik: La I=\{i_1, i_2,\ldots,i_n\} være et sett av n binære attributter med navn *objekter*. La D = \{t_1, t_2, \ldots, t_m\} være et sett av transaksjoner med navn database. Hver enkelt transaksjon i D har en unik transaksjons-ID, og inneholder en undergruppe av elementene i I. En *regel* defineres ved formelen X \Rightarrow Y der X, Y \subseteq I og X \cap Y = \emptyset. Settene av elementene (forkortes elementsettene) X og Y kalles henholdsvis *antecedent* (venstresiden eller VS) og *konsekvensen* (høyresiden eller HS) av ligningen.

For å illustrere konseptet ved assosiasjonsregellæring kan vi se for oss et eksempel fra dagligvarehandelsbransjen. Elementsettet er I= \{\mathrm{melk, baguette, margarin, cider}\}, og en liten database som inneholder elementene (1 representerer tilstedeværelse og 0 fravær av et element i en transaksjon) vises i tabellen til høyre. Et eksempel kan på en regel kan være \{\mathrm{margarin, baguette}\} \Rightarrow \{\mathrm{melk}\}, som betyr at dersom kunden kjøper margarin og baguette, kjøper kunden også melk. NB: Dette eksempelet er veldig forenklet. Ved praktisk bruk av assosiasjonsregler trengs det støtte fra flere hundre transaksjoner før de kan vurderes som statistisk signifikante. I tillegg inneholder datasettene ofte flere tusen eller millioner slike transaksjoner.

## Nyttige konsepter
 
For å velge ut interessante regler fra sett av alle mulige regler, kan man sette begrensninger på ulike kriterier for signifikans og interesse. De mest kjente begrensningene er minimumsterskler for støtte (support) og trygghet (confidence).

* Støtten (support) \mathrm{supp}(X) til et elementsett X er definert som mengden av transaksjoner i datasettet som inneholder elementsettet. I eksempeldatabasen har elementsettet \{\mathrm{melk, baguette, margarin}\} en støtte på 1/5=0.2, siden settet forekommer i 20 % av alle transaksjoner (1 av 5 transaksjoner).
* Tryggheten (confidence) til en regel defineres som: \mathrm{conf}(X\Rightarrow Y) = \mathrm{supp}(X \cup Y) / \mathrm{supp}(X). For eksempel så har regelen \{\mathrm{margarin, baguette}\} \Rightarrow \{\mathrm{melk}\} en trygghet på 0.2/0.2=1.0 i databasen, som betyr at regelen er korrekt for 100 % av transaksjonene som inneholder margarin og baguette (i 100 % av tilfellene hvor en kunde kjøper margarin og baguette kjøpes det også melk). Når man leser uttrykket:  \mathrm{supp}(X \cup Y)  betyr det i dette tilfellet "støtte for forekomster av transaksjoner hvor **både X og Y inntreffer**, ikke "støtte for forekomster" av transaksjoner hvor **enten X eller Y inntreffer**. Den siste tolkningen oppstår fordi sett union er ekvivalent til disjunksjon (logical disjunction). Argumentet \mathrm{supp}() innebærer et sett av forhåndsbetingelser, og blir derfor mer restriktiv etterhvert som det vokser (istedenfor mer inkluderende).
* Trygghet kan tolkes som et estimat av sannsynligheten P(Y|X), sannsynligheten for å finne HS av regelen i transaksjoner under betingelsen av at disse transaksjonen også inneholder VS.
* Avvik (lift) til en regel defineres som  \mathrm{lift}(X\Rightarrow Y) = \frac{ \mathrm{supp}(X \cup Y)}{ \mathrm{supp}(X) \times \mathrm{supp}(Y) }  eller forholdet til den observerte støtten til det som forventes hvis X og Y var uavhengige. Regelen \{\mathrm{melk, baguette}\} \Rightarrow \{\mathrm{margarin}\} har et avvik på \frac{0.2}{0.4 \times 0.4} = 1.25 .
* En regels overbevisning (conviction) defineres som  \mathrm{conv}(X\Rightarrow Y) =\frac{ 1 - \mathrm{supp}(Y) }{ 1 - \mathrm{conf}(X\Rightarrow Y)}. Regelen \{\mathrm{melk, baguette}\} \Rightarrow \{\mathrm{margarin}\} har en overbevisning på \frac{1 - 0.4}{1 - .5} = 1.2 , og kan tolkes som raten til en forventet frekvens hvor X oppstår uten Y (det vil si, frekvensen for at regelen spår ukorrekte utfall) dersom X og Y var uavhengig delt av den observerende frekvensen av ukorrekte spådommer. I dette eksempelet, demonstrerer overbevisningsverdien 1.2 at regelen \{\mathrm{melk, baguette}\} \Rightarrow \{\mathrm{margarin}\} ville vært feil 20 % oftere (1.2 ganger så ofte), dersom assosiasjonen mellom X og Y var utelukkende tilfeldig.

## Prosess
 Association rules are usually required to satisfy a user-specified minimum support and a user-specified minimum confidence at the same time. Association rule generation is usually split up into two separate steps:
# First, minimum support is applied to find all *frequent itemsets* in a database.
# Second, these frequent itemsets and the minimum confidence constraint are used to form rules.
While the second step is straightforward, the first step needs more attention.

Assosiasjonsregler er vanligvis krevd for å tilfredsstille både en brukerspesifisert miniumumsstøtte og en brukerspesifisert minimumstrygghet. Assosiasjonsregel-generering blir vanligvis delt opp i to separerte steg: 
Minimumsstøtte er anvendt for å finne alle hyppige elementsett i en database.
Begrensningene i de hyppige elementsettene og minimumstryggheten blir brukt til å danne regler.

Mens det andre steget er ukomplisert, krever det første steget mer fokus. Å finne alle hyppige elementsett i en database er krevende siden det involverer søk i alle mulige elementsett (element kombinasjoner). Settet av mulige elementsett er potensmengden over I og har størrelsen 2^n-1 (eksludert det tomme settet som ikke er et gyldig elementsett). Selv om størrelsen på potensmengden vokser eksponensielt i antall element n i I, så er effektive søk mulig ved hjelp av støttens ***downward-closure property*** of support (også kalt *anti-monotoni*) som garanterer at for et hyppig elementsett, så er alle undergruppene også hyppige og dermed for et sjeldent elementsett, må alle undergrupper være sjeldne. Ved å utnytte denne egenskapen, effektive algoritmer (f.eks., Apriori og Eclat) kan finne alle hyppige elementsett.

## Historie

Konseptet om assosiasjonsregler ble populært særlig på grunn av artikkelen til Agrawal et al., som har fått nesten 15000 siteringer ifølge Google Schoolar, i november 2014, og er dermed en av de mest siterte artiklene i Data Mining feltet. Imidlertid er det mulig at det som nå blir kalt assosiasjonsregler er tilnærmet likt det som forekommer i artikkelen fra 1966 på GUHA, som er en generell data mining metode utviklet av Petr Hájek et al.

## Alternative kriterier for interesse

I tillegg til trygghet, har andre kriterier for grad av interesse for regler blitt foreslått. 
Poulære kriterier:

* Total trygghet
* Kollektiv styrke
* Overbevisning
* “Leverage”
* “Lift” (originalt kalt interesse)

En definisjon av disse kriteriene finnes her . Flere kriterier blir presentert og sammenligne av Tan et al. Å lete etter teknikker som kan modellere hva brukeren har visst (og bruke disse modellene som kriterier for interesse) er for tiden en aktiv forskningstrend under navnet "Subjective Interestingness."

## Statistisk solide/velbegrunnede assosiasjoner

En begrensning i standardmetoden for å oppdage assosiasjoner, er at ved å søke i massive antall av mulige assosiasjoner for å se etter samlinger av elementer som fremstår assosierte, er det en stor risiko for å finne mange spuriøse assosiasjoner. Dette er samlinger av elementer som gjenoppstår med uventet frekvens i dataene, men bare ved tilfeldighet. For eksempel hvis vi ser for oss en samling av 10,000 elementer og søker etter regler som har to elementer på venstresiden og et element på høyresiden. Det finnes anslagsvis 1,000,000,000,000 slike regler. Hvis vi foretar en statistisk uavhengighetstest med et signifikansnivå på 0.05 så betyr det at det bare er 5% sjanse for å aksepterer en regel hvis det ikke er noen assosiasjon. Hvis vi antar at det ikke er noen assosiasjon, må vi likevel forvente å finne 50,000,000,000 regler. Statistisk velbegrunnede assosiasjonsoppdagelse kontrollerer denne risikoen, og i de fleste tilfeller reduseres risikoen for å finne spuriøse assosiasjoner til et bruker-spesifisert signifikansnivå.

## Algoritmer

Mange algoritmer for generering av assosiasjonsregler har blitt presentert opp i gjennom tidene. Velkjente algoritmer som Apriori, Eclat og FP-Growth, gjør bare halve jobben, ettersom de er algoritmer for utvinning av hyppige elementsett. Et ytterlige steg kreves etter for å generere regler fra hyppige elementsett funnet i en database.

### Apriori algoritme

Apriori er den mest velkjente algoritmen for utvinning av assosiasjonsregler. Den bruker en “breadth-first”-søkestrategi for å telle støtten til elementsett og bruker en kandidat-genereringsfunksjon som utnytter “downward closure property of support”.

### Eclat algorithm

Eclat (står for Equivalence Class Transformation) er en “depth-first”-søkealgoritme som bruker elementsett-krysning.

### Andre algoritmer

Andre algoritmer:

* FP-growth algorithm
* AprioriDP
* Context Based Association Rule Mining Algorithm
* Node-set-based algorithms
* GUHA procedure ASSOC
* OPUS search

## Se også
* Maskinlæring
* Kunstig intelligens

## Referanser