Revision history for Dokumentenklassifikation
Deletions:
Additions:
//Einige Arbeitsschritte der Dokumentenstrukturanalyse visualisiert. Links nach rechts: Ausgangsdokument, Connected Components Algorithmus, K-Nearest-Neighbor Algorithmus, Textlinienerkennung, Begradigung, Textblockerkennung Quelle: Eigenes Programm, Beispieldokument: Broschüre des BAföG-Amts.//
Deletions:
Additions:
{{image url="a1.PNG" height="200"}}{{image url="a2.PNG" height="200"}}{{image url="a3.PNG" height="200"}}{{image url="a4.PNG" height="200"}}{{image url="a5.PNG" height="200"}}{{image url="a6.PNG" height="200"}}
{{image url="GrayText2.PNG" height="200"}} {{image url="BWImage2.PNG" height="200"}}
{{image url="GrayText2.PNG" height="200"}} {{image url="BWImage2.PNG" height="200"}}
Deletions:
{{image url="GrayText2.png" width="200"}} {{image url="BWImage2.png" width="200"}}
Additions:
{{image url="a1.png" width="200"}}{{image url="a2.png" width="200"}}{{image url="a3.png" width="200"}}{{image url="a4.png" width="200"}}{{image url="a5.png" width="200"}}{{image url="a6.png" width="200"}}
{{image url="GrayText2.png" width="200"}} {{image url="BWImage2.png" width="200"}}
//Eindimensionales Signal eines Textblocks (links), Eindimensionales Signal eines Bildblocks (rechts). Quelle: Eigenes Programm//
{{image url="GrayText2.png" width="200"}} {{image url="BWImage2.png" width="200"}}
//Eindimensionales Signal eines Textblocks (links), Eindimensionales Signal eines Bildblocks (rechts). Quelle: Eigenes Programm//
Deletions:
Additions:
{{files}}
Additions:
Rechnungen gibt es in allen möglichen Ausführungen. Die Rechnungen unterschiedlicher Firmen unterscheiden sich meist. Würde ich jetzt mit einer Stichprobe von Rechnungen von nur wenigen unterschiedlichen Firmen lernen, kommt es sehr wahrscheinlich zu Fehlern bei den anderen Firmen. Deshalb //muss jedes Element der Grundgesamtheit die gleichen Chancen haben//.
Der zweite Aspekt des Wortes repräsentativ ist, dass die Stichprobe auch einen gewissen //Umfang// aufweisen muss. Es gibt dabei keinen festen Wert, da sich die Menge von Anwendungsfall zu Anwendungsfall unterscheidet und unter anderem abhängig von der Art der Merkmale ist. Generell gilt jedoch, dass mehr Daten besser sind.
Man sieht, dass man Muster //vereinfachen// kann, indem man sie immer weiter zerlegt. Wie weit sie zerlegt werden sollten, hängt dabei immer von dem Anwendungsfall ab.
Stellen wir uns erneut das komplexe Muster Dokument als digitales Bild vor. Die relativ wenigen Bestandteile sind beispielsweise die schwarzen Pixel auf einem schwarz-weiß-Dokument. Sie alleine beschreiben dieses komplexe Muster, auch wenn sie nur einen geringen Gesamtanteil am Dokumentenbild haben.
Würde ich //zufällig// schwarze Pixel auf einen weißen Hintergrund streuen, würde dies kein Dokument erzeugen, sondern lediglich ein rauschen. Deshalb //führt eine beliebige Auswahl der einfachen Bestandteile nicht zu Mustern//.
- //Verarbeitbarkeit:// Die Ausgangsdaten sollen in einer weiterverarbeitbaren Form gespeichert werden.
- //Konsistenz:// Die Datensätze sollen vollständig und widerspruchsfrei sein.
- //Vereinfachung:// Die Daten sollen nach Möglichkeit vereinfacht werden um die Streuung im Musterraum zu verringern.
- //Selektion:// Es sollen nur für den Anwendungsfall relevante Daten verarbeitet werden.
- //Eliminierung:// Fehlerbehaftete oder unnötige Daten sollen verworfen werden.
- //Korrektur:// Wenn die Möglichkeit besteht, sollen fehlerhafte Daten korrigiert werden.
- //Skalierung:// Die Vergleichbarkeit der Daten soll ermöglicht werden.
Die Aufgabe der Merkmalsextraktion ist es, den //höherdimensionalen// Musterraum auf einen möglichst //niedrigdimensionalen// Merkmalsraum abzubilden. Dieser Merkmalsraum bezeichnet praktisch das, was für den Anwendungsfall von Interesse ist.
Die Nächste-Nachbarn Klassifikation ist ein //lokaler //einfacher und schneller Klassifikator.
Die Erweiterung um den Parameter //k// erlaubt eine etwas komplexere Zuordnung. Der Parameter bestimmt dabei, wie viele der nächsten Nachbarn betrachtet werden. Ist der Parameter //k// beispielsweise 5, werden die Klassenlabels der 5 nächsten Nachbarn verglichen und das häufigste Label wird für den Merkmalsvektor übernommen.
Wichtig für die Nächste-Nachbar Klassifikation ist das geeignete Distanzmaß. Dieses unterscheidet sich je nach Anwendungsfall. Man bezeichnet ihn als lokalen Klassifikator, weil er Klassenlabels rein anhand der nächsten Punkte oder des nächsten Punktes zuordnet.
Der zweite Aspekt des Wortes repräsentativ ist, dass die Stichprobe auch einen gewissen //Umfang// aufweisen muss. Es gibt dabei keinen festen Wert, da sich die Menge von Anwendungsfall zu Anwendungsfall unterscheidet und unter anderem abhängig von der Art der Merkmale ist. Generell gilt jedoch, dass mehr Daten besser sind.
Man sieht, dass man Muster //vereinfachen// kann, indem man sie immer weiter zerlegt. Wie weit sie zerlegt werden sollten, hängt dabei immer von dem Anwendungsfall ab.
Stellen wir uns erneut das komplexe Muster Dokument als digitales Bild vor. Die relativ wenigen Bestandteile sind beispielsweise die schwarzen Pixel auf einem schwarz-weiß-Dokument. Sie alleine beschreiben dieses komplexe Muster, auch wenn sie nur einen geringen Gesamtanteil am Dokumentenbild haben.
Würde ich //zufällig// schwarze Pixel auf einen weißen Hintergrund streuen, würde dies kein Dokument erzeugen, sondern lediglich ein rauschen. Deshalb //führt eine beliebige Auswahl der einfachen Bestandteile nicht zu Mustern//.
- //Verarbeitbarkeit:// Die Ausgangsdaten sollen in einer weiterverarbeitbaren Form gespeichert werden.
- //Konsistenz:// Die Datensätze sollen vollständig und widerspruchsfrei sein.
- //Vereinfachung:// Die Daten sollen nach Möglichkeit vereinfacht werden um die Streuung im Musterraum zu verringern.
- //Selektion:// Es sollen nur für den Anwendungsfall relevante Daten verarbeitet werden.
- //Eliminierung:// Fehlerbehaftete oder unnötige Daten sollen verworfen werden.
- //Korrektur:// Wenn die Möglichkeit besteht, sollen fehlerhafte Daten korrigiert werden.
- //Skalierung:// Die Vergleichbarkeit der Daten soll ermöglicht werden.
Die Aufgabe der Merkmalsextraktion ist es, den //höherdimensionalen// Musterraum auf einen möglichst //niedrigdimensionalen// Merkmalsraum abzubilden. Dieser Merkmalsraum bezeichnet praktisch das, was für den Anwendungsfall von Interesse ist.
Die Nächste-Nachbarn Klassifikation ist ein //lokaler //einfacher und schneller Klassifikator.
Die Erweiterung um den Parameter //k// erlaubt eine etwas komplexere Zuordnung. Der Parameter bestimmt dabei, wie viele der nächsten Nachbarn betrachtet werden. Ist der Parameter //k// beispielsweise 5, werden die Klassenlabels der 5 nächsten Nachbarn verglichen und das häufigste Label wird für den Merkmalsvektor übernommen.
Wichtig für die Nächste-Nachbar Klassifikation ist das geeignete Distanzmaß. Dieses unterscheidet sich je nach Anwendungsfall. Man bezeichnet ihn als lokalen Klassifikator, weil er Klassenlabels rein anhand der nächsten Punkte oder des nächsten Punktes zuordnet.
Deletions:
Um die nachfolgenden Ausführungen bestmöglich zu verstehen, eine kurze Erklärung der Variablen. Vektornotationen ( z.B. x mit Pfeil darüber) können nicht dargestellt werden und werden deshalb als x-Vektor oder Merkmalsvektor gekennzeichnet.
**x** -> Merkmal
**k** -> Klasse/ Klassenlabel
**g** -> Cluster/ Clusternummer
**G** -> Analysegebiet
**S** -> Stichprobe
Rechnungen gibt es in allen möglichen Ausführungen. Die Rechnungen unterschiedlicher Firmen unterscheiden sich meist. Würde ich jetzt mit einer Stichprobe von Rechnungen von nur wenigen unterschiedlichen Firmen lernen, kommt es sehr wahrscheinlich zu Fehlern bei den anderen Firmen. Deshalb muss jedes Element der Grundgesamtheit die gleichen Chancen haben.
Der zweite Aspekt des Wortes repräsentativ ist, dass die Stichprobe auch einen gewissen Umfang aufweisen muss. Es gibt dabei keinen festen Wert, da sich die Menge von Anwendungsfall zu Anwendungsfall unterscheidet und unter anderem abhängig von der Art der Merkmale ist. Generell gilt jedoch, dass mehr Daten besser sind.
Man sieht, dass man Muster vereinfachen kann, indem man sie immer weiter zerlegt. Wie weit sie zerlegt werden sollten, hängt dabei immer von dem Anwendungsfall ab.
Stellen wir uns erneut das komplexe Muster Dokument vor. Die relativ wenigen Bestandteile sind beispielsweise die schwarzen Pixel auf einem schwarz-weiß-Dokument. Sie alleine beschreiben dieses komplexe Muster, auch wenn sie nur einen geringen Gesamtanteil am Dokumentenbild haben.
Würde ich zufällig schwarze Pixel auf einen weißen Hintergrund streuen, würde dies kein Dokument erzeugen, sondern lediglich ein rauschen. Deshalb führt eine beliebige Auswahl der einfachen Bestandteile nicht zu Mustern.
- Verarbeitbarkeit: Die Ausgangsdaten sollen in einer weiterverarbeitbaren Form gespeichert werden.
- Konsistenz: Die Datensätze sollen vollständig und widerspruchsfrei sein.
- Vereinfachung: Die Daten sollen nach Möglichkeit vereinfacht werden um die Streuung im Musterraum zu verringern.
- Selektion: Es sollen nur für den Anwendungsfall relevante Daten verarbeitet werden.
- Eliminierung: Fehlerbehaftete oder unnötige Daten sollen verworfen werden.
- Korrektur: Wenn die Möglichkeit besteht, sollen fehlerhafte Daten korrigiert werden.
- Skalierung: Die Vergleichbarkeit der Daten soll ermöglicht werden.
Die Aufgabe der Merkmalsextraktion ist es, den höherdimensionalen Musterraum auf einen möglichst niedrigdimensionalen Merkmalsraum abzubilden. Dieser Merkmalsraum bezeichnet praktisch das, was für den Anwendungsfall von Interesse ist.
Die Nächste-Nachbarn Klassifikation ist ein lokaler einfacher und schneller Klassifikator.
Die Erweiterung um den Parameter k erlaubt eine etwas komplexere Zuordnung. Der Parameter bestimmt dabei, wie viele der nächsten Nachbarn betrachtet werden. Ist der Parameter k beispielsweise 5, werden die Klassenlabels der 5 nächsten Nachbarn verglichen und das häufigste Label wird für den Merkmalsvektor übernommen.
Das wichtigste für die Nächste-Nachbar Klassifikation ist das geeignete Distanzmaß. Dieses unterscheidet sich je nach Anwendungsfall. Man bezeichnet ihn als lokalen Klassifikator, weil er Klassenlabels rein anhand der nächsten Punkte oder des nächsten Punktes zuordnet.
Additions:
//Arbeitsschritte der Dokumentenstrukturanalyse. Quelle: Eigenes Programm, Beispieldokument: Broschüre des BAföG-Amts.//
Der Ausgangspunkt der Dokumentenklassifikation ist ein normales Papierdokument. Sie hat zum Ziel, dieses Dokument zu "verstehen" und anhand dieses Verständnisses Schlussfolgerungen über Art und/oder Inhalt zu treffen. Dabei wird die gesamte Prozesskette der Mustererkennung angewendet: Die Daten müssen in geeigneter Form aufbereitet werden, diskriminierende Merkmale müssen gefunden und extrahiert werden und anschließend werden die Merkmale durch einen geeigneten Klassifikator klassifiziert.
Um eine Klassifizierung vorzunehmen, wird in diesem Fall ein Lernalgorithmus angewendet. Es wird eine bereits vorgelabelte Lernstichprobe genommen und anhand dieser Informationen kann der Algorithmus die Merkmale der verschiedenen Klassen lernen. Ist der Klassifikator trainiert, können unbekannte Daten von ihm mit einer gewissen Genauigkeit richtig zugeordnet werden. Die Erfolgsquote ist dabei immer von der gesamten Prozesskette abhängig.
Der Ausgangspunkt der Dokumentenklassifikation ist ein normales Papierdokument. Sie hat zum Ziel, dieses Dokument zu "verstehen" und anhand dieses Verständnisses Schlussfolgerungen über Art und/oder Inhalt zu treffen. Dabei wird die gesamte Prozesskette der Mustererkennung angewendet: Die Daten müssen in geeigneter Form aufbereitet werden, diskriminierende Merkmale müssen gefunden und extrahiert werden und anschließend werden die Merkmale durch einen geeigneten Klassifikator klassifiziert.
Um eine Klassifizierung vorzunehmen, wird in diesem Fall ein Lernalgorithmus angewendet. Es wird eine bereits vorgelabelte Lernstichprobe genommen und anhand dieser Informationen kann der Algorithmus die Merkmale der verschiedenen Klassen lernen. Ist der Klassifikator trainiert, können unbekannte Daten von ihm mit einer gewissen Genauigkeit richtig zugeordnet werden. Die Erfolgsquote ist dabei immer von der gesamten Prozesskette abhängig.
Deletions:
//Arbeitsschritte der Dokumentenklassifikation. Quelle: Eigenes Programm, Beispieldokument: Broschüre des BAföG-Amts.//
Der Ausgangspunkt der Dokumentenklassifikation ist ein normales Papierdokument. Sie hat zum Ziel, dieses Dokument zu "verstehen" und anhand dieses Verständnisses Schlussfolgerungen über Art und/oder Inhalt zu treffen.
Dieses Dokument wird in mehreren Schritten weiterverarbeitet.
1) Es wird in ein von einem Programm verwertbares Format gebracht (scannen des Dokuments -> Abspeichern z.B. in PNG)
1) Wenn der Inhalt der Datei bestimmten Kriterien nicht entspricht, wird es korrigiert (schief eingescannt, Kaffeeflecke, rauschen, zu groß/klein)
1) Es wird in seine Merkmale zerlegt (Strukturanalyse, ..)
1) Anhand der Merkmale wird das Dokument klassifiziert.
Um eine Klassifizierung vorzunehmen, muss zusätzlich noch gelernt werden. Das heißt, es werden viele Beispieldaten genommen, die bereits vorklassifiziert (gelablet) sind und anhand dieser Informationen kann ein Lernalgorithmus verschiedene Klassen erlernen und (mit einer gewissen Erfolgsquote) unterscheiden.
Ein Beispiel:
Das Programm lernt die Strukturmerkmale von 500 Beispielbriefen und 500 Beispiel-Buchseiten. Bekommt es nach diesem Training einen unbekannten Brief vorgezeigt, so ist die Wahrscheinlichkeit hoch, dass es ihn richtig erkennt.
Die Erfolgsquote ist dabei immer von der gesamten Prozesskette der Mustererkennung abhängig.
Additions:
__Musterklassifikation:__
Als letzter Schritt werden die Merkmale mit einem geeigneten Klassifikator auf eine bestimmte Anzahl Klassen abgebildet. Für den Anwendungsfall, dass die Art von Dokumenten bestimmt werden soll, würden beispielsweise die mit Klassenlabels versehenen Strukturen verschiedener Dokumenttypen gelernt werden und anschließend könnte das dabei entstehende neuronale Netz neue Dokumente zuordnen.
Additions:
Die Aufgabe der Merkmalsextraktion ist es, den höherdimensionalen Musterraum auf einen möglichst niedrigdimensionalen Merkmalsraum abzubilden. Dieser Merkmalsraum bezeichnet praktisch das, was für den Anwendungsfall von Interesse ist.
Möchte ich beispielsweise Dokumente aufgrund ihrer Struktur klassifizieren können, beinhaltet der Merkmalsraum die Lagebeziehungen und Arten der Strukturblöcke.
Die Merkmalsextraktion nutzt die aufbereiteten Daten der Vorverarbeitung um die relevanten Merkmale zu finden und zu extrahieren. Das schwierigste ist, geeignete Merkmale für den Anwendungsfall zu finden. Man sucht möglichst diskriminierende Merkmale.
Ein Beispielproblem dafür wäre das Erkennen von Textblöcken. Wir haben einen Datensatz aus verschiedensten Blöcken: Texte, Bilder, Logos, Grafiken, ... . Die Blöcke sind als Bild vorhanden. Es ist schwierig, in dem Fall ein entscheidendes Merkmal zu finden. Es gibt aber eines: Textblöcke zeichnen sich dadurch aus, dass sie aus Textzeilen bestehen. Diese verlaufen horizontal und zwischen ihnen ist immer ein gewisser Zeilenabstand. Bei den anderen Blöcken ist das nicht der Fall. Man kann nun das zweidimensionale Bild auf ein eindimensionales Signal abbilden, indem man in jeder Bildzeile die Farbwerte mittelt. Heraus kommt ein Sinusähnliches Signal bei Textblöcken, welches das diskriminierende Merkmal ist.
Die Nächste-Nachbarn Klassifikation ist ein lokaler einfacher und schneller Klassifikator.
Er klassifiziert, indem er von einem Merkmalsvektor ausgehend die Distanzen zu allen anderen Merkmalsvektoren berechnet und ihm die Klasse des Nachbarn mit dem geringsten Abstand zuweist.
Die Erweiterung um den Parameter k erlaubt eine etwas komplexere Zuordnung. Der Parameter bestimmt dabei, wie viele der nächsten Nachbarn betrachtet werden. Ist der Parameter k beispielsweise 5, werden die Klassenlabels der 5 nächsten Nachbarn verglichen und das häufigste Label wird für den Merkmalsvektor übernommen.
Das wichtigste für die Nächste-Nachbar Klassifikation ist das geeignete Distanzmaß. Dieses unterscheidet sich je nach Anwendungsfall. Man bezeichnet ihn als lokalen Klassifikator, weil er Klassenlabels rein anhand der nächsten Punkte oder des nächsten Punktes zuordnet.
Der Nachteil dieser Form der Klassifikation neben seiner Einfachheit ist, dass die gesamte Lernstichprobe verglichen werden muss. Es gibt allerdings Möglichkeiten, dieses Problem zu umgehen, zum Beispiel indem man die Lernstichprobe durch klassentypische Merkmalsvektoren ersetzt.
Möchte ich beispielsweise Dokumente aufgrund ihrer Struktur klassifizieren können, beinhaltet der Merkmalsraum die Lagebeziehungen und Arten der Strukturblöcke.
Die Merkmalsextraktion nutzt die aufbereiteten Daten der Vorverarbeitung um die relevanten Merkmale zu finden und zu extrahieren. Das schwierigste ist, geeignete Merkmale für den Anwendungsfall zu finden. Man sucht möglichst diskriminierende Merkmale.
Ein Beispielproblem dafür wäre das Erkennen von Textblöcken. Wir haben einen Datensatz aus verschiedensten Blöcken: Texte, Bilder, Logos, Grafiken, ... . Die Blöcke sind als Bild vorhanden. Es ist schwierig, in dem Fall ein entscheidendes Merkmal zu finden. Es gibt aber eines: Textblöcke zeichnen sich dadurch aus, dass sie aus Textzeilen bestehen. Diese verlaufen horizontal und zwischen ihnen ist immer ein gewisser Zeilenabstand. Bei den anderen Blöcken ist das nicht der Fall. Man kann nun das zweidimensionale Bild auf ein eindimensionales Signal abbilden, indem man in jeder Bildzeile die Farbwerte mittelt. Heraus kommt ein Sinusähnliches Signal bei Textblöcken, welches das diskriminierende Merkmal ist.
Die Nächste-Nachbarn Klassifikation ist ein lokaler einfacher und schneller Klassifikator.
Er klassifiziert, indem er von einem Merkmalsvektor ausgehend die Distanzen zu allen anderen Merkmalsvektoren berechnet und ihm die Klasse des Nachbarn mit dem geringsten Abstand zuweist.
Die Erweiterung um den Parameter k erlaubt eine etwas komplexere Zuordnung. Der Parameter bestimmt dabei, wie viele der nächsten Nachbarn betrachtet werden. Ist der Parameter k beispielsweise 5, werden die Klassenlabels der 5 nächsten Nachbarn verglichen und das häufigste Label wird für den Merkmalsvektor übernommen.
Das wichtigste für die Nächste-Nachbar Klassifikation ist das geeignete Distanzmaß. Dieses unterscheidet sich je nach Anwendungsfall. Man bezeichnet ihn als lokalen Klassifikator, weil er Klassenlabels rein anhand der nächsten Punkte oder des nächsten Punktes zuordnet.
Der Nachteil dieser Form der Klassifikation neben seiner Einfachheit ist, dass die gesamte Lernstichprobe verglichen werden muss. Es gibt allerdings Möglichkeiten, dieses Problem zu umgehen, zum Beispiel indem man die Lernstichprobe durch klassentypische Merkmalsvektoren ersetzt.
Deletions:
Additions:
Die Vorverarbeitung beschäftigt sich mit der Aufbereitung der Daten für die Weiterverarbeitung.
Ihre Ziele sind:
- Verarbeitbarkeit: Die Ausgangsdaten sollen in einer weiterverarbeitbaren Form gespeichert werden.
- Konsistenz: Die Datensätze sollen vollständig und widerspruchsfrei sein.
- Vereinfachung: Die Daten sollen nach Möglichkeit vereinfacht werden um die Streuung im Musterraum zu verringern.
- Selektion: Es sollen nur für den Anwendungsfall relevante Daten verarbeitet werden.
- Eliminierung: Fehlerbehaftete oder unnötige Daten sollen verworfen werden.
- Korrektur: Wenn die Möglichkeit besteht, sollen fehlerhafte Daten korrigiert werden.
- Skalierung: Die Vergleichbarkeit der Daten soll ermöglicht werden.
Diese Zielstellungen bestmöglich zu erfüllen ist ein essentieller Schritt für die Mustererkennung. Wird an fehlerhaften oder schlechten Daten gelernt, verschlechtert sich das Endergebnis. Eine saubere Vorverarbeitung zu ermöglichen kann deshalb sehr viel Zeit in einem Mustererkennungsprojekt in Anspruch nehmen. Leider lässt sich schlecht Bewerten, wie gut eine Vorverarbeitung ist, da die Ergebnisse von der gesamten Prozesskette abhängig ist. Jedoch können Expertenschätzungen, Parametervariationen und heuristische Bewertungen dafür einen Anhaltspunkt liefern.
Eine Beispiel der Vorverarbeitungsschritte in der Dokumentenanalyse:
- Einscannen des Papierdokuments
- Abspeichern in geeignetem Bildformat
- Umwandeln digitaler Dokumente in selbiges Format
- Änderung der Kodierung von Farbkodierung auf Graustufen
- Thresholding
- Begradigen des Dokuments
- Skalierung der Bilder auf einheitliche Größe
- Entfernen von Rauschen und anderen Verunreinigungen des Dokuments
- Extraktion der Strukturblöcke
- Vereinheitlichung und Filterung der Strukturblöcke
Die Aufgabe der Merkmalsextraktion ist es, den höherdimensionalen Musterraum auf einen möglichst niedrigdimensionalen Merkmalsraum abzubilden.
Ihre Ziele sind:
- Verarbeitbarkeit: Die Ausgangsdaten sollen in einer weiterverarbeitbaren Form gespeichert werden.
- Konsistenz: Die Datensätze sollen vollständig und widerspruchsfrei sein.
- Vereinfachung: Die Daten sollen nach Möglichkeit vereinfacht werden um die Streuung im Musterraum zu verringern.
- Selektion: Es sollen nur für den Anwendungsfall relevante Daten verarbeitet werden.
- Eliminierung: Fehlerbehaftete oder unnötige Daten sollen verworfen werden.
- Korrektur: Wenn die Möglichkeit besteht, sollen fehlerhafte Daten korrigiert werden.
- Skalierung: Die Vergleichbarkeit der Daten soll ermöglicht werden.
Diese Zielstellungen bestmöglich zu erfüllen ist ein essentieller Schritt für die Mustererkennung. Wird an fehlerhaften oder schlechten Daten gelernt, verschlechtert sich das Endergebnis. Eine saubere Vorverarbeitung zu ermöglichen kann deshalb sehr viel Zeit in einem Mustererkennungsprojekt in Anspruch nehmen. Leider lässt sich schlecht Bewerten, wie gut eine Vorverarbeitung ist, da die Ergebnisse von der gesamten Prozesskette abhängig ist. Jedoch können Expertenschätzungen, Parametervariationen und heuristische Bewertungen dafür einen Anhaltspunkt liefern.
Eine Beispiel der Vorverarbeitungsschritte in der Dokumentenanalyse:
- Einscannen des Papierdokuments
- Abspeichern in geeignetem Bildformat
- Umwandeln digitaler Dokumente in selbiges Format
- Änderung der Kodierung von Farbkodierung auf Graustufen
- Thresholding
- Begradigen des Dokuments
- Skalierung der Bilder auf einheitliche Größe
- Entfernen von Rauschen und anderen Verunreinigungen des Dokuments
- Extraktion der Strukturblöcke
- Vereinheitlichung und Filterung der Strukturblöcke
Die Aufgabe der Merkmalsextraktion ist es, den höherdimensionalen Musterraum auf einen möglichst niedrigdimensionalen Merkmalsraum abzubilden.
Additions:
Es folgt eine Beschreibung einer Auswahl von Postulaten.
==//„Für ein Analysegebiet lässt sich eine repräsentative Stichprobe finden. Jedes Element der Grundgesamtheit muss gleiche Chancen haben, in die Stichprobe aufgenommen zu werden.“//==
==//"Ein komplexes Muster lässt sich in einfachere Bestandteile zerlegen, die untereinander in strukturellen Beziehungen stehen."==
==//==
==//„Komplexe Muster lassen sich meist durch relativ wenige einfachere Bestandteile darstellen. Eine beliebige Auswahl dieser führt nicht zu Mustern.“//==
Stellen wir uns erneut das komplexe Muster Dokument vor. Die relativ wenigen Bestandteile sind beispielsweise die schwarzen Pixel auf einem schwarz-weiß-Dokument. Sie alleine beschreiben dieses komplexe Muster, auch wenn sie nur einen geringen Gesamtanteil am Dokumentenbild haben.
Würde ich zufällig schwarze Pixel auf einen weißen Hintergrund streuen, würde dies kein Dokument erzeugen, sondern lediglich ein rauschen. Deshalb führt eine beliebige Auswahl der einfachen Bestandteile nicht zu Mustern.
==//„Für ein Analysegebiet lässt sich eine repräsentative Stichprobe finden. Jedes Element der Grundgesamtheit muss gleiche Chancen haben, in die Stichprobe aufgenommen zu werden.“//==
==//"Ein komplexes Muster lässt sich in einfachere Bestandteile zerlegen, die untereinander in strukturellen Beziehungen stehen."==
==//==
==//„Komplexe Muster lassen sich meist durch relativ wenige einfachere Bestandteile darstellen. Eine beliebige Auswahl dieser führt nicht zu Mustern.“//==
Stellen wir uns erneut das komplexe Muster Dokument vor. Die relativ wenigen Bestandteile sind beispielsweise die schwarzen Pixel auf einem schwarz-weiß-Dokument. Sie alleine beschreiben dieses komplexe Muster, auch wenn sie nur einen geringen Gesamtanteil am Dokumentenbild haben.
Würde ich zufällig schwarze Pixel auf einen weißen Hintergrund streuen, würde dies kein Dokument erzeugen, sondern lediglich ein rauschen. Deshalb führt eine beliebige Auswahl der einfachen Bestandteile nicht zu Mustern.
Deletions:
//"Ein komplexes Muster lässt sich in einfachere Bestandteile zerlegen, die untereinander in strukturellen Beziehungen stehen."
//
//„Komplexe Muster lassen sich meist durch relativ wenige einfachere Bestandteile darstellen. Eine beliebige Auswahl dieser führt nicht zu Mustern.“//
Additions:
Dieses Postulat lässt sich mit einem Beispiel aus der Dokumentenanalyse erläutern:
Nehmen wir an, dass Rechnungsdokumente automatisch verarbeitet werden sollen. Dazu muss ich meine Prozesskette an einer Stichprobe testen.
Rechnungen gibt es in allen möglichen Ausführungen. Die Rechnungen unterschiedlicher Firmen unterscheiden sich meist. Würde ich jetzt mit einer Stichprobe von Rechnungen von nur wenigen unterschiedlichen Firmen lernen, kommt es sehr wahrscheinlich zu Fehlern bei den anderen Firmen. Deshalb muss jedes Element der Grundgesamtheit die gleichen Chancen haben.
Der zweite Aspekt des Wortes repräsentativ ist, dass die Stichprobe auch einen gewissen Umfang aufweisen muss. Es gibt dabei keinen festen Wert, da sich die Menge von Anwendungsfall zu Anwendungsfall unterscheidet und unter anderem abhängig von der Art der Merkmale ist. Generell gilt jedoch, dass mehr Daten besser sind.
Dieses Postulat ist ebenfalls einfach am Beispiel von Dokumenten erklärt. Betrachte ich das Dokument als Muster an sich, ist es schwierig zu verarbeiten, da ich außer den rohen Bilddaten keine wirklichen Informationen habe. Ich kann es durch verschiedene Algorithmen aber immer weiter in seine Bestandteile zerlegen:
- Das Dokument wird definiert aus Dokumentstrukturblöcken, die zueinander in einer Beziehung stehen. (Überschrift, Textblock 1, Textblock 2, ... , Bild, Grafik, Adresse)
- Diese Strukturblöcke lassen sich ebenfalls zerlegen. Die Textblöcke beispielsweise bestehen aus Textzeilen.
- Die Textzeilen bestehen aus Wörtern
- Die Wörter bestehen aus Buchstaben
- Die Buchstaben bestehen aus Pixeln
Man sieht, dass man Muster vereinfachen kann, indem man sie immer weiter zerlegt. Wie weit sie zerlegt werden sollten, hängt dabei immer von dem Anwendungsfall ab.
Nehmen wir an, dass Rechnungsdokumente automatisch verarbeitet werden sollen. Dazu muss ich meine Prozesskette an einer Stichprobe testen.
Rechnungen gibt es in allen möglichen Ausführungen. Die Rechnungen unterschiedlicher Firmen unterscheiden sich meist. Würde ich jetzt mit einer Stichprobe von Rechnungen von nur wenigen unterschiedlichen Firmen lernen, kommt es sehr wahrscheinlich zu Fehlern bei den anderen Firmen. Deshalb muss jedes Element der Grundgesamtheit die gleichen Chancen haben.
Der zweite Aspekt des Wortes repräsentativ ist, dass die Stichprobe auch einen gewissen Umfang aufweisen muss. Es gibt dabei keinen festen Wert, da sich die Menge von Anwendungsfall zu Anwendungsfall unterscheidet und unter anderem abhängig von der Art der Merkmale ist. Generell gilt jedoch, dass mehr Daten besser sind.
Dieses Postulat ist ebenfalls einfach am Beispiel von Dokumenten erklärt. Betrachte ich das Dokument als Muster an sich, ist es schwierig zu verarbeiten, da ich außer den rohen Bilddaten keine wirklichen Informationen habe. Ich kann es durch verschiedene Algorithmen aber immer weiter in seine Bestandteile zerlegen:
- Das Dokument wird definiert aus Dokumentstrukturblöcken, die zueinander in einer Beziehung stehen. (Überschrift, Textblock 1, Textblock 2, ... , Bild, Grafik, Adresse)
- Diese Strukturblöcke lassen sich ebenfalls zerlegen. Die Textblöcke beispielsweise bestehen aus Textzeilen.
- Die Textzeilen bestehen aus Wörtern
- Die Wörter bestehen aus Buchstaben
- Die Buchstaben bestehen aus Pixeln
Man sieht, dass man Muster vereinfachen kann, indem man sie immer weiter zerlegt. Wie weit sie zerlegt werden sollten, hängt dabei immer von dem Anwendungsfall ab.
Deletions:
Erklärung
Bild
Erklärung
Bild
Erklärung
Additions:
====Wichtige Variablen====
Um die nachfolgenden Ausführungen bestmöglich zu verstehen, eine kurze Erklärung der Variablen. Vektornotationen ( z.B. x mit Pfeil darüber) können nicht dargestellt werden und werden deshalb als x-Vektor oder Merkmalsvektor gekennzeichnet.
**x** -> Merkmal
**k** -> Klasse/ Klassenlabel
**g** -> Cluster/ Clusternummer
**G** -> Analysegebiet
**S** -> Stichprobe
Zu den Aufgaben der computergestützten Intelligenz gehören folgende:
__Die Klassifikation:__
Die Klassifikation hat zum Ziel, dass der Merkmalsraum auf eine diskrete Menge abgebildet wird (x --> k). Im Beispiel der Dokumentenverarbeitung bedeutet es, dass beispielsweise anhand der Strukturdaten Aussagen über die Art des Dokuments getroffen werden. Also Struktur**daten --> Aussage** wie "Brief" oder "Rechnung".
Das geschieht durch das überwachte Lernen. Überwacht bedeutet hierbei, dass gelabelte Daten vorliegen. Also ein Experte hat bereits im Vorfeld zu den jeweiligen Strukturdaten die Dokumentart vorgegeben. Somit haben wir Datenpaare **(x, k)**, die dann vom Programm gelernt werden und je nach Erfolg kann dieses dann neue Daten klassifizieren.
__Das Clustering:__
Das Clustering ähnelt stark der Klassifikation. Die Hauptunterschiede sind, dass nicht auf ein Klassenlabel k, sondern auf eine Clusternummer g abgebildet wird und es ein **unüberwachtes** Lernen ist. Das bedeutet, es sind nur die Merkmalsvektoren gegeben, keine label. Gelernt wird dabei, indem auf Ähnlichkeit geprüft wird und ähnliche Daten zu einem Cluster zusammengefügt werden.
__Die Regression:__
Die Regression lässt sich am einfachsten durch das Beispiel der Börsenspekulation erklären. Anhand der Daten aus der Vergangenheit versucht ein Programm Prognosen für die Zukunft aufzustellen. Es werden Abhängigkeiten der Merkmale gelernt.
__Die Assoziation:__
Bei der Assoziation werden Daten, die eigentlich nichts direkt miteinander zutun haben auf Verbindungen überprüft. Beispielsweise der Zusammenhang zwischen Arbeiterzufriedenheit und deren Leistung. Beides sind verschiedene Merkmalsvektoren und können doch miteinander verknüpft sein.
__Signalwandlung:__
Wir haben eine physikalische Größe, z.B. ein Papierdokument, und möchten daraus ein analoges Signal erzeugen. Das geschieht z.B. mithilfe von Sensoren und in unserem Fall durch einen Scanner.
__Digitalisierung:__
Das analoge Signal muss zu einem digitalen gewandelt werden. Dies geschieht meistens über Abtastung oder wie in unserem Fall durch Rasterisierung.
__Vorverarbeitung:__
In der Vorverarbeitung werden die digitalen Signale verbessert, z.B. durch Filterung, Normierung, Kodierung, etc. Am Ende der Vorverarbeitung sollen alle Daten gleich behandelbar sein. Im Falle der Dokumentenverarbeitung würden die Daten in ein Bildformat wie PNG kodiert werden, dann werden Fehler wie Kaffeeflecken oder Rauschen bereinigt und das Bild begradigt und auf eine einheitliche Größe gebracht.
__Merkmalsextraktion:__
Nun werden Merkmale bestimmt, die aus den Daten gezogen werden sollen. Hierbei ist es wichtig, die richtigen Merkmale zu finden, die für den jeweiligen Zweck benötigt werden. Im Falle der Dokumentenverarbeitung wäre es z.B. die Extraktion der Strukturdaten des Dokuments.
Um die nachfolgenden Ausführungen bestmöglich zu verstehen, eine kurze Erklärung der Variablen. Vektornotationen ( z.B. x mit Pfeil darüber) können nicht dargestellt werden und werden deshalb als x-Vektor oder Merkmalsvektor gekennzeichnet.
**x** -> Merkmal
**k** -> Klasse/ Klassenlabel
**g** -> Cluster/ Clusternummer
**G** -> Analysegebiet
**S** -> Stichprobe
Zu den Aufgaben der computergestützten Intelligenz gehören folgende:
__Die Klassifikation:__
Die Klassifikation hat zum Ziel, dass der Merkmalsraum auf eine diskrete Menge abgebildet wird (x --> k). Im Beispiel der Dokumentenverarbeitung bedeutet es, dass beispielsweise anhand der Strukturdaten Aussagen über die Art des Dokuments getroffen werden. Also Struktur**daten --> Aussage** wie "Brief" oder "Rechnung".
Das geschieht durch das überwachte Lernen. Überwacht bedeutet hierbei, dass gelabelte Daten vorliegen. Also ein Experte hat bereits im Vorfeld zu den jeweiligen Strukturdaten die Dokumentart vorgegeben. Somit haben wir Datenpaare **(x, k)**, die dann vom Programm gelernt werden und je nach Erfolg kann dieses dann neue Daten klassifizieren.
__Das Clustering:__
Das Clustering ähnelt stark der Klassifikation. Die Hauptunterschiede sind, dass nicht auf ein Klassenlabel k, sondern auf eine Clusternummer g abgebildet wird und es ein **unüberwachtes** Lernen ist. Das bedeutet, es sind nur die Merkmalsvektoren gegeben, keine label. Gelernt wird dabei, indem auf Ähnlichkeit geprüft wird und ähnliche Daten zu einem Cluster zusammengefügt werden.
__Die Regression:__
Die Regression lässt sich am einfachsten durch das Beispiel der Börsenspekulation erklären. Anhand der Daten aus der Vergangenheit versucht ein Programm Prognosen für die Zukunft aufzustellen. Es werden Abhängigkeiten der Merkmale gelernt.
__Die Assoziation:__
Bei der Assoziation werden Daten, die eigentlich nichts direkt miteinander zutun haben auf Verbindungen überprüft. Beispielsweise der Zusammenhang zwischen Arbeiterzufriedenheit und deren Leistung. Beides sind verschiedene Merkmalsvektoren und können doch miteinander verknüpft sein.
__Signalwandlung:__
Wir haben eine physikalische Größe, z.B. ein Papierdokument, und möchten daraus ein analoges Signal erzeugen. Das geschieht z.B. mithilfe von Sensoren und in unserem Fall durch einen Scanner.
__Digitalisierung:__
Das analoge Signal muss zu einem digitalen gewandelt werden. Dies geschieht meistens über Abtastung oder wie in unserem Fall durch Rasterisierung.
__Vorverarbeitung:__
In der Vorverarbeitung werden die digitalen Signale verbessert, z.B. durch Filterung, Normierung, Kodierung, etc. Am Ende der Vorverarbeitung sollen alle Daten gleich behandelbar sein. Im Falle der Dokumentenverarbeitung würden die Daten in ein Bildformat wie PNG kodiert werden, dann werden Fehler wie Kaffeeflecken oder Rauschen bereinigt und das Bild begradigt und auf eine einheitliche Größe gebracht.
__Merkmalsextraktion:__
Nun werden Merkmale bestimmt, die aus den Daten gezogen werden sollen. Hierbei ist es wichtig, die richtigen Merkmale zu finden, die für den jeweiligen Zweck benötigt werden. Im Falle der Dokumentenverarbeitung wäre es z.B. die Extraktion der Strukturdaten des Dokuments.
Additions:
{{image url="dk1.png" width="200"}}{{image url="dk2.png" width="200"}}{{image url="dk3.png" width="200"}}{{image url="dk4.png" width="200"}}{{image url="dk5.png" width="200"}}{{image url="dk6.png" width="200"}}
//Arbeitsschritte der Dokumentenklassifikation. Quelle: Eigenes Programm, Beispieldokument: Broschüre des BAföG-Amts.//
//Arbeitsschritte der Dokumentenklassifikation. Quelle: Eigenes Programm, Beispieldokument: Broschüre des BAföG-Amts.//
Deletions:
Bilder
Additions:
{{files}}
Additions:
Bilder
Der Ausgangspunkt der Dokumentenklassifikation ist ein normales Papierdokument. Sie hat zum Ziel, dieses Dokument zu "verstehen" und anhand dieses Verständnisses Schlussfolgerungen über Art und/oder Inhalt zu treffen.
Dieses Dokument wird in mehreren Schritten weiterverarbeitet.
1) Es wird in ein von einem Programm verwertbares Format gebracht (scannen des Dokuments -> Abspeichern z.B. in PNG)
1) Wenn der Inhalt der Datei bestimmten Kriterien nicht entspricht, wird es korrigiert (schief eingescannt, Kaffeeflecke, rauschen, zu groß/klein)
1) Es wird in seine Merkmale zerlegt (Strukturanalyse, ..)
1) Anhand der Merkmale wird das Dokument klassifiziert.
Um eine Klassifizierung vorzunehmen, muss zusätzlich noch gelernt werden. Das heißt, es werden viele Beispieldaten genommen, die bereits vorklassifiziert (gelablet) sind und anhand dieser Informationen kann ein Lernalgorithmus verschiedene Klassen erlernen und (mit einer gewissen Erfolgsquote) unterscheiden.
Ein Beispiel:
Das Programm lernt die Strukturmerkmale von 500 Beispielbriefen und 500 Beispiel-Buchseiten. Bekommt es nach diesem Training einen unbekannten Brief vorgezeigt, so ist die Wahrscheinlichkeit hoch, dass es ihn richtig erkennt.
Die Erfolgsquote ist dabei immer von der gesamten Prozesskette der Mustererkennung abhängig.
Der Ausgangspunkt der Dokumentenklassifikation ist ein normales Papierdokument. Sie hat zum Ziel, dieses Dokument zu "verstehen" und anhand dieses Verständnisses Schlussfolgerungen über Art und/oder Inhalt zu treffen.
Dieses Dokument wird in mehreren Schritten weiterverarbeitet.
1) Es wird in ein von einem Programm verwertbares Format gebracht (scannen des Dokuments -> Abspeichern z.B. in PNG)
1) Wenn der Inhalt der Datei bestimmten Kriterien nicht entspricht, wird es korrigiert (schief eingescannt, Kaffeeflecke, rauschen, zu groß/klein)
1) Es wird in seine Merkmale zerlegt (Strukturanalyse, ..)
1) Anhand der Merkmale wird das Dokument klassifiziert.
Um eine Klassifizierung vorzunehmen, muss zusätzlich noch gelernt werden. Das heißt, es werden viele Beispieldaten genommen, die bereits vorklassifiziert (gelablet) sind und anhand dieser Informationen kann ein Lernalgorithmus verschiedene Klassen erlernen und (mit einer gewissen Erfolgsquote) unterscheiden.
Ein Beispiel:
Das Programm lernt die Strukturmerkmale von 500 Beispielbriefen und 500 Beispiel-Buchseiten. Bekommt es nach diesem Training einen unbekannten Brief vorgezeigt, so ist die Wahrscheinlichkeit hoch, dass es ihn richtig erkennt.
Die Erfolgsquote ist dabei immer von der gesamten Prozesskette der Mustererkennung abhängig.
Additions:
====Was ist Dokumentenklassifikation?====
====Die Aufgaben der computergestützten Intelligenz====
====Die Prozesskette der Mustererkennung====
====Postulate====
""<div style="float:left; margin: 10px 0 10px 0; padding: 10px 15px 10px 15px; width:97%; background-color:#FFC; border:1px solid #EDD">
<h4>Was ist ein Postulat?</h4>
Ein Postulat beschreibt etwas, das nicht beweisbar ist und doch als unabdingbares Fundament für weitere Theorien gebraucht wird.
""
==Postulat:==
//„Für ein Analysegebiet lässt sich eine repräsentative Stichprobe finden. Jedes Element der Grundgesamtheit muss gleiche Chancen haben, in die Stichprobe aufgenommen zu werden.“//
Bild
Erklärung
==Postulat:==
//"Ein komplexes Muster lässt sich in einfachere Bestandteile zerlegen, die untereinander in strukturellen Beziehungen stehen."
//
Bild
Erklärung
==Postulat:==
//„Komplexe Muster lassen sich meist durch relativ wenige einfachere Bestandteile darstellen. Eine beliebige Auswahl dieser führt nicht zu Mustern.“//
Bild
Erklärung
====Die Vorverarbeitung====
====Die Extraktion und Verarbeitung der Merkmale====
====Die Nächste-Nachbarn Klassifikation "NN" und ihre Erweiterung "k-NN"====
====Die Aufgaben der computergestützten Intelligenz====
====Die Prozesskette der Mustererkennung====
====Postulate====
""<div style="float:left; margin: 10px 0 10px 0; padding: 10px 15px 10px 15px; width:97%; background-color:#FFC; border:1px solid #EDD">
<h4>Was ist ein Postulat?</h4>
Ein Postulat beschreibt etwas, das nicht beweisbar ist und doch als unabdingbares Fundament für weitere Theorien gebraucht wird.
""
==Postulat:==
//„Für ein Analysegebiet lässt sich eine repräsentative Stichprobe finden. Jedes Element der Grundgesamtheit muss gleiche Chancen haben, in die Stichprobe aufgenommen zu werden.“//
Bild
Erklärung
==Postulat:==
//"Ein komplexes Muster lässt sich in einfachere Bestandteile zerlegen, die untereinander in strukturellen Beziehungen stehen."
//
Bild
Erklärung
==Postulat:==
//„Komplexe Muster lassen sich meist durch relativ wenige einfachere Bestandteile darstellen. Eine beliebige Auswahl dieser führt nicht zu Mustern.“//
Bild
Erklärung
====Die Vorverarbeitung====
====Die Extraktion und Verarbeitung der Merkmale====
====Die Nächste-Nachbarn Klassifikation "NN" und ihre Erweiterung "k-NN"====
