🏦 Детектор відмивання грошей — кластеризація DBSCAN наживо

DBSCAN (кластеризація на основі щільності для застосунків із шумом, Ester та ін., 1996) групує точки, які щільно розташовані в просторі ознак, позначаючи точки в областях низької щільності як шум. На відміну від k-means, DBSCAN не вимагає заздалегідь обирати кількість кластерів, може знаходити кластери довільної форми, а не лише округлі плями, і явно виокремлює категорію викидів замість того, щоб примусово відносити кожну точку до якогось кластера. Це робить його добре придатним для виявлення шахрайства й аномалій, де кількість підозрілих груп невідома, а більшість рахунків є звичайним фоновим шумом.

Для обраного радіуса epsilon (ε) та мінімальної кількості сусідів minPts точка є кореневою, якщо принаймні minPts точок (включно з нею самою) лежать у її ε-околі — вона перебуває в справді щільній області. Межова точка сама не відповідає цьому порогу щільності, але лежить в ε-околі якоїсь кореневої точки, тож вона щільнісно досяжна й приєднується до кластера цієї кореневої точки. Будь-яка точка, що не є ні кореневою, ні щільнісно досяжною від кореневої, позначається як шум — викид, що не належить жодному кластеру.

Epsilon задає радіус околу, що досліджується навколо кожної точки; minPts задає, скільки сусідів (включно із самою точкою) потрібно, щоб точка вважалась достатньо щільною для статусу кореневої. Збільшення ε або зменшення minPts полегшує досягнення порогу щільності, тож кластери зростають і зливаються, а менше точок опиняються в шумі. Зменшення ε або збільшення minPts робить поріг суворішим, тож кластерами лишаються тільки найщільніші групи, а все розрідженіше перекласифіковується як шум або розпадається на менші кластери.

Просте правило на кшталт «позначати будь-який рахунок з понад N транзакціями на тиждень» розглядає кожен рахунок окремо й ігнорує те, як рахунки пов'язані між собою. Кільця відмивання грошей зазвичай виявляються як невелика група рахунків, що незвично щільно згруповані одразу за кількома ознаками — подібна частота транзакцій, подібна сума (часто трохи нижче порогу звітності — патерн, що зветься структуруванням) і висока центральність у мережі — залишаючись при цьому окремо непримітними. DBSCAN виявляє саме це: компактну, незвично щільну групу взаємно близьких точок, яку порогові правила за однією ознакою не можуть побачити, бо жодне окреме значення ознаки не є екстремальним само по собі.

Точка q безпосередньо щільнісно досяжна від кореневої точки p, якщо q лежить в ε-околі p. Щільнісна досяжність — це транзитивне замикання цього відношення: q щільнісно досяжна від p, якщо існує ланцюжок кореневих точок p = p1, p2, ..., pn = q, де кожна безпосередньо щільнісно досяжна від попередньої. Дві точки p і q є щільнісно зв'язаними, якщо існує якась коренева точка o, від якої досяжні і p, і q. Кластери DBSCAN — це саме максимальні множини щільнісно зв'язаних точок; така ланцюгова структура дозволяє одному кластеру звиватися через неопуклі, нерегулярні області, а не лише утворювати округлі плями.

DBSCAN використовує один глобальний ε і minPts для всього набору даних, тож має труднощі, коли кластери мають дуже різну щільність — налаштування, підібране під щільне кільце відмивання грошей, може поглинути розріджений звичайний кластер у шум, або навпаки (алгоритми на кшталт OPTICS і HDBSCAN вирішують це підходом зі змінною щільністю). Він також масштабується приблизно квадратично за кількістю точок без просторового індексу, такого як k-d дерево, а його результати залежать від вибору розумної метрики відстані та масштабування ознак, оскільки ознаки в дуже різних масштабах можуть спотворити те, які точки вважаються «близькими».