Naive Bayes

5. Dezember 2014

Naive Bayes 5. Dezember 2014 1 / 18

Inhaltsverzeichnis

1 Thomas Bayes2 Anwendungsgebiete3 Der Satz von Bayes4 Ausfuhrliche Form5 Beispiel6 Naive Bayes Einfuhrung7 Naive Bayes Klassifikator8 Naive Bayes Formel9 Beispiel zum Naive Bayes Classifier

10 Naive Bayes Spam Filter11 Naive Bayes Spam Filter12 Naive Bayes Spam Filter

Naive Bayes 5. Dezember 2014 2 / 18

Zu Thomas Bayes

Thomas Bayes wurde 1701 in London geboren und starb 7.4.1761 inTunbridgeBayes war Pfarrer und MathematikerVerfasste den heute als Satz von Bayes bekannten Satz in ’An essaytowards solving a problem in the doctrines of chances’Ausserdem werden Bayes noch zwei weitere Werke zugeschrieben:Divine Benevolence & An Introduction to the Doctrine of Fluxions

Naive Bayes 5. Dezember 2014 3 / 18

Anwendungsgebiete

Laut WikipediaIn der StatstikData-MiningSpamfilterKIQualitatsmanagementEntscheidungstheorieuvm.

Naive Bayes 5. Dezember 2014 4 / 18

Der Satz von Bayes

SatzDer Satz von Bayes ist ein Satz der Wahrscheinlichkeitstheorie,er beschreibt die Berechnung bedinger Wahrscheinlichkeiten.Man bezeichnet ihn auch als Formel von Bayes, Bayes Theorem oderRuckwartsinduktion. Er stellt ausserdem die Grundlage fur den NaiveBayes Klassifikator dar.

Sinn

Wie kann man von P(B|A) auf P(A|B) schließen?

Naive Bayes 5. Dezember 2014 5 / 18

Der Satz von Bayes

Abstrakt

Posterior = (Outcome|Evidence) =Prior probability of outcome * Likelihood of evidence

P(Evidence)

Formel

P(A|B) =P(A) ∗ P(B|A)

P(B)

Naive Bayes 5. Dezember 2014 6 / 18

Formulierung

Allgemeine Formulierung fur Partitionen Ai uber den Ereignisraum

P(Ai |B) =P(Ai) ∗ P(B|Ai)∑n

j=1 P(B|Aj) ∗ P(Aj)

Fur binare A gilt:

P(A|B) =P(A) ∗ P(B|A)

P(B|A) ∗ P(A) + P(B|¬A) ∗ P(¬A)

Naive Bayes 5. Dezember 2014 7 / 18

Beispiel

Rahmenbedingungen

Medizinischer Test auf eine Krankheit:P(Positiv |Krank) = 0.997(Sensitivitat)

P(Negativ |Gesund) = 0.985(Spezifitat)P(Krank) = 0.001(Pr avalenz)→ P(Gesund) = 0.999

Gesucht : P(Krank|Positiv)

Zeit online: blog.zeit.de/mathe/allgemein/weltaidstag-aids-hiv-mathematik

Naive Bayes 5. Dezember 2014 8 / 18

Kurze Einfuhrung Naive Bayes

Naive Bayes Klassifikator nimmt an, dass die einzelnen Features imHinblick auf die Klassenvariable voneinander unabhangig sind.Bei Textverarbeitung ’Bag of Words’ Darstellung. → KeineReihenfolge o.a. sondern FrequenzWird teilweise wegen der Annahme von Unabhangigkeit auch ’IdiotBayes’ genannt.Trotz der stark vereinfachten Annahme sehr effizient & schnellBenotigt keine großen Trainingssets.(Relativ) einfach zu implementieren.Wenn Unabhangigkeit korrekt ware auch Genauigkeit perfekt

Naive Bayes 5. Dezember 2014 9 / 18

Naive Bayes Klassifikator

Abstrakt

Posterior = Prior probability of outcome * Likelihood of evidenceP(Evidence)

In der PraxisBesteht meist nur Interesse am Nenner der Gleichung, da der Teiler vonder Klasse unabhangig ist und man immer durch den gleichen Wert teilt

Naive Bayes 5. Dezember 2014 10 / 18

Naive Bayes Formel

Man betrachtet also:

Der Klassifikator fur diese Formel:

Quelle:http://en.wikipedia.org/wiki/Naive Bayes classifier

Naive Bayes 5. Dezember 2014 11 / 18

Ein Beispiel zum Naive Bayes Classifier

AufgabeWir sollen eine Frucht mit den Attributen ’Long,Yellow,Sweet’ kategorisierenz.B. → P(Banana) ∗ P(Long |Banana) ∗ P(Sweet|banana) ∗ P(Yellow |Banana)

Quelle:http://stackoverflow.com/questions/10059594/a-simple-explanation-of-naive-bayes-classification

Naive Bayes 5. Dezember 2014 12 / 18

Naive Bayes Spam Filter

Spam Filter:Priori: Wahrscheinlichkeiten der Klassen, z.B. P(spam) & P(ham)Likelihood: P(Wort|Klasse) z.B. ’Viagra’ kommt in 100 vorhandenenSpam Mails 30 mal vor → P(Viagra|Spam) 0,3Aber: Produkt aller Vorhandenen Worte fur eine MailEvidence: Die Wahrscheinlichkeit fur Das Auftreten von Wortallgemein.Normalerweise mit ’Add One Smoothing’Ist Multinominal FilterBei binaren Attributen z.B. Auftreten von Worten kann man auchBernoulli Naive Bayes verwendenFur P(Mail |Klasse) muss die Wahrscheinlichkeit der jeweiligenthaltenen Worter aufmultipliziert werden. In der Praxis verwendetman den Logarithmus um Underflow zu vermeiden.

Naive Bayes 5. Dezember 2014 13 / 18

Naive Bayes Spam Filter

Formel

P(S|W ) = P(W |S)∗P(S)P(W |S)∗P(S)+P(W |H)∗P(H)

P(S|W )→ Wahrscheinlichkeit, dass Die Mail Spam ist wenn Wort W in ihrvorkommt.P(W |S)→ Wahrscheinlichkeit, dass Wort W in einer Spam Nachricht vorkommtP(W |H)→ Wahrscheinlichkeit, dass Wort W in einer Ham Nachricht vorkommtP(S)→ Wahrscheinlichkeit, dass Nachricht Spam istP(H)→ Wahrscheinlichkeit, dass Nachricht Spam ist

Naive Bayes 5. Dezember 2014 14 / 18

Naive Bayes Spam Filter Praxis

Trainingsset509 Spam Mails372 Ham Mails

Nach Tokenisierung149131 Worter in Spam Mails107104 Worter in Ham Mails

Testset93 Ham Mails82 Spam MailsErkennungsrate Ham: 100%Erkennungsrate Spam: 91%

Naive Bayes 5. Dezember 2014 15 / 18

Gibt es noch Fragen?

Naive Bayes 5. Dezember 2014 16 / 18

Quellen

blog.zeit.de/mathe/allgemein/weltaidstag-aids-hiv-mathematikhttp://de.wikipedia.org/wiki/Thomas Bayeshttp://en.wikipedia.org/wiki/Bayes%27 theorem#Extended formhttp://de.wikipedia.org/wiki/Satz von Bayeshttp://en.wikipedia.org/wiki/Naive Bayes spam filteringhttp://en.wikipedia.org/wiki/Law of total probabilityhttp://en.wikipedia.org/wiki/Naive Bayes classifierhttp://stackoverflow.com/questions/10059594/a-simple-explanation-of-naive-bayes-classificationhttp://stackoverflow.com/questions/2828113/naive-bayesian-classification-spam-filtering-which-calculation-is-righthttp://stackoverflow.com/questions/2990597/calculating-spam-probabilityhttp://www.statistik.lmu.de/institut/ag/agmg/lehre/2013 SoSe/Stat2Soz 13/vorlesung/3 Stat2Soz 4auf1.pdf

Naive Bayes 5. Dezember 2014 17 / 18

Die wichtigsten Quellen

http://yudkowsky.net/rational/bayeshttps://class.coursera.org/nlp/lecturehttp://www.mblondel.org/journal/2010/06/21/semi-supervised-naive-bayes-in-python/http://forums.udacity.com/questions/100007265/spam-filter-naive-bayes-python-implementationhttp://spamassassin.apache.org/publiccorpus/

Naive Bayes 5. Dezember 2014 18 / 18