Подход к выбору атрибутов, используемый в обучении дерева решений, предназначен для минимизации глубины окончательно сформированного дерева. Идея этого подхода состоит в том, что следует выбирать в первую очередь такой атрибут, который позволяет сразу же выполнить максимально возможный объем работы по обеспечению правильной классификации примеров. Идеальный атрибут позволяет разделить множество примеров на подмножества, целиком состоящие из положительных или отрицательных примеров. Атрибут Patrons не идеален, но является достаточно приемлемым. С другой стороны, действительно бесполезный атрибут, такой как туре, создает подмножества примеров приблизительно с такими же соотношениями положительных и отрицательных примеров, как и в первоначальном множестве.

Таким образом, нам достаточно лишь определить формальный критерий оценки понятий "достаточно приемлемый" и "действительно бесполезный", после чего появится возможность реализовать функцию Choose-Attribute, применяемую в алгоритме, который приведен в листинге 18.1. Этот критерий должен принимать максимальное значение, когда атрибут является идеальным, и минимальное значение, когда атрибут полностью бесполезен. Одним из подходящих критериев является ожидаемый объем информации, предоставляемый атрибутом; в данном определении термин "информация" используется в математическом смысле, впервые определенном Шенноном и Уивером [1394]. Чтобы понять суть концепции информации, достаточно представить себе, что она является ответом на вопрос, например, о том, упадет ли подброшенная монета орлом вверх. Объем информации, содержащийся в ответе на этот вопрос, зависит от наших априорных знаний. Чем меньше мы знаем, тем больше получим информации. В теории информации информационное содержание ответа измеряется в битах. Один бит информации является достаточным для ответа "да" или "нет" на вопрос о том, что полностью неизвестно, например, каков результат подбрасывания подлинной монеты. Вообще говоря, если возможные ответыимеют вероятности, то информационное содержание J фактического ответа определяется с помощью следующего уравнения:

Для проверки этого уравнения рассмотрим случай с подбрасыванием подлинной монеты. При этом будет получено следующее: