2.7 Рекурсивный метод.
Для построения дерева решений в случае сложной
зависимости между характеристиками, применяют методы, более сложные, чем метод
последовательного ветвления.
Общая схема метода
аналогична той, которая использовалась в методе последовательного ветвления, с
той разницей, что вместо операции разделения используется более сложная
операция разрастания. Рассмотрим основные шаги этого метода.
1)
Провести
операцию разрастания для корневой вершины;
2)
Проверить
перспективность ветвления для каждой из новых висячих вершин; если какая-либо
вершина становится листом, присвоить ей соответствующее решение.
3)
Провести
операцию разрастания для каждой висячей вершины;
Далее шаги 2,3 повторяются, пока не останется более
перспективных для ветвления вершин, либо не будет достигнута максимально допустимая
сложность дерева.
Опишем операцию разрастания.
В этой операции используется критерий качества дерева, записанный в следующем
виде: Q=Nerr/N+αM/N (для задачи РО) или Q=d/d0+αM/N
(для задачи РА), где α - некоторый заданный параметр.
Операция состоит из
следующих шагов.
1)
Фиксировать
очередную характеристику Xj (j=1,...,n).
2)
«Начальное»
ветвление (построение «начального» дерева). Под «начальным» ветвлением
подразумевается разделение вершины на максимально возможное (определяемое по
выборке) число новых вершин (рис. 14). В случае количественной характеристики
это число равно числу подынтервалов разбиения (т.е. каждому подынтервалу
сопоставляется своя новая вершина), в случае качественной или порядковой
характеристики каждой вершине сопоставляется одно значение характеристики.
Рис.14
3)
Проверить
перспективность ветвления для всех висячих вершин «начального» дерева.
4)
Рекурсивным
образом провести операцию разрастания для перспективных вершин «начального» дерева
(рис.15). Максимальная глубина рекурсии ограничена заданным порогом R.
R=3
Рис.15
5)
Вычислить
критерий качества полученного дерева.
6)
Перебрать
все допустимые для срастания пары вершин «начального» дерева.
7)
Для
каждой пары рекурсивным образом провести операцию разрастания объединенной
вершины и вычислить критерий качества
полученного варианта дерева.
8)
Запомнить
вариант дерева с наилучшим критерием качества (рис.16).
Рис.16
9)
Повторить
шаги 6–8 для новых пар срастаемых вершин «начального» дерева, оставляя каждый
раз в памяти наилучший вариант. Шаги повторяются до тех пор, пока все вершины
не объединятся в одну.
10)
Перейти к следующей характеристике и повторять
шаги 1–9 до тех пор, пока не будут рассмотрены все характеристики.
Наиболее трудоемким в этом
алгоритме является 4-й шаг. При каждом рекурсивном обращении к операции
разрастания проводятся шаги 1-11, т.е. строится оптимальное поддерево для
соответствующего подмножества наблюдений, причем эта операция может «вызывать»
сама себя несколько раз. Путем увеличения параметра R можно увеличивать
глубину рекурсивной вложенности, что позволяет находить более сложные
зависимости между характеристиками (правда, при этом увеличивается время работы
и требуемый объем памяти).
Еще одной чертой этого
метода является то, что заранее не фиксируется число ветвей, выходящих из
каждой вершины, а ищется их оптимальное число.
Параметр α можно
выбрать равным единице. При увеличении данного параметра дерево будет
становиться более простым (т.е. содержать меньшее число конечных вершин), а при
уменьшении – наоборот, становиться более сложным.