Метод кластеризации ФОРЭЛ.

Евгений Борисов

среда, 29 января 2014 г.

Кластеризация или естественная классификация это процесс объединение в группы объектов, обладающих схожими признаками. В отличие от обычной классификации, где количество групп объектов фиксировано и заранее определено набором идеалов, здесь группы заранее не определены и формируются в процессе работы системы исходя из определённой меры близости объектов.

Кластеризация применяется для решения многих прикладных задач: от сегментации изображений до экономического прогнозирования и борьбы с электронным мошенничеством.

Существует несколько основных методов разбиения множества объектов на группы. В этой статье рассматривается метод кластеризации данных, который называется ФОРЭЛ – ”ФОРмальные ЭЛементы”.

1 Введение

Рассмотрим набор точек X в n -мерном пространстве признаков с заданной на нём метрикой.

Метод ФОРЭЛ разбивает множество точек X на кластеры радиуса R , где R это параметр. Результатом работы этого метода есть набор C точек-центроидов, вокруг которых формируются кластеры по принципу ближайшего центра.

2 Описание метода

Алгоритм ФОРЭЛ выглядит следующим образом.

1. U := X - инициализировать множество некластеризованных точек
2. взять случайную точку x ₀ ∈ U
3. образовать кластер K с центром в x ₀ и радиусом R
   

4. переместить центр x ₀ в центр масс кластера K
   

5. если x ₀ ≠ x' ₀
   то x ₀ := x' ₀ , переход на п. 3
6. пометить все точки K как обработанные: U := U ∖ K
7. добавить точку-центроид x ₀ в список результатов C := C ∪{ x ₀ }
8. если есть ещё не обработанные точки: | U | > 0
   то переход на п. 2
9. конец

Если был задан достаточно малый размер кластера R , то в результате применения ФОРЭЛ к множеству точек X у нас появляется список центроидов C . Для улучшения результата к множеству C можно применить метод кластеризации КНП [ 1 ]. Таким образом, объединив слишком мелкие кластеры C ( X ) , мы получаем двухуровневую кластеризацию.

Определим функцию оценки Q качества работы кластеризатора.

Q= c ^. d _i / d _o

где

c – количество кластеров;
d _i – среднее внутрикластерное расстояние;
d _o – среднее межкластерное расстояние;

3 Реализация

На рисунках ниже проиллюстрирована результаты работы ФОРЭЛ+КНП-кластеризатора. Вначале с помощью ФОРЭЛ находим точки-центроиды кластеров первого уровня, затем применяем ним КНП [ 1 ], который строит граф на этих точках, объединяя мелкие кластеры первого уровня в более крупные кластеры второго уровня.

Количество кластеров:

первого уровня - 26 , ( Q _low = 0.04 )
второго уровня - 5 , ( Q _high = 0.25 )

Рис.1: набор данных для обработки	Рис.2: результат кластеризации
Рис.3: полный граф	Рис.4: граф с удалёнными рёбрами

Реализация в системе Octave [ здесь ].

Список литературы

При использовании материалов этого сайта, пожалуйста вставляйте в свой текст ссылку на мою статью.