Sisältöön perustuvien algoritmien vertailu sähköpostiviestien automaattisessa luokittelussa

Aapo Puhakka
13.8.2004
http://aapo.iki.fi

Sisältö

• 1 Johdanto

• 2 Tekninen arkkitehtuuri

• 3 Data-aineisto

• 4 Datan luku

• 5 Datan luokittelu

• 6 Esikäsittely

• 7 Menetelmät

  • 7.1 Paul Graham: Naive Bayes

  • 7.2 Gary Robinsonin parannukset

  • 7.3 WebSOM

  • 7.4 Sanatuplat Robinsonin menetelmällä

• 8 Tietokantarakenteet

• 9 Tulokset

• 10 Parannusmahdollisuuksia

• 11 Yhteenveto

• Kirjallisuutta

1 Johdanto

Roskapostiviestiksi (eli späm-viestiksi) kutsutaan mainossähköpostia, joka on lähetetty ilman että vastaanottaja on mitenkään ilmaissut kiinnostustaan ao. mainosten vastaanottamiseen. Kaikki mainossähköpostit eivät siten ole roskaposteja.

Späm-viestin lähettejä ei ole mitenkään yrittänyt arvioida, voisiko vastaanottaja olla kiinnostunut sähköpostista. Vastaanottajalla ei ole mitään keinoa ilmaista, ettei hän tällaisia viestejä enää halua. Lisäksi lähettäjän from-osoite on usein väärennetty - roskapostiin ei voi vastata.

Roskapostittaja kerää sähköpostiosoitteita koneellisesti eri lähteistä: uutisryhmistä, www-sivuilta, yms. Hän saattaa myös ostaa kokoelman sähköpostiosoitteita joltain toiselta roskapostittajalta.

Viime kädessä mahdollisuus roskapostitukseen johtuu suunnitteluvirheestä tai aukosta sähköpostien välitykseen käytetyssä SMTP-protokollassa. Protokollan muuttamisella ongelmasta olisi mahdollista päästä pysyvästi eroon. Mutta hyvin laajaan käyttöön levinneen protokollan muuttaminen on hidasta, sillä se vaatii kaikkien merkittävien osapuolten yhteisymmärrystä muutoksen tarpeesta ja teknisen toteutuksen yksityiskohdista. Sitä ennen täytyy tyytyä späm-viestien torjuntaan suodatuksen avulla.

Roskapostiviestien määrä on viime vuosina noussut huomattavasti ja muuttunut hankalaksi ongelmaksi, joka alentaa työtehoa ja uhkaa myös hukata oleellisia viestejä roskan joukkoon. Sähköpostiviestien käsittelyyn tarvitaan automaattisia järjestelmiä. Näille järjestelmille asetettavat vaatimukset ovat kovia: automaatti ei saisi luokitella yhtään oikeaa sähköpostiviestiä roskapostiksi. Muutoin roskapostit on välttämätöntä käydä aika ajoin manuaalisesti läpi automaattisen hävittämisen sijaan. Toisaalta lähes kaikki roskapostit pitäisi pystyä tunnistamaan, jotta järjestelmä olisi hyödyllinen.

Nykyisin on käytössä erilaisiin heuristiikkoihin perustuvia menetelmiä, jotka tällä hetkellä toimivat kohtuullisen hyvin, kuten TKK:n atk-keskuksella käytössä oleva SpamAssassin. Näiden menetelmien varjopuolena on kuitenkin se, että niitä täytyy jatkuvasti täydentää, jotta ne havaitsisivat uudetkin roskapostit. Roskapostien lähettäjät voivat ainakin periaatteessa testata viestinsä näillä menetelmillä ennen lähettämistä ja siten varmistua, että ne saapuvat perille.

Ihmiselle roskapostin tunnistaminen oikeasta on hyvin helppoa, vaikka oikeat viestit ja späm-viestit olisivat ulkoasultaan hyvin samanlaisia. Sisältöön perustuva tunnistaminen tarjoaakin luotettavamman ja tutkimuksen kannalta mielenkiintoisemman ongelman sähköpostien erotteluun.

Käytännössä suomalaisella sähköpostien vastaanottajalla roskapostit ovat yhdessä suhteessa helposti poikkeavia oikeista sähköposteista: Tavalliset sähköpostiviestit ovat useimmiten suomenkielisiä kun taas roskapostit ovat englanninkielisiä. Tämä aiheuttaa suomalaisille käyttäjille tiettyjä erikoisongelmia puhtaasti englanninkielisiin käyttäjiin verrattuna. Näitä ongelmia on ratkottu tekemällä luokittelu useampaan kuin kahteen luokkaan. Tästä aiheesta kerrotaan lisää luvussa Data-aineisto .

Tämän työn tarkoituksena on ollut löytää mahdollisimman hyvä menetelmä sisältöön perustuvaan automaattiseen luokitteluun eikä niinkään tutkia yksittäistä algoritmia. Siksi työssä on rakennettu yhtenäinen sähköpostiviestien automaattisen luokittelun tutkimiseen soveltuva tietokantarakenne ja ohjelmisto, johon kuuluu erilaisia esikäsittelymenetelmiä, joiden jälkeen voidaan käyttää useita erilaisia algoritmeja.

Sähköpostien automaattiseen luokitteluun on kokeiltu neljää eri menetelmää:

• Paul Grahamin esittelemää Naive Bayes -menetelmää [1].

• Gary Robinsonin matemaattisesti kehittyneempää versiota samasta menetelmästä [2].

• Itseoppivien karttojen (Self-Organizing Maps, SOM) -neuraaliverkkomenetelmää sovellettuna tekstidokumenttien käsittelyyn eli ns. WebSOM-menetelmää [3].

• Gary Robinsonin menetelmää laajennettuna sanapareihin eli sanoja on yhdistetty Markov-ketjujen [4] idealla.

Syöteaineistona voitaisiin käyttää erilaisia späm-arkistoja tai postituslistoja. Mutta tällöin lopputulokset olisivat hieman epäluotettavia, sillä oleellista tulosten luotettavuuden ja käyttökelpoisuuden kannalta on se, että käytetty data on mahdollisimman todellista sähköpostidataa. Siksi olen käyttänyt aineistona itse vastaanottamiani omia sähköposteja muutaman vuoden ajalta. Aineisto on sen takia laadukasta, että olen säästänyt kaikki viime vuosina vastaanottamani n. 20 000 sähköpostia.

Ensin syötesähköpostit täytyi lukea ja tulkita unix-sähköpostikansiomuodosta jatkokäsittelyn kannalta käyttökelpoisempaan tietokantapohjaiseen muotoon. Tähän liittyviä seikkoja on kuvattu luvussa Datan luku.

Tämä jälkeen syötesähköpostijoukko täytyi käydä läpi käsin läpi ja ryhmitellä sähköpostit eri luokkiin. Jakoa nopeutti merkittävästi se, että data oli tietokantapohjaisessa muodossa. Tätä on kuvattu luvussa Datan luokittelu. Lisäksi sähköpostit jaettiin opetus- ja testijoukkoihin.

Ennen varsinaisten luokittelumenetelmien käyttöä täytyi datalle tehdä erilaisia ja vaihtoehtoisia esikäsittelyoperaatiota. Esikäsittelyä on kuvattu luvussa Esikäsittely.

Järjestelmän takana oleva tietokantarakenne on esitelty luvussa Tietokantarakenteet.

Oppivien menetelmien käytössä on keskeistä kokeellisesti määrittää menetelmille sopivat parametrit ja toteutusyksityiskohdat. Hyvien parametriarvojen löytämiseksi on välttämätöntä tehdä paljon testiajoja. Jotta ajoja voitaisiin käytännössä tehdä riittävästi, täytyy menetelmien suoritusaikojen ja tilavaatimusten olla kohtuullisia. Eri menetelmien parametreja, vaihtoehtoja yksityiskohdissa, suoritusaikoja ja tilavaatimuksia on esitelty luvussa Menetelmät.

Testien tulokset on esitetty luvussa Tulokset.

Järjestelmän yleistä teknistä arkkitehtuuria on esitelty luvussa Tekninen arkkitehtuuri.

Parannusmahdollisuukssa-luvussa esitellään erilaisia parannusajatuksia, joita ei tässä työssä sen tarkemmin selvitetty eikä kokeiltu, mutta joilla voisi ehkä jatkossa parantaa luokittelun laatua.

2 Tekninen arkkitehtuuri

Ohjelmat toteutettiin Java-kielellä, jotta toteutus sujuisi mahdollisimman nopeasti sekä olisi helposti jatkossa hyödynnettävissä.

Data, tulokset ja välitulokset talletettiin SQL-kantaan (MySQL). Tietokantarakenne on esitelty luvussa Tietokantarakenteet. SQL-kannan käytöllä saavutettiin seuraavia etuja:

• SQL-kantaa käytettäessä suurten tietomäärien käsittely on helppoa ja tehokasta.

• Välitulosten ja osavaiheiden tallettaminen SQL-tauluihin helpottaa laskennan oikeellisuuden varmistamista. Väli- ja aputuloksista voidaan helposti laskea erilaisia tilastollisia tunnuslukuja ja jakaumia.

• Erilaisten raporttien muodostaminen datasta ja tuloksista on suoraviivaista.

• Sähköpostien käsin tehtävässä luokittelussa voidaan hyödyntää erilaisia heuristiikkoja ja peukalosääntöjä.

Muutoin ohjelmat toteutettiin pohjautuen diplomityössäni esittelemiini 3-tasoarkkitehtuurin mukaisten sovellusten rakentamiskomponentteihin [5]. Näiden avulla kaikille tietokannan tauluille saatiin nopeasti tehtyä graafiset käyttöliittymät niiden tutkimisen ja käsittelyn helpottamiseksi.

3 Data-aineisto

Keskeinen vaatimus syötedatan suhteen oli, että sähköpostien täytyy olla mahdollisimman oikeita, jotta voitaisiin käytännössä todentaa erilaisten menetelmien toimivuus ja käyttökelpoisuus. Syöteaineistoksi onnistuin saamaan omat sähköpostini muutaman vuoden ajalta. Olin nimittäin säästänyt muutaman vuoden ajan kaikki saamani sähköpostiviestit mukaanlukien saamani roskapostit.

En halunnut tyytyä tarkastelemaan pelkästään sähköpostien luokittelua oikeisiin ja roskaposteihin. Kehitin kaikista menetelmistä versiot, joilla voidaan suorittaa luokittelu useampaan loogiseen ryhmään. Loogisia ryhmiä voivat olla roskapostien lisäksi esim. työhön, opiskeluun, harrastuksiin, muihin henkilökohtaisiin asioihin tai tiettyihin postituslistoihin liittyvät sähköpostit.

Seuraavassa taulukossa on esitelty käytetyt luokittelut ja sähköpostimäärät. English -sarakkeessa ovat sähköpostimäärät, kun normaalit englanninkieliset sähköpostit ovat omassa luokassaan ja Ei-English sarakkeessa englanninkieliset sähköpostit ovat loogisissa luokissa.

Mainos on omana ryhmänään koska kaiken saapuvan mainossähköpostin ei voida katsoa olevan roskapostia. Kriteetinä roskapostin ja mainospostin erottelussa pidin sitä, että mainospostin lähettäjä on edes hieman käyttänyt vaivaa sen ajattelemiseen, onko vastaanottaja kiinnostunut aiheesta. Lähettäjällä on tällöin olemassa joku peruste olettaa vastaanottajan olevan kiinnostunut asiasta. Esim. verkkokirjakaupalla, josta on tilannut kirjoja, on tietty peruste olettaa, että vanha asiakas olisi kiinnostunut tietyn tyyppisistä uusista kirjoista.

Roskaposti taas on selkeästi täysin kohdistamatonta mainontaa, johon vastaanottaja ei ole antanut minkäänlaista suostumusta tai vihjettä, että hän olisi mainoksesta kiinnostunut.

Tämä luokittelulogiikan mukana pitäminen osoittautui myöhemmin varsin hyödylliseksi luokittelun osumatarkkuuden parantamisessa. Suomalaisella sähköpostin vastaanottajalla on nimittäin usein sellainen ongelma, että kaikki roskaposti on englanninkielistä. Oikeasta postista suurin osa on suomenkielistä ja pieni osa englanninkielistä. Jos postit luokitellaan vain suomenkielisiin ja englanninkielisiin viesteihin, niin Bayes-tyyppisillä menetelmillä normaalit englanninkieliset sanat vaikuttavat tilastollisessa mielessä späm-sanoilta.

Sen sijaan, kun sähköpostit luokitellaan uudestaan siten, että tuodaan mukaan uusi luokka 'English', johon luokitellaan englanninkieliset sähköpostit, tulokset paranevat merkittävästi. Tätä asiasta löytyy lisää tietoa luvusta Tulokset.

4 Datan luku

Unix-sähköpostikansioformaatti on aika lähellä SMTP-protokollan mukaista välitysmuotoa. SMTP-prokollaan on aikojen kuluessa kerääntynyt aika paljon yksityiskohtia. Lisäksi eri sähköpostiohjelmat käsittelevät yksityiskohdia hieman eri tavoilla.

Kahden sähköpostiviestin rajana kansiotiedostossa on '\n\nFrom' eli kaksi rivinvaihtoa ja From-sana. Sähköpostin otsikko- ja sisältöosien (header ja content) välissä on kaksi rivinvaihtoa. Otsikon kentät alkavat '\nAvainsana:' tyyppisellä merkkijonolla.

Sähköposti voi koostua yhdestä tai useammasta osasta. Jos sähköposti koostuu useammasta osasta, niin header-osassa on määritelty merkkijono, jolla osat erotellaan toisistaan. Useampiosaisen sähköpostin kukin osa koostuu omista otsikko- ja sisältöosistaan. Lisäksi sähköposti voi sisältää toisia sähköposteja, joilla on omat otsikko-osansa.

Sähköpostin sisältö voi olla periaatteessa minkä muotoista tahansa, tässä työssä on analysoitu vain 'text/plain' ja 'text/html' -tyyppiset sisältöosat. Lähinnä näiden tyyppien ulkopuolelle jäävät erilaiset liitetiedostot. Jos sähköpostin muoto alkaa 'multipart/' -merkkijonolla, niin tällöin on kyseessä moniosainen sähköposti. Jos muoto on 'message/rfc822', niin kyseessä on sähköpostin sisältämä toinen sähköposti.

Sähköpostin koodaukseen on olemassa useita erilaisia tapoja. Yksiosaisilla sähköposteilla sisällön koodaus on ilmoitettu otsikon kentässä 'Content-Transfer-Encoding'. Moniosaisilla sähköposteilla muoto on ilmoitettu kunkin osan otsikko-osassa. Koodausvaihtoehdot ovat 'base64' ja 'quoted-printable'.

Base64-koodauksessa ilmaistaan 8-bittiset merkit (256-vaihtoehtoa) merkeistä a-z, A-Z, 0-9, +, / koostuvalla koodauksella, jossa on 64 vaihtoehtoa. Tällä tavalla kolme 256-vaihtoehtoista merkkiä kuvautuu neljäksi 64-vaihtoehtoiseksi merkiksi (256*256*256 = 16 777 216 = 64*64*64*64). Koodattuna tiedon kokonaispituus kasvaa siis 33 %.

Quoted-printable -koodauksessa erikoismerkit ilmaistaan =-merkillä ja kaksimerkkisellä heksakoodilla. Esimerkiksi ä-kirjain kuvautuu merkkijonoksi '=E4'.

Header-osan kenttien suhteen koodaus on ilmaistu yksittäisessä kentässä. Erikoismerkkien tullessa eteen, ilmaistaan koodaustapa ja käytetty koodaus. Erilaisia merkintöjä header-osan koodauksille esiintyi n. 20 kpl. Käytännössä koodaustapa oli kaikissa joko base64 tai quoted-printable.

Päivämäärien ilmaisemiseen header-kentissä on paljon vaihtelevia formaatteja. Saapumisaika on vastaanottavan sähköpostipalvelimen merkitsemä ja siten formaatti on yksikäsitteinen. Sen sijaan lähetysaika on lähettävän sähköpostiohjelman ilmoittama ja formaatti vaihtelee hyvin paljon. Erilaisia päätyyppejä lähetysajan ilmoittamiseen esiintyi 4 ja niistä oli kustakin useita erilaisia variaatioita.

Formaatin ollessa näin monimutkainen ja vaihteleva, oli tarpeen kehittää tarkistuksia sen suhteen, oliko tieto luettu oikein. Joitakin asioita saattoi tutkia SQL-lauseilla ja silmämääräisesti, mutta muutamia tapauksia varten täytyi tehdä tarkistusalgoritmeja.

Yksi tarkistustapa oli listata suurimmat =-merkkimäärät sisältävät viestit. Nimittäin, jos quoted-printable -koodauksen purku jotenkin epäonnistuu, lopputuloksena viestissä on hyvin paljon =-merkkejä.

Toinen tarkistustapa oli etsiä viestit, joissa oli hyvin pitkiä sanoja. Hyvin pitkä sana kertoo esim. base64- tai quoted-printable -tulkinnan epäonnistumisesta tai jonkun binääriliitetiedoston mukaanottamisesta.

Kun joku puute tulkintalogiikassa on havaittu, niin syntyy epäilys, onko mahdollisesti joku ilman virhettä sisään luettu viesti luettukin väärin. Tämän varmistamiseksi rakensin mahdollisuuden lukea sisään kaikki viestit, ja vertailla uudelleen luettua tulosta kannassa jo ennestään olevaan tulokseen. Eroavat sähköpostit saattoi sitten tarkastaa käsin.

5 Datan luokittelu

20000 sähköpostin luokittelu käsin tuntuu isolta urakalta. Se ei kuitenkaan muodostunut mahdottoman isoksi työksi muutamien seikkojen ansiosta. Suurimman osan sähköposteista olin jo etukäteen luokitellut loogisiin kansioihin, jotka saattoi merkitä tiettyyn luokkaan kuuluvaksi alkuperäisen kansion nimen perusteella.

Luokittelemattomien (n. 6000 kpl) sähköpostien osalta varsin näppäräksi tavaksi osoittautui luokittelu From ja To -kenttien perusteella. Tietty henkilö lähettää nimittäin melko todennäköisesti vain tiettyyn luokkaan kuuluvaa postia. Tällöin ao. kenttien arvojen perusteella voi esim. tietyn henkilön lähettämät postit massatoimintona määritellä tiettyyn luokkaan kuuluviksi.

6 Esikäsittely

Luokittelualgoritmien toimivuuden arviointi vaatii datan jakamista opetus- ja testiaineistoon. Tätä varten tein oman toiminnon ohjelmaan, joka merkitsi sähköpostiviestit opetus- ja testijoukkoihin sekä teki merkinnän rajaviestistä tietokantaan. Jakoperuste oli se, että kustakin joukosta ensimmäiset määritettiin opetusjoukkoon ja viimeiset testijoukkoon viestin saapumisajankohdan mukaan.

Ehkä hieman oikeampi tapa olisi jakaa kaikki viestit opetus- ja testijoukkoihin saapumisajankohdan mukaan. Käytetyssä tavassa kunkin luokan tilanne on tasapainoisempi, koska luokkaa esiintyy yhtä paljon sekä opetus- että testijoukossa. Mutta kaikkien viestien yli tapahtuva jakaminen olisi ehkä lähempänä todellista luokittelutilannetta. Tämän vaihtoehdon tutkiminen olisi eräs jatkokehitysmahdollisuus.

Menetelmissä usein tarkastellaan sanojen lukumääriä. Tällöin tulee kyseeseen, kumpaa lukua kannattaa käyttää, niiden sähköpostien lukumäärää, joissa sana esiintyy vai sanan kokonaisesiintymämäärää. Eroa näissä luvuissa tulee niiden sanojen osalta, jotka esiintyvät useita kertoja samassa sähköpostissa. Useimmissa menetelmissä käytetty luku on sähköpostimäärä. Tämä on myös valinta, jonka edullisuutta voitaisiin testata.

Sähköpostit koostuvat useista merkeistä, muistakin kuin vain sanoista. On kirjaimia, numeroita ja muita merkkejä. Tämä kokonaisuus pitäisi saada yksinkertaistettua pelkiksi sanoiksi, jotta sitä voitaisiin käsitellä sanankäsittelyalgoritmeilla.

Tämän työn puitteissa sanoitusalgoritmi toimi mahdollisimman yksinkertaisesti. Viesti muutettiin pienille kirjaimille ja kaikki muut merkit kuin kirjaimet a-ö tulkittiin välilyönniksi. Tuloksia voisi mahdollisesti parantaa huomioimalla tiettyjä muitakin merkkejä sanoiksi ja käsittelemällä isot kirjaimet erikseen. Näitäkin vaihtoehtoja olisi mahdollista testata jatkokehityksessä.

Mitkä osat sähköpostista pitäisi ottaa mukaan? Otetaanko koko header vai siitä pelkästään subject-rivi? Näitä vaihtoehtoja testasin useilla eri parametreilla ja osoittautui, että yksisanaisilla tilastollisilla menetelmillä koko header-osan mukaanottaminen parantaa tuloksia.

Mitä pitäisi tehdä sähköpostiviestien HTML-tageille? Otetaanko ne mukaan vai ei? Aluksi lähdin liikkeelle siitä ajatuksesta, että on parasta käyttää kaikki mahdollinen tieto hyväksi ja otin html-tagit mukaan. Myöhemmin kuitenkin osoittautui, että html-tagien pois jättäminen vähentää merkittävästi virheellisesti späm-viesteiksi tulkittujen sähköpostiviestien määrää. Syynä tähän on se, että varsin monet späm-viestit sisältävät html-tageja ja vain harvat oikeat sähköpostit sisältävät niitä. Tämä johtaa siihen, että html-tagit saavat monilla menetelmillä osakseen vahvan späm-leiman ja ne oikeat viestit, joissa on html-tageja, saavat suotta osakseen roskapostivaikutelmaa.

7 Menetelmät

Työssä tutkittiin kokeellisesti neljää eri menetelmää. Kaikissa menetelmissä voidaan datajoukko jakaa kahtia: opetus- ja testidataan. Opetusdatalla järjestelmä alustetaan ja testidatalla voidaan tutkia luokituksen onnistumista.

Kaikissa menetelmissä luokittelu voidaan tehdä kolmitasoisesti: Luokittelu voi paitsi onnistua tai epäonnistua, niin päätyä myös epävarma-tilaan. Koska oppiva sisältöperusteinen automaattinen luokittelu ei juuri koskaan onnistu täysin oikein (luokittelua suorittavien ihmistenkin välillä on erimielisyyttä täsmällisestä luokasta joidenkin sähköpostien kohdalla), nousee Epävarma-tila merkitykselliseksi. Suodatusta tekevä ohjelma voi ehkä tuhota automaattisesti varmat roskapostit, mutta epävarmat tapaukset sen pitää tuoda käyttäjän käsiteltäviksi. Käyttäjän päätettyä epävarman sähköpostin luokan, voi ohjelma tämän tiedon avulla jatkossa opettaa itseään.

7.1 Paul Graham: Naive Bayes

Paul Grahamin Naive Bayes -menetelmässä selvitetään kaikkien opetusjoukossa esiintyvien sanojen esiintymismäärät (sähköpostimäärät) eri luokissa. Kullekin sähköpostin sisältämälle sanalle lasketaan luokkatodennäköisyydet ja nämä yhdistämällä saadaan todennäköisyydet sähköpostin kuulumiseksi eri luokkiin.

Menetelmässä sanojen luokkatodennäköisyydet lasketaan kaavalla:

      b / n_bad
----------------------
g / n_good + b / n_bad

missä:
 + b on sanan sähköpostimäärä roskaposteissa
 + g on sanan sähköpostimäärä oikeissa posteissa
 + n_bad on roskapostien määrä
 + n_good on oikeiden postien määrä

kahdella luokalla.

Yleistin ylläolevan kaavan useammalla luokalla toimivaksi seuraavasti:

              n_1 / n_luokka1
--------------------------------------------
                       n_2 + ... + n_x
n1 / n_luokka1 + ---------------------------
                 n_luokka2 + ... + n_luokkax

Yleistyksen voi tehdä myös siten, että vertaillaan kutakin luokkaa vain späm-luokkaa vastaan (ja späm-luokkaa kaikkia muita). Tai sitten, että späm-luokan vastapari on english-luokka. Tämä viimeinen osoittautui varsin toimivaksi ratkaisuksi.

Sähköpostin eri sanojen väliset todennäköisyydet yhdistetään kaavalla:

                  a * b * ... * n
---------------------------------------------------------
a * b * ... * n + ( 1 - a ) * ( 1 - b ) * ... * ( 1 - n )

Tämä kaava on yleinen itsenäisten todennäköisyyksien yhdistämisen kaava. Kaavan toimintaperiaatetta on tarkemmin kuvattu lähteissä [6] .

Grahamin kaavoilla täytyy rajoittaa yhdistämiskaavaan mukaan otettavat sanat joukkoon (esim. 15) tulosta eniten poikkeuttavaan sanaan (eli kauempana neutraalista 0.5:stä olevaan sanaan).

Lopputuloksena saadaan kullekin sähköpostille todennäköisyys, jolla se kuuluu tiettyyn luokkaan. Laskelmat suoritetaan sähköpostin osalta kaikille luokille ja sähköposti sijoitetaan siihen luokkaan, johon kuulumistodennäköisyys on suurin.

Epävarmoiksi luokituksiksi voidaan tunnistaa esim. ne sähköpostit, joilla minkään luokan todennäköisyys ei ole yli tietyn rajan (esim. 0.9) tai joilla useamman luokan todennäköisyys on yli tietyn rajan (esim. 0.9).

Lisäksi luokitusta voidaan ohjata siihen suuntaan, että tulisi vähemmän virheellisiä roskapostiluokituksia. Tämä voidaan tehdä esim. asettamalla späm-luokan raja on muiden luokkien rajoja korkeammaksi.

7.2 Gary Robinsonin parannukset

Gary Robinson on havainnut muutamia teoreettisia puutteita Paul Grahamin menetelmässä. Toisaalta luokkatodennäköisyyksien laskentakaava toimii hieman huonosti aineistossa vain vähän esiintyville tai uusille sanoille. Sanatodennäköisyyksien yhdistämiskaava ei toimi kunnolla sanoille, joilla on hyvin pieni todennäköisyys esiintyä tietyssä luokassa eikä se erottele eri luokkia toisistaan tarpeeksi selkeästi. Samoin Grahamin yhdistämiskaavassa on rajoitus, että siinä pitää keskittyä vain eniten erotteleviin sanoihin.

Gary Robinsonin menetelmä on siis muutoin sama kuin Paul Grahamin, mutta käytettävät kaavat on vaihdettu teoreettisesti paremmin perusteltuihin.

Gary Robinsonin luokkatodennäköisyyksien laskentakaava on:

       (s * x) + (n * p(w))
f(w) = --------------------
              s + n 

missä:
 + p(w) on Paul Grahamin menetelmän yhdistämiskaava
 + s on taustatiedolle annettava painokerroin
 + x on todennäköisyys, että uusi sana esiintyy luokassa
 + n on niiden opetusdatan sähköpostien lukumäärä, joissa sana esiintyy

s ja x ovat kertoimia, jotka täytyy määrittää kokeellisesti. Gary suosittelee oletusarvoiksi s = 1 ja x = 0.5.

Edellä esitetyssä Paulin kaavassa on se ongelma, että jos sana on esiintynyt vain muutamassa aiemmassa sähköpostissa, jotka ovat kuuluneet tiettyyn luokkaan, voi olla mahdollista, että sana on yleinen sana, joka vain sattumalta on ensiksi tullut vastaan tietyn luokan sanoissa. Uudella kaavalla voidaan tätä efektiä pienentää ja suunnata uusia sanoja neutraalimpaan suuntaan.

Garyn ehdottama menetelmä sanojen todennäköisyyksien yhdistämiseksi on seuraava.

Lasketaan luokkaan kuulumiselle ja ei-kuulumiselle arvot H ja S. H tarkoittaa todennäköisyyttä, että sähköposti kuuluu luokkaan (sanojen todennäköisyyksien kertoma) ja S että sähköposti ei kuulu luokkaan (sanojen todennäköisyyksien vastalukujen 1 - t_n kertoma.

Yhdistämisessä käytetään Chi-Square -jakaumaa eikä menetelmää voi (tai en ainakaan tiedä, miten voisi) kuvata yhdellä matemaattiselle kaavalla. Yhdistäminen esitetäänkin proseduurina. Seuraavana on esitetty proseduuri 'arc_C' jolle annetaan parametreina kertoma ja sähköpostin eri sanojen lukumäärä:

private double arc_C ( double dKertoma, int iLkm ) {
  if (dKertoma == 0)
    return 0;

  double dM = -Math.log( dKertoma );
  double dSum = Math.exp( -dM );
  double dTerm = dSum;

  for (int i = 1; i < iLkm; i++) {
    dTerm *= dM / i;
    dSum += dTerm;
  }

  if (dSum > 1.0) // esim. pyöristysvirheiden johdosta
    return 1.0;

  return dSum;
}

(Math.log on luonnollinen logaritmi ja Math.exp on sen käänteisoperaatio eli e^n).

Kertomat ja vastakertomat lasketaan erikseen, jotta lähellä nollaa tapahtuvat kertomiset eli pienet voimakkaasti tiettyyn luokkaan kuuluvien sanojen esiintymiset toisissa luokissa eivät pääsisi vaikuttamaan liikaa.

H ja S yhdistetään yksinkertaisesti kaavalla:

       1 + H - S
 t_n = ---------
           2

Tähän Robinsonin kaavaan voidaan sijoittaa kaikki sähköpostissa esiintyvät sanat.

Käytännössä Robinsonin kaavoilla saatiin huomattavasti parempia tuloksia, vaikkakin ensimmäisillä Robinsonin kaavoilla tapahtuneilla testiajoilla tulokset olivat huonompia kuin parhailla Grahamin kaavoilla tapahtuneilla ajoilla. Tämä osoittaa, kuinka tärkeää on suorittaa paljon ajoja eri parametreilla parhaiden parametrivaihtoehtojen löytämiseksi.

Robinsonin menetelmä voidaan yleistää useammalle luokalle siten, että toiseen joukkoon katsotaan kuuluvan tietty luokka ja toiseen kaikki muut luokat.

7.3 WebSOM

WebSOM-menetelmässä [3] luokittelu tapahtuu kahden SOM-neuraaliverkon yhdistelmänä. Ensin kaikki opetusjoukon sanatriplat (kolmen sanan yhdistelmät asetetaan sanakartalle. Tämän jälkeen sähköpostit asetetaan dokumenttikartalle sanahistogrammin perusteella. Menetelmän teoreettinen mielenkiintoisuus on sen kyvyssä ottaa huomioon sanojen lyhyet kontekstit, mihin aiemmin esittellyt puhtaasti sanapohjaiset menetelmät eivät kykene.

Varsinaisessa SOM-laskennassa saatoin käyttää SOM-algoritmien valmista C-toteutusta [7] .

WebSOM-menetelmää varten tarvitaan monia esikäsittely- ja valmisteluoperaatioita. Aluksi kaikille sanoille täytyy muodostaa satunnaislukuvektorit. Satunnaislukuvektorin pituus voi olla esim. 20-30 lukua.

Data-aineistosta täytyy selvittää sanatriplat eli yksikäsitteiset yhdistelmät, joissa tietyllä sanalla on sama sanaa edeltävä ja sitä seuraava sana sekä näiden yhdistelmien lukumäärät.

Kullekin sanalle lasketaan odotusarvovektori. Vektorin ensimmäinen ja viimeinen kolmasosa lasketaan sanaa edeltävien ja seuraavien sanojen satunnaislukuvektorien odotusarvoina. Edeltävät ja seuraavat sanat saadaan selville sanatriplaluettelosta. Keskimmäinen kolmasosa muodostetaan sanan itsensä satunnaislukuvektorista kerrottuna tietyllä vakiolla.

Kun sanojen odotusarvovektorit on laskettu, voidaan muodostaa syötetiedosto kaikista sanoista ja muodostaa sen perusteella sanakartta SOM-algoritmeilla.

Seuraavaksi opetusjoukon sähköpostit haetaan ja paloitellaan sanoihin. Sanoille haetaan niiden odotusarvot ja muodostetaan sähköpostin syötetiedosto, jossa kaikki sähköpostin sanat on ilmaistuna odotusarvovektoreina. Tämä syötetiedosto ajetaan sanakartalle ja selvitetään kartalta kunkin kartan solun osumien lukumäärä. Vektori kartan solujen osumista talletetaan tietokantaan sähköpostin histogrammina.

Sähköpostin histogrammi voitaisiin hämärtää Gaussisella konvoluutio- operaatiolla. Jätin tämän operaation tekemättä, koska hieman epäilin sen hyödyllisyyttä. Jatkotutkimuksessa voitaisiin tehdä kokeita luokittelusta hämärryksellä ja ilman ja näin saada selville, onko operaatiosta hyötyä vai ei.

Kun sähköpostien histogrammit ovat selvillä, voidaan niistä muodostaa syötetiedosto ja muodostaa siitä dokumenttikartta SOM-algoritmeille.

Tämän jälkeen voidaan ajaa varsinainen luokitteluajo. Luokitteluajossa sähköpostit ensin jaetaan sanoihin, joille haetaan odotusarvovektorit. Seuraavaksi odotusarvotvektorit ajetaan sanakartalle. Tästä saadaan tietyn sähköpostin osumahistogrammi, joka ajetaan dokumenttikartalle.

Luokittelua varten kehitin seuraavan periaatteen. Jos sähköposti osuu dokumenttikartalla soluun, johon on aiemmin osunut vain tietyn luokan sähköposteja, katsotaan luokittelu varmasti tapahtuneeksi. Jos sähköposti osuu dokumenttikartalla tyhjään soluun tai sellaiseen johon on aiemmin osunut usean eri luokan sähköposteja, katsotaan luokittelu epävarmaksi.

Käytännössä yhden ajon suorittaminen kesti omalla kannettavallani varsin pitkään eli n. 5 vuorokautta. Operaatio kesti näin kauan huolimatta siitä, että sanavektorin pituutta ja karttojen kokoa oli pienennetty suositelluista. Tulokset eivät olleet kovin hyviä. Tulokset varmasti paranisivat käyttämällä suurempia karttoja sekä ajamalla paljon testiajoja eri parametrien ja toteutusyksityiskohtien parhaiden vaihtoehtojen selvittämiseksi. Käytännössä tätä työtä ei kuitenkaan voida viisi vuorokautta kestävällä ajolla järkevässä ajassa suorittaa.

Sanakohtaisilla tilastollisilla menetelmillä yhden luokitusajon kestoaika on n. 10 min.

WebSOM ajon pitkä kesto johtuu toisaalta erillisten operaatioiden määrästä ja siitä, että käsiteltävä datamäärä kasvaa algoritmissa huomattavasti.

20 000 sähköpostin aineistossani yksikäsitteisiä sanoja on n. 187 000. Yksikäsitteisiä sanatriploja eli yhdistelmiä, joissa on sama sana, sitä edeltävä ja seuraava sana aineistossa on n. 1 249 000.

Sanojen satunnaislukujen muodostusajossa täytyy käydä läpi 187 000 sanaa ja suorittaa niille satunnaislukuvektorin pituus * sanojen määrä eli esim. 20 * 187 000 = 3 740 000 INSERT-lausetta. Selvitettäessä tripla-mahdollisuudet täytyy suorittaa kaikkien 20 000:n sähköpostin esikäsittelyoperaatiot sekä 1 249 000 INSERT-lausetta. Odotusarvovektorin muodostuksessa täytyy hakea 187 000 sanalle kullekin 3 hakuoperaatiota (edeltävien sanojen satunnaisluvut, omat luvut ja seuraavien sanojen satunnaisluvut). Sekä odotusarvovektorin pituus * sanojen määrä eli esim. 60 * 187 000 = 11 220 000 INSERT-lausetta. Nämä operaatiot täytyy suorittaa aina vaihdettaessa varsinaista esikäsittelymenetelmää tai satunnaislukuvektorin pituutta.

Sanakartan muodostamiseen tarvitaan 187 000 * 60 = 11 220 000 lukua.

Kun sanakartan koko on 16 * 12 (melko pieni), tarvitaan kaikkien sähköpostien histogrammien tallettamiseen 192 * 20 000 = 3 840 000 INSERT-lausetta. Saman verran lukuja tarvitaan myös dokumenttikartan muodostamiseen.

Sanaperustaisessa tilastollisessa käsittelyssä näitä operaatioita ei tarvita lainkaan.

7.4 Sanatuplat Robinsonin menetelmällä

Yksittäisten sanojen tilastollinen käsittely Graham/Robinson -menetelmällä on melko helppo laajentaa ottamaan huomioon lisäksi sanaparit.

Sanojen esikäsittelyalgoritmia täytyy muokata ottamaan huomioon sanaparit. Eli kaikki sähköpostien vierekkäiset sanat talletetaan kantaan sanoina, joiden keskellä on välilyönti. Tavallaan puhutaan kahden sanan pituisista Markov-ketjuista.

Erikseen voitaisiin tarkastella tilanteita, joissa huomioidaan joko pelkästään sanaparit tai sekä sanaparit että yksittäiset sanat. Tässä tarkasteltiin vaihtoehtoa, jossa käsiteltiin sekä sanaparit että yksittäiset sanat. Erilaiset parametrit olivat samoissa asennoissa kuin parhaalla Robinson-tyypin ajolla.

Tulokset olivat kohtalaisia, mutta huomattavasti huonompia kuin parhaalla yksittäisten sanojen käsittelyn ajolla. Ajo kesti kaikkiaan n. 5 tuntia, minkä johdosta lopputulos on hieman sama kuin WebSOM-menetelmän suhteen: Tulokset todennäköisesti paranisivat ajamalla lisää ajoja erilaisilla parametreilla, mutta käytännössä ajon pitkän kestoajan takia tätä ei voida tehdä. Kohtuullisessa ajassa ei voitaisi suorittaa parhaiden parametriajojen löytämiseksi tarvittavaa ajomäärää.

Yksittäisiä sanoja 20 000 sähköpostin aineistossa on n. 187 000. Eri sanapareja aineistossa on n. 861 000. Yksittäisiä sanoja ja sanapareja yhteensä on n. 1 048 000.

Käsiteltävä datamäärä kasvaa n. 5-kertaiseksi. Suoritusaika taas kasvoi (10 min -> 250 min) eli n. 25-kertaiseksi. Tämä suoritusajan huomattavasti datamäärää nopeampi kasvu johtuu toisaalta siitä, ettei algoritmin suoritusaika kasva lineaarisesti (tietokantahaut hidastuvat määrän kasvaessa), mutta ennenkaikkea koneen keskusmuistin loppumisesta. Koneen keskusmuistiin mahtuu välimuistiin n. 30 000 sanaa. Yksittäisistä sanoista tämä on 15 % -- on melko todennäköistä, että usein käytetyt sanat löytyvät välimuistista eikä niitä tarvitse hakea tietokannasta eikä kovalevyltä. Sanaparien tapauksessa määrä on alle 3 % -- välimuistista ei ole enää kovin paljon hyötyä.

8 Tietokantarakenteet

Tietokannan keskeiset taulut ovat seuraavat:

Tietokantarakenteiden kuvauksessa on käytetty seuraavia lyhenteitä:

Taulujen rakenteet ovat seuraavat:

LUOKKA

Taulussa ovat listattuina eri luokat, joihin sähköposti voi kuulua.

LUOKKAKASITELTY

Aputaulu, jossa ilmaistaan, missä kulkee kunkin sähköpostin opetusjoukon ja tulosjoukon välinen raja.

LUOKKASANA

Yhdistää luokat sanoihin eli missä luokissa tietty sana esiintyy tietyllä esikäsittelymenetelmällä.

POSTIHISTOGRAMMI

WebSOM-menetelmän tarvitsema taulu, johon on talletettu kunkin sähköpostin sanakartta.

SAHKOPOSTI

Varsinaiset sähköpostit

SAHKOPOSTISANA

Aputaulu esikäsittelyrutiinien tarkistukseen, jossa on listattuna kunkin sähköpostin sanaesiintymät.

SANA

Kaikki sähköposteissa esiintyvät sanat.

SANAESIINTYMA

Tietyn sanan esiintymämäärät tietyllä esikäsittelymenetelmällä.

SANAODOTUSARVO

WebSOM-menetelmän tarvitsema sanan odotusarvotaulukko, johon on huomioitu sanaa edeltävä ja seuraava sana.

SANASATUNNAISLUKU

WebSOM-menetelmän tarvitsema sanan satunnaislukutaulukko.

SANATRIPLA

WebSOM-menetelmän tarvitsema taulu, jolla sana yhdistetään edellisiin ja seuraaviin sanoihin.

TULOS

Tietyn luokitteluajon tulos tietyllä sähköpostilla.

TULOSLUOKKA

Sähköpostin kaikkien luokkien luokittelutodennäköisyydet tietyssa luokitteluajossa. Oleellinen Bayes-pohjaisilla menetelmillä.

9 Tulokset

Tässä luvussa on esitelty testiajot ja niiden tulokset.

Seuraavassa on ajettu samat ajot Paul Graham -menetelmällä sekä siten, että esikäsittelyssä on otettu mukaan sekä subject + content, että siten, että mukaan on otettu header + content.

Muutoin ajoissa on tarkasteltu Grahamin kaavojen ongelmia harvoin aineistossa esiintyvien sanojen suhteen.

Sarakkeet ovat seuraavat:

Näistä on nähtävissä toisaalta, että Grahamin menetelmässä todella harvinaiset sanat aiheuttavat virhettä. Näiden harvinaisten sanojen poistaminen aineistosta parantaa tuloksia.

Header + content vaikuttaa subject + content esikäsittelymenetelmää paremmalta vaihtoehdolta (kolmessa tapauksessa neljästä).

Seuraavassa on myös ajettu samat ajot subject & header -yhdistelmillä erilaisilla variaatioilla. Muutoin ajoissa on tutkittu todennäköisyyksien yhdistämiskaavassa mukaan otettavien sanojen lukumäärän vaikutusta. Kaikissa tarkasteluissa on otettu mukaan vain sanat, joita on ollut aineistossa vähintään 10.

Tällä alueella header+content -esikäsittely vaikuttaa toimivan huomattavasti paremmin kuin subject+content. Mukaan otettavien sanojen määrässä optimialue näyttäisi olevan jossain 2-15 välillä.

Seuraavassa on tarkasteltu späm-suojauksen vaikutusta yhdistelmällä 15 mukaanotettavaa sanaa, joita on aineistossa vähintään 10. Späm-suojauksella tässä tarkoitetaan, että späm-luokkaan hyväksytään vain ne viestit, joilla minkään muun luokan todennäköisyys ei ole suurempi kuin tietty suojausraja.

Tässä on uutena sarakkeena FP = false positives = virheellisesti späm:ksi tulkittujen viestien määrä.

Tästä nähdään, että suojausta kasvattamalla voidaan merkittävästi pienentää false-positiivien määrää.

Seuraavassa on suoritettu ajoja Robinsonin kaavoilla.

Ensimmäisessä ajossa (header+content) tulokset ovat FP-sarakkeessa huomattavasti huonompia kuin Grahamilla, vaikka muutoin virheellisesti luokiteltujen määrä on selkeästi pienempi. Epävarmojen määrä on huomattavasti suurempi - tämä on tyypillistä Robinson-kaavoille, joilla epävarmat huomioidaan paljon selkeämmin.

Seuraavassa tarkasteltiin Robinsonia subject+content esikäsittelyllä:

Tulokset ovat huonompia (sekä E että FP) vaikkakin epävarmojen määrä on pienempi.

Seuraavassa robinsoniin (subject+content) otettiin mukaan vain sanat, jotka esiintyvät aineistossa vähintään 10 kertaa:

-> E pieneni, FP kasvoi.

Seuraavassa tehtiin sama tarkastelu, mutta esikäsittelynä header+content:

-> Tässä myös E ja FP pienenivät vaikka U kasvoi.

Seuraavassa otettiin subject+content esikäsittelyllä mukaan kaikki sanat ja käytettiin 0.9 suojausta:

E ja FP pienenivät hieman, epävarmat pysyivät samoina.

Kaikki loput testiajot on suoritettu header+content esikäsittelyllä.

Seuraavassa tarkastelussa tutkittiin suojauksen pienentämisen vaikutusta:

Tästä voidaan havaita, että jos suojaus oli alle 0.4 FP:t katosivat, mutta tämä tapahtui epävarmojen määrän voimakkaalla kasvamisella. Näin suuri epävarmojen määrä tuskin olisi käytännön järjestelmässä hyväksyttävällä tasolla.

Aiemmin on viestin todettu kuuluvan johonkin luokkaan, jos todennäköisyys ao. luokkaan kuulumiselle on yli 0.9. Seuraavassa kokeiltiin kasvattaa tämä raja arvoon 0.98:

Väärät ja oikeat tulkinnat vähenivät ja epävarmat lisääntyivät. Virheelliset tulkinnat eivät kuitenkaan täysin poistuneet.

Seuraavassa tarkastelussa on testattu ajatusta, että sanat, joilla ei ole kovin paljoa merkitystä lopputulokseen eli joiden todennäköisyys tiettyyn luokkaan kuulumisesta on lähellä 0.5:ta, pitäisi poistaa tarkastelusta, jotta ne eivät aiheuttaisi turhia häiriöitä:

Sanojen poistaminen vähensi vääriä ja oikeita sekä kasvatti epävarmoja. Virheelliset tulkinnat eivät kuitenkaan poistuneet.

Seuraavassa on haettu parhaita arvoja menetelmän s ja x -parametreille. Aiemmin käytetyt arvot ovat olleet s = 1 ja x = 0.5.

Näiden tarkastelujen perusteella jatkossa käytettäviksi arvoiksi valittiin x = 0.4 ja s = 0.3.

Seuraavassa on tarkasteltu parametrointia, jolla säädetään lopputulosta lähemmäksi ei-späm -tulkintaa. Eli jos johonkin muuhun luokkaan kuulumisen todennäköisyys on suurempi kuin tietty kerroin, niin viestiä ei luokitella späm-luokkaan, vaan epävarmoihin:

Tällä tavalla saadaan virheellisten määrä pienemmäksi, epävarmojen määrän kasvamisen kustannuksella.

Seuraavassa luokiteltiin kaikki englanninkieliset normaalit sähköpostit omaan luokkaansa sen sijaan, että ne olisivat kuuluneet aluekohtaisiin luokkiin.

Tämä oli kaikin puolin hyvä uudistus: FP ja E-määrät pienenivät merkittävästi, oikein tunnistetut kasvoivat ja epävarmat tapaukset vähenivät.

Seuraavassa muutettiin moniluokka-algoritmia siten, että späm-vastapari on english. Tähän perusteena oli se, että jos englanninkielisten normaalien sähköpostien puolella on suomenkielisiä sähköposteja, se turhaan huonontaa tasapainoa normaalien englanninkielisten sähköpostien suhteen.

Tämä menetelmä vähensi huomattavasti E ja FP-määriä ja kasvatti hieman K-määriä. Epävarmat kasvoivat vain hiukan. Ratkaisu oli siis varsin onnistunut.

HTML-tagit ovat varsin harvinaisia normaaleissa sähköposteissa, mutta yleisiä roskposteissa. Tämä aiheuttaa HTML-tageilla turhan suuren roskapostileiman ja johtaa virhetulkintoihin paljon HTML-tageja sisältävien sähköpostien kohdalla. Seuraavaksi tarkasteltiin muutosta esikäsittelyalgorimiin, jolla html-tagit jätetään aineistosta kokonaan pois.

HTML-tagien poisto vähensi huomattavasti FP:den määrää ja vain hieman kasvatti E ja U-tyyppejä ja vähensi K-tyyppiä.

Tämä oli paras Robinson-tulos ja sillä saatiin virheellisesti späm-viesteiksi tulkittujen oikeiden viestien määräksi 0,0004 (0,04 %).

WebSOM -menetelmällä saatiin tuloksiksi:

f-rate: 0,0102 (1,02 %)

FP-määrä ei ollut kovin suuri (ensimmäiseksi ajoksi), mutta U-osuus oli iso. Se saattaisi pienentyä isommilla kartoilla.

Useampisanaisen Robinson-tyylisen luokittelun tulokseksi saatiin seuraavaa:

f-rate: 0,0073 (0,73 %)

Tulos on huonompi kuin samoilla kaavoilla yksisanaisesti toimittaessa. Luultavasti hiottu lopputulos olisi parempi - erilaisten parametrien säätämiseksi tarvittaisiin paljon ajoja.

WebSOM -menetelmää voisi kokeilla isommilla kartoilla ja pitemmillä sanavektoreilla. Lähteessä [3] mainittuja kartoille tehtäviä blur-operaatiot voisi kokeilla. Erilaisia e-arvoja sanojen odotusarvovektoreille voisi kokeilla (myös arvoa e=1).

WebSOM -menetelmässä odotusarvovektorit lasketaan satunnaisluvuista. Odotusarvot voisi muodostaa ehkä perustellummin, jos sanavektorit eivät koostuisi satunnaisluvuista vaan ne muodostettaisiin jollain kuvauksella, jolla esim. synonyymit olisivat lähellä tosiaan.

WebSOM -menetelmässä voitaisiin tyhjiin soluihin dokumenttikartalla osuvat dokumentit tulkita kuuluvaksi tiettyyn luokkaan, jos kaikki ympäröivät tai lähimmät solut kuuluvat tiettyyn luokkaan. Tämä voisi pienentää suurta epävarmojen tulkintojen määrää.

Headerien vaikutusta voisi kokeilla WebSOM- ja monisanamenetelmiin.

Jos WebSOM ja monisanamenetelmät saadaan toimimaan paremmin, voisi kokeilla eri menetelmien yhdistämistä: tekevätkö eri menetelmät virheitä eri sanoissa? Sähköpostit, joista menetelmät ovat eri mieltä, voitaisiin luokitella epävarmoiksi.

11 Yhteenveto

Työssä tutkittiin ja optimoitiin kokeellisesti erilaisia oppivia menetelmiä späm-sähköpostien tunnistukseen.

Työssä tarkasteltiin Paul Grahamin ja Gary Robinsonin esittelemiä kaavoja yksisanaisessa tilastollisessa käsittelyssä.

Monisanaisessa tunnistuksessa käytettiin WebSOM-neuraaliverkkomenetelmää ja Robinsonin kaavoja sovellettuna sanapereihin eli kahden sanan pituisiin Markov-ketjuihin.

Työssä saavutetut keskeiset havainnot ovat seuraavat:

• Yksisanaisella tilastollisella käsittelyllä Robinsonin kaavoilla voidaan saavuttaa varsin hyvä luokittelutarkkuus.

• Sähköpostin header-osan mukaanottaminen parantaa lopputuloksia yksisanaisissa tilastollisissa menetelmissä.

• Suomenkielisen vastaanottajan on tärkeää käyttää moniluokittelua, jotta englanninkielisiä sähköposteja ei suotta tulkittaisi roskapostiksi. Englanninkielisten oikeiden sähköpostien joukkoa kannattaa tarkastella roskapostijoukon vastaparina.

• HTML-tagien poistaminen esikäsittelyssä on oleellista, jottei HTML-tageja sisältäviä oikeita viestejä tulkittaisi roskapostiksi.

• Teoreettisesti parempien sanojen välisiä suhteita analysoivien luokittelumenetelmien käyttäminen ja niiden riittävä optimointi vaatii huomattavia laitteistoresursseja, joita ei itselläni ollut tähän työhön käytettävissä. Siksi näillä menetelmillä saavutetut tulokset jäivät yksisanaisia menetelmiä heikommiksi.

Projektin puitteissa syntyi ohjelmakoodia 174 kt ja 5535 riviä. Aikaa työn tekemiseen kului n. 250 tuntia.

Kirjallisuutta

• [1] Graham, Paul. 2002 - 2003.
  A Plan for Spam. http://www.paulgraham.com/spam.html
  ja
  Better Bayesian Filtering. http://www.paulgraham.com/better.html

• [2] Robinson, Gary. 2003.
  A Statistical Approach to the Spam Problem. Linux Journal. Issue 107, 2003.
  Saatavilla myös: http://www.linuxjournal.com/article.php?sid=6467
  ja
  SpamBayes: Background Reading. http://spambayes.sourceforge.net/background.html
  ja
  Spam Detection. http://radio.weblogs.com/0101454/stories/2002/09/16/spamDetection.html

• [3] Honkala Timo, Kaski Samuel, Lagus Krista, Kohonen Teuvo. 1997.
  WEBSOM - Self-Organizing Maps of Document Collections. WSOM'97, Proceedings of the Workshop on Self-Organizing Maps. Espoo. Libella Painopalvelu Oy. pp. 310-315.

• [4] Markov, Andrey.
  Markov-ketjut on julkaistu ensimmäisen kerran venäjänkielisessä julkaisussa 1906.
  Käytännössä kuvausta Markov-ketjuista löytyy esim.: http://en.wikipedia.org/wiki/Markov_chain

• [5] Puhakka, Aapo. 2001.
  Erilaisten käyttöliittymien yhteisen toiminnallisuuden keskittäminen sovelluspalvelimeen Diplomityö, Teknillinen korkeakoulu, Tietotekniikan osasto.
  Saatavilla myös: http://aapo.iki.fi/dityo

• [6] Graham, Paul ja MathPages
  Probability
  http://www.paulgraham.com/antispam.html
  Combining Probabilities
  http://www.mathpages.com/home/kmath267.htm

• [7] Kohonen Teuvo, Hynninen Jussi, Kangas Jari, Laaksonen Jorma. 1996.
  SOM_PAK: The Self-Organizing Map Program Package.
  http://www.cis.hut.fi/research/som_lvq_pak.shtml