Алгоритмы семейства FOREL
FOREL (Формальный Элемент) — алгоритм кластеризации, основанный на идее объединения в один кластер объектов в областях их наибольшего сгущения.
Цель кластеризации
Разбить выборку на такое (заранее неизвестное) число таксонов, чтобы сумма расстояний от объектов кластеров до центров кластеров была минимальной по всем кластерам. То есть наша задача — выделить группы максимально близких друг к другу объектов, которые в силу гипотезы схожести и будут образовывать наши кластеры.
Минимизируемый алгоритмом функционал качества
F = ∑ j = 1 k ∑ x ∈ K j ρ ( x , W j ) , {displaystyle F=sum _{j=1}^{k}sum _{xin K_{j}} ho (x,W_{j}),} ,где первое суммирование ведется по всем кластерам выборки, второе суммирование — по всем объектам x {displaystyle x} , принадлежащим текущему кластеру K j {displaystyle K_{j}} , а W j {displaystyle W_{j}} — центр текущего кластера, ρ ( x , y ) {displaystyle ho (x,y)} — расстояние между объектами.
Необходимые условия работы
- Выполнение гипотезы компактности, предполагающей, что близкие друг к другу объекты с большой вероятностью принадлежат к одному кластеру (таксону).
- Наличие линейного или метрического пространства кластеризуемых объектов
Входные данные
- Кластеризуемая выборка
Может быть задана признаковыми описаниями объектов — линейное пространство либо матрицей попарных расстояний между объектами.
Замечание: в реальных задачах зачастую хранение всех данных невозможно или бессмысленно, поэтому необходимые данные собираются в процессе кластеризации
- Параметр R — радиус поиска локальных сгущений
Его можно задавать как из априорных соображений (знание о диаметре кластеров), так и настраивать скользящим контролем.
- В модификациях возможно введение параметра k — количества кластеров
Выходные данные
Кластеризация на заранее неизвестное число таксонов
Принцип работы
На каждом шаге мы случайным образом выбираем объект из выборки, раздуваем вокруг него сферу радиуса R, внутри этой сферы выбираем центр тяжести и делаем его центром новой сферы. То есть мы на каждом шаге двигаем сферу в сторону локального сгущения объектов выборки, то есть стараемся захватить как можно больше объектов выборки сферой фиксированного радиуса. После того как центр сферы стабилизируется, все объекты внутри сферы с этим центром мы помечаем как кластеризованные и выкидываем их из выборки. Этот процесс мы повторяем до тех пор, пока вся выборка не будет кластеризована.
Алгоритм
Эвристики выбора центра тяжести
- В линейном пространстве — центр масс
- В метрическом пространстве — объект, сумма расстояний до которого минимальна, среди всех внутри сферы
- Объект, который внутри сферы радиуса R содержит максимальное количество других объектов из всей выборки (медленно)
- Объект, который внутри сферы маленького радиуса содержит максимальное количество объектов (из сферы радиуса R)
Наблюдения
- Доказана сходимость алгоритма за конечное число шагов
- В линейном пространстве центром тяжести может выступать произвольная точка пространства, в метрическом — только объект выборки
- Чем меньше R, тем больше таксонов (кластеров)
- В линейном пространстве поиск центра происходит за время О(n), в метрическом O(n²)
- Наилучших результатов алгоритм достигает на выборках с хорошим выполнением условий компактности
- При повторении итераций возможно уменьшение параметра R, для скорейшей сходимости
- Кластеризация сильно зависит от начального приближения (выбора объекта на первом шаге)
- Рекомендуется повторная прогонка алгоритма для исключения ситуации «плохой» кластеризации, по причине неудачного выбора начальных объектов
Преимущества
Недостатки
Надстройки
После работы алгоритма над готовой кластеризацией можно производить некоторые действия