2.1.3 Основная задача кластерного анализа
Пусть множество /=///,/;,/},..., /д/обозначает множество объектов из некоторой совокупности. Для множества / имеется множество векторов измерений X={XjX2,X3,...,Xn}, которые описывают множество /;
объекту 7/, соответствует вектор измерения Xj, объекту I2 - вектор JG и т.д.
Множество X может быть представлено, как п точек в р-мерном евклидовом пространстве.Задача кластерного анализа заключается в том, чтобы на основании данных, содержащихся в множестве X, разбить множество объектов / на т кластеров (классов), каждый объект I при этом принадлежит только одному классу. Внутри класса объекты сходны между собой, объекты, принадлежащие разным классам, разнородны.
Решением задачи кластерного анализа является разбиение, удовлетворяющее некоторому критерию оптимальности, представляющему собой некоторый функционал (целевую функцию).
Задачи кластерного анализа можно классифицировать различными способами. Например, по числу объектов классификации (векторов образов), а также по числу классов, на которое разбивается множество объектов классификации. При этом возможны следующие случаи:
. 1. Число классов известно заранее; Число классов неизвестно и его необходимо определить;
Число классов неизвестно и его не нужно определять.
Среди процедур кластеризации можно выделить следующие основные типы:
Иерархические;
Параллельные;
Последовательные.
Основной принцип иерархических процедур заключается в последовательном объединении в отдельный класс сначала наиболее близко расположенных объектов классификации, а затем - более удаленных. В большинстве алгоритмов каждый вектор образов рассматривается вначале как отдельный класс. Процесс классификации завершается, как только будет достигнут критерий качества разбиения. Достоинством иерархических методов является наглядность проведенного анализа. Недостатком является большой объем реализации этих процедур на ЭВМ.
Требуется большой объем памяти и большое количество машинного времени. Если мощность выборки больше нескольких сотен, то применение алгоритма нецелесообразно из-за практической невозможности его реализации на ЭВМ.Параллельные процедуры кластеризации реализуют, как правило, две основные идеи:
Идею оптимизации разбиения согласно заранее выбранного функционала качества разбиения;
Идею образования; кластера по принципу определения мест наибольшей плотности точек (векторов образов в метрическом
40
РОССИЙСКАЯ ГОСУДАРСТВЕННА]*
.шишютедА'
пространстве). В этом случае алгоритмы используют понятие эталонных точек (множеств) и оперируют одновременно со всеми векторами образов.
В случае последовательных кластерных процедур алгоритмы оперируют вначале с частью векторов образов в метрическом пространстве, затем со следующей' их частью, выбираемой в соответствии с заданным решающим правилом в некоторой окрестности предыдущей, порции данных и т.д. до тех пор, пока вся выборка не будет исчерпана. При этом выделение скопления точек сгущения производится путем нахождения мод. К одному и тому же кластеру (классу) относятся те векторы, которые расположены в некоторой окрестности соответствующей моды. Задавая разные разделяющие поверхности и решающие правила, можно по-разному устанавливать границы и другие характеристики кластеров. Т.к. форма кластера определяется разделяющей поверхностью, то результат классификации существенно зависит от структуры исходной выборки. Априорной информации о структуре данных исследователи чаще всего не имеют, и поэтому результаты кластеризации бывают неустойчивыми. Для принятия окончательного решения о результате классификации; необходимо, чтобы алгоритмы классификации были основаны на представлении о классе, как размытом множестве.
Использование представлений, основанных на нечетких множествах, позволяет преодолеть трудности классификации кластеров сложной формы с помощью ЭВМ, а также позволяет получить устойчивый результат классификации.
Наиболее трудное и наименее формализованное в задаче классификации - это определение понятия однородности объектов. В общем случае понятие однородности объектов задается либо введением правила вычислений расстояния p(Xj,X2J между любой парой объектов исследуемого множества {XtJC^Xs,,. .,Xnj, либо заданием некоторой функции r(XitX), характеризующей степень близости (сходства, подобия) объектов Xi и Xj. Если задана функция p(XiJC?), то близкие в смысле этой метрики объекты считаются однородными, принадлежащими одному классу. При этом, следовательно, необходимо сопоставление р(ХьХ]) с некоторым пороговым значением, определяемым в каждом конкретном случае по-своему.
Определение. Мерой близости называется действительная неотрицательная функция r(XhXj), обладающая следующими свойствами:
r(Xi,Xj)= r(Xj,XJ - симметрия;
r(X}jX^)>= max r(Xi,Xj) - максимальное сходство объекта с самим собой;
Требование монотонного убывания при заданной метрике, т.е. изp(XhXl)> =p(XbXj) следует, что r(XhX^<= г (X^XJ
Пример метрики р - обычное евклидово расстояние. Существует много метрик: расстояние Махаланобиса, различные многомерные (интегральные) меры расстояния. Евклидова метрика наиболее употребительна.
Обширный класс алгоритмов классификации основан на задании мер сходства. Существуют различные типы мер сходства:
коэффициенты подобия;
коэффициенты связи (корреляции);
показатели расстояния в метрическом пространстве.
При обработке определенного рода данных традиционные методы (методы распознания образов) классификации данных не всегда могут быть использованы.
Поэтому были разработаны алгоритмы классификации, базирующиеся на понятии нечеткого множества.