OPTIK-Algorithmus - OPTICS algorithm

Ordering Points to Identification the Clustering Structure ( OPTICS ) ist ein Algorithmus zum Auffinden dichtebasierter Cluster in Geodaten. Präsentiert wurde es von Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel und Jörg Sander. Seine Grundidee ähnelt der von DBSCAN , adressiert jedoch eine der größten Schwächen von DBSCAN: das Problem, sinnvolle Cluster in Daten unterschiedlicher Dichte zu erkennen. Dazu werden die Punkte der Datenbank (linear) so geordnet, dass räumlich am nächsten liegende Punkte Nachbarn in der Ordnung werden. Zusätzlich wird für jeden Punkt eine spezielle Distanz gespeichert, die die Dichte repräsentiert, die für einen Cluster akzeptiert werden muss, damit beide Punkte zum selben Cluster gehören. Dies wird als Dendrogramm dargestellt .

Die Grundidee

Wie DBSCAN erfordert OPTICS zwei Parameter: $ε$ , das die zu berücksichtigende maximale Entfernung (Radius) beschreibt , und $MinPts$ , die die Anzahl der Punkte beschreibt, die zum Bilden eines Clusters erforderlich sind. Ein Punkt $p$ ist ein Kernpunkt, wenn mindestens $MinPts-$ Punkte innerhalb seiner $ε$ -Umgebung (einschließlich Punkt $p$ selbst) gefunden werden. Im Gegensatz zu DBSCAN hält OPTIK auch Punkte , die Teil einer dichter gepackten Cluster sind, so dass jeder Punkt eine zugeordnet ist Kernabstand , der den Abstand zu den beschreibt $MinPts$ th nächsten Punkt: $N_{\varepsilon}(p)$

{\text{core-dist}}_{\mathit {\varepsilon ,MinPts}}(p)={\begin{cases}{\text{UNDEFINED}}&{\text{if }}|N_ {\varepsilon}(p)|<{\mathit {MinPts}}\\{\mathit {MinPts}}{\text{-kleinster Abstand in }}N_{\varepsilon}(p)&{\text{sonst }}\end{Fälle}}

Die Erreichbarkeitsdistanz eines anderen Punktes $o$ von einem Punkt $p$ ist entweder die Distanz zwischen $o$ und $p$ oder die Kerndistanz von $p$ , je nachdem, welcher Wert größer ist:

{\text{reachability-dist}}_{\mathit {\varepsilon ,MinPts}}(o,p)={\begin{cases}{\text{UNDEFINED}}&{\text{if }} |N_{\varepsilon}(p)|<{\mathit {MinPts}}\\\max({\text{core-dist}}_{\mathit {\varepsilon ,MinPts}}(p),{\text {dist}}(p,o))&{\text{sonst}}\end{cases}}

Wenn $p$ und $o$ nächste Nachbarn sind, müssen wir annehmen, dass $p$ und $o$ zum selben Cluster gehören. $\varepsilon '<\varepsilon$

Sowohl Kern-Abstand und Erreichbarkeits-Abstand nicht definiert sind , wenn keine ausreichend dichte Cluster (WRT $ε$ ) zur Verfügung steht. Bei einem ausreichend großen $ε$ passiert dies nie, aber dann gibt jede $ε$ -Nachbarschaftsabfrage die gesamte Datenbank zurück, was zur Laufzeit führt. Daher wird der Parameter $ε$ benötigt, um die Dichte nicht mehr interessanter Cluster abzuschneiden und den Algorithmus zu beschleunigen. $O(n^{2})$

Der Parameter $ε$ ist streng genommen nicht notwendig. Er kann einfach auf den maximal möglichen Wert eingestellt werden. Wenn jedoch ein räumlicher Index verfügbar ist, spielt er im Hinblick auf die Komplexität eine praktische Rolle. OPTICS abstrahiert von DBSCAN, indem es diesen Parameter entfernt, zumindest soweit, dass nur der Maximalwert angegeben werden muss.

Pseudocode

Der grundsätzliche Ansatz von OPTICS ähnelt DBSCAN , jedoch werden bekannte, aber bisher unverarbeitete Cluster-Mitglieder nicht in einer Menge verwaltet, sondern in einer Prioritätswarteschlange (zB mit einem indizierten Heap ).

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

In update() wird die Prioritätswarteschlange Seeds mit der -Nachbarschaft von bzw. aktualisiert : ${\displaystyle\varepsilon}$ $p$ $q$

function update(N, p, Seeds, eps, MinPts) is
    coredist = core-distance(p, eps, MinPts)
    for each o in N
        if o is not processed then
            new-reach-dist = max(coredist, dist(p,o))
            if o.reachability-distance == UNDEFINED then // 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 then
                    o.reachability-distance = new-reach-dist
                    Seeds.move-up(o, new-reach-dist)

OPTICS gibt die Punkte daher in einer bestimmten Reihenfolge aus, annotiert mit ihrer kleinsten Erreichbarkeitsentfernung (im ursprünglichen Algorithmus wird auch die Kernentfernung exportiert, dies wird jedoch für die weitere Verarbeitung nicht benötigt).

Extrahieren der Cluster

Mit Hilfe eines Erreichbarkeits-Plots (einer besonderen Art von Dendrogramm ) kann die hierarchische Struktur der Cluster leicht ermittelt werden. Es ist ein 2D-Plot mit der Reihenfolge der Punkte, wie sie von OPTICS verarbeitet wurden, auf der x-Achse und der Erreichbarkeitsentfernung auf der y-Achse. Da zu einem Cluster gehörende Punkte eine geringe Erreichbarkeitsentfernung zu ihrem nächsten Nachbarn haben, erscheinen die Cluster als Täler im Erreichbarkeitsdiagramm. Je tiefer das Tal, desto dichter der Cluster.

Das obige Bild veranschaulicht dieses Konzept. Im oberen linken Bereich wird ein synthetischer Beispieldatensatz angezeigt. Der obere rechte Teil visualisiert den von OPTICS erzeugten Spannbaum , und der untere Teil zeigt den von OPTICS berechneten Erreichbarkeits-Plot. Farben in diesem Diagramm sind Beschriftungen und werden nicht vom Algorithmus berechnet; aber es ist gut sichtbar, wie die Täler im Diagramm den Clustern im obigen Datensatz entsprechen. Die gelben Punkte in diesem Bild werden als Rauschen betrachtet, und in ihrem Erreichbarkeitsdiagramm wird kein Tal gefunden. Sie werden in der Regel keinen Clustern zugeordnet, außer dem allgegenwärtigen "Alle Daten"-Cluster in einem hierarchischen Ergebnis.

Das Extrahieren von Clustern aus diesem Plot kann manuell erfolgen, indem nach der visuellen Inspektion ein Bereich auf der x-Achse ausgewählt wird, indem auf der y-Achse ein Schwellenwert ausgewählt wird (das Ergebnis ähnelt dann einem DBSCAN-Clustering-Ergebnis mit den gleichen und minPts-Parametern; hier ein Wert von 0,1 kann gute Ergebnisse liefern) oder durch verschiedene Algorithmen, die versuchen, die Täler durch Steilheit, Knieerkennung oder lokale Maxima zu erkennen. Auf diese Weise erhaltene Clusterings sind normalerweise hierarchisch und können nicht durch einen einzelnen DBSCAN-Lauf erreicht werden. ${\displaystyle\varepsilon}$

Komplexität

Wie DBSCAN verarbeitet OPTICS jeden Punkt einmal und führt während dieser Verarbeitung eine -Nachbarschaftsabfrage durch . Bei einem räumlichen Index , der zur Laufzeit eine Nachbarschaftsabfrage gewährt , wird eine Gesamtlaufzeit von erhalten. Die Autoren des ursprünglichen OPTICS-Papiers berichten von einem tatsächlichen konstanten Verlangsamungsfaktor von 1,6 im Vergleich zu DBSCAN. Beachten Sie, dass der Wert von die Kosten des Algorithmus stark beeinflussen kann, da ein zu großer Wert die Kosten einer Nachbarschaftsabfrage auf lineare Komplexität erhöhen kann. ${\displaystyle\varepsilon}$ $O(\log n)$ $O(n\cdot\log n)$ ${\displaystyle\varepsilon}$

Insbesondere ist eine Auswahl (größer als der maximale Abstand im Datensatz) möglich, führt jedoch zu quadratischer Komplexität, da jede Nachbarschaftsabfrage den vollständigen Datensatz zurückgibt. Auch wenn kein räumlicher Index verfügbar ist, verursacht dies zusätzliche Kosten bei der Verwaltung des Heaps. Daher sollte entsprechend dem Datensatz ausgewählt werden. $\varepsilon >\max _{x,y}d(x,y)$ ${\displaystyle\varepsilon}$

Erweiterungen

OPTICS-OF ist ein Ausreißererkennungsalgorithmus basierend auf OPTICS. Die Hauptanwendung ist die kostengünstige Extraktion von Ausreißern aus einem bestehenden OPTIK-Lauf im Vergleich zur Verwendung einer anderen Ausreißererkennungsmethode. Die bekanntere Version LOF basiert auf den gleichen Konzepten.

DeLi-Clu, Density-Link-Clustering kombiniert Ideen aus Single-Linkage-Clustering und OPTICS, eliminiert den Parameter und bietet Leistungsverbesserungen gegenüber OPTICS. ${\displaystyle\varepsilon}$

HiSC ist ein hierarchisches Subspace-Clustering -Verfahren (achsenparallel) basierend auf OPTICS.

HiCO ist ein hierarchischer Korrelations-Clustering- Algorithmus basierend auf OPTICS.

DiSH ist eine Verbesserung gegenüber HiSC, die komplexere Hierarchien finden kann.

FOPTICS ist eine schnellere Implementierung mit zufälligen Projektionen.

HDBSCAN* basiert auf einer Weiterentwicklung von DBSCAN, schließt Grenzpunkte aus den Clustern aus und folgt damit strenger der grundlegenden Definition der Dichtestufen von Hartigan.

Verfügbarkeit

Im ELKI Data Mining Framework stehen Java-Implementierungen von OPTICS, OPTICS-OF, DeLi-Clu, HiSC, HiCO und DiSH zur Verfügung (mit Indexbeschleunigung für mehrere Distanzfunktionen und mit automatischer Cluster-Extraktion nach der using-Extraktionsmethode). Andere Java-Implementierungen umfassen die Weka- Erweiterung (keine Unterstützung für die -Cluster-Extraktion).

Das R- Paket "dbscan" enthält eine C++-Implementierung von OPTICS (mit sowohl traditioneller dbscan-ähnlicher als auch ξ-Cluster-Extraktion) unter Verwendung eines kd-Baums zur Indexbeschleunigung nur für die euklidische Distanz.

Python-Implementierungen von OPTICS sind in der PyClustering- Bibliothek und in scikit-learn verfügbar . HDBSCAN* ist in der hdbscan- Bibliothek verfügbar .

Languages

In other projects