H2:AR Assotsiatsioonireeglid Vt. Assotsiatsioonireegleid ja Apriori algoritmi: {URL("Assoc/apriori.txt")} Vt. episoodireegleid: {URL("Assoc/episodes.pdf")} * Assotsiatsioonireeglid (association rules) (kõigepealt leitakse sagedased hulgad ja nende pealt reeglid) Vaatleme näiteks suure toidupoe müügiprotsessi. Siin on meil tegemist suure hulga erinevate kaubaartiklitega. Samuti on siin kliendid, kes kaubavalikust üht-teist enda ostukorvi panevad, ning seejärel kassas ostu sooritavad. See fakt kajastub toidupoe andmebaasis nn ostukorvina. Siit koguneb toidupoele väärtuslik infovaramu näiteks turundusosakonnale, kelle ülesandeks on korraldada erinevaid kampaaniaid.

Ostukorvide pealt on võimalik leida seoseid erinevate kaupade ühte ostukorvi sattumiste kohta. Üheks selliseks on sageli erialastes artiklites käsitletav tähelepanek, et sageli ostetakse koos õlut ning beebimähkmeid {cite('thomas00incremental')}. Sellisel juhul võib vaadelda implikatsiooni {tex(' {beer}\Rightarrow {diapers}')} kui assotsiatsioonireeglit üle õlut ning mähkmeid sisaldavate ostukorvide. Assotsiatsioonireeglite analüüsi ülesandeks on leida analoogilisi seoseid andmestust --- kui ostukorvis sisalduvad teatud kaubad, millised kaubad veel samas ostukorvis tõenäoliselt esinevad? H3:1 Seoste tüübid:

Vastavaid reegleid võib tulla suhteliselt palju, üldjoontes võib need jagada järgmisse nelja gruppi {cite('ibmdatamining')}:

H3:2 Sissejuhatust

Algoritmiline pool on vaid nende reeglite tuvastamine, reeglite kvaliteedi ning praktilisuse otsustamine jääb paraku ikkagi inimese otsustada. Suureks probleemiks on siin reeglite suur hulk, näiteks mõne tuhande kaubaartikliga poes võib olla miljardeid reegleid {cite('borgelt-induction')}. Kuna sellise hulga reeglite kontroll on väga töömahukas on vaja efektiivseid algoritme. Efektiivsus tähendab siin kontrollitavate reeglite arvu piiramist, jättes võimaluse korral siiski huvitavad reeglid alles. Assotsiatsioonireeglite kaevandamise juured on jaekaubanduse ostude analüüsil {cite('agrawal93mining')} ning seetõttu vastavate seoste leidmist andmestust nimetatakse sageli ostukorviaanalüüsiks{def("",'market-basket analysis')}. Samas ei ole see piiratud ainult ostukorvide analüüsiga. Palju huvitavamaid ning ärilisest seisukohast paremini rakendatavaid tulemusi võib saada ka ostukorvide andmestu uurimisel koos klientide demograafiliste andmetega. See võib uurija viia tulemuseni, et 25--30 aastane universaalkerega autoga abielus meesterahvas ostab suure tõenäosusega koos õllega ka lapsemähkmeid. Samuti ei pruugi ühe ostukorvi mõttes tegu korraga ostetud kaupadega vaid võib vaadelda ka ühe kliendi oste mingi kindla perioodi jooksul, näiteks veebiraamatupoe või plaadipoe ostud {cite('agrawal93mining')}. Kuigi assotsiatsioonireegli all käesoleva ülevaate mõttes peame silmas lihtsalt hulkadevahelist seost, on loodud meetodeid ka järjestusega assotsiatsioonireeglite leidmiseks {cite('agrawal95mining,agrawal93efficient,srikant96mining')}. Sellist tüüpi assotsiatsioonireegleid esineb näiteks geenisekventsiandmebaaside {cite('chirn96pattern,yang02mining')} ja veebikohtade külastuste analüüsis {cite('berkhin01interactive,cooley97web,mobasher96web,mortazavi-asl-discovering')} H3:5 Negatiivsed seosed

Üks huvitav valdkond on negatiivsete assotsiatsioonide leidmine. Näiteks üks selline reegel võiks kõlada järgnevalt: "<75% abielus meestest kes ostavad õlut ei osta pakipiima">. Sedasorti probleeme lahendavaid algoritme on juba ka loodud ning autori väiteil on nad küllalt efektiivsed {cite('savasere98mining')}. * Tugi ja usaldusväärsus (support and confidence) (et jääksid alles ainult head reeglid ja et otsimisruum oleks väiksem) Olgu {tex('I = \{I_1, I_2, ..., I_m\}')} hulk binaarseid tunnuseid, ehk kaupu {cite('agrawal93mining')}. Olgu {tex('T')} ostude andmebaas, kus igat ostu {tex('t')} kirjeldab kahendvektor, milles {tex('t[k]=1')} kui ostukorvis sisaldus kaup {tex('I_k')}, ning {tex('t[k]=0')} kui ei olnud. Iga ostu kohta on andmebaasis {tex('T')} üks korteež. Olgu {tex('X \subseteq I')}. Ütleme, et ost {tex('t')} rahuldab {tex('X')} kui iga ostu {tex('I_k')} jaoks hulgas {tex('X')} nii, et {tex('t[k]=1')}. H3:7 Definitsioonid

Assotsiatsioonireegli all peame edaspidi silmas implikatsiooni kujul {tex('X \Rightarrow I_j')}, kus {tex('X \subset I')} ning {tex('I_j \in I \wedge I_j \not \in X')}. Reegel {tex('X \Rightarrow I_j')} on täidetud baasil {tex('T')} usaldusteguriga {def("",'confidence')} {tex('0 \leq c \leq 1')} kui vähemalt {tex('c\%')} ostudest baasis {tex('T')}, mis sisaldavad hulka {tex('X')}, sisaldavad ka {tex('I_j')}. Edaspidi tähistame vastavat olukorda kujul {tex('X \Rightarrow I_j \mid c')}, et reeglil {tex('X \Rightarrow I_j')} on usaldustegur {tex('c')}. Ütleme, et reegli {tex('X \Rightarrow I_j')} tugi {def("",'support')} baasil {tex('T')} on {tex('s')} kui {tex('s\%')} ostudest baasis {tex('T')} rahuldab {tex('X \cup I_j')}. Hulga {tex('a')} tuge võime väljendada ka kujul {tex('support(a)')}. Sageli vaadeldakse {tex('I_j')} asemel ka hulka {tex('I^\star')} nii, et {tex('I^\star \subseteq I')}. Kui usaldustegur mõõdab reegli tugevust siis tuge võib vaadelda kui olulisust statistilises mõttes {cite('agrawal93mining,fiore-visualizing,brin97beyond')}.

Ülesanne on leida kõik assotsiatsioonireeglid, millel on tugi suurem kui eelnevalt seatud minimaalne tugi (edaspidi i:minsup) ning usaldustegur suurem kui eelnevalt seatud minimaalne usaldustegur (edaspidi i:minconf). On võimalik seada ka mitmeid täiendavaid kitsendusi soovitud assotsiatsioonireeglitele {cite('agrawal93mining')}: H3:9 Kitsendusi

H3:a Protsess

Antud probleemi esituse korral võib assotsiatsioonireeglite leidmise protsessi jagada kaheks {cite('agrawal93mining,agrawal94fast')}:

  1. Leida kõik kaupade kombinatsioonid mille tugi on suurem kui i:minsup. Nimetame kõiki neid kombinatsioone suurteks kaupadehulkadeks {def("",'large itemset')} ning kõiki ülejäänuid, mille tugi jääb allapoole i:minsup väärtust, väikesteks kaupadehulkadeks {def("",'small itemset')}. Kaupadehulki, mille vastavust kitsendustele pole veel jõutud kontrollida, nimetame edaspidi kandidaathulkadeks. Süntaktiliste kitsenduste olemasolul peame arvestama ka nendega.
  2. Iga suure kaupadehulga {tex('Y = I_1 I_2 ... I_k, k \ge 2')} jaoks koostada reeglid mis kasutavad kaupu valikust {tex('I_1,I_2,...,I_k')}. Vastava assotsiatsioonireegli vasakuks pooleks saab alamhulk {tex('X \subset Y')} nii, et hulgal {tex('X')} on {tex('k-1')} elementi, ning reegli paremaks pooleks saab {tex('Y-X')}. Et leida reeglit {tex('X \Rightarrow I_j \mid c')} nii, et {tex('X = I_1 I_2 ... I_{j-1} I_{j+1} ... I_k')}, tuleb võtta hulga {tex('X')} tugi ning jagada see {tex('I_j')} toega. Kui tulemus on suurem kui i:minconf siis võime vastava reegli alles jätta {cite('agrawal94fast')}. Tasub märkida, et kui kaupadehulk {tex('Y')} on suur, siis on suur ka iga {tex('Y')} alamhulk ning setõttu peab meil iga kaupadehulgaga olema teada ka tema tugi. Samuti peavad kõik kaupadehulgast {tex('Y')} tuletatud reeglid rahuldama toele seatud kitsendusi sest {tex('Y')} ise seda teeb, ning ta on samas kõikide nende reeglite paremate ja vasakute poolte ühend.
H3:b Algoritmid * Algoritmid AR leidmiseks (või peaks kandidaatide genereerimine ja loendamine olema siin all?) * Apriori Vaatleme nüüd algoritmi Apriori (joonis{'apriori'}). Algoritmi esimene samm loeb kokku üksikute kaupade esinemiste arvu baasis {tex('T')} leidmaks suuri {tex('1')}-kaupadehulki. Iga järgmine samm {tex('k')} koosneb kahest osast. Kõigepealt leitakse funktsiooni AprioriGen abil eelmiselt sammult saadud suurtest kaupadehulkadest {tex('L_{k-1}')} kandidaathulgad {tex('C_k')}. Seejärel leitakse baasist {tex('T')} tugi neile hulkadele ning jäetakse alles vaid suured hulgad. Et vähendada andmebaasi läbivaatuste arvu kasutatakse kiireks loendamiseks funktsiooni AprioriSubset (kirjeldatakse allpool). H3:d Algoritm Apriori 
Apriori

Sisend 	T -- ostude baas
	minsup -- kaupadehulga suuruse kriteerium
	
Väljund  suured kaupadehulgad

\STATE {tex('L_1 = \{ suured 1-kaupadehulgad \}')}
\FOR   {tex('k=2; L_{k-1}\not =\emptyset;\ k ')}
  \STATE {tex('C_k= AprioriGen (L_{k-1})')}
  \FORALL {tex('tehingud\ t \in T')}
    \STATE {tex('C_t = AprioriSubset(C_k,t) ')}
    \FORALL  kandidaathulgad {tex('\ c \in C_t')}
      \STATE  c.count = c.count+1
    \ENDFOR
  \ENDFOR
  \STATE {tex('L_k=\{c \in C_k \mid  c.count \ge minsup\}')}
\ENDFOR
\STATE  {tex('=\bigcup_k L_k')}
H3:e Eeldused * Apriori eeldus Tavaliselt kasutavad suurte kaupadehulkade leidmise algoritmid andmestu {tex('T')} korduvat läbivaatust. Esimese läbivaatusega leitakse üksikute kaupade tugi ning otsustatakse, millised neist on toele seatud kitsenduste mõttes suured. Iga algoritmi samm kasutab eelmisel sammul leitud suuri kaupadehulki leidmaks võimalikke kandidaathulki. Seejärel leitakse andmestu {tex('T')} läbivaatusega toed neile kandidaathulkadele ning toele seatud kitsendust rahuldavad hulgad loetakse suurteks, ning seega järgmise sammu lähteandmeteks. Protsessi korratakse kuni rohkem suuri kaupadehulki ei leita. Probleemiks on siin andmestu läbivaatamiseks kulutatav ressursside maht ning samuti kandidaathulkade suur arv. Üheks lahenduseks on siin vähemoluliste kandidaathulkade võimalikult varajane kõrvalejätmine ning andmestu läbivaatuste arvu minimeerimine. Eelpoolkirjeldatud skeemi järgib küllalt laialdaselt levinud algoritmide pere Apriori {cite('agrawal94fast')}. Sellele algoritmide perele on iseloomulik uute kandidaathulkade koostamine vaid eelmiselt sammult saadud suuri kaupadehulki kasutades. Seda teha lubab teadmine, et iga suure kaupadehulga alamhulk peab samuti olema suur. Seetõttu võime koostada uusi {tex('k')} elemendilisi kandidaathulki {tex('k-1')} elemendilistest suurtest kaupadehulkadest. Neist omakorda võib välja jätta need hulgad mille ükskõik milline alamhulk pole toele seatud kitsenduste mõttes suur. Nii tehes on tulemuseks märksa väiksem arv kandidaathulki, andes nii ajalises kui ka mäluvajaduse mõttes palju paremaid tulemusi. H3:hh Kandidaadid Edaspidi nimetame kaupade arvu hulgas tema suuruseks ning suurusega {tex('k')} kaupadehulka {tex('k')}-kaupadehulgaks. Kaupu hulgas hoitakse leksikograafilises järjestuses. Notatsiooni {tex('c[1] \cdot c[2] \cdot ... \cdot c[k]')} kasutame kujutamaks {tex('k')}-kaupadehulka {tex('c')} mis koosneb kaupadest {tex('c[1],c[2],...,c[k]')}, kus {tex('c[1] AprioriGenJoin Sisend {tex('L_{k-1}: (k-1)')}-kaupadehulgad Väljund {tex('C_k: k')}-kaupadehulgad \STATE {tex('C_k=\emptyset')} \FORALL {tex('p,q \in L_{k-1}')} \IF {tex('p.{kaup}_1=q.{kaup}_1 \wedge ... \wedge p.{kaup}_{k-2} = q.{kaup}_{k-2} \wedge p.{kaup}_{k-1} < q.{kaup}_{k-1}')} \STATE {tex('C_k=C_k \cup \{p.{kaup}_1,p.{kaup}_2,...,p.{kaup}_{k-1},q.{kaup}_{k-1}\}')} \ENDIF \ENDFOR Funktsiooni AprioriGen liitmissamm ning seejärel eemaldatakse harvendamissammus (joonis apriori-gen-prune) kõik kaupadehulgad {tex('c \subset C_k')} mille ükskõik milline {tex('(k-1)')}-alamhulk ei sisaldu {tex('L_{k-1}')} sees. 
AprioriGenPrune

Sisend {tex('C_k')}: {tex('k')}-kaupadehulgad

Väljund: {tex('C_k')}: harvendatud {tex('k')}-kaupadehulgad

\FORALL {tex('kaupadehulgad\ c \in C_k')}
  \FORALL {tex('c\ (k-1)-alamhulgad\ s')}
    \IF   {tex('s \not\in L_{k-1}')}
      \STATE {tex('C_k=C_k - c')}
    \ENDIF
  \ENDFOR
\ENDFOR

Funktsiooni AprioriGen harvendamissamm
H3:m Näide Näiteks olgu {tex('L_3')} meil {tex('\{\{a b c\},\{a b d\},\{a c d\},\{a c e\},\{b c d\}\}')}. Pärast liitmissammu on {tex('C_4')} sees kaupadehulgad {tex('\{a b c d\}')} ja {tex('\{a c d e\}')}. Harvendamissammu käigus eemaldatakse kaupadehulk {tex('\{a c d e\}')} sest tema alamhulk {tex('\{a d e\}')} ei sisaldu hulgas {tex('L_3')}. Seega jääb {tex('C_4')} sisse alles ainult {tex('\{a b c d\}')}. Funktsiooni AprioriSubset ülesandeks on leida kõik kaupadehulgad mis sisalduvad nii {tex('C_k')} kui ka hetkel loendamissammu poolt käsitletavas ostus {tex('t')}. * Loendamine (hash tree abiga) Kõigi elementide kombinatsioonide esinemiste loendamine üle terve andmestu on küllalt suuremahuline töö. Seetõttu on oluline vähendada andmestu läbivaatuste arvu. Christian Borgelt ja Rudolf Kruse on välja pakkunud algoritmi Apriori kiire implementatsiooni {cite('borgelt-induction')}, mis põhineb prefiksipuu kasutamise abil kandidaathulkade genereerimisest loobumises {cite('han00mining')}. H3:o Ostukorvide loendamine

Leidmaks sagedasi kaupadehulki tuleb üle lugeda kõik ostukorvid kus nad esinevad. Kirjeldatava implementatsiooni ideeks on kaupadehulkade loendurite esitus erilise prefiksipuuna (vt joonis \ref{prefiksipuu}) mis mitte ainult ei hoia kokku mälu vaid lubab ka efektiivselt töödelda ostukorve ning hiljem esitada reegleid. Iga {tex('n_S')} kujutab endast loendurit kaupadehulga {tex('S')} jaoks. Servade lipikud juurtipust mõne lehttipuni tähistavad ühisosa neile loenduritele mis antud tipus paiknevad. Kujutatud puu pole balansseeritud kuna leksikograafilise järjestuse nõude tõttu loeme {tex('n_{abc}')} samaks mis {tex('n_{bca}')} ning seetõttu vajatakse vaid üht neist loenduritest. H3:p Hulkade genereerimine {img("prefiksipuu.eps")} Täielik kaupadehulkade puu kaupade {tex('a')}, {tex('b')}, {tex('c')}, {tex('d')} ja {tex('e')} jaoks

Apriori algoritmi esimese sammuna luuakse eelpoolkirjeldatud puu tase taseme haaval. Esimese baasi läbivaatusega luuakse {tex('1')}-kaupadehulgad, teise läbivaatusega {tex('2')}-hulgad jne. Puu selline ehitusviis lubab meil järjest välja jätta neid tippe mille tugi ei vastanud eelnevalt toele seatud kitsendustele --- tänu apriori eeldusele on meil teada, milline puu haru sisaldab endas sagedasi kaupadehulki ja milline kindlasti mitte.

Puu tippudes olevate loendurite hoidmiseks on algselt välja pakutud kolm võimalust:

  1. Täisarvude vektor, kus iga element tähistab ühe kaupadehulga tuge. Selle struktuuri juures ei ole meil otseselt viidet konkreetsele kaupadehulgale vaid igale kaupadehulgale vastab vektori konkreetne element. Seetõttu tuleb säilitada loendureid ka nende kaupadehulkade jaoks mille kohta eelmisest sammust on teada, et need on kindlalt väikesed --- vektoris ei ole tühimikud lubatud.
  2. Vektor kaupadehulkade identifikaatoritest ja vastavatest loenduritest, järjestatuna kaupadehulga identifikaatori järgi.
  3. Paisktabel. Siin on aga probleemiks efektiivse paiskfunktsiooni leidmine. Seetõttu ei paku ta piisavalt kiirusevõitu küllalt suure mälukasutuse kõrvalt ja edaspidi me seda võimalust ei vaatle.
H3:s Analüüs

On näha, et esimene viis loendurite säilitamiseks on kõige mälunõudlikum aga ka kõige kiirem. Samuti saab tippude jaoks valida, millist struktuuri loendurite säilitamiseks kasutada. Kui suhteliselt suur osa võimalikest kaupadehulkadest on suured siis on mõtet kasutada esimest meetodit. Tühikute arvu saab vähendada ka kaupadele sobivate märgiste valimisega, näiteks järjestades nad esinemissageduste järgi.

Ostude andmestu {tex('T')} töötlemine, ehk sagedaste hulkade loendamine, on eelpool kirjeldatud puu korral suhteliselt lihtne. Eeldades, et kaubad on konkreetses ostus leksikograafiliselt järjestatud, võib puu lihtsalt rekursiivselt läbi käia ning vastavalt igas tipus olevat loendurit suurendada või uusi tippe luua:

  1. leida ostu esimesele kaubale vastav alamtipp ning rakendada ülejäänud kaupadehulka selles ostus rekursiivselt sellele alamtipule
  2. jätta ostu esimene kaup kõrvale ning rakendada allesäänud kaupadehulka sellele tipule
Iga sammu juures tuleb suurendada ka vastavaid loendureid. Kui me just lisasime puule uue taseme, siis kasvatame selle uue taseme loendurit ning edasi ei liigu. Sedasi tagatakse, et kõikide ostu alla kuuluvate kaupadehulkade loendurid on korrektselt suurendatud. H3:xx Puudused Kirjeldatud implementatsiooni puuduseks on süntaktiliste kitsendustega mittearvestamine kuigi nende lisamine ei ole kuigi keeruline. Samuti võib tööd jätkata selle implementatsiooni realiseerimisel SQL põhisena. * Kiirendamine (hash-based itemset counting, transaction reduction, partitioning, sampling, dynamic itemset counting) * Loendamine kandidaate kasutamata (FP-tree abil) Sama jutt, mis loendamise all, Borgelt ja Kruse kasutasidki FP-tree'd. * Reeglite leidmine sagedaste hulkade abil Olgu meil suur kaupadehulk {tex('l')}. Vastavate reeglite leidmiseks tuleb lihtsalt leida selle kõik mittetühjad alamhulgad. Iga sellise alamhulga {tex('a')} kohta leiame reegli kujul {tex('a \Rightarrow (l-a)')} kui support(l)/support(a)≥minconf. H3:z Kiirendamine

Kirjeldatud skeemi suure kaupadehulga alamhulkade leidmiseks saab sügavuti rekursiooniga kiirendada. Näiteks hulga {tex('ABCD')} korral vaatleme kõigepealt hulka {tex('ABC')}, seejärel {tex('AB')} etc. Kui suure kaupadehulga {tex('l')} mingist alamhulgas {tex('a')} ei tule reeglit (toele seatud kitsenduste mõttes), siis võib öelda, et ka {tex('l')} alamhulki ei maksa enam reeglite leidmisel arvestada. Näiteks kui reegel {tex('ABC \Rightarrow D')} ei ole eelnevalt seatud usaldusteguri kitsenduste mõttes oluline, siis ei ole vaja ka kontrollida enam reeglit {tex('AB \Rightarrow CD')}. Nii ei lähe ükski reegel kaotsi, sest iga {tex('a')} alamhulga {tex('\bar{a}')} tugi peab olema vähemalt sama suur kui hulgal {tex('a')}. Seetõttu ei saa ka {tex('\bar{a} \Rightarrow (l-\bar{a})')} usaldustegur olla suurem kui {tex('a \Rightarrow (l-a)')} usaldustegur. Seega, kui {tex('a')} kasutamisel ei teki reeglit kõigi {tex('l')} elementidega kus {tex('a')} oleks reegli paremal poolel, ei tee seda ka {tex('\bar{a}')}. Selle idee võtab kokku algoritm joonisel \ref{vana-rules}. H3:aa Algoritm c 


\FORALL suured kaupadehulgad {tex('l_k,k \ge 2')}
  \STATE call GenRules({tex('l_k,l_k')})
\ENDFOR

GenRules

Sisend: {tex('l_k')} : suur {tex('k')}-kaupadehulk
	{tex('a_m')} : suur {tex('m')}-kaupadehulk

\STATE  {tex('A=\{(m-1)-kaupadehulgad\ a_{m-1} \mid a_{m-1} \subset a_m\}')}
\FORALL {tex('a_{m-1} \in A')}
  \STATE  {tex('conf=support(l_k)/support(a_{m-1})')}
  \IF	{tex('conf \ge minconf')}
    \STATE väljasta reegel {tex('a_{m-1} \rightarrow (l_k-a_{m-1})')}, usaldusteguriga {tex('conf')} ja toega {tex('support(l_k)')}
    \IF  {tex('m-1 > 1')}
      \STATE call GenRules({tex('l_k,a_{m-1}')})
    \ENDIF
  \ENDIF
\ENDFOR

Assotsiatsioonireeglite genereerimise algoritm
H3:ab Erijuhtumid * Järjendid (sequences, sequential ar) * Episoodid (episodes) Episoodide leidmisel defineeritakse sündmus paarina {tex('(A, t)')}, kus {tex('A')} on sündmuse tüüp ja {tex('t')} aeg. Mingid logisse kogunenud sündmused moodustavad sündmuste jada. Sündmuste jada iseloomustavad tema algusaeg {tex('T_s')} ja lõppaeg {tex('T^s')}. Seejuures kõikide sündmuste jadasse kuuluvate sündmuste toimumisaeg peab jääma vahemikku {tex('[T_s, T^s)')}. Sündmuste jadaga analoogiliselt defineeritakse aken {tex('[T_w, T^w)')}, kui mingi osa kogu sündmuste jadast. Seejuures on nõutav, et aken ja sündmuste jada vähemalt osaliselt kattuksid, st {tex('T_s Tähtsaimaks episoodidega seotud ülesandeks on episoodi esinemissageduse leidmine. Esinemissageduse leidmiseks fikseeritakse jällegi eelnevalt akna pikkus {tex('win')}. Episoodi {tex('e')} esinemissagedus mingis sündmuste jadas leitakse järgmise valemi abil % 
	episoodi {tex('e')} sisaldavate pikkusega {tex('win')} akende arv jadas
fr = -----------------------------------------------------------------------------
	kõikide pikkusega {tex('win')} akende arv
H3:bg Parallel

On olemas algoritmid sündmuste jadas kõigi piisavalt suure sagedusega paralleelsete ja järjestikuste episoodide leidmiseks. Suvaliste episoodide sageduste leidmine taandatakse enamasti vastava paralleelse episoodi leidmisele ning igas aknas, kus too paralleelne episood esines, kontrollitakse ka sündmuste järjestust. Eelpoolmainitud probleemi lahenduseks on välja pakutud algoritm sagedaste episoodide leidmiseks {cite('toivonen96frequent')}, millele siin töös viidatakse kui algoritmile Haba. See algoritm leiab sagedasi episoode sammhaaval. Esimese sammuna leitakse sagedased sündmused, ehk ühest sündmusest koosnevad sagedased episoodid. Seejärel genereeritakse võimalikud ühe sündmuse võrra pikemad kandidaatepisoodid, ning andmestu pealt leitakse, millised neist on sagedased. See protsess kasutab ära fakti, et sagedase episoodi alamepisood peab samuti olema sagedane. H3:rak Rakendusi Assotsiatsioonireeglite kaevandamise rakendusvaldkondi on palju rohkem kui jaekaubandus ning veebilehtede külastatavuse analüüs. USA relvajõududes kasutatav automaatne raketitõrjesüsteem Patriot, mis leidis laialdast kasutust Lahesõjas, kasutab assotsiatsioonireeglitel põhinevat otsustussüsteemi {cite('peter-dm')}. Automaatrežiimil suudab see süsteem saamaegselt jälgida sadu lendavaid objekte ning otsustab teatud reeglite põhjal punktiarvestust pidades millist neist objektidest alla tulistada. Näiteks lennumasin, mis tuleb läbi eeldefineeritud ", saab mõned punktid. Kui tema lennutrajektoor pole aga piisavalt paralleelne turvakoridori omaga siis ta kaotab mõned punktid. Kui aga kiirus on teatud piires siis on see hea. Lendobjekt, mis siseneb turvakoridori altpoolt radari nähtavusala (nn pop-up), saab jälle miinuspunkte. Kui tema raadioseadmed ei suuda identifitseerida teda kui sõbralikku objekti, kaotab ta veel mõned punktid. Raketitõrjesüsteem otsustab objekti allatulistamise kasuks kui punktisumma on piisavalt madal. Assotsiatsioonireeglite abil on võimalik leida reegleid ka dokumentidest, esitades dokumentides esinevaid (olulisi) sõnu kujul {tex('(d,w)')}, kus {tex('d')} on dokumendi identifikaator ning {tex('w')} tähistab dokumendis esinevat sõna. Ehk tegemist on suure (ja ilmselt ka hõreda) maatriksiga {tex('A(d,w)')}, kus read tähistavad dokumente ning verud sõnu ning iga maatriksi element näitab kas sõna esinemise fakti dokumendis või siis tema esinemiste arvu {cite('mannila02local')}. Sarnaselt võib kujutada ka veebiserveri logifaili, kolmikuna {tex('(h,p,t)')}, kus {tex('h')} on päringu esitanud tööjaama identifikaator, {tex('p')} on vaadeldud lehekülje identifikaator ning {tex('t')} on pöördumise aeg {cite('mannila02local')}. Jättes kõrvale aja, saame eelmises lõigus toodud näitega sarnase esituse. Selliste esitusviiside tulemusena tekivad küllalt suurte mõõtmetega andmestud, dokumendiandmebaasidel on täheldatud sadu tuhandeid dimensioone {cite('mannila02local')}. Samas on need maatriksid suhteliselt hõredad, seetõttu tegelik dimensioonide arv on väiksem. Samas on siin selgelt näha vajadus dimensioonide vähendamise meetodite järele. Üks huvitavaid rakendusi on ka sündmuste järjendites muudatuste leidmine, ajamõõdet järgides. Sellist lähenemist on rakendatud oluliste muudatuste leidmises demograafiliste andmete (sünniaeg, abielu ning püsiva partnerisuhte algus ja lõpp, laste sünniajad) seast {cite('blockeel01detecting')}. H3:cf Veebianalüüs Laialdast kasutamist on assotsiatsioonireeglid leidnud ka veebispetsiifiliste andmete töötlemisel {cite('tiidumaa02dm')}. Üks võimalik rakendus on veebilehtede mugandamine konkreetse kasutaja vajadustele vastavaks {cite('oracledmconcepts')}. Oletame, et veebilogist leidsime reegli {tex('A,B \Rightarrow C \mid 80\%')}, kus {tex('A')}, {tex('B')} ja {tex('C')} on veebilehed. Seda võib tõlgendada nii, et kui kasutaja on küsinud lehti {tex('A')} ja {tex('B')} siis on 80% tõenäosus, et ta küsib ka lehte {tex('C')}. Lehele {tex('C')} ei pruugi olla otsest linki lehtedelt {tex('A')} ja {tex('B')}. Selle reegli järgi võib selle lingi konkreetse kasutaja konkreetse sessiooni ajal dünaamiliselt luua. H3:oopen Lahtised küsimused: Üks probleeme assotsiatsioonireeglite leidmisel on leitud reeglite seast huvitavate ning oluliste reeglite tuvastamine {cite('silberschatz96what')}. Samuti võiksid need reeglid olla hõlpsalt tõlgendatavad ning rakendatavad. Ühed võimalikest huvitavuse kriteeriumitest ongi erinevad kitsendused, nii süntaktilised kui ka toe ning usaldusteguri mõttes. Samas nii võib tekkida suur hulk küllalt tugevaid reegleid mis ei osutu aga reaalse elu taustal küllalt huvitavateks. On välja pakutud ka eeldefineeritud mallidel põhinevaid reeglite valiku meetodeid {cite('silberschatz96what')} kui ka semantilisel lähenemisel põhinevaid meetode {cite('blake01better')}. Samas on siin ikkagi jäetud küllalt suur osa tegevusest inimese kanda ning arenguruumi veel jätkub. Töö käib ka ajadimensiooni lisamisel assotsiatsioonireeglite analüüsi. Selle näiteks võime võtta teatud tüüpi reeglid, mis kehtivad vaid kindlal ajavahemikul, näiteks kohvi ja saiakesi müüakse koos enamasti hommikutundidel. Samuti on piparkoogitaigna müük suhteliselt harvaesinev nähtus, ent detsembrikuus võib täheldada jälle vastupidist. On uuritud näiteks tsüklilisi assotsiatsioonireegleid {cite('ozden98cyclic')} ent need jäävad hätta selliste reaalsest elust pärit väidetega, nagu ", kuna tööpäevade vahelised kaugused pole konstantsed. On uuritud kalendripõhiste assotsiatsioonireeglitega seotud probleeme {cite('li01discovering,lee01mining')} ent seni pole veel päris selge, millise piirini on võimalik assotsiatsioonireegleid üldistada {cite('mannila02local')}. Ajamõõtmega tegelemisel üks huvitav lahendus on ka spetsiaalse mustrituvastusriistvara ning geneetiliste algoritmide kasutamine {cite('hetland02temporal,trom-unsupervised')}. Lahtine on ka kaubahierarhiatega tegelemise aspekt. Jaemüügis on palju valdkonnasisest teavet peidetud hierarhiliste struktuuride taha. Saku Tume ning A Le Coq Premium käivad õlle alla, õlu ja limonaad omakorda karastusjookide alla. Sedasorti üldistuste kohta käivad reeglid võivad pakkuda väga väärtuslikku üldise taseme informatsiooni. Kaubahierarhiate korral võib ülemisel tasemel olla suurem tugi ostude andmestul kui mõnel konkreetsel alamtasemel. Näiteks " ei pruugi andmebaasis piisavalt tuge omada, ent "<õlu ja krõpsud"> jälle võib. Kuigi otseselt algoritmid taolisi hierarhiaid ei toeta on välja pakutud meetodeid selle probleemi lahendamiseks {cite('holsheimer95perspective,dehaspe01discovery')}. Üldjoontes on hierarhiatega tegelemine siiski meetodi lõppkasutaja (inimese) ülesandeks jäetud. H3:cn Probleeme Probleeme tekitab ka tekkivate assotsiatsioonireeglite suur hulk, mis vajab inimese sekkumist kasulikumate reeglite identifitseerimiseks. Võib ka öelda, et suurte kaupadehulkade leidmine on oluliselt lihtsam ülesanne kui oluliste reeglite tuvastamine {cite('mannila02local')}. Andmete säilitamise poolelt valmistab probleeme algoritmide vajadus andmete maatriksikujulisele esitusele. Sageli hoitakse andmeid siiski normaliseeritud kujul, kus ostukorvid on esitatud paaridena kujul {tex('(t,i)')}. Siin {tex('t')} on ostukorvi identifikaator ning {tex('i')} on kauba identifikaator. Samuti võib olla eraldi seos konkreetse ostukorvi ja ostu sooritanud isiku, aja jms vahel. Samas on tehtud uurimistööd nn vertikaalse kaevandamise {def("",'vertical mining')} vallas, kus andmestu ongi just sellisel normaliseeritud kujul {cite('shenoy00turbocharging')} ning püütakse ära kasutada ka andmebaasisüsteemide poolt pakutavaid standardmeetodeid {cite('holsheimer95perspective')}. Hetkel käib ka töö leidmaks algoritme mis võimaldavad leida assotsiatsioone nii strktureeritud kui ka struktureerimata andmete põhjal {cite('singh97generating,singh98robust,lent97discovering')}.