Алгоритм DBSCAN

Плотностные алгоритмы

Алгоритм Fuzzy C-Means

Нечеткие методы - это методы, основанные не на бинарной логике - где все четко - элемент либо принадлежит одному кластеру, либо другому - а на предположении, что каждый элемент в какой-то степени принадлежит определенному кластеру. m - мера нечеткости, она как раз определяет нечеткость алгоритма. Минимизируемая функция почти аналогична hard c-means:

0. Выбираем число классов M, меру нечеткости функцию расстояний d(c,x) (обычно d(c,x) = | | x − c | | ²), критерий окончания поиска 0 < ε < 1. Задаем матрицу весов принадлежности точки к кластеру с центром c_j для всех точек и кластеров (можно взять принадлежности к кластеру из k-means или просто по рандому, ограничения для для (вытекают в общем из определения нечеткой принадлежности)).

1. Вычисляем центроиды :

2. Перевычисляем веса :

3. Проверяем | | U^k − U^{k − 1} | | < ε (чаще всего достаточно - если да, то заканчиваем, если нет, то переходим к шагу 1.

Другой класс алгоритмов - плотностные. Они так называются потому, что определяют кластер как группу объектов,расположенных достаточно кучно. Под кучностью понимают то, что в эпсилон-окрестности точки есть некоторое минимальное количество других объектов: d(x_i,x_j) < ε для некоторого количества j > Minpts.

Алгоритм DBSCAN обычно проводится над данными, упорядоченными в R-деревья (для удобства выборки окрестных точек). Но в общем случае этого не требует.

0. Выбираем окрестность ε, в которой мы будем требовать наличия Minpts объектов, и сам Minpts.

1. Берем произвольный еще не обработанный объект. Проверяем для него, что в эпсилон-окрестности точки есть некоторое минимальное количество других объектов: d(x_i,x_j) < ε для некоторого количества j > Minpts. Если это не так, то очевидно, что эта точка - шум. Берем следующую.

2. Если это не так, то помечаем эту точку как принадлежащую кластеру. Это так называемая корневая точка. Заносим окружающие ее точки в отдельную категорию.

2.1. Для каждой еще не обработанной точки из этой категории сначала помечаем ее как принадлежащую кластеру, а затем проверяем то же самое: что в эпсилон-окрестности точки есть некоторое минимальное количество других объектов: d(x_i,x_j) < ε для некоторого количества j > Minpts. Если это так, то заносим эти точки в эту же категорию.

2.2. После проверки выносим точку из этой временной категории. Очевидно, что рано или поздно точки в данной категории кончатся (мы достигнем границ кластера, где правило кучности не выполняется). Тогда переходим к шагу 1. Иначе возвращаемся к шагу 2.1.

Этот алгоритм имеет сложность O(NlogN). Очевидно, что основным его недостатком является неспособность связывать кластеры через узкие места, где правило плотности не выполняется.