Кластеризація на основі щільності
В даному прикладі групи в основному визначаються як галузі з більш високою непроникністю, ніж інша частина набору даних. Об’єкти в цих рідкісних частинах, які необхідні для поділу всіх компонентів, зазвичай вважаються шумом і прикордонними пунктами.
Найбільш популярним методом кластеризації на основі щільності є DBSCAN (алгоритм просторової кластеризації з присутністю шуму). На відміну від багатьох нових способів він має чітко визначену кластерну складову, звану «досяжність щільності». Подібно кластеризації на основі зв’язків, вона заснована на крапках з’єднання в межах визначених порогів відстані. Однак такий метод збирає лише ті пункти, які задовольняють критерію щільності. У вихідному варіанті, визначеному як мінімальна кількість інших об’єктів в цьому радіусі, кластер складається з усіх предметів, пов’язаних щільністю (які можуть утворювати групу довільної форми, на відміну від багатьох інших методів), а також всіх об’єктів, які знаходяться в межах допустимого діапазону.
Іншим цікавим властивістю DBSCAN є те, що його складність досить низька — він вимагає лінійного кількості запитів діапазону до бази даних. А також незвичайність полягає в тому, що він виявить, по суті, ті ж самі результати (це є детермінованим для основних і шумових точок, але не для граничних елементів) у кожному прогоні. Тому немає ніякої необхідності запускати його кілька разів.
Основний недолік DBSCAN і OPTICS полягає в тому, що вони очікують деякого падіння щільності для виявлення меж кластера. Наприклад, в наборах даних з перекриваються розподілами Гаусса — поширений випадок використання штучних об’єктів — межі кластерів, створювані цими алгоритмами, часто виглядають довільно. Відбувається це, оскільки щільність груп безперервно зменшується. А в наборі даних, що складається із сумішей гауссианов, ці алгоритми майже завжди перевершують такі методи, як EM-кластеризація, які здатні точно моделювати системи такого типу.
Середнє зміщення — це кластерний підхід, при якому кожний об’єкт переміщається в саму щільну область в околиці на основі оцінки всього ядра. Зрештою, об’єкти сходяться до локальних максимумів непроникності. Подібно кластеризації методом к-середніх, ці «атрактори щільності» можуть служити представниками для набору даних. Але середнє зміщення може виявляти кластери довільної форми, аналогічні DBSCAN. Через дорогий ітеративної процедури та оцінки щільності середнє переміщення зазвичай повільніше, ніж DBSCAN або k-Means. Крім того, застосування алгоритму типового зсуву до багатовимірних даних утруднена через нерівномірного поведінки оцінки щільності ядра, що призводить до надмірної фрагментації хвостів кластерів.
