DBSCAN

Dbscan ( gęstość przestrzenna klastry oparte na aplikacji z hałasem ) to algorytm dla danych rozdzielaniu zaproponowany w 1996 roku przez Martina Ester, Hans-Peter Kriegel, Jörg Sander i Xiaowei Xu. Jest to algorytm pomiaru gęstości w miarę, który polega na szacowanej gęstości klastrów w celu wykonania partycjonowania.

Zasada ogólna

Algorytm DBSCAN wykorzystuje 2 parametry: odległość i minimalną liczbę punktów, które muszą znajdować się w promieniu, aby te punkty zostały uznane za klaster. Parametry wejściowe są zatem oszacowaniem gęstości punktowej klastrów. Podstawową ideą algorytmu jest zatem, dla danego punktu, odtworzenie jego sąsiedztwa i sprawdzenie, czy rzeczywiście zawiera on punkty lub więcej. Ten punkt jest następnie uważany za część klastra. Następnie krok po kroku przechodzimy przez sąsiedztwo , aby znaleźć wszystkie punkty gromady. ϵ{\ displaystyle \ epsilon}MjanieP.ts{\ displaystyle MinPts}ϵ{\ displaystyle \ epsilon}ϵ{\ displaystyle \ epsilon}MjanieP.ts{\ displaystyle MinPts}ϵ{\ displaystyle \ epsilon}

Algorytm

DBSCAN(D, eps, MinPts) C = 0 pour chaque point P non visité des données D marquer P comme visité PtsVoisins = epsilonVoisinage(D, P, eps) si tailleDe(PtsVoisins) < MinPts marquer P comme BRUIT sinon C++ etendreCluster(D, P, PtsVoisins, C, eps, MinPts) etendreCluster(D, P, PtsVoisins, C, eps, MinPts) ajouter P au cluster C pour chaque point P' de PtsVoisins si P' n'a pas été visité marquer P' comme visité PtsVoisins' = epsilonVoisinage(D, P', eps) si tailleDe(PtsVoisins') >= MinPts PtsVoisins = PtsVoisins U PtsVoisins' si P' n'est membre d'aucun cluster ajouter P' au cluster C epsilonVoisinage(D, P, eps) retourner tous les points de D qui sont à une distance inférieure à epsilon de P

Struktura rozwiązania

Punkty zbioru danych są podzielone na 3 typy:

• Punkty centralne ( punkt centralny )
• Punkty graniczne ( punkt graniczny )
• Wartości odstające ( problemy z hałasem )

Punkty centralne

Mówi się, że punkt w zbiorze danych ma kluczowe znaczenie, jeśli:

1. Jego sąsiedztwo jest gęste

Punkty te tworzą połączone komponenty niezależnie od kolejności eksploracji zbioru danych.

Punkty graniczne

Punkt w zbiorze danych jest uważany za granicę, jeśli:

1. To nie jest centralny punkt
2. Należy do sąsiedztwa centralnego punktu

Punkty te gromadzą się wokół połączonych komponentów, tworząc grupy. Te grupy są powszechnie nazywane ich angielską nazwą: Clusters .

W przeciwieństwie do połączonych komponentów tworzenie klastrów zależy od kolejności eksploracji zbioru danych. Rzeczywiście, punkt graniczny jest przypisywany do pierwszego klastra napotkanego podczas etapu ekspansji. Oprócz kolejności eksploracji punkty te są wrażliwe na różne implementacje algorytmu DBSCAN.

Odstające

Punkt w zbiorze danych jest uważany za wartość odstającą, jeśli:

1. To nie jest centralny punkt
2. To nie jest punkt graniczny

Punkty te są zatem wszystkimi innymi punktami w zbiorze danych.

Uważaj, nazwa nadana tym punktom może wprowadzać w błąd, ponieważ ich oznaczenie zależy od wybranych parametrów.

Podstawowe pojęcia matematyczne

Sąsiedztwo punktu

Pojęcie sąsiedztwa jest podstawowym pojęciem leżącym u podstaw metody DBSCAN. Pozwala matematycznie zdefiniować gęste sąsiedztwa, które są wykorzystywane do lokalizacji punktów centralnych i ekspansji skupisk.

Odległość między punktami

W matematyce nazywamy odległość w zbiorze E każdej mapie D zdefiniowany w produkcie E 2 = E x E i wartości w zestawie ℝ + z dodatnich liczb rzeczywistych ,

re:mi×mi→R+{\ Displaystyle d: E \ razy E \ do \ mathbb {R} ^ {+}}

sprawdzanie następujących właściwości

Nazwisko	własność
symetria	∀(w,b)∈mi2, re(w,b)=re(b,w){\ Displaystyle \ forall (a, b) \ w E ^ {2}, \ d (a, b) = d (b, a)}
separacja	∀(w,b)∈mi2, re(w,b)=0⇔w=b{\ Displaystyle \ forall (a, b) \ w E ^ {2}, \ d (a, b) = 0 \ Leftrightarrow a = b}
nierówność trójkątna	∀(w,b,vs)∈mi3, re(w,vs)≤re(w,b)+re(b,vs){\ Displaystyle \ forall (a, b, c) \ in E ^ {3}, \ d (a, c) \ równoważnik d (a, b) + d (b, c)}

Wybór odległości między punktami jest niejawnym parametrem w metodzie DBSCAN.

W przypadku DBSCAN zwykle używana jest odległość euklidesowa.

Epsilon ray open ball

W zwykłej przestrzeni, jak w każdej przestrzeni metrycznej  : (mi,re){\ displaystyle (E, d)}

Otwarty piłka jest zbiorem punktów w przestrzeni , których odległość od punktu jest mniejsze niż  : b(p,ϵ){\ Displaystyle B (p, \ epsilon) \,}M{\ displaystyle M}mi{\ displaystyle E}p{\ displaystyle p}ϵ{\ displaystyle \ epsilon}

b(p,ϵ)={M∈mi∣re(M,p)<ϵ}{\ Displaystyle B (p, \ epsilon) = \ lewo \ {M \ w E \, \ mid \, d (M, p) <\ epsilon \ prawej \}}

Punkt jest wtedy nazywany środkiem otwartej piłki i nazywany jest promieniem otwartej piłki . p{\ displaystyle p}b(p,ϵ){\ Displaystyle B (p, \ epsilon) \,}ϵ{\ displaystyle \ epsilon}b(p,ϵ){\ Displaystyle B (p, \ epsilon) \,}

Charakterystyka piłek zależy od dwóch elementów:

1. Kształt kulek jest powiązany z odległością (parametr domyślny w DBSCAN).re{\ displaystyle d}
2. Pokrywana przestrzeń zależy od wybranego promienia (parametr jawny dla DBSCAN).ϵ{\ displaystyle \ epsilon}

Naprzeciwko otwartej kuli z punktem środkowym i promieniem jest reprezentowana w dwuwymiarowej przestrzeni dla odległości euklidesowej. Niebieska powierzchnia reprezentuje otwartą kulę : odpowiada to sąsiednim obszarowi wyszukiwania algorytmu DBSCAN. p{\ displaystyle p}ϵ{\ displaystyle \ epsilon}re{\ displaystyle d}b(p,ϵ){\ Displaystyle B (p, \ epsilon) \,}

Okolice Epsilon

Sąsiedztwo punktu jest zbiorem punktów w zbiorze danych znajduje się w otwartym w kulkach iw promieniu  : ϵ{\ displaystyle \ epsilon}Vϵ(p){\ Displaystyle V _ {\ epsilon} (p)}p{\ displaystyle p}q{\ displaystyle q}re{\ displaystyle D}p{\ displaystyle p}ϵ{\ displaystyle \ epsilon}

Vϵ(p)={q∈re∣re(q,p)<ϵ}{\ Displaystyle V _ {\ epsilon} (p) = \ lewo \ {q \ w D \, \ mid \, d (q, p) <\ epsilon \ prawej \}}

Wybrane wartości zadane danych są oparte na otwartych kulkach i dlatego zależą od następujących parametrów:

1. Odległość między punktami ire{\ displaystyle d}p{\ displaystyle p}q{\ displaystyle q}
2. Promień wyszukiwania wokół punktuϵ{\ displaystyle \ epsilon}p{\ displaystyle p}

Po przeciwnej stronie, sąsiedztwo punktu zostało przedstawione w przestrzeni o wymiarze 2 z odległością euklidesową. Czerwone kropki to punkty w zbiorze danych, które należą do sąsiedztwa punktu , a kropki w kolorze indygo reprezentują punkty w zbiorze danych , które nie należą do sąsiedztwa punktu . W przypadku algorytmu DBSCAN ważna jest liczba czerwonych kropek. ϵ{\ displaystyle \ epsilon}p{\ displaystyle p}q{\ displaystyle q}re{\ displaystyle D}ϵ{\ displaystyle \ epsilon}p{\ displaystyle p}q{\ displaystyle q}re{\ displaystyle D}ϵ{\ displaystyle \ epsilon}p{\ displaystyle p}

Gęsta okolica w Epsilon

Sąsiedztwo mówi się gęsty, jeżeli jego liczność jest większa lub równa . ϵ{\ displaystyle \ epsilon}Vϵ(p){\ Displaystyle V _ {\ epsilon} (p)}mjanieP.ts{\ displaystyle minPts}

∣Vϵ(p)∣⩾mjanieP.ts{\ Displaystyle \ mid V _ {\ epsilon} (p) \ mid \ geqslant minPts}

Ta definicja jest pierwszą, która zależy od 3 parametrów DBSCAN:

1. Minimalna liczba punktów, aby okolica została uznana za gęstą.mjanieP.ts{\ displaystyle minPts}
2. Promień sąsiedztwa wokół rozważanego punktu .ϵ{\ displaystyle \ epsilon}p{\ displaystyle p}
3. Odległość między punktami.re{\ displaystyle d}

Używając poprzedniej ilustracji, naprawiono. Jeśli jest ustalony na 3 punkty, to rozważane sąsiedztwo jest wyraźnie gęste. I odwrotnie, jeśli jest ustawiony na 50 punktów, to sąsiedztwo wyraźnie nie jest gęste. ϵ{\ displaystyle \ epsilon}mjanieP.ts{\ displaystyle minPts}mjanieP.ts{\ displaystyle minPts}

Relacje oparte na gęstości

Poniższe relacje binarne służą do przeprowadzania demonstracji metody DBSCAN, a bardziej ogólnie w uczeniu się bez nadzoru opartym na gęstości.

Bezpośrednio dostępne według gęstości

Punkt w zbiorze danych jest bezpośrednio dostępny według gęstości z innego punktu, jeśli: q{\ displaystyle q}re{\ displaystyle D}p{\ displaystyle p}

1. Vϵ(p){\ Displaystyle V _ {\ epsilon} (p)} jest gęsty
2. q∈Vϵ(p){\ displaystyle q \ in V _ {\ epsilon} (p)}

Innymi słowy, punkty bezpośrednio dostępne dla gęstości są punktami gęstego sąsiedztwa.

Taka relacja jest graficznie reprezentowana przez strzałkę biegnącą od punktu do punktu . p{\ displaystyle p}q{\ displaystyle q}

Dostępne według gęstości

Punkt w zbiorze danych jest dostępny według gęstości z innego punktu, jeśli istnieje uporządkowana sekwencja punktów, na przykład: q{\ displaystyle q}re{\ displaystyle D}p{\ displaystyle p}(p1,p2,...,pnie){\ displaystyle (p_ {1}, p_ {2}, ..., p_ {n})}

1. p1=p{\ displaystyle p_ {1} = p}
2. pja+1{\ displaystyle p_ {i + 1}} jest bezpośrednio dostępny przez gęstość z pja{\ displaystyle p_ {i}}
3. pnie=q{\ displaystyle p_ {n} = q}

Punkt jest dostępny według gęstości z innego punktu, jeśli istnieje ścieżka prowadząca od robaków . q{\ displaystyle q}p{\ displaystyle p}p{\ displaystyle p}q{\ displaystyle q}

Gęsto połączone

Punkt w zbiorze danych jest gęsto połączony z innym punktem, jeśli: q{\ displaystyle q}re{\ displaystyle D}p{\ displaystyle p}

1. o∈re{\ Displaystyle o \ in D}
2. p{\ displaystyle p} jest dostępny przez gęstość z o{\ displaystyle o}
3. q{\ displaystyle q} jest dostępny przez gęstość z o{\ displaystyle o}

Punkt i punkt są gęsto połączone, jeśli istnieją dwie ścieżki strzałek, które zaczynają się od tego samego punktu i prowadzą odpowiednio do punktów i . q{\ displaystyle q}p{\ displaystyle p}o{\ displaystyle o}p{\ displaystyle p}q{\ displaystyle q}

Estymacja parametrów

Oszacowanie parametrów i nie jest łatwym problemem, ponieważ te dwie wartości są nierozerwalnie związane z topologią przestrzeni, która ma być podzielona. Zbyt niska wartość i / lub zbyt duża wartość może uniemożliwić algorytmowi propagację klastrów. I odwrotnie, zbyt duża wartość i / lub zbyt niska wartość dla może spowodować, że algorytm zwróci tylko szum. Heurystyczny pozwala na ustalenie wspólnie i dla pewnej przestrzeni może być wyrażona wzorem: ϵ{\ displaystyle \ epsilon}MjanieP.ts{\ displaystyle MinPts}ϵ{\ displaystyle \ epsilon}MjanieP.ts{\ displaystyle MinPts}ϵ{\ displaystyle \ epsilon}MjanieP.ts{\ displaystyle MinPts}ϵ{\ displaystyle \ epsilon}MjanieP.ts{\ displaystyle MinPts}

• ϵ{\ displaystyle \ epsilon} : oblicz dla każdego punktu w przestrzeni odległość do najbliższego sąsiada. Przyjmij takie, aby „wystarczająco duża” część punktów miała odległość do najbliższego sąsiada mniejszą niż ;ϵ{\ displaystyle \ epsilon}ϵ{\ displaystyle \ epsilon}
• MjanieP.ts{\ displaystyle MinPts} : oblicz dla każdego punktu liczbę jego sąsiadów w promieniu wielkości (wielkość jego sąsiedztwa). Postaraj się , aby „wystarczająco duża” część punktów miała więcej punktów w swoim sąsiedztwie.ϵ{\ displaystyle \ epsilon}ϵ{\ displaystyle \ epsilon}MjanieP.ts{\ displaystyle MinPts}MjanieP.ts{\ displaystyle MinPts}ϵ{\ displaystyle \ epsilon}

Przez „dostatecznie duże” rozumie się na przykład % lub % punktów. 95{\ displaystyle 95}90{\ displaystyle 90}

Inną heurystyką dla przypadków 2D (zdefiniowaną w oryginalnym artykule DBSCAN) jest ustawienie wartości na 4 i wykreślenie krzywej (posortowanej w porządku malejącym) odległości od każdego punktu do ich czwartego plus bliskiego sąsiada. Następnie ustawiliśmy wartość „punktu progowego” wskazanego na wykresie. Jeśli ten próg nie jest wyraźnie identyfikowalny, użytkownik może go ustalić przez oszacowanie procentu szumu w zestawie danych: jest zatem taki, że tylko składniki szumu mają odległość do ich czwartego najbliższego sąsiada większą niż . MjanieP.ts{\ displaystyle MinPts}ϵ{\ displaystyle \ epsilon}ϵ{\ displaystyle \ epsilon}ϵ{\ displaystyle \ epsilon}

Zalety i wady

Algorytm jest bardzo prosty i nie wymaga określania liczby klastrów do znalezienia. Jest w stanie poradzić sobie z wartościami odstającymi, usuwając je z procesu partycjonowania. Klastry nie muszą być rozdzielane liniowo (tak jak na przykład w przypadku algorytmu k-średnich ). Nie jest jednak w stanie zarządzać klastrami o różnej gęstości.

Powiązane artykuły

• OPTYKA

Bibliografia

1. M. Ester, H.-P. Kriegel, J. Sander i X. Xu, „A density-based algorytm for discovery clusters in large przestrzenne databases with noise”, Proceedings of the 2nd International Conference on Knowledge Discovery and Data mining, 1996, s. 226-231.
2. (w) Michael Hahsler Matthew Piekenbrock i Derek Doran , „  dbscan: Fast Density-Based Clustering with R  ' , Journal of Statistical Software , vol.  91, n o  1,2019( ISSN  1548-7660 , DOI  10.18637 / jss.v091.i01 , czytaj online , dostęp 9 marca 2020 )
3. alitouka , spark_dbscan: algorytm klastrowania DBSCAN na szczycie Apache Spark ,18 sierpnia 2017( czytaj online )

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">