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

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

Содержание 1 Цель кластеризации 2 Минимзируемый алгоритмом функционал качества 3 Необходимые условия работы 4 Входные данные 5 Выходные данные 6 Принцип работы 7 Алгоритм 8 Эвристики выбора центра тяжести 9 Наблюдения 10 Модификации 11 Литература

Цель кластеризации

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

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

,

где первое суммирование ведется по всем кластерам выборки, второе суммирование - по всем объектам x, принадлежащим текущему кластеру, а - центр текущего кластера, - расстояние между объектами.

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

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

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

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

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

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

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

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

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

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

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

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

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

На каждом шаге мы случайным образом выбираем объект из выборки, раздуваем вокруг него сферу радиуса R, внутри этой сферы выбираем центр тяжести и делаем его центром новой сферы. Т.о. мы на каждом шаге двигаем сферу в сторону локального сгущения объектов выбоки, т.е. стараемся захватить как можно больше объектов выборки сферой фиксированного радиуса. После того как центр сферы стабилизируется, все объекты внутри сферы с этим центром мы помечаем как кластеризованные и выкидываем их из выборки. Этот процесс мы повторяем до тех пор, пока вся выборка не будет кластеризована.

Алгоритм

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

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

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

Наблюдения

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

Модификации

Литература

1. Лекции по алгоритмам кластеризации и многомерного шкалирования К.В.Воронцов
2. Прикладные методы анализа данных и знаний Новосибирск Н.Г.Загоруйко: Изд-во Ин-та математики, 1999, 270 с. ISBN 5-86134-060-9

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