Das Forschungsgebiet der Cluster Ensembles erarbeitet Verfahren zur Vereinigung mehrerer Objekt-Zuordnungen. Ein Clusterer ordnet jedem Objekt einer Menge maximal eine Gruppe zu. Die Aufgabe dieses Bereichs der Forschung liegt in der Vereinigung der Ergebnisse verschiedener Clusterer zu einer einzelnen Zuordnung, die mit den Originalzuordnungen eine m\"oglichst hohe Ähnlichkeit besitzt.
%\\$\Gamma : \{  \lambda^{(q)}  | q \in \{1,\dots,r\}  \rightarrow \lambda \}$ \\
Besondere Bedeutung besitzen Algorithmen, die jene Aufgabe ohne Kenntnis über die Zuordnungskriterien, durchführen, da derartige Verfahren wiederverwendbar und universell einsetzbar sind. Die Qualit\"at der Verfahren kann unter verschiedenen Gesichtspunkten analysiert werden. Ein wesentliches Kriterium liegt trivialerweise in der \"Ahnlichkeit der neuen Zuordnung zu jenen aus der Eingabe. Wegen eventuell großen Datenmengen muss der Laufzeit in Abh\"angigkeit von der Eingabemenge ebenfalls eine gro{\ss}e Bedeutung zugeordnet werden. Ein weiteres interessantes Kriterium, das nur eine untergeordneter Bedeutung besitzt, liegt in der potentiellen Verwendung dieses Algorithmus auf einem verteilten System. Diese zus\"atzliche Möglichkeit kann die Laufzeit des Verfahrens allerdings nur um einen konstanten Faktor senken, sollte aber dennoch nicht völlig vernachl\"assigt werden.\\\\
Als Basis f\"ur eine effiziente Bearbeitung dient eine Transformation der Eingabedaten in eine geeignete Form f\"ur die Verarbeitung. Hierzu werden  die Eingabedaten in eine Matrix transformiert, wobei die Zeilen den einzelnen Objekten entsprechen, die zugeordnet werden sollen, und die Spalten den Clusterern, die eine Zuordnung erzeugen. Die Eintr\"age der Matrix entsprechen folglich der Gruppe, die der Clusterer dem Objekt zuordnet. Wegen der Wiederverwendbarkeit des Verfahrens k\"onnen beliebige Identifikatoren verwendet werden. Die Matrix kann nun durch Erweiterung einer Spalte in einen Hypergraphen umgewandelt werden. Hierzu findet eine Ersetzung eines Clusterers durch die Gruppen, die jener erzeugt, statt. Die Eintr\"age der Matrix werden nun durch eine 1 ersetzt, falls das Objekt jener Gruppe zugeordnet ist, ansonsten durch eine 0. Eine Spalte repr\"asentiert folglich nun eine Hyperkante in einem Hypergraphen. Jegliche Objekte, die der gleichen Gruppe zugeordnet sind, werden durch Hyperkante verbunden.\\\\
Der Cluster-based Similarity Partitioning Algorithm (CSPA)\cite{Strehl/Ghosh/2002a} basiert auf einer ziemlich einfachen Idee. Die einzelnen Objekte werden miteinander verglichen und die Ähnlichkeit dieser Objekte ermittelt. Diese paarweise Betrachtung, der einzelnen Objekte kann je nach Anwendungsgebiet auch als Schwachpunkt dieses Verfahrens angesehen werden. Die Ähnlichkeit wird durch eine Matrixmultiplikation bestimmt. Hierzu wird die Matrix des Hypergraphen mit seiner transponierten Matrix multipliziert. Anschließend wird die Ergebnismatrix mit dem Inversen der Anzahl der Clusterer multipliziert. Jeder Eintrag wird somit auf einen Werte zwischen null und eins normiert, da jedes Objekt nach Definition pro Clusterer nur einer Gruppe zugeordnet werden kann und sich folglich maximal Anzahl der Clusterer Einsen pro Zeile der Originalmatrix bzw. pro Spalte der transponierten Matrix befinden. Nach Ausführung dieser Schritte wurde das Ursprungsproblem auf das Problem eines \"ahnlichkeitsbasierten Zuordnungsalgorithmus reduziert. Die Matrix bestehend aus den paarweisen Ähnlichkeiten der Objekte kann nun mit Hilfe eines solchen Algorithmus zum Beispiel METIS in die gew\"unschte Anzahl von Cluster umgruppiert werden.\\\\
Der HyperGraph-Partitioning Algorithm (HGPA)\cite{Strehl/Ghosh/2002a} versucht die Schwachstelle des Cluster-based Similarity Partitioning Algorithm mit der paarweisen Betrachtung zu beheben. Dieser Algorithmus  arbeitet wie schon der Name verrät auf einem Hypergraphen. Eine Spate in der Matrix repr\"aesentiert eine Hyperkante innerhalb dieses Hypergraphen. Aus diesem Graphen sollen möglichst wenig Kanten entfernt werden um die anvisierte Anzahl von unverbundenen Komponenten zu erreichen, wobei jede Kante die gleiche Gewichtung besitzt. Analog zum CSPA wird das Problem auf einen anderen Problemtyp reduziert, für den beispielsweise mit Hilfe des hMETIS-Algorithmus gute Ergebnisse erzielt werden können. Eine weitere Anforderung liegt in der ann\"ahernd gleichen Gr\"o{\ss}e der unverbundenen Komponenten, die eine h\"oherer Qualit\"at des Ergebnisses garantieren soll. Eine kleine Schw\"ache dieses Verfahrens mit der anschließenden Verwendung des hMETIS-Algorithmus ist eine fehlende Ber\"ucksichtigung der Schnitth\"aufigkeit einer zertrennten Kante. \\\\
Der Meta-Clustering Algorithm (MCLA)\cite{Topchy/Jain/2004a} basiert ebenfalls auf der Reduktion des eigentlichen Problems auf einen \"ahnlichkeitsbasierten Zuordnungsalgorithmus. Hierzu werden für alle Gruppen der Clusterer Knoten erzeugt. Die Kanten zwischen den einzelnen Gruppen werden hierbei mit ein Kantengewicht belegt, das die \"Ahnlichkeiten dieser Gruppen wiedergibt.  Ein etabliertes Verfahren zur Ermittlung der \"Ahnlichkeit zwischen zwei Gruppen ist das Jaccard Measure. Dieser Ma{\ss}stab wird durch den Quotienten aus den gemeinsamen Objekten und den Objekten, die mindestens in einer Menge vorkommen, ermittelt. Im Gegensatz zum CSPA, bei dem auf Basis der \"Ahnlichkeiten der Objekte neue Gruppen erzeugt werden, dient hier die Gruppen\"ahnlichkeit als Eingabe für den Algorithmus. Nachdem die neuen Gruppen, die eine Vereinigung mehrerer ursprünglicher Gruppen sind, erzeugt wurden, wird jedes Objekt einer dieser Gruppe zugeordnet. Das Kriterium für die Zuordnung stellt der Quotient aus Anzahl der Unsprungsgruppen, in denen es vorkommt, und der Anzahl der Gruppen, die vereinigt wurden.\\\\
Beim Estimation-Maximization-Algorithm (EM-Algorithm) handelt es sich um einen k-means Algorithmus. Zu Beginn des Algorithmus werden Clusterzentren an beliebigen Position des Arbeitsraumes festgelegt. Die Anzahl der Clusterzentren entspricht der Gruppenanzahl, die erzeugt werden sollen. Jedes Objekt wird mit einer  Wahrscheinlichkeit dem Zentrum mit der geringsten Distanz zugeordnet. Als Verfahren f\"ur die Ermittlung des Wahrscheinlichkeitwertes wird die Standardnormalverteilung empfohlen. Nachdem diese Zuordnung für alle Objekte vollzogen wurde, können anhand der enthaltenen Objekte und der Wahrscheinlichkeit ihrer Zugeh\"örigkeit neue Clusterzentren ermittelt werden. Mit diesen neuen Clusterzentren werden alle Objekte erneut zugeordnet. Dieser Vorgang wird wiederholt bis ein definierter Schwellenwert unterschritten wurde oder eine definierte maximale Anzahl an Wiederholungen erreicht ist. Diese zusätzliche Bedingung ist notwendig, da dieser Algorithmus ansonsten nicht zwangsl\"aufig terminiert.\\\\
Der Cluster-based Similarity Partitioning Algorithm wird besonders bei Gro{\ss}en Objektmengen sehr ineffizient, wenn nicht sogar unpraktikabel. Die Matrixmultiplikation ist zwar ein einfaches Verfahren besitzt jedoch eine Laufzeit von  ${\it O}(n^2kr)$, wobei n der Anzahl der Objekte, k der Anzahl der Clusterer und r der Gruppen pro Clusterer entspricht. Zudem ist wegen der erzeugten n $\times$ n Matrix eine hohe Speicherbelastung gegeben. Im Gegensatz dazu ist der HyperGraph-Partitioning Algorithm sehr sparsam im Ressourcenverbrauch mit seiner Laufzeit von ${\it O}(nkr)$ und d\"urfte im Rahmen dieser Projektarbeit mit vielen Objekten eine gr\"o{\ss}ere Bedeutung besitzen. Der Meta-Clustering Algorithm ist mit seiner Laufzeit von ${\it O}(nk^2r^2)$ zwar langsamer als  der HGPA, jedoch insbesondere bei wenigen Clusterern und wenig zugeordneten Gruppen interessant. Die Laufzeit des Estimation-Maximization-Algorithm ${\it O}(kNH)$ ist anh\"angig von der Anzahl der erzeugten Gruppen, Objekte und Anzahl der Wiederholungen bis zum erreichen des Schwellenwertes bzw. der maximalen Wiederholungsh\"aufigkeit.\\\\Die Qualit\"at der Ergebnisse differiert in den vorgenommenen Studien stark von dem Eingabedaten. Zumal keinerlei Eingabedaten f\"ur ein vergleichbares Forschungsgebiet vorliegen, k\"onnen hier nur schwer Ergebnisse prognostiziert werden.