imported>Corpophiliac am 2. März 2024 um 12:50 Uhr

2024-03-02T12:50:45Z

Neue Seite

'''OPTICS''' ({{enS|Ordering Points To Identify the Clustering Structure|de=[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 (Informatiker)|Jörg Sander]] entwickelt.<ref>{{Literatur |Autor=Mihael Ankerst, Markus M. Breunig, [[Hans-Peter Kriegel]], Jörg Sander |Titel=OPTICS: Ordering Points To Identify the Clustering Structure |Sammelwerk=ACM SIGMOD international conference on Management of data |Verlag=ACM Press |Datum=1999 |Seiten=49–60 |Online=[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.129.6542 CiteSeerX]}}</ref> Das Grundprinzip des Algorithmus entstammt [[DBSCAN]],<ref>{{Literatur |Autor=Martin Ester, [[Hans-Peter Kriegel]], Jörg Sander, Xiaowei Xu |Hrsg=Evangelos Simoudis, Jiawei Han, Usama M. Fayyad |Titel=A density-based algorithm for discovering clusters in large spatial databases with noise |Sammelwerk=Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96) |Verlag=AAAI Press |Datum=1996 |ISBN=1-57735-004-9 |Seiten=226–231 |Online=[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.71.1980 CiteSeerX]}}</ref> 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 <math>\varepsilon</math>-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, <math>minPts</math> und <math>\varepsilon</math>. <math>\varepsilon</math> spielt hier jedoch die Rolle einer Maximaldistanz und dient vor allem dazu, die [[Komplexität (Informatik)|Komplexität]] des Algorithmus zu begrenzen. Setzt man <math>\varepsilon = \infty</math>, so ist die Komplexität des Algorithmus <math>O(n^2)</math>, andernfalls kann sie mit Hilfe von geeigneten räumlichen [[Datenbankindex|Indexstrukturen]] wie dem [[R*-Baum]] auf <math>O(n\cdot\log n)</math> reduziert werden. Ohne diese Optimierung hingegen verbleibt die Komplexität bei <math>O(n^2)</math> für endliche <math>\varepsilon</math>.

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

Die „Erreichbarkeitsdistanz“ eines Punktes <math>p</math> von einem zweiten Punkt <math>o</math> ist definiert als <math>\max(kerndistanz(o),dist(o,p))</math>, 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 <math>\varepsilon</math>-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 ==

[[Datei:OPTICS.svg]]

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 <math>\varepsilon \le 0.5</math> und <math>minPts=10</math> verwendet. Diese Visualisierung wurde mit der OPTICS-Implementierung in [[Environment for DeveLoping KDD-Applications Supported by Index-Structures|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 (Datenstruktur)|Heap]]) verwaltet.

<pre>
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)
</pre>

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

<pre>
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)
</pre>

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<ref>{{Literatur |Autor=Markus M. Breunig, [[Hans-Peter Kriegel]], Raymond T. Ng and Jörg Sander |Titel=Principles of Data Mining and Knowledge Discovery |Verlag=Springer |Datum=1999 |ISBN=3-540-66490-4 |Kapitel=OPTICS-OF: Identifying Local Outliers |Seiten=262-270 |Online=http://springerlink.metapress.com/content/76bx6413gqb4tvta/ |DOI=10.1007/b72280}}</ref> 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,<ref>{{Literatur |Autor=E. Achtert, C. Böhm, P. Kröger |Titel=DeLi-Clu: Boosting Robustness, Completeness, Usability, and Efficiency of Hierarchical Clustering by a Closest Pair Ranking |Datum=2006 |Seiten=119 |DOI=10.1007/11731139_16}}</ref> Density-Link-Clustering kombiniert Ideen von [[Hierarchische Clusteranalyse#Single-Linkage|Single-Linkage Clustering]] und OPTICS, eliminiert so den <math>\varepsilon</math>-Parameter und erzielt eine verbesserte Performanz gegenüber OPTICS durch Verwendung eines [[R-Baum]]es als Index.

HiSC<ref>{{Literatur |Autor=E. Achtert, C. Böhm, [[Hans-Peter Kriegel]], P. Kröger, I. Müller-Gorman, A. Zimek |Titel=Finding Hierarchies of Subspace Clusters |Datum=2006 |Seiten=446 |DOI=10.1007/11871637_42}}</ref> ist ein hierarchisches (achsen-paralleles) Unterraum-Clustering-Verfahren.

HiCO<ref>{{Literatur |Autor=E. Achtert, C. Böhm, P. Kröger, A. Zimek |Titel=Mining Hierarchies of Correlation Clusters |Datum=2006 |Seiten=119 |DOI=10.1109/SSDBM.2006.35}}</ref> ist ein hierarchisches Clustering-Verfahren für beliebig orientierte Unterräume.

DiSH<ref>{{Literatur |Autor=E. Achtert, C. Böhm, [[Hans-Peter Kriegel]], P. Kröger, I. Müller-Gorman, A. Zimek |Titel=Detection and Visualization of Subspace Cluster Hierarchies |Datum=2007 |Seiten=152 |DOI=10.1007/978-3-540-71703-4_15}}</ref> ist eine Verbesserung von HiSC für komplexere Hierarchien (mit Schnitten von Unterräumen).

== Verfügbarkeit ==
Eine Referenzimplementierung ist im Software-Paket [[Environment for DeveLoping KDD-Applications Supported by Index-Structures|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<ref>{{Internetquelle |url=https://scikit-learn.org/stable/modules/generated/sklearn.cluster.OPTICS.html#sklearn.cluster.OPTICS |titel=sklearn.cluster.OPTICS — scikit-learn 0.21.2 documentation |abruf=2019-07-03}}</ref>.

== Einzelnachweise ==
<references />

[[Kategorie:Clusteranalyse]]
[[Kategorie:Abkürzung]]

OPTICS - Versionsgeschichte

imported>Corpophiliac am 2. März 2024 um 12:50 Uhr