Выбор проверок атрибутов

Подход к выбору атрибутов, используемый в обучении дерева решений, предназначен для минимизации глубины окончательно сформированного дерева. Идея этого подхода состоит в том, что следует выбирать в первую очередь такой атрибут, который позволяет сразу же выполнить максимально возможный объем работы по обеспечению правильной классификации примеров. Идеальный атрибут позволяет разделить множество примеров на подмножества, целиком состоящие из положительных или отрицательных примеров. Атрибут Patrons не идеален, но является достаточно приемлемым. С другой стороны, действительно бесполезный атрибут, такой как Туре, создает подмножества примеров приблизительно с такими же соотношениями положительных и отрицательных примеров, как и в первоначальном множестве.
Таким образом, нам достаточно лишь определить формальный критерий оценки понятий "достаточно приемлемый" и "действительно бесполезный", после чего появится возможность реализовать функцию Choose-Attribute, применяемую в алгоритме, который приведен в листинге 18.1. Этот критерий должен принимать максимальное значение, когда атрибут является идеальным, и минимальное значение, когда атрибут полностью бесполезен. Одним из подходящих критериев является ожидаемый объем информации, предоставляемый атрибутом; в данном определении термин "информация" используется в математическом смысле, впервые определенном Шенноном и Уивером [1394]. Чтобы понять суть концепции информации, достаточно представить себе, что она является ответом на вопрос, например, о том, упадет ли подброшенная монета орлом вверх. Объем информации, содержащийся в ответе на этот вопрос, зависит от наших априорных знаний. Чем меньше мы знаем, тем больше получим информации. В теории информации информационное содержание ответа измеряется в битах. Один бит информации является достаточным для ответа "да" или "нет" на вопрос о том, что полностью неизвестно, например, каков результат подбрасывания подлинной монеты. Вообще говоря, если возможные ответы vL имеют вероятности P(Vi), то информационное содержание J фактического ответа определяется с помощью следующего уравнения:
Для проверки этого уравнения рассмотрим случай с подбрасыванием подлинной монеты. При этом будет получено следующее:
А если центр тяжести монеты смещен таким образом, что в 99% выпадает орел, то будет получено 1(1/100,99/100) = 0.08 битов, а поскольку вероятность выпадения орла приближается к 1, информационное содержание фактического ответа приближается к 0.
Что касается обучения деревьев решений, то необходимо найти ответ на вопрос — какова правильная классификация для данного примера? Правильное дерево решений должно позволить найти ответ на этот вопрос. Оценка вероятностей возможных ответов, полученная перед тем, как будет выполнена проверка какого-либо из этих атрибутов, определяется соотношениями положительных и отрицательных примеров в обучающем множестве. Предположим, что обучающее множество включает р положительных примеров и п отрицательных. В таком случае оценка информации, содержащейся в правильном ответе, равна:
Обучающее множество для задачи с рестораном, приведенное в табл. 18.1, включает количество примеров р=п=б, поэтому требуется 1 бит информации.
Теперь отметим, что обычно проверка по одному атрибуту А не позволит нам получать такой объем информации, но по меньшей мере предоставит часть этой информации. Мы можем точно измерить, какова эта часть, определяя, сколько еще информации нам потребуется после проверки этого атрибута. Любой атрибут А делит обучающее множество Е на подмножества Е1г..., Ev в соответствии со значениями атрибута А, если А может иметь v различных значений. Каждое подмножество Ei включает р± положительных примеров и п± отрицательных примеров, поэтому после перехода по ветви этого атрибута нам потребуется дополнительно -ПРлУ (Pi+rii) ,nj (Pi+rii) ) битов информации, чтобы ответить на вопрос. Случайно выбранный пример из обучающего множества содержит i-e значение рассматриваемого атрибута с вероятностью {р±+п±) / (р+п), поэтому в среднем после проверки атрибута А для классификации данного примера потребуется показанное ниже количество бит информации.
Приращение информации, полученное в результате проверки атрибута, представляет собой разность между первоначальной потребностью в информации и новой потребностью:
Эвристика, используемая в функции Choose-Attribute, состоит в том, что следует выбирать атрибут с наибольшим приращением. Возвращаясь к атрибутам, показанным на рис. 18.3, получаем следующее:
Эти соотношения подтверждают интуитивное предположение о том, что Patrons — наилучший атрибут, по которому следует выполнять разбиение. В действительности атрибут Patrons позволяет получить наибольшее приращение информации по сравнению с любыми другими атрибутами и должен быть выбран алгоритмом обучения дерева решений в качестве корневого.







Материалы

Яндекс.Метрика