Archiv verlassen und diese Seite im Standarddesign anzeigen : Lernender "Filter"
rotalever
2009-07-11, 01:35:10
Hi,
ich habe ein Problem, wo ein Computerprogramm als Eingabe einen Datensatz bekommt (ein bisschen Text (einzelne Wörter und i.d.R. zusätzlich ein paar ganze Sätze), ein-zwei Zahlen) und als Ausgabe entscheiden soll in welche Kategorie der Datensatz eingeteilt werden soll.
Okay, das hört sich jetzt vielleicht etwas unverständlich an ;) Ein Beispiel für sowas wäre ein Spamfilter. Der Eingabedatensatz ist eine Email (bestehend aus Text und Headern), die Ausgabe ist Spam oder nicht Spam.
Nun möchte ich das ganze nicht für Email sondern für etwas anderes machen, auf das ich aber nicht näher eingehe. Ich denke mal das spielt auch nicht so direkt eine Rolle.
Bis jetzt arbeite ich so, dass ich die Datensätze einfach nach mir persönlich sinnvoll erscheinenden Mustern durchsuche und dadurch die Entscheidung treffe in welche Kategorie sie gehören. Dies funktioniert aber leider nur bedingt. Da bin ich auf die Idee gekommen, dass es vielleicht mit einem "intelligent" lernenden System besser klappen könnte. Das System soll also die Datensätze klassifizieren und ich ihm sage, ob es das richtig gemacht hat, oder ob es falsch war. Mit der Zeit würde das System dann immer besser werden und immer weniger Fehler machen.
Jetzt weiß ich darüber allerdings nicht sehr viel (bzw. eigentlich nichts) und da daran ja bestimmt eine Menge geforscht wird, würde ich mich interessieren, was es da so an Verfahren gibt um ein solches lernendes System zu implementieren, dass das was ich beschrieben hat, macht.
Vielleicht kennt ja auch wer schon fertige Implemtierungen, die man irgendwie einbinden kann. Wäre natürlich auch praktisch ;)
Senior Sanchez
2009-07-11, 09:41:08
Hui, na das ist ja ein Thema.
Also ich denke mal ein Klassiker wäre an dieser Stelle der Naive-Bayes-Classifier. Der ist auch nicht sonderlich schwer zu implementieren. (http://de.wikipedia.org/wiki/Naiver_Bayes-Klassifikator)
Es gibt zwar noch ne Menge anderer Klassifikatoren, aber die passen da jetzt nicht so super drauf.
Hui, na das ist ja ein Thema.
Also ich denke mal ein Klassiker wäre an dieser Stelle der Naive-Bayes-Classifier. Der ist auch nicht sonderlich schwer zu implementieren. (http://de.wikipedia.org/wiki/Naiver_Bayes-Klassifikator)
Es gibt zwar noch ne Menge anderer Klassifikatoren, aber die passen da jetzt nicht so super drauf.
Braucht man beim Bayes Klassifikator nicht die priori Wahrscheinlichkeiten, in diesem Fall also die Wahrscheinlichkeiten der Wörter für die Klassen Spam / nicht Spam? Wo nimmt er die denn her?
Spasstiger
2009-07-11, 11:06:00
Wo nimmt er die denn her?
Aus dem Training bzw. auch aus den Entscheidungen im Betrieb. Ich hatte mal in einer Vorlesung was zum Thema Spamfilter, vielleicht finde ich das wieder.
/EDIT: Finde den Artikel nicht mehr. Wir haben da eine Kopie aus einer Zeitschrift bekommen, ging auch um einen Bayes-Klassifikator. Es war so detailliert erklärt, dass man direkt mit dem Programmieren hätte loslegen können. Schade, dass ich den Artikel nicht mehr habe.
Monger
2009-07-11, 11:12:45
Braucht man beim Bayes Klassifikator nicht die priori Wahrscheinlichkeiten, in diesem Fall also die Wahrscheinlichkeiten der Wörter für die Klassen Spam / nicht Spam? Wo nimmt er die denn her?
Das kann nur vom Benutzer kommen. Jede Mail die du als Spam meldest, kommt halt in den Topf der spamverdächtigen Inhalte.
Jede neue herausgehende Mail müsste dann auf Ähnlichkeit mit diesem Topf verglichen werden, um zu beurteilen ob es Spam ist oder nicht.
Bei Mails kann ich mir das sogar noch einigermaßen vorstellen. Da gibts einige Faktoren die man berücksichtigen kann: die Nähe zu bestimmten IP Adressen, bekannte Absenderschemata, bestimmte Wörter...
Und da hört es sich schon langsam auf. Ich weiß, dass moderne Spamfilter auch auf sowas wie Satzrhythmus etc. achten, um Ähnlichkeiten zwischen Mails vom selben Provider zu schließen - was sie dann als maschinengeschriebene Mail entlarven würde. Auf der anderen Seite werden die Spammer immer kleverer, leichte Variationen im Spam zu machen die trotzdem nach natürlicher Sprache aussehen - um genau dieser Erkennung zu entgehen.
Wie genau das funktionieren soll, bewegt sich außerhalb meiner Vorstellungskraft.
So oder so besteht das Hauptproblem wohl darin, erstmal zu definieren was "ähnlich" eigentlich bedeutet, um es dann gewichten zu können.
Senior Sanchez
2009-07-11, 11:38:59
Ich hab mal einen Naive-Bayes-Classifier vor ein paar Wochen in Java geschrieben.
Das war aber zum Lernen anhand von Beispieldatensätzen, ohne Nutzerinteraktion. Der hat die Wahrscheinlichkeiten aus ner Menge von Trainingsdatensätzen jeweils berechnet und die dann auf Testdatensätze angewandt.
Das kann nur vom Benutzer kommen. Jede Mail die du als Spam meldest, kommt halt in den Topf der spamverdächtigen Inhalte.
Jede neue herausgehende Mail müsste dann auf Ähnlichkeit mit diesem Topf verglichen werden, um zu beurteilen ob es Spam ist oder nicht.
Achso, ich hatte das so verstanden dass es automatisch gehen soll. Wenn der Benutzer das System quasi trainieren kann ists ja kein Problem :)
@ TS: Wenn die Daten irgendwie nach bestimmten Mustern aufgeteilt werden sollen würde sich vielleicht auch noch sowas wie k-means anbieten, dass kommt dann im Idealfall ganz ohne Benutzereingabe aus.
http://de.wikipedia.org/wiki/K-means
Und da hört es sich schon langsam auf. Ich weiß, dass moderne Spamfilter auch auf sowas wie Satzrhythmus etc. achten, um Ähnlichkeiten zwischen Mails vom selben Provider zu schließen - was sie dann als maschinengeschriebene Mail entlarven würde. Auf der anderen Seite werden die Spammer immer kleverer, leichte Variationen im Spam zu machen die trotzdem nach natürlicher Sprache aussehen - um genau dieser Erkennung zu entgehen.
Wie genau das funktionieren soll, bewegt sich außerhalb meiner Vorstellungskraft.
Wenn ich nich recht erinnere kann man gerade im Bereich Sprache/Satzbau mit Markovketten und geeigneten Warscheinlichkeitsmodellen erstaunliche Ergebnisse erzielen. Das ganze funktioniert ungefähr so dass du für jeden Buchstaben (bzw Wort, ist dann dasselbe Prinzip nur halt auf Buchstabengruppen) eine Markovkette hast also die Wahrscheinlichkeit für den Buchstaben in Abhängigkeit von den vorhergehenden Buchstaben. Schon mit einer Länge von 2 oder 3 bekommt man da sinnvolle Wörter und fast sinnvolle Sätze wenn mans nur aus Buchstabenebene macht. Das ganze noch erweitert auf Wörter und vielleicht Länge 4 oder 5 und du kannst dir einen Roman generieren lassen ;)
Das Problem ist halt je länger die Kette desto mehr Aufwand... ich glaub länger als 5 oder so ist praktisch nicht machbar weil du Tonnen an Material benötigst um die ganzen Wahrscheinlichkeiten abzuschätzen.
Senior Sanchez
2009-07-11, 13:24:33
K-means bestimmt aber nur Ähnlichkeiten und baut Cluster auf.
Eine direkte Klassifizierung hast du da aber noch nicht.
K-means bestimmt aber nur Ähnlichkeiten und baut Cluster auf.
Eine direkte Klassifizierung hast du da aber noch nicht.
Aber klar: Jeder Datenpunkt gehört zu einem bestimmten Cluster, das ist bereits die Klassifizierung.
rotalever
2009-07-11, 14:27:10
Also ich denke mal ein Klassiker wäre an dieser Stelle der Naive-Bayes-Classifier. Der ist auch nicht sonderlich schwer zu implementieren. (http://de.wikipedia.org/wiki/Naiver_Bayes-Klassifikator)
Das ist wohl das was viele Spamfilter verwenden (zumindest hatte ich das mal gelesen). Wenn es keine besseren Alternativen gibt, werde ich es dann wohl damit mal versuchen...
Bei Mails kann ich mir das sogar noch einigermaßen vorstellen. Da gibts einige Faktoren die man berücksichtigen kann: die Nähe zu bestimmten IP Adressen, bekannte Absenderschemata, bestimmte Wörter...
Und da hört es sich schon langsam auf.
Aber ist es nicht so, dass man mit diesem Bayes-Filter z.B. die Wörter in einem Text auch analysiert, also deren Häufigkeit und dann abschätzt wie wahrscheinlich es ist, dass die Nachricht Spam ist, wenn bestimmte Wörter vorkommen. Aber vll. hab ich das Prinzip auch noch nicht verstanden, hab mich nur mal kurz auf Wikipedia eingelesen :smile:
@ TS: Wenn die Daten irgendwie nach bestimmten Mustern aufgeteilt werden sollen würde sich vielleicht auch noch sowas wie k-means anbieten, dass kommt dann im Idealfall ganz ohne Benutzereingabe aus.
http://de.wikipedia.org/wiki/K-means
Hmm.., ich glaube das würde mich nicht weiterbringen. Ich habe nur zwei Kategorieren in die ich aufteilen möchte.
@Spasstiger irgendeine Idee, wie das Paper vll. hieß?
warum nicht ein einfacher linearer kleinste Quadrate Filter (ähnlich k-Means)
wenn du über die Parameter eine Abstandsfunktion realisieren kannst
bildet der Filter deine Eingabedaten auf z.B. [0,1] ab
Senior Sanchez
2009-07-11, 14:38:07
Aber klar: Jeder Datenpunkt gehört zu einem bestimmten Cluster, das ist bereits die Klassifizierung.
Schon, nur hat das den Nachteil, dass wenn das Teil weiterlernt neue Datensätze hinzukommen und somit die Cluster ständig neu berechnet werden müssen. Das ist jetzt auch nicht sooo gut.
Eventuell bieten sich aber Instance Based Learning Verfahren an, denn die sind ja als lazy-Variante gerade dazu gedacht sich auf eine ständige ändernde Datenbasis einzustellen.
Aber ist es nicht so, dass man mit diesem Bayes-Filter z.B. die Wörter in einem Text auch analysiert, also deren Häufigkeit und dann abschätzt wie wahrscheinlich es ist, dass die Nachricht Spam ist, wenn bestimmte Wörter vorkommen. Aber vll. hab ich das Prinzip auch noch nicht verstanden, hab mich nur mal kurz auf Wikipedia eingelesen :smile:
Mit dem Bayes Klasifikator kannst du die Wahrscheinlichkeit berechnen mit der ein gegebenes Wort in eine Klasse fällt. Du hast nur 2 Klassen: Spam, kein Spam.
Du berechnest also p(Spam | Wort), die WS mit der ein gegebenes Wort (oder eine Nachricht) in die Klasse Spam fällt. Um das zu tun wendest du die Bayes Regel an, dazu benötigst du dann p(Wort | Spam), die WS für die Wörter je nach Spam / nicht Spam. Das ist die Eingabe die du als Benutzer machst wenn du eine Nachricht als Spam markierst.
Hmm.., ich glaube das würde mich nicht weiterbringen. Ich habe nur zwei Kategorieren in die ich aufteilen möchte.
Eben deswegen, wenn deine Kategorien bestimmte Muster aufweisen (z.b. Wörter mit vielen 'e' z.b. EeeePC :) sind Klasse 1, alle anderen Klasse 2 oder so) eignet sich ein k-means ganz gut. Die Schwierigkeit dabei ist nur geeignete Merkmale zu finden, in diesem Beispiel war das einfach die Anzahl der Buchstaben. Man kann sich alles mögliche ausdenken, Anzahl der Wörter mit < 4 Buchstaben, Anzahl der Wörter im ganzen Text, Position der Zahlen usw.
Sowas wie pest vorgeschlagen hat halt.
warum nicht ein einfacher linearer kleinste Quadrate Filter (ähnlich k-Means)
wenn du über die Parameter eine Abstandsfunktion realisieren kannst
bildet der Filter deine Eingabedaten auf z.B. [0,1] ab
vBulletin®, Copyright ©2000-2024, Jelsoft Enterprises Ltd.