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

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

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

Цель кластеризации[править | править код]

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

Минимизируемый алгоритмом функционал качества[править | править код]

,

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

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

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

Входные данные[править | править код]

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

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

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

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

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

Выходные данные[править | править код]

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

Принцип работы[править | править код]

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

Алгоритм[править | править код]

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

См. также[править | править код]

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