Clustering methods

У кластеризації немає правильної відповіді, з якою можна звіритися, тож звичний спосіб обрати метод — спробувати кілька й залишити найкращу оцінку — тут не працює. Його місце займає перший стовпець: кожен із цих алгоритмів кодує інше уявлення про те, чим кластер є, і корисне питання — яке з них відповідає тому, що ви шукаєте.

Найважливіший поділ — пласкі проти непласких

K-means, бісекційний k-means і гаусові суміші припускають, що кластери — це згустки. Вони різняться тим, наскільки гнучкий згусток: модель суміші підганяє еліпси будь-якої орієнтації, і «KMeans можна розглядати як окремий випадок гаусової суміші з однаковою коваріацією для кожної компоненти» [1, §2.3.1], — але всі вони питають: «до якого центру ця точка найближча?».

Ціна цього припущення точна. Цільова функція k-means «припускає, що кластери опуклі та ізотропні», і «погано реагує на видовжені кластери чи многовиди неправильної форми» [1, §2.3.2].

DBSCAN, HDBSCAN і спектральна кластеризація цього не припускають. DBSCAN «розглядає кластери як області високої щільності, розділені областями низької щільності», і «через такий досить загальний погляд кластери, знайдені DBSCAN, можуть мати будь-яку форму, на відміну від k-means, що припускає опуклу форму кластерів» [1, §2.3.7]. Спектральна кластеризація доходить туди інакше: вона вкладає матрицю спорідненості й кластеризує власні вектори [1, §2.3.5], тож критерієм стає зв’язність, а не відстань.

Непласкі методи — відповідь, «коли кластери мають специфічну форму, тобто є непласким многовидом, і стандартна евклідова відстань — не та метрика» [1, §2.3.1].

Два стовпці, які ніхто не читає, доки не стане запізно

Викиди. Лише методи щільності мають категорію «ця точка не належить жодному кластеру». Усі інші кудись відносять кожну точку, а в k-means одна далека точка тягне центр до себе. Якщо у ваших даних є сміття, це рішення алгоритм ухвалює за вас.

Нові точки. Документація називає це індуктивним і трансдуктивним, і відмінність суто операційна: трансдуктивні методи «не призначені для застосування до нових, небачених даних» [1, §2.3.1]. K-means і суміші можуть позначити нову точку за мікросекунди. DBSCAN, спектральна й агломеративна кластеризація не можуть — треба перенавчати. Для всього, що має працювати в продакшні на даних, що надходять, цей стовпець сам вирішує вибір.

Ієрархічні методи відповідають на інше питання

Агломеративна кластеризація «будує вкладені кластери, послідовно зливаючи чи розщеплюючи їх», представлені «як дерево (або дендрограма)», корінь якого містить усе, а листки — окремі зразки [1, §2.3.6]. Вам не треба обирати k заздалегідь: ви обираєте, де різати, потім, уже побачивши структуру.

Зв’язування Ward — те, яке варто знати, бо це цільова функція k-means, досягнута іншим шляхом: воно «мінімізує суму квадратів відхилень усередині всіх кластерів. Це підхід мінімізації дисперсії, і в цьому сенсі він схожий на цільову функцію k-means, але розв’язується агломеративним ієрархічним підходом» [1, §2.3.6].

Що обрати

Почніть із k-means, якщо очікуєте згустки й маєте багато даних, — із D²-sampling для початкових центрів і кількома перезапусками, бо один запуск із випадкових точок набагато частіше приземляється погано, ніж ні [2, §3.1]. Наскільки часто, див. k-means.

Переходьте на HDBSCAN, коли не знаєте k, коли форми неправильні або коли деякі точки мають право не належати нікуди. Він справляється зі «змінною щільністю кластерів» [1, §2.3.1], а саме цей параметр робить простий DBSCAN важким у налаштуванні.

Беріть гаусову суміш, коли вам потрібні ймовірності, а не жорсткі мітки, або коли кластери видовжені в різних напрямках.

Беріть агломеративну кластеризацію, коли суть — в ієрархії: таксономії, вкладені сегменти, усе, де «скільки груп?» — питання, а не вхідні дані [1, §2.3.6].

Беріть спектральну кластеризацію для невеликої кількості зв’язних, викривлених кластерів. Вона «добре працює для невеликої кількості кластерів, але не рекомендована для багатьох» [1, §2.3.5].

Одне застереження для кожного рядка. Жоден із цих методів не може сказати, чи справжня знайдена ним структура. Дані з одного згустку вони розбивають так само охоче, як дані зі справжніми групами, і результат виглядає однаково. Що б ви тут не отримали, це гіпотеза, яку треба перевірити чимось поза самою кластеризацією.