Bayesilainen roskapostin suodatus

Bayesin roskapostin suodatus on roskapostin suodatusmenetelmä , joka perustuu Bayesin lauseen suoraan käyttöön perustuvaan naiiviin Bayesin luokitteluun . Bayesin lause on nimetty sen kirjoittajan Thomas Bayesin (1702–1761) mukaan. Hän oli englantilainen matemaatikko ja pappi, joka ehdotti ensimmäisen kerran lauseen käyttöä uskomusten korjaamiseen päivitettyjen tietojen perusteella.

Historia

Ensimmäinen tunnettu ohjelma, joka suodatti postin bayesialaisella luokittimella, oli Jason Rennien iFile, joka julkaistiin vuonna 1996. Ohjelma käytti postin lajittelua kansioiden mukaan [1] . Ensimmäinen akateeminen julkaisu Naive Bayes roskapostin suodatuksesta ilmestyi vuonna 1998 [2] . Pian tämän julkaisun jälkeen aloitettiin kaupallisten roskapostisuodattimien luominen. . Kuitenkin vuonna 2002 Paul Graham pystyi merkittävästi vähentämään väärien positiivisten tulosten määrää siinä määrin, että Bayes-suodatinta voitiin käyttää ainoana roskapostisuodattimena [3] [4] [5] .

Peruslähestymistavan muunnelmia on kehitetty monissa tutkimuspapereissa ja toteutettu ohjelmistotuotteissa [6] . Monet nykyaikaiset sähköpostiohjelmat käyttävät Bayesilaista roskapostisuodatusta. Käyttäjät voivat myös asentaa erillisiä sähköpostinsuodatusohjelmia. Postipalvelinsuodattimet - kuten DSPAM , SpamAssassin , SpamBayes , SpamProbe , Bogofilter , CRM114 - käyttävät Bayesin roskapostin suodatusmenetelmiä [5] . Sähköpostipalvelinohjelmisto joko sisältää suodattimia jakelussaan tai tarjoaa APIn ulkoisten moduulien yhdistämiseen.

Kuvaus

Suodatinta opetettaessa lasketaan ja tallennetaan jokaiselle kirjaimissa esiintyvälle sanalle sen "paino" - arvio todennäköisyydestä , että tätä sanaa sisältävä kirje on roskapostia. Yksinkertaisimmassa tapauksessa taajuutta käytetään arviona: "roskapostissa esiintymiset / esiintymiset yhteensä". Monimutkaisemmissa tapauksissa on mahdollista esikäsitellä teksti: saattaa sanat alkuperäiseen muotoonsa, poistaa apusanoja, laskea kokonaisten lauseiden "paino", translitterointi ja niin edelleen.

Kun tarkistetaan äskettäin saapunut kirje, "spamiinin" todennäköisyys lasketaan käyttämällä yllä olevaa kaavaa hypoteesijoukolle. Tässä tapauksessa "hypoteesit" ovat sanoja, ja jokaiselle sanalle "hypoteesin luotettavuus" on tämän sanan osuus kirjaimesta ja "tapahtumariippuvuus hypoteesista" on sanan aiemmin laskettu "paino". Eli kirjaimen "paino" tässä tapauksessa on kaikkien sen sanojen keskimääräinen "paino". $P(A_{i})=N_{sana_{i}}/N_{sanaa~yhteensä}$ $P(B\mid A_{i})$

Kirje luokitellaan "roskapostiksi" tai "ei-roskapostiksi" sen mukaan, ylittääkö sen "paino" tietyn käyttäjän asettaman palkin (yleensä ne vievät 60-80 %). Kun kirjaimesta on tehty päätös, sen sisältämien sanojen ”painot” päivitetään tietokantaan.

Matemaattiset perusteet

Postin Bayes-suodattimet perustuvat Bayesin lauseeseen. Bayesin lausetta käytetään useita kertoja roskapostin yhteydessä:

ensimmäisen kerran laskea todennäköisyys, että viesti on roskapostia, tietäen, että annettu sana esiintyy viestissä;
toisen kerran laskemaan todennäköisyys, että viesti on roskapostia, kun otetaan huomioon kaikki sen sanat (tai niiden vastaavat osajoukot);
joskus kolmannen kerran, kun kohdataan harvinaisia sanoja sisältäviä viestejä.

Lasketaan todennäköisyys, että tietyn sanan sisältävä viesti on roskapostia

Oletetaan, että epäilty viesti sisältää sanan "Replica". Useimmat ihmiset, jotka ovat tottuneet vastaanottamaan sähköpostia, tietävät, että tämä viesti on todennäköisesti roskapostia, ja tarkemmin sanottuna tarjous myydä kuuluisien tuotemerkkien väärennettyjä kelloja. Roskapostin tunnistusohjelma ei kuitenkaan "tiedä" tällaisia tosiasioita; se voi vain laskea todennäköisyyksiä.

Ohjelmiston tämän määrittämiseen käyttämä kaava on johdettu Bayesin lauseesta ja kokonaistodennäköisyyskaavasta :

\Pr(S\mid W)={\frac {\Pr(W\mid S)\cdot \Pr(S)}{\Pr(W)))={\frac {\Pr(W\ mid S)\cdot \Pr(S)}{\Pr(W\mid S)\cdot \Pr(S)+\Pr(W\mid H)\cdot \Pr(H)))

missä:

$\Pr(S\mid W)$ - ehdollinen todennäköisyys, että viesti on roskapostia, mikäli siinä on sana "Replica";
$\Pr(S)$ on kokonaistodennäköisyys, että satunnainen viesti on roskapostia;
$\Pr(W\mid S)$ — ehdollinen todennäköisyys, että sana "replica" esiintyy viesteissä, jos ne ovat roskapostia;
$\Pr(H)$ on kokonaistodennäköisyys, että satunnainen viesti ei ole roskapostia (eli "kinkku");
$\Pr(W\mid H)$ on ehdollinen todennäköisyys, että sana "replica" esiintyy viesteissä, jos ne ovat "kinkku".

Roskapostisana _

Viimeaikaiset tilastotutkimukset [7] ovat osoittaneet, että nykyään todennäköisyys, että kaikki viestit ovat roskapostia, on vähintään 80 %: . $\Pr(S)=0,8;\Pr(H)=0,2$

Useimmat bayesilaiset roskapostintunnistusohjelmat kuitenkin olettavat, että viestille ei ole ensisijaisesti "roskapostia" mieluummin kuin "kinkkua", ja oletetaan, että molemmilla tapauksilla on yhtä suuri 50 %:n todennäköisyys: . $\Pr(S)=0,5,\Pr(H)=0,5$

Suodattimia, jotka käyttävät tätä hypoteesia, kutsutaan "no bias" -suodattimiksi. Tämä tarkoittaa, että heillä ei ole ennakkoluuloja saapuvan sähköpostin suhteen. Tämän oletuksen avulla voimme yksinkertaistaa yleisen kaavan seuraavasti:

\Pr(S\mid W)={\frac {\Pr(W\mid S)}{\Pr(W\mid S)+\Pr(L\mid K)))

Merkitystä kutsutaan sanan "spamiiniudeksi" ; jossa yllä olevassa kaavassa käytetty luku on suunnilleen sama kuin sanan sisältävien viestien suhteellinen esiintymistiheys viesteissä, jotka tunnistettiin roskapostiksi oppimisvaiheen aikana, eli: $Pr(S|W)$ $W$ $\Pr(W|S)$ $W$

Pr(W_{i}\mid S)={\frac {\mathrm {count} (M:W_{i}\in M,M\in S)}{\sum _{j}\mathrm { count} (M:W_{j}\in M,M\in S)}}

Vastaavasti suunnilleen yhtä suuri kuin sanan sisältävien viestien suhteellinen tiheys viesteissä , jotka tunnistetaan "kinkuksi" oppimisvaiheen aikana. $\Pr(W|K)$ $W$

Pr(W_{i}\mid H)={\frac {\mathrm {count} (M:W_{i}\in M,M\in H)}{\sum _{j}\mathrm { count} (M:W_{j}\in M,M\in H)}}

Jotta nämä likiarvot olisivat merkityksellisiä, koulutusviestien joukon on oltava suuri ja melko edustava. On myös toivottavaa, että opetussanomajoukko sopii 50 %:n uudelleenjakautumishypoteesiin roskapostin ja kinkun välillä, eli että roskaposti- ja kinkkuviestijoukot ovat samankokoisia.

Tietysti virhealtista on määrittää, onko viesti "roskapostia" vai "kinkkua" vain yhden tietyn sanan perusteella. Tästä syystä Bayesin roskapostisuodattimet yrittävät tarkastella useita sanoja ja yhdistää niiden roskapostin määrittääkseen yleisen todennäköisyyden, että viesti on roskapostia.

Yksittäisten todennäköisyyksien yhdistäminen

Ohjelmistojen roskapostisuodattimet, jotka on rakennettu naiivin Bayes-luokittimen periaatteille , tekevät "naiivin" oletuksen, että tapahtumat , jotka vastaavat tietyn sanan läsnäoloa sähköpostissa tai viestissä, ovat riippumattomia toisistaan. Tämä yksinkertaistaminen ei yleensä pidä paikkaansa luonnollisissa kielissä, kuten englannissa, joissa adjektiivin löytämisen todennäköisyyttä lisää esimerkiksi substantiivi. Tällaisen "naiivin" oletuksen perusteella voimme johtaa seuraavan kaavan estimointiin ratkaistaksemme ongelman, joka koskee viestien luokittelua vain kahteen luokkaan: (roskaposti) ja ("kinkku", eli ei roskapostia) Bayesin lauseesta todennäköisyys, että koko viesti sisältää sanat : $S$ $H=\neg S$ ${\displaystyle W_{1},W_{2},...W_{N))$

p(S\mid W_{1},W_{2},...W_{N})=

[Bayesin lauseen mukaan] [koska niiden oletetaan olevan riippumattomia]

={\frac {p(W_{1},W_{2},...W_{N}\mid S)\cdot p(S)}{p(W_{1},W_{2} ,...W_{N})}}=

W_i

=

={\frac {\prod _{i}p(W_{i}\mid S)\cdot p(S)}{p(W_{1},W_{2},...W_{N })}}=

[Bayesin lauseella] [ kokonaistodennäköisyyskaavalla ]

={\frac {\prod _{i}{\frac {p(S\mid W_{i})\cdot p(W_{i})}{p(S)))\cdot p(S )}{p(W_{1},W_{2},...W_{N})}}=

=

={\frac {\prod _{i}{\frac {p(S\mid W_{i})\cdot p(W_{i})}{p(S)))\cdot p(S )}{\prod _{i}(p(W_{i}\mid S))\cdot p(S)+\prod _{i}(p(W_{i}\mid \neg S))\cdot p(\neg S)}}=

={\frac {\prod _{i}(p(S\mid W_{i})\cdot p(W_{i}))\cdot p(S)^{1-N)){\ prod _{i}(p(S\mid W_{i})\cdot p(W_{i}))\cdot p(S)^{1-N}+\prod _{i}(p(\neg) S\mid W_{i})\cdot p(W_{i}))\cdot p(\neg S)^{1-N}}}=

={\frac {\prod _{i}p(S\mid W_{i})}{\prod _{i}(p(S\mid W_{i}))+\left({\ frac {p(\neg S)}{p(S)}}\right)^{1-N}\cdot \prod _{i}p(\neg S\mid W_{i})}}

Joten olettaen , että meillä on: $p(S)=p(\neg S)=0,5$

p={\frac {p_{1}p_{2}\cdots p_{N}}{p_{1}p_{2}\cdots p_{N}+(1-p_{1})(1 -p_{2})\cdots (1-p_{N})}}

missä:

$p=Pr(S\mid W_{1},W_{2},...,W_{N})$ - todennäköisyys, että viesti sisältää sanat - roskaposti; ${\displaystyle W_{1},W_{2},...,W_{N))$
$p_{1}$ - ehdollinen todennäköisyys , että viesti on roskapostia edellyttäen, että se sisältää ensimmäisen sanan (esimerkiksi "replica"); $p(S\mid W_{1})$
$p_{2}$ - ehdollinen todennäköisyys , että viesti on roskapostia edellyttäen, että se sisältää toisen sanan (esimerkiksi "katsoi"); $p(S\mid W_{2})$
jne.
$p_{N}$ — ehdollinen todennäköisyys , että viesti on roskapostia, jos se sisältää N: nnen sanan (esimerkiksi "koti"). $p(S\mid W_{N})$

(Esittely: [8] )

Tulosta p verrataan yleensä johonkin kynnykseen (esim . ) sen päättämiseksi, onko viesti roskapostia vai ei. Jos p on pienempi kuin kynnys, viestiä pidetään todennäköisenä "kinkuna", muuten sitä pidetään todennäköisenä roskapostina. $0.5$

Harvinaisten sanojen ongelma

Se tapahtuu, jos sanaa ei ole koskaan tavattu oppimisvaiheessa: sekä osoittaja että nimittäjä ovat nolla sekä yleisessä kaavassa että roskapostikaavassa.

Yleisesti ottaen sanat, joita ohjelma kohtasi vain muutaman kerran harjoitusvaiheessa, eivät ole edustavia (otoksessa oleva tietojoukko on pieni, jotta tällaisen sanan ominaisuudesta voitaisiin tehdä luotettava johtopäätös). Yksinkertainen ratkaisu on jättää huomiotta tällaiset epäluotettavat sanat.

Muita heuristisia parannuksia

"Neutraalit" sanat - kuten "the", "a", "some" tai "is" (englanniksi) tai niiden vastineet muilla kielillä - voidaan jättää huomiotta. Yleisesti ottaen jotkut Bayes-suodattimet yksinkertaisesti jättävät huomioimatta kaikki sanat, joiden roskapostipitoisuus on noin 0,5, koska tässä tapauksessa saadaan laadullisesti parempi ratkaisu. Vain ne sanat lasketaan, joiden roskasisältö on noin 0,0 (laillisten viestien tunnusmerkki - "kinkku") tai lähellä 1,0 (roskapostin tunnusmerkki). Pudotusmenetelmä voidaan konfiguroida esimerkiksi niin, että tutkittavassa viestissä säilytetään vain ne kymmenen sanaa, joilla on suurin absoluuttinen arvo |0,5 − Pr |.

Jotkut ohjelmistotuotteet ottavat huomioon sen tosiasian, että tietty sana esiintyy useita kertoja tarkistettavassa viestissä [9] , toiset eivät.

Jotkut ohjelmistotuotteet käyttävät lauseita - kaavoja (sanasarjoja) luonnollisten kielten eristettyjen sanojen sijaan [10] . Esimerkiksi nelisanaisen "kontekstiikkunan" avulla he laskevat lauseen "Viagra, hyvä" roskapostisuuden sen sijaan, että laskisivat yksittäisten sanojen "Viagra", "hyvä" ja "for" roskapostin. Tämä menetelmä on kontekstiherkempi ja poistaa paremmin Bayesin kohinan suuremman tietokannan kustannuksella.

Sekamenetelmät

"Naiivin" bayesilaisen lähestymistavan lisäksi on muitakin tapoja yhdistää - yhdistä eri sanojen yksittäiset todennäköisyydet. Nämä menetelmät eroavat "naiivista" menetelmästä tulotietojen tilastollisista ominaisuuksista tekemiensä oletusten suhteen. Kaksi erilaista hypoteesia johtavat radikaalisti erilaisiin kaavoihin yksittäisten todennäköisyyksien kokoelmalle (liitolle).

Voit esimerkiksi testata oletuksen yksittäisten todennäköisyyksien joukosta, jonka tulon logaritmi vakioon asti noudattaa khin neliöjakaumaa 2 N vapausasteella, voit käyttää kaavaa:

p=C^{-1}(-2\ln(p_{1}p_{2}\cdots p_{N}),2N)

jossa C −1 tarkoittaa khin neliöjakaumafunktion käänteisfunktiota (katso Käänteinen khin neliöjakauma ).

Yksilöllisiä todennäköisyyksiä voidaan myös yhdistää Markovin erottelumenetelmillä .

Ominaisuudet

Tämä menetelmä on yksinkertainen (algoritmit ovat alkeellisia), kätevä (voit tehdä ilman "mustia listoja" ja vastaavia keinotekoisia temppuja), tehokas (riittävän suuren näytteen harjoittamisen jälkeen se katkaisee jopa 95-97% roskapostista) , ja virheiden sattuessa sitä voidaan kouluttaa edelleen. Yleisesti ottaen on kaikki viitteitä sen laajasta käytöstä, mitä käytännössä tapahtuu - melkein kaikki nykyaikaiset roskapostisuodattimet on rakennettu sen pohjalle.

Menetelmällä on kuitenkin myös perustavanlaatuinen haittapuoli: se perustuu oletukseen , että jotkut sanat ovat yleisempiä roskapostissa, kun taas toiset ovat yleisempiä tavallisissa kirjaimissa , ja se on tehoton, jos tämä oletus on virheellinen. Kuitenkin, kuten käytäntö osoittaa, edes henkilö ei pysty määrittämään tällaista roskapostia "silmällä" - vasta kun olet lukenut kirjeen ja ymmärtänyt sen merkityksen. On olemassa Bayesin myrkytysmenetelmä, voit paljon ylimääräistä tekstiä, joka on joskus valittu huolellisesti suodattimen "huijaamiseksi".

Toinen toteutukseen liittyvä ei-pääasiallinen haitta on, että menetelmä toimii vain tekstin kanssa. Tietäessään tämän rajoituksen roskapostittajat alkoivat laittaa mainostietoja kuvaan. Kirjeen teksti joko puuttuu tai siinä ei ole järkeä. Tätä vastaan on käytettävä joko tekstintunnistustyökaluja ("kallis" menettely, jota käytetään vain ehdottoman välttämättömässä) tai vanhoja suodatusmenetelmiä - "mustia listoja" ja säännöllisiä lausekkeita (koska sellaisilla kirjaimilla on usein stereotyyppinen muoto).

Katso myös

Bayesin ohjelmointi

Muistiinpanot

↑ Jason Rennie. ifile (1996). Arkistoitu alkuperäisestä 25. lokakuuta 2012. (määrätön)
↑ Sahami, Dumais, Heckerman, Horvitz, 1998 .
↑ Paul Graham (2003), Better Bayesian filtering Arkistoitu 21. kesäkuuta 2010 Wayback Machinessa
↑ Brian Livingston (2002), Paul Graham tarjoaa hämmästyttävän vastauksen roskapostiviesteihin Arkistoitu 10. kesäkuuta 2010 Wayback Machinessa
↑ 1 2 Guzella, Caminhas, 2009 .
↑ Roskapostin hallinta . MozillaZine (marraskuu 2009). Arkistoitu alkuperäisestä 25. lokakuuta 2012. (määrätön)
↑ Yli 90 prosenttia sähköposteista kolmannella vuosineljänneksellä (2008) oli roskapostia, Certification Magazine . Käyttöpäivä: 16. syyskuuta 2012. Arkistoitu alkuperäisestä 23. syyskuuta 2012. (määrätön)
↑ Todennäköisyyksien yhdistäminen . Arkistoitu alkuperäisestä 16. huhtikuuta 2012. (määrätön)MathPagesissa
↑ Brian Burton. SpamProbe – Bayesian roskapostin suodatussäädöt (2003). Arkistoitu alkuperäisestä 16. huhtikuuta 2012. (määrätön)
↑ Jonathan A. Zdziarski. Bayesin kohinanvaimennus: kontekstuaalinen symmetrialogiikka, joka hyödyntää kuvioiden johdonmukaisuusanalyysiä (pääsemätön linkki - historia ) (2004). (määrätön) (linkki ei saatavilla)

Kirjallisuus

Guzella T. S., Caminhas W. M. Katsaus koneoppimismenetelmiin roskapostin suodatukseen // Expert Systems with Applications. - 2009. - Vol. 36, nro. 7. - P. 10206-10222. doi : 10.1016 / j.eswa.2009.02.037 .
Metsis V., Androutsopoulos I., Paliouras G. . Roskapostin suodatus Naive Bayesilla – Mitkä Naive Bayes? // CEAS 2006: Third Conference on Email and Anti-Spam, 27.-28.7.2006, Mountain View, California, USA. – 2006.
Sahami M., Dumais S., Heckerman D., Horvitz E. Bayesin lähestymistapa roskapostin suodattamiseen // AAAI Workshop on Learning for Text Categorization. tekninen raportti. – 1998.

Linkit

Paul Graham. Roskapostisuunnitelma Arkistoitu 4. huhtikuuta 2004 Wayback Machinessa // Paul Grahamin henkilökohtainen verkkosivusto.