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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

[править | править код]

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

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

[править | править код]
,

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

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

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

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

[править | править код]
  • Кластеризуемая выборка

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

  • Параметр 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.