Размещено на http://www.allbest.ru/

Введение

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

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

Объектом исследования является сфера классификации объектов. Предметом исследования являются алгоритмы, реализующие классификацию объектов на изображениях.

Задачи, которые необходимо решить в данной исследовательской работе:

· Изучить и промоделировать метод классификации объектов на изображении «случайный лес»;

· Изучить и промоделировать метод классификации объектов на изображении «CART»;

· Изучить и промоделировать метод классификации объектов на изображении «SVM»;

· Изучить и промоделировать метод опорных векторов;

· Провести сранительный анализ полученных результатов.

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

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

Во втором разделе подробно рассмотрен метод классификации объектов с помощью «деревьев решений».

В третьем разделе рассмотрена программная реализация средствами среды Matlab метода классификации объектов «случайный лес».

В четвертом разделе рассмотрена программная реализация средствами среды Matlab метода классификации объектов «CART».

В пятом разделе рассмотрена программная реализация средствами среды Matlab метода классификации объектов «SVM» (метод опорных векторов).

Заключение содержит обобщённые результаты дипломной работы, выводы по работе и рекомендации по использованию её результатов.



1. Классификация методов распознавания

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

1.1 Процедура предъявления обучающих выборок

· Фиксированная выборка - построение правил классификации по единственному обучающему множеству, предъявляемому до начала классификации;

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

Фиксированная выборка

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

Последовательная выборка

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

Свойства процедуры последовательного обучения [1]:

· сходимость - процесс изменения правил классификации должен приводить через конечное число корректировок к окончательному варианту;

· оптимальность - решающее правило, к которому сходится процесс обучения, должно быть оптимальным в смысле минимизации функции стоимости возможных ошибок;

· вычислительная сложность - финальное правило классификации должно минимизировать число шагов, необходимых для распознавания образа, время их выполнения.

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

1.2 Вид правил классификации

· параллельные - проведение ряда тестов над всей совокупностью выявленных данных об объекте и принятие решения на основе их результатов;

· последовательные - проведение последовательности тестов над подмножествами выявленных данных; выбор очередного теста определяется результатами предыдущих тестов.

Параллельная классификация

Систему с параллельным способом обработки входного образа можно проиллюстрировать следующим образом:



Рис.1.1 - Система с параллельным способом обработки входного образа

Для выполнения распознавания система производит ряд тестов над всеми компонентами описания входного объекта одновременно [1]. Решающая функция в этом случае представляется функцией не более, чем N переменных .

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

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

Последовательная классификация

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

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

В целом последовательная процедура позволяет реализовать более сложные правила классификации.

Возможно комбинирование этих двух принципов с целью достижения компромисса между простотой параллельных процедур и возможностями последовательных.

Рис.1.2 - Система с последовательным способом обработки входного образа

1.3 Способ описания объектов

· евклидово пространство - объекты представляются точками в евклидовом пространстве их вычисленных параметров, представление в виде набора измерений;

· списки признаков - выявление качественных характеристик объекта и построение характеризующего вектора;

· структурное описание - выявление структурных элементов объекта и определение их взаимосвязи.

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

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

Как правило, методы, работающие с Евклидовым пространством, используют параллельную процедуру подачи входного изображения. Распознавание основывается на проведении ряда математических вычислений над полным множеством точек изображения. Можно выделить следующие основные используемые виды правил классификации [2]:

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

Рис.1.3 - Решающие функции

· функции расстояния. Определение принадлежности объектов различным классам производится на основе анализа расстояний между точками объектов одного класса и между точками объектов различных классов. Классы представляются в виде кластеров в параметрическом пространстве. Построение правил классификации заключается в поиске функций, обеспечивающих оптимальное построение кластеров объектов. Данный подход активно использует методы кластерного анализа;

Рис.1.4 - Функции расстояния

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

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

Списки признаков

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

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

Методы данного класса являются в большой степени эвристическими. Их эффективность определяется правильностью выбора набора рассматриваемых признаков.

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

Рис.1.5 - Распознавание рукописных шифров

Структурное описание

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

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

Одним из видов структурных методов являются методы грамматической классификации образов. Они используют представление образов в виде предложений специального языка. На этапе инициализации алгоритма требуется определить виды возможных структурных элементов изображений. Построение правила классификации сводится к выводу грамматики, описывающей язык классифицируемых образов. Распознавание заключается в определении выводимости рассматриваемого предложения с помощью найденной грамматики. Примерами грамматического описания изображений служат: язык описания изображений PDL (Picture Definition Language, Язык Описания Изображений), плекс-грамматики, веб-грамматики, синтаксическое описание рукописных символов. Грамматики Эванса используют в качестве терминальных символов простые элементы изображений, такие как круг, прямоугольник, линия. В качестве терминалов, описывающих взаимоотношения элементов, используются специальные операторы, такие как ``над'', ``внутри'' и т.д [2,3].

В работе Идена приводится модель английской скорописи. В результате анализа английских скорописных текстов был выявлен ограниченный набор типов линий, с помощью комбинации которых можно изобразить любую скорописную букву. Подход нашел своё применение в системах распознавания Parascript FormXtra.

Рис.1.6 - Структурное описание изображения со смайликом

Рис.1.7 - Структурное описание модели английской скорописи

В качестве структурных элементов изображений могут использоваться траектории движения пишущего или рисующего инструмента. В таком случае эти элементы могут характеризоваться последовательностью направлений шагов перемещения пера. Направления могут кодироваться кодами из конечного набора наперёд заданных направлений, распределённых на диапазоне 0° - 360°. Другим способом является описание элементов с помощью кривых Безье.

1.4 Классификация объектов на основе нечеткого логического вывода

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

а) б)

Рис.1.8 - Объекты с непрерывным (а) и дискретным (б) выходами

Пакет Fuzzy Logic Toolbox системы MATLAB обеспечивает проектирование систем нечеткого логического вывода только для объектов с непрерывным выходом. В данной исследовательской работе показано, как расширить Fuzzy Logic Toolbox, чтобы выполнять нечеткий логический вывод для объектов с дискретным выходом. В качестве нечеткого классификатора будем использовать систему нечеткого логического вывода типа Сугено. Классам решений поставим в соответствие термы выходной переменной; наименование класса решений зададим как элемент терммножества выходной переменной. Параметры заключений правил (параметры «функций принадлежности» выходной переменной) могут быть произвольными, т. к. они не влияют на результат классификации.

Для выполнения нечеткой классификации была разработана функция fuz_classifer:

function decision=fuz_classifer(x, fis, type)

% НЕЧЕТКИЙ ЛОГИЧЕСКИЙ ВЫВОД ДЛЯ ОБЪЕКТОВ

% С ДИСКРЕТНЫМ ВЫХОДОМ

[a,b,c,d]=evalfis(x,fis);

% нечеткий вывод

% Поиск правил с максимальной степенью

% выполнения:

rule_num_max_fulfilment=find(d==max(d));

% Определение количества таких правил:

number_rules=... length(rule_num_max_fulfilment);

% Если таких правил несколько, то выбираем

% решение, имеющее наибольшее количество правил

% с максимальной степенью выполнения:

counter( 1:length(fis.output(1).mf) )=0;

for i=1:number_rules

index=... fis.rule(rule_num_max_fulfilment(i)).consequent;

counter(index)=counter(index)+1;

end

[tmp1 tmp2]=max(counter);

number_of_the_class=tmp2(1);

% Возращение результата классификации

% в требуемом формате:

switch type

case `number', decision=number_of_the_class;

case `name', decision=...

fis.output.mf(number_of_the_class).name;

otherwise, error(`Недопустимое значение... третьего аргумента'

end

Функция fuz_classifer вызывается в таком формате:

decision = fuz_classifer(x, fis, type),

где x -- вектор информативных признаков объекта классификации;

fis -- система нечеткого логического вывода;

type -- тип возвращаемого функцией результата: «number» -- порядковый номер класса; «name» -- наименование класса;

decision -- результат классификации для объекта x.

Функция fuz_classifer использует функцию evalfis для получения промежуточных результатов нечеткого логического вывода. Затем находятся правила с максимальной степенью выполнения. Если таких правил несколько, то подсчитывается их количество для каждого класса решений. После этого выбирается решение, имеющее наибольшее количество правил с максимальной степенью выполнения.

В качестве примера спроектируем систему нечеткого логического вывода для задачи классификации ирисов, предложенную Фишером в 1936 году. Задача состоит в отнесении ириса к одному из трех классов:

1. Iris Setosa,

2. Iris Versicolor,

3. Iris Virginica.

При классификации используются следующие признаки цветков: 1 x -- длина чашелистика; 2 x -- ширина чашелистика; 3 x -- длина лепестка; 4 x -- ширина лепестка [3]. Исходные данные для классификации ирисов записаны в файле iris.dat, входящем в Fuzzy Logic Toolbox. Файл содержит 150 строк, каждая из которых описывает один ирис. Информация о цветке представлена пятеркой чисел -- первые четыре числа соответствуют значениям признаков, а пятое -- классу ириса. 2D-распределения ирисов приведены на рис.1.9.

Рис.1.9 - Распределение ирисов

В редакторе fuzzy создадим систему нечетко го логического вывода типа Сугено с четырьмя входными и одной выходной переменной. Диапазоны изменения входных переменных установим такими же, как и для исходных данных: ?[47, 79]; ?[20, 44]; ?[10, 69]; ?[1, 25]. Для лингвистической оценки признаков цветков будем использовать термы «низкий», «средний» и «высокий» с установленными по умолчанию треугольными функциями принадлежности. Взаимосвязь «входы-выход» опишем тремя нечеткими правилами:

если 4 x = ' ' низкий , то y = 'Iris Setosa';

если 3 x = ' ' средний и 4 x = ' ' средний , то y = 'Iris Versicolor';

если 3 x = ' ' высокий и 4 x = ' ' высокий , то y = 'Iris Virginica'.

Применяя функцию fuz_classifer, обнаруживаем, что созданная нечеткая модель правильно классифицирует 130 из 150 ирисов. Исследуем, как влияет весовой коэффициент второго правила на результаты классификации [3]:

fis=readfis(`sample_iris.fis');

%загрузка системы нечеткого вывода

iris=load(`iris.dat') number_of_errors=[];

for w2=0.05:0.05:1 fis.rule(2).weight=w2;

for i=1:150 out_fis(i)=fuz_classifer(iris(i, 1:4),... fis, `number');

end err=sum(iris(:,5)~=out_fis') number_of_errors=[number_of_errors err];

end

plot(0.05:0.05:1, number_of_errors, `oBBr') xlabel(`Весовой коэффициент второго правила') ylabel(`Количество ошибок')

Зависимость количества ошибок классификации от веса второго правила показана на рис.1.10. Минимальное количество ошибок достигается, когда весовой коэффициент второго правила принимает значение из диапазона [0.15, 0.2]. На рис.1.11 сравниваются результаты нечеткой классификации с экспериментальными данными. Нечеткая система с тремя правилами безошибочно классифицирует ирисы Iris Setosa и Iris Versicolor и допускает 8 ошибок для ирисов Iris Virginica.

Нечеткую систему классификации можно улучшить, настраивая веса правил и параметры функций принадлежностей.



Рис.1.10 - Влияние весового коэффициента правила на безошибочность классификации

Рис.1.11 - . Сравнение экспериментальных данных с результатами нечеткой классификации



2. Деревья решений

Деревья решений - один из методов автоматического анализа данных. Основополагающей работой по данной тематике является. Сначала необходимо уточнить основные понятия из теории деревьев решений, которые в дальнейшем будут употребляться (Таб.2.1). Деревья решений - это способ представления правил в иерархической, последовательной структуре, где каждому объекту соответствует единственный узел, дающий решение. Основные классы задач, решаемые с помощью деревьев решений [4]:

· Описание данных: Деревья решений позволяют хранить информацию о данных в компактной форме. Вместо данных может храниться дерево решений, которое содержит точное описание объектов.

· Классификация: отнесение объектов к одному из заранее известных классов. Целевая переменная должна иметь дискретные значения.

· Регрессия: Если целевая переменная имеет непрерывные значения, деревья решений позволяют установить зависимость целевой переменной от входных переменных.

Таблица 2.1 Терминология деревьев решений

Название	Описание
Объект	Пример, шаблон, наблюдение
Атрибут	Признак, независимая переменная, свойство
Метка класса	Зависимая переменная, целевая переменная
Узел	Внутренний узел дерева, узел проверки
Лист	Конечный узел дерева, узел решения
Проверка (test)	Условие в узле

2.1 Схематический алгоритм построения дерева

Пусть задано некоторое обучающее множество T, содержащее объекты (примеры), каждый из которых характеризуется m атрибутами, причем один из них указывает на принадлежность объекта к определенному классу.

Пусть через обозначены классы (значения метки класса), тогда существуют 3 ситуации [4,5]:

1) Множество T содержит один или более примеров, относящихся к одному классу . Тогда дерево решений для T -- это лист, определяющий класс ;

2) Множество T не содержит ни одного примера, т.е. пустое множество. Тогда это снова лист, и класс, ассоциированный с листом, выбирается из другого множества отличного от T, например, из множества, ассоциированного с родителем;

3) Множество T содержит примеры, относящиеся к разным классам. В этом случае следует разбить множество T на некоторые подмножества. Для этого выбирается один из призна- ков, имеющий два и более отличных друг от друга значений . T разбивается на подмножества T, где каждое подмножество содержит все примеры, имеющие значение для выбранного признака. Это процедура будет рекурсивно продолжаться до тех пор, пока конечное множество не будет состоять из примеров, относящихся к одному и тому же классу.

Вышеописанная процедура построения деревьев лежит в основе многих современных алгоритмов построения деревьев решений. Для построения дерева на каждом внутреннем узле необходимо найти такое условие (проверку), которое бы разбивало множество, ассоциированное с этим узлом, на подмножества. В качестве такой проверки должен быть выбран один из атрибутов. Общее правило для выбора атрибута можно сформулировать следующим образом: выбранный атрибут должен разбить множество так, чтобы получаемые в итоге подмножества состояли из объектов, принадлежащих к одному классу, или были максимально приближены к этому, т.е. количество объектов из других классов («примесей») в каждом из этих множеств было как можно меньше. В дополнение к основному методу построения деревьев решений предлагаются следующие правила [5]:

Использование статистических методов для оценки целесообразности дальнейшего разбиения, так называемая «ранняя остановка» (prepruning). В конечном счете «ранняя остановка» процесса построения привлекательна в плане экономии времени обучения, но здесь уместно сделать одно важное предостережение: этот подход строит менее точные класси- фикационные модели и поэтому ранняя остановка крайне нежелательна.

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

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

2.2 Отсечение ветвей

Алгоритмы построения деревьев решений могут давать сложные деревья, которые имеют много узлов и ветвей. Такие «ветвистые» деревья разбивают обучающее множество на все большее количество подмножеств, состоящих из все меньшего количества объектов, и поэтому сложны для восприятия. Ценность правила, справедливого, например, для 2-3 объектов, крайне низка, и в целях анализа данных такое правило практически непригодно [5,6]. Предпочтительнее иметь дерево, состоящее из малого количества узлов, которым бы соответствовало большое количество объектов из обучающей выборки. Возникает вопрос о построении всех возможных вариантов деревьев, соответствующих обучающему множеству, и выборе среди них дерева с наименьшей глубиной. Данная задача является NP-полной и не имеет эффективных методов решения.

Для решения вышеописанной проблемы часто применяется отсечение ветвей (pruning).

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

· Построить дерево;

· Отсечь или заменить поддеревом те ветви, которые не приведут к возрастанию ошибки.

В отличии от процесса построения, отсечение ветвей происходит снизу вверх, начиная с листьев дерева, отмечая узлы как листья, либо заменяя их поддеревом [6].

Преимущества деревьев решений:

· Быстрый процесс обучения;

· Генерация правил в трудноформализуемых областях знаний;

· Извлечение правил на естественном языке;

· Интуитивно понятная классификационная модель;

· Высокая точность прогноза



3. Алгоритм CART

Существует значительное число алгоритмов, реализующих деревья решений CART, C4.5, NewId, ITrule, CHAID, CN2 и т.д.

В данной работе рассматривается CART (Classification and Regression Tree) - это алгоритм построения бинарного дерева решений - дихотомической классификационной модели. Каждый узел дерева при разбиении имеет только двух потомков. Существует несколько модифицированных версий - алгоритмы IndCART и DB-CART. Алгоритм IndCART отличается от CART использованием иного способа обработки пропущенных значений. Он не осуществляет регрессионную часть алгоритма CART и имеет иные параметры отсечения. Алгоритм DB-CART базируется на следующей идее: вместо того чтобы использовать обучающий набор данных для определения разбиений, используем его для оценки распределения входных и выходных значе- ний и затем используем эту оценку, чтобы определить разбиения. DB, соответственно, означает - «distribution based». Утверждается, что эта идея дает значительное уменьшение ошибки клас- сификации по сравнению со стандартными методами построения дерева [7].

В алгоритме CART каждый узел дерева решений имеет двух потомков. На каждом шаге построения дерева правило, формируемое в узле, делит заданное множество примеров (обу- чающую выборку) на две части - часть, в которой выполняется правило (потомок - right) и часть, в которой правило не выполняется (потомок - left). Для выбора оптимального правила используется функция оценки качества разбиения.

Обучение дерева решений относится к классу обучения с учителем, то есть обучающая и тестовая выборки содержат классифицированный набор примеров. Оценочная функция, используемая алгоритмом CART, базируется на интуитивной идее уменьшения нечистоты (неопределённости) в узле. В алгоритме CART идея «нечистоты» формализована в индексе . Если набор данных T содержит данные n классов, тогда индекс Gini определяется как:

(3.1)

где T -- текущий узел;

-- вероятность класса i в узле T.

Если набор T разбивается на две части и с числом примеров в каждом и соответственно, тогда показатель качества разбиения будет равен:

(3.2)

Наилучшим считается то разбиение, для которого минимально. Обозначим N -- число примеров в узле - предке, L, R -- число примеров соответственно в левом и правом потомке, и -- число экземпляров i-го класса в левом/правом потомке. Тогда качество разбиения оценивается по следующей формуле [7]:

(3.3)

Данную задачу минимизации можно в итоге свести к задаче максимизации следующего выражения:

(3.4)



3.1 Правила разбиения и механизм отсечения дерева

Вектор предикторных переменных, подаваемый на вход дерева, может содержать как числовые (порядковые), так и категориальные переменные. В любом случае, в каждом узле разбиение идет только по одной переменной. Если переменная числового типа, то в узле формируется правило вида ? c, где c - некоторый порог, который чаще всего выбирается как среднее арифметическое двух соседних упорядоченных значений переменной обучающей выборки. Если переменная категориального типа, то в узле формируется правило , где - некоторое непустое подмножество множества значений переменной в обучающей выборке. Следовательно, для n значений числового атрибута алгоритм сравнивает n?1 разбиений, а для категориального - (). На каждом шаге построения дерева алгоритм последовательно сравнивает все возможные разбиения для всех атрибутов и выбирает наилучший атрибут и наилучшее разбиение для него.

Механизм отсечения дерева (Minimal cost-complexity tree pruning) -- наиболее серьезное отличие алгоритма CART от других алгоритмов построения дерева. CART рассматривает отсе- чение как получение компромисса между двумя проблемами: получение дерева оптимального размера и получение точной оценки вероятности ошибочной классификации.

Основная проблема отсечения - большое количество всех возможных отсеченных поддере- вьев для одного дерева. Более точно: если бинарное дерево имеет |T| листов, тогда существует ? [1.5028369 |T|] отсечённых поддеревьев. И если дерево имеет хотя бы 1000 листов, то число отсечённых поддеревьев становится просто огромным [7].

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

Самым очевидным простым способом является выбор финального дерева через тестирование на тестовой выборке. Дерево, давшее минимальную ошибку классификации, и будет лучшим. Однако, качество тестирования во многом зависит от объема тестовой выборки и «равномерности данных», которые попали в обучающую и тестовую выборки. В случае, когда набор данных для обучения мал или каждая запись в нем по-своему «уникальна» так, что невозможно выделить выборку для обучения и выборку для тестирования, используется метод перекрестной проверки (V-fold cross-validation).

Задача состоит в классификации объектов городского ландшафта по аэрофотоснимкам высокого разрешения, которые были переконвертированы в различные типы параметров с разным уровнем сегментации объектов. Для классификации были использованы деревья решений, основанные на алгоритме CART. Основным инструментом являлся R - язык программи- рования для статистической обработки данных и библиотека деревьев решений - «rpart». Полученные результаты сравнивались с данными, полученными с помощью MATLAB - языка программирования для решения задач технических вычислений и класса ClassificationTree.

Для каждого уровня сегментации объектов было построено дерево-решение. В таблице 3.1 приведена достигнутая точность классификации и параметры, используемые при построении деревьев решений для каждого из уровней сегментации.

Таблица 3.1 Результаты построения деревьев решений для разного уровня сегментации

Параметр масштаба (уровень сегментации)	Значимые параметры, R	Достигнутая точность классификации на тестовой выборке, R	Достигнутая точность классификации на тестовой выборке, Matlab (%)
20	Bright, Compact, NDVI, SD_G	68.27	72.19
40	BrdIndx, Bright, Mean_NIR, Mean_R, NDVI, SD_G	65.48	68.44
60	Area, Mean_NIR, Mean_R, NDVI, ShpIndx	65.88	70.61
80	BrdIndx, Bright, Mean_R, NDVI, SD_G	68.44	69.03
100	BordLngth, Bright, Compact, NDVI, SD_G	70.22	65.68
120	Bright, Dens, Mean_NIR, NDVI, SD_G, ShpIndx	61.93	58.78
140	Bright, Dens, Mean_NIR, NDVI, SD_G, ShpIndx	60.95	57.79
All scales	BrdIndx_80, Bright_80, Mean_R_40, NDVI, NDVI_40, Rect, SD_G	68.05	74.16

Полученные деревья решений изображены на рисунках 3.1 - 3.7. На узлах показаны усло- вия ветвления дерева по соответствующему параметру. На листьях расположен вектор классов в лексикографическом порядке: asphalt/building/car/concrete/grass/pool/shadow/soil/tree. Значением каждого элемента этого вектора является число экземпляров конкретного класса тренировочной выборки, попавших в данный лист.

Рис.3.1 - Дерево решений для значения параметра масштаба 20

Рис.3.2 - Дерево решений для значения параметра масштаба 40

Рис.3.3 - Дерево решений для значения параметра масштаба 60

Рис.3.4 - Дерево решений для значения параметра масштаба 80

Рис.3.5 - Дерево решений для значения параметра масштаба 100

Рис.3.6 - Дерево решений для значения параметра масштаба 120

Рис.3.7 - Дерево решений для значения параметра масштаба 140

Рис.3.8 - Дерево решений для всех значений параметра масштаба

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



4. Случайный лес

Метод основан на построении большого числа (ансамбля) деревьев решений (их число - параметр метода), каждое из которых строится по выборке, получаемой из исходной обучающей выборки с помощью bootstrap (выборки с возвращением). При построении каждого дерева на стадиях расщепления вершин используется только фиксированное число случайно отбираемых признаков обучающей выборки (ещё один параметр метода) и строится полное дерево без отсечений. Классификация осуществляется с помощью голосования классификаторов, определяемых отдельными деревьями [7,8]. Точность (вероятность корректной классификации) зависит от разнообразия классификаторов, составляющих ансамбль (от того, насколько коррелированы их решения). Чем более разнообразны классификаторы ансамбля (меньше коррелированность их решений), тем выше вероятность корректной классификации. В случайных лесах решения составляющих их деревьев слабо коррелированы вследствие двойной «случайности» в алгоритме построения случайного леса - на стадии выборки с возвращением и на стадии случайного отбора признаков, используемых при расщеплении вершин деревьев.

4.1 Ансамбли классификаторов

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

· Манипулирование примерами обучающей выборки;

· Манипулирование признаками;

· Включение случайности в индуктивный алгоритм;

· Манипулирование метками классов;

· Байесовское голосование.

Случайные леса синтезируют методы первых трех групп. Первая группа методов состоит либо в прогоне базового индуктивного алгоритма на различных подвыборках исходной обучающей выборки, либо в итеративном перевзвешивании наблюдений. Наиболее простой способ формирования подвыборок предложен Брейманом. Метод основан на формировании обуча- ющей выборки для каждого классификатора ансамбля с помощью bootstrap, то есть случайной выборки (того же объема, что и исходная обучающая выборка) с возвращением из исходной обучающей выборки и использовании метода голосования для агрегирования решений отдельных классификаторов. Метод получил название bagging или агрегированный bootstrap. Теоретический анализ показал, что данный метод приводит к сокращению средней квадратичной ошибки классификации [8]. Однако, это верно не для всех базовых моделей классификаторов. К методам этой группы относится также метод, основанный на формировании множества дизъюнктивных подвыборок обучающей выборки и использовании методики кроссвалидации для формирования ансамбля классификаторов.

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

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

Методы третьей группы основаны на том, что случайность вводится непосредственно в базовый алгоритм. Так, в работах Даетерича Т.Г. алгоритм построения деревьев решений, составляющих ансамбль, был рандомизирован следующим образом: на каждом шаге расщепления вычислялось 20 наилучших расщеплений и затем осуществлялся случайный выбор одного из них.

4.2 Схематический алгоритм построения случайного леса

Алгоритм индукции случайного леса может быть представлен в следующем виде:

1) Для i = 1, 2, ..., B (здесь B -- количество деревьев в ансамбле) выполнить:

* Сформировать bootstrap выборку S размера l по исходной обучающей выборке D = ;

* По bootstrap выборке S индуцировать неусеченное дерево решений с минимальным количеством наблюдений в терминальных вершинах, равным , рекурсивно следуя следующему подалгоритму:

- из исходного набора n признаков случайно выбрать p признаков;

- из p признаков выбрать признак, который обеспечивает наилучшее расщепление;

- расщепить выборку, соответствующую обрабатываемой вершине, на две подвыборки;

2) В результате выполнения шага 1 получаем ансамбль деревьев решений ;

3) Предсказание новых наблюдений осуществлять следующим образом [8]:

* для регрессии:

(4.1)

* для классификации: пусть - класс, предсказанный деревом решений , то есть (x) = ; тогда -- класс, наиболее часто встречающийся в множестве .

Преимущества случайных лесов

* Высокая точность классификации;

* Гарантирует защиту от переподгонки (ситуации, при которой классификатор хорошо классифицирует наблюдения обучающей выборки, но непригоден для классификации наблюдений, не входящей в неё) даже в случае, когда количество признаков значительно превышает количество наблюдений;

* Для построения случайного леса по обучающей выборке требуется задание всего двух параметров, которые требуют минимальной настройки;

* Метод Out-Of-Bag (OOB) обеспечивает получение естественной оценки вероятности ошибочной классификации случайных лесов на основе наблюдений, не входящих в обуча- ющие bootstrap выборки, используемые для построения деревьев;

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

4.3 Применение случайного леса к рассматриваемой задаче

Для классификации объектов городского ландшафта был использован алгоритм случайного леса. Инструментом также являлся язык программирования R и библиотека случайного леса «randomForest», являющаяся основным пакетом, реализующим классический алгоритм случайных лесов Бреймана. Результаты сравнивались с данными, полученными с помощью языка программирования MATLAB с использованием класса TreeBagger.

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

Для одного значения параметра сегментации в состав случайного леса вошло 500 деревьев, каждое из которых использовало по 4 параметра. В случае объединения всех уровней сегментации число параметров для построения каждого из 500 деревьев равно 12.

Таблица 4.1 Результаты построения случайного леса для разного уровня сегментации

Параметр масштаба (уровень сегментации)	OOB оценка вероятности ошибочной классификации, R	Достигнутая точность классификации на тестовой выборке, R (%)	Достигнутая точность классификации на тестовой выборке, Matlab (%)
20	17.26	77.32	81.07
40	20.24	79.88	80.08
60	19.64	77.91	77.12
80	18.45	74.75	75.15
100	21.43	72.78	74.16
120	25.6	70.61	69.43
140	23.21	68.24	67.06
All scales	16.07	80.87	81.07

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

Рис.4.1 - Ошибки леса для каждого типа объекта при параметре масштаба 20

Рис.4.2 - Ошибки леса для каждого типа объекта при параметре масштаба 40

Рис.4.3 - Ошибки леса для каждого типа объекта при параметре масштаба 60

Рис.4.4 - Ошибки леса для каждого типа объекта при параметре масштаба 80

Рис.4.5 - Ошибки леса для каждого типа объекта при параметре масштаба 100

Рис.4.6 - Ошибки леса для каждого типа объекта при параметре масштаба 120



Рис.4.7 - Ошибки леса для каждого типа объекта при параметре масштаба 140

Рис.4.8 - Ошибки леса для каждого типа объекта при всех значениях параметра масштаба

Также были получены различные значения точности классификации в зависимости от выбранных параметров метода. На Рис.4.9 представлена зависимость точности классификации от числа деревьев случайного леса B на выборке, включающей данные со всеми параметрами масштаба. Можно видеть, что, начиная примерно с B=100, точность классификации колеблется около одного значения. С увеличением числа деревьев амплитуда колебаний уменьшается, так как полученный результат всё меньше зависит от отдельных случайных деревьев, но увеличивается время вычислений. Установленное по умолчанию значение B=500 является хорошим компромиссом между ожидаемой точностью и временем работы метода.

Рис.4.9 - Зависимость точности классификации от числа деревьев случайного леса на выборке, включающей данные со всеми параметрами масштаба. График построен по 1000 точек.

Таким же образом ведет себя точность классификации на выборках, включающих только данные с определенными параметрами масштаба. Однако, на Рис.4.10 можно видеть, что значения, около которых она колеблется, неодинаковы для разных параметров масштаба. Наилучшая точность классификации достигается при использовании всех данных. Это обусловлено тем, что объекты определенных классов лучше распознаются на снимках с одними параметрами масштаба и хуже на снимках с другими. По данным рис. 4.11 и таб.4.2 можно сделать следующие выводы:

· значение параметра масштаба, равное 20, позволяет с достаточной точностью распознавать объекты наибольшего числа классов;

· при значениях параметра масштаба, равных 140 и 120, достаточно успешно определяются только объекты класса concrete (бетонные конструкции);

· объекты класса building (строения) плохо распознаются при любых параметрах масштаба (возможно, это связано с тем, что здания могут сильно отличаться друг от друга);

· объекты класса tree (деревья) достаточно хорошо распознаются только при значении параметра масштаба, равном 20.

Рис.4.10 - Зависимость точности классификации от числа деревьев случайного леса на выборках, включающих только данные с определенными параметрами масштаба. Каждый график построен по 100 точкам.

Таблица 4.2 Точности распознавания объектов определенных классов на данных с разными параметрами масштаба, превышающие 0,8.

Параметр масштаба	concrete	shadow	tree	asphalt	building	grass	pool	car	soil
20		v	v	v			v	v	v
40		v		v		v	v	v
60	v	v				v		v
80	v	v				v		v
100	v	v
120	v
140	v

Кроме этого была исследована зависимость точности классификации от параметра р - количества случайно выбираемых признаков, используемых для построения отдельных деревьев леса. На Рис.4.12 можно видеть, что, начиная с некоторого момента, точность классификации уменьшается с увеличением параметра р. Для большинства наборов данных удачным является значение p = 5.

Рис.4.11 - Средняя точность распознавания объектов каждого из классов случайным лесом из 500 деревьев для наборов данных с разными параметрами масштаба.

Рис.4.12 - Зависимость точности классификации от значения параметра p для наборов данных с различными параметрами масштаба.



5. Метод опорных векторов (SVM)

Рассматривается задача обучения по прецедентам , где X -- пространство объектов, Y -- множество ответов, : X > Y -- целевая зависимость, значения которой извест- ны только на объектах обучающей выборки . Строится алгоритм a:X>Y, аппроксимирующий целевую зависимость на всём пространстве X.

В базовом алгоритме рассматривается задача классификации на два непересекающихся класса, в которой объекты описываются n?мерными вещественными векторами: X=, Y={?1,+1}. Строится линейный пороговый классификатор [8,9]:

(5.1)

где x = () - признаковое описание объекта x;

вектор щ=( )? и скалярный порог ?R являются параметрами алгоритма.

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