На рис. 18.3 показано, как начинается работа алгоритма. Ему предъявляются 12 обучающих примеров, которые классифицированы на множества положительных и отрицательных примеров. После этого принимается решение о том, какой атрибут должен использоваться для первой проверки дерева. На рис. 18.3, а показано, что Туре — неподходящий атрибут, поскольку после его проверки остаются четыре возможных результата, каждый из которых содержит одинаковое количество положительных и отрицательных примеров. С другой стороны, на рис. 18.3, б можно видеть, что Patrons — довольно важный атрибут, поскольку если его значение равно None или Some, то остаются такие множества примеров, для которых можно сразу же получить определенный ответ (No и Yes соответственно). А если значением является Full, то остается смешанное множество примеров. Вообще говоря, после того, как проверка первого атрибута разбивает множество примеров на подмножества, каждый результат сам становится определением новой задачи обучения дерева решений с меньшим количеством примеров и количеством атрибутов, сократившимся на единицу. Ниже описаны четыре случая, которые следует рассматривать при анализе подобных рекурсивных задач.

1.    Если имеются некоторые положительные и отрицательные примеры, то следует выбрать наилучший атрибут для выполнения по нему разбиения. Как показано на рис. 18.3,5, для разбиения оставшихся примеров используется атрибут Hungry.

2.    Если все оставшиеся примеры являются положительными (или отрицательными), то работа закончена и можно дать ответ Yes или No. На рис. 18.3, б показаны примеры достижения этой цели в случаях None и Some.

3.    Если не осталось ни одного примера, это означает, что соответствующие примеры не наблюдались, поэтому следует возвратить применяемое по умолчанию значение, вычисленное на основании мажоритарной классификации в родительском узле данного узла.

4.    Если не осталось ни одного атрибута, но имеются и положительные и отрицательные примеры, то налицо проблема. Такая ситуация означает, что данные примеры имеют полностью одинаковое описание, но классифицированы поразному. Такое происходит, если некоторые данные определены неправильно; принято говорить, что в данных присутствует шум. Кроме того, такое происходит, либо если атрибуты не предоставляют достаточной информации для полного описания ситуации, либо если данная проблемная область действительно является недетерминированной. Одним из простых способов преодоления такой проблемы является использование мажоритарного голосования.

Рис. 18.3. Разбиение множества примеров на подмножества путем проверки атрибутов: в результате разбиения по атрибуту Туре не удается приблизиться к решению задачи проведения различий между положительными и отрицательными примерами (а); разбиение по атрибуту Patrons позволяет многого добиться в части разделения положительных и отрицательных примеров (б). После разбиения по атрибуту Patrons довольно неплохой второй проверкой становится проверка по атрибуту Hungry