5.2 Бинарные деревья решений
Как было отмечено в разделе 4.3, использование иерархических древовидных структур (decision trees) является одним из наиболее универсальных и эффективных методов классификации и регрессии (Hunt et al., 1966; Breiman at al., 1984; Loh and Shih, 1997). Классификационные модели деревьев рекурсивно делят набор данных на подмножества, являющиеся все более и более гомогенными относительно определенных признаков. Создается решающее правило классификации иерархического типа и формируется ассоциативный логический ключ, дающий возможность выполнять распознавание объектов из новых выборок.
Самым простым, частным случаем деревьев решений являются деревья бинарной классификации, в узлах которых ветвление может вестись только в двух направлениях, т.е. осуществляется выбор из двух альтернатив (“да” и “нет”). Создание такой дихотомической классификационной модели осуществляется с использованием алгоритма ID3 (Interactive Dichotomizer).
В основе алгоритма (Quinlan, 1986) лежит циклическое разбиение обучающей выборки на классы в соответствии с переменной, имеющей наибольшую “классифицирующую силу”. Каждое подмножество наблюдений (объектов), выделяемое такой переменной, вновь разбивается на классы с использованием следующей переменной с наибольшей классифицирующей способностью и т.д. Разбиение заканчивается, когда в итоговом подмножестве оказываются объекты лишь одного класса. Пути движения по полученному дереву решений с верхнего уровня на самые нижние определяются логическими правилами в виде цепочек конъюнкций.
При выборе критерия, оценивающего классифицирующую силу, обычно используют теоретико-информационный подход. Мера информационного выигрыша IG (Information Gain) для разбиения A определяется как разность энтропии Шеннона \(H(S)\) для исходного набора данных и суммы энтропий всех фрагментов данных после разбиения \(Н(S_{\nu})\) с соответствующим весом в зависимости от размера каждой части:
\[IG(S, A) = H(S) - \sum_{\nu \in V}\frac{S_{\nu}}{S}H(S_{\nu}),\]
где \(\nu\) выбранное опорное значение переменной \(V\), использованное для разбиения \(A\). Если разделение на классы выполнено оптимально, то каждое подмножество \(S_{\nu}\) будет иметь небольшую энтропию, и, следовательно, значение \(IG\) будет максимальным. На языке R этот критерий может быть рассчитан следующим образом:
Entropy <- function(vls) {
res <- vls/sum(vls)*log2(vls/sum(vls))
res[vls == 0] <- 0
-sum(res)
}
InformationGain <- function(tble) {
entropyBefore <- Entropy(colSums(tble))
s <- rowSums(tble)
entropyAfter <- sum(s/sum(s) *
apply(tble, MARGIN = 1, FUN = Entropy ))
informationGain <- entropyBefore - entropyAfter
return (informationGain)
}Для реализации алгоритма ID3 используем компоненты пакета data.tree: объект класса tree (дерево) и метод AddChild , добавляющий к выстраиваемому дереву очередной дочерний узел (см. http://ipub.com/wp-content):
IsPure <- function(data) {
length(unique(data[, ncol(data)])) == 1
}
TrainID3 <- function(node, data) {
node$obsCount <- nrow(data)
# если текущий набор данных принадлежит к одному классу, то
if (IsPure(data)) {
#создается лист дерева с экземплярами этого класса
child <- node$AddChild(unique(data[, ncol(data)]))
node$feature <- tail(names(data), 1)
child$obsCount <- nrow(data)
child$feature <- ''
} else {
# рассчитывается вектор информационных выигрышей IG
ig <- sapply(colnames(data)[-ncol(data)],
function(x) InformationGain(
table(data[, x], data[, ncol(data)])))
# выбирается значение признака с наибольшей величиной IG
feature <- names(which.max(ig))
node$feature <- feature
# создается подмножества данных на основе этого значения
childObs <- split(data[, names(data) != feature,
drop = FALSE], data[, feature], drop = TRUE)
# создаются дочерние узлы дерева c именем признака
for (i in 1:length(childObs)) {
child <- node$AddChild(names(childObs)[i])
# осуществляется рекурсия алгоритма для дочернего узла
TrainID3(child, childObs[[i]])
}
}
}Обратим внимание, что наша функция TrainID3 является рекурсивной, т.е. для выполнения итераций вызов функции осуществляется из тела ее самой. Функция завершает работу, если все ветви дерева завершаются листьями с объектами одного класса.
Для иллюстрации работы алгоритма ID3 обратимся к нашему примеру по классификации лиц избирателей (см. рис. 5.1 в разделе 5.1). Для получения осмысленной визуализации дерева перейдем от численных обозначений к натуральным названиям признаков и их градаций. В результате получаем следующее дерево решений:
DFace <- read.delim(file = "data/Faces.txt", header = TRUE, row.names = 1)
DFaceN <- DFace[, -17]; Class <- DFace$Class
DFaceN[DFaceN == 1] <- "Да" ; DFaceN[DFaceN == 0] <- "Нет"
Class[Class == 1] <- "Патриот"
Class[Class == 2] <- "Демократ"
DFaceN <- cbind(DFaceN,Class)
colnames(DFaceN) <- c("голова_круглая", "уши_оттопырен",
"нос_круглый", "глаза_круглые", "лоб_морщины",
"носогубн_складка", "губы_толстые", "волосы", "усы","борода",
"очки","родинка_щеке", "бабочка", "брови_подняты", "серьга",
"курит_трубка", "Группа")
library(data.tree)
tree <- Node$new("DFaceN") # Создаем «пустое» дерево
TrainID3(tree, DFaceN)
print(tree, "feature", "obsCount")## levelName feature obsCount
## 1 DFaceN уши_оттопырен 16
## 2 ¦--Да борода 10
## 3 ¦ ¦--Да нос_круглый 7
## 4 ¦ ¦ ¦--Да курит_трубка 3
## 5 ¦ ¦ ¦ ¦--Да Группа 1
## 6 ¦ ¦ ¦ ¦ °--Патриот 1
## 7 ¦ ¦ ¦ °--Нет Группа 2
## 8 ¦ ¦ ¦ °--Демократ 2
## 9 ¦ ¦ °--Нет губы_толстые 4
## 10 ¦ ¦ ¦--Да Группа 1
## 11 ¦ ¦ ¦ °--Демократ 1
## 12 ¦ ¦ °--Нет Группа 3
## 13 ¦ ¦ °--Патриот 3
## 14 ¦ °--Нет Группа 3
## 15 ¦ °--Демократ 3
## 16 °--Нет брови_подняты 6
## 17 ¦--Да Группа 2
## 18 ¦ °--Демократ 2
## 19 °--Нет Группа 4
## 20 °--Патриот 4Выращивание дерева начинается с переменной, имеющей наибольшее значение критерия IG, каковой оказались оттопыренные уши: ее значению “Да” соответствует группа из 10 объектов, а значению “Нет” - из 6. Если в первой ветви для классификации последовательно привлекаются еще 4 признака (наличие бороды, круглого носа, курительной трубки и толстых губ), то во втором случае безошибочное разбиение сразу происходит при использовании поднятых бровей. Проверим теперь, насколько эффективен полученный классификатор на обучающей выборке:
Predict <- function(tree, features) {
if (tree$children[[1]]$isLeaf)
return(tree$children[[1]]$name)
child <- tree$children[[features[[tree$feature]]]]
return( Predict(child, features))
}
pred <- apply(DFaceN[, -17], 1, function(x) Predict(tree, x))
table(Факт = DFaceN$Группа, Прогноз = pred)## Прогноз
## Факт Демократ Патриот
## Демократ 8 0
## Патриот 0 8Предсказание электоральной группы по всей обучающей выборке, как и в случае логистической регрессии, также оказалось безошибочным. Однако нет уверенности, что построенные деревья будут столь же успешны при практической реализации на “свежих” данных. Для оценки эффективности модели выполним перекрестную проверку:
Nerr <- 0
for (i in 1:nrow(DFaceN)) {
tree <- Node$new("DFaceN")
TrainID3(tree, DFaceN[-i, ])
Nerr = Nerr +
sum(DFaceN[i,17] != Predict(tree,DFaceN[i, -17])) }
(Nerr/nrow(DFaceN))## [1] 0.25При выполнении скользящего контроля четыре объекта из 16 оказались неверно предсказанными с помощью бинарного дерева, построенного после исключения тестируемого примера. Считается (Дук, Самойленко, 2001), что алгоритм ID3 в случае взаимозависимых признаков нередко направляет ход логического вывода по ложному пути и создает лишь иллюзию правильного рассуждения. Но для более обоснованных выводов следует рассматривать результаты тестирования на более серьезных примерах, чем наш.