DBSCAN (кластеризація за густиною з виявленням шуму) знаходить кластери як густі області, розділені розрідженими. Він потребує двох параметрів: радіуса ε та кількості minPts.

Три види точок

• Ядрова: має щонайменше minPts точок у межах радіуса ε (рахуючи саму себе).
• Гранична: у межах ε від ядрової точки, але сама недостатньо густа.
• Шум: ані те, ані інше — розріджений викид, що малюється сірим ✕.

Вирощування кластера

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

Порівняння з k-середніх

На відміну від k-середніх, DBSCAN не потребує заздалегідь обирати кількість кластерів — він виявляє стільки густих областей, скільки є. Він також відстежує довільні форми (набори Місяці та Кільця неопуклі, де k-середніх провалюється) і явно повідомляє про викиди як про шум, а не втискає кожну точку в кластер.

Вибір ε та minPts

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