Ühingu reeglid võimaldab leida mustreid seotud sündmuste vahel. Sellise reegli näiteks on väide, et ostja, kes ostab leiba, ostab ka piima. See probleem pakuti esmakordselt välja seosereeglite otsimiseks, et leida tüüpilisi supermarketites tehtud ostumustreid, nii et mõnikord nimetatakse seda ka turukorvi analüüs(turukorvi analüüs).
Olgu siis klienditehingutest koosnev andmebaas. Iga tehing– see on ostja poolt ühe külastuse käigus ostetud kaupade komplekt. Seda tehingut nimetatakse ka turukorviks. Analüüsi eesmärk on kindlaks teha järgmised sõltuvused: kui tehingus kohtab teatud elementide komplekt X, siis selle põhjal võime järeldada, et teine elementide hulk Y peaks ka selles tehingus ilmuma. Selliste sõltuvuste tuvastamine võimaldab meil leida väga lihtsaid ja intuitiivseid reegleid.
Seostusreegel koosneb kahest kutsutud üksuste komplektist tingimus(Inglise: eelnev) Ja tagajärg(Inglise: sellest tulenevalt), kirjutatud kujul X→ Y, millel on kirjas „alates X peaks Y" Seega on assotsiatiivne reegel sõnastatud järgmiselt: "Kui tingimus, siis tagajärg".
Seostusreeglite otsimisel kasutatakse näitajaid reegli olulisuse hindamiseks. Sellega seoses saame eristada reeglite tähtsuse objektiivseid ja subjektiivseid mõõtmeid. Eesmärk on sellised meetmed nagu toetus Ja usaldusväärsus, mida saab rakendada sõltumata konkreetne rakendus. Subjektiivne seotud meetmed eriline teave, mille kasutaja määratleb lahendatava probleemi kontekstis. Sellised subjektiivsed meetmed on lift Ja võimendus.
Assotsiatsioonireeglid kirjeldavad seost tingimusele ja tagajärjele vastavate objektihulkade vahel. Seda suhet iseloomustavad kaks näitajat: tugi(d) Ja usaldusväärsus(Koos).
Reegel "Alates X peaks Y" Sellel on toetada s, Kui s% tehingud kogu komplektist sisaldavad elementide komplekte X Ja Y.
Reegli kehtivus näitab tõenäosust, et X
peaks Y. Reegel "Alates X peaks Y» õiglane koos töökindlus koos,
Kui c % tehingud kogu komplektist, mis sisaldab elementide komplekti X,
Me näitame teile edasi konkreetne näide: 75% leiba sisaldavatest tehingutest sisaldagu ka piima ja 3% kõigi tehingute koguarvust sisaldab mõlemat kaupa. 75% on reegli usaldusväärsus ja 3%– see on toetus.
Lift (L) on tingimuse esinemise sageduse suhe tehingutes, mis sisaldavad ka tagajärge, ja tagajärje kui terviku esinemise sagedust. Ühest suuremad tõusuväärtused näitavad, et tingimus ilmneb tagajärge sisaldavates tehingutes sagedamini kui teistes. Võib öelda, et lift on kahe teemarühma vahelise seose üldistatud mõõt: lifti väärtuste puhul, mis on >1, on ühendus positiivne, 1 puhul puudub ja väärtuste puhul.<1 – отрицательная.
Teine reegli olulisuse mõõt on võimendus on erinevus vaadeldava sageduse vahel, millega tingimus ja tagajärg koos esinevad (s.o. seos seosele), ning tingimuse ja tagajärje esinemissageduste (tugede) korrutis eraldi.
Sellised meetmed nagu lift Ja võimendus saab kasutada järgnevaks vaadeldavate seoste hulga piiramiseks, määrates olulisuse läve, millest allapoole jäävad seosed kõrvale jäetakse.
Seostusreeglite otsimise algoritmid on loodud selleks, et leida kõik vormi „Alates X peaks Y" ning nende reeglite tugi ja usaldusväärsus peavad jääma teatud etteantud piiridesse, mida nimetatakse vastavalt miinimumiks ja maksimumiks toetus nii miinimum kui ka maksimum usaldusväärsus.
Väärtuse piirid tugi- ja usaldusparameetrid valitakse nii, et leitud reeglite arv oleks piiratud. Kui toel on suur tähtsus, siis leiavad algoritmid reeglid, mis on analüütikutele hästi teada või nii ilmselged, et sellist analüüsi pole mõtet teha. Teisest küljest toob madal tugiväärtus kaasa tohutu hulga reeglite genereerimise, mis muidugi nõuab märkimisväärseid arvutusressursse. Kõige huvitavamad reeglid leitakse siiski madala toetusläve juures, kuigi liiga madal tugiväärtus põhjustab statistiliselt põhjendamatute reeglite genereerimist. Seega on vaja leida kompromiss, mis tagab esiteks huvi
reeglid ja teiseks nende statistiline kehtivus. Seetõttu sõltuvad nende piiride väärtused otseselt analüüsitavate andmete olemusest ja valitakse individuaalselt.
Lihtsaim otsingualgoritm on see, et kõikidele seostele, mida saab andmebaasi alusel üles ehitada, määratakse tugi ja usaldusväärsus ning seejärel valitakse need, mille puhul need näitajad ületavad etteantud läve. Enamasti on selline elementaarne lahendus siiski vastuvõetamatu, kuna analüüsitavate seoste arv on liiga suur. Seega, kui valim sisaldab ainult 100 eset, on nende moodustatud seoste arv umbes 1031 ja reaalsetes olukordades (näiteks supermarketis oste analüüsides) võib arvesse võetav tootevalik ulatuda mitme tuhandeni või enamgi. . Ilmselgelt ei piisa selliseks arvutuseks ühestki arvutusvõimsusest.
Seetõttu kasutatakse praktikas seosereeglite otsimisel erinevaid tehnikaid, mis võimaldavad vähendada otsinguruumi suuruseni, mis tagab vastuvõetavad arvutiajakulud. Nüüd on üks levinumaid algoritm a priori, mis põhineb populaarse hulga kontseptsioonil (sageli esinev ainekogum). See termin tähistab subjektide kogumit, mille esinemissagedus tehingute kogukogumis ületab teatud ettemääratud taseme.
Nii et algoritm a priori sisaldab kahte etappi:
- populaarsete komplektide otsimine;
– assotsiatsioonireeglite koostamine, mis vastavad kindlaksmääratud toetuse taseme ja usaldusväärsuse piirangutele.
IN Deduktori stuudio assotsiatsiooniprobleemide lahendamiseks kasutatakse käitlejat Ühingu reeglid. See rakendab algoritmi a priori. Käsitleja nõuab sisendiks kahte välja: tehingu ID ja tehingu element.
Kaasaegsed andmebaasid on oma mõõtmetelt väga suured, ulatudes gigabaitideni ja terabaitideni ning trend on jätkuvalt kasvav. Seetõttu on seosereeglite leidmiseks vaja tõhusaid skaleeritavaid algoritme, mis võimaldavad probleemi vastuvõetava aja jooksul lahendada. Ühte neist algoritmidest käsitletakse selles artiklis. Kirjeldame Apriori algoritmi. Kasutatav terminoloogia ja märge on toodud artiklis "Sissejuhatus assotsiatsioonireeglite analüüsi".
Algoritmi rakendamiseks on vajalik andmete eeltöötlemine: esiteks redutseerida kõik andmed binaarsesse vormi; teiseks muuta andmestruktuuri.
Tabel 1. Tehingute andmebaasi tüüpiline vaade:
Tabel 2. Normaliseeritud vaade:
| TID | A | B | C | D | E | F | G | H | I | K | ... |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1001 | |||||||||||
| 1002 | 1 | ||||||||||
| 1003 |
Tabeli veergude arv on võrdne tehingukomplektis D olevate elementide arvuga. Iga kirje vastab tehingule, kus vastav veerg on 1, kui element on tehingus olemas, ja 0 muul juhul. (vt definitsioon 1). Arvesta, et tabeli algkuju võib erineda tabelis 1 näidatust. Peaasi, et andmed teisendataks normaliseeritud kujule, vastasel juhul ei ole algoritm rakendatav.
Veelgi enam, nagu tabelist näha, on kõik elemendid järjestatud tähestikulises järjekorras (kui need on numbrid, tuleks need järjestada numbrilises järjekorras). Nagu te ilmselt juba arvasite, ei tehtud seda juhuslikult. Kuid ärgem jätkem endast ette, igal asjal on oma aeg.
Niisiis, andmed on teisendatud, nüüd saame hakata kirjeldama algoritmi ennast. Nagu eelmises artiklis mainitud, töötavad sellised algoritmid kahes etapis ja Apriori algoritm, mida me kaalume, pole erand. Esimene samm on leida sageli esinevad elementide komplektid ja seejärel eraldada neist reeglid. Elementide arvu komplektis nimetatakse hulga suuruseks ja k elemendist koosnevat hulka nimetatakse k-elemendiliseks hulgaks.
Monotoonsuse vastane omadus
Sageli esinevate elementide komplektide tuvastamine on toiming, mis nõuab palju arvutusressursse ja vastavalt ka aega. Primitiivne lähenemisviis selle probleemi lahendamiseks on kõigi võimalike elementide kogumite lihtne loetlemine. Selleks on vaja O(2 |I|) tehteid, kus |I| - elementide hulk. Apriori kasutab üht tugiatribuutidest, mis väidab, et ühegi elementide komplekti toetus ei tohi ületada ühegi selle alamhulga minimaalset toetust. Näiteks 3-elemendilise komplekti (leib, või, piim) toetus on alati väiksem või võrdne 2-elemendiliste komplektide (leib, või), (leib, piim), (või, piim) toega. Asi on selles, et iga tehing, mis sisaldab (leib, või, piim), peab sisaldama ka (leib, või), (leib, piim), (või, piim) ja vastupidine pole tõsi.
Seda omadust nimetatakse monotoonsusevastaseks ja selle eesmärk on vähendada otsinguruumi mõõdet. Kui meil sellist omadust poleks, oleks mitmeelemendiliste hulkade leidmine arvutuste eksponentsiaalse kasvu tõttu praktiliselt võimatu ülesanne.
Teine monotoonsusevastase omaduse sõnastus on see, et kui elementide komplekti suurus suureneb, siis tugi väheneb või jääb samaks. Eelnevast järeldub, et iga k-elemendiline hulk on sagedane siis ja ainult siis, kui kõik selle (k-1)-elemendilised alamhulgad on sagedased.
Kõik võimalikud elementide hulgad I-st saab esitada võrena, alustades tühjast hulgast, seejärel 1-elemendilised hulgad 1. tasemel, 2-elemendilised hulgad 2. tasemel jne. Tase k tähistab k-elemendilisi komplekte, mis on seotud kõigi nende (k-1)-elemendiliste alamhulkadega.
Vaatleme joonist 1, mis illustreerib elementide komplekti I – (A, B, C, D). Oletame, et elementide komplektil (A, B) on toetus alla etteantud läve ja seetõttu pole see sage. Seejärel pole monotoonsusevastase omaduse kohaselt ka kõik selle superkomplektid sagedased ja visatakse ära. Kogu see haru alates (A, B) on taustal esile tõstetud. Selle heuristika kasutamine võib otsinguruumi oluliselt vähendada.
Apriori algoritm
Algoritmi esimeses etapis loendatakse 1-elemendilised sagedased hulgad. Selleks tuleb läbida kogu andmestik ja arvutada nende toetus, s.t. mitu korda see andmebaasis ilmub?
Järgmised sammud koosnevad kahest osast: potentsiaalselt sagedaste üksuste (nimetatakse kandidaatideks) genereerimine ja kandidaatidele toetuse arvutamine.
Ülalkirjeldatud algoritmi saab kirjutada järgmise pseudokoodina:
- F 1 = (sageli 1-elemendilised komplektid)
- jaoks (k=2; F k-1<>$\oslash$; k++) (
- C k = Apriorigen(Fk-1) // kandidaatpõlvkond
- kõikide tehingute puhul t $\epsilon$ T (
- C t = alamhulk(C k , t) // üleliigsete reeglite eemaldamine
- kõikidele kandidaatidele c $\epsilon$ C t
- c.count++
- F k = ( c $\epsilon$ Ck | c.count >= minsupport) // kandidaatide valik
- Tulemus $\cup$ F k
Kirjeldame kandidaatide genereerimise funktsiooni. Seekord pole enam vajadust andmebaasi juurde pääseda. K-elemendiliste hulkade saamiseks kasutame (k-1)-elementide komplekte, mis olid määratletud eelmises etapis ja mida sageli kohtab.
Tuletage meelde, et meie originaalkomplekti hoitakse tellitud kujul. Kandidaatide genereerimine koosneb samuti kahest etapist.
- Ühing. Iga kandidaat C k moodustatakse sagedase suuruse (k-1) komplekti laiendamisega, lisades elemendi teisest (k-1) elemendikomplektist.
Esitame selle Apriorigeni funktsiooni algoritmi väikese SQL-i sarnase päringu kujul.
sisestage C k
vali lk 1 , lk 2 , … , p.üksus k-1 , q.üks k-1
Alates F k-1 p, F k-1 q
kus p.üksus 1 = q.üksus 1, p.üksus 2 = q.üksus 2, …, p.üksus k-2 = q.üksus k-2, p.üksus k-1< q.item k-1 - Üleliigsete reeglite eemaldamine. Antimonotoonsuse omaduse põhjal tuleks kõik hulgad c $\epsilon$ C k eemaldada, kui vähemalt üks selle (k-1) alamhulkadest ei ole sage.
Pärast kandidaatide genereerimist on järgmiseks ülesandeks iga kandidaadi toetuse arvutamine. Ilmselgelt võib kandidaatide hulk olla väga suur ja see on vajalik tõhus meetod loendamine. Kõige triviaalsem viis on võrrelda iga tehingut iga kandidaadiga. Kuid see on kaugel Parim otsus. Palju kiirem ja tõhusam on kasutada lähenemist, mis põhineb kandidaatide räsipuu salvestamisel. Puu sisemised sõlmed sisaldavad räsitabeleid, mis viitavad järglastele, ja lehed sisaldavad viiteid kandidaatidele. Vajame seda puud kandidaatide toetuse kiireks arvutamiseks.
Iga kord, kui kandidaate luuakse, koostatakse räsipuu. Esialgu koosneb puu ainult juurest, mis on leht, ja ei sisalda ühtegi kandidaatkomplekti. Iga kord, kui moodustatakse uus kandidaat, sisestatakse see puu juurtesse ja nii edasi, kuni kandidaatide arv juurelehes ületab teatud läve. Niipea, kui kandidaatide arv muutub lävendist suuremaks, teisendatakse juur räsitabelis, s.o. muutub sisemiseks sõlmeks ja selle jaoks luuakse lapselehed. Ja kõik näited jaotatakse järeltulijate sõlmede vahel vastavalt komplekti kuuluvate elementide räsiväärtustele jne. Iga uut kandidaati räsitakse sisemistes sõlmedes, kuni see jõuab esimese lehe sõlme, kus seda hoitakse seni, kuni komplektide arv ületab taas läve.
Koostatakse seatud kandidaatidega räsipuu, nüüd on räsipuud kasutades lihtne iga kandidaadi toetus välja arvutada. Selleks tuleb iga tehing puust “läbi lasta” ja suurendada nende kandidaatide loendureid, mille elemendid samuti tehingus sisalduvad, s.t. C k $\cap$ T i = C k . Juurtasandil rakendatakse tehingu igale elemendile räsifunktsioon. Järgmisena rakendatakse teisel tasemel räsifunktsiooni teistele elementidele jne. K-tasemel on k-element räsistatud. Ja nii edasi, kuni jõuame leheni. Kui lehel salvestatud kandidaat on kõnealuse tehingu alamhulk, suurendage selle kandidaadi toetusloendurit ühe võrra.
Pärast seda, kui algse andmestiku iga tehing on puu kaudu läbi viidud, saab kontrollida, kas kandidaatide toetusväärtused vastavad minimaalsele lävele. Kandidaadid, kelle puhul see tingimus on täidetud, viiakse sageli esinevate kategooriasse. Lisaks peaksime meeles pidama seatud tuge, see on meile reeglite väljavõtmisel kasulik. Samade sammudega leitakse (k+1)-elemendihulgad jne.
Kui kõik sageli esinevad elementide komplektid on leitud, võite jätkata otse reeglite genereerimisega.
Reeglite väljavõtmine on vähem aeganõudev ülesanne. Esiteks, reegli usaldusväärsuse arvutamiseks piisab, kui on teada hulga enda ja reegli tingimuses sisalduva hulga tuge. Näiteks on sageli esinev hulk (A, B, C) ja me peame arvutama reegli AB $\Rightarrow$ C usaldusväärsuse. Me teame hulga enda toetust, kuid selle hulk (A, B) , mis peitub reegli tingimuses, esineb sageli ka monotoonsusevastase omaduse tõttu ja seetõttu on selle tugi meile teada. Siis saame lihtsalt usaldusväärsuse arvutada. See säästab meid tehingute andmebaasi soovimatust sirvimisest, mis oleks vajalik, kui see tugi oleks teadmata.
Reegli eraldamiseks sagedast hulgast F tuleb leida kõik selle mittetühjad alamhulgad. Ja iga alamhulga s jaoks saame formuleerida reegli s $\Rightarrow$ (F – s), kui reegli conf(s $\Rightarrow$ (F – s)) = supp(F)/supp(s) usaldusväärsus on mitte vähem kui minconfi lävi.
Pange tähele, et lugeja jääb konstantseks. Siis on usaldusväärsus olemas minimaalne väärtus, kui nimetajal on maksimaalne väärtus, ja see juhtub siis, kui reegli tingimus sisaldab komplekti, mis koosneb ühest elemendist. Kõik superkomplektid antud komplekt neil on väiksem või võrdne tugi ja vastavalt suurem usaldusväärsus. Seda omadust saab kasutada reeglite eraldamisel. Kui alustame reeglite eraldamist, võttes esmalt arvesse ainult ühte elementi reegli tingimuses ja see reegel on seda teinud vajalikku tuge, siis on kõigil reeglitel, mille tingimus sisaldab selle elemendi ülemkogumeid, ka usaldusväärtus, mis ületab määratud läve. Näiteks kui reegel A $\Rightarrow$ BCDE vastab minimaalsele usalduslävele minconf, siis vastab ka AB $\Rightarrow$ CDE. Kõikide reeglite väljavõtmiseks kasutatakse seda rekursiivne protseduur. Oluline märkus: iga sagedasest komplektist koostatud reegel peab sisaldama kõiki komplekti elemente. Näiteks kui hulk koosneb elementidest (A, B, C), siis reeglit A $\Rightarrow$ B ei tohiks arvesse võtta.
Kirjandus
- R. Agrawal, T. Imielinski, A. Swami. 1993. Kaevandamise seosed massilistes andmebaasides olevate esemete komplektide vahel. Proc. 1993. aasta ACM-SIGMOD rahvusvahelisest konverentsist. andmete haldamise kohta, 207–216.
- R. Agrawal, R. Srikant. "Ühendusreeglite kiire avastamine", Proc. 20. rahvusvahelisel VLDB konverentsil Santiagos, Tšiilis 1994. aasta septembris.
Sagedaste objektide komplektide tuvastamine on toiming, mis nõuab palju arvutusi ja seega ka aega. Apriori algoritmi kirjeldasid 1994. aastal Ramakrishnan Srikant ja Rakesh Agrawal. See kasutab ühte tugiatribuutidest, mis ütleb, et ühegi objektide komplekti toetus ei tohi ületada selle alamhulga minimaalset toetust:
Näiteks 3-objektikomplekti (õlu, vesi, krõpsud) toetus on alati väiksem või võrdne 2-objektikomplektide (õlu, vesi), (vesi, krõpsud), (õlu, krõpsud) toetusega. Seda seetõttu, et iga (õlu, vesi, krõpsud) sisaldav tehing sisaldab ka komplekte (õlu, vesi), (vesi, krõpsud), (õlu, krõpsud) ja vastupidine pole tõsi.
Apriori algoritm tuvastab sagedased komplektid mitmes etapis. Peal i-etapp, kõik sageli esinevad i-elementide komplektid. Iga etapp koosneb kahest etapist: kandidaatide genereerimine ja kandidaatide loendamine.
Mõelgem i etapp. Kandidaatide genereerimise etapis loob algoritm kandidaatide komplekti i-elemendikomplektid, mille toetust pole veel arvutatud. Kandidaatide loendamise etapis skannib algoritm tehingute komplekti, arvutades kandidaatkomplektide toe. Pärast skannimist visatakse kõrvale kandidaadid, kelle toetus on väiksem kui kasutaja määratud miinimum, ja alles jäetakse vaid sageli esinevad. i-elementide komplektid. Esimese etapi jooksul sisaldab valitud kandidaatkomplektide komplekt kõiki i-elemendi sagedased komplektid. Algoritm arvutab nende toetuse kandidaatide loendamise etapis.
Kirjeldatud algoritmi saab kirjutada järgmise pseudokoodina:
Kirjeldame algoritmis kasutatud tähistust:
Kirjeldame seda algoritmi samm-sammult.
1. samm. Määrake k= 1 ja valige kõik 1-elemendilised komplektid, mille tugi on suurem kui minimaalne kasutaja määratud Supp min .
Samm2.k = k+ 1.
Samm 3. Kui k-elemendilisi komplekte pole võimalik luua, siis lõpeta algoritm, vastasel juhul soorita järgmine samm.
Samm 6. Iga kandidaadi kohta komplektist KOOS To
suurendada toetusväärtust ühe võrra.
Samm 7. Valige ainult kandidaadid L k paljudelt KOOS To , y kelle toetusväärtus on suurem kasutaja määratud Supp min Naaske 2. sammu juurde.
Algoritmi tulemuseks on kõigi hulkade liit L k kõigi jaoks To.
Vaatleme algoritmi toimimist tabelis toodud näite abil. 6,1, mille - Supp min = 0,5. Esimeses etapis on meil järgmine kandidaatide komplekt KOOS 1 (toote identifikaatorid on märgitud) (tabel 6.5).
Tabel 5.5
Tabel 5.6.
Konstrueeritud kandidaatidest vastavad etteantud minimaalsele toetusele vaid kandidaadid 2, 4, 5 ja 6, seega:
Kolmandas etapis liigume edasi 3-elemendiliste kandidaatide loomise ja nende toetuse arvutamise juurde. Selle tulemusena saame järgmise hulga C 3 (tabel 6.7).
Tabel 5.7
See komplekt rahuldab minimaalse toetuse, seega:
L 3 = {{2,3,5}}.
Kuna 4-elemendilisi komplekte ei saa luua, on algoritmi tulemuseks komplekt:
Kandidaatide toetuse arvutamiseks peate iga tehingut iga kandidaadiga võrdlema. Ilmselgelt võib kandidaatide arv olla väga suur ja vaja on tõhusat loendusviisi. Palju kiirem ja tõhusam on kasutada lähenemist, mis põhineb kandidaatide räsipuu salvestamisel. Puu sisemised sõlmed sisaldavad räsitabeleid, mis viitavad lastele, ja lehed sisaldavad viiteid kandidaatidele. Seda puud kasutatakse kandidaatide toetuse kiireks arvutamiseks.
Räsipuu luuakse iga kord, kui kandidaate luuakse. Esialgu koosneb puu ainult juurest, mis on leht, ja ei sisalda ühtegi kandidaatkomplekti. Iga kord, kui moodustatakse uus kandidaat, sisestatakse see puu juure ja nii kuni numbrini i juurnimekirjas olevad kandidaadid ei ületa teatud künnist. Kui see juhtub, teisendatakse juur räsitabeliks, st sellest saab sisemine sõlm ja selle jaoks luuakse alamlehed. Kõik kandidaadid jaotatakse "järglaste sõlmede" vahel vastavalt komplekti kuuluvate elementide räsiväärtustele. Iga uut kandidaati räsitakse sisemistes sõlmedes, kuni see jõuab esimese lehe sõlme, kus seda hoitakse seni, kuni komplektide arv ületab taas läve.
Kui kandidaatide komplektidega räsipuu on koostatud, on lihtne iga kandidaadi toetus välja arvutada. Selleks tuleb iga tehing puust läbi lasta ja nende kandidaatide loendureid suurendada; mille elemendid sisalduvad ka tehingus, C k n T, = KOOS To . Juurtasandil rakendatakse räsifunktsiooni tehingu igale objektile. Järgmisena rakendatakse teisel tasemel räsifunktsiooni teistele objektidele jne. Kell k-m tasemel, räsitakse k-elementi ja nii edasi, kuni jõuame lehele. Kui lehel salvestatud kandidaat on kõnealuse tehingu alamhulk, suurendage selle kandidaadi tugiloendurit ühe võrra. Pärast seda, kui algse andmestiku iga tehing on puu kaudu läbi viidud, saab kontrollida, kas kandidaatide toetusväärtused vastavad minimaalsele lävele. Kandidaadid, kelle puhul see tingimus on täidetud, viiakse sageli esinevate kategooriasse. Lisaks peaksite meeles pidama ka seatud tuge, mis on reeglite ekstraheerimisel kasulik.
Otsimiseks kasutatakse samu samme (k + 1)-elemendihulgad jne.
TARKVARASÜSTEEMI ARENDAMINE APRIORI ALGORITMI ALUSEL OTSIMISEKS ÜHENDUSREEGLID
Sizikh Anna Faritovna 1, Bazhenov Ruslan Ivanovitš 2
1 Sholom Aleichemi nimeline Amuuri Riiklik Ülikool, üliõpilane
2 Sholom Aleichem Priamuri Riiklik Ülikool, pedagoogikateaduste kandidaat, dotsent, informaatika ja arvutitehnika osakonna juhataja
annotatsioon
Artiklis tutvustatakse arengut tarkvarasüsteem, mis rakendab seosereeglite otsimist. Apriori algoritm ja selle rakendamine Delphi keskkond. Uuringus kasutati reaalseid müügiandmeid. Väljatöötatud programmi saab kasutada õppetööks kursustel “Intelligentsed infosüsteemid”, “Intellektuaalne andmete analüüs”.
APRIORI ALGORITMI ALUSEL PÕHINEV TARKVARASÜSTEEMI OTSINGU ÜHENDUSE REEGLIDE ARENDAMINE
Sizikh Anna Faritovna 1, Bazhenov Ruslan Ivanovitš 2
1 Sholom-Aleichem Priamursky Riiklik Ülikool, üliõpilane
2 Sholom-Aleichem Priamursky Riiklik Ülikool, pedagoogikateaduste kandidaat, dotsent, arvutiteaduse osakonna juhataja
Abstraktne
Artiklis tutvustatakse assotsiatsioonireeglite otsingut rakendava tarkvarasüsteemi väljatöötamist. Näitab apriori algoritmi ja selle rakendamist Delphikeskkonnas. Uuringus kasutati reaalseid müügiandmeid. Väljatöötatud programmi saab kasutada kursuste „Intelligentsed infosüsteemid“, „ Andmete kaevandamine».
Bibliograafiline link artiklile:
Sizykh A.F., Bazhenov R.I. Tarkvarasüsteemi arendamine seosereeglite otsimiseks apriori algoritmi alusel // Kaasaegne Teaduslikud uuringud ja innovatsiooni. 2014. nr 10. 1. osa [Elektrooniline ressurss]..03.2019).
Andmekaeve on üks prioriteetsed valdkonnad kaasaegsed uuringud. Tohutu hulk teavet kaasaegses raamatupidamises infosüsteemid nõuab nende mõistmist ja teadmiste ammutamist, mis võimaldab teil koostada soovitusi äritegevuse parandamiseks. Kirjeldatud probleemi lahendamise meetodiks võib olla assotsiatsioonireeglite otsing, mille tulemusi kasutatakse ostude, reklaamikulude jms optimaalseks planeerimiseks.
Assotsiatsioonireeglite otsimise probleemiga on tegelenud erinevad teadlased. A.Shahidi arvustas üldised probleemid otsida assotsiatsioonireegleid. M.G.Aseev, V.A. Duke näitas andmetest kui-siis reeglite leidmise probleeme. Süsteemi "kui-siis" tüüpi ärireeglite leidmiseks transpordilogistika probleemides töötasid välja I. A. Minakov ja S. I. Volman. A.P. Kornilkov, T.V. Khabibulina näitasid assotsiatiivsete reeglite otsimise rakendamist keele abil php programmeerimine. Assotsiatsioonireeglite interaktiivset analüüsi andmebaasides uuris A.V., A.S. E.V Galkina uuris ärianalüüsi ja -kontrolli assotsiatsioonireegleid. M.V Tereshonok kasutas võrgukoormuse analüüsimiseks seosereeglite otsingut mobiilside. Assotsiatsioonireeglite otsimise meetodit andmete töötlemisel hajutatud infosüsteemides näitas T.Yu. A.Yu Krakovetsky kasutas tugevate andmekogumite ja fp-puu põhjal seostusreeglite otsimise meetodit. A.N. Šabelnikov, V.A. Šabelnikov uuris anomaaliate otsimist tehnilistes aegridade andmebaasides. V.M Grinyak jt kirjeldasid infotehnoloogiat hooajamüügi planeerimiseks. R.I. Bazhenov, V.A. Veksler töötas välja konfiguratsiooni 1C: Enterprise süsteemi jaoks ennustavaks analüüsiks koos seosereeglite otsimise toega. Välisteadlased kirjeldasid meetodi rakendamist erinevates valdkondades.
Seostusreeglite otsingu rakendamiseks valiti üsna lihtne Apriori algoritm. Kirjeldame seda.
Seal on andmebaas, mis koosneb klientide tehingutest. Iga tehing on ostja poolt korraga ostetud kaupade komplekt.
Olgu I = (i 1 , i 2 , i 3 , …i n ) – kaupade või elementide kogum (komplekt). Olgu D tehingute hulk, kus iga tehing T on I, T elementide hulkI. Iga tehing on binaarvektor, kus t[k]=1, kui i k element on tehingus olemas, vastasel juhul t[k]=0. Tehing T sisaldab X-i, mõnda elementide komplekti I-st, kui XT. Assotsiatiivset reeglit nimetame implikatsiooniks X Y, kus X I, Y I ja X Y = . Reegel X Y-l on tugi s (toetus), kui s% tehingutest D-st sisaldab X-i Y, supp(X Y) = supp(X Y). Reegli kehtivus näitab tõenäosust, et X viitab Y-le. Reegel XY on tõene usaldusega c, kui c% tehingutest D-st, mis sisaldab X-i, sisaldab ka Y, conf(X Y) = supp(X Y)/supp(X) .
Töötati välja programm, mis rakendab Delphis Apriori algoritmi. Näitame põhiprotseduuri.
funktsioon TForm1.gen(cand: TList) : TList;
var
i, j, k: täisarv;
set_len: täisarv; (Komplekti ühisosa pikkus kombineerituna)
tSet, tSet1, tSet_new: PProdSet;
new_cand: TList;
võrdne: Boolean;
alustada
{ Uus nimekiri komplektid)
new_cand:= TList.Create;
kui cand = null siis
alustada
(Üksikkomplektid)
i jaoks:= 0 kaupadele.Loenda – 1 tee
alustada
(Uus kandidaat)
Uus(tSet);
SetLength(tSet^.Items, 1);
tMäära^.Üksused := i;
tSet^.podder:= 0;
new_cand.Add(tSet);
lõpp;
lõpp
muidu
alustada
(Mitmeelemendilised komplektid)
(Kui loendis on rohkem kui üks komplekt)
kui cand.Arv > 1 siis
alustada
for i:= 0 kuni cand.count – 1 do
alustada
(Esmalt seadistatud ühendamiseks)
tSet:= cand.Items[i];
(ühine osa pikkus)
set_len:= Kõrge(tSet^.elemendid);
j jaoks:= i + 1 kuni cand.count – 1 do
alustada
(Teine komplekt kombineerimiseks)
tSet1:= cand.Items[j];
if set_len võrdne:= true
muidu
alustada
(komplektide ühiste osade võrdlemine)
võrdne:= tõsi;
k:= 0 jaoks set_len - 1 do
if tSet^.Items[k] tSet1^.Items[k] siis
võrdne:= vale;
lõpp;
kui võrdne siis
alustada
(Uus komplekt)
Uus(tSet_uus);
tSet_New^.podder:= 0;
(uue komplekti pikkus)
SetLength(tSet_new^. Items, set_len + 2);
(Kopeerige esimene komplekt)
k:= 0 puhul High(tSet^.items) tehke
alustada
tSet_new^.Items[k] := tSet^.items[k];
lõpp;
(Lisage ülejäänud osa teisest komplektist)
tSet_new^.Items := tSet1^.items;
(Lisama uus komplekt kandidaatide nimekirja)
new_cand.Add(tSet_new);
lõpp;
lõpp;
lõpp;
lõpp;
Andmed esitas Birobidzhanis asuv ettevõte. Need laaditi alla 1C:Enterprise 8 süsteemist ja kujutavad endast 2014. aasta esimese kvartali müügiaruannet. Andmeid töödeldi ja esitati .csv-vormingus (joonis 1).
Joonis 1 – Analüüsi sisendandmed
Programmi põhiaken on näidatud joonisel 2.
Joonis 2 – Laaditud andmetega programmiaken
Pärast algoritmi käivitamist on vaja valida indikaatorid, mille järgi arvutus tehakse (joonis 3).
Joonis 3 – indikaatorite valimise aken
Pärast analüüsi kuvatakse saadud reeglid eriline ala(joonis 4).
Joonis 4 – Programmi aken pärast andmetöötlust
joonis 5 – Tekstifail tulemustega
Uuringu tulemusena saadud ühingureeglid anti üle ettevõtte juhtkonnale otsustamiseks.
Seega töötati see välja lihtne programmühenduse reeglite otsimiseks. Uuringu käigus saadud materjale saab praktikas kasutada 1C:Enterprise'ist allalaaditud andmete analüüsimiseks ja vastavate laboritööd kursustel “Intelligentsed infosüsteemid”, “Andmekaeve”.
Bibliograafia
- Shahidi A. Sissejuhatus assotsiatsioonireeglite analüüsi. URL: http://www.basegroup.ru/library/analysis/association_rules/intro/ (vaadatud 29. septembril 2014)
- Aseev M.G., hertsog V.A. Kui-siis reeglite otsimine andmetest: probleemid ja väljavaated // Proceedings of SPIIRAS. 2005. T. 2. nr 2. Lk 76-85.
- Minakov I.A., Volman S.I. Süsteem "kui-siis" tüüpi ärireeglite leidmiseks transpordilogistika ülesannetes // Infotehnoloogiad. 2007. nr 12. Lk 35-42
- Kornilkov A.P., Khabibulina T.V. Assotsiatiivsete reeglite otsingu rakendamisest php programmeerimiskeele abil // Moodne tehnoloogia ja tehnoloogia. 2014. nr 5 (33). Lk 13.
- Bondarenko A.V., Gudkov A.S. Andmebaaside seostamisreeglite interaktiivne analüüs // Arvuti- ja infotehnoloogiate bülletään. 2006. nr 10. Lk 42-45.
- Galkina E.V. Assotsiatiivsed reeglid ärianalüüsis ja -kontrollis // Vene ettevõtlus. 2013. nr 9 (231). lk 111-117.
- Tereshonok M.V. Ühenduse reeglite otsimine mobiilsidevõrkude koormuse analüüsimisel // Elektrosvyaz. 2008. nr 6. Lk 32-33.
- Gorokhova T. Yu. Assotsiatsioonireeglite otsimise metoodika andmete töötlemisel hajutatud infosüsteemides // Maailmas teaduslikud avastused. 2010. nr 4-11. lk 107-109.
- Krakovetsky A. Yu. Tugevate andmekogumite ja fp-puu põhjal seostusreeglite otsimise meetod // Vinnitsa Riikliku Tehnikaülikooli teaduslikud tööd. 2008. nr 1. Lk 2.
- Šabelnikov A.N., Šabelnikov V.A. Anomaaliate otsimine tehnilistes aegridade andmebaasides // Lõuna-Föderaalülikooli uudised. Tehnikateadus. 2008. T. 81. Nr 4. Lk 167-173.
- Grinyak V.M., Kogai E.I., Semenov S.M. Infotehnoloogia hooajamüügi planeerimiseks // Uute võimaluste territoorium. Vladivostokski bülletään riigiülikool majandus ja teenindus. 2010. nr 2. Lk 191-198
- Bazhenov R.I. Intellektuaal infotehnoloogia. Birobidzhan: PSU nime saanud. Sholom Aleichem, 2011. 176 lk.
- Veksler V.A., Bazhenov R.I. Nomenklatuuriüksuste seoste määramine 1C:Enterprise 8.3 abil // Kaasaegne teadusuuringud ja innovatsioon. 2014. nr 7 (39). lk 45-49.
- Bazhenov R.I., Veksler V.A. Tarbijakorvide analüüs 1C: Ettevõtlus ABC analüüsi näitel // Informatiseerimine ja suhtlus. 2013. nr 5. Lk 117-123.
- Bazhenov R.I., Veksler V.A. XYZ analüüsi rakendamine aastal programmi kood sisemine programmeerimiskeel 1C:Enterprise 8.3 // Informatiseerimine ja suhtlus. 2014. nr 1. Lk 37-42.
- Bazhenov R.I., Veksler V.A., Grinkrug L.S. RFM analüüs kliendibaas V rakenduse lahendus 1C:Enterprise 8.3 // Informatiseerimine ja side. 2014. nr 2. Lk 51-54.
- Xiao F., Fan C. Andmekaeve hooneautomaatikasüsteemis hoone töövõime parandamiseks // Energy and Buildings. 2014. nr 75. lk 109-118.
- Guo Z., Chi D., Wu J., Zhang W. Uus tuulekiiruse prognoosimise strateegia, mis põhineb kaootilise aegridade modelleerimise tehnikal ja Apriori algoritmil // Energy Conversion and Management. 2014. nr 84. Lk.140-151.
AIS-i algoritmis genereeritakse mitme komplekti kandidaadid ja loendatakse neid andmebaasi skaneerimise ajal.
SETM-i algoritm. Selle algoritmi loomise ajendiks oli soov kasutada SQL-keelt sageli esinevate tootekomplektide arvutamiseks. Sarnaselt AIS-i algoritmiga genereerib SETM andmebaasi teisenduste põhjal ka kandidaate. Tavalise liitumisoperatsiooni kasutamiseks SQL keel Kandidaatide genereerimiseks eraldab SETM kandidaatide genereerimise nende loendamisest.
AIS-i ja SETM-i algoritmide miinuseks on liigne kandidaatide genereerimine ja ülelugemine, mis selle tulemusena ei osutu sagedasteks. Nende jõudluse parandamiseks pakuti välja Apriori algoritm.
Töö sellest algoritmist koosneb mitmest etapist, iga etapp koosneb järgmistest etappidest:
- kandidaatide moodustamine;
- kandidaatide loendamine.
Kandidaatide moodustamine(kandidaatide genereerimine) - etapp, kus algoritm andmebaasi skaneerides loob i-elemendi kandidaatide komplekti (i on etapi number). Kandidaadi toetust praeguses etapis ei arvestata.
Kandidaatide loendamine(kandidaatide loendamine) - iga i-elemendi kandidaadi toetuse arvutamise etapp. Siin lõikame ära ka kandidaadid, kelle toetus on miinimumist väiksem, kasutaja installitud(min_sup). Ülejäänud i-elementide komplekte nimetame sageli esinevateks.
Vaatleme Apriori algoritmi toimimist andmebaasi D näitel. Algoritmi toimimise illustratsioon on näidatud joonisel fig. 15.1. Minimaalne toetuse tase on 3.
Riis.
15.1.
Esimeses etapis moodustatakse üheelemendilised kandidaadid. Järgmisena arvutab algoritm toe üksikutele komplektidele. Komplektid, mille tugitase on väiksem kui kehtestatud, see tähendab 3, lõigatakse ära. Meie näites on need hulgad e ja f, mille toetus on võrdne 1-ga. Ülejäänud kaubahulki peetakse sageli esinevateks üksikuteks kaubahulkadeks: need on hulgad a, b, c, d. Järgmiseks moodustatakse kaheelemendilised kandidaadid, arvutatakse nende toetus ja lõigatakse ära hulgad, mille toetustase on alla 3, ülejäänud kaheelemendilised kaubahulgad, mida loetakse sageli esinevateks kaheelemendilisteks komplektideks ab, ac, bd. , osa võtma edasine töö
algoritm. Kui me vaatame algoritmi toimimist sirgjooneliselt, viimane etapp
algoritm moodustab kolmeelemendilised kaupade komplektid: abc, abd, bcd, acd, arvutab nende toe ja lõikab ära hulgad, mille toetustase on väiksem kui 3. Kaupade hulka abc võib nimetada sageli esinevaks.
