Решающее дерево
Cтраница 3
Решающие деревья более сложны для понимания, чем продукционные правила, что является их недостатком. С другой стороны, любое решающее дерево может быть преобразовано в набор продукционных правил: каждому пути от корня дерева до концевой вершины соответствует одно продукционное правило. Его посылкой является конъюнкция условий атрибут - значение, соответствующих пройденным вершинам и ребрам дерева, а заключением - имя класса, соответствующего концевой вершине. [31]
Алгоритм ID5R строит решающее дерево инкрементно, модифицируя решающее дерево таким образом, чтобы наиболее информативный атрибут всегда проверялся первым. Хотя алгоритм сохраняет обучающие примеры в решающем дереве, они используются только в процессе изменения структуры дерева, а не обрабатываются каждый раз при добавлении нового примера. [32]
Решающее дерево, простроенное этим алгоритмом, совпадает с решающим деревом, которое было бы построено с помощью алгоритма J. Инкрементная версия сохраняет предыдущий вариант дерева решений, а при добавлении новых примеров лишь перестраивает его. Алгоритм хранит достаточно информации, чтобы при появлении нового примера заново вычислить информативность каждого атрибута и перестроить дерево таким образом, чтобы наиболее информативный атрибут оказался в вершине дерева. [33]
Алгоритм ID5R выглядит следующим образом. Он получает на входе решающее дерево и очередной обучающий пример и выдает обновленное решающее дерево. [34]
Характерной чертой алгоритма / D3 является то, что для детерминированных ( без шума) входных данных примеры обучающего множества всегда классифицируются правильно. Когда алгоритм ID3 применяется к данным, которые могут содержать значения в некоторой степени случайным образом искаженные, например, в результате ошибок, измерения, результирующее решающее дерево становится слишком большим и сильно ветвящимся. В этом случае предлагается построение решающего дерева разбить на три части. Сначала с помощью алгоритма / D3 или IDbR строится первоначальное большое дерево, затем это дерево подвергается упрощению с целью удаления ветвей с низкой статистической достоверностью. Последним этапом является обработка дерева для повышения его понятности. [35]
Три формы представления решающего дерева соответствуют трем предложениям отношения решить. Поэтому все, что нам нужно сделать для изменения нашей исходной программы решить, - это подправить каждое из этих трех предложений, просто добавив в каждое из них решающее дерево в качестве второго аргумента. Измененная программа показана на рис. 13.8. В нее также введена дополнительная процедура отобр для отображения решающих деревьев в текстовой форме. [36]
Мы получаем ответ да или нет, но не получаем решающее дерево. Можно было бы восстановить решающее дерево при помощи трассировки программы, но такой способ неудобен, да его и недостаточно, если мы хотим иметь возможность явно обратиться к решающему дереву как к объекту программы. [37]
 |
Отношение рассмотрен Цель, Трасса, Ответ. [38] |
Теперь мы приступим к реализации нашей оболочки, следуя тем идеям, которые обсуждались в предыдущем разделе. Цель - это вопрос, подлежащий рассмотрению; Трасса - это цепочка, составленная из целей-предков и правил, находящихся между вершиной Цель и вопросом самого верхнего уровня; Ответ - решающее дерево типа И / ИЛИ для вершины Цель. [39]
Это немного упрощает исследование дерева решения. Если решающее дерево все же очень велико, вы можете, по крайней мере, найти приближенные решения, даже если они и не являются наилучшими. [40]
Характерной чертой алгоритма / D3 является то, что для детерминированных ( без шума) входных данных примеры обучающего множества всегда классифицируются правильно. Когда алгоритм ID3 применяется к данным, которые могут содержать значения в некоторой степени случайным образом искаженные, например, в результате ошибок, измерения, результирующее решающее дерево становится слишком большим и сильно ветвящимся. В этом случае предлагается построение решающего дерева разбить на три части. Сначала с помощью алгоритма / D3 или IDbR строится первоначальное большое дерево, затем это дерево подвергается упрощению с целью удаления ветвей с низкой статистической достоверностью. Последним этапом является обработка дерева для повышения его понятности. [41]
В результате процесс поиска не успевает осознать, что А - это тоже целевая вершина и что порождено решающее дерево. Вместо этого происходит переключение активности на конкурирующую альтернативу с. Теперь процесс поиска обнаруживает, что найдено решающее дерево ( включающее в себя целевые вершины h и g), на чем поиск заканчивается. [42]
 |
Формулировка игровой задачи для игры двух лиц в форма И / ИЛИ-дерева. участники игры. - игрок и противник. [43] |
Таким образом, все позиции противника - это И-вершины. Целевые вершины - это позиции, выигранные согласно правилам игры, например позиции, в которых король противника получает мат. Позициям проигранным соответствуют задачи, не имеющие решения. Для того, чтобы решить игровую задачу, мы должны построить решающее дерево, гарантирующее победу игрока независимо от ответов противника. Такое дерево задает полную стратегию достижения выигрыша: для каждого возможного продолжения, выбранного противником, в дереве стратегии есть ответный ход, приводящий к победе. [44]
На любой стадии поиска каждый преемник ИЛИ-вершины соответствует некоторому альтернативному решающему дереву-кандидату. Процесс поиска всегда принимает решение продолжать просмотр того дерева-кандидата, для которого F-оценка минимальна. Вернемся еще раз к рис. 13.4 и посмотрим, как будет вести себя процесс, поиска на примере И / ИЛИ-графа, изображенного на этом рисунке. В начале дерево поиска состоит всего из одной вершины - стартовой вершины а, далее дерево постепенно растет до тех пор, пока не будет найдено решающее дерево. На рис. 13.10, показан ряд мгновенных снимков, сделанных в процессе роста дерева поиска. Для простоты мы предположим, что А 0 для всех вершин. [45]
Страницы: 1 2 3 4