přejít na obsah přejít na navigaci

Linux E X P R E S, Bayesův filtr

Bayesův filtr

Lukáš Zapletal - krátký úvod do toho, jak funguje Bayesův filtr.


reklama

Jistě jste o něm slyšeli. Filtr, který dokáže eliminovat většinu reklamních e-mailů – takzvaný spam. Princip funkce je jednoduchý – uživatel algoritmu předá několik vzorových zpráv, které jsou spamem, a které nejsou (těm se říká ham). Ten si na základě jistých statistických metod všechno "zapamatuje", a poté je schopen určit, co je spam, a co není.

Tohle byl popis z hlediska uživatele, ale co se skrývá pod pokličkou? Jak je Bayesův filtr účinný? Ačkoliv problematika spadá do oblasti informatiky s názvem strojové učení (machine learning), metoda je překvapivě jednoduchá. Je založena na tvrzení nazývaném O pravděpodobnosti příčin, jež poprvé vyslovil a dokázal matematik Thomas Bayes, a které se v jednoduché formě učí na středních školách v kapitole o pravděpodobnosti.

Tvrzení mohu vysvětlit matematicky, nebo prakticky. Zvolím druhou variantu, jeden příklad je lepší než tisíc vzorců. Dovolím si použít příklad od Paula Grahama (paulgraham.com/naivebayes.html). Předpokládejme, že člověk měřící více než 190 centimetrů je z 60% basketbalista a dále člověk, který má v ruce basketbalový míč, že je z 72% basketbalista. Nyní se zamysleme, jaká je pravděpodobnost, že člověk měřící nad 190 centimetrů s basketbalovým míčem v ruce je basketbalista.

Bayes zjistil, že pokud máme dva neslučitelné jevy, jejichž průnikem je jev jistý (tzv. úplný systém jevů), pak se pravděpodobnost po provedení pokusu, při kterém nastaly oba jevy, dá snadno vypočítat. V našem jednoduchém případě o dvou jevech by to podle Bayesova vzorce bylo (0,6 * 0,72) / [(0,6 * 0,72) + (1 - 0,6) * (1 - 0,72)]. Výsledkem je 0,794, což mi trošku připomnělo základní školu a paní učitelku, která mě nabádala odpovídat celou větou: Pravděpodobnost, že vysoký člověk s míčem je basketbalistou, je 79,4%. Podobný vzorec platí nejen pro dvojici, ale také obecně pro n jevů (k pochopení obecného vzorce je nutná základní znalost teorie pravděpodobnosti, dobrou stránkou je například en.wikipedia.org/wiki/Bayes'_theorem).

Bayesovo filtrování funguje právě na uvedeném principu, přičemž se předpokládá, že jevy jsou nezávislé, což v praxi není pravda. I přesto metoda (někdy označovaná jako "naivní") podává výborné výsledky. Mějme množinu textů (e-mailů), které jsou spamem, a množinu textů, již spamem nejsou (ham). Je nutno si uvědomit, že příliš nezáleží na počtu těchto textů jako spíše na jejich "kvalitě" – měly by pokrývat svým obsahem širokou škálu e-mailů obsahově reklamních, respektive "čistých". Nejdříve první i druhou množinu profiltrujeme a rozdělíme ji na slova. Dnešní filtry umějí odhalit slova z hlavičky e-mailu nebo HTML, nám postačí obyčejné rozdělení na slova, přičemž je vhodné zachovat velikost písmen (nekonvertovat vše na malá). Nyní se spočtou výskyty slov, což je jednoduchá operace, kterou počítač pomocí hashovacích tabulek zvládne velmi rychle. Tuto strukturu je možné velmi snadno a efektivně ukládat i aktualizovat.

Přichází nejtěžší část – je nutno z obou tabulek (slovo-počet výskytů) sestavit tabulku jednu (slovo-pravděpodobnost), ve které bude uvedeno, s jakou pravděpodobností se dané slovo vyskytuje ve spamu resp. hamu. Číslo 0,5 bude reprezentovat stejný počet ham-slov i spam-slov v obou množinách, číslo 0,01 bude znamenat, že se slovo vyskytuje pouze jako ham a 0,99 pouze jako spam. Není však dobré tuto tabulku vytvořit pouhým sloučením obou počtů, pokusy ukazují, že je dobré počty ham-slov násobit dvěma – filtr je pak přesnější. Každá implementace to má jinak, právě na tomto místě je prostor pro další bádání a testy.

Jestliže vytvoření bayesovských tabulek slov bylo rychlé, klasifikace příchozího e-mailu (jestli je, nebo není spam) je ještě rychlejší. Text se rozdělí na slova a v tabulkách se vyhledají pravděpodobnosti všech těchto slov. Vybere se rozumný počet (zdroje uvádějí například patnáct) slov, která mají pravděpodobnost nejdále od středu, tj. 0,5. Na tyto pravděpodobnosti se použije Bayesovo pravidlo a výsledkem je pravděpodobnost, že je daný e-mail spam.

Malý příklad vybereme z reklamního mailu tato (pro didaktické účely pouze tři) "nejzajímavější" slova: sex (91%), viagra (99%) a Perl (0,09%). Jak je vidět, slovo "sex" se vyskytovalo ve spamu často, "viagra" se nikdy v hamu nevyskytovala (výchozí hodnota 0,99) a slovo "Perl" se ve spamu zřejmě párkrát již vyskytlo (spammeři se snaží na konec reklamních mailů zařazovat slova netýkající se tématu). Pravděpodobnost, že daný e-mail je spam je (0.91 * 0.99 * 0.09) / ((0.91 * 0.99 * 0.09) + (1 - 0.91) * (1 - 0.99) * (1 - 0.09)) = 0,99. Takový e-mail je z 99% spam.

A jak je bayesovský filtr účinný? To je těžká otázka, záleží na tom, jak si ho "vychová" sám uživatel. Pokud mu dodá nevhodné vzorky, nemusí být účinný vůbec, ale jestliže někdo pečlivě označuje reklamní zprávy, pak se účinnost blíží ke 100%. Záleží na implementaci – dnešní filtry se umějí vypořádat s různými technikami, kterými se snaží spammeři tuto metodu oblafnout. Například SpamAssassin přidává různé heuristické testy a takzvané bonusy, které při správném nastavení ve výsledku fungují téměř s jistotou.

Bayesova metoda nachází uplatnění nejen při boji se spamem, ale v libovolné kategorizaci textů (dokumentů). Následující odstaveček bude takovým nahlédnutím do oblasti dolování dat (data mining). Představte si, že máte obrovský počet dokumentů o Linuxu (které jste například stáhli pomocí Google vyhledávače), ale zajímají vás jen některé články (například kde se srovnává výkon Linuxu a operačního systému Solaris). Bayesovu kategorizaci využijete tak, že přečtete například sto článků a u každého stanovíte, zda je to pro vás článek zajímavý nebo nezajímavý. Na zbytek textů použijete Bayesův algoritmus a jestliže vyberete pro obě třídy vhodné vzory, algoritmus velmi rychle dokumenty rozdělí do dvou tříd. V jedné najdete pro vás zajímavé dokumenty (kde se budou vyskytovat podobná slova), v té druhé pak zbytek.

Nahoru

(Jako ve škole)
Průměr: 1,30 | Hodnotilo: 10
 

Top články z OpenOffice.cz

Příspěvky

Chyba v clanku
Anonymous 22. 03. 2008, 20:08:55
Odpovědět  Odkaz 
Chyba:
"Bayes zjistil, že pokud máme dva neslučitelné jevy, jejichž průnikem je jev jistý (tzv. úplný systém jevů)," tohle je nesmysl viz definice neslucitelneho jevu. Pokud jsou dva jevy neslucitelne znamena to ze jejich prunikem je prazdna mnozina. Takze by tam melo zrejme byt sjednoceni jevu...
Bayesův filtr
pepe 7. 04. 2008, 23:40:00
Odpovědět  Odkaz 
Zajímalo by mne jak se to řeší když mi prijde email(který bude SPAM) a bude se v něm vyskytovat jedno slovo, ktere se vyskytuje pouze v hamech (tudíž má pravděpodobnost spamu 0%) tak bude v tom zlomku v čitateli 0 a tudíž bude 0% pravděpodobnost spamu....?
Re:Bayesův filtr
Marek 10. 04. 2008, 14:12:32
Odpovědět  Odkaz 
No vzasade se to da resit velice jednoduse takovemu slovu dmae pravdepodobmnost 0.00000000001 cimz nam celkove ohodnoceni emailu zvysuje velice nepatrne.

Přidat názor

Nejsou podporovány žádné značky, komentáře jsou jen čistě textové. Více o diskuzích a pravidlech najdete v nápovědě.
Diskuzi můžete sledovat pomocí RSS kanálu rss



 
 

Lukáš Zapletal

Lukáš Zapletal

Senior Software Engineer @ Red Hat


  • Distribuce: Fedora
  • Hodnocení autora: ***

| blog



Public Relations

QNAP uvedl novou modelovou řadu NAS TVS-x82T

Společnost QNAP uvedla na trh novou modelovou řadu NAS TVS-x82T, kterou tvoří tři různé modely (TVS-1282T, TVS-882T a TVS-682T). Nová řada je založena na vícejádrových procesorech Intel Core aktuální generace se 14nm výrobním procesem. Díky nim mohou nové NASy nabídnout dostatek výkonu i pro aplikace náročné na CPU.

Pokračování ...


CIO Agenda 2016

Tagy