Klastrowanie z DBSCAN

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) to algorytm grupowania, który grupuje blisko siebie punkty na podstawie kryterium gęstości. W przeciwieństwie do innych modeli Clustering, takich jak K-średnie, DBSCAN może identyfikować klastry o dowolnych kształtach i nie wymaga wcześniejszego określenia liczby klastrów. Jest mniej wrażliwy na szum i może obsługiwać klastry o różnej gęstości.

Aby uzyskać satysfakcjonujący wynik przy użyciu algorytmu DBSCAN zakłada się, że różne klastry w danych mają względnie podobną gęstość, gdzie przez gęstość rozumiemy liczbę punktów, które istnieją w każdym zdefiniowanym sąsiedztwie N(x, ε) przez promień ε i punkt danych x. Twierdzenie to można optycznie zweryfikować, obserwując przykład DBSCAN w środku powyższego zdjęcia, gdzie punkty wokół niebieskiej gromady, które mają nieco inną gęstość, są uważane za część pomarańczowej gromady.

Jedynymi parametrami potrzebnymi do wdrożenia DBSCAN są:

• MinPts = minimalna liczba punktów, które musi mieć sąsiedztwo punktu danych, aby punkt danych można było uznać za główny punkt klastra
• ε = promień sąsiedztwa (tj. jak duże mają być nasze „kręgi” wokół centralnego punktu danych)

1. Core Point : Ten typ punktu danych ma gęstość ≥ MinPts. Oznacza to, że liczba punktów danych w N(x, ε) jest większa lub równa MinPts.

2. Punkt graniczny: Ten typ punktu danych ma gęstość < MinPts, ale odległość (y, cp) ≤ ε, gdzie cp jest punktem rdzenia. Oznacza to, że punkty te nie mają gęstości wymaganej do bycia punktami rdzeniowymi, ale nie są też tak daleko od punktu rdzenia, aby można je było uznać za szum.

Przykład: MinPts = 4, ε = 3, wtedy y jest punktem granicznym

3. Punkt szumu: Ten typ punktu danych ma gęstość < MinPts i odległość (z, cp) ≥ ε. Oznacza to, że nie ma gęstości wymaganej do bycia punktem rdzenia i jest daleko od jakiegokolwiek punktu rdzenia.

Przykład: MinPts = 4, ε = 3, wtedy z jest punktem szumu

I tak, w oparciu o ten proces kategoryzacji punktów danych, algorytm DBSCAN wygląda następująco:

1. Iteruj każdy punkt danych i klasyfikuj go w jednej z tych trzech kategorii
2. Wyeliminuj wszystkie punkty hałasu
3. Rozważmy, że wszystkie punkty rdzeniowe, które leżą blisko siebie, znajdują się w tym samym skupieniu (co oznacza, że ​​jeśli cp_1 i cp_2 są punktami rdzeniowymi, a odległość (cp_1, cp_2) ≤ ε, to uważa się, że cp_1 i cp_2 znajdują się w tym samym skupieniu).
4. Przypisz każdy punkt graniczny w klastrze punktów podstawowych na podstawie ich odległości (punkty graniczne, które leżą dokładnie w punkcie środkowym między dwoma klastrami, należy rozwiązać osobno, może rzucić monetą ;D )