Полная версия

Главная

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

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

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

Процедуры кластерного анализа в настоящее время являются одними из наиболее широко используемых на практике методов классификации. Процедуры классификации отличаются от других методов многомерной классификации отсутствием априорной информации о распределении генеральной совокупности и обучающих выборок. Различия между схемами решения задач классификации во многом определяются тем, что понимают под понятиями "сходство" и "степень сходства". На практике обычно используют разбиения, являющиеся наиболее устойчивыми [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) – систематизированная группа любой категории.
 
<<   СОДЕРЖАНИЕ   >>