Decision Trees (writing this program in java) Imagine you only ever do three thi
ID: 3742352 • Letter: D
Question
Decision Trees (writing this program in java)
Imagine you only ever do three things at the weekend: go shopping, watch a movie, or just stay in. What you do depends on three things: the weather (good or bad); how much money you have (rich or poor) and whether your parents are visiting. You say to your yourself: if my parents are visiting, we'll go to the cinema. If they're not visiting and the weather's good and I'm rich, then I'll go shopping. If they're not visiting, and the weather's good and I'm poor, then I will go to the cinema. If they're not visiting and the weather is bad and I'm rich, I'll go to the cinema. If they're not visiting and the weather is bad and I'm poor, I'll stay in.
Create a program asking whether the parents are visiting, whether the weather is good, and whether you are rich or poor. Your program should print "go to the cinema" "go shopping" or "stay in" as appropriate.
Hint: There are two possibilities for the "Parents visiting?" question, two for the "is weather good?" question, and two for the "are you rich?" question. That gives eight possible cases:
The problem can be solved by testing a lot fewer cases than 8, but if you get confused, the full 8 case solution might provide a way to understand all of the possibilities.
Truth Table for Did You Ever Have to Make Up Your Mind? Are parents visiting? Is the weather good? Are you rich? What you do y y y y y n y n y y n n n y y n y n n n y n n nExplanation / Answer
Answer:
import java.io.*;
import java.util.*;
public class ID3
{
int valuefeature;
String []featurenames;
Vector []domainnames;
class InformationPoint{
public int []features;
public informationPoint(int valuefeature) {
features = new int[valuefeature];
}
};
class TreeNode {
public double entropy;
public Vector information;
public int decompositionAttribute;
public int decompositionValue;
public TreeNode []children;
public TreeNode parent;
public TreeNode() {
information = new Vector();
}
};
TreeNode root = new TreeNode();
public int getSymbolValue(int attribute, String symbol) {
int index = domainnames[attribute].indexOf(symbol);
if (index < 0) {
domainnames[attribute].addElement(symbol);
return domainnames[attribute].size() -1;
}
return index;
}
public int []getAllValues(Vector information, int attribute) {
Vector values = new Vector();
int num = information.size();
for (int i=0; i< num; i++) {
InformationPointpoint = (informationPoint)information.elementAt(i);
String symbol =
(String)domainnames[attribute].elementAt(point.features[attribute] );
int index = values.indexOf(symbol);
if (index < 0) {
values.addElement(symbol);
}
}
int []array = new int[values.size()];
for (int i=0; i< array.length; i++) {
String symbol = (String)values.elementAt(i);
array = domainnames[attribute].indexOf(symbol);
}
values = null;
return array;
}
public Vector getSubset(Vector information, int attribute, int value) {
Vector subset = new Vector();
int num = information.size();
for (int i=0; i< num; i++) {
InformationPointpoint = (informationPoint)information.elementAt(i);
if (point.features[attribute] == value) subset.addElement(point);
}
return subset;
}
public double calculateEntropy(Vector information) {
int numinformation = information.size();
if (numinformation == 0) return 0;
int attribute = valuefeature-1;
int numvalues = domainnames[attribute].size();
double sum = 0;
for (int i=0; i< numvalues; i++) {
int count=0;
for (int j=0; j< numinformation; j++) {
InformationPointpoint = (informationPoint)information.elementAt(j);
if (point.features[attribute] == i) count++;
}
double probability = 1.*count/numinformation;
if (count > 0) sum += -probability*Math.log(probability);
}
return sum;
}
public boolean alreadyUsedToDecompose(TreeNode node, int attribute) {
if (node.children != null) {
if (node.decompositionAttribute == attribute )
return true;
}
if (node.parent == null) return false;
return alreadyUsedToDecompose(node.parent, attribute);
}
public void decomposeNode(TreeNode node) {
double bestEntropy=0;
boolean selected=false;
int selectedAttribute=0;
int numinformation = node.information.size();
int numinputfeatures = valuefeature-1;
node.entropy = calculateEntropy(node.information);
if (node.entropy == 0) return;
for (int i=0; i< numinputfeatures; i++) {
int numvalues = domainnames.size();
if ( alreadyUsedToDecompose(node, i) ) continue;
double averageentropy = 0;
for (int j=0; j< numvalues; j++) {
Vector subset = getSubset(node.information, i, j);
if (subset.size() == 0) continue;
double subentropy = calculateEntropy(subset);
averageentropy += subentropy *
subset.size();
}
averageentropy = averageentropy / numinformation; //
Taking the weighted average
if (selected == false) {
selected = true;
bestEntropy = averageentropy;
selectedAttribute = i;
} else {
if (averageentropy < bestEntropy) {
selected = true;
bestEntropy = averageentropy;
selectedAttribute = i;
}
}
}
if (selected == false) return;
int numvalues = domainnames[selectedAttribute].size();
node.decompositionAttribute = selectedAttribute;
node.children = new TreeNode [numvalues];
for (int j=0; j< numvalues; j++) {
node.children[j] = new TreeNode();
node.children[j].parent = node;
node.children[j].information = getSubset(node.information,
selectedAttribute, j);
node.children[j].decompositionValue = j;
}
for (int j=0; j< numvalues; j++) {
decomposeNode(node.children[j]);
}
node.information = null;
}
public int readinformation(String filename) throws Exception {
FileInputStream in = null;
try {
File inputFile = new File(filename);
in = new FileInputStream(inputFile);
} catch ( Exception e) {
System.err.println( "Unable to open information file: " + filename + " " + e);
return 0;
}
BufferedReader bin = new BufferedReader(new InputStreamReader(in) );
String input;
while(true) {
input = bin.readLine();
if (input == null) {
System.err.println( "No information found in the information file: " + filename +
" ");
return 0;
}
if (input.startsWith("//")) continue;
if (input.equals("")) continue;
break;
}
StringTokenizer tokenizer = new StringTokenizer(input);
valuefeature = tokenizer.countTokens();
if (valuefeature <= 1) {
System.err.println( "Read line: " + input);
System.err.println( "Could not obtain the names of features in the
line");
System.err.println( "Expecting at least one input attribute and one
output attribute");
return 0;
}
domainnames = new Vector[valuefeature];
for (int i=0; i < valuefeature; i++) domainnames = new Vector();
featurenames = new String[valuefeature];
for (int i=0; i < valuefeature; i++) {
featurenames = tokenizer.nextToken();
}
while(true) {
input = bin.readLine();
if (input == null) break;
if (input.startsWith("//")) continue;
if (input.equals("")) continue;
tokenizer = new StringTokenizer(input);
int numtokens = tokenizer.countTokens();
if (numtokens != valuefeature) {
System.err.println( "Read " + root.information.size() + " information");
System.err.println( "Last line read: " + input);
System.err.println( "Expecting " + valuefeature + " features");
return 0;
}
InformationPointpoint = new informationPoint(valuefeature);
for (int i=0; i < valuefeature; i++) {
point.features = getSymbolValue(i, tokenizer.nextToken()
);
}
root.information.addElement(point);
}
bin.close();
return 1;
}
public void printTree(TreeNode node, String tab) {
int outputattr = valuefeature-1;
if (node.children == null) {
int []values = getAllValues(node.information, outputattr );
if (values.length == 1) {
System.out.println(tab + " " + featurenames[outputattr] + " = "" +
domainnames[outputattr].elementAt(values[0]) + "";");
return;
}
System.out.print(tab + " " + featurenames[outputattr] + " = {");
for (int i=0; i < values.length; i++) {
System.out.print(""" + domainnames[outputattr].elementAt(values) + ""
");
if ( i != values.length-1 ) System.out.print( " , " );
}
System.out.println( " };");
return;
}
int numvalues = node.children.length;
for (int i=0; i < numvalues; i++) {
System.out.println(tab + "if( " +
featurenames[node.decompositionAttribute] + " == "" +
domainnames[node.decompositionAttribute].elementAt(i)
+ "") {" );
printTree(node.children, tab + " ");
if (i != numvalues-1) System.out.print(tab + "} else ");
else System.out.println(tab + "}");
}
}
public void DecisionTreeDiscover() {
decomposeNode(root);
printTree(root, "");
}
public static void main(String[] args) throws Exception {
ID3 me = new ID3();
int status = me.readinformation("c:\in.txt");
if (status <= 0) return;
me.DecisionTreeDiscover();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.