🏦 Detektor prania pieniędzy — klasteryzacja DBSCAN na żywo

DBSCAN (przestrzenna klasteryzacja oparta na gęstości dla aplikacji z szumem, Ester i in., 1996) grupuje punkty, które są ściśle skupione w przestrzeni cech, oznaczając punkty w obszarach o niskiej gęstości jako szum. W przeciwieństwie do k-means, DBSCAN nie wymaga wcześniejszego wyboru liczby klastrów, potrafi znajdować klastry o dowolnym kształcie, a nie tylko okrągłe skupiska, i jawnie tworzy kategorię wartości odstających zamiast wymuszać przypisanie każdego punktu do jakiegoś klastra. Dzięki temu doskonale nadaje się do wykrywania oszustw i anomalii, gdzie liczba podejrzanych grup jest nieznana, a większość kont to po prostu zwykły szum tła.

Dla wybranego promienia epsilon (ε) i minimalnej liczby sąsiadów minPts, punkt jest punktem rdzeniowym, jeśli w jego ε-sąsiedztwie znajduje się co najmniej minPts punktów (łącznie z nim samym) — oznacza to, że leży on w naprawdę gęstym obszarze. Punkt brzegowy sam nie spełnia tego progu gęstości, ale leży w ε-sąsiedztwie jakiegoś punktu rdzeniowego, więc jest gęstościowo osiągalny i dołącza do klastra tego punktu rdzeniowego. Każdy punkt, który nie jest ani punktem rdzeniowym, ani gęstościowo osiągalnym z takiego punktu, jest oznaczany jako szum — wartość odstająca, która nie należy do żadnego klastra.

Epsilon ustala promień sąsiedztwa przeszukiwanego wokół każdego punktu; minPts ustala, ilu sąsiadów (łącznie z samym punktem) jest wymaganych, aby punkt uznać za wystarczająco gęsty, by był punktem rdzeniowym. Zwiększenie ε lub zmniejszenie minPts ułatwia spełnienie progu gęstości, więc klastry rosną i łączą się, a mniej punktów kończy jako szum. Zmniejszenie ε lub zwiększenie minPts zaostrza próg, więc jako klastry przetrwają tylko najściślejsze grupy, a wszystko luźniejsze zostaje przeklasyfikowane jako szum lub rozpada się na mniejsze klastry.

Prosta reguła w rodzaju „oznacz każde konto z więcej niż N transakcjami tygodniowo” traktuje każde konto niezależnie i ignoruje to, jak konta są ze sobą powiązane. Pierścienie prania pieniędzy zwykle ujawniają się jako niewielki zbiór kont, które są niezwykle ściśle skupione jednocześnie wokół kilku cech — podobna częstotliwość transakcji, podobna kwota (często tuż poniżej progu raportowania, wzorzec zwany strukturyzacją) i wysoka centralność w sieci — pozostając przy tym indywidualnie niepozornymi. DBSCAN wykrywa dokładnie to: zwartą, niezwykle gęstą grupę wzajemnie bliskich punktów, której progi oparte na pojedynczej cesze nie widzą, ponieważ żadna pojedyncza wartość cechy nie jest sama w sobie ekstremalna.

Punkt q jest bezpośrednio gęstościowo osiągalny z punktu rdzeniowego p, jeśli q leży w ε-sąsiedztwie p. Gęstościowa osiągalność jest przechodnim domknięciem tej relacji — q jest gęstościowo osiągalny z p, jeśli istnieje łańcuch punktów rdzeniowych p = p1, p2, ..., pn = q, gdzie każdy jest bezpośrednio gęstościowo osiągalny z poprzedniego. Dwa punkty p i q są gęstościowo spójne, jeśli istnieje jakiś punkt rdzeniowy o, z którego zarówno p, jak i q są gęstościowo osiągalne. Klastry DBSCAN to dokładnie maksymalne zbiory gęstościowo spójnych punktów; to łańcuchowanie pozwala pojedynczemu klastrowi wić się przez niewypukłe, nieregularne obszary, zamiast tworzyć wyłącznie okrągłe skupiska.

DBSCAN używa jednego globalnego ε i minPts dla całego zbioru danych, więc ma trudności, gdy klastry mają bardzo różną gęstość — ustawienie dostrojone do ścisłego pierścienia prania pieniędzy może pochłonąć luźny, zwykły klaster jako szum, albo odwrotnie (algorytmy takie jak OPTICS i HDBSCAN rozwiązują to podejściem ze zmienną gęstością). Skaluje się on też z grubsza kwadratowo względem liczby punktów bez indeksu przestrzennego, takiego jak drzewo k-d, a jego wyniki zależą od wyboru sensownej metryki odległości i skalowania cech, ponieważ cechy o bardzo różnych skalach mogą zniekształcać to, które punkty są uznawane za „bliskie”.