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  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.

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.

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.