Глава 18. 18.1, Для всего множества примеров: I = 2.2Э25

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 > Y_E!, 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(b_r 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).