联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-21:00
  • 微信:codinghelp

您当前位置:首页 >> Java编程Java编程

日期:2021-03-03 10:16

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.


版权所有:编程辅导网 2021 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。 站长地图

python代写
微信客服:codinghelp