Einführung

Das starke Anwachsen der Datenmenge macht es notwendig, die Analyse der Daten und die Bestimmung der in ihnen enthaltenen Informationen mittels intelligenter Methoden zu automatisieren. Diese Anforderungen an die Informatik werden im Forschungsgebiet Data Mining, häufig auch bezeichnet als Knowledge Discovery in Databases (KDD), behandelt.

Data Mining & Knowledge Discovery

Eine viel zitierte Definition stammt von Piatetsky-Shapiro und Frawley (nach [FPM 91]):

• Die englische Lebensmittelkette "Safeway" fand mit Data Mining heraus, daß ein bestimmter Käse, der nur an Platz 209 der Verkaufsrangliste lag, hauptsächlich von ihren besten, umsatzstärksten Kunden gekauft wurde. Hätte das Unternehmen diesen umsatzmäßig unwichtigen Käse aus dem Sortiment genommen, hätte es damit seine beste Kundschaft verärgert. [CNC 97]
• Die Gemischtwarenkette "Walmart" in den USA wollte mehr über das Kaufverhalten ihrer Kunden wissen. Hierzu wurden die Daten über die Verkäufe, die mittels Barcodelesern erfaßt wurden, mit einer Knowledge Discovery Methode analysiert. Ergebnis: Wer Grußkarten kauft, so fand man heraus, kauft auch Kosmetika (kein Ergebnis, das von einem Werbepsychologen vorausgesagt worden wäre!). Walmart räumte die Läden um und stellte Grußkarten neben Kosmetika. Der Erfolg: dreißig Prozent Umsatzwachstum bei beiden Produktgruppen. [Klu 97]

Viele Datenbestände enthalten hingegen komplex strukturierte Daten, wie z.B. Datenobjekte in OODBSs, temporale und Transaktionsdaten, sowie Geodaten in Spatial DBSs bzw. Geographischen Informationssystemen. Gerade die Belange der Analyse von räumlichen Datenbeständen werden durch klassische Data Mining Verfahren nicht ausreichend unterstützt ([HKS 97], [Han 97]).

Spatial Data Mining

Ziel des räumlichen (Spatial) Data Mining ist die Gewinnung von implizit vorhandenen Kenntnissen, räumlichen Beziehungen oder anderen interessierenden Mustern in großen räumlichen Datenbeständen, die nicht explizit in Geodatenbanken gespeichert sind [KH 95]. Besonders interessant sind das Entdecken von Zusammenhängen zwischen Geo- und Sachdaten (nicht räumlichen Attributen), die Anfrageoptimierung und die Datenreorganisation in SDBMSs.

Erkenntnisse, die aus räumlichen Daten gewonnen werden, können sehr verschiedener Art sein, wie z.B. das Aufstellen charakteristischer Regeln, die Beschreibung von hervorstechenden Häufungen und Mustern, die Bestimmung räumlicher Verknüpfungen, etc.

Die bisherige Anwendungen von Data Mining auf räumliche Daten sind auf die klassischen Datentypen wie Punkte, Polygone, oder auch Regionen (siehe [Gue 94]) beschränkt. Die geographischen Objekte werden durch räumliche Datentypen sowie Beziehungen modelliert und zusammen mit den Sachinformationen im Mining-Algorithmus analysiert ([KAH 96], [Han 97], [EKS 97], [HKS 97]).

Beispiele verschiedener Zielrichtungen und Methoden sind:

• Beschreibung von allgemeinen Wettermustern gemäß einer vorgegebenen, hierarchisch geordneten räumlichen Aufteilung eines Gebiets sowie nachfolgend die Bestimmung der Unterschiede in den Mustern. [HKS 97]
• Ermittlung des Zusammenhangs zwischen Bevölkerungsverteilung und Arbeitslosenrate zur Bestimmung der Wirtschaftskraft einer Region und Erklärung der Abweichung vom theoretischen Erwartungswert. [EKS 97]
• Bestimmung der Korrelation zwischen Charakteristiken bestimmter Gebiete; z.B. kann so die Beziehung gefunden werden, das Gebiete mit einer hohen Rate von im Ruhestand lebenden Menschen häufig stark korrelieren mit der Nähe von Bergen und Flüssen. [EKS 97]

Topologisches Data Mining

Im folgenden wird das topologische, raumbezogene Data Mining stets eingebettet in einem räumlichen Kontext betrachtet und verkürzt als topologisches Data Mining bezeichnet. Zwei kurze Beispiele zum praktischen Einsatz von topologischem Data Mining:

• Im Bereich des Geo-Marketing ist es interessant festzustellen, welche Restpotentiale ein Versorgungsnetz besitzt, diese Netzbereiche (Teilnetze) in Bezug zum betroffenen Kundenklientel zu erklären und darauf aufbauend strategische Maßnahmen zu ergreifen, die zu einer höheren Auslastung des Netzes führt.
• In funkgestützten Telekommunikationsnetzen (Mobiltelefon) treten bei Schlechtwettergebieten wiederholt Versorgungslöcher im Übertragungsnetz auf. Der Netzbetreiber benötigt für einen störungsfreien Betrieb Informationen über den Zusammenhang dieser Löcher mit geographischen Gegebenheiten, der gewählten Versorgungsform oder dem Kundenverhalten.

• In einem EVU sind die Aufwendungen für die Instandhaltung von elektrischen Transportnetzen mit dem Ziel der Sicherung der Stromversorgung in einer Region sehr hoch. Hier bedarf es in Zukunft sehr hoher Reinvestitionen der Netze und Anlagen.

• Allgemeines Ziel von Versorgungsunternehmen ist die wirtschaftliche, ressourcenschonende und störungsfreie Versorgung der Kunden mit den jeweiligen Versorgungsgütern (z.B. Strom, Gas, Wärme, oder Wasser). Hierzu sind u.a. Erhaltungsaufwendungen im Bereich der Versorgungsnetze durchzuführen, die möglichst kostengünstig und effizient erfolgen sollten. Neben der Pflege und Wartung sind auch vollständige Erneuerungen von Netzeinbauten und Leitungen notwendig, mit dem Ziel evtl. zukünftige Störfälle zu vermeiden. Dies ist in den vergangenen Jahrzehnten eher unregelmäßig und weitgehend zufalls-/störungsbedingt geschehen. Eine wichtige Aufgabe ist die Bewertung von Netzabschnitten hinsichtlich deren Ausfallsicherheit und darausfolgend die Einleitung von entsprechenden Erneuerungsmaßnahmen zur Sicherung der Energie- und Wasserversorgung.

Zum Beispiel werden in Telekommunikationsnetzen von jeder Komponente Fehlerinformationen (Alarmmeldungen) an die Leitzentrale weitergeleitet, wobei das Operating auf verschiedene Fehlerzustände sofortige Maßnahmen zur Schadenbegrenzung oder -vermeidung einleiten muß. In [HKMRT 96] wird ein Data Mining Algorithmus beschrieben, mit dem die Alarmdaten auf Regelmäßigkeiten analysiert werden. Es werden z.B. Regeln der Art "Falls ein Alarmtyp A vor einem des Typs B, und C vor D auftritt (in einer bestimmten Zeitspanne), dann wird mit 80% Wahrscheinlichkeit die Fehlersituation vom Typ E auftreten".

Diese Information stellt einen wertvollen Erkenntnisgewinn für das Netzwerkmanagement dar. Ohne Data Mining kristallisieren sich derartige Zusammenhänge erst nach langjähriger Beschäftigung mit einer Thematik heraus (in vielen Fällen nur in Form von Erfahrungswerten). Im Operating eines Netzwerk, mit ständig wechselnden technischen Komponenten, ist die Zeitspanne sogar meist zu kurz, um überhaupt zu gesicherten Erkenntnissen zu kommen.

Der Algorithmus in [HKMRT 96] generalisiert die Fehlerinformationen zur Ermittlung der Regeln. Leider wird nur implizit die Netztopologie verwendet und die zusätzlichen räumlichen Einflußfaktoren bleiben vollständig unberücksichtigt. Aus diesen Umgebungsdaten lassen sich weitergehende Informationen ableiten, welche die räumliche Lage, die topologische Struktur und die Sachdaten berücksichtigen.

Abschließend kann festgehalten werden, daß die existierenden Data Mining Ansätze die spezifischen Auswertungsmöglichkeiten topologischer Strukturen im Zusammenhang mit räumlichen Informationen nicht berücksichtigen.

Ziele, Nutzen und methodischer Ansatz

Speziell werden hier zwei Fragestellungen betrachtet:

• Was sind, bzw. Wo liegen die Häufungen (Cluster) oder Muster im Datenbestand?
• Warum existieren diese Muster?

1. Zunächst werden topologische Regelmäßigkeiten bzw. Muster identifiziert, die zu einer Klassifikation der betrachteten raumbezogenen, topologischen Objekte führt und die Frage nach dem Was/Wo beantwortet.
2. Basierend auf diesen Ergebnissen werden die Charakteristiken der Klassen bzw. Muster bestimmt. Dies dient der Suche nach der Ursache der entdeckten Muster, also als Vorstufe zur Beantwortung der Frage Warum?

Die Antwort einem, wenn auch "intelligenten", Algorithmus zuzutrauen ist m.E. nicht angemessen. Hier ist und bleibt der analytische Sachverstand eines Fachmanns gefragt, dessen weitere Analysen durch die vorliegenden Mining-Ergebnisse unterstützt werden.

Der Nutzen besteht in einer effizienteren und insbesondere effektiveren Analyse der Daten und dem daraus resultierenden Erkenntnisgewinn. Dies kann für den Anwender bzw. das Unternehmen gerade nach der Liberalisierung der Märkte erhebliche Vorteile im nationalen wie internationalen Wettbewerb bringen.

Das Ziel dieser Arbeit ist, im Bereich der anwendungsorientierten Grundlagenforschung in der Praktischen Informatik, ein entsprechend anwendbares Verahren zu entwickeln und dieses mit realen Daten zu evaluieren. Dazu wird zunächst im zweiten Kapitel ein Überblick über die verwendete Terminologie und einige existierende Data Mining Verfahren gegeben. Anschließend wird im dritten Kapitel das Topologische Data Mining definiert und ein konkretes Cluster-Verfahren (TopClu) entwickelt. Im vierten und fünften Kapitel wird das Design, Realisisierungsaspekte und ein Benutzerhandbuch zum entwickelten Prototyp  dokumentiert, welcher zur Evaluation des TopClu-Verfahrens verwendet wird. Im sechsten Kapitel wird die Effektivität von TopClu im Rahmen einer Fallstudie zur topologischen Segmentierung auf Netzstrukturen untersucht. Abschließend wird im siebten Kapitel eine Bewertung des Verfahrens gegeben, die Einordnung von TopClu in den Gesamtkontext des Knowledge Discovery Prozeß auf Netzstrukturen vorgenommen und ein Ausblick auf weitere Entwicklungspotentiale aufgezeigt.