18.1, Для всего множества примеров: I = 2.2Э25
IreE(size)» 1,5422, Gain(size) = 0.7503
Info(size) - 0.979S, GainRatio(size) = 0.7503/0.9799
- 0.7657 Ires(holes) = 0.9675, Gain[holes> = 1.324 Info(holes) = 1.5546, GainRatio(holes) = 0.8517
18.2. Gain = I - ires
I - - (p(D) log p{D) + p(~D) log p(~D)>
= - (0.25 log C.25 + 0.75 log 0.75) - 0.6113 Для вычисления Ires требуется p(S), p(~S), p(DIS), p[D(-S) p(S) = p(S[D> p<D) + p(SI~D) p(~D) - 0.75 * 0.25
+ 1/6 * 0.75 - 0.3125 С использованием формулы Байеса:
p(D|S) - ptD) p(SID) / p[S> - 0.25 * 0.75 / 0.3125 = 0.6 p(~D|S! =0.4 plD|-S> = p(D)*p(~5|D) / p(~S) = 0.25 * 0.25 / (1-0.3125)
= 0.09090 Ires = p(S)*I(D|S> + p(~S}*I(D|~S) = 0.6056 В приведенной выше формуле I(D|S) обозначает количество информации о болезни, полученное с учетом наличия указанного симптома. Gain = 0.2057 GainRatio - GainiS) / I(S) - 0.2057/0.8Э60 == 0.2296
18.5. % prunetree(Tree, PrunedTcee): переменная PrunedTree
i представляет собой дерево Tree, отсечение поддеревьев
% которого выполнено оптимальным образом по отношению
% к оиеночнсму значению ошибки классификации
% Предполагается, что деревья являются бинарными:
% Tree = leaf(Mode, ClassFreguencyListi или
% Tree = tree(Root, LeftSubtree, RightSubtree)
prunetree(Tree, PrunedTree):-
prune(Tree, PrunedTree, Ecror, FreguencyList). I prune(Tree г PrunedTree, Error, FreguencyList): % переменная PeunedTree представляет собой дерево Tree, I отсечение поддеревьев которого выполнено оптимальным % образом пс отношению к оценочному значению ошибки % классификации, a FreguencyList - это список частот % классов в корне дерева Tree prune (leaf(Node, FregList), leafi Node, FregList), Error, FregL.ist):-
static_error(FregList, Error). prune(tree! Root, Left, Right}, PrunedT, Error, FregList):-
prune(Left, Leftl, LeftEcror, LeftFreg),
prune! Right, Rightl, RightError, RightFreg),
sijmlists! LeftFreg, RightFreg, FregList), % Добавить
% соответствующие элементы
static_error(FregList, StaticErr),
sum{ LeftFreg, N1),
suml RightFreg, K2),
BackedErr is (N1 * LeftError + H2 * RightError) / (Ml + H2),
decide! StaticErr, EackedErr, Root, FregList, Leftl, Rightl, Error, PrunedT). % Предикат, вырабатывающий решение о том, должно ли быть
Решения к отдельным упражнениям
\ выполнено отсечение или нет:
decide! S tatErr, BackErr, Root, FreqL, _, _, StatErr,
leaf(Root, FreqLM:-
StatErr «< BackErr,!. % Статическая опжбка меньше: % выполнить отсечение поддеревьев % В противном случае не выполнять отсечение: decide) _, BackErr, Root, _, Left, Right, BackErr,
treet Root, Left, Right)). % static_error[ ClassFrequencyList, Error): оценочное i значение ошибки, классификации static_error(FreqList, Error):-
max[ FreqList, Max), I максимальное число I в списке FreqList
sum (FreqList, All), $ Сумма чисел в списке FreqList
number_of_classes(NumClasses),
Error is (All - Max + NumClasses - 1) / { All + NuraClassesl. sum{[],0). suiffl [Number I Numbers], Sum):-
sural Numbers, Suml),
Sum is Suml + Number. max< [X], X). max([X,Y I List], Max):-
X > YE!, max([X I List], Max)
maxt [Y I List!, Max). sumlistsm, [],[)]-
sumlistst (XI I LI]. 1X2! L2], [X3 I L3]):-
X3 is XI + X2,
suralistst LI, L2, L3). % Произвольное дерево treel(tree(a, i Корень
tree(br leaf(e, [3,2]), leaf(f, [1,0])), % Левое
% поддерево
treet с, tree' d, leaf! g, [1,1}), leaf! h, 10,1])}, leaf! i, [1,0])))). rauaber_of_classea (2). % Контрольный вопрос: %?- treel(Tree), prunetree) Tree, PrunedTree).
