Software zur Distanzbasierten Clusteranalyse und Validierung hierarchischer Clusteranalyse

Autor: Achim Mucha, WIAS Berlin (www.wias-berlin.de)

Einige ausgewählte Verfahren der Clusteranalyse wurden in Algorithmen, geschrieben in Visual Basic for Applications (VBA) und einsetzbar z.B. in der Spreedsheet-Umgebung von Excel, umgesetzt. Diese „Spielmodule“ enthalten im Quelltext einige wenige Kommentare zur Erklärung. Im Microsoft Excel kann mit der Tastenkombination [ALT] + [F11] die Programmierumgebung verfügbar gemacht und der Quellcode der Algorithmen eingesehen sowie bearbeitet werden.

Im Folgenden werden ganz kurz Funktion, Ein- und Ausgabe und evtl. Aufruf-Parameter der wichtigsten Module beschrieben. Die Eingabe, Ausgabe bzw. Übergabe von Daten und Ergebnissen zwischen den Modulen erfolgt meist über markierte (selektierte) Bereiche in Excel-Tabellenblättern. Die Module haben entweder gar keine oder aber optionale (Aufruf-) Parameter. Letztere sind eigentlich nur dann von Interesse, wenn man programmieren möchte und diese Module intern aufzurufen sind (Zugang für Programmierer). Optional heißt, dass bei Nichtbelegung die Eingabe über eine Dialogsteuerung abgefordert wird. Dies ist für Anwender der übliche Zugang zu den Methoden der hier enthaltenen Software. In Excel kann mit der Tastenkombination [ALT] + [F8] die Liste der verfügbaren Module (Makros) angezeigt und das betreffende Makro ausgewählt und gestartet werden. Alternativ kann solch ein Aufruf auch über die Menüleisten von Excel erfolgen.

Die Dialogsteuerung wird bei bereits vorhandener Belegung automatisch unterdrückt. Dadurch können die Module z.B. für umfangreiche Simulationsrechnungen eingesetzt werden, ohne daß Benutzereingriffe erforderlich sind.

Modulübersicht

DistMat.XCDistMat (metric, mass, weight, p)

Funktion: Berechnung einer Distanzmatrix aus einer Datentabelle

Dateninput: Datenmatrix mit Namen (1. Zeile, 1. Spalte) und optionalen Gewichten der Zeilen (letzte Spalte) und Spalten (letzte Zeile)

Parameter:

Ergebnisausgabe: Distanzmatrix mit Namen (1. Zeile, 1. Spalte) und Gewichten (letzte Spalte). Wird als Eingabe für XCAgglom erwartet.

Agglom.XCAgglom (method, beta)

Funktion: Hierarchische agglomerative Clusteranalyse

Dateninput: Distanzmatrix mit Namen (1. Zeile, 1. Spalte) und Gewichten (letzte Spalte)

Parameter:    

Ergebnisausgabe: sogenanntes Fusionsprotokoll, welches jeden einzelnen Fusionsschritt beginnend vom Zusammenfassen der beiden ähnlichsten Objekte zu einem Cluster bis hin zur Verschmelzung in ein einziges (triviales) Cluster, welches alle Objekte enthält.

AgglomS.XCAgglomS (method, beta, isim)

Funktion: Hierarchische agglomerative Clusteranalyse mit aktiven (positive Gewichte) und supplementären Objekten (Gewichte gleich oder kleiner 0), sonst wie XCAgglom. Eigentlich ist dieser Modul speziell nur für Simulationszwecke entwickelt worden (siehe hierzu Modul AggSimAS), wo anschließend kein Dendrogramm gezeichnet werden soll. Jedoch kann diese graphische Ausgabe genau dann gemacht werden, wenn im Dateninput die aktiven Objekte vor den supplementären Objekten angeordnet vorliegen. Auf diese Weise können z.B. Ausreißer in den Daten (=supplementärer Status) in die Hierarchie eingeordnet werden, ohne das diese die Clusterbildung beeinflussen können.

Dateninput: Distanzmatrix mit Namen (1. Zeile, 1. Spalte) und Gewichten (letzte Spalte), wobei die Gewichte über eine Zufallsfunktion belegt werden müssen (z.B. zufällige Ziehen von etwa der Hälfte der Beobachtungen als aktiv: „=if(rand()<0,5; 1; 0)“ oder zufälliges Ziehen von ca. 75% der Beobachtungen als aktiv: „=if(rand()<0,75; 1; 0)“, wobei die Excel-Funktion rand() eine gleichverteilte Zufallszahl aus dem Intervall [0, 1) generiert).

Parameter:    

Ergebnisausgabe: sogenanntes Fusionsprotokoll, welches jeden einzelnen Fusionsschritt beginnend vom Zusammenfassen der beiden ähnlichsten Objekte zu einem Cluster bis hin zur Verschmelzung in ein einziges (triviales) Cluster, welches alle Objekte umfaßt, dokumentiert. In der hier vorliegenden Testversion ist dieses Fusionsprotokoll nur dann gültig und zur Dendrogrammdarstellung nutzbar wenn im Dateninput alle aktiven Objekte vor den supplementären Objekten angeordnet sind! Eine mögliche Anwendung wäre z.B. die Deklaration von Ausreißern im Datenmaterial als supplementär um als Ergebnis ein „vollständiges“ Dendrogramm mit sämtlichen Objekten zu erhalten.

TiHexM.XCTiHex (metric, metricB, mass, weight, initP, ib, ds, dst, method, kmin, kmax, initR, initM, maxiter, iii, nsh, sp, us)

Funktion: Verschiedene Methoden der partitionierenden Clusteranalyse auf der Basis einer Matrix der paarweisen Distanzen für Partitionen (Gruppierungen) in kmin, kmin+1,..., kmax Cluster. Die Distanzmatrix kann aus einer Matrix (Tabelle) aus quantitativen (metrischen) Daten (die, wenn vorhanden, in den ersten Spalten angeordnet sein müssen), kategorialen Daten (Binär- bzw. Nominaldaten) oder „gemischten“ Daten berechnet werden. Hierbei wird für Variablen mit quantitativer Meßskala als Distanzmaß metric, für solche mit kategorialer Skala (binärskalierte Daten (0-1-Daten) bzw. nominalskalierte Daten) metricB benutzt. Nominale Daten können mehr als zwei Kategorien und eine beliebige Kodierung dieser Kategorien haben.

In der Regel wird nur eine lokal optimale Klassifikationslösung berechnet, die von der gewählten Startpartition abhängt. Es empfiehlt sich deshalb das mehrfache Ausführen des Moduls. Ein Beispiel für ein geeignetes Rufprogramm für beliebig viele solcher Clusteranalysen ist XCTiHexMain. Die Ergebnisse des von H. Späth vorgeschlagenen Algorithmus hängen zusätzlich noch von der physischen Reihenfolge der Objekte in der Distanz- bzw. Datenmatrix ab. Die hier implementierten speziellen Algorithmen haben keine derartige Abhängigkeit (Methoden GradientSum, GradientAverage und GradientLogSum) oder praktisch keine derartige Abhängigkeit durch rein zufällige Auswahl der Objektfolge (Methoden Sum, Average und LogSum).

Dateninput Möglichkeiten:

Parameter:    

Ergebnisausgabe: Tabelle, die in den Spalten die Partitionen in kmin, kmin+1,..., kmax Cluster enthält sowie unten angefügt die Anzahl der ausgeführten Iterationen, die Kriteriumswerte in den einzelnen Clustern und den totalen Kriteriumswert enthält.

XCTiHexMain

Funktion: Rufprogramm für XCTiHex

Dateninput: siehe XCTiHex

Parameter:     Keine, über zusätzliche Dialogeingabe wird die Anzahl der Clusteranalysen (=Anzahl der Wiederholungen mit verschiedenen Startpartitionen) abgefragt

Ergebnisausgabe: wie XCTiHex, jedoch für mehrere Clusteranalysen (maximal 255 Spalten sind dafür vorgesehen)

Außerdem werden die Partitionen, die unter allen Wiederholungen die besten (kleinsten) Kriteriumswerte ausweisen, in einer zusätzlichen Tabelle ausgegeben.

AggSimAs

Funktion: Rufprogramm für XCAgglomS zur Stabilitätsuntersuchung hierarchischer agglomerativer Clusteranalysen mit aktiven (positive Gewichte) und supplementären Objekten (Gewichte gleich oder kleiner 0)

Dateninput: siehe XCAgglomS

Parameter:     Keine, über zusätzliche Dialogeingabe wird die Clusteranalysemethode, ein evtl. zusätzlicher Parameter zur Methode, die Anzahl der Simulationen (=Clusteranalysen über jeweils zufällig ausgewählten aktiven und supplementären Objekten), die maximale Anzahl der Cluster sowie die Verfahrensweise mit supplementären Objekten abgefragt. Letzteres bedeutet entweder die Klassifikation supplementärer Objekte mit der K-Nächsten-Nachbarn Methode in die berechneten Cluster, wobei K=3 Nachbarn Voreinstellung sind und alternativ K=1 gewählt werden kann, oder keinerlei Klassifikation (K=0 im Dialogfeld setzen). Die anschließende Validierung der Clusteranalysen basiert auf der Berechnung von drei verschiedenen Übereinstimmungsmaßen zwischen Klasseneinteilungen. Im Falle der Klassifikation supplementärer Objekte (K=1 oder K=3) werden hierfür die „vollen“ Kontingenztafeln (erzeugt über alle Objekte) oder im Falle des Weglassens supplementärer Objekte die Kontingenztafeln nur aus den aktiven Objekten benutzt.

Ergebnisausgabe:

Die Visualisierungen der Ergebnisse der Stabilitätsuntersuchungen der hierarchischen Clusteranalyse (HCA) erfolgt in 3 Diagrammen (Diagramm1, Diagramm2 und Diagramm3 bzw. Chart1, Chart2 und Chart3): hier wird die Frage nach der Stabilität der gesamten hierarchischen Clusteranalyse in Abhängigkeit von der Klassenzahl beantwortet d.h. gröbste Stabilitätsbeurteilung einer jeden möglichen Partition, die man aus der hierarchischen Clusteranalyse durch geraden “Schnitt” im Dendrogramme erhalten kann = Bestimmung der Clusteranzahl): In den Diagrammen sind die Statistiken der folgenden Maße veranschaulicht (Die zugehörigen numerischen Werte zu den Diagrammen sind in der Tabelle Stat4Diagram abgelegt):
Stabilitätsbeurteilung eines jeden möglichen Clusters: Die Stabilität der einzelnen Cluster wird in der Tabelle ClustValid abgelegt. Je Partition in 2, 3,… Cluster werden je zwei Spalten mit:
FeinstmöglicheStabilitätsbeurteilung eines jeden Objekts: Die Stabilität einzelner Objekte kann daran gemessen werden, wie oft sie bei Clusteranalyse über alle Stichproben in andere Gruppen als bei der Partition P0 (übliche Clusteranalyse über allen Daten) eingeteilt wurden. Das Ergebnis ist die relative Eingruppierungssicherheit in % und wird zusammen mit der zugehörigen Partition der üblichen HCA in der Tabelle PartValid abgelegt