Markow-Filter

Dieser Artikel wurde aufgrund von inhaltlichen Mängeln auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf mit, die inhaltlichen Mängel dieses Artikels zu beseitigen und beteilige dich an der Diskussion! (+)
Begründung: Scheinbar zusammenhangslose Informationen. Was genau ein Markov-Filter ist, steht hier leider gar nicht. Siehe auch Diskussionsseite. --pberndt _(DS) 12:40, 27. Okt. 2011 (CEST)

Der Markow-Filter (nach Andrei Andrejewitsch Markow) ist ein Spamfilter basierend auf einem Hidden Markov Model und stellt eine Weiterentwicklung des Bayes-Filters dar. Der Markow-Filter errechnet dabei die Wahrscheinlichkeit, mit der die Wortketten des überprüften Textes zu Wortketten typischer Spamtexte passen. Während bei einem Bayes-Filter die Wahrscheinlichkeit einzelner Wörter errechnet wird, zieht der Markow-Filter Wortketten zur Ermittlung der Wahrscheinlichkeit heran und gewichtet die einzelnen Kombinationsmöglichkeiten. Ähneln die Wortketten des überprüften Textes denen typischer Spamtexte, so gilt der überprüfte Text als Spam.

Beispiel für Gewichtung der Kombinationsmöglichkeiten

Am Beispiel des Satzes „Der schnelle braune Fuchs springt ...“ kann man die Kombinationsmöglichkeiten und Gewichtungen 2^2N im Markow-Filter veranschaulichen:

Wortkette	Gewichtung	N
Der	1	0
Der schnelle	4	1
Der <...> braune	4	1
Der <...> <...> Fuchs	4	1
Der schnelle braune	16	2
Der <...> braune Fuchs	16	2
Der schnelle <...> Fuchs	16	2
Der schnelle braune Fuchs	64	3

Formale Darstellung der Wahrscheinlichkeitsberechnung in Bayes- und Markow-Filter

Während die Wahrscheinlichkeit aufgrund des Bayes-Filters durch

$P_\textrm{lokal}=0.5+\frac{P_{\mathrm{gut}}-P_\mathrm{schlecht}}{P_\mathrm{gut}+P_\mathrm{schlecht}+1}\;$

angegeben wird, gilt für den Markow-Filter

$P_\mathrm{lokal}=0.5+\frac{(P_\mathrm{gut}-P_\mathrm{schlecht}) \cdot \mathit{Gewichtung}}{(P_\mathrm{gut}+P_\mathrm{schlecht}+1) \cdot \mathit{Gewichtung}_\mathrm{maximal}}\;$.

Literatur

• Shalendra Chhabra, William S. Yerazunis, Christian Siefkes: Spam Filtering using a Markov Random Field Model with Variable Weighting Schemas. In: Fourth IEEE International Conference on Data Mining (ICDM'04). 2004, S. 347-350, doi:10.1109/ICDM.2004.10031.

Weblinks

• CRM114 – the Controllable Regex Mutilator