: induce_tree(Attributes, Examples, Tree)
II. Prolog
Tree , Examples Attributes. , 18.1, , , :
induce tree! Tree):-
findalK example (Class, Obj), example(Class, Obj), Examples), findalK Att, attribute; Att,), attributes}, induce_tree(Attributes, Examples, Tree).
.
1. Tree = null, .
2. Tree = leaf (Class), Class.
3. Tree = tree{ Attribute, [ Vail: SubTreel, Val2: SubTree2,... ]), , Attribute , Vail, Val2,... Attribute, a SubTreel, SubTree2,... - .
:
% induce tree! Attributes, Examples, Tree) iadtaee_tr~ie (_, [], null);- 1.
induce treef, [ example (Class, i I Examples], leaf Class)):-
not ( member t example (ClassX, ~_), Examples), %
classx \== Class),!. %
induce tre(Attributes, Examples, trees Attribute, SubTrees)):-
22£.Att5&Values], restAtts, ^... .,.
induce trees SubTrees Examples Values Attribute :
% induce trees! Att, Vals, RestAtts, Examples, SubTrees)
induce_trees [ -, [], _, _, 111. % ,
induce trees(Att, [vail | vals], RestAtts, Exs, [Vail: Treel | Trees]):-attvll subset R Att =, ailxa ExseS Exam,leSubset!,
attval_subset(Attribute = Value, Examples, Subset) , Subset -- Examples, Attribute = Value :
attval_subsett Attribute Value, Examples, ExampleSubset):-
satisfy* Object, Description) 18.3. choose_attribute , . . setof. , .
18. 431
choose_a-tribute(Atts, Examples, BestAtc):-setoft Impurity/Att,
|
|
(membert Att, Atts), irapurityl. Examples, ktt, Impurity)), [ Hinlmpurity/BestAtt I _)).
impurityl[ Examples, Attribute, Impurity)
; Impurity Examples Attribute.
18.3.
, impurity!.
, ,
Gini, . ,
18.1, size Gini
:
?- Examples =... , 18.1 impurityl (Examples, size. Impurity). Impurity - 0.647619
, Impurity :
Impurity = Gini size)
(small)*((nut I small)*p(screw | small)+...)+p(large)*(...)
= 7/12 * (3/7 * 2/7 +...) + 5/12 *(...) = 7/12 * 0.653061 - 5/12 * 0.64 = 0.647619
18.4. ,
, , ,
18.1. ,
choose_attribute, setof,
.
show! DecisionTree!
, . , , . 18.10, :
holes none size
small ==> screw large ==> pen 1
shape
long *=> key compact ■■ nut other ==> null 2
size
small:> key large > scissors 3 ==> null many ■="> null
432 II. Prolog
18.6.
, , . . , . , , . , , , . , , , . . , , . , .
: -, , , , -, . , . , .
|
|
, S. , S 100 , 99 1, 2. , , , , , 2 S . , , 1. , , , .
- . , , . , , , ..
, , (forward pruning), , (post-pruning). , . , , . . 18.12. . , . ?
18.
. 18JS. .
, , .. , - . - , , . , . , . . , , . .
( ) , , . , , .
|
|
, , . , . , , ? , , , . , (minimal error pruning).
, . . 18.13, , s, ,... , pi , ^ __. , , . , s (.. .,...). , . , ;,... .
, . ? , .. . , .
434 II. Prolog
?
. 18.13.
1.
, s . s
s , ,
.
, ,
s, , .
(static error) s
:
e(s) = p(class * I s)
2. s,
E(Ti), E{Ta),...
Tj, T2..........
. :
; E(Ti) + 2 {2) +...
<backed-up error). , s : , , . , ,
()
i(e(s),Zj pi E(Ti) )
, , () = (s).
, e(s), , . , , , s. , S, 5 N, . s. , , , / ( ) s. , s , , , , . , , s . 1/1 * 100 = 100%, 0/1 = 0. s , -
|
|
18.
. , s . 1/2 * 100 = 50%!
, , . , . , 1. , , 0,5. "" , 0,5, 1, , . , , .
, , . , , . m- ;
" N +
pi , . . , , . . , . , ; . m- . , , . m- , .
m- : fa . N " ' B;m+ N* fj^
m-; , , N . , N = 0 = . (N ), n/'N. . m (m > G) , .
m - . , , m (, = 100) . , , , , (, . = 0.2) . , , . , -
|
|
II. Prolog
. , .
, -,. , . , ( s), , . ( ) , . -, . ,
Pa = * **/ m k
:
+; = N +■
, . , , , . , .
. 18.14 . [3,2]. , 1 2. , , :
E(b_ieft) = 1 - ^ = 1 -|-4 = 0.429
b (b_right) = 0. 333. : e(b> = 0.375
: BackedUpError> = 5 /6 * -429 + 1/6 * 0.333 == 0.413
, b :
() = 0.375
m- . m- , . . , . , , m- . m .
18.
11(>|'| ."i- |
[1. 1] [0, 1] 0.5 03J3 |
: |
[1.2] [1.0]
. 18.14. . , 1 2, . , ,, , . , . ( )
. . , . 5 (growing set) (pruning set). , "" . , , , . , -
438 II. Prolog
. . , , , . , , , , , , .
18.5. . , , , , . 30 25 . , , . , , , 30%, , , , 50-60%. , , , m-. ?
18.6.
prune tree { Tree, PrunedTree)
Tree , . Tree , . , , , number of classes ().