Subject: Re: work with ID3

From: "Richard A. O'Keefe" <[email-masked]>
Date: Thu, 19 Oct 2000 11:09:14 +1300 (NZDT)

"Oliver" wrote

	I used the id3 algorithm to get a output tree in the form of e.g.
	tree(legs,
	    [2+man,
	     3+[],
	     4+t(food,
	                [meat+lion,
	                 vegetables+giraffe])])
	
This can't be right.  Presumably it's
	tree(legs, [
	    2+man,
	    3+[],
	    4+tree(food, [
	      ^^^^meat+lion,
	          vegetables+giraffe])])
and I'm rather unhappy about the 3+[] case, which doesn't make much sense.
This is a claim that if something has 3 legs then it is a '[]', and not at
all a claim that nothing is known to have 3 legs.

How do you use a tree like this?  First of all, let's write down a type:

    :- type tree    --> tree(atom, list(branch)).
    :- type branch  --> +(atomic, oddball).
    :- type oddball --> tree 'UNION' atom.

It would be much much cleaner if it were
	:- type tree --> empty | leaf(atom) | tree(atom,list(branch)).
	:- type branch --> +(atomic,tree).

	tree(legs, [
	    2+leaf(man),
	    3+empty,
	    4+tree(food, [
	    	meat+leaf(lion),
	    	vegetables+leaf(giraffe)])])

and that's what I'm going to assume.

How do you use a tree like this to classify things?
By writing a recursive predicate that follows the structure of
the tree, how else?  You will need some other predicate to be
supplied to tell you what the attribute values of some thing
to be classified are, let's call that

	object_attribute_value(Object, Attribute, Value)

Then the code is ridiculously simple.
(By the way, I find that naming predicates by stringing together the
names of the argument types is often a good idea.  Sometimes you need
another word or two.)

	tree_object_class(leaf(Class), _, Class).
	tree_object_class(tree(Attribute,Branches), Object, Class) :-
	    object_attribute_value(Object, Attribute, Value),
	    member(Value+Subtree, Branches),
	    tree_object_class(Subtree, Object, Class).

With the original defaulty representation, we'd need a type test or two
and some cuts.