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