30.11.2005

Natürliche Objektklassifizierung durch sequentielles superparamagnetisches Clustering

In vielerlei Hinsicht ist das menschliche Gehirn dem Computer weit überlegen. Das Bilden von Gruppen aus vorgegebenen Objekten (sog. Clustering) ist eine der Stärken biologischer "Rechenmaschinen" und lässt sich mit Computern kaum automatisieren. Ein neuartiges Clusteringkonzept, entwickelt von der Stoop Group an der ETH/UNI Zürich, verspricht Abhilfe zu leisten.

Clustering und die Schwierigkeiten

Seit den 60er Jahren ist die Entwicklung von computergestützter Objektklassifizierung Gegenstand der AI Forschung (AI: artificial intelligence) und Neuroinformatik. Die Aufgabenstellung ist nicht trivial: Gegeben eine Menge von Datenpunkten, wie lassen sich diese sinnvoll in Gruppen unterteilen? Die Frage stellt sich uns täglich, ohne bewusst Notiz davon zu nehmen: Bei der Erkennung von Gegenständen beispielsweise gruppieren wir visuelle Reize der Netzhaut in Windeseile und praktisch immer fehlerfrei.

Für die Wirtschaft ist die Existenz guter Clusteringalgorithmen von nicht unterschätzbarem Wert: Umfrageauswertung, Marktsegmentierung, Wissensmanagement und viele der üblichen Optimierungskonzepte setzen Clustering voraus. Aufgrund Limitationen bestehender Algorithmen blieb dies aber meist Aufgabe des Menschen. In solchen abstrakten Clusteringaufgaben spielt uns der Verstand jedoch oft einen entscheidenden Streich. Wir tendieren dazu, unbekannte Daten nach vordefinierten Kriterien (Erfahrungswerte, "Gespür") zu gruppieren, anstatt unvoreingenommen zu sein.

Limitationen bestehender Techniken

Die Entwicklung unvoreingenommener Clustering-Algorithmen geniesst also grosses Interesse. Bisherige Versuche krankten hauptsächlich an zwei Punkten:

1. Um Gruppen aus Objekten bilden zu können, ist ein Mass für Zusammengehörigkeit oder Ähnlichkeit zweier Objekte erforderlich. Sobald mehr als eine Eigenschaft pro Objekt verglichen wird, stellt sich die Frage nach der Gewichtung. Ist es z.B. wichtiger, geometrische Figuren anhand ihrer Farbe oder ihrer Form zu gruppieren? Die Angabe solcher Ähnlichkeitspräferenzen bestimmt aber bereits das erwartete Aussehen der Gruppen und wird dadurch dem Anspruch, unvoreingenommen zu sein, nicht gerecht.
2. Anderer Natur ist die Frage nach der Natürlichkeit von Clustern. Es ist leicht verständlich, dass fürs Clustering ein Parameter existiert, der die Feinkörnigkeit der Gruppenbildung steuert. Beim Essen interessieren uns weniger einzelne Moleküle als deren Zusammenschluss zum Steak, während wir andrerseits -zum Glück- nicht Steak und Teller als dieselbe Gruppe auffassen. Bestehende Algorithmen schoben in Ermangelung eines natürlichen Masses für Cluster dem Menschen die Aufgabe der richtigen Wahl der Grobkörnigkeit zu. Beim Steak-Teller-Problem ist diese bewältigbar, aber nur, weil wir die Lösung bereits kennen. Bei allgemeinen Daten, wo keine Idee einer idealen Grobkörnigkeit existiert, wird dieselbe Aufgabe kaum lösbar. Tragischer ist jedoch, dass aufgrund eines fehlenden "Gespürs" für die Natürlichkeit von Clustern die Resultate der Algorithmen oft so falsch sind, dass auch bei optimaler Wahl der Grobkörnigkeit die Ergebnisse nicht zufriedenstellend sind.

Der Natur auf die Finger geschaut

Basierend auf der Physik von Ferromagneten gelang es der Stoop Group kürzlich, einen Algorithmus zu entwickeln, der den obigen Punkten Rechnung trägt. Das sog. sequentielle superparamagnetische Clustering umschifft das erste Problem durch die Einbeziehung der Umgebung der Datenpunkte in die Beurteilung von Ähnlichkeit. Sind z.B. die meisten geometrischen Objekte rötlicher Farbe, macht eine Aufteilung nach Form mehr Sinn, als eventuelle Nuancen in der roten Farbe aufzutrennen.

Tiefgreifender und völlig neu ist die Herangehensweise an die zweite Problematik. Der Algorithmus ist dank eines Masses für die Natürlichkeit von Clustern in der Lage, eine Gruppenhierarchie nach Natürlichkeit anstelle von Grobkörnigkeit zu bilden. Dabei werden untrennbare Gruppen sequentiell erkannt und vom weiteren Clusteringprozess ausgeschlossen, wodurch sich eine Zuordnung von Objekten zu falschen Gruppen fast vollständig verhindern lässt.

Im Sinne des obigen Beispiels werden Steak, Teller und Beilage als eigenständige, nicht weiter auftrennbare Cluster entdeckt, wodurch sich die Frage nach der richtigen Gröbkörnigkeit gänzlich erübrigt.

Somit ist auch die Anwendung auf unbekannte Daten ohne Zutun des Menschen möglich. Als Dreingabe wird selbst das Rauschen, also Daten, welche sich überhaupt nicht klassifizieren lassen, als solches erkannt.

Vielschichtige Anwendunggebiete

Die neuartige Technik ist bereits erfolgreich für die Klassifizierung von Molekülen anhand chemischer Eigenschaften verwendet worden. Dies erlaubt Pharmakonzernen, anstelle einer Unmenge unbekannter Substanzen gezielt einen Vertreter der gefundenen Molekülgruppen auf medikamentöse Wirkung zu testen.

Dank Erkennung des Datenrauschens sind auch erste Experimente im Bereich der Objekterkennung sehr überzeugend verlaufen. Zurzeit forscht die Gruppe mit Unterstützung eines japanischen Technologiekonzerns an der Anwendung zur Spracherkennung für den Einsatz in der Robotik.

Mit der Partnerschaft der Stoop Group und Vitus sollen die Clusteringkonzepte in Verbindung mit neuartigen Optimierungstechniken auf Neuland wie die Optimierung von Prozessen oder Projektportfolien, die Analyse von Geschäftsstrukturen oder das Wissensmanagement übertragen werden.
Von Interesse ist im Speziellen auch der Effekt des menschlichen Clusterings im Vergleich zu einem unvoreingenommenen, maschinellen Verfahren. Vorteil des letzteren ist schliesslich, dass unerwartete, bisher nicht erkannte Gruppen detektiert werden können, während selbige vom Menschen aufgrund der Voreingenommenheit unbewusst übersehen werden.

Referenzen:

Stoop Group Website
Clusteranalyse (Wikipedia)

zurück...