ласти, а не в прилегающих областях. Можно сказать, что[век торы измерений имеют тенденцию группироваться вблизи моды. Анализ набора векторов измерений, имеющий цель выявить эту тенденцию, называется-.,кластерным анализом, или просто jклacтepизaциe й. {

[ Методы кластеризации разрабатывались с целью выявления свойственной данным или естественной структуры данных. Чтобы проиллюстрировать понятие «естественная структура», предположим, что нам необходимо было отразить в двухмерном пространстве измерений рост и массу множества случайно выбранных взрослых людей. Результат может быть таким, как показано на рис. 111.24,0. Не имея никакой дополнительной информации об измеренных индивидуумах, мы бы заключили, чтО получившиеся кластеры отвечают соответственно мужчинам (в среднем выше и тяжелее) и женщинам (в среднем ниже и легче). В действительности, если бы у нас были на то основания, мы могли бы провести границу решения между кластерами и последовательно классифицировать всех индивидуумов, измерения которых оказываются по одну сторону от границы, как мужчин, а по другую - как женщин. Разумеется, такая классификация иногда будет ошибочной, но мы будем иметь некоторую, вполне оправданную уверенность в том, что наша классификация в большинстве случаев будет правильная, чем ошибочная. Заметим, что, применив такую стратегию классификации, мы не использовали обучающие выборки в смысле, описанном ранее. Это значит, что при построении границы решения мы не пользовались априорными данными об истинной классификации каждого отдельного набора измерений. Однако использовались другие данные и предположения об измеряемых объектах: мы знали, что они взрослые и предполагали, что среди них есть, мужчины и женщины.

Теперь предположим, что располагаем набором многоспектральных обучающих образов, о которых известно из наземных наблюдений, что они относятся к пшеничным полям. Предположим далее, что рис. HI.24, б представляет графическое отображение этих данных в видимом и ближнем инфракрасном диапазонах длин волн. Применяя наши знания о 1) пшеничных полях, 2) времени года и 3) физиологии пшеницы, можем предположить, что естественная структура этого множества данных отображает совершенно разные стадии зрелости сельскохозяйственных культур и, возможно, еще различия сортов. В любом случае класс «пшеница» имеет многомодальную функцию плотности вероятностей, и это один из случаев, когда один многомодальный класс должен быть разбит на одномодальные под-клас.сы.

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

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

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

Мужчины

женщины

60 80

Масса, кг

Рис. 111.24. Данные, имеющие тенденцию к образованию кластеров: а - распределение взрослых людей по росту и массе, б - многомодальное распределение данных с пшеничных полей {гипотетическая иллюстрация)

ИЛИ классу приложений [12, 13]. Мы обсудим одно из них, которое широко использовалось в применениях многоспектраль-

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

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

На рис. П1.25 определяется также расстояние, как сумма компонент расстояния. На некоторых ЭВМ это расстояние между точками вычисляется несколько легче евклидового расстояния, и поэтому его использование может привести к получению более быстрого алгоритма при соответствующей реализации. Однако имеются и другие меры межточечного расстояния, некоторые из них придают различные веса разным компонентам (например, расстояние Махаланобиса [13], с. 24, 21,3-217). Но евклидово расстояние и Li-расстояние вычисляются наиболее просто и широко используются в алгоритмах кластеризации, принятых для анализа данных дистанционных измерений. 182

/ I

"i

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

(Orbi

В двухмерном пространстве, п=2

i]-расстояние

Рис. 111.25. Различные меры расстояний- между точками пространства

Существует много способов и для определения и измерения расстояния между группами точек.

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

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

Было изучено много критериев кластеризации [13]. Обычно, однако, они отражают назначение точек в кластеры таким образом, что расстояния между точками внутри кластера минимальны, а расстояния между кластерами максимальны. Посмотрим, как это связывается с нашим предыдущим обсуждением межточечных и межгрупповых расстояний. Для этого-очень кратко остановимся на двух критериях кластеризации.

Широко используемый критерий кластеризации, которому, как было показано, эквивалентны многие другие критерии,- это критерий суммы квадратов ошибок. Пусть мы имеем с кластеров. Mi - вектор математического ожидания для (-го кластера [вычислен по формуле (III.5)], а Ci- набор точек данных, принадлежащих i-му кластеру. Тогда сумма квадратов ошибок

СКО = 2 WX-Mi, (111.42)=

i=l ХеС.

где \\Х-MiW-евклидово расстояние между X и Mi. Другими словами, СКО - это совокупное расстояние между каждой точ-