Классификация многомерных данных

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

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

Рассмотрим следующую задачу. Пусть исследуется совокупность из п объектов, каждый из которых характеризуется k признаками. Требуется разбить эту совокупность на однородные, в некотором смысле, группы (классы).

В литературе полученные в результате разбиения группы, как правило, именуются кластерами (таксонами), методы их нахождения — кластерным анализом.

Решение задачи состоит в определении естественного расслоения исходных наблюдений на четко выраженные кластеры, лежащие друг от друга на некотором расстоянии. При этом может оказаться, что множество исходных наблюдений не обнаруживает естественного расслоения на кластеры, т.е. имеет место один кластер.

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

Обычной формой представления исходных данных в этих задачах анализа служит прямоугольная таблица:

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

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

Наиболее трудное и наименее формализованное в задаче классификации — определение понятия однородности объектов. В общем случае понятие однородности объектов задается путем введения правила вычисления расстояний между любой парой исследуемых объектов {} х2п). Пусть d(xv X;) характеризует расстояние между i и j объектами, где i,j =1,2, ..., п. Если задана функция d(xv х), то близкие с точки зрения этой метрики объекты — однородные, принадлежащие к одному классу. Очевидно, что необходимо при этом сопоставлять d{xv xj) с некоторыми пороговыми значениями, определяемыми в каждом конкретном случае по-своему.

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

Обычное евклидово расстояние

где xie, Xje — величина е-го признака у г-го (/-го) объекта (е = 1,2, ..., k, i,j= 1, 2,..., п).

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

П й

Здесь х — среднее значение е-го признака; Se = Y (х. -х )2 — средне-

V n

квадратическое отклонение е-ro признака.

Однако эта операция может привести к нежелательным последствиям. Если кластеры хорошо разделены по одному и нс разделены по другому признаку, то после нормирования дискриминирующие возможности первого признака будут уменьшены в связи с увеличением «шумового» эффекта второго.

«Взвешенное» евклидово пространство

применяется в тех случаях, когда каждой компоненте xt вектора наблюдений X удается приписать некоторый «вес» (О/, пропорционально степени важности признака в задаче классификации. Как правило, принимают О < а>е < 1, где е = 1,2, ..., k.

Определение «весов» в основном связано с дополнительными исследованиями, например, организацией опроса экспертов и обработкой их мнений. Определение весов Ш/ только по данным выборки может привести к ложным выводам.

Как правило, решение задач классификации многомерных данных предусматривает в качестве предварительного этапа исследования реализацию методов, позволяющих выбрать из компонент х1; х2, ..., xk, наблюдаемых векторов X, сравнительно небольшое число наиболее существенно информативных, т.е. уменьшить размерность наблюдаемого пространства.

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

Пусть Sj — i-я группа (класс, кластер), состоящая из и, объектов; х — вектор средних арифметических признаков, полученных по пл наблюдениям s,-ro класса, т.е. «центр тяжести» i-й группы; d(S/, sm) — расстояние между группами st и sm.

В качестве расстояния между классами объектов будем рассматривать расстояние, измеряемое по принципу «ближайшего соседа»:

I

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

При этом расстояние между классами Sj и s(/qy являющихся объединением двух других классов s,„ и s„, можно определить по формуле

где dem = d(Se, SJ; drq = d(Se, SJ; dmq = d{Sm, SJ - расстояния между классами S/, sm и sq; a, (3,8 и у — числовые коэффициенты, значения которых определяют специфику процедуры, ее алгоритм. Например, при a = (3 = = -8 = 1/2 и у = 0 приходим к расстоянию, построенному по принципу «ближайшего соседа».

Иерархические (древообразные) процедуры — наиболее распространенные (в смысле реализации на ЭВМ) алгоритмы кластерного анализа. В этих алгоритмах начальным является разбиение, состоящее из п одноэлементных классов, а конечным — из одного класса.

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

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

Большинство программ, реализующих алгоритм иерархической классификации, предусматривает графическое представление результатов классификации в виде дендрограммы (рис. 6.3).

Пример 6.3

Проведите классификацию п = 6 объектов, каждый из которых характеризуется двумя признаками.

Номер объекта (г)

1

2

3

4

5

6

*«1

5

6

5

10

11

10

ха

10

12

13

9

9

7

Расположение этих точек на плоскости показано на рис. 6.2.

Воспользуемся иерархическим алгоритмом классификации. В качестве расстояния между объектами примем обычное евклидово расстояние. Тогда, согласно (6.10), расстояние между объектами 1 и 2

а между объектами 1 и 3

Расположение объектов

Рис. 6.2. Расположение объектов

Очевидно, что

Из матрицы расстояний следует, что объекты 4 и 5 наиболее близки 4 5 = 1,00 и поэтому объединяются в один кластер.

После объединения имеем пять кластеров.

Номер кластера

1

2

3

4

5

Состав кластера

(1)

(2)

(3)

(4,5)

(6)

Расстояние между кластерами будем находить по принципу «ближайшего соседа», воспользовавшись формулой пересчета (6.13). Так, расстояние между объектом х, и кластером х(4 5)

Мы видим, что расстояние Pi.(4,s> равно расстоянию от объекта 1 до ближайшего к нему объекта, входящего в кластер х(4 т.е. d, (4 5) = d{ 4 = 5,1. Тогда матрица расстояний

Объединим объекты 2 и 3 с наименьшим расстоянием d2 3 = 1,41. После объединения имеем четыре кластера: s(1), s(2 3), s(4,5)> s(6у

Вновь найдем матрицу расстояний. Для этого рассчитаем расстояние до кластера 5(2,3)- Воспользуемся матрицей расстояний Z)2.

Например, расстояние между кластерами s(4 5) и s(2 3)

Проведя аналогичные расчеты, получим

Объединенные кластеры 5) и $(6ч, расстояние между которыми, согласно матрице /?3, наименьшее: 5) 6 = 2.

В результате имеем три кластера: s{, $/23 и 5 fi).

Матрица расстояний

Объединим теперь кластеры sx и s2 3, расстояние между которыми равно d (2 з) = 2,24. В результате получим два кластера s(1 2 3) и s(4 5 6), расстояние между которыми, найденное по принципу «ближайшего соседа», равно: 2 3) (4 5 6) = 5.

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

Дендрограмма

Рис. 63. Дендрограмма

В задаче предпочтение следует отдать предпоследнему этапу классификации, когда все объекты объединены в два кластера: 2,3) и s(t, 5, ь> (см- рис. 6.1).

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >