Algorytm OPTYKA - OPTICS algorithm

Porządkowanie punktów do identyfikacji struktury klastrowania ( OPTICS ) to algorytm do wyszukiwania klastrów opartych na gęstości w danych przestrzennych. Prezentowali go Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel i Jörg Sander. Jego podstawowa idea jest podobna do DBSCAN , ale rozwiązuje jedną z głównych słabości DBSCAN: problem wykrywania znaczących klastrów w danych o różnej gęstości. W tym celu punkty bazy danych są (liniowo) uporządkowane w taki sposób, że najbliższe przestrzennie punkty stają się sąsiadami w porządkowaniu. Dodatkowo dla każdego punktu reprezentującego gęstość, która musi być zaakceptowana dla klastra, przechowywana jest specjalna odległość, aby oba punkty należały do tego samego klastra. Jest to reprezentowane jako dendrogram .

Podstawowy pomysł

Podobnie jak DBSCAN , OPTICS wymaga dwóch parametrów: $ε$ , który opisuje maksymalną odległość (promień) do rozważenia, oraz $MinPts$ , opisujący liczbę punktów wymaganych do utworzenia klastra. Punkt $p$ jest punktem centralnym, jeśli przynajmniej punkty $MinPts$ znajdują się w jego otoczeniu $ε$ (w tym sam punkt $p$ ). W przeciwieństwie do DBSCAN , OPTICS uwzględnia również punkty, które są częścią gęściej upakowanego klastra, więc każdemu punktowi przypisywana jest odległość rdzenia, która opisuje odległość do najbliższego punktu $MinPts$ : ${\ Displaystyle N_ {\ varepsilon } (p)}$

{\ Displaystyle {\ tekst {odległości rdzenia}} _ {\ mathit {\ varepsilon, MinPts}} (p) = {\ zacząć {przypadki} {\ tekst {NIEZDEFINIOWANY}} i {\ tekst {jeśli}} | N_ {\varepsilon }(p)|<{\mathit {MinPts}}\\{\mathit {MinPts}}{\text{-ta najmniejsza odległość w }}N_{\varepsilon }(p)&{\text{w przeciwnym razie }}\end{przypadki}}}

Odległość osiągalności innego punktu $o$ od punktu $p$ jest albo odległością między $o$ i $p$ , albo odległością rdzenia $p$ , w zależności od tego, która jest większa:

{\ Displaystyle {\ tekst {odległości zasięgu}} _ {\ mathit {\ varepsilon, MinPts}} (o, p) = {\ rozpocząć {przypadki} {\ tekst {NIEZDEFINIOWANY}} i {\ tekst {jeśli}} |N_{\varepsilon }(p)|<{\mathit {MinPts}}\\\max({\text{odległości rdzenia}}_{\mathit {\varepsilon ,MinPts}}(p),{\text {odleg}}(p,o))&{\text{inaczej}}\end{przypadki}}}

Jeśli $p$ i $o$ są najbliższymi sąsiadami, musimy założyć, że $p$ i $o$ należą do tego samego klastra. $\varepsilon '<\varepsilon$

Zarówno odległość rdzenia, jak i odległość osiągalności są nieokreślone, jeśli nie jest dostępny wystarczająco gęsty klaster (wrt $ε$ ). Biorąc pod uwagę wystarczająco duże $ε$ , to się nigdy nie zdarza, ale wtedy każde zapytanie $ε$ -neighborhood zwraca całą bazę danych, co skutkuje uruchomieniem . Stąd parametr $ε$ jest wymagany do odcięcia gęstości skupień, które już nie są interesujące i przyspieszenia działania algorytmu. ${\ Displaystyle O (n ^ {2})}$

Ściśle rzecz biorąc, parametr $ε$ nie jest konieczny. Można go po prostu ustawić na maksymalną możliwą wartość. Kiedy jednak dostępny jest indeks przestrzenny, odgrywa on praktyczną rolę w odniesieniu do złożoności. OPTICS abstrahuje od DBSCAN, usuwając ten parametr, przynajmniej do tego stopnia, że wystarczy podać tylko maksymalną wartość.

Pseudo kod

Podstawowe podejście OPTICS jest podobne do DBSCAN , ale zamiast utrzymywać w zbiorze znane, ale do tej pory nieprzetworzone elementy klastra, są one utrzymywane w kolejce priorytetowej (np. za pomocą indeksowanej sterty ).

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)

W funkcji update() kolejka priorytetowa Seeds jest aktualizowana z -neighborhood i , odpowiednio: $\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 zatem wyprowadza punkty w określonej kolejności, z adnotacją o najmniejszej odległości osiągalności (w oryginalnym algorytmie odległość rdzenia jest również eksportowana, ale nie jest to wymagane do dalszego przetwarzania).

Wyodrębnianie klastrów

Korzystając z wykresu osiągalności (specjalnego rodzaju dendrogramu ), można łatwo uzyskać hierarchiczną strukturę klastrów. Jest to wykres 2D, z kolejnością punktów przetworzonych przez OPTICS na osi X i odległością osiągalności na osi Y. Ponieważ punkty należące do klastra mają małą odległość osiągalności od najbliższego sąsiada, klastry są wyświetlane jako doliny na wykresie osiągalności. Im głębsza dolina, tym gęstsza gromada.

Powyższy obrazek ilustruje tę koncepcję. W lewym górnym obszarze pokazany jest syntetyczny przykładowy zestaw danych. Prawa górna część przedstawia drzewo opinające stworzone przez OPTICS, a dolna pokazuje wykres osiągalności obliczony przez OPTICS. Kolory na tym wykresie są etykietami, a nie obliczane przez algorytm; ale dobrze widać, jak doliny na wykresie odpowiadają skupiskom w powyższym zestawie danych. Żółte punkty na tym obrazie są uważane za szum, a na ich wykresie osiągalności nie ma doliny. Zazwyczaj nie są one przypisywane do klastrów, z wyjątkiem wszechobecnego klastra „wszystkie dane” w wyniku hierarchicznym.

Wyodrębnianie klastrów z tego wykresu można wykonać ręcznie, wybierając zakres na osi x po inspekcji wizualnej, wybierając próg na osi y (wynik jest wtedy podobny do wyniku klastrowania DBSCAN z tymi samymi parametrami i minPts; tutaj wartość 0,1 może dać dobre wyniki) lub przez różne algorytmy, które próbują wykryć doliny na podstawie stromości, wykrywania kolan lub lokalnych maksimów. Uzyskane w ten sposób klastry są zwykle hierarchiczne i nie można ich osiągnąć za pomocą pojedynczego uruchomienia DBSCAN. $\varepsilon$

Złożoność

Podobnie jak DBSCAN , OPTICS przetwarza każdy punkt raz i wykonuje jedno zapytanie -neighborhood podczas tego przetwarzania. Biorąc pod uwagę indeks przestrzenny, który przyznaje zapytanie sąsiedztwa w czasie wykonywania, uzyskiwany jest ogólny czas wykonywania . Autorzy oryginalnego artykułu OPTICS podają rzeczywisty stały współczynnik spowolnienia wynoszący 1,6 w porównaniu z DBSCAN. Zauważ, że wartość może mieć duży wpływ na koszt algorytmu, ponieważ zbyt duża wartość może podnieść koszt zapytania sąsiedztwa do liniowej złożoności. $\varepsilon$ ${\ Displaystyle O (\ log n)}$ ${\ Displaystyle O (n \ cdot \ log n)}$ $\varepsilon$

W szczególności wybór (większy niż maksymalna odległość w zestawie danych) jest możliwy, ale prowadzi do kwadratowej złożoności, ponieważ każde zapytanie o sąsiedztwo zwraca pełny zestaw danych. Nawet jeśli nie jest dostępny żaden indeks przestrzenny, wiąże się to z dodatkowymi kosztami zarządzania stertą. Dlatego powinny być odpowiednio dobrane do zbioru danych. ${\ Displaystyle \ varepsilon > \ max _ {x, y} d (x, y)}$ $\varepsilon$

Rozszerzenia

OPTICS-OF to algorytm wykrywania wartości odstających oparty na technologii OPTICS. Głównym zastosowaniem jest ekstrakcja wartości odstających z istniejącej serii OPTICS przy niskich kosztach w porównaniu z zastosowaniem innej metody wykrywania wartości odstających. Bardziej znana wersja LOF opiera się na tych samych koncepcjach.

DeLi-Clu, Density-Link-Clustering łączy idee klastrowania z pojedynczym łączem i OPTICS, eliminując ten parametr i oferując poprawę wydajności w porównaniu z OPTICS. $\varepsilon$

HiSC to hierarchiczna metoda grupowania podprzestrzennego ( osiowo -równoległa) oparta na technologii OPTICS.

HiCO to hierarchiczny algorytm grupowania korelacji oparty na technologii OPTICS.

DiSH to ulepszenie w stosunku do HiSC, które może znaleźć bardziej złożone hierarchie.

FOPTICS to szybsza implementacja przy użyciu losowych projekcji.

HDBSCAN* opiera się na udoskonaleniu DBSCAN, wykluczając punkty graniczne z klastrów, a tym samym ściślej przestrzegając podstawowej definicji poziomów gęstości opracowanej przez Hartigana.

Dostępność

Implementacje Java OPTICS, OPTICS-OF, DeLi-Clu, HiSC, HiCO i DiSH są dostępne w ramach eksploracji danych ELKI (z akceleracją indeksów dla kilku funkcji odległościowych oraz z automatycznym wyodrębnianiem klastrów metodą ekstrakcji ξ). Inne implementacje Java obejmują rozszerzenie Weka (brak obsługi ekstrakcji klastrów ξ).

R pakiet „dbscan” obejmuje C ++ realizacji optyki (z tradycyjnej ekstrakcji klastra dbscan-podobnego i Ę) za pomocą drzewa kd dla przyspieszenia indeksu dla tylko odległości euklidesowej.

Implementacje OPTICS w Pythonie są dostępne w bibliotece PyClustering oraz w scikit-learn . HDBSCAN* jest dostępny w bibliotece hdbscan .

Languages

In other projects