Mustererkennung

Die Mustererkennung, ein Teilgebiet der Informatik, untersucht Verfahren, die gemessene Signale automatisch in Kategorien einordnen. Zentraler Punkt ist dabei das Erkennen von Mustern, den Merkmalen, die allen Dingen einer Kategorie gemeinsam sind und sie vom Inhalt anderer Kategorien unterscheiden. Mustererkennungsverfahren befähigen Computer, Maschinen und Roboter, statt präziser Eingaben auch die weniger exakten Eindrücke einer natürlichen Umgebung zu verarbeiten.

Typische Beispiele für die zahllosen Anwendungsgebiete sind Spracherkennung, Texterkennung und Gesichtserkennung, Dinge, die die menschliche Wahrnehmung andauernd und scheinbar mühelos erledigt. Die elementare Fähigkeit der Klassifizierung ist jedoch auch der Grundstein von Begriffsbildung und Abstraktion und damit letztlich von Intelligenz, so dass die Mustererkennung auch für allgemeinere Gebiete wie die Künstliche Intelligenz oder das Data-Mining von zentraler Bedeutung ist.

Erste systematische Untersuchungsansätze der Mustererkennung kamen Mitte der 1950er Jahre mit dem Wunsch auf, Postzustellungen maschinell statt von Hand zu sortieren. Im Laufe der Zeit kristallisierten sich mit syntaktischer, statistischer und struktureller Mustererkennung die drei heutigen Gruppen von Mustererkennungsverfahren heraus. Als Durchbrüche wurden die Nutzbarmachung von Support Vector Machines und künstlichen neuronalen Netzen in den späten 1980er Jahren empfunden. Obwohl viele der heutigen Standardverfahren schon sehr früh entdeckt wurden, wurden sie erst nach erheblichen methodischen Verfeinerungen und der generellen Leistungssteigerung handelsüblicher Computer alltagstauglich. Die Mustererkennung ist bis heute ein offenes Forschungsgebiet, das immer wieder neue, interessante Ideen hervorbringt.

Ansätze

Syntaktisch

Ziel der syntaktischen Mustererkennung ist es, Dinge so durch Folgen von Symbolen zu beschreiben, dass Objekte der gleichen Kategorie die selben Beschreibungen aufweisen. Möchte man etwa Äpfel von Bananen trennen, so könnte man Symbole für rot (R) und gelb (G) sowie für länglich (L) und kugelförmig (K) einführen; alle Äpfel würden dann durch die Symbolfolge RK und alle Bananen durch das Wort GL beschrieben. Das Problem der Mustererkennung stellt sich in diesem Fall als Suche nach einer formalen Grammatik dar, also nach einer Menge von Symbolen und Regeln zum Zusammenfügen derselben. Da für gewöhnlich eine klare Zuordnung zwischen Merkmal und Symbol nicht ohne weiteres möglich ist, kommen hier Methoden der Wahrscheinlichkeitsrechnung zum Einsatz, um die Zuordnung zu bestimmen. So kommen beispielsweise Farben in unzähligen Abstufungen vor, man muss sich jedoch zwingen, eine präzise Unterscheidung zwischen rot und gelb vorzunehmen. Bei komplexen Sachverhalten wird damit das eigentliche Problem nur hinausgezögert statt gelöst, weshalb dieser Ansatz nur noch wenig Beachtung findet und nur bei sehr klaren Aufgabenstellungen zum Einsatz kommt.

Statistisch

In diesen Bereich fällt das Gros der heutigen Standardmethoden, insbesondere auch die oben erwähnten Support Vector Machines und neuronalen Netze. Ziel ist es hier, zu einem Objekt die Wahrscheinlichkeit zu bestimmen, dass es zur einen oder anderen Kategorie gehört und es letztlich in die Kategorie mit der höchsten Wahrscheinlichkeit einzusortieren. Statt Merkmale nach vorgefertigten Regeln auszuwerten, werden sie hier einfach als Zahlenwerte gemessen und in einem sogenannten Mustervektor zusammengefasst. Eine mathematische Funktion ordnet dann jedem denkbaren Mustervektor eindeutig eine Kategorie zu. Die große Stärke dieser Vefahren liegt darin, dass sie auf nahezu alle Sachgebiete angewandt werden können und keine tiefergehende Kenntnis der Zusammenhänge vonnöten ist.

Strukturell

Die strukturelle Mustererkennung verbindet verschiedene syntaktische und/oder statistische Verfahren zu einem einzigen neuen Verfahren. Ein typisches Beispiel ist die Gesichtserkennung, bei der für verschiedene Gesichtsteile wie Auge und Nase unterschiedliche Klassifikationsverfahren eingesetzt werden, die jeweils nur aussagen, ob der gesuchte Körperteil vorliegt oder nicht. Übergeordnete strukturelle Verfahren wie etwa Bayessche Netze führen diese Einzelergebnisse zusammen und berechnen daraus das Gesamtergebnis, die Kategoriezugehörigkeit. Die grundlegende Merkmalserkennung wird dabei allgemeinen statistischen Verfahren überlassen, während übergeordnete Inferenzverfahren Spezialwissen über das Sachgebiet einbringen. Strukturelle Verfahren kommen besonders bei sehr komplexen Sachverhalten wie der Computer-assisted Detection, der computergestützten ärztlichen Diagnosestellung, zum Einsatz.

Teilschritte der Mustererkennung

Ein Mustererkennungsprozess lässt sich in mehrere Teilschritte zerlegen, bei denen am Anfang die Erfassung und am Ende eine ermittelte Klasseneinteilung steht. Bei der Erfassung werden Daten oder Signale mittels Sensoren aufgenommen und digitalisiert. Aus den meist analogen Signalen werden Muster gewonnen, die sich mathematisch in Vektoren und Matrizen darstellen lassen. Zur Datenreduktion und zur Verbesserung der Qualität findet eine Vorverarbeitung statt. Durch Extraktion von Merkmalen werden die Muster bei Merkmalsgewinnung anschließend in einen Merkmalsraum transformiert. Die Dimension des Merkmalsraums, in dem die Muster nun als Punkte repräsentiert sind, wird bei der Merkmalsreduktion auf die wesentlichen Merkmale beschränkt. Der abschließende Kernschritt ist die Klassifikation durch einen Klassifikator, der die Merkmale verschiedenen Klassen zuordnet. Das Klassifikationsverfahren kann auf einem Lernvorgang mit Hilfe einer Stichprobe basieren.

Erfassung

Siehe auch: Signalverarbeitung, Messung, Digitalisierung, Messtechnik, Datenerhebung

Vorverarbeitung

Um Muster besser erkennen zu können, findet in der Regel eine Vorverarbeitung statt. Die Entfernung bzw. Verringerung unerwünschter oder irrelevanter Signalbestandteile führt nicht zu einer Reduktion der zu verarbeitenden Daten, dies geschieht erst bei der Merkmalsgewinnung. Mögliche Verfahren der Vorverarbeitung sind unter Anderem die Signalmittelung, Anwendung eines Schwellwertes und Normierung. Gewünschte Ergebnisse der Vorverarbeitung sind die Verringerung von Rauschen und die Abbildung auf einen einheitlichen Wertebereich.

Merkmalsgewinnung

Nach der Verbesserung des Musters durch Vorverarbeitung lassen sich aus seinem Signal verschiedene Merkmale gewinnen. Dies geschieht in der Regel empirisch nach durch Intuition und Erfahrung gewonnenen Verfahren, da es wenige rein analytische Verfahren (z.B. die Automatische Merkmalsynthese) gibt. Welche Merkmale wesentlich sind, hängt von der jeweiligen Anwendung ab. Merkmale können aus Symbolen beziehungsweise Symbolketten bestehen oder mit statistischen Verfahren aus verschiedenen Skalenniveaus gewonnen werden. Bei den numerischen Verfahren unterscheidet man Verfahren im Originalbereich und Verfahren im Spektralbereich. Mögliche Merkmale sind beispielsweise

Mittels Transformationen wie der diskreten Fourier-Transformation (DFT) und diskreten Kosinustransformation (DCT) können die ursprünglichen Signalwerte in einen handlicheren Merkmalsraum gebracht werden. Die Grenzen zwischen Verfahren der Merkmalsgewinnung und Merkmalsreduktion sind fließend. Da es wünschenswert ist, möglichst wenige aber dafür umso aussagekräftigere Merkmale zu gewinnen, können Beziehungen wie die Kovarianz und der Korrelationskoeffizient zwischen mehreren Merkmalen berücksichtigt werden. Mit der Karhunen-Loève-Transformation (Hauptachsentransformation) lassen sich Merkmale dekorrelieren.

Merkmalsreduktion

Zur Reduktion der Merkmale auf die für die Klassifikation wesentlichen wird geprüft, welche Merkmale für die Klassentrennung relevant sind und welche weggelassen werden können. Verfahren der Merkmalsreduktion sind die Varianzanalyse, bei der geprüft wird, ob ein oder mehrere Merkmale Trennfähigkeit besitzen, und die Diskriminanzanalyse, bei der durch Kombination von elementaren Merkmalen eine möglichst geringe Zahl trennfähiger nichtelementarer Merkmale gebildet wird.

Klassifikation

Der letzte und wesentlichste Schritt der Mustererkennung ist die Klassifikation der Merkmale in Klassen. Dazu existieren verschiedene Klassifikationsverfahren (weiteres siehe dort).

Lebewesen benutzen zur Mustererkennung in den Signalen unserer Sinne meist Neuronale Netze. Diese Herangehensweise wird in der Bionik analysiert und imitiert. Die Neuroinformatik hat gezeigt, dass durch künstliche neuronale Netze Lernen und Erkennung komplexer Muster möglich sind, auch ohne dass vorher eine Regelabstraktion in oben gezeigter Art erfolgt.

Im Anschluss an die Klassifikation des Musters kann versucht werden, das Muster zu interpretieren. Dies ist Gegenstand der Musteranalyse. In der Bildverarbeitung kann auf die Klassifikation von Bildern eine sogenannte Bilderkennung folgen, also die bloße Erkennung von Objekten in einem Bild ohne Interpretation oder Analyse von Zusammenhängen zwischen diesen Objekten.

Siehe auch

Regressionsanalyse (Lineare Regression und Nichtlineare Regression), Bildverarbeitung, Bildverstehen, Rasteranalyse, Spracherkennung, Support-Vector-Maschine, Pattern Matching, Fuzzy-Suche, Neuigkeitsfilter, Hauptkomponentenanalyse, Clusteranalyse, Paarung (Graphentheorie)

Literatur

Richard O. Duda, Peter E. Hart, David G. Stork: Pattern classification. Wiley, New York 2001, ISBN 0471056693
J. Schuermann: Pattern Classification - A Unified View of Statistical and Neural Approaches. Wiley, New York 1996, ISBN 0471135348
K. Fukunaga: Statistical Pattern Recognition. Academic Press, New York 1991. ISBN 0122698517
H. Niemann: Klassifikation von Mustern. Springer, Berlin 1983 (online). ISBN 3-540-12642-2
Christopher M. Bishop: Pattern Recognition and Machine Learning. Springer, Berlin 2006, ISBN 0387310738

Weblinks