Klassifikation von Handschriften-Vektoren (Schreibererkennung)

Data Mining

Wenn eine Menge von Datensätzen vorliegt, möchte man Zusammenhänge zwischen ihnen erkennen. Dafür kommen Algorithmen des Data Mining zum Einsatz. In unserem Beispiel gibt es eine Menge von Feature-Vektoren, zwischen denen man den Zusammenhang in Form von Ähnlichkeiten untersuchen möchte. Ein Feature-Vektor besteht aus n Features (ungefähr 80), die jeweils eine Achse im n-dimensionalen Raum bilden. Wenn man die Werte der Features auf den entsprechenden Achsen abträgt, wird jeder Feature-Vektor durch einen Punkt in diesem Raum repräsentiert. Nun ist es die Aufgabe die Abstände zwischen den Punkten bzw. zwischen den Feature-Vektoren zu bestimmen. Dazu wählt man eine Distanzfunktion, die für jedes Paar von Feature-Vektoren einen skalaren Wert berechnet. Die Wahl der Distanzfunktion ist abhängig von der Art der Eingabedaten, ihren Datentypen und der vorliegenden Problemstellung.

Beschreibung der Distanzfunktion

In diesem Projekt werden die Distanzen zwischen Feature-Vektoren mit der Hamming-Distanz ermittelt, da sie in dem vorliegenden Fall die besten Resultate erzielt. Zuerst braucht man eine Bewertungsfunktion, die die Distanz zweier einzelner Merkmale bzw. Features auf einen Wert zwischen 0 und 1 abbildet. Diese Bewertungsfunktion ist von der Art des Features abhängig. Einerseits kommt der einfache Wertevergleich (gleich oder nicht, 0 oder 1) in Frage. Andererseits werden die Distanzen aller Werte des Wertebereichs eines Features in Distanzmatrizen gespeichert, welche heuristisch von den Musikwissenschaftlern erstellt wurden. Wenn der Wertevergleich zweier Features über mehrere Ebenen stattfindet, werden die Distanzen für jede Ebene bestimmt, aufaddiert und die Ebenenverwandtschaft in einer weiteren Distanzmatrix abgelesen. Zwei Werte, deren Pfade sich nur ein einer Ebene unterscheiden sind relativ ähnlich und können einen geringen Distanzwert erhalten. Distanzmatrizen sind effizienter; sie benötigen am Anfang einen erhöhten Berechnungsaufwand, dafür sind keine Berechnungen zur Laufzeit notwendig.

Nachdem man die Distanzwerte für jedes Feature-Paar bestimmt hat, wird der Durchschnitt der Distanzen gebildet. Jedes Feature erhält zusätzlich noch ein Gewicht, welches die Relevanz bzw. Wichtigkeit dieses Features widerspiegelt.

Wenn die Distanz zweier Feature-Vektoren klein ist, dann sind die Handschriftcharakteristiken, die sie repräsentieren, ähnlich. Mit Clustering-Methoden aus dem Data-Mining-Bereich kann man eine Menge von Datensätzen, in unserem Beispiel Feature-Vektoren, in Klassen einteilen, die ähnliche Handschriftenmerkmale widerspiegeln und im besten Fall genau einem Schreiber entsprechen. Im vorliegenden Fall sind die Klassen bereits bekannt, und die Aufgabe ist es neue Feature-Vektoren zu klassifizieren. Im enoteHistory-Projekt wurde das instanzbasierte Klassifikationsverfahren k-nearest-neighbor eingesetzt, da es sich am günstigsten erwies. Es klassifiziert existierende Feature-Vektoren mit der Verwendung der Hamming-Distanz und lernt mit jedem neuen Feature-Vektor. Detaillierte und formelle Beschreibungen zu der Distanzfunktion sind in der Diplomarbeit von Lars Milewski zu finden.

Vorgehensweise bei einer Anfrage

Wenn der Nutzer den Schreiber einer unbekannten Notenhandschrift bestimmen möchte, dann stellt er eine Anfrage an das System, indem er manuell die Merkmale der vorliegenden Handschrift abliest. Die Merkmale der Handschrift bilden einen Feature-Vektor. Zur Bestimmung des Schreibers, wird zuerst mit dem Klassifikationsverfahren k-nearest-neighor die k-nächsten Feature-Vektoren zu dem Anfrage-Vektor berechnet, deren Distanz unter einem gewissen Schwellwert liegt. Diese ermittelten Feature-Vektoren repräsentieren die ähnlichsten Handschriften zu der unbekannten Notenhandschrift. Anschließend wird der Schreiber ermittelt, zu dem die meisten Feature-Vektoren in dieser berechneten Menge gehören. Ist die Anzahl der Feature-Vektoren zweier Schreiber gleich, wird der Schreiber zu dem Feature-Vektor ausgegeben, der den kleinsten Distanzwert zum Anfrage-Vektor hat. Somit erhält der Nutzer eine gerankte Liste von Schreibern. In der folgenden Abbildung ist der Ablauf dargestellt, indem die Handschriftcharakteristik einer Notenhandschrift extrahiert und klassifiziert wird.

Evaluierung der Distanzfunktion

Um die besten Resultate bei der Schreibererkennung zu erzielen, ist es notwendig die Distanzfunktion und ihre Parameter zu evaluieren. Dazu bedient man sich einer Scoring-Funktion für instanzbasierte Clustering-Methoden. Die Scoring-Funktion ist ein Maß zur Ähnlichkeit von Clustern. Die Distanzen zwischen Instanzen in einem Cluster sollen so klein wie möglich sein; dagegen versucht man die Distanzen zwischen Instanzen unterschiedlicher Cluster zu maximieren. Das K-Maß bewertet das System basierend auf Klassifikationsaspekten. Die berechnete Ergebnismenge zur Identifikation des Schreibers wird daran bewertet, ob es den richtigen Schreiber enthält oder nicht. K ist somit der Anteil aller Anfragen, in denen der Schreiber richtig erkannt wurde.

Wahl der Distanzfunktion

Es wurden verschiedene Distanzfunktionen getestet und bewertet. Im Schreibererkennungssystem sind keine Cluster-Verfahren zur Berechnung der Klassen notwendig, da die Schreiberklassen bereits bekannt sind. Um die Qualität der Distanzfunktion und ihre Parameter zu bewerten, wird ein Clustering-Algorithmus auf die bereits existierenden Feature-Vektoren angewendet. Die Ausgabe soll genau die bereits bekannten Klassen berechnen. Dabei erzielte die Hamming-Distanz, gemessen an der Scoring-Funktion und dem K-Maß, die besten Resultate.

Optimierung des Schwellwertes

Der Umfang der Ergebnismenge von Feature-Vektoren hängt vom Schwellwert ab. Zur Ermittlung des optimalen Schwellwerts wurden Precision und Recall verwendet. Precision ist ein Maß für die Qualität des Ergebnisses und repräsentiert den Anteil der Feature-Vektoren, die wirklich relevant sind. Dagegen ist Recall ein Maß für die Quantität des Ergebnisses und gibt den Anteil der erwarteten Feature-Vektoren an, die auch wirklich im Ergebnis enthalten sind. Als optimalen Schwellwert ergab sich 0,13, mit dem ein Precision-Wert von 85% und ein Recall-Wert von 70% erreicht wurde.

Gewichte der Features

In der Distanzfunktion erhält jedes Feature ein Gewicht, welches die Relevanz des Features in der Distanzberechnung repräsentiert. Diese Gewichte beeinflussen somit den Distanzwert zwischen zwei Feature-Vektoren. Eine Optimierung eines einzelnen Gewichts kann man erreichen, indem man die Distanz ohne das entsprechende Feature berechnet und analysiert, ob sich das Ergebnis verbessert oder verschlechtert. Wenn sich das Ergebnis verbessert, dann hat das Feature keine so große Bedeutung und sein Gewicht wird verringert. Wenn sich dagegen das Ergebnis verschlechtert, ist das Feature wichtiger und sein Gewicht muss erhöht werden.

Weiterhin muss die Verteilung der Gewichte betrachtet werden. Dabei ergab sich als Kompromiss für eine gute Scoring-Funktion und ein gutes K-Maß eine lineare Verteilung der Gewichte, bei der alle Features unterschiedliche Gewichte haben, welche linear ansteigen. Im Prototypen wurde eine Mischung aus den Gewichten gewählt, die auf dem musikwissenschaftlichen Fachwissen basiert und aus den Tests ermittelt wurden.

Distanzmatrizen

Die Werte in den Distanzmatrizen bestimmen die Ähnlichkeit bzw. den Unterschied zwischen zwei Werten eines Features. Diese Werte wurden von den Musikwissenschaftlern festgelegt. Um auch die Distanzmatrizen zu optimieren, wurden die Werte etwas variiert. Die Ergebnisse konnten nur minimal verbessert werden, indem die ursprünglichen Werte etwas herabgesetzt wurden. Im Prototypen wurden in den meisten Fällen die Werte beibehalten.

Nullwerte

In dem Schreibererkennungssystem unterscheidet man zwischen zwei Arten von Nullwerten für Features: Die Entscheidung, um welche Art des Nullwertes es sich handelt, wird automatisch getroffen, da der Nutzer den Unterschied zwischen ihnen nicht kennt. Auf jeden Fall erhält man bessere Ergebnisse, wenn man so wenige Nullwerte wie möglich im Anfrage-Vektor hat. Bei der manuellen Schreiberanalyse wird neben der Distanz auch der ND-Wert angegeben, der den prozentualen Anteil der Merkmale angibt, die zur Berechnung der Distanz herangezogen wurden. Da Nullwerte Einfluss auf das Ergebnis haben, ist somit der Distanzwert verlässlicher, je größer der ND-Wert ist. Anhand die durchgeführten Tests konnte man eine optimale Konfiguration der Distanzfunktion und ihren Parametern, sowie des Systems finden, welches zur Steigerung der Erkennungsrate von Schreibern beiträgt. In den Test lag die Erkennungsrate bei 90%.