In this assignment, you are required to implement and test a decision tree building algorithm. In particular, the Iterative Dichotomiser 3 (ID3) decision tree building algo- rithm is considered^1. For more information on the ID3 algorithm, consider the following sources see the Additional Material section at the end of this document. Instructions for the practical are as follows:
- Implement the Iterative Dichotomiser 3 (ID3) decision tree building algorithm in Python. As usual, you must implement a generic algorithm. That is, your function should be able to handle any dataset presented to it in a particular format.
- Test your ID3 algorithm on the restaurant dataset presented in the prescribed book. This dataset is presented in Chapter 18 and is reproduced as follows:
- Use the decision tree generated by the ID3 algorithm to make decisions on the following sample two examples. Show the decision path that is followed through the tree. X 1 ={Alt=N o, Bar=N o, F ri=Y es, Hun=Y es, P at=F ull, P rice= $$, Rain=Y es, Res=N o, T ype=T hai, Est= 10− 30 }
X 2 ={Alt=Y es, Bar=N o, F ri=N o,
Hun=Y es, P at=F ull, P rice= $$,
Rain=Y es, Res=N o, T ype=Italian, Est= 30− 60 }
X 3 ={Alt=Y es, Bar=N o, F ri=Y es,
Hun=Y es, P at=Some, P rice= $,
Rain=N o, Res=N o, T ype=Burger, Est= 0− 10 }
(^1) The decision tree learning algorithm in the prescribed book is a variation of the ID3 algorithm
[1] T. Mitchell, Machine Learning, ser. McGraw-Hill international editions - computer
science series. McGraw-Hill Education, 1997, ch. 3. [Online]. Available: http:
//www.cs.princeton.edu/courses/archive/spr07/cos424/papers/mitchell-dectrees.pdf
[2] J. R. Quinlan, “Induction of decision trees”, Machine learning, vol. 1, no. 1, pp.
81-106, 1986. [Online]. Available:
https://wwwold.cs.umd.edu/class/fall2009/cmsc828r/PAPERS/
fulltextQuilanAshwinKumar.pdf
[3] J. W. Grzymala-Busse,“Selected algorithms of machine learning from examples”,
Fundam. Inform., vol. 18, pp. 193-207, 1993. [Online]. Available: http:
//people.eecs.ku.edu/∼jerzy/j24-sel.pdf
[4] Wikipedia, “Id3 algorithm”, https://en.wikipedia.org/wiki/ID3 algorithm.
If you can’t find these papers by following the link, simply search the title of the paper on Google Scholar. There are also a couple of good video tutorials on Youtube.
You have to write a short technical report for this assignment. Your report must be written in LATEX. In the report you will give your results as well as provide a discussion on the results. Make sure to follow the guidelines as set out in the separate questions to form a complete report.
Reports will only be handed in as digital copies, but a hard copy plagiarism statement needs to be handed in at the following week’s practical session (on the final day of the practical submission).
- Write a technical report on your finding for this assignment.
- Include your code in the digital submission as an appendix.
- All reports must be in PDF format and be named report.pdf.
- Place the software in a folder called SOFTWARE and the report in a folder called REPORT.
- Add the folders to a zip-archive and name itEAI320_prac5_studnr.zip.
- All reports and simulation software must be e-mailed [email protected] no later than 17:00 on 23 March 2018. No late submissions will be accepted.
- Use the following format for the subject header for the email: EAI 320 Prac 5 - studnr.
- Bring your plagiarism statements to the practical session on Thursday, 22 March 2018, where they will be collected.
- Submit your report online on ClickUP using the TurnItIn link.
- Do not copy! The copier and the copyee (of software and/or documentation) will receive zero for both the software and the documentation.
- For any questions or appointments email me [email protected].
- Make sure that you discuss the results that are obtained. This is a large part of writing a technical report.
Your report will be marked as follow:
- 60% will be awarded for the full implementation of the practical and the subsequent results in the report. For partially completed practicals, marks will be awarded as seen fit by the marker.Commented code allows for easier marking!
- 40% will be awarded for the overall report. This includes everything from the report structure, grammar and discussion of results. The discussion will be the bulk of the marks awarded.