Aus dem Stand der Technik sind verschiedene Clusteringverfahren zur Zuordnung einer Datei zu einem Cluster einer vorgegebenen Clustermenge bekannt. Eine wichtige Anwendung solcher Clusteringverfahren ist die Kategorisierung von Dokumenten, das heißt die Zuordnung von Dokumenten zu vordefinierten Clustern, die in diesem Fall auch als Kategorien bezeichnet werden.

Den bekannten Clusteringverfahren gemeinsam ist die Unterscheidung zwischen einer Trainings- und einer Clustering-bzw. Kategorisierungsphase. Die Trainingsphase dient dazu, die Schemata zu definieren, die die Grundlage für die anschließende Kategorisierung darstellen. Diese durch Training gewonnenen Schemata werden beispielsweise in Form von Parameterwerten gespeichert.

Gängige Clusteringverfahren, die für die Zwecke der Kategorisierung verwendet werden, sind Zentroidvektorverfahren und Entscheidungsbaumverfahren.

Die Zentroidvektorverfahren bauen während der Trainingsphase einen Vektor aus den signifi- kantesten Wörtern der Trainingsdokumente pro Kategorie auf, die gleichzeitig am distinktivsten zu den Wörtern der anderen Kategorien sind. Während der Phase der Kategorisierung wird dann das Vokabular des Dokuments mit den Vektoren der jeweiligen Kategorien verglichen.

Entscheidungsbaumverfahren überführen die Trainingsdokumente auf Basis Wahr-Falsch-Fragen bezüglich des Themas in binäre Baumstrukturen. Ein solcher binärer Baum repräsentiert eine Struktur von Ja-Nein-Fragen, wobei jedes Dokument entweder zugehörig oder nicht zugehörig zur Kategorie zugeordnet wird. Dann wird in der Phase der Kategorisierung das zu klassifizierende Dokument mit diesem Entscheidungsbaum verglichen.

Ein weiteres Verfahren zur Aufteilung einer Menge von Daten in eine gegebene Anzahl von Clustern ist das k-Means Verfahren (vgl. Hartigan, J. A. ; Wong, M. A. (1979), A K-Means Clustering Algorithm. Applied Statistics 28 und I. S. Dhillon and D. S. Modha. Concept decompositions for large sparse text data using clustering. Machine Learning, 42 (1) : 143-175, Januar 2001) Ein verbesserter k-Means Algorithmus zur Kategorisierung von Dokumenten ist aus"Iterative clustering of high dimensional text data augmented by local search", Data Mining, 2002.

Proceedings. 2002 IEEE International Conference, Dhillon, I. S. ; Yuqiang Guan ; Kogan, J., Seiten 131-138 bekannt.

Ferner werden für das Clustering auch trainierte neuronale Netze verwendet. Eine entsprechende Software für die assoziative Suche ist kommerziell erhältlich von SER Systems AG, SER brainware (www. ser. de). Dieses Programm ermöglicht die assoziative Suche auf der Basis von beispielhaften Textpassagen. Die assoziative Suche bedient sich dabei eines zuvor in einem Klassifikationsmodus trainierten neuronalen Netzes. Der dabei verwendete Lernprozess wird auch als"Learning by Example"bezeichnet.

Der Erfindung liegt dem gegenüber die Aufgabe zu Grunde, ein verbessertes Clusteringverfahren zur Zuordnung einer Datei zu einem Cluster aus einer vorgegebenen Clustermenge zu schaffen sowie ein entsprechendes digitales Speichermedium und ein Computersystem.

Die der Erfindung zu Grunde liegenden Aufgaben werden jeweils mit den Merkmalen der unabhängigen Patentansprüche gelöst. Bevorzugte Ausführungsformen der Erfindung sind in den abhängigen Patentansprüchen angegeben.

Erfindungsgemäß werden zur Zuordnung einer Datei zu einem Cluster aus einer vorgegebenen Clustermenge zumindest drei verschiedene Clusteringverfahren eingesetzt. Die einzelnen Clusteringverfahren sind zuvor in einer Trainingsphase mit gleichen oder unterschiedlichen Beispieldateien, die Clustern der vorgegebenen Clustermenge zugeordnet sind, trainiert worden.

Zur nachfolgenden Kategorisierung einer Datei wird diese mittels der verschiedenen Clustering- verfahren jeweils einem Cluster der Clustermenge zugeordnet. Dabei kann es vorkommen, dass die verschiedenen Clusteringverfahren zu unterschiedlichen Ergebnissen kommen. Erfindungsgemäß wird aus den einzelnen Ergebnissen der verschiedenen Clusteringverfahren der wahrscheinlich zutreffendste Cluster durch ein sogenanntes Voting-Verfahren ausgewählt.

Voting-Verfahren sind an sich auf dem Gebiet der fehlertoleranten Steuerungs-und Regelungs- systeme bekannt ("Fehlertolerante Steuerungs-und Regelungssysteme", Hubert Kirrmann und Karl-Erwin Großpietsch, Automatisierungstechnik 50,2002). Solche Voting-Verfahren werden im Stand der Technik durch Majoritätsschaltungen realisiert, beispielsweise für Leitstellen in Kraft- werken, Netzleittechnik, Automatisierungstechnik, Eisenbahn-Signalisierung und Flugzeug- elektronik. Der Erfindung liegt die Erkenntnis zugrunde, dass solche Voting-Verfahren auch für das Clustering und insbesondere für die Kategorisierung von Dokumenten einsetzbar sind.

Wenn beispielsweise drei verschiedene Clusteringverfahren zur Kategorisierung desselben Doku- ments verwendet werden, kann es vorkommen, dass eines der Clusteringverfahren zu einem anderen Ergebnis kommt, als die anderen beiden Clusteringverfahren. In diesem Fall wird durch das Voting-Verfahren eine Majoritätsentscheidung getroffen, das heißt es wird derjenige Cluster als der wahrscheinlich zutreffendste Cluster bestimmt, der von der Mehrheit der Clusteringverfahren übereinstimmend ermittelt worden ist. In dem betrachteten Beispielsfall wird also das Clustering-

verfahren mit dem von den beiden anderen Clusteringverfahren abweichenden Ergebnis "überstimmt".

Diese Vorgehensweise ist für eine zuverlässige Clustering von Dateien von besonderem Vorteil, da die aus dem Stand der Technik bekannten Clusteringverfahren je für sich nicht hinreichend zuver- lässig arbeiten.

Nach einer bevorzugten Ausführungsform der Erfindung sind die vorgegebenen Cluster der Clustermenge als hierarchischer Baum strukturiert. Vorzugsweise handelt es sich dabei um einen binären Baum, bei dem von jedem Knoten des Baums, mit Ausnahme der Blattknoten, zwei Zweige ausgehen. Jeder Knoten der Baumstruktur repräsentiert dabei einen der Cluster. Im weiteren werden die Bezeichnungen"Knoten"und"Cluster"synonym verwendet.

Jedes der Clusteringverfahren wird in der Trainingsphase für jeden der Knoten der Baumstruktur separat mit entsprechenden Trainingsdokumenten trainiert. Die Trainingsdokumente für einen bestimmten Knoten der Baumstruktur sind dabei den Clustern der nächst tieferen Baumebene zuge- ordnet, mit denen der betreffende Knoten verbunden ist. Das Clustering verläuft hier also schrittweise entlang einem Pfad innerhalb der Baumstruktur. Aufgrund dieser schrittweisen Vorgehensweise lässt sich eine besonders hohe Qualität und Sicherheit einer zutreffenden Kategorisierung einer Datei oder eines Dokuments erreichen.

Im weiteren werden bevorzugte Ausführungsbeispiele der Erfindung mit Bezugnahme auf die Zeichnungen erläutert. Es zeigen : Figur 1 ein Blockdiagramm eines Computersystems mit mehreren Clusteringmodulen, Figur 2 ein Flussdiagramm eines Clusteringverfahrens mit einem Voting-Schritt, Figur. 3 ein Blockdiagramm eines Computersystems mit einer Steuerung zur schrittweisen Clustering entlang eines Pfads in einer Baumstruktur, Figur 4 eine hierarchische Baumstruktur mit Trainingsdokumenten für jeden Knoten, Figur 5 ein Flussdiagramm eines Clusteringverfahrens zur schrittweisen Clustering entlang eines Pfads der Baumstruktur.

Figur 1 zeigt ein Computersystem 100 mit einem Clusteringmodul 102. Das Clusteringmodul 102 hat eine Anzahl von n Clusteringprogrammen k, wobei 1 < k < n. Die Clusteringprogramme 1 bis n können dabei auf unterschiedlichen Clusteringverfahren beruhen, wie zum Beispiel Zentroidvektor- verfahren, Entscheidungsbaumverfahren, K-Means-Verfahren, neuronale Netze oder andere Verfahren, die eine Datei einem Cluster aus einer vorgegebenen Clustermenge zuordnen können.

Die Clusteringprogramme 1 bis n sind mit einem Voting-Modul 104 verknüpft, welches beispiels- weise zur Bildung einer Majoritätsentscheidung basierend auf den einzelnen Clusteringergebnissen der Clusteringprogramme 1 bis n ausgebildet ist.

Das Computersystem 100 hat ferner einen Speicher 106 zur Speicherung von Parametersätzen Pl, P2,. .. für die entsprechenden Clusteringprogramme 1, 2,. ... Ferner hat das Computersystem 100 ein Steuerungsprogramm 108 sowie eine Eingabe 110 und eine Ausgabe 112. Die Ausgabe 112 ist in dem hier betrachteten Beispiel mit einer Datenbank 114 verknüpft.

Die Parametersätze für die verschiedenen Clusteringprogramme werden in einer Trainingsphase gewonnen. Hierzu werden, die einzelnen Clusteringprogramme mit kategorisierten Beispiel- dokumenten trainiert, wie es an sich aus dem Stand der Technik bekannt ist.

Beim Betrieb des Computersystems 100 wird über die Eingabe 110 ein Dokument in das Clusteringmodul 102 eingegeben. Daraufhin wird das Dokument von jedem der Clustering- programme 1 bis n nach den jeweiligen Clusteringverfahren zu einem Cluster der Clustermenge zugeordnet. Hierzu greifen die einzelnen Clusteringprogramme auf ihre jeweiligen Parametersätze des Speichers 106 zu.

Die jeweiligen Ergebnisse der Clusterings werden von den einzelnen Clusteringsprogrammen 1 bis n an das Voting-Modul 104 ausgegeben. Dieses bestimmt aus den einzelnen Clusteringser- gebnissen, die voneinander verschieden sein können, durch eine Majoritätsentscheidung den wahrscheinlich zutreffendsten der Cluster. Dieser wahrscheinlich zutreffendste Cluster wird über die Ausgabe 112 ausgegeben. Die Clusterzugehörigkeit des Dokuments 110 kann in der Datenbank 114 abgespeichert werden.

Die Figur 2 zeigt ein entsprechendes Flussdiagramm. In dem Schritt 200 wird ein Dokument ein- gegeben. Daraufhin werden parallel und unabhängig voneinander in den Schritten 202,204 und 206 die Clusteringverfahren 1, 2 und 3 durchgeführt, die jeweils auf unterschiedlichen Clustering- algorithmen beruhen können. Die jeweiligen Clusteringergebnisse, das heißt die jeweilige Zuord- nung des Dokuments zu einem der Cluster der vorgegebenen Clustermenge wird in einem Voting- Verfahren in dem Schritt 208 bewertet, das heißt es wird aus den einzelnen Clusteringergebnissen der Schritte 202, 204 und 206 durch eine Majoritätsentscheidung der wahrscheinlich zutreffendste Cluster ermittelt. Dieser wahrscheinlich zutreffendste Cluster wird in dem Schritt 210 ausgegeben.

Die Figur 3 zeigt ein Blockdiagramm eines Computersystems 300. Elemente der Figur 3, die Elementen der Figur 1 entsprechen, sind mit um 200 erhöhten Bezugszeichen gekennzeichnet. Im Unterschied zu der Ausführungsform der Figur 1 ist die vorgegebene Clustermenge in der Aus- führungsform der Figur 3 als Baumstruktur ausgeführt.

Jeder Knoten der Baumstruktur ist dabei genau einem Cluster zugeordnet. Das Clustering wird dabei beginnend von der Baumwurzel entlang eines Pfades bis zu einem Blatt der Baumstruktur schrittweise durchgeführt. Hierzu sind in dem Speicher 306 für jedes der Clusteringprogramme 1 bis n Parametersätze gespeichert und zwar für jeden der Knoten der Baumstruktur, mit Ausnahme der Blattknoten.

Diese Parametersätze werden durch Training der verschiedenen Clusteringprogramme mit Beispiel- dokumenten, die spezifisch für jeden der Knoten sind, gewonnen. Dies wird weiter unten mit Bezugnahme auf die Figur 4 noch näher erläutert.

Zur Realisierung der schrittweisen Clustering entlang eines Pfades in der Baumstruktur ist das Steuerungsprogramm 308 mit dem Voting-Modul 304 verbunden. Das Steuerungsprogramm 308 empfängt also von dem Voting-Modul 304 das Ergebnis von dessen Majoritätsentscheidung.

Im Betrieb des Computersystems 300 wird über die Eingabe 310 wiederum ein Dokument in das Clusteringmodul 302 eingegeben. Daraufhin wird ein erster Clusteringschritt ausgeführt, um aus- gehend von der Wurzel der Baumstruktur den wahrscheinlich zutreffendsten Cluster auf der nächsten Ebene der Baumstruktur zu finden. Dies erfolgt so, dass die Steuerung die für die Baum- wurzel spezifischen Parametersätze der verschiedenen Clusteringprogramme 1 bis n aus dem Speicher 306 abruft und in die entsprechenden Clusteringprogramme 1 bis n eingibt, die auf dieser Grundlage das Clustering durchführen.

Das Voting-Modul 304 wertet die einzelnen Clusterzuordnungen der Clusteringprogramme 1 bis n mittels einer Majoritätsentscheidung aus, und gibt das Ergebnis, das heißt den wahrscheinlich zu- treffendsten Cluster der nächsten Ebene der Baumstruktur, an die Steuerung 308 aus. Die Steuerung 308 ruft dann wiederum die für diesen wahrscheinlich zutreffendsten Cluster spezi- fischen Parametersätze der verschiedenen Clusteringsprogramme 1 bis n aus dem Speicher 306 ab und gibt diese in die Clusteringprogramme 1 bis n ein.

Diese führen daraufhin jeweils einen weiteren Clusteringschritt für das Dokument aus, um den Cluster auf der nächsten Ebene der Baumstruktur zu ermitteln. Die einzelnen Zuordnungsergeb- nisse der Clusteringprogramme 1 bis n werden wiederum in das Voting-Modul 304 eingegeben, welches eine Majoritätsentscheidung trifft, und diese an die Steuerung 308 ausgibt. Auf dieser Grundlage ruft die Steuerung 308 wiederum die für den wahrscheinlich zutreffendsten Cluster der aktuellen Ebene spezifischen Parametersätze der Clusteringprogramme 1 bis n aus dem Speicher 306 ab, und gibt diese Parametersätze in die Clusteringprogramme 1 bis n ein, so dass ein weiterer Clusteringschritt erfolgen kann, usw.

Dieser Prozess läuft solange ab, bis die Steuerung 308 feststellt, dass ein Blatt der Baumstruktur erreicht worden ist. Der von dem Voting-Modul 304 ermittelte wahrscheinlich zutreffendste Cluster eines Blatts der Baumstruktur wird über die Ausgabe 312 ausgegeben. Die so ermittelte Clusterzugehörigkeit des Dokuments kann wiederum in der Datenbank 314 abgespeichert werden.

Ergänzend ist es auch möglich, dass die einzelnen Zwischenergebnisse des schrittweise ver- laufenden Clusteringverfahrens, das heißt die wahrscheinlich zutreffendsten Cluster der verschie- denen Ebenen der Baumstruktur, ebenfalls ausgegebenen werden.

Die Figur 4 zeigt ein Beispiel für eine Baumstruktur 400. In dem betrachteten Beispielsfall der Figur 4 handelt es sich um eine binäre Baumstruktur. Die Wurzel der Baumstruktur 400 repräsen- tiert einen Cluster Cl 1. Dieser befindet sich auf der Ebene 1 der Baumstruktur 400.

Auf der Ebene 2 der Baumstruktur 400 befinden sich zwei Knoten, die Cluster C21 und C22 repräsentieren. Mit diesen beiden Clustern ist der Cluster Cl 1 über entsprechende Zweige der Baumstruktur 400 verbunden.

Auf der darunter liegenden Ebene 3 befinden sich vier Knoten, die die Cluster C31, C32, C33 und C34 repräsentieren. Dabei gelangt man von dem Cluster C21 der Ebene 2 entweder zu den Clustern C31 oder C32 der Ebene 3 und von dem Cluster C22 der Ebene 2 zu dem Cluster C33 oder dem Cluster C34 der Ebene 3.

Entsprechend verhält es sich für weiter darunter liegende Ebenen i der Baumstruktur 400, die jeweils Cluster Cij repräsentieren.

Jedem der Knoten der Baumstruktur 400 sind Trainingsdaten 402,404, 406,408,... zugeordnet.

Beispielsweise sind die Trainingsdaten 402 dem Cluster C11 der Ebene 1 zugeordnet. Die Trainingsdaten 402 beinhalten Beispieldokumente, die entweder dem Cluster C21 oder dem Cluster C22 der darunter liegenden Ebene 2 zugeordnet sind. Mit Hilfe dieser Trainingsdaten 402 werden die Clusteringprogramme 1 bis n (vgl. Figur 3) jeweils trainiert, um für jedes der Clustering- programme einen für den Cluster Cl1 spezifischen Parametersatz zu erhalten, der in dem Speicher 306 (vgl. Figur 3) abgespeichert wird.

Entsprechend sind die Trainingsdaten 404 dem Cluster C21 zugeordnet und beinhalten Beispiel- dokumente, die den Clustern, auf die der Cluster C21 verweist, zugeordnet sind ; das heißt die Trainingsdaten 404 beinhalten Beispieldokumente, die entweder dem Cluster C31 oder dem Cluster C32 zugeordnet sind. Entsprechend verhält es sich für die weiteren Trainingsdaten 406 bis 408.

Mit Hilfe der Trainingsdaten 402,404, 406,408,... wird für jeden der Cluster der Baumstruktur 400 und für jedes der Clusteringprogramme 1 bis n ein spezifischer Parametersatz generiert, der in dem Speicher 306 (vgl. Figur 3) gespeichert wird.

Wenn ein Dokument in das Computersystem 300 der Figur 3 eingegeben wird, werden zunächst die Parametersätze der Clusteringprogramme 1 bis n, die für den Cluster C11 spezifisch sind, geladen. Das Clustering des Dokument hat daher entweder eine Zuordnung zu dem Cluster C21 oder zu dem Cluster C22 zur Folge. Wenn beispielsweise der Cluster C21 als der wahrscheinlich zutreffendste Cluster ermittelt worden ist, werden im nächsten Schritt die Parametersätze, die für den Cluster C21 spezifisch sind, geladen. Diese Parametersätze wurden aufgrund der Trainings- daten 404 jeweils für die Clusteringprogramme 1 bis n ermittelt.

In einem weiteren Clusteringschritt wird daraufhin das Dokument entweder dem Cluster C31 oder dem Cluster C32 der nächsten Ebene der Baumstruktur 400 zugeordnet. Dieser Prozess läuft solange ab, bis entlang eines Pfades der Baumstruktur 400 ein Blattknoten auf der untersten Ebene der Baumstruktur 400 erreicht worden ist. In dem Beispielsfall der Figur 4 könnte ein solcher Pfad wie folgt lauten : C11-C21-C31-C42-C54, wobei es sich bei C54 um einen Blattknoten auf der untersten Ebene 5 der Baumstruktur 400 handelt.

Die Figur 5 zeigt entsprechendes Flussdiagramm. In dem Schritt 500 wird ein zu klassifizierendes Dokument eingegeben. In dem Schritt 502 werden die Indizes i, j und k auf 1 gesetzt. In dem Schritt 504 werden die n Parametersätze P1 bis Pn der Clusteringprogramme 1 bis n, die spezifisch für den Knoten C11 sind, abgerufen.

Auf der Grundlage dieser spezifischen Parametersätze werden daraufhin in den Schritten 506,508, 510,.... die entsprechenden Clusteringverfahren mit Hilfe der Clusteringprogramme 1 bis n durch- geführt. Die entsprechenden Clusteringergebnisse werden in dem Schritt 512 durch ein Voting- Verfahren bewertet, um den wahrscheinlich zutreffendsten Cluster Csj der nächst darunter liegende Ebene in dem Schritt 514 zu ermitteln.

Von dort aus geht die Ablaufsteuerung zu dem Schritt 504 zurück, wo die für den in dem Schritt 514 ermittelten Cluster Cij ermittelten spezifischen Parametersätze der Clusteringprogramme 1 bis n abgerufen werden, um den wahrscheinlich zutreffendsten Cluster für die nächst darunter liegende Ebene der Baurnstruktur zu ermitteln. Dieses Verfahren läuft solange ab, bis ein Blatt der Baumstruktur erreicht ist.

Bezugszeichenliste 100 Computersystem 102 Clusteringmodul 104 Voting-Modul 106 Speicher 108 Steuerungsprogramm 110 Eingabe 112. Ausgabe 114 Datenbank 300 Computersystem 302 Clusteringmodul 304 Voting-Modul 306 Speicher 308 Steuerungsprogramm 310 Eingabe 312 Ausgabe 314 Datenbank 400 Baumstruktur 402 Trainingsdaten 404 Trainingsdaten 406 Trainingsdaten 408 Trainingsdaten