View
223
Download
6
Category
Preview:
Citation preview
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
Recommended