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.^[1] Basert på konseptet om sterke regler, introduserte Rakesh Agrawal et al.^[2] 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

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 $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.^[3]
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

Hyppig elementsett rutenett, der fargen på boksen indikerer hvor mange transaksjoner inneholder en kombinasjon av elementer. Vær oppmerksom på at lavere nivåer av rutenettet kan inneholde maksimalt det minste antallet av foreldrenes elementer; for eksempel ac} kan bare maksimalt ha $min(a,c)$ items. Dette kalles *downward-closure property*.^[2]

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^[2]^[4] (også kalt anti-monotoni^[5]) 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^[6] og Eclat^[7]) kan finne alle hyppige elementsett.

Historie

Konseptet om assosiasjonsregler ble populært særlig på grunn av artikkelen til Agrawal et al.,^[2] 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^[8] på GUHA, som er en generell data mining metode utviklet av Petr Hájek et al.^[9]

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^[10]
Kollektiv styrke^[11]
Overbevisning^[12]
“Leverage”^[13]
“Lift” (originalt kalt interesse)^[14]

En definisjon av disse kriteriene finnes her Arkivert 2. august 2018 hos Wayback Machine.. Flere kriterier blir presentert og sammenligne av Tan et al.^[15] Å 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^[6] 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^[7] (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å

Referanser

^ 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.
^ ^a ^b ^c ^d Rakesh Agrawal; Tomasz Imieliński; Arun Swami (1993). «Mining association rules between sets of items in large databases». ACM SIGMOD. 22 (2): 207–216. doi:10.1145/170035.170072.
^ Jochen Hipp; Ulrich Güntzer; Gholamreza Nakhaeizadeh (2000). «Algorithms for association rule mining — a general survey and comparison». ACM SIGKDD Explorations Newsletter. 2 (1): 58–64. doi:10.1145/360402.360421.
^ Tan, Pang-Ning; Michael, Steinbach; Kumar, Vipin (2005). «Chapter 6. Association Analysis: Basic Concepts and Algorithms» (PDF). Introduction to Data Mining. Addison-Wesley. ISBN 0-321-32136-7.
^ Pei, 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
^ ^a ^b Agrawal, Rakesh; and Srikant, Ramakrishnan; Fast algorithms for mining association rules in large databases Arkivert 25. februar 2015 hos Wayback Machine., 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
^ ^a ^b M.J. Zaki (2000). «Scalable algorithms for association mining». IEEE Transactions on Knowledge and Data Engineering. 12 (3): 372 – 390. doi:10.1109/69.846291.
^ Hájek, Petr; Havel, Ivan; Chytil, Metoděj; The GUHA method of automatic hypotheses determination, Computing 1 (1966) 293-308
^ 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
^ Omiecinski, Edward R.; Alternative interest measures for mining associations in databases, IEEE Transactions on Knowledge and Data Engineering, 15(1):57-69, Jan/Feb 2003
^ Aggarwal, 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
^ 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. 255-264
^ Piatetsky-Shapiro, Gregory; Discovery, analysis, and presentation of strong rules, Knowledge Discovery in Databases, 1991, pp. 229-248
^ 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
^ Tan, Pang-Ning; Kumar, Vipin; and Srivastava, Jaideep; Selecting the right objective measure for association analysis, Information Systems, 29(4):293-313, 2004

Autoritetsdata

[piatetsky-1] 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.

[mining-2] Rakesh Agrawal; Tomasz Imieliński; Arun Swami (1993). «Mining association rules between sets of items in large databases». ACM SIGMOD. 22 (2): 207–216. doi:10.1145/170035.170072.

[hipp-3] Jochen Hipp; Ulrich Güntzer; Gholamreza Nakhaeizadeh (2000). «Algorithms for association rule mining — a general survey and comparison». ACM SIGKDD Explorations Newsletter. 2 (1): 58–64. doi:10.1145/360402.360421.

[4] Tan, Pang-Ning; Michael, Steinbach; Kumar, Vipin (2005). «Chapter 6. Association Analysis: Basic Concepts and Algorithms» (PDF). Introduction to Data Mining. Addison-Wesley. ISBN 0-321-32136-7.

[pei-5] Pei, 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

[apriori-6] Agrawal, Rakesh; and Srikant, Ramakrishnan; Fast algorithms for mining association rules in large databases Arkivert 25. februar 2015 hos Wayback Machine., 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

[eclat-7] M.J. Zaki (2000). «Scalable algorithms for association mining». IEEE Transactions on Knowledge and Data Engineering. 12 (3): 372 – 390. doi:10.1109/69.846291.

[guha_oldest-8] Hájek, Petr; Havel, Ivan; Chytil, Metoděj; The GUHA method of automatic hypotheses determination, Computing 1 (1966) 293-308

[pospaper-9] 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

[allconfidence-10] Omiecinski, Edward R.; Alternative interest measures for mining associations in databases, IEEE Transactions on Knowledge and Data Engineering, 15(1):57-69, Jan/Feb 2003

[collectivestrength-11] Aggarwal, 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

[brin-dynamic-itemset1-12] 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. 255-264

[leverage-13] Piatetsky-Shapiro, Gregory; Discovery, analysis, and presentation of strong rules, Knowledge Discovery in Databases, 1991, pp. 229-248

[brin-dynamic-itemset2-14] 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

[measurescomp-15] Tan, Pang-Ning; Kumar, Vipin; and Srivastava, Jaideep; Selecting the right objective measure for association analysis, Information Systems, 29(4):293-313, 2004

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]