Материал из MachineLearning.

FOREL (Формальный Элемент) - алгоритм кластеризации, основанный на идее объединения в один кластер объектов в областях их наибольшего сгущения.

Содержание 1 Необходимые условия работы 2 Входные данные 3 Выходные данные 4 Принцип работы 5 Наблюдения

Необходимые условия работы

• Выполнение принципа сходства

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

• Наличие линейного или метрического пространства кластеризуемых объектов

Входные данные

• Параметр R - радиус поиска локальных сгущений

Его можно задавать как из априорных соображений (знание о диаметре кластеров), так и настраивать скользящим контролем.

• В модификациях возможно введение параметра k - количества кластеров

Выходные данные

Кластеризация на заранее неизвестное число таксонов

Принцип работы

• • • Случайно выбираем объект из выборки
    • Помечаем объекты находящиеся на расстоянии менее, чем R от текущего
    • Вычисляем их центр тяжести, помечаем этот центр как новый текущий объект
  • Повторяем пока новый текущий объект не совпадет с прежним
  • Помечаем объекты внутри сферы радиуса R вокруг текущего объекта как кластеризованные, выкидываем их из выборки
• Повторяем, пока не будет кластеризована вся выборка

Наблюдения

• Доказана сходимость алгоритма за конечное число шагов
• В линейном прстранстве центром тяжести может выступать произвольная точка пространства, в метрическом - только объект выборки
• Чем меньше R, тем больше таксонов (кластеров)
• В линейном пространстве поиск центра происходит за время О(n), в метрическом O(n²)
• Наилучших результатов алгоритм достигает на выборках с хорошим выполнением условий компактности
• При повторении итераций возможно уменьшение параметра R, для скорейшей сходимости
• Кластеризация сильно зависит от начального приближения (выбора объекта на первом шаге)

Данная статья является непроверенным учебным заданием. Студент: Участник:Rooney Преподаватель: Участник:Константин Воронцов Срок: 4 января 2010 До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.