ПЛАМЯ кластеризация

Нечеткая кластеризация посредством локальной аппроксимации членства (FLAME) — это алгоритм кластеризации данных , который определяет кластеры в плотных частях набора данных и выполняет назначение кластеров исключительно на основе отношений соседства между объектами. Ключевой особенностью этого алгоритма является то, что отношения соседства между соседними объектами в пространстве признаков используются для ограничения членства соседних объектов в нечетком пространстве членства.

Описание алгоритма FLAME

Алгоритм FLAME в основном разделен на три этапа:

Извлечение информации о структуре из набора данных:
1. Постройте граф окрестностей, чтобы соединить каждый объект с его K-ближайшими соседями (KNN);
2. Оцените плотность каждого объекта на основе его близости к его KNN;
3. Объекты делятся на 3 типа:
  1. Объект поддержки кластера (CSO): объект с плотностью выше, чем у всех его соседей;
  2. Кластерные выбросы: объект с плотностью ниже, чем у всех его соседей, и ниже заранее определенного порога;
  3. остальные.
Локальное/соседнее приближение нечеткого членства :
1. Инициализация нечеткого членства:
  1. Каждой ОГО присваивается фиксированное и полное членство, чтобы представлять один кластер;
  2. Всем выбросам присваивается фиксированное и полное членство в группе выбросов;
  3. Остальные распределяются с равным членством по всем кластерам и группе выбросов;
2. Затем нечеткое членство всех объектов типа 3 обновляется с помощью сходящейся итеративной процедуры, называемой локальным/соседним приближением нечеткого членства , в которой нечеткое членство каждого объекта обновляется линейной комбинацией нечеткого членства его ближайших соседей.
Построение кластера из нечеткого членства двумя возможными способами:
1. Назначение кластера объектов «один к одному» для назначения каждого объекта кластеру, в котором он имеет наивысшее членство;
2. Назначение одного-множеству кластеров объектов, чтобы назначить каждый объект кластеру, в котором его членство превышает пороговое значение.

Проблема оптимизации в FLAME

Локальная/соседская аппроксимация нечетких членов — это процедура, позволяющая минимизировать ошибку локальной/соседской аппроксимации (LAE/NAE), определяемую следующим образом:

E(\{{\boldsymbol {p}}\})=\sum _{{\boldsymbol {x}}\in {\boldsymbol {X}}}{\bigg \|}{\boldsymbol {p(x)}}-\sum _{\boldsymbol {y\in {\mathcal {N}}(x)}}w_{\boldsymbol {xy}}{\boldsymbol {p(y)}}{\bigg \|}^{2}

где ${\boldsymbol {X}}$ представляет собой набор всех объектов типа 3, ${\boldsymbol {p(x)}}$ это нечеткий вектор принадлежности объекта ${\boldsymbol {x}}$ , ${\mathcal {N}}(x)$ множество ближайших соседей ${\boldsymbol {x}}$ , и $w_{\boldsymbol {xy}}$ с $\sum _{\boldsymbol {y\in {\mathcal {N}}(x)}}w_{\boldsymbol {xy}}=1$ – коэффициенты, отражающие относительную близость ближайших соседей.

NAE можно минимизировать, решив следующие линейные уравнения с единственным решением, которое представляет собой уникальный глобальный минимум NAE со значением ноль:

p_{k}({\boldsymbol {x}})-\sum _{\boldsymbol {y\in {\mathcal {N}}(x)}}w_{\boldsymbol {xy}}p_{k}({\boldsymbol {y}})=0,\quad \forall {{\boldsymbol {x}}\in {\boldsymbol {X}}},\quad k=1,...,M

где $M$ – это количество ОГО плюс одна (для группы выбросов). Для решения этих линейных уравнений можно использовать следующую итерационную процедуру:

{{\boldsymbol {p}}^{t+1}({\boldsymbol {x}})}=\sum _{\boldsymbol {y\in {\mathcal {N}}(x)}}w_{\boldsymbol {xy}}{{\boldsymbol {p}}^{t}({\boldsymbol {y}})}

Простая иллюстрация набора данных двумерного тестирования.

См. также

Внешние ссылки