[ЗАСТАВКА] Мы с вами разобрались в методе построения решающих деревьев, которые называются ID3 (индукция решающих деревьев). И поняли, что одна из проблем этого метода — это переусложнение структуры дерева. Давайте разберемся на примере из-за чего это происходит. Пример очень известный, это такая синтетическая задача классификаций, которая называется «задача исключающего ИЛИ», и это пример задачи, которая не решается, например, линейным классификатором. Эта выборка не может быть разделена прямой на два класса без ошибок. Но вот решающее дерево глубины 2 легко разделяет эту выборку, но, однако, нетривиально догадаться, особенно для жадного алгоритма, что на первом шаге деления надо просто произвольным образом провести прямую, например, там, либо вертикальную прямую посередине, либо горизонтальную прямую посередине, и вот тогда на втором шаге у нас выборка разделится без ошибок. Жадный алгоритм этого не видит на первом шаге. И жадный алгоритм на первом же шаге попытается отделить 2 объекта одного из классов, и весь процесс построения дерева дальше пойдет таким образом, что оптимальное двухуровневое дерево уже будет невозможно построить, и в итоге строится вот такое дерево из 4-х уровней, которое, конечно же, делит выборку не так, как нам хотелось бы. Как можно с этой ситуацией... ну если не устранить ее полностью, то хотя бы смягчить ее? Есть много разных подходов, и один из самых удачных и прижившихся называется усечением или подрезанием решающих деревьев, по-английски pruning. Этот алгоритм вошел в состав очень известной процедуры C4.5, которая имеет свободнодоступную реализацию, она выложена в Интернете. Этот алгоритм был предложен тем же автором, что и ID3, — Квинланом. Он основан на вот какой идее: что если наша проблема заключается в переобучении, переусложнении структуры дерева, значит, нам нужна контрольная выборка данных, для того чтобы оценивать обобщающую способность. Ну можно это было бы делать в процессе построения дерева, ну вот в этом алгоритме это делается после того, как ID3 уже построил все дерево. Давайте разобьем обучающую выборку на две части: обучающая часть и контрольная. Обычно делается так, чтобы контрольная часть была вдвое короче обучающей. По первой части мы, с помощью ID3, строим дерево, а вторую используем, для того чтобы это дерево упростить. Итак, давайте возьмем каждый объект второй выборки, пропустим его через дерево, получим для каждой внутренней вершины подмножество объектов, которые до этой вершины дошли. И теперь для каждой внутренней вершины мы постараемся понять, нужна она или ее можно заменить терминальной вершиной, или упростить каким-то образом поддерево, которое растет из этой внутренней вершины. Итак, если оказалось, что множество Sv (множество объектов, дошедших до данной внутренней вершины) пусто, то есть какие-то объекты обучающей выборки сюда дошли, но из контрольных объектов не дошел ни один. Давайте тогда эту вершину упростим и заменим ее листовой вершиной, и выберем в этой листовой вершине тот класс, к которому относится большинство объектов обучающей выборки. У нас же нет объектов контрольных, которые сюда пришли, значит, пользуемся обучающими. Дальше мы должны принять решение, чем можно было бы заменить эту внутреннюю вершину. Здесь вариантов много, но в алгоритме прунинга C4.5 используется только 4 возможных варианта: либо мы оставляем это поддерево без изменений, либо мы заменяем поддерево вершины v ее левым дочерним поддеревом, либо мы заменяем ее ее же правым дочерним поддеревом, ну либо мы заменяем ее терминальной вершиной. Как выбрать один из этих четырех вариантов? Очень просто. Надо с помощью каждого из этих вариантов классифицировать объекты контрольной выборки, объекты множества Sv, и сравнить число ошибок, которое получается в каждом из этих четырех вариантов, ну и выбрать тот, где число ошибок меньше. Ну и вот таким образом мы можем вершину за вершиной упростить дерево. Порядок просмотра всех вершин может быть разным, в зависимости от реализации этого алгоритма, можно идти сверху вниз, снизу вверх или идти по внутренним вершинам в каком-то случайном порядке, это зависит от реализации. Есть и другие стратегии построения решающих деревьев и другие очень известные алгоритмы, ну вот, в частности, алгоритм CART — расшифровывается как Classification and Regression Tree (деревья, которые слегка обобщают ту схему, о которой мы говорили выше). Там тоже есть очень похожий на ID3 жадный рекурсивный алгоритм построения дерева, там тоже применяются стратегии усечения (или прунинга), но алгоритм обобщен на тот случай, когда мы решаем задачу регрессии. Как это сделано? Ну, естественно, мы используем другой критерий, и самое простое в этом случае и самое естественное — это использовать критерий среднеквадратичной ошибки, тот же самый, который используется в методе наименьших квадратов. Итак, пусть Uv по-прежнему — это множество объектов обучающей выборки, дошедших до вершины v. Если эта вершина терминальная, то мы можем просто усреднить значение ответов во всех этих объектах, и вот это среднее значение, оно и будет оптимальным решением метода наименьших квадратов в этой терминальной вершине. И точно также критерий ветвления, который используется в каждой внутренней вершине этого дерева в процессе его построения. Самый естественный способ — это взять среднеквадратичную ошибку. И тогда для предиката β, который мы собираемся использовать для ветвления, для разбиения выборки U на выборку U0 и U1, только часть объектов, которая пойдет налево и часть, которая пойдет направо, вот выбор этого предиката будет осуществляться по тому, насколько хорошо будет классифицировать то дерево, которое в левом дочернем будет иметь свое среднее значение, в правом дочернем — свое среднее значение. И вот так вот произойдет разбиение, и дальше уже процесс пойдет рекурсивно. В итоге, дерево регрессии строит кусочно-постоянную функцию, потому что в каждом листе ответ, который будет выдавать этот алгоритм, является константой — это среднее значение ответов в объектах обучающей выборки, дошедших до этой листовой вершины. Ну это и означает, что дерево регрессии осуществило разбиение всего пространства объектов на какие-то куски, и в каждом куске выдается свое константное значение, то есть это кусочно-постоянная функция. Как осуществлять оптимизацию структуры дерева в этом случае? Вот для Classification and Regression Tree придуман очень эффективный критерий, который позволяет выбрать структуру дерева, и делает это несколько не так, как в процедуре прунинга (или усечения), о который я рассказывал до этого в алгоритме C4.5. Здесь можно выписать критерий, который состоит из двух частей: первая — это среднеквадратичная ошибка, которую мы и минимизируем в алгоритме CART, а вторая часть — это штрафное слагаемое, вот оно для нас и интересно. Это штрафное слагаемое представляет собой просто количество листовых вершин, домноженное на какой-то коэффициент, который называется константа регуляризации. Так вот, если этот коэффициент мы начинаем увеличивать, увеличивается штраф за сложность дерева, за то, что в этом дереве данное количество листовых вершин, и дерево должно, по идее, упроститься. То есть, при каждом значении α мы построим свое дерево, чем больше α, тем проще дерево. Но самый интересный факт, это строго доказываемый факт, который заключается в том, что если мы будем менять этот коэффициент α (мы будет его непрерывно, например, увеличивать), то в таком случае получим последовательность вложенных деревьев, которая к тому же единственная, то есть она не зависит от того, как у нас пойдет процесс построения дерева. Ну и это означает то, что мы можем всегда выбрать вот эту вот константу α таким образом, чтобы у нас была минимальна ошибка на тестовой выборке. И вот эта стратегия как раз и лежит в основе метода, который называется Minimal Cost-Complexity Pruning. Для случая классификации аналогичная стратегия может быть использована для усечения деревьев, и в таком случае используется критерий Джини. Давайте подытожим. Итак, решающие деревья имеют очевидные преимущества: они хорошо интерпретируемы, допускают разнотипные данные, данные с пропусками. Имеют также некоторые недостатки: переобучение, фрагментация. Недостатки следуют из того, что построение дерева — это жадная процедура. Но недостатки можно смягчить применением всякого рода усечений: процедур прунинг или процедур со штрафным слагаемым, которое используется в методе CART. Еще одним способом устранения этих недостатков является композиция — мы уже можем использовать не одно дерево, а построить много деревьев и усреднять их ответы. Но это уже другая история, и это будет рассказано в лекциях про композиции. [ЗАСТАВКА]
