Tutkielman kokeellisessa osiossa suoritettiin assosiaatioanalyysi vähittäistavarakaupan myyntipisteessä muodostuneelle transaktiodatalle. Tiedonlouhintaongelmaa lähesty-tään Maimonin & Roachin esittelemän 9-portaisen KDD-prosessin pohjalta, joka on esitetty sivulla 51 kuvassa 11 (Mainmon & Roach, 2005). KDD-prosessin mukaisesti työssä tutustutaan ensin aihealueeseen, jolla tiedonlouhintaprosessi tapahtuu. Tähän on hyödynnetty vähittäiskaupan kokonaisvalintaisten kassa- ja raportointijärjestelmien kehittäjän ja tutkielman toimeksiantajan työntekijöiden tietotaitoa. Tutkielman kokeel-lista osiota ei toteuteta yhdelle asiakkaalle kohdennettuna tiedonlouhintatehtävänä, vaan tarkoituksena on tutkia ja kartoittaa mahdollisuuksia sekä kiinnostusta tiedon-louhintaa kohtaan vähittäiskaupan pienempien toimijoiden keskuudessa.
Useat pienistä tai keskisuurista vähittäiskaupan yrityksistä eivät tallenna asiakastietoja, joten monet asiakkaan identifioimiseen keskittyvät tiedonlouhintatehtävät kuten asia-kaspoistuma-analyysi tai asiakasprofilointi jätetään tässä tutkielmassa tarkastelematta.
Tutkielman yhteistyötahon johdon kanssa käydyn keskustelun perusteella on järkevää lähteä liikkeelle transaktiodatasta, jota jokaisen asiakkaamme tietokantaan tallentuu lähes joka päivä lisää. Toinen perusteltava syy transaktiodatan käyttöön on sen ano-nymiteetti. Datasta ei kyetä yksilöimään ostoksen tehnyttä henkilöä, koska esimerkiksi luottokortin numeroa ei käytetä asiakkaan identifioimiseen. Valveutuneimmat kansa-laiset tiedostavat tämän päivän tietoyhteiskunnan voimavarat hyvin, eivätkä välttämät-tä anna enää tietojaan käytetvälttämät-täväksi kaikille toimijoille. Tämän vuoksi ongelmaa lähes-tytään myös henkilön identiteetin suojaamisen kannalta. (Provost & Fawcett, 2013).
Oikeus yksityisyydensuojaan on ihmisen perusoikeus. Henkilötietojen käsittelyyn vai-kuttavat monet lait, joka tekevät tietojen käsittelystä näin ollen säädellympiä ja turva-tumpia. Henkilötietojen suojasta säädetään Suomen perustuslain (731/1999) 10 §:n mukaan. Kansainväliset säännökset ja Euroopan unionin normit tai muut kansainväli-set säädökkansainväli-set voivat myös vaikuttaa henkilötietojen käsittelyyn. Yksityisyydensuojaan vaikuttavat konkreettisesti useat säännökset kuten esimerkiksi Suomen
henkilötietola-ki (523/1999). Suomen liikenne- ja viestintäministeriön tekemässä selvityksessä (Alanko & Salo, 2013) todetaan oikeusturvan valvomisen muodostuvan tulevaisuuden tietoyhteiskunnassa haastavaksi. Ilmiönä data ja big data koetaan yleisesti mielenkiin-toisena ja tärkeänä, koska sitä pidetään muutosvoimaisena ja Suomen kilpailukyvyn parantajana. Useille organisaatioille big data on uusi ja hankalasti lähestyttävä asia ja sitä kokonaisvaltaisesti hyödyntävää osaamista on markkinoilla tarjolla vähän. Näi-denkin asioiden pohjalta tietosuoja voi olla vaarassa kärsiä. (Alanko & Salo, 2013.) Massachusetts Institute of Technologyssä (MIT) tehdyssä tutkimuksessa (Hardesty, 2015) todetaan ihmisen henkilöllisyyden yksilöimiseen tarvittavan kolme luottokort-tiostosta, yksi päivitys kuvapalvelu Instagramissa sekä yksi päivitys pikaviestipalvelu Twitterissä. Tarkkuus henkilön oikein tunnistamiselle edellä esitettyjen toimenpiteiden jälkeen on 94 prosenttia. Identifioimiseen ei käytetty nimeä, osoitetta, luottokortin numeroa tai muuta yksilöivää tekijää. Siten 90 prosenttia 1,1 miljoonan käyttäjän muodostamasta luottokorttidatasta voitiin yksilöidä. Data sisälsi kauppojen nimet ja sijainnin, jossa ostos on tehty sekä päivämäärän ja summan. Samalla kortilla tehdyt ostokset merkattiin satunnaisella tunnistenumerolla. Edellä mainittu tutkimus osaltaan selvittää, kuinka helppoa henkilön yksilöiminen usean tietolähteen datasta on tämän-hetkisillä työkaluilla. Tämän pro gradu –tutkielman kokeellisessa osiossa keskitytään anonyymin datan tarkasteluun, jotta henkilön yksityisyydensuoja olisi turvattu.
Kuva 11. Tiedonlouhintaprosessin vaiheet. Mukailtu lähteestä Mainmon & Roach, 2014.
4.1! Datan valinta ja kuvailu
Useissa yrityksissä muodostuu paljon dataa päivittäisten toimintojen johdosta. Vähit-täiskaupassa tämä tarkoittaa esimerkiksi kassapisteiden keräämää tietoa ostetuista tuot-teista, kanta-asiakkaista ja maksutapahtumista. Tutkielman kokeellinen osio käsittelee ostoskoridataa eli tuotejoukkoa, jonka yksittäinen asiakas on ostanut. Taulukko 1 ku-vaa tällaista ostoskoridataa, jossa jokainen rivi on erillinen transaktio. Jokainen rivi kuvaa yhden asiakkaan yhdellä kertaa ostamaa tuotejoukkoa. Taulukon sarakeotsikko TID tarkoittaa transaktionumeroa, joka erottelee transaktiot yksilöidyiksi tapahtumik-si. Tällaiseen datan louhintaan käytetään usein apuna assosiaatioanalyysia, jonka avul-la suuresta ostoskoridatajoukosta voidaan löytää mielenkiintoisia linkkejä alkioiden välille. Nämä mielenkiintoiset yhteydet alkioiden välillä voidaan esittää assosiaatio-sääntöjen tai kattavan joukon avulla. (Provost & Fawcett, 2013.) Assosiaatioassosiaatio-sääntöjen ja kattavan joukon muodostaminen esitellään tulevissa kappaleissa tarkemmin.
2.#Datan#valinta#
3.#Esiprosessoin2#
4.#Muuntaminen#
5,6,7.#Tiedonlouhinta#
8.#Arvioin2#
9.#Tiedon#löytäminen#
(visualisoin2#ja#
integroin2)#
1.#Toimialueen##
ymmärtäminen#
ja#suunniIelu#
(datan#tutkiskelu)#
#
Taulukko 1. Transaktioissa esiintyviä alkiojoukkoja.
TID Alkiot
1 {maitoa, piimää}
2 {maitoa, piimää, leipää}
3 {juustoa, tomaattia}
4 {tomaattia, leipää}
Tämän tutkielman kokeelliseen osioon valittu yritys on pieni päivittäistavarakauppa, jolla on yksi myymälä. Analysoitavan yrityksen tuoterekisterissä on yhteensä 22 010 tuotetta. Kanta-asiakasjärjestelmää kyseisessä vähittäistavarakaupassa ei ole käytössä.
Rekisteröityjä asiakkaita on yhteensä 442, joista suurin osa on yritysasiakkaita. Tässä tutkielmassa ei kuitenkaan suoriteta asiakastietoihin perustuvaa tiedonlouhintaa. Tut-kielmassa käytettävä data on kerätty 727 päivän ajalta. Kuitin keskiostos on 9,7 euroa.
Alkuperäisessä datassa on 911 054 tuotemyyntiriviä, jotka muodostavat yhteensä 165 137 erillistä kuittia eli transaktiota.
4.2! Datan esiprosessointi ja muuntaminen
Tutkielmassa esitetyssä kokeellisessa osassa on tiedonlouhintaprosessi, jossa data esi-prosessoidaan ja muunnetaan tarvittaessa oikeaan muotoon. Tuotemyyntidataan tallen-tuu useita tietoja, kuten esimerkiksi tuotenumero, tuotenimi, summa, viimeisin myyn-tipäivä, tavarantoimittaja, tuoteryhmä. Assosiaatioanalyysiin siitä, mitä tuotteita esiin-tyy samalla kuitilla, tarvitaan kuitenkin vain kuitin numero sekä tuotteen identifioiva tekijä, kuten nimi tai tuotenumero. Assosiaatioanalyysin jälkeen tarkasteluun on mah-dollista tarvittaessa yhdistää muita tietoja kuitin numeron ja tuotteen perusteella.
Esiprosessoinnissa datasta on järkevää poistaa muutamia tuotteita. Esimerkiksi tuot-teet, kuten pullopantti, tuote alv tai muovikassi poistetaan datasta. Datajoukosta on järkevää poistaa lopputulosta mahdollisesti väärentävät tiedot, kuten ’tuote alv’. Jokai-sella tuotteella on olemassa arvonlisävero, joten arvonlisäverosta muodostuvat assosi-aatiosäännöt olisivat turhaa tietoa. Tässä tutkielmassa hyödynnetään R:n ohjelmisto-ympäristöä. Tietokanta on R:n RODBC-kirjaston kautta helppo yhdistää R:n, josta
data voidaan hakea suoraan SQL-kyselyllä ja tehdä samalla haluttua esiprosessointia.
Tietoa keräävän ohjelmiston tietokantana toimii Pervasiven PSQL-tietokanta, minne transaktiotiedot kerätään. Transaktiotiedot kerääntyvät esivaiheessa peräkkäistiedos-toon, josta ne ajetaan myynninpäivityksen yhteydessä tietokantaan.
Ostoskorianalyysiin käytettävä apriori-algoritmi on laskennallisesti raskas toteuttaa, joten transaktioiden määrään pienentäminen on suotavaa. Esiprosessoinnin jälkeen, jossa ennalta määriteltyjä tuotenimiä poistettiin datasta, on tuotemyyntirivien määrä pienentynyt 553 465 kappaleeseen. Erillisten tuotemyyntirivien määrää on siis saatu supistettua lähes 40 prosenttia. Erillisiä kuitteja eli transaktiota esiprosessoidussa da-tassa on 161 543.
4.3! Assosiaatioanalyysi
Esiprosessoinnin jälkeen toteutetaan itse tiedonlouhinta, joka vastaa kuvassa 6 kohtia 5, 6 ja 7. Tässä tiedonlouhinnan vaiheessa valitaan käytettävät menetelmät ja mallit tiedonlouhinnan suorittamiseen. Tässä tutkielmassa toteutettava kokeellinen osio käsit-telee assosiaatioanalyysia sovellettuna ostoskoridataan. Sovellettaessa assosiaatio-analyysia ostoskoridataan on huomioitava kaksi asiaa. Ensinnäkin hahmojen löytämi-nen laajasta transaktiodatasta on laskennallisesti erittäin haastavaa. Toiseksi täytyy huomioida löydettyjen hahmojen luotettavuus, sillä ne voivat ilmentyä sattumalta.
(Kotu & Deshpande, 2014.) Aluksi esitellään assosiaatioanalyysiin liittyvä perus ter-minologia, sekä formaaleja esitystapoja. Näiden jälkeen edetään apriori-algoritmin soveltamisen kautta vähittäiskaupan transaktiodatan käsittelyyn ja assosiaatiosääntöjen muodostamiseen.
Ostoskoridata voidaan esittää binäärimuodossa, jolloin 1 tarkoittaa, että alkio esiintyy joukossa, kun taas 0 tarkoittaa, että alkio ei kuulu joukkoon. Taulukossa 2 on kunkin
alkion esiintymä transaktiossa kuvattu binäärilukujen avulla. Olkoon '(joukko18 alkioi-ta ' = )*, ),, … , ). . Olkoon / joukko transaktioita / = 0*, 0,, … , 0. . Jokainen transaktio on uniikki ja sisältää joukon ' alkioista muodostuvan osajoukon. Jos esi-merkiksi alkiojoukkoon kuuluu 3 alkiota, kuten Taulukossa 1 transaktio ID:llä kaksi on kuvattu {ID)0JD, K))Iää, MN)Kää}, niin joukko on 3-alkiojoukko19.
Assosiaatiosääntö on implikaatio 1 ⟶ 3, missä 1, 3( ⊆ '(ja 1 ∩ 3 = (∅. Määritellään säännöille tukiarvo20 20 %, joka sääntöjen tulee toteuttaa. Tukiarvo määrittelee, kuin-ka monessa tapahtumassa säännön tulee esiintyä, jotta se on hyväksyttävä. Tukiarvoa käytetään hyödyksi, koska suuri osa säännöistä voi esiintyä aivan sattumalta. Myös liiketoiminnan kannalta ajateltuna ei ole taloudellisesti järkevää mainostaa harvemmin yhdessä ostettuja tuotteita. Tukiarvoa käytetään rajaamaan ulos mielenkiinnottomat säännöt (Kotu & Deshpande, 2014).
QRS)DTUJ = (V(1 ∪ 3)
X (6)
Luotettavuusarvo21 kuvaa säännöstä muodostetun päättelyn luotettavuutta. Olkoon annettu sääntö 1( ⟶ (3. Mitä korkeampi luotettavuusarvo, sitä todennäköisemmin
18 Tunnetaan myös nimellä itemset.
19 Tunnetaan myös k-itemset, missä k = alkioiden lukumäärä.
20 Tunnetaan myös nimellä support.
21 Tunnetaan myös nimellä confidence.
Taulukko 2. Harva binäärimatriisi transaktiodatasta
TID maitoa piimää leipää juustoa tomaattia
1 1 1 0 0 0
2 1 1 1 0 0
3 0 0 0 1 1
4 0 0 1 0 1
3(esiintyy transaktioissa jotka sisältävät 1:(C. Luotettavuusarvo arvioi myös ehdollista todennäköisyyttä tapahtumalle 3, kun 1 on annettu (Kotu & Deshpande, 2014).
ZRJ0N00DURR&DTUJ = (V(1 ∪ 3) V(1) (
(7)
Assosiaatiosääntöjen löytäminen voidaan kuvata formaalisti seuraavalla tavalla: on annettu joukko Q, joka sisältää transaktioita. Etsitään kaikki säännöt joilla tukiarvo ≥ I)C&RK ja luotettavuusarvo ≥ I)CGJC\, missä I)C&RK ja I)CGJC\ ovat annettuja raja-arvoja. Tukiarvon ja luotettavuusarvon lisäksi monesti sääntöjen kiinnostavuuden mittaamiseen käytetään myös nostearvoa22. Korkean luotettavuusarvon omaavat sään-nöt voivat joskus olla harhaanjohtavia, koska luotettavuusarvo ei ota huomioon raussäännön tukiarvoa. Tähän ongelmaan voi tuoda apua nostearvo, joka laskee seu-raussäännön luotettavuusarvon ja tukiarvon välisen suhteen. (Kotu & Deshpande, 2014.)
XJ&0NDTUJ = (G(] ⟶ ^)
&(^)
(8) Assosiaatiosääntöjen tuloksia on tulkittava varoen. Muodostuneet säännöt eivät vält-tämättä suoranaisesti tarkoita syy-seuraussuhdetta eli kausaliteettia. Sen sijaan muo-dostuneet säännöt ehdottavat vahvaa yhdessä esiintymisen suhdetta alkioiden välillä.
Kausaliteetti vaatii tarkempaa tietämystä syystä ja muista vaikuttavista tekijöistä da-tassa. Tyypillisesti kausaliteettiin tarvitaan ajan mittaan useita esiintymiä, jotta voi-daan ajatella suhteiden muodostuneen alkioiden välille. Kausaliteetin sisältävänä esi-merkkinä voidaan ajatella esimerkiksi otsonikadon vaikutusta ilmastonlämpenemi-seen. (Kotu & Deshpande, 2014.)
22 Tunnetaan myös nimellä lift.
Useissa assosiaatiosääntöjen louhinta-algoritmeissa ongelman käsittely hajautetaan yleensä kahteen osaan:
1.! Etsitään kaikki annetun raja-arvon (I)C&RK) omaavat alkiojoukot ja kutsutaan muodostunutta joukkoa kattavaksi joukoksi.
2.! Käytetään edellisen vaiheen muodostamaa kattavaa joukkoa assosiaatiosääntö-jen erottamiseen. Muodostettuja sääntöjä kutsutaan vahvoiksi säännöiksi.
Kattava joukko on siis eri asia kuin assosiaatiosäännöt ja ne tulee käsitellä erillisinä asioina (Kotu & Deshpande, 2014). Kattavan joukon muodostaminen esitellään seu-raavassa kappaleessa. Assosiaatiosääntöjen muodostaminen kattavan joukon alkioiden perusteella käsitellään kappaleessa 4.2.3.
Apriori on usein esiintyvien tapahtumajoukkojen louhintaan ja assosiaatiosääntöjen muodostukseen kehitetty algoritmi, jonka esitteli ensimmäisen kerran Agrawal & Sri-kant (1995). Apriori-algoritmin nimi perustuu siihen, että se käyttää aikaisemmin mää-riteltyä tietoa hyödykseen. Apriori-algoritmin pääperiaate on, että jos tapahtumajouk-ko on usein esiintyvä, myös sen osajoutapahtumajouk-kot ovat usein esiintyviä. Toisaalta, jos tapah-tumajoukko on harvinainen, myös sen ylijoukot ovat harvinaisia. Apriori-algoritmin hyvä puoli on sen täydellisyys. algoritmi löytää siis kaikki säännöt. Apriori-algoritmi hyödyntää leveyshakua, jossa puurakenteen saman tason kaikki solmut käy-dään läpi ennen siirtymistä seuraavalle tasolle. (Agrawal & Srikant, 1995.) Apriori-algoritmia käytetään tutkielman kokeellisessa osiossa ja algoritmin toimintaan pereh-dytään syvemmin tulevissa kappaleissa.
4.3.1! Kattavan joukon muodostaminen
Kattava joukko23 on yksinkertaisesti joukko alkioita, jotka esiintyvät yhdessä usein.
Kattavan joukon muodostamisen tavoite on löytää kaikki I)C&RK raja-arvon
23 Tunnetaan myös nimellä frequent itemset.
vat alkiojoukot. Kattavan joukon muodostus on yleinen osa assosiaatioalgoritmeja, mutta se on laskennallisesti raskas operaatio. Kompleksisuuden vähentämiseen käyte-tään karsimistekniikoita, joita tässä tapauksessa on kaksi kappaletta. Karsimistekniikat esitellään tässä kappaleessa. Tukiarvon avustuksella voidaan pienentää löydettyjen kandidaattijoukkojen määrää kattavan joukon muodostuksen aikana. Tukiarvon käyt-täminen kandidaattijoukkojen karsimiseen pohjautuu seuraavaan teoreemaan, apriori-seen periaatteeapriori-seen:
Jos alkiojoukko on kattava, jokainen sen alijoukoista on kattava
Apriorisen periaatteen selventämiseksi ajatellaan, että {D, F, G} on kattava alkiojoukko.
Jokainen transaktio joka sisältää alkiojoukon {D, F, G}, sisältää myös alijoukot {DF}, {DG}, {FG}, {D}, {F} ja {G}. Eli jos {D, F, G} on kattava, myös sen alijoukot ovat katta-via. Tämä toimii myös käänteisesti eli, jos {D, F} ei ole kattava ei myöskään mikään sen ylijoukoista ole kattava. Tätä kutsutaan luotettavuusarvoon perustuvaksi karsin-naksi24. Apriori-algoritmi on ensimmäinen assosiaatiosääntöjen louhimiseen käytetty algoritmi, joka käyttää luotettavuusarvoon perustuvaa karsintaa kandidaattijoukon kasvamisen kontrolloimiseen. Tukiarvolla on anti-monotoninen (anti-monotone) omi-naisuus, jonka perusteella joukon tukiarvo ei koskaan ylitä alijoukkojensa tukiarvoa.
(Kotu & Deshpande, 2014.)
Määritellään seuraavaksi monotonisuuden käsite. Olkoon ' joukko alkioita ja _ = 2` potenssijoukko25 joukosta '. \ on monotoninen jos
∀1(, 3( ∈ (_ ∶ ( (1( ⊆ (3( ⟶ (\( (1( ≤ (\( (3( ,(
(9) mikä tarkoittaa, että jos 1 on 3:n alijoukko niin \(1) ei saa ylittää arvoa \(3). Toi-saalta, f on anti-monotoninen, jos
24 Tunnetaan myös nimellä confidence-based pruning.
25 Esimerkiksi joukon {1,2}(potenssijoukko on { ∅ , 1 , 2 , 1,2 }.
∀(1(, 3( ∈ (_ ∶ ( ((1( ⊆ (3() ( ⟶ \(((3() ( ≤ (\(((1()(,
(10) mikä tarkoittaa, että jos 1 on 3:n alijoukko, niin \(3)(ei saa ylittää arvoa \(1). Jokai-nen anti-monotonisuuden sisältävä mitta voidaan sisällyttää tiedonlouhinta-algoritmiin ja näin karsia huomattavasti kandidaattijoukkojen vaatimaa eksponentiaalista tilavaa-timusta.
Brute-force -menetelmää käytetään kattavan joukon löytymiseen niin, että jokaiselle kandidaattijoukolle määritetään tukiarvo. Brute-force tarkoittaa kaikkien mahdollisten kombinaatioiden luettelemista, jotka määriteltyjen joukkojen perusteella voidaan muodostaa. Tukiarvojen määrittelemiseen jokaiselle kandidaattijoukolle täytyy jokais-ta kandidaattia verjokais-tailla jokaisjokais-ta transaktiojokais-ta vasten. Kandidaattialkion tukiarvo kas-vaa, jos alkio esiintyy transaktiossa. Tämä lähestymistapa on laskennallisesti todella raskasta, sillä se saattaa tarvita e(Xfg) vertailua, missä X on transaktioiden luku-määrä, f( = ( 2h− 1 on kandidaattijoukkojen lukumäärä ja g(on suurimman transak-tion leveys. Tämän vuoksi karsimistekniikoita tarvitaan avuksi. (Kotu & Deshpande, 2014.)
Kattavan joukon luomiseen apriori-algoritmilla on kaksi tärkeää ominaisuutta. Ensin-näkin algoritmi hyödyntää leveyshakua. Toisekseen se käyttää “luo ja testaa” – strategiaa (bottom-up) kattavien joukkojen löytämiseen. Jokaisella iteraatiokierroksella uudet kandidaattijoukot luodaan edellisellä iteraatiokierroksella löydettyjen kattavien joukkojen perusteella. Jokaisen kandidaatin tukiarvo on täten laskettu ja testattu I)C&RK arvoa vasten. Algoritmissa tarvittavien iteraatioiden lukumäärä on S(.ij + (1 missä S(.ij on kattavien joukkojen suurin koko. (Kotu & Deshpande, 2014.) Määri-tellään seuraavaksi kattava joukko ja kandidaattijoukko:
•! Kattava joukko on joukko, jonka tukiarvo on suurempi kuin käyttäjän määritte-lemä raja-arvo (I)C&RK). Olkoon kattava joukko Zh, missä S on joukon koko.
•! Kandidaattijoukko on potentiaalinen kattava joukko, jonka täytyy läpäistä kak-si karkak-simisvaihetta ollakseen kattava joukko. Olkoon kandidaattijoukko kh, missä k on joukon koko.
Ensimmäinen karsimisvaihe perustuu aikaisemmin määriteltyyn aprioriseen periaat-teeseen. Kandidaattijoukon (k+1) -alkiojoukon luomisen jälkeen tarkastellaan kandi-daattijoukon alijoukkoja. Jos yksikin alijoukoista ei kuulu joukkoon Zh, niin kandi-daatti hylätään, koska se ei ole kattava. Muuten kandikandi-daatti jatkaa seuraavaan karsi-mistestiin. Edellisestä karsimisesta selvinneiden kandidaattijoukkojen tukiarvo tarkas-tetaan seuraavassa karsimisvaiheessa. Jos tukiarvo ylittää raja-arvon (I)C&RK) arvon, niin kandidaatti hyväksytään kattavaksi joukoksi. Tämä karsimisvaihe implementoi-daan yleensä hajautuspuun26 avulla. (Kotu & Deshpande, 2014.)
4.3.2! Assosiaatiosääntöjen muodostaminen
Tässä kappaleessa kuvataan, kuinka kattavasta joukosta saadaan muodostettua tehok-kaasti assosiaatiosääntöjä. Jokainen kattava k-joukko27 3 voi tuottaa jopa 2h(− (2 as-sosiaatiosääntöä pois lukien säännöt, joilla on tyhjä alkutilanne ∅ ⟶ 3 tai tyhjä seu-raus 3 ⟶ ∅. Assosiaatiosääntö voidaan erottaa jakamalla kattava joukko Y kahteen alijoukkoon, jotka eivät ole tyhjiä joukkoja. Olkoon jaetut joukot 1 ja 3 − 1(niin, että 1 ⟶ 3 − 1 täyttää luotettavuusarvon. Jokainen kattavasta joukosta muodostettava sääntö kattaa jo tukiarvon, sillä kattava joukko on määritelty aikaisemmin tukiarvon perusteella.
Luotettavuusarvolla ei ole monotonista ominaisuutta, kuten tukiarvolla on. Esimerkik-si implikaation 1 ⟶ 3 luotettavuusarvo voi olla suurempi, pienempi tai sama toiselle säännölle 1 (( ⟶ ( 3( , missä 1 ( ⊆ (1 ja 3 ( ⊆ (3. Jos kuitenkin verrataan samasta katta-vasta joukosta 3 muodostettuja sääntöjä, seuraava teoreema pätee luottamusarvolle.
(Kotu & Deshpande, 2014.)
26 Tunnetaan myös nimellä hash tree.
27 Tunnetaan myös nimellä frequent k-itemset.
Jos sääntö 1 ⟶ 3 − 1 ei täytä luotettavuusarvon raja-arvoa, silloin mikä tahansa sääntö 1l ⟶ 3 − 1′, missä 1’ on 1:n alijoukko, ei saa täyttää luotettavuusarvon raja-arvoa.
Apriori-algoritmi hyödyntää leveyshakua assosiaatiosääntöjen muodostuksessa, jossa jokainen taso vastaa alkioiden määrää, jotka kuuluvat seuraussääntöön. Ensiksi erote-taan suuren luotettavuusarvon omaavat säännöt, joilla on vain yksi alkio seuraussään-nössä. Näiden sääntöjen pohjalta muodostetaan uusia kandidaattisääntöjä. Esimerkiksi, jos DFG ⟶ o ja DGo ⟶ F ovat vahvoja sääntöjä, niin kandidaattisääntö DG ⟶ oF voidaan luoda yhdistämällä molempien sääntöjen seuraussäännöt. Ol-koon luotettavuusarvo FGo ⟶ D matala ja alle määritellyn raja-arvon. Tällöin kaikki tämän säännön alijoukot pystytään karsimaan välittömästi edellä esitellyn teo-reeman perusteella. Kaikki säännöt, jotka sisältävät alkion D seuraussäännössä mukaan lukien Go ⟶ {DF}, Fo ⟶ {DG}, FG ⟶ {Do} ja o ⟶ {DFG}, voidaan hylätä.
(Kotu & Deshpande, 2014.) Alla on kuvattu apriori-algoritmin toiminta pseudokoodil-la.
$ Lk$=$candidates$in$Ck$with$min_sup$
$ end!!
!
$
return$∪k$Lk;$$$
Kuva 12. Apriori-algoritmin pseudokoodi
4.4! Tiedonlouhinta
Tässä kappaleessa kuvataan ostoskorianalyysin tekemiseen tarvittavia työkaluja ja esitetään saatuja tuloksia ostoskoridatalle muodostetun assosiaatioanalyysin avulla.
Tiedonlouhintatehtävät suoritetaan R-ohjelmistoympäristöllä ja apuna käytetään siitä löytyvää arules-kirjastoa. Arules-kirjasto sisältää apriori-algoritmin implementaation, jota käytetään assosiaatiosääntöjen muodostamiseen. Kappaleessa edetään kuvaamalla ensin datan noutaminen tietokannasta, jonka jälkeen datasta muodostetaan analyysiin soveltuvaa transaktiodataa. Seuraavaksi transaktiodatalle tehdään assosiaatioanalyysi ja saatuja tuloksia visualisoidaan ja kuvaillaan R:n avulla. R:ssä käytetyt komennot kulkevat mukana läpi kappaleen.
Ensiksi otetaan käyttöön tarvittavat kirjastot ja luodaan kysely, jonka avulla data saa-daan tietokannasta. Kyselyssä haetaan yksinkertaisesti jokainen tosite eli kuitti, tuot-teen nimi sekä päivämäärä. Kyselyssä transaktioista poistetaan pullopantit, tuottuot-teen arvonlisäveron, muovikassit, veikkauspelit ja pullonpalautukset. Jokaisen sanan ympä-rillä käytetään % merkkiä eli sanaa ennen tai sanan jälkeen voi lukea mitä tahansa.
Esimerkiksi merkkijono %veikkau% sisältää sanat veikkauksen voitonmaksu, veik-kauspeli, veikkaus. Nämä kyseiset tuotteet on poistettu datasta, koska niitä esiintyi hyvin monessa ostoskorissa. Voidaan myös ajatella, onko kiinnostavaa tietää muovi-kassin kuuluvan melkein jokaiseen ostoskoriin vai tiedetäänkö se jo muutenkin?
$
Seuraavaksi luodaan tietokantayhteys Pervasiven tietokantaan ODBC-rajapinnan kaut-ta ja haekaut-taan transaktiodakaut-ta dakaut-ta-muuttujaan, jonka jälkeen ne kirjoitekaut-taan CSV-tiedostoon.
#"Luodaan"tietokantayhteys"tietokantaan"nimeltä"'MBA'$
Seuraavaksi muodostetaan transaktiodata csv-tiedostossa olevasta datasta. Samalla poistetaan datasta duplikaattiarvot. Transaktiodataan jää transaktion numero, sekä transaktiossa esiintyvä tuotenimi. Tämän jälkeen tarkastellaan muodostettuja transak-tioita tarkemmin.
R:llä muodostettu itemMatrix -tietorakenne on matriisi, joka on todella harva. Harvan matriisin yksi ominaisuus on, että suurimmassa osassa tietorakenteen soluista on arvo 0. Muodostetun transaktiomatriisin transactions koko on 5686 x 156 664 ja matriisin tiheys on 0.0006035587. Tiheys kertoo, kuinka suuri osa matriisista esiintyy eri arvolla kuin 0. Kuvan 13 histogrammissa on yleisimmin transaktiodatassa esiintyviä tuotteita.
Niistä viisi yleisintä tuotetta lukumäärineen ovat:
1.! OLVI III 4,5% 0,33L TLK (7730 kpl)
2.! MYYNTIKOODI KOFF 0,33L TLK (5203 kpl) 3.! ARLA KEVYTMAITO SUOMI 1L (5117 kpl) 4.! BANAANI BAJELLA (4747 kpl)
5.! MYYNTIKOODI SANDELS III 0,33L TLK (4474 kpl)
Muita esiintymiä on lisäksi yhteensä 510 374 kappaletta. Kuitilla esiintyvien den lukumäärän mediaani on 2 ja keskiarvo 3,432. Yhdellä kuitilla esiintyvien tuottei-den maksimimäärä on 77.
Kuva 13. Transaktiojoukon 25 yleisintä tuotetta.
Seuraavaksi muodostetaan itse assosiaatiosäännöt. Esimerkissä luotettavuusarvoksi valitaan 0.0001 ja tukiarvona annetaan olla R:n apriori-algoritmin vakioarvo, joka on 0.8. Sääntöjä muodostettiin monilla eri luotettavuus- ja tukiarvoilla kaikkien merkittä-vien sääntöjen löytämiseksi datasta. Target eli kohde ilmaisee, minkä tyyppisiä assosi-aatioita louhitaan. Tässä tapauksessa kohde on sääntöjoukko.
#"Muodostetaan"assosiaatiosäännöt"$
basket_rules$<:$apriori($transactions,$parameter$=$list($sup$=$0.0001 ,$target="rules"$)$)$
#"Tarkastellaan"muodostuneita"sääntöjä$
summary($basket_rules$)$
#"Hajontakuvio"muodostuneista"assosiaatiosäännöistä$
plot($basket_rules$)$
Kuva 14. Hajontakuvio assosiaatiosäännöistä
Kuvassa 14 on hajontakuvio 73 muodostuneesta säännöstä. x-akselilla on tukiarvo, y-akselilla on luotettavuusarvo ja mittauspisteen tummuus kuvaa alkion nostearvoa.
Sääntöjen pituuden jakautuminen on esitetty kuvassa 15, jossa vasemman ja oikean puolen tuotteet otetaan huomioon lukumäärässä. Suurin osa säännöistä on yhteispituu-deltaan kolmen tai neljän tuotteen mittaisia.
Kuva 15. Sääntöjen lukumäärä jaoteltuna niissä esiintyvän yhteisen tuotemäärän mukaan, jossa 1
41
30
1 0
5 10 15 20 25 30 35 40 45
2!tuotetta 3!tuotetta 4!tuotetta 5!tuotetta