Алгоритмы семейства forelТекущая версия (не проверялась)

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

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

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

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

,

где первое суммирование ведется по всем кластерам выборки, второе суммирование — по всем объектам x, принадлежащим текущему кластеру K_j, а W_j — центр текущего кластера, ρ(x,y) — расстояние между объектами.

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

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

• Наличие линейного или метрического пространства кластеризуемых объектов

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

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

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

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

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

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

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

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

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

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

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

1. Случайно выбираем текущий объект из выборки

2. Помечаем объекты выборки, находящиеся на расстоянии менее, чем R от текущего

3. Вычисляем их центр тяжести, помечаем этот центр как новый текущий объект

4. Повторяем шаги 2-3, пока новый текущий объект не совпадет с прежним

5. Помечаем объекты внутри сферы радиуса R вокруг текущего объекта как кластеризованные, выкидываем их из выборки

6. Повторяем шаги 1-5, пока не будет кластеризована вся выборка

#define R 30 //ширина поиска локальных сгущений - входной параметр алгоритма

Clustering_not_finish(); //все ли объекты кластеризованы

Rand_object(); //возвращает произвольный некластеризованный объект

Generate_same_object(type *object); //возвращает массив объектов, расположенных на расстоянии <= R от текущего

Center_of_objects(type *mas_of_objects); //возвращает центр тяжести указанных объектов

Delete_objects(type *mas_of_objects); //удаляет указанные объекты из выборки (мы их уже кластеризовали)

while(Clustering_not_finish())

{

currently_object = Rand_object();

mas_of_same_objects = Generate_same_object(currently_object);

center_object = Center_of_objects(mas_of_same_objects);

while (center_object != currently_object) //пока центр тяжести не стабилизируется

{

currently_object = center_object;

mas_of_same_objects = Generate_same_object(currently_object);

center_object = Center_of_objects(mas_of_same_objects);

}

Delete_objects(mas_of_same_objects);

}

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

• В линейном пространстве — центр масс

• В метрическом пространстве — объект, сумма расстояний до которого минимальна, среди всех внутри сферы

• Объект, который внутри сферы радиуса R содержит максимальное количество других объектов из всей выборки (медленно)

• Объект, который внутри сферы маленького радиуса содержит максимальное количество объектов (из сферы радиуса R)

[править] Наблюдения

• Доказана сходимость алгоритма за конечное число шагов

• В линейном прстранстве центром тяжести может выступать произвольная точка пространства, в метрическом — только объект выборки

• Чем меньше R, тем больше таксонов (кластеров)

• В линейном пространстве поиск центра происходит за время О(n), в метрическом O(n²)

• Наилучших результатов алгоритм достигает на выборках с хорошим выполнением условий компактности

• При повторении итераций возможно уменьшение параметра R, для скорейшей сходимости

• Кластеризация сильно зависит от начального приближения (выбора объекта на первом шаге)

• Рекомендуется повторная прогонка алгоритма для исключения ситуации «плохой» кластеризации, по причине неудачного выбора начальных объектов

[править] Модификации

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

1. Точность минимизации функционала качества (при удачном подборе параметра R)

2. Наглядность визуализации кластеризации

3. Сходимость алгоритма

4. Возможность операций над центрами кластеров — они известны в процессе работы алгоритма

5. Возможность подсчета промежуточных функционалов качества, например, длины цепочки локальных сгущений

6. Возможность проверки гипотез схожести и компактности в процессе работы алгоритма

[править] Недостатки

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

2. Плохая применимость алгоритма при плохой разделимости выборки на кластеры

3. Неустойчивость алгоритма (зависимость от выбора начального объекта)

4. Произвольное по количеству разбиение на кластеры

5. Необходимость априорных знаний о ширине (диаметре) кластеров

[править] Надстройки

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

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

2. Пересчет кластеризации (многоуровненвость) с использованием метода КНП