Экзаменационный билет номер 6

Параметрические и непараметрические методы классификации, обоснование их применения

Непосредственное построение разделяющих или решающих функций без предположений о каких-либо закономерностях группировки образов внутри классов, которые можно описать математическими функциями, часто называют непараметрическим подходом. Применение непараметрического подхода целесообразно в тех случаях, когда нам ничего неизвестно о каких- либо закономерностях распределения образов внутри классов. При тематической обработке изображений земной поверхности такой метод бывает очень удобен для оценки положения определенных тематических категорий в признаковом пространстве. Простейший вариант этой процедуры реализуется в пакете ERDAS Imagine путем построения обучающих спектральных сигнатур непосредственно в признаковом пространстве (Selecting Feature Space Objects). Некоторые разновидности непараметрического подхода, применяющиеся при обработке изображений, рассмотрены в [11,12,18,19]. При большом количестве образов, классов и признаков-измерений непараметрическая классификация становится чрезвычайно сложной и чаще, в том числе и при поэлементной классификации изображений, используются методы, априори предполагающие существование некоторых закономерностей внутри классов. Такие методы мы и будем в дальнейшем рассматривать

Алгоритм вычисления оценок

Мы рассмотрим здесь один из наиболее простых и распространенных логических методов распознавания - алгоритм вычисления оценок (метод голосования) [24,25]. Он может применяться в тех случаях, когда выделяемые классы характеризуются наличием определенных комбинаций признаков-индикаторов, причем некоторые из этих признаков или комбинаций имеют различную значимость (вес) для разных классов. Суть метода заключается в следующем. Пусть для наших объектов (образов) задан набор булевых признаков S={s1,…,sn} и перечень классов W={w1,…,wK}, по которым мы хотим распределить эти объекты. Рассмотрим основные этапы построения алгоритма вычисления оценок. 1. На основе анализа доступных данных формируем типичные для каждого класса наборы значений булевых переменных {s1,…,sn}. Удаляем наборы, одинаковые для разных классов. В ряде случаев, чтобы «уравновесить» такие наборы по классам, целесообразно ввести весовые коэффициенты, характеризующие степень «типичности» определенных наборов в каждом классе. 2. Выделяем опорные множества - группы признаков SlÌS, l=1,…,L по которым лучше всего определяется принадлежность объекта тому или иному классу. Если таковые выделить не удается, в [22], например, предлагается использовать все возможные наборы. Однако такой подход сильно увеличивает вычислительную емкость и далеко не всегда оправдан. 3. Задаем меру близости dl , l=1,…,L между наборами признаков объектов внутри каждого множества Sl и правила вычисления оценки gl подобия образов на множестве Sl . Самой простой мерой близости является совпадение наборов по каждому опорному множеству Sl . 4. Задаем правила вычисления оценок Gkl=aklgl k=1,…,K, l=1,…,L для каждого из K классов на основе выбранных оценок подобия между образами. Заметим, что вместо введения весовых коэффициентов на полные наборы булевых переменных, как предложено в пункте 1, можно ввести весовые коэффициенты akl на каждое из опорных множеств. 5. Выбираем вид суммарной оценки Gk=SbklGkl по всем опорным множествам для принятия решения о принадлежности объекта тому или иному классу. Коэффициенты bkl определяют значимость каждого из L опорных множеств. В простейшем случае они могут быть равны единице. При распознавании для каждого предъявляемого системе образа вычисляются оценки Gkl по опорным множествам и суммарные оценки Gk по всем K классам. Решение о принадлежности объекта тому или иному классу принимается по максимальному значению оценки Gk , то есть по “большинству голосов” в пользу данного класса. Таким образом, достоинством данного метода является оценка не по отдельным признакам, а по группам. Поскольку каждая группа может иметь свой весовой коэффициент, и для каждого класса группы могут браться тоже со своими весовыми коэффициентами, то этот метод можно рассматривать как «промежуточный» между статистическими и чисто логическими методами классификации. Чисто логические методы ближе к теории экспертных систем.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 7

ЭКЗАМЕНАЦИОННЫй БИЛЕТ № 7

1.Обоснование применения алгоритмов кластерного анализа (неконтролируемой классификации) при тематической классификации изображений.

2. Постановка задачи факторного анализа, интерпретация решения задачи методом главных компонент

2)Факторный анализ имеет своей основной целью снижение размерности множества данных

Общая постановка задачи. Пусть у нас есть n параметров (факторов), заданных векторами x1,x2,...,xn. Требуется выбрать m<nнаиболее значимых факторов f1,f2,...,fm.

Заметим, что здесь исходными параметрами являются вектор-столбцы стандартизованной (нормированной) матрицы данных, элементы которой представлены в виде

В задачах факторного анализа решение ищется из системы линейных уравнений вида

Коэффициенты akj называются факторными нагрузками, а свободный член xj - характерным фактором.

Уравнение (7.8) отличается от обычной линейной регрессии тем, что заранее неизвестны ни сами факторы fk, ни факторные нагрузки akj . Фактор xj играет роль шумовой компоненты, поэтому M(xj)=0, но дисперсия также заранее неизвестна.

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

, векторы называются вычисленными параметрами.

В модели главных компонент критерием близости является минимальная суммарная дисперсия характерных факторов (то есть, как и в НСКО-алгоритмах кластеризации, минимизируется сумма квадратов ошибок).

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

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

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 8

ЭКЗАМЕНАЦИОННЫй БИЛЕТ № 8

1.Основные типы задач кластерного анализа. Методы «выращивания» кластеров.

2. Обучение нейросетей методом обратного распространения ошибок.

1)Кластером обычно называют группу образов {xi}, удовлетворяющих условию: ||xi-xk||<d

где ||.|| - мера сходства между образами, d - заданное пороговое ограничение по этой мере.

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

Методы кластерного анализа в пакетах обработки данных ДЗ называют неконтролируемой классификацией.

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

Наиболее раcпространенные методы кластерного анализа можно условно разделить на две группы. 1. Методы выявления (выращивания) кластеров при заданном пороговом ограничении на расстояние между точками множества. 2. Методы формирования кластеров при заданном количестве групп.

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

Односвязывающий метод. Простейшим способом выявления кластеров является такой: выбираем произвольную точку (вектор) множества Х, назначаем ее центром первого кластера (xk, k=1) и присоединяем к этому кластеру все точки, удовлетворяющие условию ||xi-xk||<d Первая точка, для которой условие ||xi-xk||<d не выполняется, назначается центром следующего кластера. Далее для каждой точки вычисляется расстояние уже до двух центров, и она относится к тому кластеру, расстояние до которого меньше. Если расстояние до существующих кластеров больше заданного порога, образуется новый кластер и т.д. В конечном итоге мы получим некоторое разбиение на классы, вид которого, как уже говорилось, очень сильно зависит от порядка просмотра образов, особенно в тех случаях, когда тенденция к образованию групп прослеживается слабо

Полносвязывающий метод.. В качестве исходного образа выберем некоторую “крайнюю” точку, например, с минимальными координатами в пространстве Х. Назовем ее центром m1 кластера К1. В качестве второго центра К2 выберем наиболее удаленную от нее точку по всему множеству образов. Определим пороговое значение d как d=||m1-m2||/2

Шаг 1. Вычисляем расстояния до центров m1 и m2 ||x-m1||, ||x- m2|| для всех x нашего множества образов. Из каждой пары расстояний выбираем минимальное .

Шаг 2. Определяем максимальное значение M=max{min(||x-m1||,||x- m2|| )} по всему множеству образов. Пусть этому значению соответствует образ xi . Если M>d, назначаем xi центром кластера К3. В качестве новой пороговой меры d можно взять величину d=M/2 или половину среднего значения по всем минимальным расстояниям, рассчитанным на предыдущем шаге.

Шаг 3. Для всех x вычисляем минимальное из K расстояний до центров уже образованных кластеров: min||x-mk||, k=1,...,K.

Шаг 4. Вычисляем среднее минимальное расстояние образа x до центра кластера rср.(x,mk)=|| x-mk||/N, где N - общее количество пар (x,mk). Назначаем новый порог d=rср.(x,mk). Шаг 5. Ищем xi , соответствующий значению М из M=max{min(||x-m1||,||x- m2|| )} по всему множеству образов. Если М<=d, процесс заканчивается. В противном случае назначаем xi очередным центром кластера и переходим к шагу 3.

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

2) Что же представляет собой современная нейросеть? В наиболее общем виде это система, включающая в себя следующие компоненты . · Множество простых процессоров (сенсоров). · Структуру связей. · Правило распространения сигналов. · Правило комбинирования входных сигналов. · Правило вычисления сигнала активности. · Правило обучения, корректирующее связи.

Наиболее успешная сфера применения нейросетей – диагностика сложных технических систем

Правило обучения, корректирующее связи, – одно из главных достоинств нейронной сети, так как оно обеспечивает ее автоматическую настройку на принятие решения. Целью обучения является изменение весовых характеристик таким образом, чтобы добиться требуемого поведения сети.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 9

Билет №9