Učenje pravilom asocijacije

U traženju podataka učenje pravilom asocijacije je popularan i dobro istražen metod za otkrivanje interesantnih odnosa između promenljivih u velikim bazama podataka. Namenjeno je pronalaženju jakih zakona otkrivenim u bazama podataka korišćenjem različitih mera interesantnosti. Zasnovano na konceptu jakih zakona, Rakeš Agraval et al. (Rakesh Agrawal et al.) je uveo pravila asocijacije za otkrivanje regularnosti između produkata u transakcijama podataka velikih razmera zabeleženih od strane mesta prodaje (POS) sistema u supermarketima. Na primer, pravilo $\{\mathrm {luk,krompir} \}\Rightarrow \{\mathrm {pljeskavica} \}$ nađeno u podacima o prodaji supermarketa znači da ako kupac pazari luk i krompir zajedno najverovatnije da će takođe kupiti i meso za pljeskavicu. Takve informacije mogu biti korišćene kao osnova za odluke o marketinškim aktivnostima kao što su promotivne cene ili raspoređivanje proizvoda. Kao dodatak gorenavedenom iz analize potrošačkih korpi asocijativna pravila su danas uključena u mnoge oblasti kao što su pretraživanje korišćenja veba, detekcije upada, neprekidne produkcije i bioinformatike. Nasuprot pretraživanju nizova učenje pravilom asocijacije obično ne uzima u obzir redosled pojmova ili u ili kroz transakcije.

Definicija

Primer baze sa 4 proizvoda i 5 transakcija

Broj transakcije	mleko	hleb	puter	pivo
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

Prateći prvobitnu definiciju Agravala et al. problem pretraživanja učenjem pravilom asocijacije je definisano kao: Neka su $I=\{i_{1},i_{2},\ldots ,i_{n}\}$ set $n$ binarnih atributa nazvanih stavke. Neka je $D=\{t_{1},t_{2},\ldots ,t_{m}\}$ set transakcija nazvan bazom podataka. Svaka transakcija u $D$ ima jedinstvenu identifikaciju i sadrži podniz stavki u $I$. Pravilo je definisano kao implikacija izraza $X\Rightarrow Y$ gde je $X,Y\subseteq I$ i $X\cap Y=\emptyset$. Nizovi stavki $X$ and $Y$ se nazivaju prethodnici (leva strana ili LHS - left-hand-side) i sledbenici (desna strana ili RHS - right-hand-side).

Da bismo ilustrovali koncepte, koristimo kratki primer iz oblasti supermarketa. Lista stavki je $I=\{\mathrm {mleko,hleb,puter,pivo} \}$ i mala baza podataka koja sadrži stavke (1 kodira prisustvo a 0 odsustvo stavke u transakciji) je prikazana u tabeli sa desne strane. Primer pravila za supermarket može da bude $\{\mathrm {puter,hleb} \}\Rightarrow \{\mathrm {mleko} \}$ što može da znači da ako bi kupci uzeli hleb i puter, takođe bi uzeli i mleko.

Napomena: ovaj primer je izuzetno mali. U praktičnoj primeni pravilo mora da bude potkrepljeno sa nekoliko stotina transakcija pre nego što bi bilo smatrano statistički značajnim, a grupe podataka često sadrže hiljade ili milione transakcija.

Korisni koncepti

Da bismo odabrali interesantna pravila iz grupe svih mogućih pravila, ograničenja na različitim merilima značaja mogu biti korišćena. Najpoznatija ograničenja su minimalni pragovi podrške i poverenja.

• Podrška $\mathrm {supp} (X)$ grupe stavki $X$ je definisana kao proporcija transakcija u grupi podataka koja sadrži tu grupu stavki. U primeru baze podataka grupa stavki $\{\mathrm {mleko,hleb,puter} \}$ ima podršku $1/5=0.2$ jer se dešava u 20% svih transakcija (u jednoj od pet transakcija).
• Poverenje pravila je definisano $\mathrm {conf} (X\Rightarrow Y)=\mathrm {supp} (X\cup Y)/\mathrm {supp} (X)$ . Na primer, pravilo $\{\mathrm {mleko,hleb} \}\Rightarrow \{\mathrm {puter} \}$ ima poverenje $0.2/0.4=0.5$ u bazi podataka, što znači da je za 50% transakcija koje sadrže mleko i hleb pravilo ispravno (50% od svih situacija kada kupac uzme mleko i hleb, uzima i puter). Budite oprezni kada čitate izraz: Ovde supp(X∪Y) znači "podrška za situacije transakcija u kojima se X i Y pojavljuju, a ne podrška za situacije transakcija gde se ili X ili Y pojavljuju". Argument $\mathrm {supp} ()$ je grupa preduslova, pa s tim postaje restriktivnija kako raste (umesto više inkluzivna).
• Poverenje može da bude interpretirano kao procena verovatnoće $P(Y|X)$, verovatnoća nalaženja sledbenika ovog pravila u transakcijama pod uslovom da ove transakcije takođe sadrže prethodnik.
• [[Lift (eksploracija podataka)|Lift] pravila je definisan kao $\mathrm {lift} (X\Rightarrow Y)={\frac {\mathrm {supp} (X\cup Y)}{\mathrm {supp} (X)\times \mathrm {supp} (Y)}}$ ili učestalost posmatrane podrške onoga što je očekivano ako su X i Y nezavisni. Pravilo $\{\mathrm {mleko,hleb} \}\Rightarrow \{\mathrm {puter} \}$ ima lift ${\frac {0.2}{0.4\times 0.4}}=1.25$.
• Konvikcija pravila je definisana kao $\mathrm {conv} (X\Rightarrow Y)={\frac {1-\mathrm {supp} (Y)}{1-\mathrm {conf} (X\Rightarrow Y)}}$. Pravilo $\{\mathrm {mleko,hleb} \}\Rightarrow \{\mathrm {puter} \}$ ima konvikciju ${\frac {1-0.4}{1-.5}}=1.2$, i može biti interpretirano kao udeo očekivane učestalosti kojom se X pojavljuje bez Y (odnosno učestalost kojom pravilo čini pogrešno predviđanje) ako su X i Y nezavisni i podeljeni posmatranom učestalošću netačnih predviđanja. U ovom primeru, vrednost konvikcije od 1.2 pokazuje da će pravilo $\{\mathrm {mleko,hleb} \}\Rightarrow \{\mathrm {puter} \}$ biti netačno 20% češće ako je povezanost između X i Y potpuno slučajna.

Proces

Boja pravougaonika pokazuje koliko transakcija sadrži kombinaciju stavki. Uzmite u obzir da niži nivoi grafika sadrže najviše minimalni broj svojih roditelja - stavki. Ovo se zove mogućnost zatvaranja nadole.

Pravila asocijacije često moraju da zadovoljavaju minimalnu podršku naznačenu od strane korisnika, kao i minimalno poverenje u isto vreme. Izrada pravila asocijacije je obično podeljena na dva odvojena koraka:

1. Minimalna podrška se primenjuje kako bi bile pronađene učestale grupe stavki u bazi podataka.
2. Ove učestale grupe stavki i ograničenje minimalnog poverenja se koriste za izradu pravila.

Dok je drugi korak direktan, prvi korak zahteva više pažnje.

Nalaženje svih učestalih grupa stavki u bazi podataka je teško zato što ono uključuje pretragu svih mogućih grupa stavki (kombinacije stavki). Skup mogućih grupa stavki je [[Partitivni skup|nadskup] od $I$ veličine $2^{n}-1$ (isključujući prazan skup koji nije validan skup stavki). Iako veičina nadskupa raste eksponencijalno u broju stavki $n$ u $I$, efikasna pretraga je moguća koristeći mogućnost zatvaranja nadole što garantuje da za čest skup stavki svi njegovi podskupovi su takođe česti i stoga za redak skup stavki svi njegovi nadskupovi moraju biti takođe retki. Istražujući ovu osobinu, efikasni algoritmi mogu naći sve česte skupove stavki.

Istorija

Koncept asocijativnih pravila je popularizovan najviše zahvaljujući članku Agravala et. al iz 1993. koji je pribavio više od 6000 citata i stoga je jedan od najcitiranijih radova u oblasti prikupljanja podataka. Ipak, moguće je da su sada zvana "pravila asocijacije" slična onome što se pojavljuje u radu 1966. godine. Na Guha, opštem metodu pretrage podataka razvijenom od strane Petr Hájek et al.

Alternativne mere zanimljivosti

Pored poverenja i druge mere interesantnosti su predložene za pravila. Neke popularne mere su:

• Potpuno poverenje
• Kolektivna snaga
• Ubeđenje
• Prednost
• Lift

Definicija ovih mera može biti nađena ovde Arhivirano na sajtu Wayback Machine (2. avgust 2018). Još nekoliko mera je predstavljeno i upoređeno od strane Tan et al. Traženje tehnika koje predstavljaju šta je korisnik znao (i korišćenje ovih modela kao mera interesantnosti) je trenutno aktivno istraživanje pod imenom "Subjektivna zanimljivost".

Statistički važne asocijacije

Jedno ograničenje standardnog pristupa otkrivanju asocijacija je što pretraga velikog broja mogućih asocijacija u potrazi za kolekcijama stavki koje se povezuju, povlači veliki rizik za pronalaženje mnogo sumnjivih asocijacija. Ovo su kolekcije stavki koje se dešavaju neočekivanom učestalošću u podacima, ali samo slučajno. Na primer, pretpostavimo da u kolekciji od 10 000 stavki tražimo pravila koja sadrže dve stavke u levoj strani i jednu u desnoj. Približno ima 1 000 000 000 000 takvih pravila. Ako primenimo statistički tekst za nezavisnost sa nivoom značaja od 0.05 to znači da postoji samo 5% šanse za prihvatanje pravila ako ne postoji asocijacija. Ako pretpostavimo da asocijacije ne postoje, bez obzira na to možemo očekivati da nađemo 50 000 000 000 pravila. Otkrivanje statistički značajnih asocijacija kontroliše ovaj rizik, u većini slučajeva smanjujući rizik nalaženja bilo kakvih lažnih asocijacija za nivo korisnički definisan nivo značaja.

Algoritmi

Mnogi algoritmi za pravljenje pravila asocijacije su vremenom prikazani.

Neki poznati algoritmi su Apriori, Eklat i FP-rast, ali oni rade samo pola posla, zbog toga što su algoritmi za pronalaženje učestalih skupova stavki. Još jedan korak mora biti urađen da bi se napravila pravila iz učestalih skupova stavki nađenih u bazi podataka.

Apriori algoritam

Apriori algoritam - apriori je najpoznatiji algoritam za pretraživanje pravila asocijacije. Koristi BFS strategiju (pretraga u širinu) za brojanje skupova stavki i koristi funkciju nalaženja kandidata koja ima osobinu zatvaranja nadole.

Eklat algoritam

Eklat je algoritam za pretragu u dubinu koji koristi presecanje skupova.

FP-rast algoritam

FP označava učestali šablon (na engleskom).

U prvom prolazu, algoritam broji pojavljivanje stavki (parovi atribut-vrednost) u skupu podataka, i učitava ih u 'heder tabelu'. U drugom prolazu pravi FP stablo tako što ubacuje instance. Stavke u svakoj instanci moraju biti sortirane u opadajućem poretku prema svojoj učestalosti u skupu podataka, tako da stablo može biti brzo obrađeno. Stavke u svakoj instanci koje ne zadovoljavaju prag minimalne pokrivenosti se odbacuju. Ako mnogo instanci deli najučestalije stavke, FP stablo pruža visoku kompresiju u blizini korena stabla.

Rekurzivno obrađivanje ovih kompresovanih verzija glavnog skupa podataka stvara velike skupove stavki direktno, umesto pravljenja stavki kandidata i testiranja istih u odnosu na celu bazu podataka. Rast počinje sa dna tabele zaglavlja (heder tabele koja ima najduže grane), nalaženjem svih instanci koje odgovaraju datom uslovu. Pravi se novo drvo sa tačkama iz prvobitnog drveta u odnosu na skup instanci koje su uslovljene atributom, sa svakim čvorom koji sadrži sumu tačaka svoje dece. Rekurzivni rast se završava kada ni jedna stavka uslovljena atributom ne dostigne minimalni prag podrške i procesiranje se nastavlja na ostatku stavki zaglavlja prvobitnog FP drveta.

Kada se rekurzivni proces jednom završi svi veliki skupovi stavki sa minimalnom pokrivenošću su nađeni i počinje stvaranje pravila asocijacije.

GUHA procedura

GUHA je uopšteni metod za analizu podataka koji ima teoretski temelj u izračunavanju posmatranjem.

ASSOC procedura je GUHA metod koji traži generalizovana pravila asocijacije koristeći brze operacije bit stringa. Pravila asocijacije pronađena ovim metodom su više uopštena nego ona nađena apriori metodom, na primer "stavke" mogu biti povezane i sa konjukcijom i sa disjunkcijom i relacija između prethodnika i sledbenika pravila nije ograničena na postavljanje minimalne podrške i poverenja kao u apriori-u: kombinacija podržanih mera interesovanja može biti korišćena.

OPUS pretraga

OPUS je efikasan algoritam za promalaženje pravila koji, suprotno mnogima alternativama, ne zahteva ni monotona ni antimonotona ograničenja kao što su minimalna podrška. Prvobitno korišćeno za pronalaženje pravila za fiksiranu i doslednu, a proširen za nalaženje pravila za bilo koju stavku kao doslednu. Opus pretraga je ključna tehnologija u popularnom Magnum Opus sistemu otkrivanja asocijacija.

Znanje

Poznata priča o pronalaženju pravila asocijacije je priča o "pivu i peleni". Anketa o ponašanju kupaca u supermarketu otkrila je da kupci (mladi muškarci najčešće) koji kupe pelene vrlo često kupe i pivo. Ova anegdota je postala popularna kao primer toga kako neočekivana pravila asocijacije mogu biti nađena u podacima iz svakodnevice. Postoje različita mišljenja o tome koliko je ova priča tačna. Daniel Powers says:

1992. godine, Tomas Blišok, menadžer konsalting grupe u "Teradata", zajedno sa svojim zaposlenima, pripremio je analizu 1,2 miliona potrošačkih korpi iz otprilike 25 prodavnica Osko. Upitnik je izrađen za prepoznavanje sklonosti. Analiza "je otkrila da su potrošači između pet i sedam časova popodne kupovali pivo i pelene". Menadžeri u Osku NISU iskoristili povezanost piva i pelena tako što bi pomerili proizvode bliže jedan drugom na policama.

Ostali tipovi traženja asocijacija

Učenje različitih skupova je oblik asocijativnog učenja. Oni koji ga koriste, koriste pravila koja značajno odstupaju u svojoj raspoređenosti kroz potskupove.

Učenje opterećenih klasa je još jedan oblik asocijativnog učenja u kome opterećenost možće biti dodeljena klasama kako bi dala fokus određenom problemu za potrošača rezultata pronalaženja podataka.

Otkrivanje šablona visokog reda - ove tehnike ubrzavaju hvatanje šablona visokog reda (politetičkih) ili asocijacija događaja unutar kompleksnih podataka stvarnog sveta.

K-optimalno otkrivanje šablona omogućava alternativu standardnom pristupu učenju pravila asocijacije koje zahteva da se svaki šablon ponavlja u podacima.

Generalizovana pravila asocijacije - konceptna hijerarhija.

Kvantitativna pravila asocijacije - kategorični i kvantitativni podaci.

Pravila asocijacije podataka u intervalima.

Maksimalna pravila asocijacije.

Pronalaženje sekvencijalnih šablona - niz je uređena lista transakcija.

Sekvencijalna pravila - otkrivanje povezanosti između stavki uzimajući u obzir vremensku raspoređenost. Najčešće se primenjuje na bazu podataka nizova. Na primer, sekvencijalno pravilo nađeno u bazi podataka nizova transakcija potrošača može biti da potrošači koji su kupili kompjuter i cd-romove, kasnije kupe veb kameru.

Literatura

• Tan, Pang-Ning; Michael, Steinbach; Kumar, Vipin (2005). „Chapter 6. Association Analysis: Basic Concepts and Algorithms” (PDF). Introduction to Data Mining. Addison-Wesley. ISBN 978-0-321-32136-7. 
• Hájek, Petr (1978). Mechanizing Hypothesis Formation: Mathematical Foundations for a General Theory. and Havránek, Tomáš. Springer-Verlag. ISBN 978-3-540-08738-0.