Кластерный анализ, непараметрическая классификация без обучения

Основные понятия и определения кластерного анализа

Процедуры кластерного анализа в настоящее время являются одними из наиболее широко используемых на практике методов классификации. Процедуры классификации отличаются от других методов многомерной классификации отсутствием априорной информации о распределении генеральной совокупности и обучающих выборок. Различия между схемами решения задач классификации во многом определяются тем, что понимают под понятиями «сходство» и «степень сходства». На практике обычно используют разбиения, являющиеся наиболее устойчивыми [29].

Свое название кластерный анализ получил от английского слова cluster^[1]. Основная цель кластерного анализа — разбиение множества исследуемых объектов или признаков на однородные в определенном смысле группы или кластеры. Достоинством кластерного анализа является то, что он позволяет производить разбиение объектов не по одному параметру, а по целому набору признаков. Кроме того, кластерный анализ, в отличие от большинства математико-статистических методов, не накладывает жестких ограничений на вид рассматриваемых объектов.

Кластерами (таксонами^[2], образами) называют группы объектов, полученные в результате разбиения, а кластерным анализом — методы их нахождения (соответственно численной таксономией или распознаванием образов с самообучением).

Кластеры представляют собой скопления точек (объектов) различной формы (рис. 6.1). Решение задачи классификации заключается в определении естественного расслоения исходных наблюдений на четко выраженные кластеры, лежащие друг от друга на некотором расстоянии.

Проведение кластерного анализа включает следующие этапы.

• 1. Отбор выборки для классификации.
• 2. Определение множества переменных, по которым будет проводиться классификация. На этом этапе исследователь должен выяснить, какие из к априори рассматриваемых факторов являются наиболее характерными, определяющими с точки зрения точности разбиения исследуемых объектов на классы. Решение этой задачи позволит перейти от априорного набора к факторов к меньшему числу (к' < к) наиболее информативных признаков и тем самым снизить размерность пространства, избавиться от «шумовых», «засоряющих» признаков, облегчить интерпретацию результатов.
• 3. Вычисление расстояния (сходства) между объектами.
• 4. Создание с помощью методов кластерного анализа групп сходных объектов.
• 5. Проверка достоверности результатов кластерного решения.

Рис. 6.1. Формы кластеров.

Для проведения кластерного анализа исходные данные должны быть представлены в виде прямоугольной таблицы, каждая строка которой представляет результат измерений к рассматриваемых признаков на одном из обследованных объектов:

Отметим, что в некоторых задачах может представлять интерес не только группировка объектов, но и группировка признаков.

Сформулируем постановку задачи автоматической классификации. Пусть исследуется совокупность п объектов, каждый из которых характеризуется k замеренными на нем признаками на определенный момент времени (г = const). Требуется разбить эту совокупность на р однородных в некотором смысле групп (классов) так, чтобы каждый объект принадлежал только одному подмножеству разбиения (кластеру). Объекты одного кластера должны быть схожими (находиться на сравнительно небольших расстояниях друг от друга), а объекты, принадлежащие разным кластерам, — разнородными (несходными). Априорная информация о количестве кластеров и их характеристиках отсутствует.

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

Предположение: геометрическая близость двух или нескольких точек в пространстве означает близость физических состояний соответствующих объектов. Таким образом, решение задачи классификации заключается в определении естественного расслоения исходных наблюдений на четко выраженные кластеры, лежащие друг от друга на некотором расстоянии. Отметим, что данная задача может не иметь решения.

Определим понятия сходства и разнородности объектов. Как мы можем определить, что, например, объекты и сходны или различны? Задача была бы решена, если «'-й и /-и объекты попадали в один кластер тогда и только тогда, когда расстояние между точками и было бы достаточно малым, и наоборот, попадали бы в разные кластеры в случае достаточно большого расстояния между ними.

Понятие однородности объектов является наиболее трудным и менее формализованным в задаче кластерного анализа. Для решения этой задачи вводитсяпонятие расстояния между объектами, которое обозначается через или

Неотрицательная вещественная функция d (Xt, Xj) называется функцией (метрикой)расстояния, если выполняются следующие условия:

• 1) для всех ;
• 2) , если ;
• 3)
• 4) , где - любые три вектора из пространства наблюдений.

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

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

Исходная информация в задачах классификации может быть задана в виде квадратной матрицы расстояний :

или в виде квадратной матрицы сходства F = (/^), i, j = 1, 2, и:

Вещественная функция называется мерой сходства, если выполняются следующие условия:

Таким образом, объекты сходны положительно (положительным образом), если значение /jj близко к 1; объекты сходны отрицательно (отрицательным образом), если значение близко к -1; не сходны, если значение функции fij близко к 0.

Понятие сходства между двумя объектами является понятием, противоположным понятию расстояния (djj) между объектами Х: и Xf.

Большинство алгоритмов кластерного анализа полностью исходят из матрицы расстояний (или близостей) либо требуют вычисления отдельных ее элементов, поэтому если данные представлены в форме матрицы X, то первым этапом решения задачи поиска кластеров будет выбор способа вычисления расстояний (степени близости) между объектами или признаками.

• [1] Кластер (англ, duster — «гроздь», «скопление») — группа элементов, характеризуемых каким-либо общим свойством.
• [2] Таксон (англ, taxon) — систематизированная группа любой категории.