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.Piatetsky-Shapiro, Gregory (1991), Discovery, analysis, and presentation of strong rules, in Piatetsky-Shapiro, Gregory; and Frawley, William J.; eds., Knowledge Discovery in Databases, AAAI/MIT Press, Cambridge, MA. 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.

 Definisjon 
+ Eksempeldatabase med 4 objector og 5 transaksjoner transaksjons ID  melk  baguette  margarin  cider 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 

I den opprinnelige definisjonen til Agrawal et al., defineres problemet i assosiasjonsregellæring slik: La  være et sett av  binære attributter med navn objekter. La  være et sett av transaksjoner med navn database. Hver enkelt transaksjon i  har en unik transaksjons-ID, og inneholder en undergruppe av elementene i . En regel defineres ved formelen  der  og . Settene av elementene (forkortes elementsettene)  og  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 , 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 , 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)  til et elementsett  er definert som mengden av transaksjoner i datasettet som inneholder elementsettet. I eksempeldatabasen har elementsettet  en støtte på , siden settet forekommer i 20 % av alle transaksjoner (1 av 5 transaksjoner).
 Tryggheten (confidence) til en regel defineres som: . For eksempel så har regelen  en trygghet på  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:  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  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 , sannsynligheten for å finne HS av regelen i transaksjoner under betingelsen av at disse transaksjonen også inneholder VS.
 Avvik (lift) til en regel defineres som  eller forholdet til den observerte støtten til det som forventes hvis X og Y var uavhengige. Regelen  har et avvik på .
 En regels overbevisning (conviction) defineres som . Regelen  har en overbevisning på , 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  ville vært feil 20 % oftere (1.2 ganger så ofte), dersom assosiasjonen mellom X og Y var utelukkende tilfeldig.

 Prosess 
 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  og har størrelsen  (eksludert det tomme settet som ikke er et gyldig elementsett). Selv om størrelsen på potensmengden vokser eksponensielt i antall element  i , så er effektive søk mulig ved hjelp av støttens downward-closure property of support (også kalt anti-monotoniPei, Jian; Han, Jiawei; and Lakshmanan, Laks V. S.; Mining frequent itemsets with convertible constraints, in Proceedings of the 17th International Conference on Data Engineering, April 2–6, 2001, Heidelberg, Germany, 2001, pages 433-442) 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., AprioriAgrawal, Rakesh; and Srikant, Ramakrishnan; Fast algorithms for mining association rules in large databases , in Bocca, Jorge B.; Jarke, Matthias; and Zaniolo, Carlo; editors, Proceedings of the 20th International Conference on Very Large Data Bases (VLDB), Santiago, Chile, September 1994, pages 487-499 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 1966Hájek, Petr; Havel, Ivan; Chytil, Metoděj; The GUHA method of automatic hypotheses determination, Computing 1 (1966) 293-308 på GUHA, som er en generell data mining metode utviklet av Petr Hájek et al.Hájek, Petr; Feglar, Tomas; Rauch, Jan; and Coufal, David; The GUHA method, data preprocessing and mining, Database Support for Data Mining Applications, Springer, 2004, ISBN 978-3-540-22479-2

 Alternative kriterier for interesse 

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

 Total trygghetOmiecinski, Edward R.; Alternative interest measures for mining associations in databases, IEEE Transactions on Knowledge and Data Engineering, 15(1):57-69, Jan/Feb 2003
 Kollektiv styrkeAggarwal, Charu C.; and Yu, Philip S.; A new framework for itemset generation, in PODS 98, Symposium on Principles of Database Systems, Seattle, WA, USA, 1998, pages 18-24
 OverbevisningBrin, Sergey; Motwani, Rajeev; Ullman, Jeffrey D.; and Tsur, Shalom; Dynamic itemset counting and implication rules for market basket data, in SIGMOD 1997, Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD 1997), Tucson, Arizona, USA, May 1997, pp. 255-264
 “Leverage”Piatetsky-Shapiro, Gregory; Discovery, analysis, and presentation of strong rules, Knowledge Discovery in Databases, 1991, pp. 229-248
 “Lift” (originalt kalt interesse)Brin, Sergey; Motwani, Rajeev; Ullman, Jeffrey D.; and Tsur, Shalom; Dynamic itemset counting and implication rules for market basket data, in SIGMOD 1997, Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD 1997), Tucson, Arizona, USA, May 1997, pp. 265-276

En definisjon av disse kriteriene finnes her . Flere kriterier blir presentert og sammenligne av Tan et al.Tan, Pang-Ning; Kumar, Vipin; and Srivastava, Jaideep; Selecting the right objective measure for association analysis, Information Systems, 29(4):293-313, 2004 Å 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

Kategori:Informatikk