Hints(1) for :

Lab 2: Implementing a Decision Tree Based Learning Agent in Java
http://www.cs.iastate.edu/~cs572/labs/lab2/lab2.html 

Out: Nov 11, 2002
Due: Dec 2, 2002 

ComS 572 Principles of Aritifical Intelligence
Dimitris Margaritis
Department of Computer Science
Iowa State University

TA, Jie Bao
Dept of Computer Science
Iowa State University
baojie@cs.iastate.edu
http://www.cs.iastate.edu/~baojie
Nov 11, 2002

is a Decision!

1. Problem restatement

You are required to implement the decision tree algorithm and test it on THREE datasets.

Be careful to following things:

Real values
To handle attributes of real values(nominal value, continuous value, linear value), you need to convert them into a discrete domain. One possible approach is to divide them into 2, 3 or 5 intervals according to the max and min attribute values in the dataset.
 
Missing Value
There are missing values in some datasets. You need to substitute a default values for them. A natural substitution strategy is "majority is default"
 
Dividing training set and test set
Relevance between training set and test set may damage the  truthfulness of the testing accuracy. Please split the data file into training sets and test sets RANDOMLY. An appropriate ratio for dataset size in craning and testing is 2:1
 
The algorithm
You are required to implement standard decision tree algorithm with information gain criterion. It's actually the ID3 algorithm.
For detail refer to Building Classification Models: ID3 and C4.5 and The ID3 Algorithm
 
Storage for  tree
You need to find a way to store the tree in java. Since there is no pointer in java, you may need to simulate a tree by Vector, Map or other data structures. Note that you need to define your tree Node class to store some important information (eg: parents, IsGoal, attributes...)
 
Pruning:  
Pruning is to cut redundant branch's out of the tree. For a general idea about pruning, refer to : Noise Handling in Tree Induction (Introduction to Pruning).

You are not required to implement pruning in this project, but you need to observe your result and find where may pruning be applied. To get a reference system, you can compare your result with the "laconic" (small sized tree) output of some standard decision tree package (such as Weka, see Part 4)

More details will be discussed in next help session.

2. About the dataset

UC-Irvine archive of machine learning datasets is a famous Repository for Maching Learning.

One dataset is composed by two files: name file & data file. Name file gives domains for Attributes, and data file actually is a table with Attributes as column and examples as rows. (you can open the .data file with Excel and view it as table)

For example, the Voting dataset can be understood as:

handicapped -infants: y,n	water- project- cost- sharing: y,n	adoption- of- the- budget- resolution : y,n	physician- fee- freeze: y,n	el- salvador- aid: y,n	religious- groups- in- schools : y,n	Other Attributes	ClassName :republican, democrat
n	y	n	y	y	y	.	republican
n	y	n	y	y	y	.	republican
?	y	y	?	y	y	.	democrat
n	y	y	n	?	y	.	democrat
y	y	y	n	y	y	.	democrat
n	y	y	n	y	y	.	democrat
n	y	n	y	y	y	.	democrat
n	y	n	y	y	y	.	republican
n	y	n	y	y	y	.	republican
y	y	y	n	n	n	.	democrat
n	y	n	y	y	n	.	republican
n	y	n	y	y	y	.	republican
n	y	y	n	n	n	.	democrat
y	y	y	n	n	y	.	democrat
n	y	n	y	y	y	.	republican
.	.	.	.	.	.	.	.

The three datasets:

• Congressional Voting Records Database
• 1984 United Stated Congressional Voting Records
• Classification: Republican or Democrat
• Documentation: completed
• All attributes are Boolean valued; plenty of missing values; 2 classes
• Arrhythmia Database
• Documentation: On everything
• The aim is to distinguish between the presence and absence of cardiac arrhythmia and to classify it in one of the 16 groups.
• 16 classes
• 452 examples
• 279 attributes, 206 numeric
• Some missing attribute values
• Audiology Databases
• From Baylor College
• Documentation: On everything except database statistics
• Non-standardized attributes (differs between instances)
• A standard set of attributes have been defined in terms of the original properties according to a well defined set of rules described in the documentation files.
• 70 nominally-valued attributes
• Some missing attributes

3. What to turn in

How to turn in: Suppose your files are stored in subdirectory lab2, WITHIN lab2 execute the following: /home/course/cs572/public/Utilities/turin lab2
Note: If you turnin in your root directory, all of your files - even your emails - will be submitted! 

Since many students feel they weren't clear about the grading policy and where did they lose points on lab1, this time a HARDCOPY of your lab report is required for TA to write comments. And it's better to write all your code in C5.java with input parameters:
           C5 <namesFile> <trainsetFilename> <testsetFilename>  
It will greatly simplify TA's work.

Grading policy is :

Code:60%
- A readme file for how to compile and run the program: 5%
- The code to randomly split the datasets: 5%
- Can compile and run with no errors or exceptions: 25%
- Gives results on all datasets:15% (5% for each datasets)
- Clear comments in source code: 10%

Report: 40%
- A list of your classes and functions with short description: 5%
- Printed decision trees: 5%
- Do the induced decision trees make sense given what you know about the domains we used? 5%
- Are you able to obtain any interesting insights about these two test domains by looking at the induced trees? 5%
- Do you see any places where pruning might have been useful had we implemented it? Please explain pruning first. 10%
- How do the learned trees compare to the very simple learning algorithm that simply determines the majority class in the training set, and then always guesses that class on the test set? (For this last question, compute the accuracy of this simple algorithm and compare it to the accuracy of C5.0): 10%

Example output 1(part):

adoption-of-the-budget-resolution=y       :democrat    adoption-of-the-budget-resolution=n       synfuels-corporation-cutback=y          :democrat       synfuels-corporation-cutback=n          superfund-right-to-sue=y             :democrat          superfund-right-to-sue=n             mx-missile=y                religious-groups-in-schools=y                   :democrat                religious-groups-in-schools=n                   crime=y                      : republican                   crime=n                      :democrat             mx-missile=n                : republican Incorrect test sample No: 1, 41, 64, 108, 133 (5 in total) Number of correct test results: 153 Number of test results: 158 The percentage of accuracy is: 0.9683544



Example output 2



physician-fee-freeze = y | adoption-of-the-budget-resolution = y | | anti-satellite-test-ban = y: republican (14.88/0.78) | | anti-satellite-test-ban = n | | | water-project-cost-sharing = y: democrat (4.71/0.03) | | | water-project-cost-sharing = n: republican (3.02/1.0) | adoption-of-the-budget-resolution = n: republican (85.71/2.1) physician-fee-freeze = n: democrat (170.67/1.22)  Number of Leaves : 5 Size of the tree : 9 Correctly Classified Instances 274: 98.2079 % Incorrectly Classified Instances 5: 1.7921 %

4. Related Resources

Sample decision tree programs (free and with soucrce code)

	A decision trees in Java by Frans Coenen: http://www.csc.liv.ac.uk/~frans/COMP101/AdditionalStuff/javaDecTree.html it's a good beginning for implementing decision tree
	Weak:Machine Learning Software in Java A excellent java package for Machine Learning: ID3:weka.classifiers.Id3 C4.5: weka.classifiers.j48
	MLC++: Machine Learning for C++ library:http://www.kddresearch.org/Groups/Machine-Learning/Docs/overview-summary.html Incudes two decision tree algorithms: ID3 & C4.5.
	YALE: Yet Another Learning Environment(in Java): http://yale.cs.uni-dortmund.de/javadoc/edu/udo/cs/yale/operator/learner/package-summary.html Also includes ID3 & C4.5.
	C4.5, (in C) the "classic" decision-tree tool, developed by J. R. Quinlan, (restricted distribution)
	Decision Tree Java Applet by Pierre Geurts: http://www.montefiore.ulg.ac.be/~geurts/dtapplet/dtexplication.html
	See5(Windows 98/Me/2000/XP) and C5.0(Unix) from RULEQUEST: http://www.rulequest.com/see5-info.html See5 & C5 are sophisticated data mining tools for discovering patterns that delineate categories, assembling them into classifiers, and using them to make predictions.
	The OC1 (in C) by Steven Salzberg :http://www.cs.jhu.edu/~salzberg/announce-oc1.html OC1 (Oblique Classifier 1) is a decision tree system continuous feature values; builds decision trees with linear combinations of attributes at each internal node; these trees then partition the space of examples with both oblique and axis-parallel hyperplanes
	Classification Tree in Excel, from Angshuman Saha
	YaDT: Yet another Decision Tree builder. & Efficient C4.5: http://www.di.unipi.it/~ruggieri/software.html by Salvatore Ruggieri YaDT is a new from-scratch implementation of the entropy-based tree construction algorithm; EC4.5 is a more efficient version of c4.5, which uses the best among three strategies at each node construction.
	IND, provides Gini and C4.5 style decision trees and more. Publicly available from NASA but with export restrictions.
	LMDT, builds Linear Machine Decision Trees (based on Brodley and Utgoff papers).
	ODBCMINE, analyzes ODBC databases using C4.5, and outputs simple IF..ELSE decision rules in ascii.
	PC4.5, a parallel version of C4.5 built with Persistent Linda (PLinda) system.

You can read them and find inspiration, but NEVER copy them! Write every line by yourself.