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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм

1. Случайно выбираем текущий объект из выборки;
2. Помечаем объекты выборки, находящиеся на расстоянии менее, чем R от текущего;
3. Вычисляем их центр тяжести, помечаем этот центр как новый текущий объект;
4. Повторяем шаги 2-3, пока новый текущий объект не совпадет с прежним;
5. Помечаем объекты внутри сферы радиуса R вокруг текущего объекта как кластеризованные, выкидываем их из выборки;
6. Повторяем шаги 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, для скорейшей сходимости;
• Кластеризация сильно зависит от начального приближения (выбора объекта на первом шаге);
• Рекомендуется повторная прогонка алгоритма для исключения ситуации «плохой» кластеризации, по причине неудачного выбора начальных объектов.

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

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

Недостатки

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

Надстройки

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

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

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

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

См. также

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

Литература

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