Probleme mit früheren Verfahren

Frühere Clusterverfahren waren wenig effektiv bei großen Datenmengen und haben den Fall, dass die Daten nicht in den Arbeitsspeicher passen, nicht berücksichtigt. Daher war eine Menge Verwaltungsaufwand notwendig, um Zugriffe auf die Daten außerhalb des Arbeitsspeichers zu minimieren. Für die meisten von BIRCHs Vorgängeralgorithmen gab es keine Heuristik, um zu entscheiden, ob ein Objekt zu einem bestimmten Cluster gehört. Daher war es notwendig auf alle Objekte (oder zumindest alle bis dahin gebildeten Cluster) zuzugreifen.

Vorteile

• Die Zuordnung zu einem Cluster ist eine lokale Entscheidung, d. h., es müssen nicht alle Objekte oder Cluster untersucht werden.
• Der Algorithmus nutzt aus, dass die Objekte nicht gleichmäßig verteilt sind bzw. dass die Objekte für das Clustering nicht alle gleich wichtig sind.
• Er nutzt den zu Verfügung stehenden Arbeitsspeicher voll aus, um die Zugriffskosten auf die Datenbank zu minimieren.
• Er ist eine inkrementelle Methode, die nicht die Kenntnis aller Objekte erfordert. Sie kann damit auch zum Clustern von Datenströmen eingesetzt werden.

Clustering-Algorithmus

Jeder Cluster wird mit folgenden Parametern beschrieben:

• ${\displaystyle n_{k}}$ die Anzahl der Objekte im Cluster ${\displaystyle k}$,
• den Vektor der Summe der ${\displaystyle n_{k}}$ Beobachtungswerte ${\displaystyle LS_{k}}$ und
• den Vektor der Summe der ${\displaystyle n_{k}}$ quadrierten Beobachtungswerte ${\displaystyle SS_{k}}$.

Die Parameter ${\displaystyle (n_{k},LS_{k},SS_{k})}$ nennt man die Clustering-Funktion ${\displaystyle CF_{k}}$. Dabei sind ${\displaystyle LS_{k}}$ und ${\displaystyle SS_{k}}$ d-dimensionale Vektoren mit d die Anzahl der Variablen (auch: Attribute oder Features). Aus ${\displaystyle LS_{k}}$ kann das Clusterzentrum als arithmetisches Mittel berechnet werden und der Clusterradius aus ${\displaystyle LS_{k}}$ und ${\displaystyle SS_{k}}$ als die totale Varianz der Beobachtungen im Cluster.

Die Clusterfunktionen werden in einem CF-Baum, einem balancierten Baum mit festgelegter Maximalhöhe, organisiert. Zur Generierung des CF-Baums werden zwei Parameter benötigt:

• der Verzweigungsfaktor B und
• die Schwelle T.

Jeder Nicht-Blatt-Knoten (rot oder blau in der Grafik) enthält höchstens B Einträge in der Form ${\displaystyle [CF_{i},child_{i}]}$, wobei ${\displaystyle child_{i}}$ ein Zeiger auf den i-ten Kind-Knoten und ${\displaystyle CF_{i}}$ die Clustering-Funktion des damit verbundenen Unterclusters ist. Jeder Blattknoten (grün in der Grafik) enthält höchstens ${\displaystyle L}$ Einträge der Form ${\displaystyle [CF_{i}]}$. Der Clusterradius eines Blattknotens darf den Schellwert T nicht überschreiten. Des Weiteren enthält jeder Blattknoten noch zwei Zeiger Prev und Next und diese verbinden alle Blattknoten als Kette. Die Baumgröße, die Anzahl der Knoten im Baum, hängt von der Schwelle T ab. Ein Knoten darf eine vorher festgelegten Maximalgröße im Arbeitsspeichers nicht überschreiten; damit sind die Maximalwerte P für B bzw. L festgelegt. Der Parameter P wird als Tuningparameter verwendet. Der CF-Baum ist eine sehr kompakte Darstellung der Daten, da jeder Eintrag im CF-Baum selbst ein Cluster ist.

Um ein neues Objekt in den CF-Baum aufzunehmen, wird der abstandsmäßig nächste Clustereintrag im Wurzelknoten (rot in der Grafik) bestimmt. Danach wird in den entsprechenden Kindknoten verzweigt und der Prozess wiederholt, bis ein Clustereintrag in einem Blattknoten gefunden wurde.

• Fall 1: Wenn durch Hinzufügen des Objektes die Bedingung Clusterradius < T nicht verletzt wird, dann kann es hinzugefügt werden. Dann müssen die Clustereinträge in den Knoten zwischen dem Blattknoten und dem Wurzelknoten upgedatet werden.
• Fall 2: Wird der Clusterradius zu groß, dann muss ein neuer Clustereintrag erstellt werden. Ist die Maximalzahl der Clustereinträge überschritten, muss der Blattknoten aufgespalten werden in zwei neue Blattknoten. Dabei werden die Clustereinträge, die am weitesten voneinander entfernt sind, in die beiden neuen Blattknoten übertragen. Jeder Clustereintrag des alten Blattknoten wird dann einem der beiden neuen Blattknoten zugeordnet, je nachdem zu welchem Clustereintrag er näher liegt. Auch hier müssen alle Clustereinträge in den Knoten zwischen den neuen Blattknoten und dem Wurzelknoten upgedatet werden.

Der BIRCH-Algorithmus wird in vier Schritten durchgeführt:

1. Der Algorithmus baut aus allen Objekten einen ersten CF-Baum, der in den Arbeitsspeicher passt.
2. (optional) Danach wird der Baum verkleinert. Dabei werden auch Ausreißer in den Daten und zu volle Knoten umgeordnet.
3. Auf den Clustereinträgen in den Blattknoten wird eine agglomerative hierarchische Clusteranalyse durchgeführt.
4. (optional) Durch einen weiteren Lauf über die Datenbank können die Cluster verbessert, z. B. durch Zuordnen von Objekten zu einem anderen Clustereintrag, sowie Ungenauigkeiten korrigiert werden.

Distanzmaße

Die verwendeten Distanzmaße im BIRCH Algorithmus lehnen sich bei der hierarchischen Clusteranalyse an:

• Euklidische Distanz (D0) zwischen den Clusterzentren
• Manhattan-Distanz (D1) zwischen den Clusterzentren
• Average-Linkage (D2): die Distanz zwischen zwei Clustern ist der mittlere Abstand zwischen allen Paaren von Objekten in beiden Clustern, wobei die Objekte aus verschiedenen Cluster kommen
• Average-Group-Linkage (D3): die Distanz zwischen zwei Clustern ist der mittlere Abstand zwischen allen Paaren von Objekten in beiden Clustern, wobei die Objekte auch aus demselben Cluster kommen können
• Wards minimum variance (D4): der Zuwachs der totalen Varianz, also die Differenz der totale Varianz des merged cluster, minus der beiden totalen Varianzen der Einzelcluster.

Alle diese Distanzmaße können effizient nur mit Hilfe Cluster-Funktion und der Lance und Williams Formel berechnet werden.

Auszeichnungen

Der BIRCH-Artikel wurde 2006 mit dem SIGMOD Test of Time Award ausgezeichnet.