DE10134926A1 - Vorrichtung und Verfahren zum Erzeugen eines Klassifikators für das automatische Sortieren von Objekten - Google Patents

Abstract

Die Erfindung betrifft eine Vorrichtung zum Erzeugen eines Klassifikators für das automatische Sortieren von Objekten, die jeweils durch elektronische Attribute charakterisiert sind, insbesondere eines Klassifikators zum automatischen Sortieren von hergestellten Produkten in qualitätsgerechte Produkte und mangelhafte Produkte, mit einer Speichereinrichtung zum Speichern einer Menge elektronischer Trainingsdaten, die für Trainingsobjekte eine jeweilige elektronische Attributmenge umfaßt, und einer Prozessoreinrichtung zum Verarbeiten der elektronischen Trainingsdaten, wobei durch die Anzahl von Attributen in der jeweiligen elektronischen Attributmenge eine Dimension (d) bestimmt ist. Die Prozessoreinrichtung umfaßt Diskretisierungsmittel zum automatischen Diskretisieren eines über den reellen Zahlen (R·d·) definierten Funktionenraums (V) in Unterfunktionenräume (V¶N¶, N = 2, 3, ...) mit Hilfe einer Dünngitter-Technik beim Verarbeiten der elektronischen Trainingsdaten mit der Prozessoreinrichtung.

Description

Die Erfindung liegt auf dem Gebiet automatischer Systeme zum elektronischen Klassifizieren von Objekten, die durch elektronische Attribute charakterisiert sind.

Derartige Systeme werden beispielsweise in Verbindung mit der Herstellung von Produkten in großer Stückzahl genutzt. Im Verlauf der Produktion eines industriellen Massenprodukts werden mit Hilfe von Sensormitteln verschiedene elektronische Daten über die Eigenschaften der hergestellten Produkte automatisch erfaßt, um beispielsweise die Einhaltung bestimmter Qualitätskriterien zu überprüfen. Hierbei kann es sich zum Beispiel um die Abmessungen, das Gewicht, die Temperatur oder die Materialzusammensetzung des Produkts handeln. An­ hand der erfaßten elektronischen Daten sollen mangelhafte Produkte automatisch erkannt und aussortiert sowie anschließend manuell begutachtet werden. Hierbei werden zunächst histori­ sche Daten über hergestellte Produkte, d. h. über die bei vergangenen Herstellungsprozessen erzeugten Produkte, in einer Datenbank elektronisch gespeichert. über ein Datenbankzu­ griffsmittel einer Computereinrichtung werden die historischen Daten im Rahmen eines Klas­ sifikationsverfahrens einer Prozessoreinrichtung zugeführt, welche auf der Basis der histori­ schen Daten automatisch charakteristische Profile der beiden Qualitätsklassen "Produkt in Ordnung" und "Produkt mangelhaft" generiert und in einer Klassifikatordatei ablegt. Auf dieses Weise wird mittels maschinellen Lernens automatisch ein sogenannter Klassifikator gebildet.

Während des Produktionsprozesses zum Herstellen der zu prüfenden bzw. zu klassifizieren­ den Produkte werden dann die von den Sensoren gelieferten elektronischen Daten für jedes hergestellte Produkt im online-Klassifikationsmodus von einer online-Klassifikations­ einrichtung auf Grundlage der Klassifikatordatei bzw. des Klassifikators ausgewertet und das geprüfte Produkt automatisch einer der beiden Qualitätsklassen zugeordnet. Falls es sich um die Klasse "Produkt mangelhaft" handelt; wird das entsprechende Produkt aussortiert und zur manuellen Begutachtung geschickt.

Ein wesentliches Problem bei dem beispielhaft beschriebenen Klassifizieren besteht heute in der großen Anzahl der erfaßten historischen Daten. Im Zuge der umfassenden Vernetzung von computergesteuerten Produktionsanlagen oder anderen Computeranlagen über Inter- und Intranetze sowie der unternehmensweiten Zentralisierung von elektronischen Daten findet derzeit ein explosives Wachstum der elektronischen Datenbestände in den Unternehmen statt. Viele Datenbanken enthalten schon heute Millionen und Milliarden von Kunden- und/oder Produktdaten. Die Verarbeitung großer Datenbestände spielt daher nicht nur in Verbindung mit dem oben geschilderten Produktionsprozeß eine immer größere Rolle in allen Bereichen der Datenverarbeitung. Einerseits ist die aus historischen Daten, die in sehr großer Anzahl vorliegen, automatisch ableitbare Information hinsichtlich der Bildung des Klassifikators "wertvoller", da bei seiner automatischen Erzeugung eine große Anzahl historischer Daten verwendet wird, andererseits besteht das Problem, beim Auffinden des Klassifikators mit der Anzahl der historischen Daten hinsichtlich des zeitlichen Aufwands effizient umzugehen.

Bekannte Klassifikationsverfahren, wie sie beispielsweise in der Druckschrift US 5,640,492 beschrieben sind, basieren zumeist auf Entscheidungsbäumen oder Neuronalen Netzen. Ent­ scheidungsbäume erlauben zwar die automatische Klassifikation über großen elektronischen Datenmengen, weisen jedoch im allgemeinen eine niedrige Qualität der Klassifikation auf, da sie die Attribute der Daten getrennt und nicht multivariat behandeln.

Die besten herkömmlichen Klassifikationsverfahren, wie Backpropagation-Netze, "Radial Basis Functions" oder Support-Vektor-Maschinen lassen sich zumeist als Regularisierungs- Netzwerke formulieren. Regularisierungs-Netzwerke minimieren ein Fehlerfunktional, wel­ ches aus einer gewichteten Summe eines Näherungs-Fehlerterms sowie eines Glättungsope­ rators besteht. Die bekannten maschinellen Lernverfahren führen diese Minimierung über dem Raum der Datenpunkte, dessen Größe von der Anzahl der erfaßten historischen Daten abhängt, aus und sind daher nur für kleinere bis mittelgroße historische Datensätze geeignet.

Hierbei ist üblicherweise das folgende Klassifikations- bzw. Regressionsproblem zu lösen. Es existieren M Datenpunkte in einem d-dimensionalen Raum x_i, i = 1, . . ., M, x_i∈^d. Den Datenpunkten sind Funktionswerte zugeordnet: y_i, i = 1, . . ., M, y_i∈^d (Regression) bzw. y_i∈{-1; +1} (Klassifikation). Somit ergibt sich als Trainingsmenge S = {(x_i, y_i)∈^d ×} M|i=1. Es ist nun das folgende Regularisierungsproblem zu lösen:

wobei
C(x, y) ein Fehlerfunktional, z. B. C(x, y) = (x - y)²;
ϕ(f) ein Glättungsoperator, ϕ(f) = ∥Pf∥ 2|2, z. B. Pf = ∇f;
f eine Regressions-/Klassifikatorfunktion mit den nötigen Glattheitseigenschaf­ ten für den Operator P; und
λ ein Regularisierungsparameter sind.

Hierbei wird die Klassifkationsfunktion f gewöhnlich als gewichtete Summe von Ansatzfunk­ tionen ϕ_i über den Datenpunkten bestimmt:

Der bekannte Lösungsansatz führt im wesentlichen zu zwei Problemen: (i) Aufgrund des glo­ balen Charakters der Ansatzfunktionen ϕ_i und der Anzahl der Koeffizienten α_i (gleich der Anzahl M der Datenpunkte) ist die Lösung des Regressionsproblems sehr zeitaufwendig und mitunter für größere Datenmengen unmöglich, da sie die Nutzung von Matrizen der Größe M × M erfordert; (ii) die Anwendung der Klassifikatorfunktion f_c auf neue Datensätze im Rahmen der online-Klassifikation ist sehr zeitaufwendig, da über alle Funktionen ϕ_i(i = 1, . . ., M) zu summieren ist.

Aufgabe der Erfindung ist es, eine Möglichkeit zur Nutzung automatischer Systeme zum elektronischen Klassifizieren von Objekten, die durch elektronische Attribute charakterisiert sind, auch für Anwendungsfälle zu schaffen, bei denen eine sehr große Anzahl von Daten­ punkten vorliegt.

Die Aufgabe wird erfindungsgemäß durch die unabhängigen Ansprüche gelöst.

Ein wesentlicher Gedanke, welcher von der Erfindung umfaßt ist, besteht in der Anwendung der Dünngitter-Technik. Dazu wird die Funktion f nicht gemäß dem Ansatz aus (3) erzeugt, sondern eine Diskretisierung des Raumes V vorgenommen, wobei V_N∈V ein endlich­ dimensionaler Unterraum von V und N die Dimension des Unterraums V_N ist. Die Funktion f wird bestimmt als

Sodann ist das Regularisierungsproblem im Raum V_N zur Bestimmung von f_N:

wobei C(x, y) = (x - y)² und ϕ(f) = ∥Pf∥ 2|2 ist.

Im Gegensatz zu herkömmlichen Verfahren wird als Unterraum V_N der Raum der Dünnen Gitter gewählt. Hierdurch werden die Probleme des Standes der Technik vermieden. Die Anzahl N der zu bestimmenden Koeffizienten α_i hängt nur von der Diskretisierung des Rau­ mes V ab. Der Aufwand zur Lösung von (5) skaliert linear mit der Anzahl M der Datenpunk­ te. Daher ist das Verfahren für nahezu beliebig große Datenmengen anwendbar. Die Klassi­ fikationsfunktion f_N ist nur aus N Ansatzfunktionen aufgebaut und ist daher schnell in der Anwendung auswertbar.

Der wesentliche Vorteil, welcher sich mit der Erfindung gegenüber dem Stand der Technik ergibt, besteht darin, daß der Aufwand zur Erzeugung des Klassifikators nur linear mit der Anzahl der Datenpunkte skaliert und damit der Klassifikator für nahezu beliebig große elek­ tronische Datenmengen erzeugt werden kann. Ein weiterer Vorteil besteht in der höheren Geschwindigkeit der Anwendung des Klassifikators auf neue Datensätze, d. h. in der schnelle­ ren online-Klassifikation.

Das Dünngitter-Klassifikationsverfahren kann auch zur Bewertung von Kunden-, Finanz- und Firmendaten eingesetzt werden.

Vorteilhafte Weiterbildungen der Erfindung sind in den abhängigen Unteransprüchen offen­ bart.

Die Erfindung wird im folgenden anhand von Ausführungsbeispielen unter Bezugnahme auf eine Zeichnung näher erläutert. Hierbei zeigen:

Fig. 1 ein schematisches Blockdiagramm einer Vorrichtung zum automatischen Erzeugen eines Klassifikators bzw. zur online-Klassifikation;

Fig. 2 ein schematisches Blockdiagramm zur Erläuterung eines Verfahrens zum automatischen Erzeugen eines Klassifikators mittels Dünngitter-Techno­ logie;

Fig. 3 ein schematisches Blockdiagramm zur Erläuterung eines Verfahrens zum automatischen Anwenden einer online-Klassifikation;

Fig. 4A und 4B eine Darstellung eines zweidimensionalen bzw. eines dreidimensionalen Dünnen Gitters (Level n = 5);

Fig. 5 die Kombinationstechnik für Level 4 in 2 Dimensionen; und

Fig. 6A und 6B ein Spiraldatensatz mit Dünnen Gittern für Level 6 bzw. Level 8.

Im folgenden wird das Dünngitter-Klassifikationsverfahrens detailliert beschrieben.

Hierbei wird zunächst eine beliebige Diskretisierung V_N des Funktionenraumes V betrachtet, die auf das Regularisierungsproblem (5) führt. Das Einsetzen der Ansatzfunktion (4) in die Regularisierungsformulierung (5) ergibt

Differentiation nach a_k, k = 1, . . ., N, ergibt

Dies ist äquivalent zu (k = 1, . . ., N)

In Matrix-Notation entspricht dies dem linearen System

(λC + B.B^T) α = By. (9)

Hier ist C eine quadratische N × N Matrix mit Einträgen C_j,k = M.(Pϕ_i, Pϕ_k)_L2, j, k = 1, . . . N, und B ist eine rechteckige N × M Matrix mit Einträgen B_i,j = ϕ_j(x_i), i = 1, . . . M, j = 1, . . ., N. Der Vektor y enthält die Daten y_i und hat die Länge M. Der unbekannte Vektor a enthält die Freiheitsgrade α_j und hat die Länge N.

Abhängig vom Regularisierungsoperator werden verschiedene Minimierungsprobleme im d-dimensionalen Raum erhalten. Wenn beispielsweise der Gradient P = ∇ im Regularisie­ rungsausdruck in (2) verwendet wird, erhält man ein Poisson-Problem mit einem zusätzlichen Term, der dem Interpolationsproblem entspricht. Die natürlichen Randbedingungen für solch eine Differentialgleichung in beispielsweise Ω = [0,1]^d sind Neumann-Bedingungen. Die Diskretisierung (4) ergibt nun das lineare Gleichungssystem (9), wobei C einer diskreten Laplace-Matrix entspricht. Um den Klassifikator f_N zu erhalten, muß dieses System nun gelöst werden.

Die bisherige Darstellung war nicht spezifisch darin, welcher endlich-dimensionale Teilraum V_N und welcher Typ von Basisfunktionen {ϕ_i} N|j=1 benutzt werden soll. Im Gegensatz zu ge­ wöhnlichen Data-Mining-Zugängen, die mit Ansatzfunktionen arbeiten, welche Datenpunkten zugeordnet sind, wird nun ein bestimmtes Gitter im Merkmalsraum benutzt, um den Klassifi­ kator mit Hilfe dieser Gitterpunkte zu bestimmen. Dies ist ähnlich zu der numerischen Be­ handlung von partiellen Differentialgleichungen. Aus Gründen der Einfachheit wird die wei­ tere Beschreibung auf deü Fall x_i ∈Ω = [0,1]^d eingeschränkt. Diese Situation läßt sich immer durch eine geeignete Reskalierung des Datenraums erreichen. Eine konventionelle Finite- Elemente-Diskretisierung würde nun ein äquidistantes Gitter Ω_n verwenden mit Gitterweite h_n = 2^-n in jeder Koordinatenrichtung, wobei n die Verfeinerungstiefe, oder auch Verfeine­ rungslevel, ist. Im folgenden wird immer der Gradient P = ∇ im Regularisierungsausdruck in (2) benutzt. Bei j der Multi-Index (j_i, . . ., j_d)∈N^d. Eine Finite-Elemente-Methode mit stückweise d-linearen Ansatz- und Testfunktionen ϕ_n,j(x) auf dem Gitter Ω_n würde nun

ergeben und der Variationsansatz (6) - (9) würde zu dem diskreten Gleichungssystem

(λC_n + B_n.B T|n)α_n = B_ny (10)

der Größe (2ⁿ + 1)^d und Matrixeinträgen gemäß (9) führen. Es wird darauf hingewiesen, daß f_n im Raum

V_n: = span{ϕ_n,j, j_t = 0, . . ., 2ⁿ, t = 1, . . ., d}

lebt. Das diskrete Problem (10) könnte im Prinzip durch einen geeigneten Löser, wie die konjungierte Gradientenmethode, ein Multigrid-Verfahren oder ein anderes effizientes Iterati­ onsverfahren behandelt werden. Doch ist diese direkte Anwendung einer Finiten-Element- Diskretisierung und eines geeigneten linearen Lösers auf das entstehende Gleichungssystems nicht für d-dimensionales Probleme möglich, falls d größer als 4 ist. Die Zahl der Gitter­ punkte wäre von der Ordnung O(h -d|n) = O(2^nd) und im besten Fall, wenn eine effektive Technik wie die Mehrgittermethode benutzt wird, ist die Zahl der Operationen von der glei­ chen Ordnung. Es zeigt sich hier der "Fluch" der Dimensionalität: Die Komplexität des Pro­ blems wächst exponentiell mit d. Zumindest für d < 4 und einen vernünftigen Wert von n kann das entstehende lineare Gleichungssystem auch auf den größten heutigen parallelen Computern nicht mehr gespeichert und gelöst werden.

Um den "Fluch" der Dimension zu reduzieren wird deswegen mit einem Dünngitter-Ansatz vorgegangen: Bei l = (l₁, . . ., l_d) ein Multiindex. Das Problem wird diskretisiert und gelöst auf einer gewissen Sequenz von Gittern Ω_l mit uniformer Gitterweite h_t = 2^-l_t in der t-ten Koor­ dinatenrichtung. Diese Gitter können verschiedene Gitterweiten für verschiedene Koordina­ tenrichtungen besitzen. Hierzu werden die Ω_l, mit

l₁ + . . . + l_d = n + (d-1)-q, q = 0, . . ., d-1, l_t < 0 (11)

betrachtet.

Der Finite-Elemente-Ansatz mit stückweise d-linearen Testfunktionen

ergibt auf dem Gitter Ω_l

und der Variationsansatz (6) - (9) resultiert in dem diskreten Gleichungssystem

(λC_l + B_l.B T|1)α_l = B_ly (13)

mit den Matrizen

(C_l)_j,k = M.(∇ϕ_l,j, ∇ϕ_l,j) und (B_l)_l,j = ϕ_l,j(x_i),

j_t, k_t = 0, . . ., 2^l_t , t = 1, . . ., d, i = 1, . . ., M und dem unbekannten Vektor (α_l)_j, j_t = 0, . . ., 2^l_t , t = 1, . . ., d. Diese Probleme werden dann mit einer geeigneten Methode gelöst. Dazu wird das konjugierte Gradientenverfahren zusammen mit einem diagonalen Vorkonditionierer benutzt. Aber auch eine geeignete Mehrgittermethode mit teilweiser Semi-Vergröberung läßt sich anwenden. Die diskreten Lösungen f₁ sind in den Räumen

V_l: = span{ϕ_l,j, j_t = 0, . . ., 2^l_t , t = 1, . . ., d (14)

der stückweise d-linearen Funktionen auf dem Gitter Ω_l, enthalten.

Es wird darauf hingewiesen, daß all diese Probleme im Vergleich zu (10) nun substantiell in ihrer Größe reduziert sind. An Stelle eines Problems der Größe dim(V_n) = O(h -d|n) = O(2^nd) müssen wir O(dnd^-1) Probleme der Größe dim(V_t) O(h -d|n) = O(2ⁿ) behandeln. Weiterhin können diese Probleme unabhängig voneinander gelöst werden, was eine einfache Paralleli­ sierung ermöglicht (vgl. M. Griebel, THE COMBINATION TECHNIQUE FOR THE SPARSE GRID SOLUTION OF PDES ON MULTIPROCESSOR MACHINES, Parallel Processing Letters, 2, 1992, Seiten 61-70).

Schließlich werden die Ergebnisse f_l(x) = Σ_jα_l,jϕ_l,j(x)∈V_l der verschiedenen Gitter Ω_l wie folgt kombiniert:

Die resultierende Funktion f (c)|n lebt im Dünngitter-Raum

Der Dünngitter-Raum besitzt die Dimension dim(V (s)|n) O(h -1|n(log(h -1|n))d^-1). Er wird durch eine stückweise d-lineare hierarchische Tensorproduktbasis aufgespannt (vgl. H.-J. BUNGARTZ, DÜNNE GITTER UND DEREN ANWENDUNG BEI DER ADAPTIVEN LÖSUNG DER DREIDIMENSIONALEN POISSON-GLEICHUNG, Dissertation, Institut für Informatik, Technische Universität München, 1992). Für den zweidimensionalen und dreidimensionalen Fall ist ein Dünnes Gitter in Fig. 4A bzw. 4B (Level 5) dargestellt. Fig. 5 zeigt die Gitter, die in der Kombinationsformel des Levels 4 im zweidimensionalen Fall benötigt werden. In Fig. 5 ist auch dargestellt, wie die Überlagerung der Punkte in der Se­ quenz der Gitter der Kombinationstechnik ein Dünnes Gitter vom entsprechenden Level n liefert.

Es wird darauf hingewiesen, daß die Summe über die diskreten Funktionen aus verschiedenen Räumen V_l in (15) die d-lineare Interpolation benötigt, die gerade der Transformation auf die Darstellung in die hierarchische Basis entspricht. Details sind in dem folgenden Dokument beschrieben: M. Griebel, M. Schneider, C. Zenger, A COMBINATION TECHNIQUE FOR THE SOLUTION OF SPARSE GRID PROBLEMS, Iterative Methods in Linear Algebra, P. de Groen and R. Beauwens, eds., IMACS, Elsevier, North Holland, 1992, Seiten 263-281. Im dargestellten Fall wird jedoch nie explizit die Funktion f (c)|n aufgestellt. Statt dessen wer­ den die Lösungen f_l auf den verschiedenen Gittern Ω_l gehalten, die in der Kombinations­ formel auftreten. Jede lineare Operation F über f (c)|n kann nun leicht mit Hilfe der Kombina­ tionsformel (15) ausgedrückt werden, wobei direkt auf den Funktionen f_n gearbeitet wird, d. h.

Wenn nun eine neu gegebene Menge von Datenpunkten {} (die Test- oder Evaluierungs­ daten) mit

ausgewertet werden soll, müssen nur die Kombination der zugehörigen Werte für f_l gemäß (15) gebildet werden. Die Evaluierung der verschiedenen f_l in den Testpunkten kann kom­ plett parallel erfolgen, ihr Summierung benötigt im wesentlichen eine All-Reduce Operation.

Für elliptische partielle Differentialgleichungen zweiter Ordnung wurde bewiesen, daß die Kombinationslösung f (c)|n nahezu so genau ist wie die Vollgitterlösung f_n, d. h. der Diskreti­ sierungsfehler erfüllt

unter der Voraussetzung einer geringfügig strengeren Glattheitsforderung an f im Vergleich zum Vollgitteransatz. Es wird benötigt, daß die Halbnorm

beschränkt ist. Weiterhin ist eine Reihenentwicklung des Fehlers notwendig. Ihre Existenz ist für PDE-Modelprobleme bekannt (vgl. H.-J. Bungartz, M. Griebel, D. Röschke, C. Zen­ ger, POINTWISE CONVERGENCE OF THE COMBINATION TECHNIQUE FOR THE LAPLACE EQUATION, East-West J. Numer. Math., 2, 1994, Seiten 21-45).

Die Kombinationstechnik ist nur eine von verschiedenen Methoden, um Probleme auf Dün­ nen Gittern zu lösen. Es wird darauf hingewiesen, daß auch Galerkin-, Finite-Eelemente-, Finite-Differenzen-, Finite-Volumen- und Kollokations-Zugänge existieren, die direkt mit der hierarchischen Produktbasis auf dem Dünnen Gitter arbeiten. Die Kombinationstechnik ist jedoch konzeptuell einfacher und leichter zu implementieren. Weiterhin erlaubt sie Standard- löser für ihre verschiedenen Teilprobleme wiederzuverwenden und sie ist in einfacher Weise parallelisierbar.

Bisher wurden lediglich d-lineare Basisfunktionen basierend auf einem Tensorprodukt-Ansatz erwähnt (vgl. J. Garcke, M. Griebel, M. Thess, DATA MINING WITH SPARSE GRIDS, SFB 256 Preprint 675, Institut für Angewandte Mathematik, Universität Bonn, 2000). Aber für die Gitter der Kombinationstechnik sind ebenso lineare Basisfunktionen basierend auf simplizialen Zerlegungen möglich. Hierzu wird die sogenannte Kubrische Triangulation ge­ nutzt (vg. H. W. Kuhn, SOME COMBINATORIAL LEMMAS IN TOPOLOGY, IBM j. Res. Develop., 1960, Seiten 518-524). Dieser Fall wurde beschrieben in J. Garcke und M. Griebel, DATA MINING WITH SPARSE GRIDS USING SIMPLIZIAL BASIS FUNCTIONS, KDD 2001 (akzeptiert), 2001.

Es können auch andere Ansatzfunktionen, zum Beispiel Funktionen höherer Ordnung oder Wavelets, als Basisfunktionen benutzt werden. Darüber hinaus können sowohl andere Regula­ risierungsoperatoren P als auch andere Kostenfunktionen C eingesetzt werden.

Im folgenden wird der Einsatz des Verfahrens am Beispiel der Qualitätssicherung im industri­ ellen Bereich beschrieben.

Im Verlauf der Produktion eines industriellen Massengegenstandes werden durch Sensoren verschiedene Daten über das Produkt automatisch erfaßt. Anhand dieser Daten sollen man­ gelhafte Produkte automatisch aussortiert und manuell begutachtet werden. Erfaßte Da­ ten/Attribute können beispielsweise sein: Abmaße des Produktes, Gewicht, Temperatur, und/oder Materialzusammensetzung.

Jedes Produkt wird durch mehrere Attribute charakterisiert und entspricht somit einem Daten­ satz x_i. Die Anzahl der Attribute bildet die Dimension d. Es existiert nun eine umfangreiche historische Produktdatenbank, in der alle Attribute (Meßwerte) der Produkte gemeinsam mit der Information über deren Qualitätsklasse ("in Ordnung", "mangelhaft") abgespeichert sind (y_i). Hierbei soll y_i = 1 die Qualitätsklasse "in Ordnung" und y_i = -1 die Qualitätsklas­ se "mangelhaft" bedeuten. Es soll nun aufgrund der Produktdatenbank ein Klassifikator f konstruiert werden, welcher im online-Betrieb für jedes neue Produkt anhand dessen Meß­ werten eine Prognose über dessen Qualitätsklasse erlaubt. Als "mangelhaft" klassifizierte Produkte werden automatisch zur manuellen Qualitätskontrolle aussortiert.

Es handelt sich hierbei um eine Klassifikationsaufgabe. Eine Vorrichtung 1 zur Erzeugung eines Klassifikators für die Qualität der Produkte ist in Fig. 1 schematisch dargestellt. Bevor ein Klassifikator erzeugt werden kann, müssen historische Daten vorliegen. Zu diesem Zweck werden die im Produktionsprozeß 10 anfallenden Daten mittels Meßsensoren 20 elek­ tronisch erfaßt. Dieser Prozeß kann unabhängig von dem automatischen Erzeugen des Klassi­ fikators zu einem früheren Zeitpunkt stattfinden. Die erfaßten Daten können noch mittels einer Signalverarbeitungsvorrichtung 30 dadurch vorverarbeitet werden, daß die Signale bei­ spielsweise normiert werden oder speziellen Transformationen, beispielsweise Fourier- oder Wavelet-Transformationen, unterzogen und möglicherweise geglättet werden. Danach wer­ den die Meßdaten vorzugsweise in Tabellenform mit den Produktattributen als Spalten und den Produkten als Zeilen abgelegt. Die Ablage der erfaßten/verarbeiteten (historischen) Da­ ten erfolgt in einer Datenbank oder einfach in einer Datei 40, so daß eine elektronische Trai­ ningsmenge vorliegt.

Mit Hilfe einer Zugriffsvorrichtung 50 werden die Daten der Produkttabelle von dem Prozes­ sor einer mit Speicher ausgerüsteten Recheneinheit 60, welche mit der Klassifikationssoft­ ware basierend auf der Dünngitter-Technik ausgestattet ist, eingelesen. Die Klassifikations­ software berechnet einen funktionalen Zusammenhang (Klassifikator) zwischen den Produk­ tattributen und der(den) Qualitätsklasse(n). Der Klassifikator 80 kann mittels der Ausgabe­ vorrichtung 70 grafisch visualisiert, zur online-Klassifikation versendet oder in einer Daten­ bank/Datei 90 abgespeichert werden, wobei im Fall einer Datenbank die Datenbank 90 mit der Datenbank 40 identisch sein kann.

Der Einsatz herkömmlicher Klassifikationsverfahren stößt beim automatischen Erzeugen des Klassifikators auf zwei Schwierigkeiten:

• a) Aufgrund der großen Anzahl von Produkten in der historischen Produktdatenbank (häu­ fig einige zehntausend bis einige Millionen) können klassische Klassifikationsverfahren nicht auf die gesamte Datenmenge angewendet werden. Daher kann der Klassifikator f_c nur auf einer kleinen Teilstichprobe, die zum Beispiel mit Hilfe eines Zufallsgene­ rators erzeugt wurde, konstruiert werden und ist qualitativ minderwertig.
• b) Der von herkömmlichen Verfahren konstruierte Klassifikator f_c ist zeitaufwendig in der online-Klassifikation, was im online-Einsatz zu Leistungsproblemen führt, insbe­ sondere zu zeitlichen Verzögerungen des zu optimierenden, industriellen Prozesses.

Die Anwendung des Dünngitter-Verfahrens löst beide Probleme. Der Ablauf einer Dünngit­ ter-Klassifikation ist in Fig. 2 schematisch dargestellt. Das Verfahren wird im folgenden anhand eines Beispiels erläutert. Zu Beginn der Klassifikation liegen die Produktattribute zusammen mit der Qualitätsklasse für alle Produkte der historischen Produktdatenbank als Trainingsdatensatz 110 vor. In einem folgenden Schritt 120 werden alle kategorischen Pro­ duktattribute, d. h. alle Attribute ohne definierte Metrik, wie z. B. die Produktfarbe, in numeri­ sche Attribute, d. h. Attribute mit Metrik, transformiert. Das kann beispielsweise durch Zu­ weisung einer Zahl für jede Attributausprägung oder Umwandlung in einen Satz von Binärat­ tributen geschehen. Danach werden alle Attribute mittels einer affin-linearen Abbildung auf den Wertebereich [0,1] transformiert, um sie numerisch vergleichbar zu machen.

Im Schritt 130 werden unter Anwendung des Kombinationsverfahrens der Dünngitter- Technik, für jedes der L Teilgitter des Kombinationsverfahrens die Steifigkeitsmatrix und der Lastvektor des diskretisierten Systems (13) assembliert. Hierbei wird das Diskretisierungs­ level n vom Nutzer so vorgegeben, daß eine ausreichende Komplexität der Klassifikatorfunk­ tion gewährleistet ist. Da die Anzahl L der Gleichungssysteme (13) sowie deren Dimension nur vom Diskretisierungslevel n (und der Anzahl der Attribute d), nicht aber von der Anzahl der Datenpunkte (Produkte) abhängt, können die Gleichungssysteme (13) auch für eine sehr große Anzahl von Produkten in kurzer Zeit aufgestellt (und gelöst) werden. Im Schritt 140 werden die resultierenden L Gleichungssysteme (13) für jedes Teilgitter des Kombinations­ verfahrens mittels Iterationsverfahren, im allgemeinen einem vorkonditionierten Verfahren der konjugierten Gradienten, gelöst. Die Koeffizienten α_l definieren die Teilklassifikator­ funktionen f₁ über den einzelnen Gittern, deren lineare Kombination den Gesamtklassifikator f (c)|n ergibt. Dieser liegt somit im Schritt 150 über die Koeffizienten α_l vor. Der Klassifi­ kator f (c)|n beschreibt den Zusammenhang zwischen den Meßwerten und der Qualitätsklasse der untersuchten Produkte. Je höher der Funktionswert der Klassifikatorfunktion, desto besser die Qualität des Produktes und je niedriger sein Wert, desto schlechter. Somit erlaubt der Klassifikator nicht nur die Zuordnung zu einer der beiden Qualitätsklassen "in Ordnung", "mangelhaft", sondern sogar eine abgestufte Sortierung bezüglich der Qualitätswahrschein­ lichkeit.

Im Zuge der online-Klassifikation werden die Daten des Produktionsprozesses mittels Meß­ sensoren erfaßt und mittels der Signalverarbeitungsvorrichtung vorverarbeitet (vgl. 10-30 in Fig. 1). Danach werden die Daten direkt an eine mit Prozessor und mit Speicher ausgerü­ stete Recheneinheit weitergeleitet, welche mit der Recheneinheit zur automatischen Erzeu­ gung des Klassifikators identisch oder eine hiervon verschiedene Recheneinheit sein kann und welche mit der online-Klassifikationssoftware basierend auf der Dünngitter-Technik ausge­ stattet ist. Zur Vereinfachung der Darstellung wird die Recheneinheit in Fig. 1 zur automati­ schen Erzeugung des Klassifikators und zur online-Klassifikation genutzt. Es kann jedoch auch vorgesehen sein, daß der Klassifikator mit einer Recheneinrichtung erzeugt wird und daß der erzeugte Klassifikator dann auf einer anderen Recheneinrichtung zur online-Klassifikation genutzt wird. Die zur online-Klassifikation genutzte Recheneinheit muß eine geeignete Schnittstelle (nicht dargestellt) zum Empfang der mit Hilfe der Meßsensoren erfaßten, elek­ tronischen Produkt-Attribute/Daten aufweisen.

Die im Rahmen der online-Klassifikation genutzte Recheneinheit erstellt auf Grundlage der gemessenen Produktattribute mit Hilfe des Dünngitter-Klassifikators unter Nutzung von Analysemitteln (nicht dargestellt) eine Prognose der Qualitätsklasse für das jeweilige Produkt und ordnet diese dem Produkt elektronisch zu, wobei die Qualitätsklasse mittels einer Ausga­ bevorrichtung visualisiert bzw. direkt zur Auslösung von Aktionen benutzt werden kann. Eine solche Aktion kann beispielsweise darin bestehen, daß ein als "mangelhaft" charakteri­ siertes Produkt _i(f (c)|n(_i)< 0) automatisch aussortiert und zur manuellen Begutachtung ge­ schickt wird. Darüber hinaus kann in Abhängigkeit des Grades der Mangelhaftigkeit (Wert von f (c)|n < 0), die Sortierung in verschiedene Kategorien erfolgen, welche wiederum ver­ schiedene Aktionen zur Untersuchung und Beseitigung des Mangels auslösen.

Die online-Klassifikation mittels Dünngitter-Verfahrens ist in Fig. 3 schematisch dargestellt. Jedes Produkt wird durch seine gemessenen und vorverarbeiteten Attribute charakterisiert und entspricht somit einem Datensatz _i. Die Anzahl der Attribute bildet wiederum die Dimensi­ on d. Zu Beginn der online-Klassifikation liegen somit die Produktattribute für alle zu klassi­ fizierenden Produkte als Evaluierungsdatensatz 160 vor. Hierbei beträgt die Anzahl der Eva­ luierungsdaten häufig nur = 1, wenn das im Produktionsprozeß vorliegende Produkt sofort klassifiziert werden soll. Zugleich wird der Klassifikator f (c)|n (über die Koeffizienten α_l aller L Teilgitter) aus dem Speicher oder aus einer Datenbank/Datei vom online- Klassifikationsprogramm eingelesen. Im Schritt 170 werden dann alle kategorischen in nu­ merische Attribute transformiert und danach eine (0,1)-Transformation aller Attribute vorge­ nommen. Dieser Schritt geschieht mit den gleichen Verfahren wie in Schritt 120. Danach werden im Schritt 180 die einzelnen Teilklassifikatoren f_l aller L Teilgitter auf die Evaluie­ rungsdaten angewendet. Die berechneten Funktionswerte werden schließlich im Schritt 190 für alle Teilgitter zusammengefaßt. Im Ergebnis liegt im Schritt 200 ein Vektor der progno­ stizierten Qualitätsklassen für alle Evaluierungsdaten vor, welcher zur oben beschrie­ benen Weiterverarbeitung genutzt werden kann. Da die Anzahl der Koeffizienten α_l sowie der Teilgitter L unabhängig von der Zahl der Trainingsdatensätze und somit relativ klein ist, erfolgt die online-Klassifikation sehr schnell, was die beschriebene Dünngitter-Klassifikation besonders geeignet für die Qualitätsüberwachung in der Massenproduktion macht.

Die Dünngitter-Klassifikation wurde am Beispiel der Klassifikation von Herstellungsproduk­ ten beschrieben. Für den Fachmann ergibt sich jedoch, daß die im Rahmen der online- Klassifikation verarbeiteten (klassifizierten) elektronischen Daten/Attribute beliebige Gegen­ stände oder Ereignisse charakterisieren können, so daß das Verfahren und die zur Ausführung genutzte Vorrichtung nicht auf den hier beschriebenen Anwendungsfall beschränkt sind. So ist das Dünngitter-Klassifikationsverfahren insbesondere auch zur automatischen Bewertung von Kunden-, Finanz- und Firmendaten nutzbar.

Das beschriebene Dünngitter-Klassifikationsverfahren ist aufgrund der erreichten Klassifika­ tionsgüte und der gegebenen Schnelligkeit jedoch für beliebige Anwendungen der Klassifika­ tion geeignet. Dieses wird im folgenden am Beispiel zweier Benchmarks gezeigt.

Das erste Beispiel ist ein Spiraldatensatz, welcher von A. Wieland von MITRE Corp. vorge­ schlagen wurde (vgl. E: Fahlmann, C. Lebiere, THE CASCADE-CORRELATION LEARNING ARCHITECTURE, Advances in Neural Information Processing Systems 2, Touretzky, ed., Morgan-Kaufmann, 1990). Der Datensatz ist in Fig. 6A dargestellt. Hierbei beschreiben 194 Datenpunkte zwei ineinander verwobene Spiralen, die Anzahl der Attribute d ist 2. Es ist bekannt, daß Neuronale Netze häufig Schwierigkeiten mit diesem Datensatz ha­ ben und einige Neuronale Netze nicht in der Lage sind, die beiden Spiralen zu trennen.

In den Fig. 6A und 6B ist das Resultat der Dünngitter-Kombinationsmethode für λ = 0.001 und n = 6 bzw. n = 8 dargestellt. Bereits mit Level 6 (vgl. Fig. 6A) können beide Spiralen korrekt getrennt werden. Hierbei werden lediglich 577 Dünngitter-Punkte benötigt. Für Level 8 (vgl. Fig. 6B) Dünngitter-Punkte wird die Form der beiden Spiralen glatter und übersichtlicher.

Zur Messung der Leistung des Dünngitter-Klassifikationsverfahrens wurde als zweites Bei­ spiel mit dem Datengenerator DatGen (vgl. G. Melli, DATGEN: A PROGRAM THAT CREATES STRUCTURED DATA. Website, http:/ / www.datasetgenerator.com), ein 10- dimensionaler Testdatensatz mit 5 Millionen Datenpunkten als Training- und 50000 Daten­ punkten als Evaluierungsdaten generiert. Der Aufruf lautete datgen -r1-XO/200,R,O:0/200,R,O:0/200,R,O:0/200,R,O:0/200,R,O:0/200,R,O:0/200,R,O:0/200,R,O:0/200,R,O:0/2 00,R,O:0/200,R,O:0/200,R,O-R2-C2/6-D2/7-T10/60-O5050000-p-e0.15.

Die Ergebnisse sind in Tabelle 1 dargestellt.

Die Messungen wurden auf einer Pentium III 700 MHz Maschine ausgeführt. Der höchste Speicherbedarf (für Level 2 mit 5 Millionen Datenpunkten) betrug 500 MByte. Der Wert des Regularisierungsparameters betrug λ = 0.01.

In der dritten und vierten Spalte von Tabelle 1 sind die Klasifikationsgüten auf der Trainings- und Testmenge (in Prozent) dargestellt. Die letzte Spalte enthält die Anzahl der Iterationen des Verfahrens der konjugierten Gradienten zur Lösung der Gleichungssysteme. Die Ergeb­ nisse sind in der untenstehenden Tabelle zu sehen. Die Gesamtrechenzeit skaliert etwa linear und ist selbst für diese riesigen Datensätze moderat.

Tabelle 1

Die in der vorstehenden Beschreibung, der Zeichnung und den Ansprüchen offenbarten Merkmale der Erfindung können sowohl einzeln als auch in beliebiger Kombination für die Verwirklichung der Erfindung in ihren verschiedenen Ausführungsformen von Bedeutung sein.

Claims (10)

1. Vorrichtung zum Erzeugen eines Klassifikators für das automatische Sortieren von Ob­ jekten, die jeweils durch elektronische Attribute charakterisiert sind, insbesondere eines Klassifikators zum automatischen Sortieren von hergestellten Produkten in qualitätsge­ rechte Produkte und mangelhafte Produkte, mit einer Speichereinrichtung zum Speichern einer Menge elektronischer Trainingsdaten, die für Trainingsobjekte eine jeweilige elek­ tronische Attributmenge umfaßt, und einer Prozessoreinrichtung zum Verarbeiten der elektronischen Trainingsdaten, wobei durch die Anzahl von Attributen in der jeweiligen elektronischen Attributmenge eine Dimension (d) bestimmt ist, dadurch gekennzeichnet, daß die Prozessoreinrichtung Diskretisierungsmittel zum automatischen Diskreti­ sieren eines über den reellen Zahlen () definierten Funktionenraums (V) in Unter­ funktionenräume (V_N, N = 2, 3, . . .) mit Hilfe einer Dünngitter-Technik beim Verarbeiten der elektronischen Trainingsdaten mit der Prozessoreinrichtung aufweist.

2. Vorrichtung nach Anspruch 1, dadurch gekennzeichnet, daß die Prozessorein­ richtung Evaluierungsmittel zum automatischen Bewerten des beim Verarbeiten der elektronischen Trainingsdaten erzeugten Klassifikators aufweist, um den Klassifikator auf ein Menge elektronischer Bewertungsdaten anzuwenden, so daß eine Güte des Klassi­ fikators bewertet werden kann.

3. Vorrichtung nach Anspruch 1 oder 2, gekennzeichnet durch Schnittstellenmittel zum Ankoppeln einer Eingabeeinrichtung für Benutzereingaben und/oder zum Ankop­ peln einer grafischen Ausgabeeinrichtung.

4. Verfahren zum Erzeugen eines Klassifikators für das automatische Sortieren von Objek­ ten, die jeweils durch elektronische Attribute charakterisiert sind, insbesondere eines Klassifikators zum automatischen Sortieren von hergestellten Produkten in qualitätsge­ rechte Produkte und mangelhafte Produkte, das Verfahren die folgenden Schritte aufwei­ send:
Übertragen einer Menge elektronischer Trainingsdaten, die für Trainingsobjekte eine jeweilige elektronische Attributmenge umfaßt, von einer Speichereinrichtung an eine Prozessoreinrichtung, wobei durch die Anzahl von Attributen in der jeweiligen elek­ tronischen Attributmenge eine Dimension (d) bestimmt ist;
1 Verarbeiten der elektronischen Trainingsdaten in der Prozessoreinrichtung, wobei ein über definierter Funktionenraum (V) mit Hilfe von Diskretisierungsmitteln unter Verwendung einer Dünngitter-Technik in Unterfunktionenräume (V_N, N = 2, 3, . . .) elektronisch diskretisiert wird;
Bilden des Klassifikators in Abhängigkeit von dem Verarbeiten der elektronischen Trainingsdaten in der Prozessoreinrichtung; und
elektronisches Speichern des gebildeten Klassifikators.

5. Verfahren nach Anspruch 4, dadurch gekennzeichnet, daß der gebildete Klassifi­ kator zum Bewerten einer Güte des Klassifikators auf eine Menge elektronischer Evaluie­ rungsdaten automatisch angewendet wird, um Güteparameter auszubilden, die für die Güte des Klassifikators indikativ sind.

6. Verfahren nach Anspruch 4 oder 5, dadurch gekennzeichnet, daß zum elektroni­ schen Diskretisieren des Funktionsraumes (V) ein Kombinationsverfahren der Dünngit­ ter-Technik angewendet wird.

7. Verwendung einer Vorrichtung nach einem der Ansprüche 1 bis 3 zum Ausführen eines Data-Mining-Verfahrens.

8. Verwendung eines Verfahrens nach einem der Ansprüche 4 bis 6 zum Ausführen eines Data-Mining-Verfahrens.

9. Vorrichtung zum Online-Sortieren von Objekten, die durch jeweilige elektronische Attri­ bute charakterisiert sind, insbesondere von hergestellten Produkten in qualitätsgerechte Produkte und mangelhafte Produkte, mit Hilfe eines unter Verwendung der Dünngitter- Technik erzeugten elektronischen Klassifikators, die Vorrichtung aufweisend:
Empfangsmittel zum Empfangen von charakteristischen Merkmalen für die zu sortie­ renden Objekte in Form elektronischer Attribute; und
eine Prozssoreinrichtung mit:
Analysemitteln zum Online-Analysieren der elektronischen Attribute mit Hilfe des Klassifikators; und
Zuordnungsmitteln zum elektronischen Zuordnen der zu sortierenden Objekte zu einer von mehreren Sortierklassen in Abhängigkeit von dem automatischen On­ line-Analysieren.

10. Verfahren zum Online-Sortieren von Objekten, die durch jeweilige elektronische Attri­ bute charakterisiert werden, insbesondere von hergestellten Produkten in qualitätsge­ rechte Produkte und mangelhafte Produkte, mittels eines unter Verwendung der Dünn­ gitter-Technik erzeugten elektronischen Klassifikators, das Verfahren die folgenden Schritte aufweisend:
Online-Erfassen von charakteristischen Merkmalen für die zu sortierenden Objekte in Form elektronischer Attribute;
automatisches Online-Analysieren der elektronischen Attribute unter Verwendung des Klassifikators mit Hilfe einer Prozessoreinrichtung; und
Zuordnen der zu sortierenden Objekte zu einer von mehreren Sortierklassen in Ab­ hängigkeit von dem automatischen Online-Analysieren.