Naiwne filtrowanie spamu metodą Bayesa

Naiwne klasyfikatory Bayesa są popularną techniką statystyczną filtrowania wiadomości e-mail . Zazwyczaj używają worka słów do identyfikowania spamu w wiadomościach e-mail , co jest często stosowane w klasyfikacji tekstu .

Naiwne klasyfikatory Bayesa działają na zasadzie korelacji użycia tokenów (zwykle słów lub czasami innych rzeczy) ze spamem i niespamowymi wiadomościami e-mail, a następnie wykorzystują twierdzenie Bayesa do obliczenia prawdopodobieństwa, że ​​wiadomość e-mail jest lub nie jest spamem.

Naiwne filtrowanie spamu metodą Bayesa to podstawowa technika radzenia sobie ze spamem, która może być dostosowana do potrzeb e-mailowych poszczególnych użytkowników i zapewnia niski wskaźnik fałszywych trafień wykrywanych spamu, który jest ogólnie akceptowalny dla użytkowników. Jest to jeden z najstarszych sposobów filtrowania spamu, którego korzenie sięgają lat 90.

Historia

Algorytmy bayesowskie były używane do filtrowania wiadomości e-mail już w 1996 roku. Chociaż naiwne filtry bayesowskie stały się popularne dopiero później, w 1998 roku wydano wiele programów mających na celu rozwiązanie rosnącego problemu niechcianych wiadomości e-mail. Pierwsza publikacja naukowa na temat Bayesowskiego filtrowania spamu została napisana przez Sahami i in. w 1998 r. Wkrótce potem ta praca została wdrożona w komercyjnych filtrach spamu.

Warianty podstawowej techniki zostały zaimplementowane w wielu pracach badawczych i komercyjnych produktach programistycznych . Wiele nowoczesnych klientów pocztowych stosuje Bayesowskie filtrowanie spamu. Użytkownicy mogą również zainstalować oddzielne programy do filtrowania wiadomości e-mail . Filtry poczty e -mail po stronie serwera , takie jak DSPAM, SpamAssassin , SpamBayes , Bogofilter i ASSP , wykorzystują Bayesowskie techniki filtrowania spamu, a funkcjonalność ta jest czasami osadzona w samym oprogramowaniu serwera poczty . CRM114 , często cytowany jako filtr Bayesa, nie jest przeznaczony do używania filtra Bayesa w produkcji, ale zawiera funkcję ″unigram″ w celach informacyjnych.

Proces

Poszczególne słowa mają określone prawdopodobieństwo wystąpienia w wiadomościach spamowych i w legalnych wiadomościach e-mail. Na przykład większość użytkowników poczty e-mail często napotyka słowo „ Viagra ” w spamie, ale rzadko widzi je w innych wiadomościach e-mail. Filtr nie zna tych prawdopodobieństw z góry i musi najpierw zostać przeszkolony, aby mógł je budować. Aby wyszkolić filtr, użytkownik musi ręcznie wskazać, czy nowa wiadomość e-mail jest spamem, czy nie. Dla wszystkich słów w każdym e-mailu szkoleniowym filtr dostosuje prawdopodobieństwo, że każde słowo pojawi się w spamie lub legalnej wiadomości e-mail w swojej bazie danych. Na przykład filtry antyspamowe Bayesa zazwyczaj uczą się bardzo wysokiego prawdopodobieństwa spamu dla słów „Viagra” i „refinansowanie”, ale bardzo niskiego prawdopodobieństwa spamu dla słów widocznych tylko w legalnych wiadomościach e-mail, takich jak imiona przyjaciół i członków rodziny.

Po szkoleniu prawdopodobieństwa słów (znane również jako funkcje wiarygodności ) są używane do obliczenia prawdopodobieństwa, że ​​wiadomość e-mail zawierająca określony zestaw słów należy do którejkolwiek z kategorii. Każde słowo w wiadomości e-mail przyczynia się do prawdopodobieństwa spamu wiadomości e-mail lub tylko najciekawszych słów. Udział ten nazywany jest prawdopodobieństwem a posteriori i jest obliczany przy użyciu twierdzenia Bayesa . Następnie prawdopodobieństwo spamu e-maila jest obliczane dla wszystkich słów w e-mailu, a jeśli suma przekroczy określony próg (powiedzmy 95%), filtr oznaczy e-mail jako spam.

Podobnie jak w przypadku każdej innej techniki filtrowania spamu , wiadomości e-mail oznaczone jako spam mogą zostać automatycznie przeniesione do folderu „śmieci”, a nawet całkowicie usunięte. Niektóre programy implementują kwarantanny , które definiują ramy czasowe, w których użytkownik może przejrzeć decyzję oprogramowania.

Wstępne szkolenie można zwykle udoskonalić, gdy zostaną zidentyfikowane błędne oceny oprogramowania (fałszywie pozytywne lub fałszywie negatywne). Pozwala to oprogramowaniu na dynamiczne dostosowywanie się do stale ewoluującego charakteru spamu.

Niektóre filtry antyspamowe łączą wyniki Bayesowskiego filtrowania spamu i innych heurystyk (wstępnie zdefiniowane reguły dotyczące zawartości, sprawdzanie koperty wiadomości itp.), co skutkuje jeszcze wyższą dokładnością filtrowania, czasem kosztem adaptacyjności.

Podstawa matematyczna

Bayesowskie filtry poczty e-mail wykorzystują twierdzenie Bayesa . Twierdzenie Bayesa jest używane kilka razy w kontekście spamu:

• po raz pierwszy obliczyć prawdopodobieństwo, że wiadomość jest spamem, wiedząc, że dane słowo występuje w tej wiadomości;
• po raz drugi, aby obliczyć prawdopodobieństwo, że wiadomość jest spamem, biorąc pod uwagę wszystkie jej słowa (lub odpowiedni ich podzbiór);
• czasami po raz trzeci, aby poradzić sobie z rzadkimi słowami.

Obliczanie prawdopodobieństwa, że ​​wiadomość zawierająca dane słowo jest spamem

Załóżmy, że podejrzana wiadomość zawiera słowo „ replika ”. Większość osób przyzwyczajonych do otrzymywania wiadomości e-mail wie, że ta wiadomość może być spamem, a dokładniej propozycją sprzedaży podrobionych kopii znanych marek zegarków. Oprogramowanie do wykrywania spamu jednak nie „zna” takich faktów; wszystko, co może zrobić, to obliczyć prawdopodobieństwa.

Formuła używana przez oprogramowanie do określenia tego pochodzi z twierdzenia Bayesa

${\ Displaystyle \ Pr (S | W )={\frac {\Pr(W|S)\cdot \Pr(S)}{\Pr(W|S)\cdot \Pr(S)+\Pr(W|H)\cdot \Pr(H )}}}$

Gdzie:

• ${\ Displaystyle \ Pr (S | W)}$ to prawdopodobieństwo, że wiadomość jest spamem, wiedząc, że jest w niej słowo „replika”;
• ${\ Displaystyle \ Pr (S)}$ to ogólne prawdopodobieństwo, że dana wiadomość to spam;
• ${\ Displaystyle \ Pr (W | S)}$ to prawdopodobieństwo, że słowo „replika” pojawi się w wiadomościach spamowych;
• ${\ Displaystyle \ Pr (H)}$ to ogólne prawdopodobieństwo, że dana wiadomość nie jest spamem (jest „szynką”);
• ${\ Displaystyle \ Pr (W | H)}$ to prawdopodobieństwo, że słowo „replika” pojawi się w wiadomościach krótkofalarskich.

(Aby uzyskać pełną demonstrację, zobacz Twierdzenie Bayesa # Forma rozszerzona .)

Spamowość słowa

Statystyki pokazują, że obecnie prawdopodobieństwo, że jakakolwiek wiadomość jest spamem, wynosi co najmniej 80%:

${\ Displaystyle \ Pr (S) = 0,8; \ Pr (H) = 0,2}$

Jednak większość oprogramowania Bayesa do wykrywania spamu przyjmuje założenie, że nie ma a priori powodu, dla którego jakakolwiek wiadomość przychodząca jest spamem, a nie szynką, i uważa, że ​​oba przypadki mają równe prawdopodobieństwo 50%:

${\ Displaystyle \ Pr (S) = 0,5; \ Pr (H) = 0,5}$

Mówi się, że filtry, które wykorzystują tę hipotezę, są „niestronne”, co oznacza, że ​​nie mają żadnych uprzedzeń w odniesieniu do przychodzącej wiadomości e-mail. Założenie to pozwala uprościć wzór ogólny do:

${\ Displaystyle \ Pr (S | W) = {\ Frac {\ Pr (W | S)}} \Pr(W|S)+\Pr(W|H)}}}$

Jest to funkcjonalnie równoważne z pytaniem „jaki procent wystąpień słowa„ replika ”występuje w wiadomościach spamowych?”

Ta wielkość jest nazywana „spamowością” (lub „spamowością”) słowa „replika” i można ją obliczyć. Liczba $uczenia$ wiadomości zawierających „replikę” w wiadomościach zidentyfikowanych jako spam podczas fazy Podobnie ${\ Displaystyle \ Pr (W | H)}$ jest przybliżona do częstotliwości komunikatów zawierających „replikę” w komunikatach zidentyfikowanych jako ham w fazie uczenia się. Aby te przybliżenia miały sens, zbiór wyuczonych komunikatów musi być wystarczająco duży i reprezentatywny. Wskazane jest również, aby wyuczony zestaw wiadomości był zgodny z hipotezą 50% dotyczącą ponownego podziału między spam i ham, tj. że zestawy danych spamu i ham są tej samej wielkości.

Oczywiście ustalenie, czy wiadomość jest spamem, czy hamem, na podstawie obecności słowa „replika” jest podatne na błędy, dlatego też Bayesowskie oprogramowanie spamujące próbuje rozważyć kilka słów i połączyć ich spamowość, aby określić ogólne prawdopodobieństwo, że wiadomość zostanie spam.

Łączenie indywidualnych prawdopodobieństw

Większość bayesowskich algorytmów filtrowania spamu opiera się na formułach, które są ściśle poprawne (z probabilistycznego punktu widzenia) tylko wtedy, gdy słowa obecne w wiadomości są zdarzeniami niezależnymi . Warunek ten na ogół nie jest spełniony (na przykład w językach naturalnych, takich jak angielski, prawdopodobieństwo znalezienia przymiotnika zależy od prawdopodobieństwa posiadania rzeczownika), ale jest to użyteczna idealizacja, zwłaszcza że statystyczne korelacje między poszczególnymi wyrazami zwykle nie są znany. Na tej podstawie z twierdzenia Bayesa można wyprowadzić następujący wzór:

${\ 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 })}}}$

Gdzie:

• ${\ displaystyle p}$ to prawdopodobieństwo, że podejrzana wiadomość to spam;
• ${\ Displaystyle p_ {1}}$ to prawdopodobieństwo , że pojawia się pierwsze słowo (na przykład „replika”), ${\ Displaystyle p (W_ {1} | S)} , biorąc pod uwagę, że wiadomość$ jest spamem;
• ${\ Displaystyle p_ {2}}$ to prawdopodobieństwo , że pojawi się drugie słowo (na przykład „zegarki”), biorąc pod uwagę, że wiadomość ${\ Displaystyle p (W_ {2} | S)}$ jest spamem;
• itp...

Oprogramowanie do filtrowania spamu oparte na tej formule jest czasami określane jako naiwny klasyfikator Bayesa , ponieważ „naiwny” odnosi się do silnych założeń niezależności między funkcjami. Wynik p jest zwykle porównywany z zadanym progiem, aby zdecydować, czy wiadomość jest spamem, czy nie. Jeśli p jest niższe niż próg, wiadomość jest traktowana jako prawdopodobny ham, w przeciwnym razie jest uważana za prawdopodobny spam.

Inne wyrażenie formuły łączenia poszczególnych prawdopodobieństw

Zwykle p nie jest obliczane bezpośrednio przy użyciu powyższego wzoru z powodu niedomiaru zmiennoprzecinkowego . Zamiast tego p można obliczyć w domenie logarytmicznej, przepisując oryginalne równanie w następujący sposób:

${\ Displaystyle {\ Frac {1} {p}} -1 = {\ Frac {(1-p_{1})(1-p_{2})\kropki (1-p_{N})}{p_{1}p_{2}\kropki p_{N}}}}$

Pobieranie kłód z obu stron:

${\ Displaystyle \ ln \ lewo ({\ Frac {1} {p}} -1 \ prawo)=\suma _{i=1}^{N}\lewo[\ln(1-p_{i})-\ln p_{i}\prawo]}$

Niech ${\ Displaystyle \ eta = \ suma _ {i = 1} ^ {N} \ lewo [\ ln (1-p_ {i})-\ln p_{i}\right]}$ . Dlatego,

${\ Displaystyle {\ Frac {1} {p}} -1 = e ^ {\ eta}}$

Stąd alternatywna formuła obliczania połączonego prawdopodobieństwa:

${\ Displaystyle p = {\ Frac {1} {1 + e ^ {\ eta}}}}$

Radzenie sobie z rzadkimi słowami

W przypadku, gdy w fazie uczenia się nigdy nie spotkano słowa, zarówno licznik, jak i mianownik są równe zeru, zarówno we wzorze ogólnym, jak i we wzorze spamiczności. Oprogramowanie może zdecydować o odrzuceniu takich słów, dla których nie ma dostępnych informacji.

Mówiąc bardziej ogólnie, słowa, które napotkano tylko kilka razy podczas fazy uczenia się, powodują problem, ponieważ błędem byłoby ślepe zaufanie do informacji, które dostarczają. Prostym rozwiązaniem jest po prostu unikanie brania pod uwagę również takich niewiarygodnych słów.

Stosując ponownie twierdzenie Bayesa i przyjmując, że klasyfikacja między spamem a hamem wiadomości e-mail zawierających dane słowo („replika”) jest zmienną losową o rozkładzie beta , niektóre programy decydują się na użycie skorygowanego prawdopodobieństwa:

${\ Displaystyle \ Pr '(S | W) = {\ Frac {s \ cdot \ Pr (S) +n\cdot \Pr(S|W)}{s+n}}}$

Gdzie:

• ${\ Displaystyle \ Pr '(S | W)}$ to skorygowane prawdopodobieństwo, że wiadomość jest spamem, wiedząc, że zawiera dane słowo;
• ${\ displaystyle s}$ to siła, jaką dajemy podstawowym informacjom o przychodzącym spamie;
• ${\ displaystyle \ Pr (S)}$ to prawdopodobieństwo, że jakakolwiek wiadomość przychodząca będzie spamem;
• ${\ displaystyle n}$ to liczba wystąpień tego słowa podczas fazy uczenia się;
• ${\ Displaystyle \ Pr (S | W)}$ to spamowość tego słowa.

(Demonstracja:)

To skorygowane prawdopodobieństwo jest używane zamiast spamiczności we wzorze łączącym.

${\ displaystyle \ Pr (S)}$ można ponownie przyjąć jako równe 0,5, aby uniknąć zbytniej podejrzliwości w stosunku do przychodzących wiadomości e-mail. 3 jest dobrą wartością dla s , co oznacza , że wyuczony korpus musi zawierać więcej niż 3 komunikaty z tym słowem , aby wartość spamiczności była bardziej wiarygodna niż wartość domyślna .

Formułę tę można rozszerzyć na przypadek, w którym n jest równe zeru (i gdzie spamiczność nie jest zdefiniowana) i ocenia w tym przypadku na ${\ Displaystyle Pr (S)}$ .

Inne heurystyki

„Neutralne” słowa, takie jak „the”, „a”, „some” lub „is” (w języku angielskim) lub ich odpowiedniki w innych językach, można zignorować. Są one również znane jako słowa Stop . Mówiąc bardziej ogólnie, niektóre filtry bayesowskie po prostu ignorują wszystkie słowa, które mają spamiczność bliską 0,5, ponieważ niewiele przyczyniają się do dobrej decyzji. Pod uwagę brane są słowa, których spamowość jest bliska 0,0 (charakterystyczne oznaki prawidłowych wiadomości) lub bliskie 1,0 (charakterystyczne oznaki spamu). Metodą może być np. zachowanie w badanej wiadomości tylko tych dziesięciu słów, które mają największą wartość bezwzględną |0,5 − pi |.

Niektóre programy uwzględniają fakt, że dane słowo pojawia się kilka razy w badanej wiadomości, inne nie.

Niektóre produkty oprogramowania używają wzorców (sekwencji słów) zamiast pojedynczych słów języka naturalnego. Na przykład, mając „okno kontekstowe” składające się z czterech słów, obliczają spamowość „Viagra jest dobra dla”, zamiast obliczać spamowość „Viagra”, „jest”, „dobra” i „dla”. Ta metoda daje większą wrażliwość na kontekst i lepiej eliminuje szum bayesowski kosztem większej bazy danych.

Metody mieszane

Istnieją inne sposoby łączenia poszczególnych prawdopodobieństw dla różnych słów niż podejście „naiwne”. Metody te różnią się od niej założeniami dotyczącymi właściwości statystycznych danych wejściowych. Te różne hipotezy skutkują radykalnie różnymi wzorami łączenia poszczególnych prawdopodobieństw.

Na przykład, zakładając, że poszczególne prawdopodobieństwa są zgodne z rozkładem chi-kwadrat z 2 N stopniami swobody, można użyć wzoru:

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

gdzie C ⁻¹ jest odwrotnością funkcji chi-kwadrat .

Indywidualne prawdopodobieństwa można również łączyć z technikami dyskryminacji Markowa .

Dyskusja

Zalety

Jedną z głównych zalet Bayesowskiego filtrowania spamu jest to, że można go trenować dla poszczególnych użytkowników.

Spam, który otrzymuje użytkownik, jest często związany z działaniami użytkownika online. Na przykład użytkownik mógł zasubskrybować biuletyn internetowy, który użytkownik uważa za spam. Ten biuletyn online może zawierać słowa, które są wspólne dla wszystkich biuletynów, takie jak nazwa biuletynu i adres e-mail, z którego pochodzi. Bayesowski filtr antyspamowy ostatecznie przypisze wyższe prawdopodobieństwo na podstawie określonych wzorców użytkownika.

Prawdziwe e-maile, które otrzymuje użytkownik, będą się różnić. Na przykład w środowisku korporacyjnym często wymienia się nazwę firmy i nazwiska klientów lub klientów. Filtr przypisze mniejsze prawdopodobieństwo spamu do wiadomości e-mail zawierających te nazwy.

Prawdopodobieństwa słów są unikalne dla każdego użytkownika i mogą ewoluować w miarę upływu czasu wraz ze szkoleniem korygującym, gdy filtr nieprawidłowo klasyfikuje wiadomość e-mail. W rezultacie dokładność filtrowania spamu Bayesa po szkoleniu często przewyższa predefiniowane reguły.

Szczególnie dobrze sprawdza się w unikaniu fałszywych alarmów , gdy legalna wiadomość e-mail jest nieprawidłowo klasyfikowana jako spam. Na przykład, jeśli wiadomość e-mail zawiera słowo „Nigeria”, które jest często używane w wyłudzającym opłaty zaliczkowe , wstępnie zdefiniowany filtr reguł może go odrzucić. Filtr Bayesa oznaczałby słowo „Nigeria” jako prawdopodobne słowo będące spamem, ale uwzględniałby inne ważne słowa, które zwykle wskazują na wiarygodną wiadomość e-mail. Na przykład imię współmałżonka może wyraźnie wskazywać, że wiadomość e-mail nie jest spamem, co mogłoby zniwelować użycie słowa „Nigeria”.

Niedogodności

W zależności od implementacji Bayesowskie filtrowanie spamu może być podatne na zatrucie Bayesowskie , technikę stosowaną przez spamerów w celu obniżenia skuteczności filtrów spamu, które opierają się na filtrowaniu Bayesowskim. Spamer stosujący zatrucie bayesowskie będzie wysyłał e-maile z dużą ilością wiarygodnego tekstu (zebranego z wiarygodnych wiadomości lub źródeł literackich). Spamer taktyki obejmują wstawianie losowych, nieszkodliwych słów, które zwykle nie są kojarzone ze spamem, zmniejszając w ten sposób ocenę spamu wiadomości e-mail, zwiększając prawdopodobieństwo prześlizgnięcia się przez filtr antyspamowy Bayesa. Jednak w (na przykład) schemacie Paula Grahama używane są tylko najbardziej znaczące prawdopodobieństwa, więc wypełnienie tekstu słowami niezwiązanymi ze spamem nie wpływa znacząco na prawdopodobieństwo wykrycia.

Słowa, które zwykle pojawiają się w dużych ilościach w spamie, mogą również zostać przekształcone przez spamerów. Na przykład słowo „Viagra” zostanie zastąpione słowem „Viaagra” lub „V!agra” w wiadomości będącej spamem. Odbiorca wiadomości nadal może odczytać zmienione słowa, ale każde z tych słów jest rzadziej spotykane przez filtr Bayesa, co utrudnia jego proces uczenia się. Zasadniczo ta technika spamowania nie działa zbyt dobrze, ponieważ słowa pochodne są rozpoznawane przez filtr tak samo, jak zwykłe.

Inną techniką używaną do próby pokonania Bayesowskich filtrów antyspamowych jest zastąpienie tekstu obrazami, dołączonymi bezpośrednio lub połączonymi linkami. Cały tekst wiadomości lub jego część jest zastępowana obrazkiem, na którym ten sam tekst jest „narysowany”. Filtr antyspamowy zwykle nie jest w stanie przeanalizować tego zdjęcia, które zawierałoby wrażliwe słowa, takie jak „Viagra”. Ponieważ jednak wielu klientów pocztowych wyłącza wyświetlanie połączonych obrazów ze względów bezpieczeństwa, spamer wysyłający łącza do odległych obrazów może dotrzeć do mniejszej liczby celów. Ponadto rozmiar obrazu w bajtach jest większy niż odpowiedni rozmiar tekstu, więc spamer potrzebuje większej przepustowości, aby wysyłać wiadomości zawierające bezpośrednio obrazy. Niektóre filtry są bardziej skłonne uznać wiadomość za spam, jeśli zawiera ona głównie treść graficzną. Rozwiązanie stosowane przez Google w swoim systemie pocztowym Gmail ma przeprowadzać OCR (Optical Character Recognition) na każdym obrazie średniej i dużej wielkości, analizując znajdujący się w nim tekst.

Ogólne zastosowania filtrowania bayesowskiego

Podczas gdy filtrowanie Bayesa jest szeroko stosowane do identyfikowania spamu, technika ta może klasyfikować (lub „grupować”) prawie każdy rodzaj danych. Ma zastosowanie w nauce, medycynie i inżynierii. Jednym z przykładów jest program do klasyfikacji ogólnego przeznaczenia o nazwie AutoClass , który pierwotnie był używany do klasyfikowania gwiazd według charakterystyk widmowych, które w przeciwnym razie byłyby zbyt subtelne, aby je zauważyć.

Zobacz też

• Techniki antyspamowe
• Zatrucie bayesowskie
• Filtrowanie wiadomości e-mail
• Dyskryminacja Markowa
• Mozilla Thunderbird z natywną implementacją filtrów Bayesa