Глава 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! StatErr,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 IList! , 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) .