1 Wine Quality Prediction with 1NN (K-d Tree)

Wine experts evaluate the quality of wine based on sensory data. We could also collect the features of wine from objective tests, thus the objective features could be used to predict the expert’s judgement, which is the quality rating of the wine. This could be formed as a supervised learning problem with the objective features as the data features and wine quality rating as the data labels.

In this assignment, we provide objective features obtained from physicochemical statistics for each white wine sample and its corresponding rating provided by wine experts.  You are expect to implement k-d tree (KDT), and use the training set to train your k-d tree, then provide wine quality prediction on the test set by searching the tree.

Wine quality rating is measured in the range of 0-9.  In our dataset, we only keep the samples for quality ratings 5, 6 and 7. The 11 objective features are listed as follows [1]:

• f acid: fixed acidity

• v acid: volatile acidity

• c acid: citric acid

• res sugar: residual sugar

• chlorides: chlorides

• fs dioxide: free sulfur dioxide

• ts dioxide: total sulfur dioxide

• density: density

• pH: pH

Note: Sorting is not necessary in some cases depending on your implementation. Please figure out whether your code needs to sort the number first. Also, if you compute the median by yourself, when there’s an even number of points, say [1,2,3,4], the median is 2.5.

1.2 Deliverable

Write your k-d tree program in Python 3.6.9 in a file called nn kdtree .py. Your program must be able to run as follows:

$ python nn_kdtree .py  [train]  [test]  [dimension]

The inputs/options to the program are as follows:

•  [train] specifies the path to a set of the training data file.

•  [test] specifies the path to a set of testing data file.

•  [dimension] is used to decide which dimension to start the comparison.  (Algo- rithm 1).

Given the inputs, your program must construct a k-d tree (following the prescribed algorithms) using the training data, then predict the quality rating of each of the wine sample in the testing data. Your program must then print to standard output (i.e., the command prompt) the list of predicted wine quality ratings, vertically based on the order in which the testing cases appear in [test].

1.3 Python libraries

You are allowed to use the Python standard library to write your k-d tree learning program (see https://docs.python.org/3/library/ for the components that make up the Python v3.6.9 standard library).  In addition to the standard library, you are allowed to use NumPy and Pandas. Note that the marking program will not be able to run your program to completion if other third-party libraries are used.  You are NOT

allowed to use implemented tree structures from any Python package, otherwise the mark will be set to 0.

1.4 Submission

You must submit your program files on Gradescope. Please use the course code 6ZWNXV to enrol into the course.  Instructions on accessing Gradescope and submitting assign-

ments are provided at https://help.gradescope.com/article/5d3ifaeqi4-student-canvas. For undergraduates, please submit your k-d tree program (nn kdtree .py) to Assign-

ment 2 - UG. If there are any questions or issues with Gradescope, please contact Ankit Yadav via email at [email protected].

1.5 Expected run time

Your program must be able to terminate within 600 seconds on the sample data given.

1.6 Debugging Suggestions

Step-by-step debugging by checking intermediate values/results will help you to identify the problems of your code. This function is enabled by most of the Python IDE. If not in your case, you could also print the intermediate values out.  You could use sample data or create data in the same format for debugging.

1.7 Assessment

I will compile and run your code on several test problems.  If it passes all tests, you will get 15% (undergrads) or 12% (postgrads) of the overall course mark. For under- graduates, bonus marks of 3% will be awarded if Section 2 is completed correctly.

There will be no further manual inspection/grading of your program to award marks on the basis of coding style, commenting or “amount”of code written.

1.8 Using other source code

You may not use other source code for this assignment.  All submitted code must be your own work written from scratch. Only by writing the solution yourself will you fully understand the concept.

1.9 Due date and late submission policy

This assignment is due by 11:59pm Wednesday 3 May 2023. 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.

2.1 Deliverables

Write your random forest program in Python 3.6.9 in a file called nn kdforest .py. Your program must be able to run as follows:

$ python nn_kdforest .py  [train]  [test]  [random_seed]  [d_list]

The inputs/options to the program are as follows:

•  [train] specifies the path to a set of training data file.

•  [test] specifies the path to a set of testing data file.

•  [random_seed] is the seed value generate random values.

•  [d_list] is a list of depth values (In Algorithm 2 n trees==len(d list)).

Given the inputs, your program must learn a random forest (following the prescribed algorithms) using the training data, then predict the quality rating of each wine sample in the testing data.  Your program must then print to standard output (i.e., the command prompt) the list of predicted wine quality ratings, vertically based on the order in which the testing cases appear in [test].