Mini-project 1
COMP 5/630 Spring 2021
Guidelines
Submission. Submit a single pdf document via Canvas that includes your solutions, figures, and
printouts of code. For readability, you may attach the code printouts at the end of the solutions.
Submissions may be 48 hours late with a 50% deduction. Submissions more than 48 hours after the
deadline will be given zero.
Plagiarism. We might reuse problem set questions from previous years, covered by papers and
webpages. We expect the students not to copy, refer to, or look at the solutions in preparing their
answers. We expect students to want to learn and not google for answers.
Collaboration. The homework must be done individually, except where otherwise noted in the
assignments. ’Individually’ means each student must hand in their own answers, and each student
must write their own code in the programming part of the assignment. It is acceptable, however, for
students to collaborate in figuring out answers and helping each other solve the problems. We will
be assuming that you will be taking the responsibility to make sure you personally understand the
solution to any work arising from such a collaboration.
Using other programming languages. Python is recommended. You are free to use other languages
such as Matlab or Java. We won’t be able to answer or debug programming questions, as this is not
a programming language course.
1 Data
A rich repository of small scale machine learning data is at
https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/
1.a Binary classification
The data we use for binary classification tasks the UCI a4a data.
https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/binary.html#a4a
1.b Multi-class classification
The data we use for multi-class classification tasks the UCI IRIS data. The multi-class classification method is One
vs. All (OVA).
https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/multiclass.html#iris
For all the methods, we will need you to practice and report the results of both data sets.
2 Method
We will use three methods, aka, decision tree (with two criteria to choose which attribute to split the data: entropy
and classification error), perceptron, and kNN. Note that the implementation of all these methods should be
implemented on your own.
2.a Decision Trees
Entropy and classification error
In class, we used the classification error to pick the best attribute to split the data. A different
criterion is to use Entropy. Given a random variable Y with probability distribution p(y) the
entropy H(Y ) is defined as
It can be shown that for a binary random variable Y is in {yes, no} with p(Y = yes) = θ, the entropy
It should be apparent that entropy and classification error are similar (up to a scale) and an alternate
way to select features to split is to pick one that offers the highest information gain (or reduction in
Entropy), i.e., InfoGain(X) = H(Y ) − H(Y |X)
This is the criteria for the ID3 algorithm in the Quinlan 1986 paper (in the Canvas system). Note
that a decision tree will cause overfitting easily, and normally pruning technique is used. In this
project, you don’t need to use any pruning technique for your ease. Hint: to make information gain
easier to calculate, you may wish to use this formula for conditional entropy:
2.b kNN
You need to implement kNN with two types of distance metrics. Which distance metric to use is up to you.
Remember that you can subsample your training set to reduce the neighborhood computation cost (note that you
need to compute the distance to every neighbor in the training set to obtain the top-k neighbor).
2.c Perceptron
You need to implement the perceptron algorithm (Algorithm 8.4, MLaPP Sec. 8.5.4, pp 269). This algorithm is
originally designed for binary classification, but you can use the method we talked about in class to extend it to the
multi-class classification task.
3 Evaluation
1. You can use the misclassification error to measure the prediction accuracy rate.
2. Visualize the importance of attributes. Both decision-tree and perceptron algorithms involve an
inductive bias that attributes are not equally important. Aka, disregard kNN for this subtask.
(1) Think about how to reflect the different importance of attributes using either decision-tree and
perceptron (not necessarily both, but if you present both, TA will consider it as a good plus) , and describe
it in your report.
(2) Use plots to visualize your way of thinking. You can just visualize the top 20 most important
attributes.
4 Checklist
Here is a tentative checklist of items to include in your hand-in.
• misclassification error of all three methods on UCI a4a data for binary classification.
• misclassification error of all three methods on UCI IRIS data for multi-class classification.
• Visualization of attributes importance ordering (top 20 attributes) on UCI a4a data and UCI a4a
data.