на главную ] 

Метод кластеризации КНП.

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

пятница, 24 января 2014 г.


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

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

Существует несколько основных методов разбиения множества объектов на группы. В этой статье рассматривается метод кластеризации данных, который называется КНП – ”Кратчайший Незамкнутый Путь”.

1 Введение

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

qecl

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

 
 

 
 

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

Алгоритм КНП выглядит следующим образом.

  1. найти пару точек (xi,xj)
    с наименьшим расстоянием ρ(xi,xj)
  2. соединить пару (xi,xj) ребром
  3. найти пару точек (xi,xj)
    изолированную xi и связанную xj
    с наименьшим расстоянием ρ(xi,xj)
  4. соединить пару (xi,xj) ребром
  5. если в выборке остаются изолированные точки
    то переход на п.3
  6. удалить k-1 самых длинных рёбер
  7. конец

 
 

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

Q= c . di / do

где

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

 
 

 
 

3 Реализация

На рисунках ниже проиллюстрирована результаты работы КНП-кластеризатора.

 

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

 
 

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

 
 

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

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

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

Яндекс.Метрика
TOP.zp.ua PR-CY.ru
При использовании материалов этого сайта, пожалуйста вставляйте в свой текст ссылку на мою статью.