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