Алгоритмы семейства FOREL

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

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

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

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

\text{[math]}

F=\sum _{j=1}^{k}\sum _{x\in K_{j}}\rho (x,W_{j}),

,

где первое суммирование ведется по всем кластерам выборки, второе суммирование — по всем объектам $\text{[math]}$ $\text{[math]}$ $x$ , принадлежащим текущему кластеру $\text{[math]}$ $\text{[math]}$ $K_{j}$ , а $\text{[math]}$ $\text{[math]}$ $W_{j}$ — центр текущего кластера, $\text{[math]}$ $\text{[math]}$ $\rho (x,y)$ — расстояние между объектами.

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

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

Входные данныеПравить

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

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

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

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

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

Выходные данныеПравить

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

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

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

АлгоритмПравить

Случайно выбираем текущий объект из выборки;
Помечаем объекты выборки, находящиеся на расстоянии менее, чем R от текущего;
Вычисляем их центр тяжести, помечаем этот центр как новый текущий объект;
Повторяем шаги 2-3, пока новый текущий объект не совпадет с прежним;
Помечаем объекты внутри сферы радиуса R вокруг текущего объекта как кластеризованные, выкидываем их из выборки;
Повторяем шаги 1-5, пока не будет кластеризована вся выборка.

Псевдокод алгоритма на C-подобном языке:

 
#define R 30 //ширина поиска локальных сгущений - входной параметр алгоритма 
clusterisation_not_finished(); //все ли объекты кластеризованы 
get_random_object(); //возвращает произвольный некластеризованный объект 
get_neighbour_objects(type *object); //возвращает массив объектов, расположенных на расстоянии <= R от текущего 
center_of_objects(type *mass_of_objects); //возвращает центр тяжести указанных объектов 
delete_objects(type *mass_of_objects); //удаляет указанные объекты из выборки (мы их уже кластеризовали) 
 
while(clusterisation_not_finished()) 
{ 
   current_object = get_random_object(); 
   neighbour_objects = get_neighbour_objects(current_object);  
   center_object = center_of_objects(neighbour_objects); 
    
   while (center_object != current_object)  //пока центр тяжести не стабилизируется 
   { 
      current_object = center_object; 
      neighbour_objects = get_neighbour_objects(current_object); 
      center_object = center_of_objects(neighbour_objects); 
   }  
   delete_objects(neighbour_objects); 
}

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

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

НаблюденияПравить

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

ПреимуществаПравить

Точность минимизации функционала качества (при удачном подборе параметра R);
Наглядность визуализации кластеризации;
Сходимость алгоритма;
Возможность операций над центрами кластеров — они известны в процессе работы алгоритма;
Возможность подсчета промежуточных функционалов качества, например, длины цепочки локальных сгущений;
Возможность проверки гипотез схожести и компактности в процессе работы алгоритма.

НедостаткиПравить

Относительно низкая производительность (решается введение функции пересчета поиска центра при добавлении 1 объекта внутрь сферы);
Плохая применимость алгоритма при плохой разделимости выборки на кластеры;
Неустойчивость алгоритма (зависимость от выбора начального объекта);
Произвольное по количеству разбиение на кластеры;
Необходимость априорных знаний о ширине (диаметре) кластеров.

НадстройкиПравить

После работы алгоритма над готовой кластеризацией можно производить некоторые действия:

Выбор наиболее репрезентативных (представительных) объектов из каждого кластера. Можно выбирать центры кластеров, можно несколько объектов из каждого кластера, учитывая априорные знания о необходимой репрезентативности выборки. Таким образом, по готовой кластеризации мы имеем возможность строить наиболее репрезентативную выборку;
Пересчёт кластеризации (многоуровневость) с использованием метода КНП.

Область примененияПравить

Решение задач кластеризации;
Решение задач ранжирования выборки.

См. такжеПравить

Кластерный анализ

ЛитератураПравить

Воронцов К. В. Лекции по алгоритмам кластеризации и многомерного шкалирования, МГУ, 2007
Загоруйко Н. Г., Ёлкина В. Н., Лбов Г. С. Алгоритмы обнаружения эмпирических закономерностей. — Новосибирск: Наука, 1985. — 999 с.
Загоруйко Н. Г. Прикладные методы анализа данных и знаний. — Новосибирск: ИМ СО РАН, 1999. — 270 с. — ISBN 5-86134-060-9.