# 编程英语之KNN算法

School of Computer Science

The University of Adelaide

Artificial Intelligence

Assignment 2

Semester 1, 2018

due 11:55pm, Thursday 14th May 2018

# 介绍

In this assignment, you will develop several classification models to classify noisy input images into the classes square or circle, as shown in Fig. 1

Figure 1: Samples of noisy images labelled as square (left)and circle (right).

Your classification models will use the training and testing sets (that are available with this assignment) containing many image samples labelled as square or circle.  Your task is to write a Python code that can be run on a Jupyter Notebook session, which will train and validate the following classification models:

1) K Nearest neighbour (KNN) classifier [35 marks].  For the KNN classifier, you can only use standard Python libraries (e.g., numpy) in order to implement all aspects of the training and testing algorithms.  You will need to implement two functions: a) one to build a K-d tree from the training set (this function takes the training samples and labels as its parameters), and b) another to test the KNN classifier and compute the classification accuracy, where the parameters are K and the test images and labels.  Using matplotlib, plot a graph of the evolution of classification accuracy for the training and testing sets as a function of K, where K = 1 to 10.  Clearly identify the value of K, where generalisation is best.

1)k近邻(KNN)分类器[35分]。

Decision tree classifier [35 marks].  For the decision tree classifier, you can only use standard Python libraries (e.g., numpy) in order to implement all aspects of the training and testing algorithms.  Essentially you will need to implement two functions: a) one to train the decision tree using the training samples and labels plus a pre-pruning parameter indicating the minimum information content before stop splitting, and b) another to test the decision tree and compute the classification accuracy (similarly to the KNN classifier, the test function takes as one of its parameters the test images and labels and returns the classification accuracy).  Using matplotlib, plot a graph of the evolution of classification accuracy for the training and testing sets as a function of the information content, where information content = 0 to 0.5 bits.  Clearly identify the value of information content, where generalisation is best.

2) Convolutional neural network (CNN) classifier [20 marks]. For the convolutional neural network, you are allowed to use Keras using TensorFlow backend, similar to the example shown in the code provided.  The CNN structure is the lenet structure used in lecture.  Using matplotlib, please plot a graph of the evolution of accuracy for the training and testing sets as a function of the number of epochs, where the max number of epochs is 200.  Clearly identify the value of information content, where generalisation is best.

A sample code that trains and tests a multi-layer perceptron classifier that can run on a Jupyter Notebook session is provided, and it is expected that the submitted code can run on a Jupyter Notebook session in a similar manner.  A held-out test set will be used to test the generalisation of the implemented classification models, but this held-out set will only be available after the assignment deadline – please note that this held-out set will contain samples obtained from the same distributions used to generate the training and testing sets.

held-out测试集将用于测试实现的分类模型的概括,但这held-out集在作业的最后期限之后提供,请注意,这个held-out集将包含获从被用于生成训练和测试的集合的相同的分布中获得的样本。

You must write the program yourself in Python, and the code must be a single file that can run on a Jupyter Notebook session (file type .ipynb).   You will only get marks for the parts that you implemented yourself.  If you use a library package or language function call for training or testing a KNN or a Decision Tree classifier, then you will be limited to 50% of the available marks (noting that this assignment is a hurdle for the course). If there is evidence you have simply copied code from the web, you will be awarded no marks and referred for plagiarism

# Submission

You must submit, by the due date, two files:

1. ipynb file containing your code with the three classifiers and all implementations described above

ipynb 文件包含你的三个分类器和以上描述的所有实现代码

2. pdf file with a short written report detailing your implementation in no more than 1 page, and the following results:

pdf文件，一个简短的书面报告，在不超过1页的情况下详细说明你的实现，和以下结果:

a) The training and testing accuracies at the best generalisation operating point for each type of classifier, using a table [5 marks]: 【通过表最好概括每种类型分类器训练和测试精度工作点】

Training Accuracy

Testing Accuracy

K=1 NN

K=10 NN

DT (IC = 0 bits)

DT (IC = 0.5 bits)

CNN

b) Running time for training and testing algorithms accuracies of each type of classifier, using a table [5 marks]: 通过表记录训练和测试算法的每一种分类器的精度

Training Time

Testing Time

K=1 NN

K=10 NN

DT (IC = 0 bits)

DT (IC = 0.5 bits)

CNN

c) Bonus question: How can the classification accuracy of the decision tree classifier be improved?  Please implement your idea (hint: dimensionality reduction) [10 marks].附加问题，如何提高决策树分类器的精度？请实现你的想法（提示，维度减少）。，

# Total number of marks: 100 + 10 bonus marks

This assignment is due 11.55pm on Thursday 14th May, 2018. If your submission is late, the maximum mark you can obtain will be reduced by 25% per day (or part thereof) past the due date or any extension you are granted.

This assignment relates to the following ACS CBOK areas: abstraction, design, hardware and software, data and information, HCI and programming.

80 篇文章30 人订阅

0 条评论

## 相关文章

8510

21330

17150

12410

38050

### 平方根的C语言实现(三) ——最终程序实现

了解了浮点数的存储以及手算平方根的原理，我们可以考虑程序实现了。 　　先实现一个64位整数的平方根，根据之前的手算平方根，程序也不是那么难写了。 #incl...

26080

37840

31120

### 【致敬周杰伦】基于TensorFlow让机器生成周董的歌词（附源码）

? 周杰伦 深深地 影响了我们 一代人 这句话 不足为过 前言 今日推文将介绍如何使用TensorFlow一步步来搭建一个序列建模的应用——机器创作歌词，训练...

1.8K50

367100