Klassifikator (Informatik)

Ein Klassifikator (Informatik) ist ein Algorithmus, der Objekte (z.B. Dokumente) anhand ihrer Merkmale in vorgegebene Kategorien einordnet. Der Begriff "Klassifikator" wird meist spezifisch für solche Algorithmen verwendet, in denen der Klassifikation von Objekten eine Lernphase ("Training") vorausgeht. Diese Methodik kommt z.B. im Webmining, in der Bioinformatik, und in der Robotik häufig zum Einsatz.

Trainieren

In der Lernphase wird dem Klassifikator ein Satz von Trainingsdaten zur Verfügung gestellt. Man unterscheidet folgende Lernszenarien:

• Betreutes Lernen (supervised learning): Für jedes Trainingsbeispiel ist die Kategorisierung bekannt.
• Halb-betreutes Lernen (semi-supervised learning): Nur ein Teil der Trainingsbeispiele ist kategorisiert. Unter den algorithmischen Ansätzen für dieses Szenario finden sich (neben vielen weiteren, z.T. raffinierteren Ideen):
  • Selbst-Training (self-training): Der Klassifikator ordnet die Beispiele selbst ein.
  • Co-Training: Zwei Klassifikatoren ordnen gegenseitig ihre Beispiele ein.
  • Multi-View-Lernen: Zwei oder mehrere Klassifikatoren, die unterschiedlich trainiert wurden, ordnen gegenseitig ihre Beispiele ein.
• Aktives Lernen (active learning): Ausgehend von größtenteils unkategorisierten Daten kann der Klassifikator die Kategoriesierung von einem Teil der Trainingsbeispiele erfragen.
• Unterstütztes Lernen (reinforcement learning): Der Klassifikator, oft Agent genannt, bekommt zwar Feedback von der Umwelt zu seiner Kategorisierung, erfährt aber nicht explizit, was die richtige Kategorisierung gewesen wäre.
• Unbetreutes Lernen (unsupervised learning): Es gibt keine vorkategorisierten Beispiele.

Lernmethoden

Klassifikatoren können auf sehr unterschiedliche Weise lernen und ihre Trainingsbeispiele verwerten. Die Wahl des Algorithmus ist abhängig von der Art der Trainingsdaten sowie den verfügbaren Leistungsreserven. Folgende Lernmethoden werden eingesetzt:

• Entscheidungsbäume und Regressionsbäume
• Induktive logische Programmierung
• Neuronale Netzwerke
• Support-Vector-Maschine
• Clustering z. B. k-means-Clustering (unsupervised)
• Genetische Algorithmen
• kNN-Klassifikator (überwacht)
• Rocchio Klassifikator
• statistische Modellierung z. B. Naive Bayes Klassifikator
• Regelbasierte Klassifikator (Rasteranalyse)

Weitere Lernansätze sind beispielsweise

• Lernen als Suchen
• Generalisierung mit Bias (Der Lerner hat bestimmte „Vorlieben“, zieht Klassen vor)
• Teile und Herrsche-Strategien
• Overfitting-Avoidance: Das Modell generalisieren um die Fehleranfälligkeit zu reduzieren (Bsp.: (Ockhams Rasiermesser)

Evaluierung

Zur Evaluierung des gelernten Modells werden folgende Verfahren eingesetzt:

• Validierung durch Experten
• Validerung auf Daten
• Online-Validierung

Die Valdierung auf Daten hat als Nachteil, dass Trainingsdaten zur Validierung „verschwendet“ werden (Out-of-Sample Testing). Dieses Dilemma kann durch Quer-Validierung (Cross-Validation) gelöst werden: Man teilt die Datensätze in n Teile. Dann nutzt man für jede Partition p die anderen n-1 Partitionen zum Lernen und die Partition p zum Testen.

Zur Bewertung eines Klassifizieres werden gängigerweise drei Größen angegeben, die auf folgender Tabelle basieren:

	positiv klassifiziert	negativ klassifiziert
tatsächlich positiv	a	c	a+c
tatsächlich negativ	b	d	b+d
	a+b	c+ d	n

Treffergenauigkeit (Accuracy)

Die Treffergenauigkeit gibt den Anteil der korrekt klassifizierten Beispiele an.

$\text{accuracy} = \frac{a+d}{n}$

Erinnerung (Recall)

Die Erinnerung gibt den Anteil der positiven Beispiele an, die positiv klassifiziert wurden.

$recall= \frac{a}{a+c}$

Präzision (Precision)

Die Präzision gibt den Anteil der positiv klassifizierten Beispiele an, die tatsächlich positiv sind.

$precision = \frac{a}{a+b}$

zusätzliche Eigenschaften (Feature Engineering)

Die Ansätze zur Erweiterung von Klassifikatoren gliedern sich wie folgt:

• textabhängige Eigenschaften
  • n-Gramme: Ausnutzen des Kontextes durch Verwendung von Sequenzen der Länge n anstelle einzelner Worte (dadurch Unterscheidung von z. B. „mining“ in „web mining“ und „coal mining“)
  • Positionsinformationen
• Linguistische Eigenschaften
  • Stemming: gebeugte Verben auf ihren Wortstamm zurückführen
  • noun phrases: Fokus von n-Grammen auf „echte“ Sätze beschränken (z. B. nur Bigramme mit Noun-Noun und Adverb-Noun)
  • linguistic phrases: Finde alle Vorkommnisse eines syntaktischen Templates (z. B. „noun aux-verb <d-obj>“ findet „I am <Thomas>“)
• Strukturelle Eigenschaften
  • Structural markup
  • Hypertexte
• Feature Subset Selection (FSS)
  • Häufigkeitsbasiert
  • TF-IDF (unsupervised FSS)
  • Maschinelles Lernen
  • Filter und Wrapper
• Feature Construction
  • Latent Semantic Indexing: Die Probleme von Mehrdeutigkeit und Synonymen durch Trennung der Beispiele mit Hyperebenen mittels Singular Value Decomposition lösen.
• Stoppwort-Listen

Verwendung von Dokumentbezügen

Dokumente stehen für gewöhnlich nicht alleine, sondern befinden sich gerade im Netz in gegenseitigem Bezug, vor allem durch Links. Die Informationen aus diesen Links und der Vernetzungsstruktur lassen sich von Klassifikatoren verwenden.

Hubs & Authorities

Siehe auch den Artikel Hubs und Authorities

• Authorities sind Seiten, die viele Informationen zum gesuchten Thema enthalten
• Hubs sind Seiten, die viele Links auf gute Authorities haben

Hierdurch ergibt sich eine gegenseitige Verstärkung. Durch iterative Berechnung der Scores mittels Hub score $h(x) = \sum a(y)$ und Authority score $a(x) = \sum h(y)$ sowie anschließende Normalisierung konvergiert das Verfahren. Probleme:

• Effizienz
• Irrelevante Links (z. B. Werbelinks)
• Gegenseitige Verstärkung von Hosts
• Abweichungen vom Thema

Verbesserungen:

• Verbesserte Verbindungsanalyse: Die Wertungen nach Anzahl der Links normalisieren (Mehrere Links von einem Host werden schwächer gewertet)
• Relevanz-Gewichtung: Dokumente die eine ungenügende Ähnlichkeit zu einem Durchschnittsdokument des Root-Sets haben werden nicht betrachtet

Page Rank

Siehe auch den Artikel PageRank.

Die Idee hinter dem Page Rank ist der „Random Surfer“, der mit Wahrscheinlichkeit d auf einen zufälligen Link auf einer Seite klickt.

Der Page Rank bevorzugt Seiten mit

• vielen eingehenden Links
• Vorgängern mit hohem Page Rank
• Vorgängern mit wenig ausgehenden Links

Hypertext Klassifizierung

Häufig enthalten Webseiten nur wenig Text und/oder viele Bilder. Sie sind in einer anderen Sprache geschrieben, enthalten irritierende Begriffe oder enthalten gar keine nützliche Information. Links hingegen sind von mehreren Autoren geschrieben, enthalten ein reicheres Vokabular, redundante Informationen, erschließen unterschiedliche Aspekte einer Seite und haben ihren Fokus auf den wichtigen Inhalten von Seiten. Sie sind daher zur Klassifizierung von vernetzten Dokumenten sehr geeignet. Die besten Ergebnisse lassen sich erzielen, wenn man zur Klassifizierung einer Seite die Klassen der Vorgänger sowie den Text betrachtet.

Hyperlink Ensembles

• Der Seitentext ist nicht interessant
• Jeder Link zur Seite wird ein eigenes Beispiel
• Linkankertext, Überschrift und den Paragraphen, in dem der Link vorkommt erfassen
• die Trainingsbeispiele (einer pro Link) klassifizieren und daraus die Klassifizierung für das aktuelle Dokument berechnen

Quellen

J. Fürnkranz: Webmining – Data Mining im Web http://www.ke.informatik.tu-darmstadt.de/lehre/ss05/web-mining.html