Bayesisk spamfiltrering

Den bayesiske spamfiltrering (henviser til Bayes teorem ) er en teknisk statistisk deteksjon av spam basert på den Naive Bayes klassifikator .

Bayesiske filtre fungerer ved å korrelere tilstedeværelsen av visse elementer (vanligvis ord, noen ganger andre ting) i en melding og om de vanligvis vises i uønskede meldinger ( spam ) eller i legitime meldinger. ( Skinke ) for å beregne sannsynligheten for at denne meldingen er spam.

Bayesian spam-filtrering er en kraftig teknikk for å håndtere spam-e-post. Den tilpasser seg hverandres postvaner og gir en falsk positiv rate som er lav nok til å være akseptabel.

Historisk

Den første e-filtrering program ved hjelp av Bayes var Jason Rennie er iFile program, utgitt i 1996. Dette programmet ble brukt til å klassifisere post i mapper . Den første akademiske publikasjonen om Bayesian spam-filtrering ble laget av Sahami et al. i 1998. I 2002 ble prinsippene for Bayesian-filtrering gjort oppmerksom på et bredere publikum i en artikkel av Paul Graham .

Variasjoner av den grunnleggende teknikken er implementert i flere forskningsarbeider og programvareprodukter . Mange moderne e-postagenter implementerer Bayesiske spamfiltre . Brukere kan også installere tredjepartsprogramvare som spesialiserer seg på denne jobben. Det er også mulig å distribuere denne type filtre på servere som bruker spesialisert programvare som DSPAM  (en) , Spamassassin , SpamBayes  (en) , Altospam , Bogofilter , OutClock , Spamihilator eller ASSP  (en) , og denne funksjonen er ofte integrert med selve e-postserveren.

Prosess

Visse ord vises mer sannsynlig i spam og legitim e-post. For eksempel vil de fleste ofte møte ordet "  Viagra  " i spam-e-postene sine, men de vil sjelden støte på det i deres legitime e-post. Filteret kjenner ikke disse sannsynlighetene på forhånd, og det tar derfor en læringskurve å evaluere dem. Læringen er brukerens ansvar, som manuelt må indikere om en melding er spam eller ikke. For hvert ord i hver "lærte" melding vil filteret justere sannsynligheten for å møte det ordet i søppelpost eller legitim e-post og lagre dem i sin database. For eksempel er det sannsynlig at Bayesian-filtre har stor sannsynlighet for å spamme ordet "Viagra", men svært lav sannsynlighet for ord som oppstår i legitim e-post, for eksempel navnene på venner og slektninger til brukeren.

Etter trening brukes ordsannsynligheter (også kalt sannsynlighetsfunksjoner ) for å beregne sannsynligheten for at en melding (alle disse ordene) er spam. Hvert ord i meldingen, eller i hvert fall hvert "interessante" ord i meldingen, bidrar til sannsynligheten for at meldingen blir spam. Dette bidraget beregnes ved bruk av Bayes teorem . Når beregningen for hele meldingen er fullført, sammenligner vi sannsynligheten for å være spam med en vilkårlig verdi (for eksempel 95%) for å markere eller ikke meldingen som spam.

Som med alle andre søppelfiltreringsteknikker, kan meldinger som er merket som søppelpost automatisk flyttes til en "søppel" -mappe, eller til og med slettes på stedet. Noen programvarer implementerer karantene mekanismer som definerer et tidsintervall der brukeren har muligheten til å gjennomgå programvarens beslutning.

Innledende læring kan ofte forbedres hvis noen gang dårlige programvarebeslutninger blir identifisert ( falske positive eller falske negativer ). Dette gjør at programvaren kan tilpasse seg utviklingen av spam.

Noen spamfiltre kombinerer resultatene av Bayesian spamfiltrering med andre heuristiske metoder (forhåndsdefinerte regler angående meldingsinnhold, undersøkelse av meldingskonvolutten  osv. ), Noe som fører til enda mer presis filtrering, noen ganger på bekostning av tilpasningsevne.

Matematiske grunnlag

Bayesianske spamfiltre er basert på Bayes 'teorem . Bayes teorem brukes flere ganger i sammenheng med spam:

• en første gang for å beregne sannsynligheten for at meldingen er spam, vel vitende om at et gitt ord vises i denne meldingen;
• en gang til, for å beregne sannsynligheten for at meldingen er spam, med tanke på alle ordene, eller en betydelig delmengde av ordene;
• noen ganger en tredje gang, for å håndtere sjeldne ord.

Beregn sannsynligheten for at en melding som inneholder et gitt ord er spam

Anta at den mistenkelige meldingen inneholder ordet "  Replika  ". I 2009 vet de fleste som er vant til å motta e-post at det er sannsynlig at denne meldingen er spam, spesielt et forsøk på å selge falske berømte klokkemerker. Programvare for spamoppdagelse ignorerer slike fakta, men alt det kan gjøre er å beregne sannsynligheter.

Formelen som programvaren bruker for å bestemme denne sannsynligheten er hentet fra Bayes 'teorem . Disse, i sin mest generelle form, er:

P(S|M)=P(M|S)⋅P(S)P(M|S)⋅P(S)+P(M|H)⋅P(H){\ displaystyle P (S | M) = {\ frac {P (M | S) \ cdot P (S)} {P (M | S) \ cdot P (S) + P (M | H) \ cdot P (H)}}}

eller:

• P(S|M){\ displaystyle P (S | M)}er sannsynligheten for at meldingen er spam, vel vitende om at ordet "  Replika  " er der;
• P(S){\ displaystyle P (S)} er den absolutte sannsynligheten for at enhver melding er spam;
• P(M|S){\ displaystyle P (M | S)}er sannsynligheten for at "  Replika  " vises i spam-meldinger;
• P(H){\ displaystyle P (H)}er den absolutte sannsynligheten for at enhver melding ikke er søppelpost (dvs. "  skinke  ");
• P(M|H){\ displaystyle P (M | H)}er sannsynligheten for at "  Replika  " vil vises i meldinger fra skinke .

(Bevis: Bayes 'setning # Andre skrifter om Bayes' setning )

Spamitet

Nyere statistikk viser at den nåværende sannsynligheten for at en melding blir spam, er minst 80%:

P(S)=0,8;P(H)=0,2{\ displaystyle P (S) = 0,8; P (H) = 0,2}

De fleste Bayesiansk spam deteksjon programvare mener at det ikke er a priori grunn til at en mottatt melding er spam i stedet for skinke , og vurdere de to tilfeller å ha identiske sannsynlighetene for 50%:

P(S)=0,5;P(H)=0,5{\ displaystyle P (S) = 0,5; P (H) = 0,5}

Filtre som antar denne antagelsen sies å være "upartiske", noe som betyr at de ikke har noen skjevhet i mottatt post. Denne antagelsen gjør det mulig å forenkle den generelle formelen ved å:

P(S|M)=P(M|S)P(M|S)+P(M|H){\ displaystyle P (S | M) = {\ frac {P (M | S)} {P (M | S) + P (M | H)}}}

Denne mengden kalles spamiciteten til ordet "  Replika  " og kan beregnes. Antallet som vises i denne formelen er tilnærmet av frekvensen av meldinger som inneholder "  Replika  " blant meldingene som er identifisert som spam i løpet av læringsfasen. Tilsvarende er tilnærmet av frekvensen av meldinger som inneholder "  Replika  " blant meldingene som er identifisert som skinke i løpet av læringsfasen. For at disse tilnærmingene skal være realistiske, må settet med "lærte" meldinger være tilstrekkelig stort og representativt. I tillegg anbefales det at meldingssettet som brukes til opplæring, er i samsvar med 50% antagelsen om splittelsen mellom spam og uskyldige meldinger, det vil si spam spam og spam corpus. Skinke er omtrent like store. P(M|S){\ displaystyle P (M | S)}P(M|H){\ displaystyle P (M | H)}

Å bestemme om en melding er spam eller ikke bare basert på tilstedeværelsen av ordet " Replica  " kan selvfølgelig  føre til feilen, og derfor prøver antispam-programvare å vurdere flere ord og kombinere søppelpost for å bestemme den samlede sannsynligheten for å være spam .

Kombiner individuelle sannsynligheter

Bayesisk programvare for spamfiltrering antar naivt at ordene i meldingen er uavhengige hendelser . Dette er galt i naturlige språk som fransk, hvor sannsynligheten for å finne et adjektiv, for eksempel, er påvirket av sannsynligheten for å ha et navn. Uansett, med denne antagelsen, kan vi trekke en annen formel fra Bayes 'teorem  :

s=s1s2⋯sIKKEs1s2⋯sIKKE+(1-s1)(1-s2)⋯(1-sIKKE){\ displaystyle 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})}}}

eller:

• s{\ displaystyle p} er sannsynligheten for at den mistenkelige meldingen er spam;
• s1{\ displaystyle p_ {1}}er sannsynligheten for at det er spam, vel vitende om at det inneholder et første ord (for eksempel "  Replika  ");P(S|M1){\ displaystyle P (S | M_ {1})}
• s2{\ displaystyle p_ {2}}er sannsynligheten for at det er nettsøppel, vel vitende om at det inneholder et andre ord (f.eks. "  klokker  ");P(S|M2){\ displaystyle P (S | M_ {2})}
• etc.
• sIKKE{\ displaystyle p_ {N}}er sannsynligheten for at det er spam, vel vitende om at det inneholder et ith-ord (for eksempel "  hjem  ").P(S|MIKKE){\ displaystyle P (S | M_ {N})}IKKE{\ displaystyle N}

(Demonstrasjon: Kombinere sannsynligheter på MathPages-siden)

Slike antakelser gjør Bayesian filtreringsprogramvare til en naiv Bayesisk klassifiseringsprosess .

Resultatet blir vanligvis sammenlignet med en gitt terskel for å avgjøre om meldingen er spam eller ikke. Hvis er under denne terskelen, blir meldingen ansett som en sannsynligvis legitim. Ellers regnes det som sannsynlig ulovlig. s{\ displaystyle p}s{\ displaystyle p}

Et annet uttrykk for formelen for å kombinere de individuelle sannsynlighetene

Ofte beregnes ikke direkte ved hjelp av formelen ovenfor, fordi den har en tendens til å produsere aritmetiske suppeoppgaver ( aritmetiske underløp ) en gang implementert i et dataprogram. I stedet kan vi bruke logaritmer ved å omskrive den opprinnelige formelen slik: s{\ displaystyle p}

1s-1=(1-s1)(1-s2)...(1-sikke)s1s2...sikke{\ displaystyle {\ frac {1} {p}} - 1 = {\ frac {(1-p_ {1}) (1-p_ {2}) \ prikker (1-p_ {n})} {p_ { 1} p_ {2} \ prikker p_ {n}}}}

Tar logaritmen til begge sider av likestillingen:

ln⁡(1s-1)=∑Jeg=1IKKE[ln⁡(1-sJeg)-ln⁡sJeg]{\ displaystyle \ ln \ left ({\ frac {1} {p}} - 1 \ right) = \ sum _ {i = 1} ^ {N} \ left [\ ln (1-p_ {i}) - \ ln p_ {i} \ høyre]}

La oss stille . Så, η=∑Jeg=1IKKE[ln⁡(1-sJeg)-ln⁡sJeg]{\ displaystyle \ eta = \ sum _ {i = 1} ^ {N} \ left [\ ln (1-p_ {i}) - \ ln p_ {i} \ right]}

1s-1=eη{\ displaystyle {\ frac {1} {p}} - 1 = e ^ {\ eta}}

Dette gir det alternative uttrykket for formelen for beregning av den kombinerte sannsynligheten:

s=11+eη{\ displaystyle p = {\ frac {1} {1 + e ^ {\ eta}}}}

Takle sjeldne ord

I tilfelle hvor ordet "  Replika  " aldri har blitt oppstått i løpet av læringsfasen, er telleren og nevneren begge null, begge i den generelle formelen for beregning av sannsynligheten og en melding som inneholder dette ordet er bare spam i formelen for beregning spamiteten til det ordet. E-postfiltreringsprogramvare kan bestemme seg for å avvise slike ord som ingen informasjon er tilgjengelig for.

Mer generelt er ord som bare har vært oppstått et lite antall ganger i løpet av læringsfasen problematiske, fordi det vil være en feil å blindt stole på informasjonen de gir. En enkel løsning er å legge disse ordene til side også.

Ved å bruke Bayes teorem igjen, og forutsatt at rangeringen mellom spam og legitim e-post er en tilfeldig variabel som overholder beta-loven , bestemmer annen programvare seg for å bruke en korrigert sannsynlighet:

P′(S|M)=s⋅P(S)+ikke⋅P(S|M)s+ikke{\ displaystyle P '(S | M) = {\ frac {s \ cdot P (S) + n \ cdot P (S | M)} {s + n}}}

eller:

• P′(S|M){\ displaystyle P '(S | M)} er den korrigerte sannsynligheten for at meldingen er spam, vel vitende om at den inneholder et gitt ord;
• s{\ displaystyle s}er styrken vi gir til informasjon om omgivelses spam;
• P(S){\ displaystyle P (S)} er sannsynligheten for at en innkommende melding er spam;
• ikke{\ displaystyle n} er antall forekomster av dette ordet i løpet av læringsfasen;
• P(S|M){\ displaystyle P (S | M)} er spamitet av ordet.

(Demonstrasjon: i artikkelen En statistisk tilnærming til spamproblemet )

Den korrigerte sannsynligheten brukes i stedet for spamitet i formelen som kombinerer sannsynlighetene for hvert ord.

P(S){\ displaystyle P (S)}kan igjen tas lik , for å unngå å få et for mistenkelig filter. er en god verdi for , noe som betyr at det trengs mer enn tre meldinger for å være mer trygge på spamverdien enn i den aktuelle spaminformasjonen. 0,5{\ displaystyle 0.5}3{\ displaystyle 3}s{\ displaystyle s}

Denne formelen kan utvides til det tilfellet der det er null (og spamitet er ikke definert), og gir i dette tilfellet . ikke{\ displaystyle n}P(S){\ displaystyle P (S)}

Annen heuristikk

Nøytrale ord som "le", "la", "un" (på fransk) eller deres ekvivalenter på andre språk blir vanligvis ignorert.

Mer generelt ignorerer de fleste Bayesian-programvarene ganske enkelt ethvert ord hvis spamitet er nær 0,5, fordi det ikke bidrar til en god beslutning. Ordene som tas i betraktning er de hvis spamitet er nær 0,0 (karakteristiske tegn på legitime meldinger) eller nær 1.0 (karakteristiske tegn på ulovlige meldinger). En metode kan være å holde bare de ti ordene som den absolutte verdien er størst for. |0,5-sJeg|{\ displaystyle | 0,5-pI |}

Noen programvare tar hensyn til det faktum at et gitt ord vises mer enn en gang i den undersøkte meldingen, andre gjør det ikke.

Noen programvare bruker mønstre (grupper av ord) i stedet for enkeltord på naturlig språk. For eksempel, for en pop- up på fire ord, beregner de spamisiteten til "Viagra er bra for", i stedet for å beregne spamiciteten til "Viagra", "er", "god" og "for". Denne metoden gir mer kontekstfølsomhet og eliminerer Bayesian støy bedre , men krever en større database.

Blandede metoder

Det er andre måter å kombinere individuelle sannsynligheter for forskjellige ord enn den "naive" tilnærmingen. Disse metodene skiller seg fra den naive metoden på forutsetningene som blir gjort om inngangsdataene. Disse forskjellige antagelsene resulterer i radikalt forskjellige formler for å kombinere de individuelle sannsynlighetene.

Hvis vi for eksempel antar at de enkelte sannsynlighetene følger en lov på with² med frihetsgrader, kan vi bruke formelen: 2⋅IKKE{\ displaystyle 2 \ cdot N}

s=VS-1(-2ln⁡(s1s2⋯sIKKE),2IKKE){\ displaystyle p = C ^ {- 1} (- 2 \ ln (p_ {1} p_ {2} \ cdots p_ {N}), 2N)}

hvor er det omvendte av funksjonen χ². VS-1{\ displaystyle C ^ {- 1}}

Individuelle sannsynligheter kan også kombineres med Markovian-diskrimineringsteknikker .

Diskusjon

fordeler

En av de viktigste fordelene med Bayesian-filteret er at det tilpasser seg brukeren.

Spammen som en bruker mottar, er ofte relatert til deres aktivitet på Internett. For eksempel, mens han surfer på nettet, kan han utilsiktet ha blitt plassert på en adresseliste (presentert som et "forretningsbrev") som han vil vurdere som spam. Mesteparten av tiden inneholder alle meldinger som sendes til denne listen vanlige ord, for eksempel navnet på listen og avsenderens e-postadresse. Bayesian-filteret vil oppdage disse fellestrekkene og gi dem stor sannsynlighet.

På samme måte har legitim e-post mottatt av flere brukere en tendens til å være annerledes. For eksempel, i et profesjonelt miljø, vil ofte navnet på selskapet hvor man jobber samt navnene på kunder og leverandører bli nevnt. Filteret vil tildele lav sannsynlighet for e-poster som inneholder disse navnene.

Sannsynlighetene kan endres over tid, gjennom kontinuerlig læring, når filteret feilklassifiserer en melding. Som et resultat er et Bayesian-filter ofte mer presist enn forhåndsdefinerte regler.

Bayesiske filtre er spesielt flinke til å unngå falske positive, det vil si å klassifisere legitime meldinger som spam. For eksempel, hvis e-postmeldingen inneholder ordet "Nigeria", som ofte vises i nigeriansk svindel- spam , vil et forhåndsdefinert regelsett automatisk avvise det. Et Bayesian-filter vil markere ordet "Nigeria" som et kjennetegn på spam, men vil også ta hensyn til andre viktige ord, som ektefellens navn eller vennenavn, som vanligvis er tegn på legitim e-post og vil ha forrang. ordet “Nigeria”.

Ulemper

Bayesisk forgiftning er en teknikk som brukes av spammere for å forsøke å redusere effektiviteten til Bayesiske spamfiltre. Den består i å plassere en stor mengde uskadelig tekst (fra for eksempel nyhetssider eller litteratur) eller tekstsalat (tilfeldige ordsekvenser som virker sammenhengende men ikke betyr noe), for å drukne ut uønsket tekst og lure filteret.

Spammere kan også transformere ord som vanligvis bare vises i spam. Dermed vil "Viagra" bli transformert for eksempel til "Viaagra" eller "V! Agra". Lesing er fremdeles mulig av mottakeren, men hvert av disse transformerte ordene vil bare forekomme sjeldnere, noe som straffer læring av det Bayesiske filteret. I praksis fungerer denne teknikken ganske dårlig, fordi de avledede ordene i seg selv blir gjenkjent av filteret.

En annen teknikk som brukes av spammere for å prøve å lure det Bayesiske filteret, er å erstatte tekst med bilder. Hele teksten, eller deler av den, erstattes av et bilde der den samme teksten er "tegnet". Spamfilteret klarer vanligvis ikke å analysere dette bildet som inneholder sensitive ord som "Viagra". Imidlertid slår mange brukere av visningen av bilder av sikkerhetsgrunner, noe som fører til at spammere når målene mindre. I tillegg er størrelsen på et bilde større enn den tilsvarende teksten, og spammere trenger mer båndbredde for å sende meldinger som inneholder bilder. Noen filtre har en tendens til å bestemme at en melding er spam når den har for mye grafisk innhold. Til slutt har Google foreslått en løsning som sannsynligvis er mer effektiv, og den brukes av Gmail- e-postsystemet  : behandle ethvert medium eller stort bilde ved optisk tegngjenkjenning for å analysere teksten den inneholder.

Merknader og referanser

1. (i) Jason Rennie, "  ifile  " [tekst]1996(åpnet 23. april 2020 )
2. (i) Jason DM Rennie, "  ifile: An Application of Machine Learning to E-Mail Filtering  " [PDF] , Boston, MA USA, KDD-2000 Text Mining Workshop2000(åpnet 23. april 2020 )
3. (in) Mr. Sahami, S. Dumais, D. Heckerman, E. Horvitz, A Bayesian Approach to Filtering Junk E-Mail , AAAI'98 Workshop on Learning for Text Categorization ,1998.
4. (en) Paul Graham , "  A Plan for Spam  " [html] ,2002(åpnet 23. april 2020 ) .
5. (i) Dylan Mors og Dermot Harnett, "  State of Spam, en månedlig utsettelse, utsettelse # 33  " (per 23. mars 2019 på Internett-arkivet ) .
6. (no) Gary Robinson, “  En statistisk tilnærming til spam-problemet  ” , Linux Journal ,1 st mars 2003( les online , konsultert 23. april 2020 ).
7. (in) Trevor Stone, "  Parametrization of Naïve Bayes for Spam Filtering  ", høsten 2003
8. (no) Prosessprogramvare, introduksjon til Bayesian Filtering
9. (i) "  Kombinere sannsynligheter  " på nettstedet MathPages.
10. (i) Brian Burton, "  SpamProbe - Bayesian Spam Filtering Tweaks  " ,2003.
11. (in) Jonathan A. Zdziarski, "  Bayesian Noise Reduction: Contextual Logic Symmetry Utilizing Consistency Pattern Analysis  " ( Arkiv • Wikiwix • Archive.is • Google • Hva skal jeg gjøre? ) ,2004.
12. (in) "  Gmail bruker Googles innovative teknologi for å holde spam utenfor innboksen din  »

Se også

Relaterte artikler

• Bayesian slutning
• Samarbeidsfiltrering
• Anti spam

Eksterne linker

• (i) filtrerer Bayesiansk spam Guide: 1 st  del , to av delen .
• (no) Detaljert forklaring av Paul Graham-formler av Tim Peters
• (in) Gary Robinsons blogg om spam
• Matematisk grunnlag for læring Statistikk

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">