Hi, I'm looking for an help implementation of decision learning tree.
This is my class MP, so I don't want a direct answer.
In this MP, I'm supposed to implement pseudocode in page 537 of "Artificial
Intelligence A Morden Approach by Rusell and Norvig".
I implemented Choose-Attribute and Majority-Value functions so that I can
know which attribute is the best for the given examples and attributes.
For example, I have the following information.
bestTree: (3 ((u h m 2 4 m m) (u h b 2 2 m m) (u l m 2 3 l m) (u h s 2 2 l
l) (u l b 2 5 h m) (u l b 2 2 v m))
((u m b m 5 h v) (a h s m 4 m v) (u l m m 3 l m) (a m b m 3 m h)
(u l b m 4 l v) (u l b m 4 v l)
(u l s m 3 v h) (u h m m 5 v h) (u l m m 3 m m))
((a h b 4 5 l h) (a m b 4 3 h m) (a m m 4 5 m m) (a h m 4 4 m l)
(u m s 4 3 m h)))
It says the best attribute is the third attribute in the attribute set and
there are three different partitions under this attribute.
I think the next thing is calling Decision-Learning-Tree function
recursively, but I got stuck here. The format of decision tree is given to
us. The format is "([attrvalue] [attrnum] default [subtrees])" The problem
is the root node does not have a attrvalue and the other subnodes have the
attrvalue which is determined by the parent node.
How can one recursive function, Decision-Learning-Tree can have two
different attrvalue, NIL for root node and a real attrvalu for other
subnodes? I tried to use a global variable, but it still not easy to me.
Any ideas on how to construct the tree with the given format?
Any comment would be greatly appreciated.
Thanks in advance.
I'd like to explain more what I thought. So I attahced one of my trial codes
to the previous posting.
Hi, I'm looking for an help implementation of decision learning tree.
This is my class MP, so I don't want a direct answer.
In this MP, I'm supposed to implement pseudocode in page 537 of "Artificial
Intelligence A Morden Approach by Rusell and Norvig".
I implemented Choose-Attribute and Majority-Value functions so that I can
know which attribute is the best for the given examples and attributes.
For example, I have the following information.
bestTree: (3 ((u h m 2 4 m m) (u h b 2 2 m m) (u l m 2 3 l m) (u h s 2 2 l
l) (u l b 2 5 h m) (u l b 2 2 v m))
((u m b m 5 h v) (a h s m 4 m v) (u l m m 3 l m) (a m b m 3 m h)
(u l b m 4 l v) (u l b m 4 v l)
(u l s m 3 v h) (u h m m 5 v h) (u l m m 3 m m))
((a h b 4 5 l h) (a m b 4 3 h m) (a m m 4 5 m m) (a h m 4 4 m l)
(u m s 4 3 m h)))
It says the best attribute is the third attribute in the attribute set and
there are three different partitions under this attribute.
I think the next thing is calling Decision-Learning-Tree function
recursively, but I got stuck here. The format of decision tree is given to
us. The format is "([attrvalue] [attrnum] default [subtrees])" The problem
is the root node does not have a attrvalue and the other subnodes have the
attrvalue which is determined by the parent node.
How can one recursive function, Decision-Learning-Tree can have two
different attrvalue, NIL for root node and a real attrvalu for other
subnodes? I tried to use a global variable, but it still not easy to me.
Here is what I came up with.
(list bestAttr
(loop for tr in (cdr bestTree) collect
(dtree-learn tr
(remove bestAttr attributes)
(dtree-majority-value examples))))
Above code give me the following result.
default case: ((u m s 4 3 m h) (u l m m 3 m m) (u h m m 5 v h) (u l s m 3 v
h) (u l b 2 2 v m) (u l b m 4 v l)
(u l b m 4 l v) (a h m 4 4 m l) (u l b 2 5 h m) (a m m 4 5 m
m) (u h s 2 2 l l) (a m b m 3 m h)
(a m b 4 3 h m) (u l m 2 3 l m) (u h b 2 2 m m) (u l m m 3 l
m) (a h s m 4 m v) (a h b 4 5 l h)
(u m b m 5 h v) (u h m 2 4 m m))
bestTree: (3 ((u h m 2 4 m m) (u h b 2 2 m m) (u l m 2 3 l m) (u h s 2 2 l
l) (u l b 2 5 h m) (u l b 2 2 v m))
((u m b m 5 h v) (a h s m 4 m v) (u l m m 3 l m) (a m b m 3 m h)
(u l b m 4 l v) (u l b m 4 v l)
(u l s m 3 v h) (u h m m 5 v h) (u l m m 3 m m))
((a h b 4 5 l h) (a m b 4 3 h m) (a m m 4 5 m m) (a h m 4 4 m l)
(u m s 4 3 m h)))
bestAttr: 3
homogenous example: ((u h m 2 4 m m) (u h b 2 2 m m) (u l m 2 3 l m) (u h s
2 2 l l) (u l b 2 5 h m) (u l b 2 2 v m))
return: u
default case: ((u m b m 5 h v) (a h s m 4 m v) (u l m m 3 l m) (a m b m 3 m
h) (u l b m 4 l v) (u l b m 4 v l)
(u l s m 3 v h) (u h m m 5 v h) (u l m m 3 m m))
bestTree: (5 ((u h m m 5 v h) (u l s m 3 v h) (u l b m 4 v l)) ((u l b m 4 l
v) (u l m m 3 l m))
((u l m m 3 m m) (a m b m 3 m h) (a h s m 4 m v)) ((u m b m 5 h
v)))
bestAttr: 5
homogenous example: ((u h m m 5 v h) (u l s m 3 v h) (u l b m 4 v l))
return: u
homogenous example: ((u l b m 4 l v) (u l m m 3 l m))
return: u
default case: ((u l m m 3 m m) (a m b m 3 m h) (a h s m 4 m v))
bestTree: (1 ((a h s m 4 m v)) ((a m b m 3 m h)) ((u l m m 3 m m)))
bestAttr: 1
homogenous example: ((a h s m 4 m v))
return: a
homogenous example: ((a m b m 3 m h))
return: a
homogenous example: ((u l m m 3 m m))
return: u
homogenous example: ((u m b m 5 h v))
return: u
default case: ((a h b 4 5 l h) (a m b 4 3 h m) (a m m 4 5 m m) (a h m 4 4 m
l) (u m s 4 3 m h))
bestTree: (2 ((u m s 4 3 m h)) ((a h m 4 4 m l) (a m m 4 5 m m)) ((a m b 4 3
h m) (a h b 4 5 l h)))
bestAttr: 2
homogenous example: ((u m s 4 3 m h))
return: u
homogenous example: ((a h m 4 4 m l) (a m m 4 5 m m))
return: a
homogenous example: ((a m b 4 3 h m) (a h b 4 5 l h))
return: a
As you can see above results, my code works fine in terms of the return
values. It finds the best partition and returns appropriate values. But I
cannot construct the given tree format.
Any ideas on how to construct the tree with the given format?
Any comment would be greatly appreciated.
Thanks in advance.
"Young-Jin Lee" <······@uiuc.edu> wrote in message
·························@vixen.cso.uiuc.edu...
> Hi, I'm looking for an help implementation of decision learning tree.
> This is my class MP, so I don't want a direct answer.
>
> In this MP, I'm supposed to implement pseudocode in page 537 of
"Artificial
> Intelligence A Morden Approach by Rusell and Norvig".
>
> I implemented Choose-Attribute and Majority-Value functions so that I can
> know which attribute is the best for the given examples and attributes.
> For example, I have the following information.
> bestTree: (3 ((u h m 2 4 m m) (u h b 2 2 m m) (u l m 2 3 l m) (u h s 2 2 l
> l) (u l b 2 5 h m) (u l b 2 2 v m))
> ((u m b m 5 h v) (a h s m 4 m v) (u l m m 3 l m) (a m b m 3 m
h)
> (u l b m 4 l v) (u l b m 4 v l)
> (u l s m 3 v h) (u h m m 5 v h) (u l m m 3 m m))
> ((a h b 4 5 l h) (a m b 4 3 h m) (a m m 4 5 m m) (a h m 4 4 m
l)
> (u m s 4 3 m h)))
> It says the best attribute is the third attribute in the attribute set and
> there are three different partitions under this attribute.
>
> I think the next thing is calling Decision-Learning-Tree function
> recursively, but I got stuck here. The format of decision tree is given to
> us. The format is "([attrvalue] [attrnum] default [subtrees])" The problem
> is the root node does not have a attrvalue and the other subnodes have the
> attrvalue which is determined by the parent node.
> How can one recursive function, Decision-Learning-Tree can have two
> different attrvalue, NIL for root node and a real attrvalu for other
> subnodes? I tried to use a global variable, but it still not easy to me.
>
> Any ideas on how to construct the tree with the given format?
> Any comment would be greatly appreciated.
>
> Thanks in advance.
>
>
>
I've read your question a few times now, and I'm going to respond with
my best-guess as to the nature of your problem. I would *strongly*
recommend you talk to your TA if you can. There are a number of
different ways of implementing decision trees. You have not included
sufficient detail about the tree you are constructing here. Given that I
don't have my copy of AIMA handy, I cannot give you a precise answer.
The simplest decision tree asks at a given node: Does attribute [x] have
value [xi] at the current node? If so, it takes the "yes" branch, and if
not it takes the "no" branch. A decision tree learning function must
consequently evaluate for each attribute/value pair the best one for
classifying the given data set. This works great for binary attributes,
but for multivalued attributes there are a variety of adjustments that
become necessary. Quinlan's first attempt, ID3, worked with binary
valued attributes. The properties of this algorithm were studied in some
detail by many researchers, and variants were born. Quinlan has since
then refined the ID3 tree and come up with C4 and C4.5. I don't know the
current state of the art. The latest versions have support for real
valued attributes as well. But I'm digressing from your question. The
real point of all this background is that there are a variety of
implementation strategies based on:
1. The number of values an attribute may take (two, many, continuous,
infinite, etc.)
2. The number of categories into which the examples are classified.
3. The presence of noise.
And probably other factors that I'm now forgetting. You have to be more
specific as to the nature of the data you are working with before I can
give a reasonable response.
Sunil
Young-Jin Lee wrote:
> I'd like to explain more what I thought. So I attahced one of my trial codes
> to the previous posting.
>
> Hi, I'm looking for an help implementation of decision learning tree.
> This is my class MP, so I don't want a direct answer.
>
> In this MP, I'm supposed to implement pseudocode in page 537 of "Artificial
> Intelligence A Morden Approach by Rusell and Norvig".
>
> I implemented Choose-Attribute and Majority-Value functions so that I can
> know which attribute is the best for the given examples and attributes.
> For example, I have the following information.
> bestTree: (3 ((u h m 2 4 m m) (u h b 2 2 m m) (u l m 2 3 l m) (u h s 2 2 l
> l) (u l b 2 5 h m) (u l b 2 2 v m))
> ((u m b m 5 h v) (a h s m 4 m v) (u l m m 3 l m) (a m b m 3 m h)
> (u l b m 4 l v) (u l b m 4 v l)
> (u l s m 3 v h) (u h m m 5 v h) (u l m m 3 m m))
> ((a h b 4 5 l h) (a m b 4 3 h m) (a m m 4 5 m m) (a h m 4 4 m l)
> (u m s 4 3 m h)))
> It says the best attribute is the third attribute in the attribute set and
> there are three different partitions under this attribute.
>
> I think the next thing is calling Decision-Learning-Tree function
> recursively, but I got stuck here. The format of decision tree is given to
> us. The format is "([attrvalue] [attrnum] default [subtrees])" The problem
> is the root node does not have a attrvalue and the other subnodes have the
> attrvalue which is determined by the parent node.
> How can one recursive function, Decision-Learning-Tree can have two
> different attrvalue, NIL for root node and a real attrvalu for other
> subnodes? I tried to use a global variable, but it still not easy to me.
>
> Here is what I came up with.
> (list bestAttr
> (loop for tr in (cdr bestTree) collect
> (dtree-learn tr
> (remove bestAttr attributes)
> (dtree-majority-value examples))))
>
> Above code give me the following result.
>
> default case: ((u m s 4 3 m h) (u l m m 3 m m) (u h m m 5 v h) (u l s m 3 v
> h) (u l b 2 2 v m) (u l b m 4 v l)
> (u l b m 4 l v) (a h m 4 4 m l) (u l b 2 5 h m) (a m m 4 5 m
> m) (u h s 2 2 l l) (a m b m 3 m h)
> (a m b 4 3 h m) (u l m 2 3 l m) (u h b 2 2 m m) (u l m m 3 l
> m) (a h s m 4 m v) (a h b 4 5 l h)
> (u m b m 5 h v) (u h m 2 4 m m))
> bestTree: (3 ((u h m 2 4 m m) (u h b 2 2 m m) (u l m 2 3 l m) (u h s 2 2 l
> l) (u l b 2 5 h m) (u l b 2 2 v m))
> ((u m b m 5 h v) (a h s m 4 m v) (u l m m 3 l m) (a m b m 3 m h)
> (u l b m 4 l v) (u l b m 4 v l)
> (u l s m 3 v h) (u h m m 5 v h) (u l m m 3 m m))
> ((a h b 4 5 l h) (a m b 4 3 h m) (a m m 4 5 m m) (a h m 4 4 m l)
> (u m s 4 3 m h)))
> bestAttr: 3
> homogenous example: ((u h m 2 4 m m) (u h b 2 2 m m) (u l m 2 3 l m) (u h s
> 2 2 l l) (u l b 2 5 h m) (u l b 2 2 v m))
> return: u
> default case: ((u m b m 5 h v) (a h s m 4 m v) (u l m m 3 l m) (a m b m 3 m
> h) (u l b m 4 l v) (u l b m 4 v l)
> (u l s m 3 v h) (u h m m 5 v h) (u l m m 3 m m))
> bestTree: (5 ((u h m m 5 v h) (u l s m 3 v h) (u l b m 4 v l)) ((u l b m 4 l
> v) (u l m m 3 l m))
> ((u l m m 3 m m) (a m b m 3 m h) (a h s m 4 m v)) ((u m b m 5 h
> v)))
> bestAttr: 5
> homogenous example: ((u h m m 5 v h) (u l s m 3 v h) (u l b m 4 v l))
> return: u
> homogenous example: ((u l b m 4 l v) (u l m m 3 l m))
> return: u
> default case: ((u l m m 3 m m) (a m b m 3 m h) (a h s m 4 m v))
> bestTree: (1 ((a h s m 4 m v)) ((a m b m 3 m h)) ((u l m m 3 m m)))
> bestAttr: 1
> homogenous example: ((a h s m 4 m v))
> return: a
> homogenous example: ((a m b m 3 m h))
> return: a
> homogenous example: ((u l m m 3 m m))
> return: u
> homogenous example: ((u m b m 5 h v))
> return: u
> default case: ((a h b 4 5 l h) (a m b 4 3 h m) (a m m 4 5 m m) (a h m 4 4 m
> l) (u m s 4 3 m h))
> bestTree: (2 ((u m s 4 3 m h)) ((a h m 4 4 m l) (a m m 4 5 m m)) ((a m b 4 3
> h m) (a h b 4 5 l h)))
> bestAttr: 2
> homogenous example: ((u m s 4 3 m h))
> return: u
> homogenous example: ((a h m 4 4 m l) (a m m 4 5 m m))
> return: a
> homogenous example: ((a m b 4 3 h m) (a h b 4 5 l h))
> return: a
>
> As you can see above results, my code works fine in terms of the return
> values. It finds the best partition and returns appropriate values. But I
> cannot construct the given tree format.
>
> Any ideas on how to construct the tree with the given format?
> Any comment would be greatly appreciated.
>
> Thanks in advance.
>
> "Young-Jin Lee" <······@uiuc.edu> wrote in message
> ·························@vixen.cso.uiuc.edu...
>
>> Hi, I'm looking for an help implementation of decision learning tree.
>> This is my class MP, so I don't want a direct answer.
>>
>> In this MP, I'm supposed to implement pseudocode in page 537 of
>
> "Artificial
>
>> Intelligence A Morden Approach by Rusell and Norvig".
>>
>> I implemented Choose-Attribute and Majority-Value functions so that I can
>> know which attribute is the best for the given examples and attributes.
>> For example, I have the following information.
>> bestTree: (3 ((u h m 2 4 m m) (u h b 2 2 m m) (u l m 2 3 l m) (u h s 2 2 l
>> l) (u l b 2 5 h m) (u l b 2 2 v m))
>> ((u m b m 5 h v) (a h s m 4 m v) (u l m m 3 l m) (a m b m 3 m
>
> h)
>
>> (u l b m 4 l v) (u l b m 4 v l)
>> (u l s m 3 v h) (u h m m 5 v h) (u l m m 3 m m))
>> ((a h b 4 5 l h) (a m b 4 3 h m) (a m m 4 5 m m) (a h m 4 4 m
>
> l)
>
>> (u m s 4 3 m h)))
>> It says the best attribute is the third attribute in the attribute set and
>> there are three different partitions under this attribute.
>>
>> I think the next thing is calling Decision-Learning-Tree function
>> recursively, but I got stuck here. The format of decision tree is given to
>> us. The format is "([attrvalue] [attrnum] default [subtrees])" The problem
>> is the root node does not have a attrvalue and the other subnodes have the
>> attrvalue which is determined by the parent node.
>> How can one recursive function, Decision-Learning-Tree can have two
>> different attrvalue, NIL for root node and a real attrvalu for other
>> subnodes? I tried to use a global variable, but it still not easy to me.
>>
>> Any ideas on how to construct the tree with the given format?
>> Any comment would be greatly appreciated.
>>
>> Thanks in advance.
>>
>>
>>