Глава 7. Задачи о классификациях: кластерный анализ

Дальше

Назад

Начало

Конец

Список

7.3. Задача о разбиении на группы: кластерный анализ

Формулировка задачи

Пусть имеется матрица наблюдений X размерностью n´ m, строки i которой соответствуют гидробиологическим пробам, i = 1,2,…,n, а столбцы j содержат конкретные гидробиологические показатели, j = 1,2,…,m, полученные в точке наблюдения i и выраженые в шкалах измерений произвольного характера.

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

Рекомендуемая литература: [Айвазян с соавт., 1974; Миркин, Розенберг, 1978; Дюран, Оделл, 1980; Классификация и кластер.., 1980; Жамбю, 1988; Мандель, 1988].

Математический лист

Кластер определяется, как совокупность точек, лежащих на расстоянии не больше, чем r от некоторого "центра тяжести" в m-мерном пространстве (внутри гиперсферы радиуса r или гиперкуба со сторонами 2r).

В литературе описывается множество различных методов кластеризации, основанных на использовании матриц сходства, оценивании функций плотности статистического распределения, эвристических алгоритмах перебора, идеях математического программирования и др. Большая часть этих алгоритмов, при всей их несхожести, методически основаны на одной предпосылке – гипотезе компактности, т.е. “в используемом пространстве признаков измерения, принадлежащие одному и тому же классу, близки между собой, а измерения, принадлежащие разным классам хорошо разделимы друг от друга” [Кольцов, 1989].

Рассмотрим некоторые алгоритмы, основанные на использовании меры расстояния между объектами D. Введение метрики m-мерного пространства (т.е. способа оценки расстояний) является естественным приемом квантификации свойства схожести объектов: чем ближе между собой объекты в данной метрике, тем они более сходны и наоборот. Без этого само понятие “кластер” во многом теряет смысл, поэтому алгоритмы кластерного анализа часто формулируют в терминах дистанций.

Был предпринят ряд попыток разработать аксиоматический подход к введению метрических мер, согласно которым, например, расстоянием D называется двухместная действительная функция D(x₁, x₂), обладающая следующими свойствами:

D(x₁, x₂) ³ 0 – неотрицательная определенность расстояния (хотя тот же коэффициент корреляции Пирсона принимает и отрицательные значения);

D(x₁, x₂) = 0 тогда и только тогда, когда x₁ = x₂ – неразличимость тождественных объектов;

D(x₁, x₂) = D(x₂, x₁) – симметричность расстояния (хотя в разделе 4.7 приводятся примеры несиметричных мер);

D(x₁, x₂) + D(x₂, x₃) ³ D(x₁, x₃) – неравенство треугольника (длина любой стороны треугольника не больше суммы длин двух оставшихся).

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

Пусть мы имеем симметричную матрицу расстояний D между объектами исходной матрицы наблюдений:

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

Наиболее распространенную группу эвристических методов кластеризации составляют методы, основывающиеся на иерархической агломеративной процедуре (от латинского agglomero – присоединяю, накапливаю). Эти алгоритмы дают лишь условно-оптимальное решение в некотором подмножестве локальных разбиений (кластеров), однако достоинством этих методов является простота вычислений и интерпретации полученных результатов. Смысл иерархический агломеративной процедуры заключается в следующем. Перед началом кластеризации все объекты считаются отдельными кластерами, т.е. имеется p = n кластеров, каждый из которых включает по одному элементу. На первом шаге алгоритма определяются два наиболее близких или сходных объекта, которые объединяются в один кластер, общее количество которых сокращается на 1 (p ® p - 1). Итеративный процесс повторяется, пока на последнем (р - 1)-м шаге все классы не объединятся. На каждом последующем шаге агломеративной процедуры требуется пересчет лишь одной строки и одного столбца матрицы D, т.е. рассчитываются расстояния от образованного кластера до каждого из оставшихся кластеров.

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

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

Для определения расстояния между произвольной парой кластеров {X_i}, i = 1,…k₁ и {Y_j}, j = 1,…k₂ с использованием различных версий алгоритмов классификации были сформулированы следующие подходы:

метод “одиночной связи или минимального локального расстояния” (single linkage), знакомый нам по "вроцлавской таксономии", когда для включения объекта в кластер требуется максимальное сходство всего лишь с одним членом кластера;

метод “полной связи или максимального локального расстояния” (complete linkage), когда последовательность сцепления между кластерами определяются наибольшим расстоянием между любыми двумя объектами в различных кластерах (т.е. "наиболее удаленными соседями");

метод “средней связи Кинга или попарного арифметического среднего” (unweighted pair-group method using arithmetic averages), где мера сходства между "кандидатом" и членами кластера устанавливается как арифметическое среднее

. (7.8)

Выделяется также совокупность методов, использующих статистические расстояния между кластерами (метод групповых средних, центроидный метод, метод Уорда и т.д.), где предполагается объединение, приводящее к минимизации суммы квадратов отклонений между каждым объектом и центром кластера, содержащим этот объект. Например, в методе Уорда [Ward, 1963] используется мера:

, где . (7.9)

Кроме иерархических методов классификации большое распространение получили также различные итерационные процедуры, которые пытаются найти наилучшее разбиение, ориентируясь на заданный критерий оптимизации, не строя при этом полного дерева. В начале последовательных итераций в качестве центра выбирается один из элементов и формируется кластер из элементов, удаленных от него не далее чем на r. Далее процедура повторяется для остальных элементов, причем в качестве очередного центра выбирается, например, "типическая" точка – лежащая на минимальном расстоянии от центра оставшегося множества объектов. После выполнения очередного шага выясняется, достигнуто ли желательное разбиение. Существуют различные методы определения критерия остановки процедуры:

получено определенное заранее количество кластеров;

все кластеры содержат более определенного числа элементов;

кластеры обладают требуемым соотношением внутренней однородности и разнородности между собой.

На первом условии основывается наиболее популярный алгоритм – метод k-средних Мак-Кина [Фрей, 1967], в котором сам пользователь должен задать искомое число конечных кластеров, обозначаемое k. Принцип классификации заключается в следующем:

выбираются или назначаются k наблюдений, которые будут первичными центрами кластеров;

остальные наблюдения приписываются к ближайшим заданным кластерным центрам;

текущие координаты первичных кластерных центров заменяются на кластерные средние;

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

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

Другим примером критерия однородности может быть, например, функция, описанная А.А. Дорофеюком [1971]:

,(7.10)

значения которой подсчитываются для всех возможных вариантов разбиения исходного множества на m классов. В этой формуле D(p, p) – среднее сходство между собой всех векторов, попавших в одну группу, а D(p, q) – среднее сходство по всем парам векторов из разных групп p и q:

,(7.11)

где n_p и n_q – число элементов в группах p и q.

Результаты расчетов

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

Выполним в терминах меры сходства анализ воспроизводимости повторяющихся измерений, сделанных в разное время в окрестности одной географической точки. Для каждой малой реки Самарской области рассчитаем по формулам (7.11) А.А. Дорофеюка два показателя:

среднее внутригрупповое расстояние измерений, сделанных на одной станции D(p, p);

среднее межгрупповое расстояние проб, полученных на разных станциях наблюдения D(p,q).

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

для численности N_i и биомассы В_i каждого вида в пробе рассчитаем значение

X_i = ln((N_i _* В_i)^0.5) ;

пронормируем полученные величины на интервале от 0 до 1 по формуле

Y_i = ( max X_i - X_i) / ( max X_i – min X_i) ;

используем в качестве меры расстояния между пробами D(x_i, x_k) манхэттенское расстояние, равное сумме разностей нормированных ln((N_i _* В_i)^0.5), вычисленных по всем видам – см. формулу (4.32) из раздела 4.7.

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

Таблица 7.4

Среднее количество проб, взятых на одной станции наблюдения, количество пар сравниваемых между собой измерений N_D, среднее манхэттенское расстояние M_D и его доверительный интервал E_D
(отдельно для проб, относящихся к одной и той же станции и к разным станциям)

Наименование реки	Проб на станции	Внутригрупповое среднее			Межгрупповое среднее
Наименование реки	Проб на станции	N_D	M_D	E_D	N_D	M_D	E_D
Чапаевка (верховья)	10.8	812	11.82	± 0.40	7573	13.63	± 0.14
Чапаевка (низовья)	12.9	647	5.73	± 0.31	4106	6.08	± 0.11
Сок	6.8	365	14.95	± 0.63	3913	15.95	± 0.20
Байтуган	3.9	47	18.93	± 1.96	388	16.96	± 0.72
Маза	2.6	20	10.87	± 1.56	170	11.34	± 0.56
Тайдаков	2.6	10	10.42	± 3.64	45	13.25	± 1.29
Муранка	2.5	20	11.20	± 2.93	151	11.35	± 0.98

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

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

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

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

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

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

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

Выполним кластерный анализ участков реки с использованием различных методов объединения и мер расстояния:

евклидова расстояния в пространстве показателей обилия 155 видов, рассчитанных по формуле ln((N_*B)^0.5);

евклидова расстояния с использованием показателя обилия, пронормированного от 0 до 1 по максимальному размаху для каждого вида;

меры сходства по Съеренсену.

Полученные дендрограммы, представленые на рис. 7.4, свидетельствуют о том, что при выполнении кластерного анализа исследователь находится в тяжелом комбинаторном положении, будучи поставлен перед необходимостью выбора не только комплекта исходных данных, но также метрики расстояния и алгоритма объединения. Например, для тех же 14 классифицируемых станций р. Сок можно использовать не менее 5 общеупотребимых формул для матрицы сходства и не менее 5 широко распространенных методов построения иерархической классификации. В результате для 14 объектов мы получаем 25 возможных вариантов разбиений, т.е. деревьев, в разной степени отличающихся друг от друга. В итоге неопределенность исходных данных подменяется другой, еще более туманной – неопределенностью результатов классификаций.

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

Существуют некоторые, в разной степени логически размытые рекомендации по выбору технологии расчетов. Например, считается, что более изощренные центроидный метод или алгоритм Уорда приводят к хорошим результатам, хотя при сравнении фиг. “А” и “Б” рис. 7.4 серьезных изменений не обнаруживается.

Евклидово расстояние зависит только от нескольких "доминирующих" разностей, поскольку они возводятся в квадрат, и практически игнорирует длинный "хвост" небольших расхождений. Если это расстояние основывается на натуральных показателях обилия, то его величина определяется 2–3 видами с наибольшей численностью или биомассой. Если, однако, используются нормированные исходные данные, то на первый план в формировании расстояния выдвигаются редкие виды вне зависимости от их абсолютной численности. Напомним, что мера сходства по Съеренсену вообще не учитывает обилия, а только факт наличия или отсутствия каждого вида бентоса.

Любой класс (таксон, кластер), состоящий из некоторого подмножества реальных объектов и полученный по технологии "без учителя" – всегда некоторая умозрительная теоретическая конструкция, созданная из субъективных предположений или на основе эвристических алгоритмов, качество которой принципиально невозможно точно измерить. Сказать, например, что классификация “Г” лучше, чем “В”, может только коллектив компетентных экспертов, основывающийся, чаще всего, не на формальных критериях, а на интуитивном опыте. Правда, один из авторов [Розенберг, 1975] предлагал в качестве формализации такого сравнения вычисление меры диссонанса полученной классифицированной матрицы (напрмер, матрицы сходства, упорядоченной по последовательности “Г”) от "случайно перемешанной" матрицы (т.е. матрицы, упорядоченной по случайной последовательности станций); чем больше мера диссонанса, тем лучше классификация. Этот эвристический прием был весьма эффективно использован при анализе мозаичности травянистых растительных сообществ на ценотическом уровне [Миркин, Розенберг, 1977а].

Нетривиальной является и задача оценки близости (предупорядоченности) двух произвольных деревьев, состоящих из одних и тех же "листьев". Чтобы дать точный ответ, значимо ли отличаются друг от друга варианты классификаций, следует провести, своего рода, кластерный анализ результатов кластерного анализа [Миркин, Черный, 1970; Наумова, 1979]. Например, В.Л. Андреев [1979а] рекомендует использовать в этом случае графо-аналитические методы, известные под общим названием "поиск лидера" и основанные на ранговой корреляции последовательностей агрегируемых элементов, однако, подробное рассмотрение этой задачи выходит за рамки нашей монографии.

Дальше

Назад

Начало

Конец

Список