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.
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.:
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:
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:
Da die Anzahl Kugeln und deren Farbe in beiden Urnen bekannt ist, erhalten wir für Urne A:
und für Urne B:
daraus ergibt sich für das Ziehen einer roten Kugel eine Wahrscheinlichkeit von:
Unter Anwendung des Bayes Theorem erhalten wir nun die Wahrscheinlichkeit, dass eine rote Kugel aus Urne A stammt von:
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:
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:
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.
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.
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:
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:
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.
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
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.
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.
Hallo Mathias.
Danke für die Rückmeldung, da fehlte tatsächlich ein teil der Bezeichnung der Formel. Wir haben das nun korrigiert.