Капралов Е.Г., Кошкарев А.В., Тикунов В.С. и др. Геоинформатика

Подождите немного. Документ загружается.

где

NW *ы

'"'Nt.

Краткая характеристика методов классификации. Все возмож-

ные типы методов классификации можно подразделить по различ-

ным основаниям на некоторые группы. Основаниями для система-

тизации методов классификаций в экологии и географии чаще всего

являются цель классификации, определение класса, наличие обу-

чающей выборки, использование географического пространства,

наличие априорной информации о статистических свойствах клас-

сов,

способ подачи ОТЕ на вход классификатора.

По цели чаще всего выделяют оценочные и типологические

классификации. Оценочные классификации необходимы для ана-

лиза и сравнения ОТЕ в терминах хорошо-плохо и лучше-хуже,

типологические

—

для выделения некоторых устойчивых типов ОТЕ.

По степени учета географического про-

странства методы классификации подразделяются на исполь-

зующие и не использующие его в собственно математических про-

цедурах.

По определению класса методы классификаций быва-

ют обычные и нечеткие. Методы нечеткой классификации опреде-

ляют вероятность принадлежности ОТЕ к каждому из классов, а

не относят ОТЕ однозначно к одному из них.

По наличию обучающей выборки методы класси-

фикации подразделяются на методы контролируемой и неконтро-

лируемой классификации, также называемые классификациями

«с учителем» и «без учителя» (автоматические классификации).

По наличию априорной информации о статис-

тических свойствах классов возможны параметрические

и непараметрические методы классификации. Целью параметри-

ческих методов является отыскание неизвестных параметров изве-

стных функций распределения ОТЕ в пределах каждого класса и

вероятностей появления этих классов. Непараметрические методы

обычно разделяют на иерархические и неиерархические, а после-

дние — на эвристические и оптимизационные. Иерархические ме-

тоды формируют нужное количество классов путем последователь-

ного объединения отдельных ОТЕ или разбиения единственного

класса, содержащего все ОТЕ. Эвристические процедуры основа-

ны на интуитивном представлении исследователя о конечной цели

классификации. Оптимизационные алгоритмы производят разбие-

ние таким образом, чтобы обратить в максимум выбранный функ-

ционал качества.

По способу подачи ОТЕ на вход анализа разли-

чают последовательные и параллельные методы классификации.

Последовательные методы просматривают по очереди все ОТЕ один

раз,

начиная с о

и заканчивая o

. Параллельные процедуры требу-

ют подачи на вход классификатора сразу всех ОТЕ.

Оценочные и типологические классификации. Оценочные клас-

сификации используют для получения нескольких классов S

S>, для которых можно сказать, лучше или хуже представители

одного класса представителей другого (а иногда и насколько луч-

ше или хуже). Всегда считается, что классы ОТЕ, полученные в

результате проведения оценочной классификации, упорядочены

специальным образом, т.е.

{

< S

<... < S

или S

> S

> ... > S

Под обозначением Sj <Sj понимается, что любая ОТЕ /-го клас-

са лучше ОТЕ у-го класса по комплексу показателей. Считается

также, что в пределах каждого класса ОТЕ приблизительно одина-

ково хороши или одинаково плохи (в разрезе проблемы, описыва-

емой показателями).

Обязательным этапом в оценочных классификациях является

переход к единственному признаку. Результирующий показатель

получают таким образом, чтобы классы ОТЕ с его минимальными

значениями могли интерпретироваться как «плохие», а с макси-

мальными как «хорошие», или наоборот. Например, пусть в ка-

честве ОТЕ выступают земельные участки, а в качестве показате-

лей

—

тип почв, удаленность от водных ресурсов, близость к транс-

портной сети и т.д. Тогда целевым признаком может быть степень

целесообразности постройки жилого дома. В зависимости от значе-

ний целевого признака ОТЕ могут разбиваться на три класса: «не-

пригодные для строительства», «приемлемые» и «наилучшие для

строительства».

Целью типологических классификаций является получение ус-

тойчивых групп ОТЕ в Af-мерном признаковом пространстве, т.е.

возможных «типов» ОТЕ. В отличие от оценочных классификаций,

показатели редко интерпретируются как «хорошие» или «плохие»,

а результирующие классы могут содержать ОТЕ с «хорошими» зна-

чениями по одному показателю и «плохими» по другому. Приме-

ром типологической классификации может служить выявление

закономерности сочетания тяжелых металлов (свинца, меди, цинка,

железа) в культурном лессовом слое городища средневекового Са-

марканда по четырем этапам

VII—VIII,

IX—X,

XI—XIII

и XX вв.

н. э. [А. К. Евдокимова и др.,

1988].

После проведения типологичес-

кой классификации специалистами по теме исследования всегда

дается содержательная интерпретация каждому классу-типу, т.е.

выделяются диапазоны изменения каждого показателя на ОТЕ этого

класса.

Нечеткие классификации. Иногда ставится более широкая (по

сравнению с уже описанной канонической) задача нечеткой (раз-

мытой) классификации. Этот тип классификации должен приме-

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

рактер. Например, в работе [А. М.Трофимов, Н.М.Солодухо, 1986]

отмечено, что «... исходя из принципа комплексности взаимодей-

ствия в пространстве частей различной природы, в принципе можно

считать, что размытость границы — это ее естественное состоя-

ние,

тогда как границы ясной и четкой линейной или полосной

выраженности представляют собой лишь частный случай проявле-

ния граничности геосистем».

Основное отличие нечеткой классификации от канонической

состоит в получении не номеров классов для всех ОТЕ, а вероят-

ностей принадлежности ОТЕ к каждому из классов. При необхо-

димости однозначного отнесения ОТЕ к одному из классов (т.е.

сведения результатов нечеткой классификации к каноническому

случаю) находится тот класс, в котором появление ОТЕ наиболее

вероятно.

Использование географического пространства при классифика-

циях. Формирование классов при проведении многих классифика-

ций происходит в общем случае на основе и географического, и

атрибутивного признакового пространств. Однако, исходя из сте-

пени использования географического пространства, возможны

следующие варианты (либо их комбинации, за исключением пер-

вого):

• географическое пространство при классификации не исполь-

зуется;

• географическое пространство используется перед проведени-

ем классификации при формировании признаков атрибутивного

пространства (соответствующие примеры были приведены при

обсуждении представления атрибутивного пространства в виде таб-

лицы ОТЕ-признак);

• географическое пространство используется при визуализации

хода и результатов классификации (т.е. ход и результаты анализа

картографируются);

• географическое пространство представлено матрицей близос-

тей вида ОТЕ-ОТЕ, которая используется алгоритмом классифи-

кации вместе с матрицей, представляющей атрибутивное призна-

ковое пространство.

Обозначим, как это было и ранее, матрицы ОТЕ-признак и

ОТЕ-ОТЕ для атрибутивного признакового пространства симво-

лами X и А соответственно, матрицу ОТЕ-ОТЕ географического

пространства — символом G.

Примером географических классификаций является группиро-

вание регионов (ОТЕ) по силе связей (наиболее часто — эконо-

мических). Целью такой классификации является получение групп,

связи между ОТЕ которых максимальны. Географические расстоя-

ния здесь задаются отдельной таблицей и являются одним из ви-

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

мещения товара из одной ОТЕ в другую.

Еще один вид классификации с использованием матриц сразу

двух пространств (причем матрица вида ОТЕ-ОТЕ, представляю-

щая географическое пространство, бинарная) — районирование.

Под районированием понимается деление территории на множе-

ство непересекающихся целостных районов, представляющих со-

бой компактные сгущения ОТЕ как в географическом, так и в

признаковом пространствах [В. И. Блануца, 1993. — С. 3]. В класси-

ческом географическом понимании это разделение территории по

принципу их различия, непохожести. Матрица расстояний G в

данном классе методов представлена таблицей смежности. В тер-

минах районирования синонимом класса с ограничением на его

пространственную нерасчлененность является понятие района.

В основе постановки задачи районирования лежит необходи-

мость территориального управления ОТЕ. Ограничением райони-

рования, помимо пространственной нерасчлененности классов,

являются также целостность получаемых классов-районов, а воз-

можно и учет прежней административно-территориальной сетки

(например, экономических районов, федеральных округов).

Обучающая выборка. При проведении классификаций очень

важно максимально использовать при анализе априорную инфор-

мацию о классах, которые необходимо сформировать. Такой ин-

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

выборка, т.е. множество ОТЕ, для каждой из которых известна ее

принадлежность одному из классов.

Обладание обучающей выборкой в большинстве случаев облег-

чает проведение классификаций и повышает их качество. Она мо-

жет использоваться для настройки математических моделей — вы-

бора метрики d и показателя качества классификации Q, опреде-

ления числа классов К, их ядер и т.д. Например, при проведении

классификации стран мира по уровню социально-экономического

развития, как это описано в работе [В.С.Тикунов,

1997],

обучаю-

щая выборка состояла из нескольких наиболее типичных стран-

представителей каждого класса, что позволило осмысленно с точ-

ки зрения географии сформировать классы.

Оценивание

истинного количества классов. Очень часто при прове-

дении классификаций необходимо оценивать количество классов,

которые необходимо сформировать. Для определения истинного

количества классов

ИСТ

существует достаточно простой, но широ-

ко используемый подход. Этот подход основан на использовании

значений функционала качества классификации Q(K), рассчитан-

ного для количества классов К е [К^,К

тах

]. Истинное значе-

ние

Аист

лежит сразу после последнего резкого скачка функциона-

ла качества Q(K). Это означает, что увеличение количества классов

не дает затем существенного прироста в качестве классификации.

При решении конкретной задачи целесообразно задаваться ми-

нимально и максимально возможными количествами классов К

тт

и (например,

min

= 2 и

mSkX

= 10). Чем больше диапазон, тем

легче находить

ист

и тем больше вычислений придется произвести.

Предварительная обработка данных. Важным этапом классифи-

кации ОТЕ является их предварительная обработка, часто включа-

ющая нормировку, взвешивание, снижение размерности и агре-

гирование.

Нормировка показателей. На практике при проведении класси-

фикаций очень редко встречаются ситуации, когда анализируе-

мые показатели представлены в одинаковых единицах измерения

и масштабе. Существуют специальные термины для обозначения

соизмеримых и несоизмеримых систем показателей (монострук-

турные и полиструктурные соответственно). Примером монострук-

турной системы показателей является процент занятых по разным

отраслям промышленности.

Наиболее часто используются следующие виды нормировки.

1. Нормировка по заданному показателю.

В социально-экономической географии чаще всего нормирую-

щим показателем является общая численность населения ОТЕ или

площадь занимаемой ОТЕ территории.

Пусть

(Л

_ исходный признак, j е

{1,Л/},

фпогт _ нормирующий признак.

Тогда нормировка заключается в пересчете

°i

Примеры нормировки по заданному показателю:

• показатель плотности населения (нормировка численности

населения ОТЕ площадью, занимаемой ОТЕ);.

• процент голосов, отданный на выборах за какую-либо поли-

тическую партию (нормировка числа проголосовавших за партию

в данной ОТЕ общим числом избирателей);

• валовой внутренний продукт страны (ВВП) на душу населе-

ния (нормировка ВВП общим числом граждан; в качестве ОТЕ

выступают страны мира).

2. Нормировка по заданным значениям осуществляется по об-

щей формуле

gU)

o^>-A, у/€{1,...,А/},/€{1,...,ЛГ}.

(2.28)

Д2

В качестве А, в числителе выступает число, отклонения от кото-

рого наиболее интересны; А

представляет величину разброса зна-

чений ОТЕ по заданному показателю. Ниже приведены наиболее

известные разновидности нормировки

по

заданным значениям (слу-

чаи

2.1 и 2.2).

2.1.

Нормировка

по

дисперсиям

математическим ожиданиям.

Целью данной нормировки является приведение каждого пока-

зателя

стандартному виду

(в

результате математическое ожида-

ние любого показателя становится равным нулю,

дисперсия

—

единице).

Пусть

qU)

_ —у

и) _

оценка математического ожиданияу-го пока-

зателя,

var(o

) =

—£(о,-

-о

)

—

оценка дисперсии

у-го

показа-

ла

теля.

Тогда нормировка заключается

пересчете

5j"

= % L~ V/ е

{1,....

М}, i

€

{1,....

N),

/var(o

(

)

т.е.

Д, = о"), д

= Vvar(o<»). (2.29)

2.2.

Нормировка

по

наилучшим

или

наихудшим значениям

[В.С.Тикунов,

1985].

Целью данной нормировки является перевод показателя

про-

центы отклонений

от

заданного наилучшего

или

наихудшего зна-

чения

с.

Пусть

min{o<»|/6l,...,^b

o<& = max{oP|i€l,...,tf},

Тогда нормировка заключается

пересчете

о?

°^~

и)

{1,....

М}, /

{1,....

Т.

е.

Ai=c, Д

=о<&-о<£.

(2.30)

Часто

(не

всегда)

качестве

берут максимальные

или

мини-

мальные значения у-го показателя

или о^

Допустим, макси-

мальное значение показателя

до

нормировки соответствовало наи-

лучшей ситуации

в ОТЕ

(например, ожидаемой продолжительно-

сти жизни). Если нормировать показатель

по

максимальному зна-

чению,

то

нулю будет соответствовать наилучшее значение, еди-

нице

—

наихудшее.

Полученные в результате нормировки по наилучшим или наи-

худшим значениям oj

ограничены отрезком

[0,1].

Иногда в фор-

мулу нормировки вводят умножение на 100, изменяя диапазон

значений на отрезке [0,100].

В ряде случаев требуется нормировать показатели по наилуч-

шим или наихудшим УСЛОВНЫМ значениям. Например, для оценок

заболеваемости теоретически наилучшее значение — нуль, т.е.

можно положить с = 0 ё [о$

л9

ojfij.

При этом следует изменить

знаменатель в формуле нормировки:

с-^, если о о<&,

otil-c,

еслис<о

(2.31)

ССЛИ

€[0^,О<&].

Взвешивание показателей. Процесс получения весов для пока-

зателей необходим для корректного проведения классификаций.

Зачастую, по аналогии с различными единицами измерения по-

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

метной области. Исследователь, например, может включить в чис-

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

различия степени их влияния на конечный результат уменьшить

влияние второстепенных показателей, «взвешивая» их. Такое взве-

шивание может заключаться в делении уже нормированного пока-

зателя j е{1, ...,Л/} на какое-либо число / € R, т.е. присвоении

показателю веса со, = -.

При типологических классификациях знак веса никак не влия-

ет на результат анализа, поскольку исходный показатель можно

умножать на

-1.

В случае использования показателей для проведе-

ния оценочных классификаций их знаки могут оказаться решаю-

щими. Так, взвешивание может заключаться только в домножении

некоторых показателей на

-1,

чтобы увеличение значений любого

из них сигнализировало бы или об улучшении, или об ухудшении

ситуации в рассматриваемой ОТЕ.

Способы получения объективных весов для показателей раз-

личны. Наиболее часто используется экспертный метод, при кото-

ром специалист или их группа в конкретной предметной области

оценивает важность каждого показателя. Существуют также и так

называемые аналитические методы. Проблема взвешивания пока-

зателей в географических исследованиях обсуждается в работе

[В.

С. Тикунов,

1997].

После нахождения вектора весов

со

= (со,,<ь

) он применя-

ется либо к матрице ОТЕ-признак, либо используется при расчете

расстояний между ОТЕ в признаковом пространстве.

Анализ главных компонент. Анализ главных компонент, или

компонентный анализ, — один из наиболее часто используемых

методов снижения размерности. Данным методом решается задача

отыскания на основе существующей системы атрибутивных при-

знаков, описывающих ОТЕ, новой системы со следующими свой-

ствами:

• признаки новой системы являются линейными комбинация-

ми признаков исходной системы;

• количество признаков в новой системе в общем случае не

больше, а на практике всегда меньше числа признаков в исходной

системе;

• признаки новой системы ортогональны, т.е. не коррелиро-

ваны;

• признаки новой системы упорядочены в порядке убывания

дисперсии;

• признаки новой системы несут столько же информации (или

наперед заданный процент информации, например 90 %) об из-

менчивости объектов, сколько и исходные признаки. Под инфор-

мацией понимается дисперсия признаков.

Метод главных компонент следует применять для исправления

искаженного взаимными корреляциями исходного пространства

признаков, снижения объемов хранящихся данных без потери су-

щественной части информации об ОТЕ, визуализации ОТЕ в про-

странстве признаков (что достигается, например, изображением

ОТЕ в виде точек на плоскости первых двух главных компонент) и

выявления латентных (т.е. скрытых, не наблюдаемых в явном виде)

показателей, отражающих суть процесса или явления.

В матричной форме результат работы метода главных компо-

нент записывается в следующем виде:

Z = XL или

Z„

NxM

Mxnn

(2.32)

где М — количество исходных признаков; т — количество полу-

ченных главных компонент, т < М\ Z =

Nxm

(,)

{m)

) —

матрица новых признаков (как и в исходной матрице, признаки

расположены по столбцам); X = X

NxM

= (о

(,)

,о

(А/)

) — исходная

матрица ОТЕ-признак; L =

Mxm

(,)

(т)

)

— вычисленная

матрица компонентных нагрузок.

Наиболее просто воспринимается геометрическая интерпрета-

ция метода главных компонент. В многомерном пространстве при-

знаков ОТЕ рассматриваются как точки, геометрическая структу-

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

нает Л/-мерный эллипсоид. За новые признаки принимаются глав-

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

уменьшения дисперсий ОТЕ по осям.

Применение метода главных компонент в качестве предвари-

тельного этапа классификации описано в подразд. 3.1 «ГИС и дис-

танционное зондирование». Компонентный анализ является не

единственным методом снижения размерности. В качестве приме-

ров других распространенных методов снижения размерности можно

отметить факторный анализ, многомерное шкалирование и метод

экстремальной группировки признаков.

Агрегирование. Агрегирование в наиболее простой интерпрета-

ции является одним из методов перехода от множества исходных

показателей к единственному, по которому следует различать ОТЕ.

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

измеренными в различных шкалах, и служат для получения иерар-

хии признаков.

Агрегирование очень часто используется в географических и

экологических исследованиях, поскольку позволяет получать оце-

ночные классификации по многим показателям. Чаще всего ре-

зультирующий показатель получают таким образом, чтобы ОТЕ с

его минимальными значениями могли интерпретироваться как

«плохие», а с максимальными — как «хорошие» (в разрезе пробле-

мы,

описываемой показателями), или наоборот.

Ограничимся рассмотрением двух наиболее часто используемых

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

ющий признак

(agr)

(o,

(agr)

,о^)

путем:

• суммирования значений предварительно нормированных и

взвешенных показателей, т.е.

• расчета расстояний до наилучшей или наихудшей (возможно

условной) ОТЕ о\ т.е.

o™=d(o

o').

В первом случае нормировка показателей может производиться

и по дисперсиям, и по наилучшим (наихудшим) значениям. Важ-

но,

чтобы после нормировки большие (меньшие) значения всех

показателей указывали на лучшую (худшую) ситуацию в ОТЕ, или

наоборот. Если нормировка производилась по дисперсиям (и соот-

ветственно направление признаков не учтено), необходимо до-

множить, например, группу негативных признаков на -1. Метод

главных компонент для «исправления кривизны» признакового про-

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

ные компоненты могут не быть в общем случае интерпретируемы-

ми в терминах хорошо-плохо.

Второй метод подразумевает образования (ЛГ+1)-й условной ОТЕ

о\

показатели которой являются наилучшими (наихудшими). Век-

тор о' = (о\, ...,о'д/) покоординатно необходимо дописать в матри-

цу ОТЕ-признак. Далее показатели можно (и нужно) нормиро-

вать,

взвешивать, проводить компонентный анализ. После этого и

рассчитываются расстояния от (#+1)-й условной ОТЕ о'до всех

остальных ОТЕ и формируется новый признак. Большие значения

этого признака сигнализируют о худшей (лучшей) ситуации в ОТЕ

по комплексу исходных показателей.

Можно заметить,- что второй метод сводится к первому при

нормировке по наилучшим (наихудшим) значениям, без приме-

нения метода главных компонент, и использовании манхэтген-

ского расстояния d

(т.

е. первый метод — частный случай второго).

Методы классификации, основанные на описании классов ядра-

ми.

«Ядерные» методы нацелены на выявление сгущений ОТЕ в

признаковом пространстве и ранее носили чисто эвристический

характер, так как понятие компактности ОТЕ в признаковом про-

странстве не было формализовано. Для ряда эвристических проце-

дур с развитием теории были найдены функционалы качества

разбиения на группы и тем самым формализовано соответствую-

щее им понятие компактности

[С.

А.

Айвазян и др., 1989. — С. 217].

В соответствии с этим алгоритмы классификации, основанные на

описании классов ядрами, подразделяют на эвристические и оп-

тимизационные. Кроме того, методы можно разделить по способу

подачи ОТЕ на вход алгоритма. Если ОТЕ подаются по одному

(последовательно), то соответствующие процедуры называются

последовательными. Если на вход алгоритмов подаются сразу все

ОТЕ, то они называются параллельными. Преимуществом после-

довательных процедур является высокая скорость работы, парал-

лельных — независимость получаемой классификации от порядка

ОТЕ в исходном множестве О.

Под ядром класса подразумевается некоторая реально существу-

ющая или условная наиболее «представительная» ОТЕ, весь комп-

лекс характеристик которой является эталоном данного класса.

Часто алгоритмы, основанные на описании классов ядрами, ис-

пользуют процедуру классификации ОТЕ к ядрам по минималь-

ности расстояний:

• задаться метрикой d;

• найти ядра классов;

• классифицировать все ОТЕ к ядрам по минимальности рас-

стояния до них.

Для нахождения ядер обычно используют обучающую выбор-

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

меняют специальные формальные процедуры.

Некоторые эвристические подходы к выбору ядер. Некоторые

эвристические формализованные процедуры выбора ядер классов

известны уже более двух десятков лет [В.С.Тикунов,

1978].

Во-первых, отыскивать ядра классов можно исходя из принци-

па их максимальной гетерогенности. Например, в качестве первых

двух ядер можно выбрать две ОТЕ, наиболее отличающиеся между

собой по комплексу показателей. Далее, если уже имеется (К-1)