[БЕЗ_ЗВУКА] Давайте
обсудим еще одну важную проблему,
которая появляется при построении решающих деревьев.
Решающие деревья очень хорошо и эффективно обходят проблему пропусков в данных.
Я об этой проблеме упоминал, когда говорил о медицинских задачах, где признаковое
описание одного пациента, как правило, содержит лишь небольшую часть измерений.
Вот в таких задача проблема пропусков возникает крайне часто.
Что произойдет, если мы хотим классифицировать объект и используем для
этого решающее дерево, и оказались во внутренней вершине, и нам эта вершина
задает некие вопросы об этом объекте, а мы просто не знаем ответ на этот вопрос?
Врач спрашивает пациента, а пациент говорит: «Я не знаю».
Вот что делать в этом случае?
Мы должны предпринять некие меры как на стадии обучения,
так и на стадии классификации.
Вот на стадии обучения все достаточно просто.
Если вдруг оказывается, что некие объекты обучающей выборки не
подходят для вычисления предиката β,
то он просто исключается из выборки, он просто не учитывается,
и критерий информативности вычисляется без этого объекта.
Но этим дело не заканчивается, и мы должны иметь некую
дополнительную информацию в каждой внутренней вершине о том,
насколько часто объекты в этой внутренней вершине классифицируются и
уходят в левое дочернее поддерево и в правое дочернее поддерево.
Значит, давайте вычислим просто частоту — оценка вероятности левой ветви и,
соответственно, оценка вероятности правой ветви.
И таким образом, мы можем определить функцию,
которая имеет интерпретацию условной вероятности для листовых вершин.
Это условная вероятность класса y для данного объекта x,
который дошел до листовой вершины v.
Но это просто доля объектов обучающей выборки,
которые дошли до этой вершины и принадлежат данному классу y.
То есть это такое простое естественное определение,
частотная оценка условной вероятности.
Вот эти дополнительные величины qv и вот эта вот оценка условной
вероятности класса, мы их должны посчитать для каждой,
соответственно, внутренней вершины, листовой вершины на этапе обучения.
Теперь этап классификации.
Итак, у нас есть объект x, который мы хотим классифицировать,
мы его начинаем пропускать через наше решающее дерево, сверху вниз, от корня,
и вдруг он наталкивается на вершину, в которой предикат не может быть вычислен.
Например, он спрашивает значение некоторого признака,
а этот признак на данном объекте x мы просто не знаем.
Что делать?
Простое решение — это пропустить этот объект дальше в левое
дочернее и в правое дочернее.
И вот для этого нам и нужны те самые оценки условной вероятности,
что объект, дойдя до внутренней вершины v,
пойдет дальше либо в левую дочернюю, либо в правую дочернюю.
Мы эти оценки посчитали.
Это вот та самая величина qv.
Поэтому мы можем определить значение условной вероятности
класса для данного объекта x в данной вершине через
условные вероятности этого класса для этого объекта в левой дочерней
и в правой дочерней, зная, с какой вероятностью он в эти вершины попадет.
Ну теперь, другой случай, более простой.
Если все-таки значение предиката мы можем вычислить в вершине x,
то тогда мы его вычисляем, объект однозначно идет либо налево, либо направо.
Ну в этом случае мы тоже можем посчитать оценки условных вероятностей классов,
просто взяв их непосредственно либо из левой дочерней, либо из правой дочерней.
Ну и так, повторяя вот это рекурсивное вычисление оценок
условной вероятности классов для данного объекта x,
которые мы хотим классифицировать в каждой вершине дерева,
мы в итоге сможем посчитать эти самые условные вероятности для корневой вершины.
И если мы имеем условные вероятности классов для данного
объекта x в корневой вершине, мы просто, что логично,
отнесем объект x к тому классу, для которого эта вероятность максимальна.
Это принцип максимума апостериорной вероятности.
Вот так вот можно обобщить конструкцию решающего дерева на тот случай,
когда в данных есть пропуски.
Давайте резюмируем достоинства и недостатки метода ID3.
Ну, во-первых, он строит решающие деревья,
которые являются простым и интерпретируемым алгоритмом классификации.
Это очень гибкий метод, мы можем по-разному задавать множество
предикатов B, из которого мы выбираем предикаты во внутренних вершинах.
Вплоть до того, что это могут быть какие-то другие модели классификации,
главное, чтобы они возвращали ответ «да» или «нет».
Мы можем приспособить этот алгоритм для работы с данными с пропусками.
И этот алгоритм очень эффективен вычислительно, его трудоемкость линейна,
как по числу объектов обучения, так и по числу признаков.
Важно, что у него не бывает отказов от классификации, любой объект так
или иначе дойдет до какой-то терминальной вершины и будет классифицирован.
Недостатки вытекают из того, что это жадная стратегия,
и решение о ветвлении, которые принимаются в каждой внутренней вершине
дерева оно локально оптимально, но оно не оптимально глобально.
Мы всегда могли бы полным перебором найти гораздо более компактное дерево решающее,
которое решает данную задачу, может быть даже и с меньшим числом ошибок.
Но поскольку принимая решение о ветвлении во внутренние вершины,
мы не можем заглянуть далее и понять, насколько хорошо будет
идти процесс ветвления дальше, тут происходит серия неоптимальных
решений о постановке предикатов во внутренних вершинах.
А когда мы доходим до вершин, близких к терминальным,
мы вообще имеем дело с высокой фрагментацией выборки.
Туда доходит небольшое число объектов, и решение о том,
какой предикат поместить во внутреннюю вершину или к какому классу отнести объект
в терминальной вершине, эти решения становятся статистически ненадежными.
Они принимаются по выборкам малого объема.
Ну и наконец, данная процедура очень
чувствительна и к составу выборки, и к шумовым признакам.
Можно показать, что, например, изъятие одного объекта из обучающей
выборки часто приводит к тому, что дерево строится совсем другое.
В какой-то вершине произошел выбор другого предиката,
и дальше все поддерево уже будет строиться совсем по-другому.
То есть вот эти недостатки они вытекают из того,
что процедура жадная.
[БЕЗ_ЗВУКА] [БЕЗ_ЗВУКА]