Machine Learning: Einsatz von Bayes’schen Klassifikatoren

Blogpostserie Teil 2: Der Logik auf der Spur

Im ersten Blogpost habe ich einen praktischen Anwendungsfall für Maschine Learning eingeführt und eine grobe Lösung skizziert. In diesem zweiten Blogpost möchte ich etwas näher auf die verwendeten Algorithmen eingehen. Daher ist dies wohl der trockenste Blogbeitrag, den wir hier je publiziert haben, aber um zu verstehen wie der beschriebene Machine Learning Ansatz funktioniert, müssen wir ein wenig in die Mathematik eintauchen.

Bei der Lösungssuche für die Zuweisung der Budgetposten habe ich den Tipp erhalten, dass allenfalls ein Bayes’scher Klassifikator ein möglicher Ansatz ist. Durch Tests und verschiedene Versuche habe ich mit der Zeit, für das im ersten Blogpost beschriebe Problem der Budgetpostenzuordnung herausgefunden, dass die Verwendung eines Bayesianischen Netzes die besten Resultate bringt. Spannend war bei der Lösunsgsuche auch die Tatsache, dass eine solche Klassifikation bessere Resultate ergibt als weitaus komplexere Ansätze (wie beispielsweise Neuronale Netze oder der Algorithmus des Nearest Neighbour). Bereits hier müsste klar werden, dass es nicht einfach eine Lösung für das Thema Machine Learning gibt. Auch die hier gezeigte Lösung ist spezifisch für diesen Anwendungsfall.

Um den mathematischen Ansatz hinter der Budgetzuweisung zu erklären, möchte ich zuerst ein paar Begriffe definieren und erläutern;

Begriffsdefinitionen

Attribut

Attribute entsprechen Eigenschaften eines Objekts. So kann beispielsweise ein Objekt “Zahlung” ein Attribut “Betrag” aufweisen. Jedes Attribut besitzt eine Menge von Werten, welche es annehmen kann.

Attributwert

Attributwerte (auch Merkmal genannt), sind definierte Einheiten, welche zu einem Attribut gehören. Dies können nummerische Werte sein, oder eine fest definierte Menge von Werten, z.B.

Formel_Attributwerte

Klasse

Die Klasse, auch als Klassenattribut bezeichnet, ist das gesuchte Attribut. Jede Klassifizierung versucht anhand einer Menge von Attributen eine Klasse zu suchen bzw. einen Klassenwert zu berechnen.

Klassenwert

Ein Klassenwert entspricht einem Wert, den die Klasse annehmen kann, z.B.:

Formel_Klassenwert

Objekt

Ein Objekt besitzt Eigenschaften, z.B. eine Zahlung.

Beispiel

Objekte werden, sobald diese klassifiziert sind, als „Beispiele“ bezeichnet.

Trainingsdaten

Als Trainingsdaten wird die Menge von möglichen Beispielen bezeichnet, die als Referenzen für künftige Klassifizierungen verwendet werden können.

Trainingsset

Die Trainingsdaten, die als Lerngrundlage für eine Klassifizierung verwendet werden, nennt man Trainingsset oder Testdaten.

Da eine Menge von Attributen auch als Koordinate eines Vektors im n-dimensionalen Raum betrachtet werden kann, sprechen wir auch von Eigenschafts-Vektoren (Featurevector). Somit entspricht ein Beispiel bzw. Objekt der Trainingsdaten einem Vektor bzw. einem Featurevektor im Raum.

Objekt

Wird im Raum als Eigenschaft-Vektor oder Featurevector bezeichnet.

Trainingsdaten

Entsprechen nun einer Menge von klassifizierten Eigenschafts-Vektoren.

Im Falle der Budgetposten-Zuweisung wäre somit eine Zahlung ein Objekt, für welches wir einen Eigenschafts-Vektor bilden. Dieser wird mittels Klassifikation einem Klassenattribut, im Falle der Budgetposten-Zuweisung einem Budgetposten, zugewiesen.

Für die Verwendung eines Klassifikators als Zuweisungsgrundlage für die Auswahl von Budgetposten erschien mir die Verwendung eines selbstlernenden automatischen Klassifikators sinnvoll. Ziel eines klassifizierenden Lernens ist die Vorhersage von Merkmalen eines bestimmten Attributes, dessen Werte nur für einen Teil der Daten bekannt ist. Mit andern Worten: Wir kennen nicht für alle Eigenschaften einer Zahlung die zugehörige Klasse. Beispiele, bei denen uns die Klasse bekannt ist, nennt man klassifizierte Beispiele. Dementsprechend kennen wir die Klasse von unklassifizierten Beispielen nicht.

Klassifizierendes Lernen setzt sich aus zwei Schritten zusammen. Der erste Schritt besteht aus dem Aufbau oder auch Training eines Klassifikators, mit welchem wir in einem zweiten Schritt für unklassifizierte Eigenschafts-Vektoren Klassen suchen und diesen zuordnen. Diese Zuordnung wird als Klassifikation bezeichnet.

Bayes Klassifikation

Ein Bayes’scher Klassifikator weist jedes Objekt der Klasse zu, zu der es mit der grössten Wahrscheinlichkeit gehört oder bei der durch die Einordnung die wenigsten Kosten entstehen. Es handelt sich dabei um eine mathematische Funktion, welche jeden Punkt eines Merkmalraums einer Klasse zuordnet. Der Bayes’sche Klassifikator verwendet dabei ein Kostenmass, welches jeder möglichen Klassifizierung Kosten zuweist. Dabei wird vom Bayes’schen Klassifikator versucht, diese Kosten zu minimieren und die optimale Zuweisung zu finden. Im einfachsten Fall wird ein Kostenmass angenommen, welches nur Kosten verursacht, wenn ein Fehlentscheid vorliegt. Das Ziel des Klassifikators ist also, die Kosten möglichst klein zu halten. Voraussetzung für die Erstellung und Zuweisung eines Kostenmasses ist jedoch, dass bekannt ist, mit welcher Wahrscheinlichkeit ein Punkt des Merkmalraumes zu einer bestimmten Klasse gehört. Da diese Wahrscheinlichkeit in einer praktischen Anwendung jedoch nicht bekannt ist, wird diese abgeschätzt. Dabei geht man von einer Wahrscheinlichkeitsverteilung (in der Regel eine Normalverteilung) aus und versucht, deren Parameter abzuschätzen.
Der Bayes’sche Klassifikator wendet dabei die mathematischen Grundlagen des Bayes Theorem an.

Bayes Theorem

Der Satz von Bayes oder auch Bayes Theorem beschreibt, wie man mit bedingten Wahrscheinlichkeiten rechnet. Der Satz von Bayes lautet für zwei Zufallsereignisse A und B wie folgt:

Formel3

Die bedingten Wahrscheinlichkeiten und nennen wir die a posteriori Wahrscheinlichkeiten. Hingegen bezeichnen wir die Wahrscheinlichkeiten und als a priori Wahrscheinlichkeiten.

Das Bayes Theorem kann mit einem einfachen Urnenbeispiel veranschaulicht werden. In zwei Urnen A und B sind rote und weisse Kugeln. In A befinden sich sieben rote Kugeln und drei weisse Kugeln, in B eine rote und neun weisse. Es wird nun aus A oder B eine beliebige Kugel gezogen. Ob aus A oder B gezogen wird, sei a priori gleich wahrscheinlich. Die gezogene Kugel ist rot. Gesucht ist die Wahrscheinlichkeit dafür, dass diese Kugel aus Urne A stammt. Da die Wahl der Urne gleich wahrscheinlich ist, ergibt sich:

Formel8

Da die Anzahl Kugeln und deren Farbe in beiden Urnen bekannt ist, erhalten wir für Urne A:

Formel9

und für Urne B:

Formel10

daraus ergibt sich für das Ziehen einer roten Kugel eine Wahrscheinlichkeit von:

Formel11

Unter Anwendung des Bayes Theorem erhalten wir nun die Wahrscheinlichkeit, dass eine rote Kugel aus Urne A stammt von:

fehlende Formel

Naive Bayes Klassifikation

Der Satz von Bayes ermöglicht die Abschätzung der Wahrscheinlichkeit einer Klasse für ein gegebenes Klassifizierungsbeispiel. Anhand dieser Wahrscheinlichkeit kann der Featurevektor klassifiziert werden, indem wir die Klasse voraussagen, für die die höchste Wahrscheinlichkeit geschätzt wurde. Wir sind an den a posteriori Wahrscheinlichkeiten für eine Klasse unter dem Auftreten des Vektors interessiert. Setzen wir und in das Bayes Theorem ein, bekommen wir folgenden Berechnungsansatz:

Formel18

Das Klassifikationsproblem kann im Fall der naiven Bayes’schen Klassifikation als die Wahscheinlichkeit, dass eine Zahlung, gegeben durch den Featurevektor , der Klasse zuzuordnen ist, beschrieben werden. Für alle Klassenattribute wird also die bedingte Wahrscheinlichkeit berechnet.

Wenn alle bekannt sind, kann eine Zahlung mit Featurevektor in die Klasse eingeordnet werden, für welche den grössten Wert annimmt. Da in der Budgetposten-Zuweisung nur nominale Attribute zum Einsatz kommen, werde ich mich auf die Berechnung mit nominalen Werten beschränken. Da selten alle bekannt sind, wird folgender Ansatz verfolgt:

Formel28

wobei der Anzahl Trainingssets und der Anzahl der Trainingssets, welche der Klasse zugeordnet wurden, entspricht. Die absolute Häufigkeit der Klasse wird also durch die Anzahl der Trainingssets geteilt. Um dies zu bestimmen, werden alle Trainingssets durchlaufen und wird dementsprechend erhöht. Die Wahrscheinlichkeit, dass genau der von uns gesuchte Vektor bereits im Trainingsset vorhanden ist, ist relativ klein oder nicht vorhanden. Das fehlen von Vektoren würden bei der Abschätzung der Wahrscheinlichkeiten zu sehr kleinen, zu wenig aussagekräftigen Werten führen. Deshalb wird eine naive Annahme getroffen, indem alle Attribute als unabhängig angenommen werden. Damit ergibt sich eine Abschätzmöglichkeit für die gesuchten, bedingten Wahrscheinlichkeiten. Aufgrund dieser Unabhängigkeitsannahme wird dieser Bayes’sche Klassifikator als naiver Bayes’scher Klassifikator bezeichnet.

Formel37

Die Wahrscheinlichkeit kann unabhängig von den anderen Attributen abgeschätzt werden. Dazu wird die relative Häufigkeit der Vektoren, für welche das Attribut den Wert aufweist und das Klassentattribut ist, durch die relative Häufigkeit der Klasse geteilt.

Formel43

entspricht der Anzahl der Trainingssets mit Klassenattribut und Attributwert für das Attribut . Diese kann bereits beim Durchlaufen der Trainingsdaten für die Bestimmung der Anzahl Trainingssets mit Klassenattribut definiert werden. Dabei ergibt sich jedoch ein Problem: Falls die absolute Häufigkeit eines Attributwertes der Klasse 0 beträgt, gilt dies auch für die Wahrscheinlichkeit und somit auch für das Produkt von . Dies hat zur Folge, dass die übrigen Wahrscheinlichkeiten nebensächlich werden. Eine Lösung für dieses Problem ist die m-Abschätzung. Diese geht von einer a priori Schätzung der Wahrscheinlichkeit aus.

m-Abschätzung: Formel58

m steht dabei für die equivalent sample size. Diese ist eine Konstante, welche bestimmt, wie stark relativ zu den trainierten Daten gewichtet wird. Der Name equivalent sample size kommt dabei durch eine mögliche Interpretation als Erweiterung der Attribute in den Klassen um virtuelle Attribute, welche entsprechend verteilt sind. Unter Anwendung der m-Abschätzung ergibt sich folgende Formel für die naive Bayes’sche Klassifikation:

Formel64

Bayes’sche Netzwerke

Im Gegensatz zum naiven Bayes Ansatz wird bei der Anwendung einer Klassifikation mittels Bayes’scher Netzwerke nicht von einer Unabhängigkeit der Attribute ausgegangen. Es können in Form eines gerichteten azyklischen Graphen (DAG) Abhängigkeiten zwischen einzelnen Attributen definiert werden, wobei Knoten Merkmale und deren Kanten Abhängigkeiten zwischen Merkmalen darstellen. Der naive Bayes’sche Klassifikator kann auch als Spezialfall eines Bayes’schen Netzwerk Klassifikators angesehen werden, indem ein sternförmiges Bayes’sches Netz erstellt wird, bei welchem alle Attribute nur von der Klasse abhängen.

Abbildung 1

Jeder Knoten kann einen Wahrscheinlichkeitswert von 0 bis 1 annehmen. Mit diesen Wahrscheinlichkeiten werden die Wahrscheinlichkeiten der Folgeknoten berechnet. Für jeden Knoten wird so eine Tabelle mit bedingten Wahrscheinlichkeiten berechnet. Wenn ein Knoten nur einen Vorgängerknoten besitzt, kann dieser eine einfache bedingte Wahrscheinlichkeit sein.

Die Tabelle der bedingten Wahrscheinlichkeiten enthält für jede mögliche Kombination von direkten Vorgängermerkmalen die bedingte Wahrscheinlichkeit für die Merkmalsausprägungen als . Dadurch kann mit

Formel68

die Wahrscheinlichkeit für einen bestimmten Pfad von Merkmalsausprägungen berechnet werden. Für die Klassifikation werden ein oder mehrere Knoten des Graphen als Zielknoten gewählt. Diese entsprechen der Gruppe, nach welcher die Objekte klassifiziert werden sollen. Um ein Objekt zu klassifizieren, werden die Wahrscheinlichkeiten der Pfade zu den gewählten Zielknoten verglichen und der Zielknoten mit der höchsten Wahrscheinlichkeit ausgewählt.

Zurück zur Praxis

Da ich in einer Anwendung nicht den kompletten Algorithmus implementieren will, entschied ich mich für die Verwendung von WEKA einer Java-Library die eine Vielzahl von Algorithmen bereits fix fertig zur Verfügung stellt. Das Prinzip der Berechnung bleibt dabei das Gleiche. Für jedes Merkmal meiner Zahlung wird die für jeden möglichen Budgetposten die Wahrscheinlichkeit berechnet. So erhalte ich Schlussendlich von WEKA eine Liste meiner Budgetposten und die jeweilige prozentuale Zuordungswahrscheinlichkeit. Ich muss somit nur noch den Budgetposten mit dem grössten Wert selektieren und erhalte so eine relativ hohe Trefferquote. Natürlich kann alles noch optimiert werden. Besipielsweise durch die Verwendung eines Bayes’schen Netzes, indem Abhängigkeiten unter den Zahlunsgmekrmalen definiert werden. So kann ich Beispielsweise definieren, dass die Art des Einkaufs direkt vom Wochentag abhängig ist. Da ich meist am Samstag Grosseinkäufe und Kleidereinkäufe tätige, ergibt sich dadurch bereits eine Verbesserung.

Wie ich Weka in meiner Lösung eingebunden habe und wie mit dem API der Library gearbeitet werden kann werde ich im nächsten Blogpost erklären.

 Hier den dritten Teil der Blogpostserie lesen.

Hier den ersten Teil der Blogpostserie lesen. 

2 Kommentare

  • Matthias Viehweger, 29. November 2016

    Danke für diesen Artikel. Es hat etwas gedauert, ihn zu lesen, aber ich fand es sehr interessant. Leider scheint in der Mitte ein kleiner Teil zu fehlen. Sucht einfach mal nach /^tzung:/ Ich denke mal, dass der Sinn nicht grossartig verloren ging, aber ich wollte es euch trotzdem wissen lassen.

  • mm
    Daniel Binggeli, 1. Dezember 2016

    Hallo Mathias.
    Danke für die Rückmeldung, da fehlte tatsächlich ein teil der Bezeichnung der Formel. Wir haben das nun korrigiert.