klaus_b@.NET

… oder wie bestimme ich die Wahrscheinlichkeit, ob der angegebene Domänenname des Kommentator den Kriterien eines Kommentarspammers entspricht?

Für mich als Person ist es relativ einfach, einen Kommentar unter einem Blogartikel als Spammer zu erkennen. Aber wie bringe ich meine Erkenntnisse und Erfahrungen einem “Stück Software” bei?
Hier betrachte ich einfach die üblichen Verfahren, wie etwa den Vergleich mit bestehenden Listen, als gegeben und bereits erfüllt. Da auf Listen basierende Filter immer nur gegen bereits bekannte Namen und Kriterien filtern können, hinken sie immer hinterher. Genau hier will ich ansetzen.

Ein angenommener Kommentar hat diese Filter bereits passiert und wurde als unbedenklich eingestuft. Jetzt soll, als letzte Instanz vor der Freigabe, ein heuristischer Filter weiterhelfen.
Damit ist nicht die Heuristik gemeint wie sie etwa ein Virenscanner einsetzt, sondern im Sinne der Definition des Wortes:

Heuristik bezeichnet die Kunst, mit begrenztem Wissen und wenig Zeit zu guten Lösungen zu kommen.

Die Grundlage für so einen Filter kann, aus meiner Sicht, nur ein Verfahren ähnlich einer
Mustererkennung sein, welche auf den Domänennamen angewendet wird. Der Inhalt des Kommentars wird bewusst aus der Bewertung ausgenommen, da eine Einbeziehung des Inhalt des Kommentars nur eine zusätzliche Sprachbarriere bedeuten würde.
Aber wie soll das Ergebnis einer solchen Mustererkennung bewertet werden? Wie soll das Vorkommen eines oder mehrerer erkannter Muster in einem Domänennamen betrachtet werden? Die alleinige Tatsache, dass eines oder mehrere Muster erkannt wurden, stellt noch kein zuverlässiges Kriterium dar. Warum?

Durch die Verarbeitung des alleinigen Vorhandensein eines Begriffes in einem Domänennamen, ist eine sehr hohe Fehlerrate praktisch schon vorbestimmt. Hier ein kleines Beispiel.
Gegeben sind die Begriffe pay, day und loan als Spam-Begriffe. Überprüft soll eine angenommene Domäne paydayloans.org werden. Es werden alle drei Spam-Begriffe erkannt und die Domäne wird als Spam eingestuft. Soweit ist das auch richtig.
Jetzt überprüfen wir einmal eine angenommene Domäne idontlikepaydayloans.com. Diese würde ebenfalls als Spam eingestuft, da auch hier alle drei Spam-Begriffe gefunden werden. Das Ergebnis wäre in diesem Fall aber falsch, da sie mit diesem Namen mit Sicherheit keine Vergabe von Darlehen bewirbt. Nur wie soll diese Aussage bewiesen werden?

Genau solche Probleme werden in der Stochastik behandelt. Genaugenommen in deren Teilgebiet, der Wahrscheinlichkeitstheorie.
Um überhaupt die Wahrscheinlichkeit des Eintretens eines Ereignis, in diesem Fall Domäne-ist-Spammer, berechnen zu können, müssen einige Bedingungen oder Vorgaben, die Axiome, erfüllt sein. Laut den Komolgorow Axiomen wären folgende Vorgaben zu erfüllen:

1. Für jedes Ereignis A aus dem Ereignisraum ist die Wahrscheinlichkeit P(A) eine reelle Zahl zwischen einschließlich 0 und 1.
2. Das sichere Ereignis hat die Wahrscheinlichkeit 1.
3. Die Wahrscheinlichkeit einer Vereinigung abzählbar vieler inkompatibler Ereignisse entspricht der Summe der Wahrscheinlichkeiten der einzelnen Ereignisse.

Als mögliche Ereignisse sind nur Domäne ist Spam oder Domäne ist kein Spam, also Ham, zu erwarten. Wobei das Ereignis Domäne ist Ham das Gegenereignis von Domäne ist Spam darstellt, denn ein Domänenname kann entweder als Spam oder Ham eingestuft werden, nicht aber als beides.

Demzufolge ergibt sich eine Ereignismenge bestehend aus Spam und Ham:

Es gibt nur die beiden Elementarereignisse Spam und Ham. Beide Ereignisse können mit gleicher Wahrscheinlichkeit eintreten. Die beiden Ereignisse sind inkompatibel, d.h. wenn das eine Eintritt, kann das andere nicht eintreten. Damit ist die Voraussetzung für das dritten Axiom erfüllt und es gilt:

Als Ansatz für die Berechnung des Wahrscheinlichkeitsmaßes zur Bewertung eines Domänennamen, wähle ich die Dichte der erkannten Muster im Domänennamen.
Oder anders ausgedrückt:
Ich stelle die Anzahl an Buchstaben aus Spam-Begriffen in einem Domänennamen der Anzahl der Buchstaben des Domänennamens gegenüber.
Ich wage hier die These aufzustellen:

Die Wahrscheinlichkeit, dass ein Domänennamen das Kriterium eines Kommentarspammers entspricht, steigt mit der Anzahl der vorkommenden Spam-Begriffe im Domänennamen.

Oder als Formel dargestellt:

Da die Summe der Buchstaben aus den erkannten Spam-Begriffen nie die Anzahl der Buchstaben des Domänennamen überschreiten kann wird sichergestellt, dass der Wert der Wahrscheinlichkeit immer zwischen einschließlich 0 und 1 liegt. Somit betrachte ich auch die Vorgabe des ersten Axioms als erfüllt.

Sehen wir uns auf Basis der Spam-Formel die oben genannten Beispiele noch einmal an und setzen die entsprechenden Werte ein:
Die drei Spam-Begriffe pay, day und loan gegenüber dem Domänennamen paydayloans.

Der Wert von 0.91, oder 91%, bestätigt die erste Aussage, diese Domäne würde wahrscheinlich richtig als Spam eingestuft.

Betrachten wir jetzt das zweite Beispiel mit idontlikepaydayloans als Domänennamen. Dieser Name suggeriert auf den ersten Blick, er habe nichts mit dem Bewerben von Anleihen zu tun.

Wenn das bloße Vorhandensein von Spam-Begriffen gewertet würde, wäre die Domäne als Spam eingestuft worden. Dem gegenübergestellt die nur 50% Wahrscheinlichkeit aus obiger Gleichung, gibt dem ersten Eindruck Recht oder stellt zumindest die Einstufung als Spam in Frage.

Nachdem die Gleichung steht, werfen wir nun einen Blick auf die Implementierung der algorithmischen Lösung.
Diese Lösung ist nicht weiter kompliziert. Es muss lediglich der Inhalt eines Wörterbuches mit dem Domänennamen verglichen werden. Wird ein Treffer erzielt, summiert sich die Anzahl der Buchstaben des gefundenen Spam-Begriffs auf die Gesamtzahl der bereits gefundenen Begriffe auf. Zum Vermeiden von überlappenden Treffern, wird der jeweilig gefundene Begriff aus dem Domänennamen entfernt. Dieser Vorgang wird solange wiederholt, bis das Wörterbuch abgearbeitet ist.
Um von Anfang an ein günstiges Laufzeitverhalten zu gewährleisten, habe ich mich für den Aufbau eines kategorisiertes Wörterbuch entschieden. Darin werden geläufige Spam-Begriffe als Schlüsselwörter hinterlegt. Unter jedem Schlüsselwort ist eine Liste von weiteren Folgewörtern vorhanden. Diese Liste wird erst verarbeitet, wenn das übergeordnete Schlüsselwort im Domänennamen erkannt wird. Nach dem eine Liste abgearbeitet wurde, wird der Algorithmus beendet und ein Ergebnis zurückgegeben. Daraus ergibt sich im ungünstigsten Fall ein Laufzeitverhalten von: O(N_Keywords + N_Subwords), wie man sehr schön in folgendem Flussdiagramm erkennen kann.

Ich fasse an dieser Stelle noch einmal zusammen.
Die aufgestellte These lautete:
Die Wahrscheinlichkeit, dass ein Domänennamen das Kriterium eines Kommentarspammers entspricht, steigt mit der Anzahl der vorkommenden Spam-Begriffe im Domänennamen.

Die Frage lautet demnach: Wie hoch ist die Wahrscheinlichkeit, dass es sich bei einem Domänennamen um einen Spammer handelt, wenn die Dichte der Spam-Begriffe in diesem Domänennamen hoch genug ist?

Bis jetzt ist lediglich ein Wert ermittelt, der etwas über die Dichte der Spam-Begriffe in einem angegebenem Domänennamen aussagt. Was noch fehlt ist eine Aussage, wie hoch die Wahrscheinlichkeit ist, ob es sich bei dem Domänennamen um einen Spammer handelt.
Gesucht ist also die bedingte Wahrscheinlichkeit des Eintretens Domänennamen ist Spam, wenn das Ereignis Spam-Begriffe im Domänennamen erfüllt ist.
Probleme wie diese lassen sich bestens mit dem Bayestheorem lösen. Sehen wir uns das Theorem einmal an und übertragen die Problemstellung.
Die Formel lautet:

Hierbei bedeuten:

• P(A|B) Die Wahrscheinlichkeit für das Ereignis A wenn B bereits erfüllt ist.
• P(B|A) Die Wahrscheinlichkeit für ein Ereignis B unter der Bedingung, dass A bereits eingetreten ist. Dabei haben die beiden Ereignisse A und B nichts mit den vorherigen Ereignissen aus P(A|B) zu tun sondern stellen eigene Ereignisse dar.
• P(A) Die A-priory-Wahrscheinlichkeit für das Ereignis A aus P(A|B).
• P(B) Die A-priory-Wahrscheinlichkeit für das Ereignis B aus P(A|B)

Da P(B) unbekannt ist, kann diese Größe aus den bekannten Größen abgeleitet werden.
Der wichtigste Punkt hierbei lautet:
Wir haben nur zwei inkompatible Ereignisse. So ist ein Ereignis das Komplement des jeweils anderen. Aus diesem Punkt lässt sich P(B) wie folgt umformen:

Nach der Umformung von P(B) sieht die gesamte Formel folgendermaßen aus:

Darin steht A^c für das Komplement von A. Durch das dritte Axiom kann hier auch geschrieben werden:
A^c = 1 – A und P(B|A^c) = 1 – P(B|A)

Bevor jetzt das Theorem auf die bis jetzt bekannten Werte angewendet wird, möchte ich noch etwas zur A-priory-Wahrscheinlichkeit für das Ereignis A anmerken.
Wie schon aus dem verlinkten Artikel ersichtlich, wird mit dieser Größe die Ursprungswahrscheinlichkeit des Ereignis A, also die Domäne ist Spam, beeinflusst. Für eine unvoreingenommene Bewertung würde diese Größe mit dem Wert 1/2 also 0.5 belegt werden, da die Wahrscheinlichkeit ob Spam oder Ham eintritt ursprünglich gleich ist.
Sollte sich im Laufe der Zeit eine Aussage über die Trefferquote des Filters treffen lassen, so könnte sich diese als Wert auf die Ursprungswahrscheinlichkeit auswirken und diese höher oder niedriger werden lassen.
Es dürfen durchaus auch andere Erkenntnisse des Filters auf diesen Wert angewendet werden. Diese angewandten Erkenntnisse müssen aus dem System selbst, also hier dem Filter der auf dem Theorem basiert, gewonnen worden sein. Aber dazu später mehr.

Wenden wir jetzt das Theorem auf das erste Beispiel mit 10 Buchstaben aus Spam-Begriffen im Domänennamen an.
Die Frage war: Wie wahrscheinlich besteht der Domänenname aus Spam-Begriffen? Als Ergebnis wurde 0.91 ermittelt. Somit setzen wir den Wert in die Gleichung für P(B|A) ein.
Für P(A) setzen wir, wie vorher begründet, 0.5 ein. Nun sieht die Gleichung wie folgt aus:

Der Wahrscheinlichkeit des Eintretens des Ereignisses Domäne ist Spam ist genau so groß wie das ermittelte Verhältnis der Anzahl der Spam-Begriffe zur Anzahl der Buchstaben des Domänennamen.

Nehmen wir nun an, das Schlüsselwort der Spam-Begriffe würde schon öfter in einem Domänennamen gefunden und deshalb als erfolgreich eingestuft. Dadurch wurde die Ursprungswahrscheinlichkeit für dieses Schlüsselwort auf 0,7 erhöht. Wenden wir das Theorem nun auf den neuen Wert an:

Wie erwartet, verschiebt sich die Bewertung mehr in Richtung Einstufung als Spam. Betrachten wir jetzt einmal das zweite Beispiel mit 10 Buchstaben aus Spam-Begriffen gegenüber 20 Buchstaben des Domänennamen mit dem Ergebnis 0.5. Gegeben sei wieder die Ursprungswahrscheinlichkeit des Schlüsselwort mit 0.7:

Wie man aus dem zweiten Beispiel ersehen kann, neigt ein Filter der auf dieser Formel basiert sehr stark dazu, die Domänennamen in Richtung Spam zu bewerten. Die Unschuldsvermutung greift also erst bei Domänennamen mit einer sehr geringen Dichte an Spam-Begriffen.
Man könnte jetzt argumentieren: Die Spam-Begriffe kommen aus einem Wörterbuch welches wirklich nur mit Wörtern gefüllt ist, die überwiegend in Domänennamen auftreten welche auch tatsächlich zum spammen von Kommentaren neigen. Also kann die A-priory-Wahrscheinlichkeit auch hoch genug gewählt werden.
Dem möchte ich die oppositionellen Namen, wie etwa aus dem zweiten Beispiel, entgegen halten. Diese Namenskombinationen würden alle sehr stark in Richtung Spam bewertet werden. Eine unverhältnismäßig hohe falsch-positiv Erkennung wäre die logische Folge.

Einen Ausweg aus dem Dilemma könnte die Verwendung der Wahrscheinlichkeit Domänenname ist Spam-Begriff P(B|A) als A-priory-Wahrscheinlichkeit sein. Ich erhoffe mir dadurch eine deutliche Verschiebung der Wahrscheinlichkeit oberhalb von 0.5 in Richtung Spam und unterhalb in Richtung Ham. Die Werte mit exakt 0.5 sind nicht betroffen, da bei einer Verwendung von 0.5 als A-priory-Wahrscheinlichkeit keine Änderung der Domänenname ist Spam-Begriff Wahrscheinlichkeit P(B|A) eintritt.
Die korrigierte Formel sieht also folgendermaßen aus:

oder in gekürzter Form:

Setzen wir jetzt den Wert 0.91 aus dem ersten Beispiel ein:

Wie erwartet tritt eine starke Verschiebung in Richtung Spam auf.
Setzen wir jetzt eine angenommene Domänenname ist Spam-Begriff Wahrscheinlichkeit
P(B|A) von 0.4 in die Formel ein:

Auch hier tritt die erwartete Verschiebung, diesmal in Richtung Ham, auf.
Durch diese neue Formel neigt der verwendende Filter dazu, bewertete Ergebnisse etwas weiter in die ursprüngliche Richtung zu verschieben und ermöglicht dadurch eine deutlichere Unterscheidung der Ergebnisse.

Ich sehe in der Verwendung der Domänenname ist Spam-Begriff Wahrscheinlichkeit P(B|A) als A-priory-Wahrscheinlichkeit keinen Wiederspruch in der Definition der A-priory-Wahrscheinlichkeit. Ich betrachte diesen Weg als die Anwendung des Prinzips der maximalen Entropie. Dieses erlaubt bereits vorhandenes Wissen über ein System in der A-priory-Wahrscheinlichkeit auszudrücken. Ich betrachte die ermittelte Domänennamen ist Spam-Begriff Wahrscheinlichkeit P(B|A) als vorhandenes Wissen über den Zustand, denn dieser Wert drückt bereits eine Tendenz in eine Richtung aus und erfordert kein zusätzliches Wissen über das System.

Nun ist ein Wert ermittelt, der zwar die Wahrscheinlichkeit mit der es sich um einen Kommentar-Spammer handelt angibt, es ist jedoch noch keine gesicherte Aussage getroffen.
Diese Entscheidung wird in der Regel mit einem Schwellenwert getroffen, der die Trennung zwischen Spam und Ham vornimmt. Doch wo ist die Grenze zu ziehen, bzw. wie hoch ist dieser Wert zu setzen?
Dieses Thema werde ich in einem folgenden Artikel behandeln.

Fazit:

Da heutzutage, dank der SEO-Bemühungen der Seitenbetreiber Keyworddomains zu verwenden, meist der Name einer Webseite schon sehr viel über deren Inhalt aussagt, lässt sich auch ohne Kenntnis der eigentlichen Seite eine gute Vorhersage treffen, wie sicher es sich bei der angegebenen Webseite in einem Blog-Kommentar um einen Spammer handelt. Der eigentliche Inhalt des Kommentars kann hierbei völlig außer Acht gelassen werden.
Natürlich bleibt bei diesem Ansatz noch genügend Raum für Fehler. Ich gebe hier aber zu bedenken, dass ich schon eingangs diesen Ansatz als zusätzlichen Filter vorschlug, der als heuristischer Filter nach einem Regelwerk angesetzt werden sollte.

Wenn ihnen der Artikel gefallen hat oder er für sie hilfreich war, bitten "kicken" sie ihn.