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

Главная arrow Статистика arrow Многомерный статистический анализ эколого-геохимических измерений. Ч.1. Математические основы

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


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Кластерный анализ

Кластерный анализ [12, 17, 20, 24, 26, 38] - это статистический анализ, позволяющий получить разбиение большого объема данных на классы или группы (от англ, cluster - класс) согласно некоторому критерию или их совокупности.

Для проведения классификации данных Хх,...,Хп используют понятие метрики или расстояния.

Метрикой называется функция р отображающая некоторое метрическое пространство в пространство действительных чисел и обладающая следующими свойствами (аксиомами метрики):

  • 1) р(ЗД>0,
  • 2) p(X,Y)=p (Y,X),
  • 3) р(Х, У) = 0 <=> X = Y,
  • 4) P(X,Y)<P(X,Z) + P(Z,Y).

В теории кластерного анализа используются следующие метрики для измерения расстояния между отдельными точками (векторами):

1) евклидово расстояние

2) взвешенное евклидово расстояние

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

т

и полагают, что ^ w* = 1;

  • *=i
  • 3) хеммингово расстояние (или city-block) - расстояние по карте между кварталами в городе

4) расстояние Махаланобиса (или угол Махаланобиса)

где А - симметричная положительно определенная матрица весовых коэффициентов (часто выбирается диагональной); А - матрица ковариаций векторов Х19...,Хп;

5) расстояние Минковского

Расстояния 1), 2), 3) или 5) используют в случае нормального распределения независимых случайных величин Xl9...,Xn ~N(M,A) или в случае их однородности по геохимическому смыслу, когда каждый вектор одинаково важен для классификации. Расстояние 4) используют в случае наличия ковариационной связи векторов Хх,...,Хп.

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

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

Пусть S{ - /-ый кластер, состоящий из nt векторов или точек. Пусть

X(l) - выборочное среднее по точкам, попадающим в кластер Sf, или центр тяжести кластера 5.. Тогда различают следующие расстояния между кластерами, не имеющими внутри других кластеров:

1) расстояние между кластерами по принципу «ближнего соседа»

2) расстояние между кластерами по принципу «дальнего соседа»

3) расстояние между центрами тяжести групп

4) расстояние между кластерами по принципу «средней связи»

5) обобщенное расстояние по Колмогорову

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

где S^k ^ - кластер, полученный объединением классов Sk и St .

Все частные случаи расстояний получаются из этой обобщенной формулы. При а = р = 1 / 2, 8 = -1/2, у = 0 имеем расстояние по принципу «ближнего соседа», при а = р = 5 = 1/ 2, у = О - «дальнего соседа»,

и и

при а =--—, р =--— ,5 = 0, у = 0 - расстояние по центрам тяже-

пк + ni пк+ ni

сти групп.

Методы кластерного анализа подразделяются на I) агломеративные (объединяющие), II) дивизимные (разделяющие) и III) итеративные.

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

Рассмотрим подробнее агломеративные методы. Агломеративные методы являются наиболее простыми и распространенными среди алгоритмов кластерного анализа. На первом шаге каждый вектор или объект Х19...,Хп исходных данных рассматривается как отдельный кластер или класс. По вычисленной матрице расстояний выбираются наиболее близкие друг к другу и объединяются. Очевидно, что процесс завершится через (п - 1) шаг, когда в результате все объекты будут объединены в один кластер.

Последовательность объединений можно представить в виде дендрограммы, или дерева. На рис. 1.18 показано, что на первом шаге были объединены векторы Xt,X2, так как расстояние между ними 0,3.

На втором шаге к ним был присоединен вектор Х3, отстоящий от кластера 12} на расстояние 0,5, и т. д. На последнем шаге объединяются все векторы в один кластер.

Дендограмма

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

К агломеративным относят методы одиночной, средней, полной связи и метод Уорда.

1. Метод одиночной связи. Пусть Xv...,Xn - векторные данные, причем каждый вектор образует один кластер. Сначала вычисляется матрица расстояний между этими кластерами, причем в качестве метрики используется расстояние по принципу ближнего соседа. С помощью этой матрицы выбирают два наиболее близких вектора, которые и образуют первый кластер 5,. На следующем шаге между S] и оставшимися векторами (которые мы считаем кластерами) вычисляется новая матрица расстояний, причем в качестве метрики используется расстояние между кластерами, объединенными в классы (а = р = 1/ 2, 5 = -1/2, у = 0). Ближайший к полученному ранее классу S{ кластер объединяется с ним, образуя S2 . И т. д. Через п— 1 шагов получаем, что все векторы объединены в один кластер.

Достоинства: 1) на каждом шаге алгоритма добавляется только один элемент, 2) метод чрезвычайно прост, 3) алгоритм нечувствителен к преобразованиям исходных данных (вращению, сдвигу, переносу, растяжению).

Недостатки: 1) необходимо постоянно пересчитывать матрицу расстояний, 2) число кластеров заранее известно и не может быть уменьшено

  • 2. Метод полной связи. Метод практически повторяет метод одиночной связи за исключением того, что включение нового объекта в кластер происходит тогда и только тогда, когда расстояние между объектами (векторами или кластерами) меньше некоторого наперед заданного числа. Число задается пользователем. Расстояние вычисляется только по принципу «дальнего соседа» (то же самое можно сказать и про расстояние между классами, объединенными в классы - только принцип дальнего соседа при ос = р = 8 = 1/2, у = 0).
  • 3. Метод средней связи. Алгоритм образования кластеров совпадает с алгоритмом одиночной связи, однако при решении вопроса о включении нового объекта в кластер вычисления производятся по принципу средней связи. Как и в методе полной связи, все вычисленные между кластерами расстояния сравниваются с задаваемым пользователем числом. И если оно (расстояние) меньше заданного числа, новый объект включается в старый класс. Таким образом, метод средней связи отличается от метода полной связи только способом вычисления расстояния между кластерами.
  • 4. Метод УОРДА. Пусть Х19...,Хп - данные, причем каждый вектор образует один кластер. Находим матрицу расстояний, используя какую-нибудь метрику (например, расстояние Махаланобиса), определяем по ней наиболее близкие друг к другу кластеры. Вычисляем сумму квадратов отклонений векторов внутри кластера Sk по формуле:

где к - номер кластера, i - номер вектора в кластере, j - номер координаты Xt е У1Р, пк - число векторов в кластере, Xjk - выборочное среднее Xi в Sk. Величина Vk характеризует отклонения векторов друг от друга внутри кластера (нового Sk +Sf или старого^ ). Расчет Vk следует проводить до и после объединения, причём нужно перебирать все возможные варианты таких объединений. В дальнейшем в кластер Sk добавляются только те векторы или кластеры, которые приводят к наименьшему изменению Vk после объединения и, как следствие, которые будут расположены на минимальном расстоянии от исходного кластера Sk.

Рассмотрим далее итеративные методы. Сущность итеративных методов заключается в том, что кластеризация начинается с задания некоторых начальных условий. Например, требуется задать число получаемых кластеров или задать расстояние, определяющее конец процесса образования кластеров, и т. д. Начальные условия выбираются согласно результату, который нужен исследователю. Однако обычно они задаются по решению, найденному одним из агломеративных методов. К итеративным методам относят метод ^-средних и метод поиска сгущений.

1. Метод /г-средних. Пусть имеются векторы Xl9...,Xn e9F и их необходимо разбить на к кластеров. На нулевом шаге из п векторов случайным образом выбираем к из них, считая, что каждый образует один кластер. Получаем множество кластеров-эталонов ,...,е[0) с весами

coj0),...,<, определяющими число элементов в них. Индекс сверху обозначает номер итерации. На этом этапе все веса равны единице. На следующем шаге из оставшегося набора данных выбираем некоторый вектор, например, X. и вычисляем матрицу расстояний между X. и эталонами е1(0),...,^0) по некоторой метрике, например по евклидовой:

На основе знания вычисленной матрицы расстояний вектор Х{ помещается в тот эталон, расстояние до которого минимально. Допустим для определенности, что это . Он заменяется новым, пересчитанным с учетом присоединенной точки, по формуле

Кроме того, пересчитывается и вес:

Если в матрице встречается два или более минимальных расстояния, то Xt включают в кластер с наименьшим порядковым номером.

На следующем шаге выбирают следующий вектор из оставшихся, и процедура повторяется. Таким образом, через (п-к) шагов каждому

эталону е^~к) будет соответствовать вес и процедура кластеризации завершится. При большом п и малом к алгоритм быстро сходится к устойчивому решению, т. е. к решению, в котором эталоны, полученные после первого применения алгоритма, совпадают по количеству и составу с эталонами, найденными при повторном применении метода. Тем не менее, алгоритмическую процедуру всегда повторяют несколько раз, используя полученное в предыдущих расчетах разбиение в качестве векторов-эталонов (как начальное приближение): найденные ранее эталоны е[п к е(2п к)к) принимаются за е(х0) 9...9е(к0) 9 и алгоритмическая процедура повторяется.

  • 2. Метод поиска сгущений. Это следующий итеративный алгоритм. Он не требует априорного задания числа кластеров. На первом шаге вычисляется матрица расстояний между ХХ9...9Хп еУ1р по какой-нибудь метрике. Затем случайным образом выбирают один вектор, который будет играть роль центра первого кластера. Это начальное приближение. Положим, что этот вектор лежит в центре р-мерной сферы радиуса R, причем этот радиус задается исследователем. После этого определяются векторы XSi,...9XSk, попавшие внутрь этой сферы, и по ним высчитывается выбо-
  • — 1 к

рочное математическое ожидание X = ~У]Х5 . Затем центр сферы пере-

носится в X , и расчетная процедура повторяется. Условием окончания итерационного процесса является равенство векторов средних X, найденных на т и (т+1) шагах. Попавшие внутрь сферы элементы Х9...9Х

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

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

Пусть ХХ9...9Хп еУ1Р - некоторая совокупность наблюдений, которая разбивается на классы S = {Sl9...9Sk}9 причем к заранее известно. Тогда основные функционалы качества разбиения при известном числе кластеров имеют вид:

1) Взвешенная сумма внутриклассовых дисперсий

где а{1) - выборочное математическое ожидание кластера Sl.

Функционал Q{(S) позволяет оценить меру однородности всех кластеров в целом.

2) Сумма попарных внутриклассовых расстояний между элементами или

где п1 - число элементов в кластере S{.

3) Обобщенная внутриклассовая дисперсия

где nj - число элементов в S., А;. - выборочная ковариационная матрица для Sj.

Функционал является средней арифметической характеристикой обобщенных внутриклассовых дисперсий, подсчитанных для каждого кластера. Как известно, обобщенная дисперсия позволяет оценить степень рассеивания многомерных наблюдений. Поэтому Q3(S) позволяет оценить средний разброс векторов наблюдений в классах Sl9...9Sk. Отсюда и его название - обобщенная внутриклассовая дисперсия. Q3(S) применяется в случае, когда необходимо решить задачу о сжатии данных или о сосредоточении наблюдений в пространстве с размерностью меньше исходной.

4) Качество классификации наблюдений можно оценить и с помощью критерия Хотеллинга. Для этого применим критерий для проверки гипотезы Н0 о равенстве векторов средних двух многомерных совокупностей и вычислим статистику

где nt и пт - число векторов в классах Sl,Sm; X, ,Хт - центрированные исходные данные; S* - объединенная ковариационная матрица кластеров SnSm: S* =---(XjXl +X^Xm). Как и ранее, значение Q4(S)

п,+пт-2

сравнивают с табличным значением, вычисленным согласно формуле

где m - исходная размерность векторов наблюдений, а - уровень значимости.

Гипотеза Н0 принимается с вероятностью (1-ос), если Q4(S) < T^m n_m, и отвергается в противном случае.

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

Если число кластеров в S = {Sl9...,Sk} заранее неизвестно, то используют следующие функционалы качества разбиения при произвольно выбираемом целом m:

II к 1 1 m

- средняя мера внутриклас-

П i=1 ni XjeSj X'tSj J

сового рассеяния,

j_

  • (1 П / 1 W
  • — X ~—~ r “ мера концентрации точек множества

п nV л J J

S, - число элементов в кластере, содержащем точку Хг

Заметим, что при произвольном значении параметра т функционал Zm(S) достигает минимума, равного I/ п, если исходное разбиение на кластеры S = {Sl9...,Sk} является разбиением на моно кластеры S. = {Xj}, так как V(Xt) = 1. В то же время Zm(S) достигает максимума, равного 1, если S - один кластер, содержащий все исходные данные,

так как V(X{) = n. В частных случаях можно показать, что Z_l(S) = —, где к - число различных кластеров в S = {Sl9...9Sk}9 ZX(S) = max — ,

*' V п )

где nt - число элементов в кластере Si9 Z^(S) = min — ,

г' п)

Заметим, что в случае неизвестного числа кластеров функционалы качества разбиения Q(S) можно выбирать в виде алгебраической комбинации (суммы, разности, произведения, отношения) двух функционалов Im(S), Zm(S), так как первый является убывающей, а другой - возрастающей функцией числа классов к. Такое поведение Zm(S)

гарантирует существование экстремума Q(S).

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>