Алгоритм ФорЭл
Материал из MachineLearning.
FOREL (Формальный Элемент) - алгоритм кластеризации, основанный на идее объединения в один кластер объектов в областях их наибольшего сгущения.
Содержание |
Необходимые условия работы
- Выполнение принципа сходства
Это означает, что близкие друг к другу объекты с большой вероятностью принадлежат к одному кластеру (таксону).
- Наличие линейного или метрического пространства кластеризуемых объектов
Входные данные
- Параметр R - радиус поиска локальных сгущений
Его можно задавать как из априорных соображений (знание о диаметре кластеров), так и настраивать скользящим контролем.
- В модификациях возможно введение параметра k - количества кластеров
Выходные данные
Кластеризация на заранее неизвестное число таксонов
Принцип работы
- Случайно выбираем объект из выборки
- Помечаем объекты находящиеся на расстоянии менее, чем R от текущего
- Вычисляем их центр тяжести, помечаем этот центр как новый текущий объект
- Повторяем пока новый текущий объект не совпадет с прежним
- Помечаем объекты внутри сферы радиуса R вокруг текущего объекта как кластеризованные, выкидываем их из выборки
- Повторяем, пока не будет кластеризована вся выборка
Наблюдения
- Доказана сходимость алгоритма за конечное число шагов
- В линейном прстранстве центром тяжести может выступать произвольная точка пространства, в метрическом - только объект выборки
- Чем меньше R, тем больше таксонов (кластеров)
- В линейном пространстве поиск центра происходит за время О(n), в метрическом O(n²)
- Наилучших результатов алгоритм достигает на выборках с хорошим выполнением условий компактности
- При повторении итераций возможно уменьшение параметра R, для скорейшей сходимости
- Кластеризация сильно зависит от начального приближения (выбора объекта на первом шаге)
Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |