Cтраница 1
Решающее дерево представим следующим образом. [1]
Полное решающее дерево для экспертной системы приведено на рис. 6.11. Сеть, реализующая эту систему с помощью нейропакета Neural Planner, приведена на рис. 6.12. Сеть обучена при помощи 18 обучающих векторов, которые приведены в табл. 6.10. Для опроса сети необходимо закодировать в двоичном виде вопросы, а затем проделать обратную операцию с ответами. [2]
Изначально решающее дерево является пустым. Решающий атрибут выбирается произвольным образом, в данном случае им является атрибут рост. Сразу после преобразования дерево имеет вид, изображенный на рис. 13.6 в ( в квадратных скобках показано количество положительных и отрицательных примеров соответственно), но наиболее информативным является атрибут глаза. [3]
Стоимость решающего дерева мы определим как сумму стоимостей его дуг. [4]
Программа строит решающее дерево ( если таковое существует), рассчитывая на то, что оно окажется оптимальным решением. Будет ли это решение в действительности самым дешевым, зависит от той функции / г, которую использует алгоритм. Существует теорема, в которой говорится о том, как оптимальность решения зависит от А. Эта теорема аналогична теореме о допустимости алгоритма поиска с предпочтением в пространстве состояний ( гл. Обозначим через С ( В) стоимость оптимального решающего дерева для вершины В. Если для каждой вершины В И / ИЛИ-графа эвристическая оценка h ( B) s C ( B), то гарантируется, что процедура и нли найдет оптимальное решение. Если же h не удовлетворяет этому условию, то найденное решение может оказаться субоптимальным. Существует тривиальная эвристическая функция, удовлетворяющая условию оптимальности, а именно А 0 для всех вершин. Ее недостатком является отсутствие эвристической силы. [5]
Алгоритм строит такое решающее дерево, в котором с каждым узлом ассоциирован атрибут, являющийся наиболее информативным среди всех атрибутов, еще не рассмотренных на пути от корня дерева. В качестве меры информативности обычно используется теоретико-информационное понятие энтропии, хотя возможны и другие подходы. [6]
Алгоритм ID5R строит решающее дерево инкрементно, модифицируя решающее дерево таким образом, чтобы наиболее информативный атрибут всегда проверялся первым. Хотя алгоритм сохраняет обучающие примеры в решающем дереве, они используются только в процессе изменения структуры дерева, а не обрабатываются каждый раз при добавлении нового примера. [7]
Поддерево - это решающее дерево для одного из преемников вершины Верш. [8]
Три формы представления решающего дерева соответствуют трем предложениям отношения решить. Поэтому все, что нам нужно сделать для изменения нашей исходной программы решить, - это подправить каждое из этих трех предложений, просто добавив в каждое из них решающее дерево в качестве второго аргумента. Измененная программа показана на рис. 13.8. В нее также введена дополнительная процедура отобр для отображения решающих деревьев в текстовой форме. [9]
Как видно, разметка решающего дерева отличается от разметки, используемой в алгоритме / D3, поэтому его интерпретация также несколько отличается. Когда дерево используется для классификации обучающего примера, от корня дерева проходится путь в соответствии со значениями атрибутов в узлах проверки до тех пор, пока не будет достигнут лист, в котором все примеры принадлежат одному классу. Если достигнутый лист содержит примеры разных классов, то алгоритм развертывает его в поддерево и продолжает работу. [10]
Применение метода графов и выделение решающего дерева - задача трудоемкая и сложная. Необходимо полную задачу свести к подзадачам, а затем, размечая вершины, установить, где вершины разрешимые, а где нет. Остается оценить эти деревья ( работает ЭВМ на микропроцессоре) и далее выбрать из них то ( тот путь перебора), которое имеет минимальную стоимость. [11]
Этот алгоритм также напоминает алгоритм построения решающего дерева ответа на вопрос пользователя, применявшийся в оболочке экспертной системы ( гл. [12]
ИЛИ-список и при только что проведенном расширении получено решающее дерево, считать, что задача, соответствующая всему списку деревьев, также решена, а ее решающее дерево и есть само дерево Дер. Остальные случаи легко понять из текста процедуры собрать. [13]
Алгоритм ID5R строит решающее дерево инкрементно, модифицируя решающее дерево таким образом, чтобы наиболее информативный атрибут всегда проверялся первым. Хотя алгоритм сохраняет обучающие примеры в решающем дереве, они используются только в процессе изменения структуры дерева, а не обрабатываются каждый раз при добавлении нового примера. [14]
Программу нетрудно изменить с тем, чтобы она порождала решающее дерево. [15]