Алгоритм ФорЭл

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 7: Строка 7:
=Входные данные=
=Входные данные=
 +
*Кластеризуемая выборка
 +
Может быть задана признаковыми описаниями объектов - линейное пространство либо матрицей попарных расстояний между объектами.
 +
''Замечание:'' в реальных задачах зачастую храниние всех данных невозможно или бессмыслено, поэтому необходимые данные собираются в процессе кластеризации
*Параметр R - радиус поиска локальных сгущений
*Параметр R - радиус поиска локальных сгущений
Его можно задавать как из априорных соображений (знание о диаметре кластеров), так и настраивать скользящим контролем.
Его можно задавать как из априорных соображений (знание о диаметре кластеров), так и настраивать скользящим контролем.

Версия 12:43, 5 января 2010

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

Содержание

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

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

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

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

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

  • Кластеризуемая выборка

Может быть задана признаковыми описаниями объектов - линейное пространство либо матрицей попарных расстояний между объектами. Замечание: в реальных задачах зачастую храниние всех данных невозможно или бессмыслено, поэтому необходимые данные собираются в процессе кластеризации

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

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

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

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

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

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

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

Наблюдения

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

Эвристики выбора центра тяжести

  • В линейном пространстве - центр масс
  • В метрическом пространстве - объект, сумма расстояний до которого минимальна, среди всех внутри сферы
  • Объект, который внутри сферы радиуса R содержит максимальное количество других объектов из всей выборки (медленно)
  • Объект, который внутри сферы маленького радиуса содержит максимальное количество объектов (из сферы радиуса R)


Минимзируемый алгоритмом функционал качества

D=\sum_{j=1}^k \sum_{x \in K_j}\|x-W_j\|^2,


Данная статья является непроверенным учебным заданием.
Студент: Участник:Rooney
Преподаватель: Участник:Константин Воронцов
Срок: 4 января 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.


Личные инструменты