Implement the ID3 algorithm in C/C++ or Java. The program should ask the user to enter the name of the text file containing set of examples (training set) and other related data and should display the decision tree on screen as described below.
Input text file format
n //an integer representing number of attributes
A1 m1//string representing attribute 1 and an integer representing the number of attribute A1 values.
A2 m2//string representing attribute 2 and an integer representing the number of attribute A2 values.
…
An mn//string representing attribute n and an integer representing the number of attribute An values.
A1 V11 V12 … //strings representing attribute 1 and its values
A2 V21 V22 … //strings representing attribute 1 and its values.
….
An Vn1 Vn2 … //strings representing attribute 1 and its values
r// integer representing number of classes
C1// string representing first class
…
Cr// string representing last class
k// an integer representing number of examples in the training set
A1 V1 A2 V2 … An Vn Class//Example 1 in the training set; strings representing list of attributes and their values and class
…
A1 W1 A2 W2 … An Wn Class//Example k in the training set; strings representing list of attributes and their values and class
As an example, for the training set
| example | color | shape | size | class |
| 1 | red | square | big | + |
| 2 | blue | square | big | + |
| 3 | red | round | small | – |
| 4 | green | square | small | – |
| 5 | red | round | big | + |
| 6 | green | square | big | – |
The input text file should contain the following lines; without comments!
3 //an integer representing number of attributes
color 3//string representing attribute 1 and an integer representing the number of attribute A1 values.
shape 2//string representing attribute 2 and an integer representing the number of attribute A2 values.
size 2//string representing attribute 3 and an integer representing the number of attribute An values.
color red blue green //strings representing attribute 1 and its values
shape square round//strings representing attribute 2 and its values.
size big small//strings representing attribute 3 and its values.
2// integer representing number of classes
+// string representing first class
-// string representing second class
6// an integer representing number of examples in the training set
color red shape square sizebig+//Example 1 in the training set; strings representing list of attributes and their values and class
color blue shape square sizebig+//Example 2
color red shape round sizesmall-//Example 3
color green shape square sizesmall-//Example 4
color red shape round sizebig+//Example 5
color green shape square sizebig-//Example 6
Output Format
The program should output the decision tree on the screen as a list of edges of the form
node label node
For example, given the input file describes above your program should print the decision tree generated by ID3 algorithm
| color |
| size |
| – |
| + |
| + |
| – |
| red |
| green |
| blue |
| big |
| small |
as follows
color red size
color green –
color blue +
size big +
size small –
EXPERT ANSWER
