Метод кластеризации КНП.
Евгений Борисов пятница, 24 января 2014 г.Кластеризация или естественная классификация это процесс объединение в группы объектов, обладающих схожими признаками. В отличие от задачи классификации, где количество групп объектов фиксировано и заранее определено набором идеалов, здесь группы заранее не определены и формируются в процессе работы системы исходя из определённой меры близости объектов.
Кластеризация применяется для решения многих прикладных задач: от сегментации изображений до экономического прогнозирования и борьбы с электронным мошенничеством.
Существует несколько основных методов разбиения множества объектов на группы. В этой статье рассматривается метод кластеризации данных, который называется КНП – ”Кратчайший Незамкнутый Путь”.
1 Введение
Рассмотрим набор точек X в n-мерном пространстве признаков с заданной на нём метрикой.
Метод КНП строит на точках выборки X ациклический связный граф, соединяя точки исходя из минимального расстояния между ними. После того как граф построен, из него удаляются k самых длинных рёбер, где k это параметр, который определяет количество кластеров.
2 Описание метода
Алгоритм КНП выглядит следующим образом.
- найти пару точек (xi,xj)
с наименьшим расстоянием ρ(xi,xj) - соединить пару (xi,xj) ребром
- найти пару точек (xi,xj)
изолированную xi и связанную xj
с наименьшим расстоянием ρ(xi,xj) - соединить пару (xi,xj) ребром
- если в выборке остаются изолированные точки
то переход на п.3 - удалить k-1 самых длинных рёбер
- конец
Определим функцию оценки Q качества работы кластеризатора.
c – количество кластеров;
di – среднее внутрикластерное расстояние;
do – среднее межкластерное расстояние;
3 Реализация
На рисунках ниже проиллюстрирована результаты работы КНП-кластеризатора.
 |
 |
| Рис.1: набор данных для обработки | Рис.2: результат кластеризации Q=0.2 |
|
|
| Рис.3: полный граф | Рис.4: граф с удалёнными рёбрами |
Реализация в системе Octave [ здесь ].
Список литературы
