на главную ] 

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

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

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


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

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

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

1 Введение

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

qecl

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

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

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

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

    K  := {x ∈ U |ρ(x,x0) ≤ R }
  4. переместить центр x0 в центр масс кластера K

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

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

 
 

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

Q= c . di / do

где

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

 
 

 

3 Реализация

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

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

первого уровня - 26 , ( Qlow = 0.04 )
второго уровня - 5 , ( Qhigh = 0.25 )

 

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

 
 

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

 
 

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

[1]    Евгений Борисов Метод кластеризации КНП. -- http://www.mechanoid.kiev.ua/ml-knp.html

[2]    Воронцов К.В. Методы кластеризации – http://shad.yandex.ru/lectures/machine_learning.xml

[3]    GNU Octave – http://www.gnu.org/software/octave/

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