Foreningsregel

Innen datautvinning er søket etter assosieringsregler en populær metode studert i dybden, og målet er å oppdage relasjoner av interesse for statistikeren mellom to eller flere variabler lagret i veldig store databaser . Piatetsky-Shapiro presenterer ekstremt sterke assosieringsregler oppdaget i databaser ved hjelp av forskjellige mål av interesse. Basert på konseptet med sterke relasjoner, presenterer Rakesh Agrawal og hans team tilknytningsregler som har til hensikt å avdekke likheter mellom produkter i data som er lagt inn i stor skala i IT-systemene for kjedeprodukter. For eksempel kan en regel oppdaget i salgsdata i et supermarked indikere at en kunde som kjøper løk og poteter samtidig, sannsynligvis vil kjøpe en hamburger. Slik informasjon kan brukes som grunnlag for å ta markedsføringsbeslutninger som for eksempel kampanjer eller velvalgte steder for tilknyttede produkter. I tillegg til de ovennevnte eksemplene på forbrukerkurven, brukes foreningsregler i dag på mange områder, inkludert nettdrift , innbruddsdeteksjon og bioinformatikk .

Historie

Konseptet med assosiasjonsregel ble popularisert, særlig av en artikkel av Rakesh Agrawal fra 1993. Men det er mulig at denne oppfatningen ble oppdaget under navnet GUHA i 1966 av Petr Hájek og hans kolleger.

Prinsipper

Definisjon

En assosieringsregel kan formelt defineres slik:

Definisjon : Vurder et sett med indekser ( varer ) og et sett med transaksjoner, slike som inneholder et delsett av (dvs. ). En assosieringsregel, som kan være sann eller usann, uttrykkes i form: ${\ displaystyle \ mathrm {I} = \ left \ {i_ {1}, i_ {2}, ..., i_ {m} \ right \}}$ ${\ displaystyle \ mathrm {T} = \ left \ {t_ {1}, t_ {2}, ..., t_ {n} \ right \}}$ $t_i$ $\ Iota$ ${\ displaystyle t_ {i} \ supseteq \ mathrm {I}}$

\ Chi \ høyre pil Y

, hvor og

{\ displaystyle \ mathrm {X} \ in \ mathrm {T}, ~ Y \ in \ mathrm {T},}

{\ displaystyle \ mathrm {X} \ cap Y \ neq \ emptyset}

Nyttige forestillinger

For et delsett av indekser (kalt itemset ): $X$ ${\ displaystyle X \ subseteq \ mathrm {I}}$

Recovery eller dekselet (i ) er settet av transaksjoner observert inneholdende : . $X$ $T$ $X$ ${\ displaystyle \ mathrm {K} _ {T} {\ bigl (} X {\ bigr)} = \ left \ {k = {1,2, .. n} | X \ subseteq t_ {k} \ right \ }}$

Legg merke til det , som gjenspeiler det faktum at hvis og bare hvis og . ${\ displaystyle \ mathrm {K} _ {T} {\ bigl (} X \ cup Y {\ bigr)} = \ mathrm {K} _ {T} {\ bigl (} X {\ bigr)} \ cap \ mathrm {K} _ {T} {\ bigl (} Y {\ bigr)}}$ ${\ displaystyle X \ cup Y \ subseteq t}$ ${\ displaystyle X \ subseteq t}$ ${\ displaystyle Y \ subseteq t}$

Støttetelleren ( " count carrier " ) av in er antall transaksjoner som inneholder . Vi merker det . $\ Chi$ $\ mathrm {T}$ $\ mathrm {T}$ $\ Chi$ ${\ displaystyle \ mathrm {X} .count = | \ mathrm {K} _ {\ mathrm {T}} {\ bigl (} \ mathrm {X} {\ bigr)} |}$
Bæreren ( “ support ” ) er da andelen av beholder transaksjoner , dvs . Dette kan sees på som et estimat på sannsynligheten . $\ mathrm {T}$ $\ Chi$ ${\ displaystyle Supp (\ mathrm {X}) = {\ frac {\ mathrm {X} .count} {Card (\ mathrm {T})}}}$ ${\ displaystyle \ Pr (\ mathrm {X})}$
Styrken til en assosiasjonsregel måles av støtteindeksen og tillitsindeksen.
- Bæreren indeks ( " support " ) av en regel er definert av den andel av transaksjoner som inneholder ( både X og Y , ikke X eller Y), dvs . Det er derfor et estimat av sannsynligheten . $\ Chi \ høyre pil Y$ $\ mathrm {T}$ ${\ displaystyle \ mathrm {X} \ cap Y}$ ${\ displaystyle Supp (\ mathrm {X} \ cap Y)}$ ${\ displaystyle \ Pr (\ mathrm {X} \ cap Y)}$
- Tillitsindeksen ( " hemmelighet " ) til en regel er definert av andelen transaksjoner som inneholder som også inneholder en av dem . Det kan sees på som et estimat av den betingede sannsynligheten . Merk: . $\ Chi \ høyre pil Y$ $\ mathrm {T}$ $\ Chi$ $Y$ ${\ displaystyle {\ frac {(\ mathrm {X} \ cap Y) .count} {\ mathrm {X} .count}}}$ ${\ displaystyle \ Pr (Y | \ mathrm {X})}$ ${\ displaystyle Conf (\ mathrm {X} \ rightarrow Y) = {\ frac {Supp (\ mathrm {X} \ cap Y)} {Supp (\ mathrm {X})}}}$
Den “ løft ” av en regel måler forbedring brakt ved foreningen regelen sammenlignet med et sett av tilfeldige transaksjoner (hvor X og Y vil være uavhengig). Det er definert av . Et “ løft ” større enn 1 gjenspeiler en positiv korrelasjon mellom X og Y, og derfor den vesentlige karakteren av foreningen. $\ Chi \ høyre pil Y$ ${\ displaystyle {\ frac {Supp (\ mathrm {X} \ cap Y)} {Supp (\ mathrm {X}) .Supp (Y)}}}$

Algoritmer

Apriori

KRAV: En terskelstøtte S

SIKRER: Listen over hyppige varesett

L1 ‹- Liste over gjenstander der støtten er større enn S; i ‹- i + 1;

GJENTA

i ‹— 1; À partir des Li-1, construire l'ensemble Ci des itemsets fréquents, candidats comprenant i items ; Li ‹— {}; POUR tout élément e € Ci FAIRE SI support(e) > S ALORS ajouter e à Li; FINSI FINPOUR

TIL L1 == {}

Stråling

Eclat er en assosiasjonsalgoritme som bruker skjæringspunktet mellom sett.

FP-vekst

FP-vekst (hyppig mønstervekst) bruker et FP-tre for å lagre en komprimert form av en database. FP-growth vedtar en skjæringsstrategi for å bryte ned data mining og databaseoppgaver . Det bruker en " mønsterfragmentvekst " -metode for å unngå den kostbare kandidatgenererings- og testprosessen som brukes av Apriori.

GUHA-prosedyre ASSOC

GUHA ( " General Unary Hypotheses Automaton " ) er en metode for automatisk å generere hypoteser fra empiriske data, så det er en metode for data mining. Prosedyren er en ASSOC GUHA-metode som utforsker dataene for raskt å finne generaliserte tilknytningsregler ved hjelp av array-datastrukturer ( " Array Bit " ).

En attributtregel

Ideen bak utformingen av OneR (one-attribute-rule) algoritmen er å finne et attributt å bruke som gir minst mulig prediksjonsfeil. Peter Ross oppdaget at enkle regler med bare ett attributt i tilstanden faktisk fungerer bra.

OPUS

OPUS er en effektiv algoritme for å finne tilknytningsregler, som, i motsetning til andre, ikke krever anti-monotone og monotone begrensninger som minimum støtte. Opprinnelig brukt til å finne regler for en gitt konklusjon, ble den senere utvidet til å finne regler med ethvert element som en konklusjon. OPUS-søkemotoren er den sentrale teknologien i det populære Magnum Opus assosiasjonssystemet .

Nullattributtregel

Se også

Merknader

(fr) Denne artikkelen er delvis eller helt hentet fra den engelske Wikipedia- artikkelen med tittelen " Association rule learning " ( se forfatterlisten ) .

Interne lenker

Referanser

Piatetsky-Shapiro, G. (1991), Discovery, analyse og presentasjon av sterke regler, i G. Piatetsky-Shapiro & WJ Frawley, red., 'Knowledge Discovery in Databases', AAAI / MIT Press, Cambridge, MA.
R. Agrawal; T. Imielinski; A. Swami: Mining Association Rules Between Sets of Items in Large Databases ", SIGMOD Conference 1993: 207-216
Petr Hajek, Tomas Feglar, Jan Rauch, David Coufal. GUHA-metoden, databehandling og gruvedrift. Database Support for Data Mining Applications, ( ISBN 978-3-540-22479-2 ) , Springer, 2004
Gurmeet Singh Manku, Rajeev Motwani , tilnærmet frekvens teller over datastrømmer
Bing Liu, Web Data Mining, Springer, 2010-utgave, Side 14
Mohammed J. Zaki. Skalerbare algoritmer for tilknytningsgruvedrift. IEEE Transactions on Knowledge and Data Engineering 12 (3): 372-390, mai / juni 2000.
Jiawei Han, Jian Pei, Yiwen Yin og Runying Mao. Gruvedrift hyppige mønstre uten kandidatgenerering. Data Mining and Knowledge Discovery 8: 53-87, 2004.
GUHA GUHA - grunnleggende informasjon Offisielt nettsted
P. Hájek, P. Havranek mekanisere Hypotese Formation - Matematiske Foundations for en generell teori, Springer-Verlag, Edition 1978, ( ISBN 0387087389 )
Peter Ross, oner: den enkleste metoden
Webb, GI (1995). OPUS: En effektiv tillatt algoritme for uordnet søk. Journal of Artificial Intelligence Research 3. Menlo Park, CA: AAAI Press, sider 431-465 online tilgang .
RJ Bayardo , R. Agrawal og D. Gunopulos , “ Constraint basert regel gruvedrift i store, tette databaser ”, Data Mining og Knowledge Discovery , vol. 4, n o to2000, s. 217–240 ( DOI 10.1023 / A: 1009895914772 )
Webb, GI (2000). Effektiv søk etter foreningsregler. I R. Ramakrishnan og S. Stolfo (red.), Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2000) Boston, MA. New York: Association for Computing Machinery, side 99-107. online tilgang