Тикунов В. С. Геоинформатика. Параметрические методы классификации, основанные на модели смеси распределений. Иерархические методы классификации.

Скачать полную версию учебника (с рисунками, формулами, картами, схемами и таблицами) одним файлом в формате MS Office Word Скачать книгу

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

Формула (доступно при скачивании полной версии книги)

Модель смеси распределении применительно к задачам классификации подразумевает, что i -й класс полностью характеризуется i -й компонентой смеси и вероятностью ее появления. Задача классификации ОТЕ состоит в определении, в рамках какого из классов появление данной ОТЕ наиболее вероятно.
Самым сложным этапом при классификации на основе модели смеси распределений является процедура идентификации смеси, т. е. алгоритм получения числа классов М и оценок для pi и 9i , которые необходимы для построения решающего правила. Не все смеси идентифицируемы, т.е. не для всех типов распределений можно найти единственные оценки М, pi и 9i . Например, смесь нормальных распределений идентифицируема, а смесь равномерных — нет.
Существуют различные подходы к оцениванию по множеству ОТЕ параметров смеси, наиболее распространенным из которых является ЕМ-алгоритм.
Название ЕМ-алгоритм происходит от сокращений английских терминов Estimation (оценивание) и Maximization (максимизация).
Этот метод для фиксированного числа классов (элементов смеси) К позволяет определять оценки параметров смеси pi и 9i , iє (1,..., К) путем многократного нахождения очередных приближений к оценкам (шаг Estimation) и максимизации с учетом приближений функции правдоподобия (шаг Maximization).

Иерархические методы классификации. Иерархические методы классификации нацелены либо на последовательное объединение исходных ОТЕ в заранее заданное или незаданное меньшее количество классов, либо, наоборот, на расчленение одного или нескольких классов до нужной степени детализации. Процедуры первого типа носят название иерархических агломеративных алгоритмов классификации, второго — иерархических дивизимных алгоритмов классификации.
Исходной информацией для проведения иерархической классификации обычно служит матрица близостей вида ОТЕ-ОТЕ. Исключением является, например, дивизимный алгоритм на основе метода 2-средних (т. е. метода k-средних при k = 2).
Преимуществами иерархических алгоритмов являются возможности их применения без наличия априорной информации о свойствах классов (например, ядер классов или обучающих выборок), модификации для целей географического районирования, применения при неизвестном числе классов и наглядной визуализации хода и результатов классификации на специальном графике, который называется дендрограммой:

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

На оси х этого графика изображаются ОТЕ (в том порядке, в котором они объединялись или разъединялись), по оси у — либо шаг алгоритма, либо расстояние между вновь объединяемыми или разделяемыми классами. Два объединяемых или разъединяемых класса соединяются П-образной линией. Ее нижние концы упираются в середины двух классов, а длины вертикальных отрезков равны расстоянию между классами.
К недостаткам иерархических процедур следует отнести большую вычислительную стоимость их реализации. Данный недостаток частично компенсируется существованием так называемых «быстрых» (или «пороговых») иерархических алгоритмов.

Агломеративные алгоритмы. Классический агломеративный алгоритм иерархической классификации начинает свою работу с формирования К1 = N классов (при этом каждая ОТЕ на нулевом шаге представляет отдельный класс) и проводит в общем случае I=N-1итерацию. На каждом шаге алгоритма происходит объединение двух «ближайших» классов в один, т.е. Кп - 1 = Кп+1. Последний (TV-l)-ft шаг алгоритма характеризуется объединением двух сформированных на предыдущих этапах классов в один класс, включающий в себя все имеющиеся (поступившие на вход анализа) ОТЕ. Выбор расстояния настолько влияет на результат классификации, что зачастую оно вносится в название алгоритма (например, «агломеративный алгоритм средней связи»).
Если число классов К, которое нужно получить, известно заранее, достаточно провести I=N-К итераций, в результате которых и будет сформировано ровно К классов. Если количество классов заранее неизвестно, то анализируются либо значения функционала качества разбиения для К є (2, ..., Кmax), либо применяются другие методы (см., например, метод анализа сложности группировочного дерева в работе В. И. Блануца, 1993. — С. 94). Информацию о количестве классов может дать и визуальный анализ дендрограммы.
Необходимо отметить существование так называемых «быстрых» агломеративных алгоритмов. Они основаны на использовании некоторой заранее задаваемой или настраиваемой в процессе классификации последовательности пороговых значений с1, ..., сI (при этом вполне возможно, что сi = с = const Vn є (1, ..., I).
На очередной итерации алгоритма п є(1,..., I) объединяются те классы, расстояния между которыми не превышают заданного порога сi. Таким образом, на каждом шаге не требуется искать минимальный элемент в матрице расстояний. При верном выборе пороговых значений такой подход повышает скорость работы алгоритма без потери качества классификации.
Детальное описание процедур агломеративных иерархических классификаций можно найти в работе [М.Жамбю, 1989].

Скачать полную версию учебника (с рисунками, формулами, картами, схемами и таблицами) одним файлом в формате MS Office Word Скачать книгу