OPTICS

OPTICS (englisch Ordering Points To Identify the Clustering Structure ‚[etwa] Punkte ordnen um die Clusterstruktur zu identifizieren‘) ist ein dichtebasierter Algorithmus zur Clusteranalyse. Er wurde von Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel und Jörg Sander entwickelt. Das Grundprinzip des Algorithmus entstammt DBSCAN, jedoch löst der Algorithmus eine wichtige Schwäche des DBSCAN-Algorithmus: im Gegensatz zu diesem kann er Cluster unterschiedlicher Dichte erkennen. Gleichzeitig eliminiert er (weitgehend) den $\varepsilon$-Parameter des DBSCAN-Algorithmus. Hierzu ordnet OPTICS die Punkte des Datensatzes linear so, dass räumlich benachbarte Punkte in dieser Ordnung nahe aufeinander folgen. Gleichzeitig wird die sogenannte „Erreichbarkeitsdistanz“ notiert. Zeichnet man diese Erreichbarkeitsdistanzen in ein Diagramm, so bilden Cluster „Täler“ und können so identifiziert werden.

Kernidee

OPTICS verwendet wie DBSCAN zwei Parameter, $minPts$ und $\varepsilon$. $\varepsilon$ spielt hier jedoch die Rolle einer Maximaldistanz und dient vor allem dazu, die Komplexität des Algorithmus zu begrenzen. Setzt man $\varepsilon =\infty$, so ist die Komplexität des Algorithmus $O(n^{2})$, andernfalls kann sie mit Hilfe von geeigneten räumlichen Indexstrukturen wie dem R*-Baum auf $O(n\cdot \log n)$ reduziert werden. Ohne diese Optimierung hingegen verbleibt die Komplexität bei $O(n^{2})$ für endliche $\varepsilon$.

In DBSCAN ist ein Punkt ein „Kernpunkt“, wenn seine $\varepsilon$-Umgebung mindestens $minPts$ Punkte enthält. In OPTICS hingegen wird geschaut, ab wann ein Punkt ein Kernpunkt wäre. Das wird mit der „Kerndistanz“ umgesetzt, also demjenigen $\varepsilon$-Wert, ab dem ein Punkt in DBSCAN ein „Kernpunkt“ wäre. Gibt es kein $\varepsilon$, mit dem ein Punkt ein Kernpunkt wäre, ist dessen Kerndistanz unendlich oder „undefiniert“.

Die „Erreichbarkeitsdistanz“ eines Punktes $p$ von einem zweiten Punkt $o$ ist definiert als $\max(kerndistanz(o),dist(o,p))$, also als das Maximum des echten Abstandes und der Kerndistanz des verweisenden Punktes.

OPTICS ordnet jetzt die Objekte in der Datenbank, indem es bei einem beliebigen unbearbeiteten Punkt anfängt, die Nachbarn in der $\varepsilon$-Umgebung ermittelt und sie sich nach ihrer bisher besten Erreichbarkeitsdistanz in einer Vorrangwarteschlange merkt. Es wird jetzt immer derjenige Punkt als Nächstes in die Ordnung aufgenommen, der die kleinste Erreichbarkeitsdistanz hat. Durch das Verarbeiten eines neuen Punktes können sich die Erreichbarkeitsdistanzen der unverarbeiteten Punkte verbessern. Durch die Sortierung dieser Vorrangwarteschlange verarbeitet OPTICS einen detektierten Cluster vollständig, bevor er beim nächsten Cluster weitermacht.

Visualisierung

OPTICS kann als Erreichbarkeitsdiagramm (unten) visualisiert werden. Hierbei sind die Punkte entlang der x-Achse nach der von OPTICS berechneten Ordnung sortiert, und auf der y-Achse ist die Erreichbarkeitsdistanz angegeben. „Täler“ in diesem Diagramm entsprechen erkannten Clustern im Datensatz; die Tiefe des Tales zeigt die Dichte des Clusters an. Als zusätzliche Visualisierung wird hier (rechts oben) jeder Punkt mit seinem Erreichbarkeits-Vorgänger verbunden. Der so entstehende Spannbaum visualisiert die von OPTICS ermittelte Dichte-Verbundenheit der Punkte im Datensatz. Als Parameter wurden hier $\varepsilon \leq 0.5$ und $minPts=10$ verwendet. Diese Visualisierung wurde mit der OPTICS-Implementierung in ELKI erstellt.

Pseudocode

Der Grundansatz von OPTICS ist ähnlich zu dem von DBSCAN, aber statt eine Menge von „bekannten aber noch nicht verarbeiteten“ Objekten zu pflegen, werden diese in einer Vorrangwarteschlange (beispielsweise einem indizierten Heap) verwaltet.

  OPTICS(DB, eps, MinPts)
     for each point p of DB
        p.reachability-distance = UNDEFINED
     for each unprocessed point p of DB
        N = getNeighbors(p, eps)
        mark p as processed
        output p to the ordered list
        Seeds = empty priority queue
        if (core-distance(p, eps, Minpts) != UNDEFINED)
           update(N, p, Seeds, eps, Minpts)
           for each next q in Seeds
              N' = getNeighbors(q, eps)
              mark q as processed
              output q to the ordered list
              if (core-distance(q, eps, Minpts) != UNDEFINED)
                 update(N', q, Seeds, eps, Minpts)

In update() wird die Vorrangwarteschlange mit der $\varepsilon$-Umgebung von $p$ bzw. $q$ aktualisiert:

  update(N, p, Seeds, eps, Minpts)
     coredist = core-distance(p, eps, MinPts)
     for each o in N
        if (o is not processed)
           new-reach-dist = max(coredist, dist(p,o))
           if (o.reachability-distance == UNDEFINED) // o is not in Seeds
               o.reachability-distance = new-reach-dist
               Seeds.insert(o, new-reach-dist)
           else               // o in Seeds, check for improvement
               if (new-reach-dist < o.reachability-distance)
                  o.reachability-distance = new-reach-dist
                  Seeds.move-up(o, new-reach-dist)

OPTICS gibt die Punkte also in einer bestimmten Reihenfolge aus, annotiert mit ihrer kleinsten Erreichbarkeitsdistanz (der veröffentlichte Algorithmus speichert auch die Kerndistanz, sie wird aber nicht weiter benötigt).

Erweiterungen

OPTICS-OF ist ein auf OPTICS aufbauendes Verfahren zur Ausreißer-Erkennung. Ein wichtiger Vorteil ist hier, dass Cluster im Zuge eines normalen OPTICS-Laufes ermittelt werden können, ohne eine separate Ausreißer-Erkennung durchführen zu müssen.

DeLiClu, Density-Link-Clustering kombiniert Ideen von Single-Linkage Clustering und OPTICS, eliminiert so den $\varepsilon$-Parameter und erzielt eine verbesserte Performanz gegenüber OPTICS durch Verwendung eines R-Baumes als Index.

HiSC ist ein hierarchisches (achsen-paralleles) Unterraum-Clustering-Verfahren.

HiCO ist ein hierarchisches Clustering-Verfahren für beliebig orientierte Unterräume.

DiSH ist eine Verbesserung von HiSC für komplexere Hierarchien (mit Schnitten von Unterräumen).

Verfügbarkeit

Eine Referenzimplementierung ist im Software-Paket ELKI des Lehrstuhls verfügbar, inklusive Implementierungen von DBSCAN und anderen Vergleichsverfahren.

Im Modul „scikit-learn“ ist eine Implementierung von OPTICS in Python seit der Version scikit-learn v0.21.2 enthalten.