Диссертация (1090370), страница 10

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

Текст из файла (страница 10)

Для выбора оптимального правила используется функция оценки качества разбиения.Обучение дерева решений относится к классу обучения с учителем, тоесть обучающая и тестовая выборки содержат классифицированный наборпримеров. Оценочная функция, используемая алгоритмом CART, базируетсяна интуитивной идее уменьшения «нечистоты» (неопределённости) в узле.Поясним это на примере с двумя классами и узлом, имеющим по 50примеров каждого класса. Узел имеет максимальную «нечистоту». Если будет найдено разбиение, которое разбивает данные на две подгруппы - 40:5примеров в одной и 10:45 в другой, то интуитивно «нечистота» уменьшится.Она полностью исчезнет, когда будет найдено разбиение, которое создастподгруппы 50:0 и 0:50.В алгоритме CART идея «нечистоты» формализуется индексом Gini.Для набора данных Т, содержащих информацию о n классах, индекс Giniопределяется формулой [17]Gini (T )  1 n pi2 ,i 1где pi - вероятность принадлежности данных i-му классу в наборе T.73Если набор Т разбивается на две части T1 и T 2 с числом примеров вкаждом N 1 и N 2 соответственно, то показатель качества разбиения (Split)будет равенGiniS (T ) N1NGini (T1 )  2 Gini (T2 ) .NNНаилучшим считается разбиение, для которого индекс Gini минимален:GiniS (T )  min .(3.1)Обозначим через N число примеров в узле-предке, через L и R - числопримеров в левом и правом потомке соответственно, li и ri - число экземпляров i-го класса в левом/правом потомке.

Тогда качество разбиения оценивается по следующей формуле:GiniS (T ) LNnnR221(l/L)][1(r/R)iiNi 1 i 11 n 21 n 21   1 n 21 n 2  ri LlRL1lR1rii 2  i L R N   L2 i 1i 1i 1 R i 1  1 n1 n  N     li 2    ri 2  .R i1  L i 1Следовательно, критерий (3.1) можно заменить следующим:1 n 2 1 n 2GS   li    ri  max .L i1R i1~Вектор предикторных переменных, подаваемый на вход дерева можетсодержать как числовые (порядковые) так и категориальные переменные.

Влюбом случае разбиение в каждом узле проводится только по одной переменной.Если предикторная переменная x числового типа, то в узле формируется правило видаx c,74где с - некоторый порог, который чаще всего выбирается как среднее арифметическое двух соседних упорядоченных значений переменной x в обучающей выборке.Если переменная x - категориального типа, то в узле формируется правилоxD,где D - некоторое непустое подмножество множества значений переменнойx в обучающей выборке.Следовательно, для n значений числового атрибута алгоритм сравнивает n  1 разбиений, а для категориального 2n1  1 . На каждом шаге построения дерева алгоритм последовательно сравнивает все возможные разбиениядля всех атрибутов и выбирает наилучший атрибут и наилучшее разбиениедля него.Механизм отсечения дерева (оригинальное название minimal costcomplexity tree pruning) является наиболее серьезным отличием алгоритмаCART от других алгоритмов построения ДР. CART рассматривает отсечениекак получение компромисса между двумя проблемами: получение дерева оптимального размера и получение точной оценки вероятности ошибочнойклассификации.Основная проблема отсечения - большое количество всех возможныхотсеченных поддеревьев для одного дерева.

Базовая идея метода - не рассматривать все возможные поддеревья, ограничившись только «лучшимипредставителями» согласно приведённой ниже оценке.Введем обозначения: |T | - число листьев (терминальных узлов) дерева,R(T ) - ошибка классификации дерева, равная отношению числа неправильно классифицированных примеров к числу примеров в обучающей выборке.Определим оценку (показатель) затраты–сложность дерева какC ( T )  R(T )   |T | ,75где   0 - некоторый параметр. Таким образом, полная стоимость дерева состоит из двух компонент - ошибки классификации дерева и штрафа за егосложность. Если ошибка классификации дерева неизменна, тогда с увеличением  полная стоимость дерева будет увеличиваться. В зависимости от менее ветвистое дерево дающее большую ошибку классификации, но можетстоить меньше, чем дерево, дающее меньшую ошибку, но более ветвистое.Определим T - максимальное по размеру дерево, которое предстоитобрезать.

При заданном  существует наименьшее минимизируемое поддерево T () , удовлетворяющее следующим условиям:C ( T ())  min{C ( T ) | T  T } ;C  ( T (  ))  C  ( T )  T (  )  T .Первое условие означает, что не существует такого поддерева дереваT , которое имело бы меньшую стоимость, чем T () при этом значении  .Второе условие означает, что если существует более одного поддерева, имеющего данную полную стоимость, тогда мы выбираем наименьшее дерево.Можно показать, что для любого значения  существует такоенаименьшее поддерево. Хотя имеется бесконечное число значений  , существует конечное число поддеревьев дерева T .

Можно построить последовательность уменьшающихся поддеревьев:T1  T2  ...  { t } ,(3.2)где t - корневой узел дерева, Tk - наименьшее минимизируемое поддереводля [  k ,  k 1 ) .Это важный результат, так как он означает, что мы можем получитьследующее дерево в последовательности, применив отсечение к текущемудереву. Это позволяет разработать эффективный алгоритм поиска наименьшего минимизируемого поддерева при различных значениях  . Первое де-76рево в этой последовательности - наименьшее поддерево дерева T , имеющеетакую же ошибку классификации, как и T , т.е.T1  T (  0) .Пояснение.

В случае, когда разбиение выполняется до тех пор, пока вкаждом узле останется только один класс, имеем: T1  T . Однако часто применяются методы ранней остановки (prepruning) и тогда может существоватьподдерево дерева T , имеющее такую же ошибку классификации.Каким образом мы получаем следующее дерево в последовательности(3.2) и соответствующее значение  ?Обозначим через Tt ветвь дерева Т с корневым узлом t.

При каких значениях  дерево T \ Tt будет лучше, чем Т? Если мы отсечём дерево Т в узлеt, тогда вклад данного узла в полную стоимость дерева T \ Tt станет равнымC ( { t })  R(t )   ,гдеR(t )  r(t )  p(t ) ,r(t ) - это ошибка классификации узла t, а p(t ) - пропорция случаев, которые«прошли» через узел t. Альтернативный вариант:R( t )  m / n ,где m - число примеров классифицированных некорректно, а n - общее числоклассифицируемых примеров для всего дерева.Вклад Tt в полную стоимость дерева Т составитC ( Tt )  R(Tt )   |Tt | ,гдеR(Tt )  R(t) .t  TtДерево T \ Tt будет лучше, чем T, когда77C ({t})  C (Tt ) ,(3.3)потому что при этой величине  они имеют одинаковую стоимость, но T \ Tt- наименьшее из двух.

В случае (3.3) получаем:R (t )    R (Tt )   |Tt | .Отсюда следуетR(t )  R(Tt ).|Tt |  1Если для любого узла t в дереве T1 выполняется это неравенство:R(t )  R(T1,t )|T1,t |  1,дерево, полученное отсечением в узле t, будет лучше, чем T1 .Основная идея, лежащая в основе построения последовательности поддеревьев (3.2), состоит в следующем: вычислим величинуg (t ) R ( t )  R (T1,t )|T1,t |  1для каждого узла в дереве T1 и затем выберем «слабые связи» (их может бытьбольше чем одна), т.е. узлы для которых эта величина является наименьшей.Мы отсекаем T1 в этих узлах, чтобы получить T2 - следующее дерево в последовательности (3.2).

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

Организация вычислительных экспериментовВ качестве инструментария построения и применения ДР выбран ПППStatistic Toolbox системы MATLAB. Алгоритм CART реализует библиотечная функция classificationtree(). Для идентификации ДП используется библиотечная функция predict().Алгоритм построения деревьев классификации ЛА поясняет рис.

3.4.πРис. 3.4. Принцип построения дерева классификации ЛАОбучающая и тестирующая выборки генерируются посредством программы BSS. Ширина строба дальности: L  200 м .Далее рассматривается задача построения секторного классификаторадля диапазона КУ 1   11 .Обучающая выборка охватывает весь этот диапазон с шагом измененияКУ   0,05 . Таким образом, для ее построения используется 2000 ДП, причем для каждого типа ЛА - 200 ДП. Тестирующая выборка охватывает диапазон КУ 4,525    7 с шагом   0,025 . Таким образом, для ее построенияиспользуется 1000 ДП, причем 100 ДП - для каждого типа ЛА.На рис.

3.5 представлен ДП бомбардировщика B-52 для КУ   5 , а нарис. 3.6 - семейство ДП в обучающей выборке.792.521.510.50020406080100120140160180200Рис. 3.5. ДП самолета B-52 при   5Рис. 3.6. Семейство ДП B-52 для условий наблюдения 1    11Далее при анализе схем распознавания ВЦ на основе ДР ограничимсярассмотрением спектральных информативных признаков ВЦ (см.

§2.2, формулы (2.8) и (2.9)). Используемый кортеж спектральных признаков:( x1 , x 2 ,..., x n )  ( a0 , a1 ,..., aK , b1 , b2 ,..., bK ) .Здесь n  2K  1. Далее полагаем K  9 .803.5. Статическая схема распознавания ВЦПредлагаемую схему распознавания ВЦ представляет рис. 3.7.πРис. 3.7.

Статическая схема распознавания ВЦ на основе ДРСтруктуру построенного ДР отражает рис. 3.8, а его параметры приведены в табл. 3.3. В каждом узлом реализуется критерий сортировки видаx c ,где x - атрибут (один из информативных признаков), а с - его пороговое значение.Рис. 3.8. Структура дерева решений81Таблица 3.3Параметры ДР, классифицирующего ЛАузелатрибутпорогузелатрибутпорог12345678910111213141516x8x11x1x11x1x14x13x3x19x10x8x19x15x15x1x111,54,0527,752,85370,6–11,3514,7527,359,8510,25–13,0515,451,8–8,845,155,05171819202122232425262728293031x10x2x12x4x2x19x11x1x11x1x3x19x12x3x13–6,9524,6–11,15–25,25–30,5136,3547,63,7550,525,515–9,2524,812,35Итоговые результаты апробации алгоритма распознавании:обучающая выборка - 2000 паттернов; из нихo правильно классифицированы - 1987 паттернов;o ошибочно классифицированы - 13 паттернов;тестирующая выборка - 1000 паттернов; из нихo правильно классифицированы - 976 паттернов;o ошибочно классифицированы - 24 паттернов.3.6.

Характеристики

Список файлов диссертации