1st Assignment COMPX523-22A [v2]
Heitor Murilo Gomes, Albert Bifet
March 2022
1 Overall Description
This assignment aims to implement a modified version of the k Nearest Neigh-
bours (kNN) classifier. This assignment has a value of 20% of the final score
and has two parts, each of them graded as follows:
1. Coding (10% of the final score);
2. Experimentation and Analysis (10% of the final score).
Important information:
• Deadline: See Moodle
• Code the assignment preferably using either MOA or river.
• There is no need to implement the algorithm from scratch; both MOA
and river already have implementations that can be extended 1.
• Your submission must contain a zip file with 3 files:
1. the file containing the code (.java or .py);
2. a pdf report with the experiments and analysis;
3. a README file with details about how to run the code and repro-
duce the experiments: optionally, the README file can be replaced
by a Jupyter notebook with the experiments’ execution. Notice that
a Jupyter notebook does not replace the PDF report.
Throughout this assignment, there are (Optional) questions and requests.
These do not give extra credit nor influence the final score. They are challenges
that may go beyond what was taught in the course or require more coding and
analysis efforts. In summary, you are encouraged to try them, but you are not
required to so.
1For example, you can copy the kNN class in MOA and adapt it
1
1) New Instance
2) Find the 3 nearest neighbours
3) Predict as the class label
Majority vote
Figure 1: Majority vote using k = 3 for a binary classification 2 dimensional
problem.
2 Coding
You can create a new classifier by implementing a sliding window kNN from
scratch, or you can create a copy 2 and adapt one of the existing kNN im-
plementations. However, we strongly recommend that you use the existing
implementations. Notice that your kNN adaptation must be implemented in a
way that it can be executed as a stand-alone classifier.
Standard kNN. A standard implementation of kNN for data streams main-
tains a single sliding window W with the latest N instances seen. The pre-
diction yˆ for an unlabelled instance x is the most common label among the k
closest instances (nearest neighbors) to x in W , i.e. neighbours(x, k,W ). This
process is shown in Figure 2, where all instances (red and blue circles) belong
to W .
2.1 kNN with per class windowing (kNN-cw)
Training. In contrast to the standard kNN, you are asked to maintain c win-
dows, where c corresponds to the number of class labels. Each window will
contain a maximum of w instances3. After a window reaches w instances, it
will start forgetting the oldest member of that window. Notice that this is very
similar to the standard kNN algorithm, except that the instance is stored in a
specific window corresponding to its class label during training.
Predictions. A prediction will use all the windows, i.e. {W0,W1, . . . ,Wc}.
The distance from x will be calculated in each of the windows. After obtaining
the k closest neighbours in each window, the final prediction is given by the
2You will need the original kNN implementation for the experiments, so do not override it
3This parameter is the same as the limit in MOA
2
WWG
WR
WB
kNN-cw (w=6)
Stream
kNN (w=6)
...
Figure 2: Comparison between standard sliding window kNN x sliding win-
dow kNN-cw. The parameter w determines the window size. The k parameter
is not shown in this figure.
majority vote 4 of the overall closest neighbours. The prediction is very similar
to when we had only one sliding window to store all the instances. The main
difference is that now we keep instances from the same class for longer periods.
For coding tips using MOA or river, see the Appendix.
3 Evaluation and Analysis
The results should be presented using a table format, followed by a short analy-
sis about them guided by the questions associated with each experiment. More
details are presented in the subsections for each experiment. At the end of this
section you will find more details about how to prepare, run and report your
experiments.
Evaluation framework. For all experiments, use a test-then-train evalua-
tion approach and report the final result obtained, i.e. the result obtained after
testing using all instances.
Metrics. For all experiments, report accuracy, recall (per class), and execu-
tion time5.
4majority = half of the votes cast + 1
5In MOA, the execution time can be estimated using the CPU Time measurement
3
3.1 Experiment 1: kNN-cw and other classifiers
Perform experiments using five algorithms: kNN-cw, kNN, Hoeffding Tree
and Naive Bayes; and 1 baseline algorithm: Majority Classifier. Use the de-
fault values for the hyperparameters of these algorithms.
Dataset. The dataset used in this experiment will be “GMSC”. Refer to
attached materials to obtain the “.arff” and “.csv” versions.
3.1.1 Guiding questions for the analysis of Experiment 1
These are questions that you must cover in your analysis, you can also dis-
cuss other interesting aspects that you observed. Remember that you are not
required to answer the (Optional) questions.
1. What is the best model in terms of accuracy? If we assume that correct
predictions on either class label are equally important. Is this model a
reasonable solution to the problem?
2. Assuming the minority class is more important than the majority class.
Which metric would you focus on, and which model would you choose?
3. What are the pros and cons of kNN-cw in comparison to kNN?
4. (Optional) Are there exceptional cases where kNN-cw will fail to pro-
duce accurate predictions in comparison to kNN? You can use an exam-
ple classification problem to illustrate your answer.
5. (Optional) How would you improve the run time of kNN-cw?
3.2 Experiment 2: Hyperparameter tunning
The goal of this experiment is to obtain better results using kNN and kNN-
cw. You will use different combinations of hyperparameters (varying k and
the width of the sliding window). For example, kNN with window length
= 100 and k = 5; kNN-cw with k = 100 and windows of size = 100; kNN with
window length = 1000 and k = 5; and so on.
The goal is to improve upon the results you obtained using kNN in Exper-
iment 1. Remember to report the results for all configurations that you have
tried (one row for each). There are infinite possible combinations, but you are
only asked to report 10 different configurations (5 for kNN and 5 for kNN-cw).
You are free to report more if you want.
Dataset. The dataset used in this experiment will be “GMSC”. Refer to
attached materials to obtain the “.arff” and “.csv” versions.
3.2.1 Guiding questions for the analysis of Experiment 2
These are questions that you must cover in your analysis, you can also dis-
cuss other interesting aspects that you observed. Remember that you are not
required to answer the (Optional) questions.
4
1. What is the best configuration that you obtained in terms of accuracy?
What is the best one in terms of the minority class recall? Rationalize
why the configurations were better than the others based on the seman-
tics of each hyperparameter and their values, also take into account the
evaluation metric. Example: “The best configuration was kNN using
k = X , w = Y [...], because when k was too large and the window size w
too short [...]”
2. Explain the differences between each configuration, i.e. kind of a jus-
tification for why you have tried that configuration. Example: “I tried
k = {1, 5, 10, 20}, so that I could observe the impact of a small k and a
larger k. I observed that when k is small... ”
3. What is the impact in terms of execution time of the window length w?
Tip: show at least two experiments with a large difference in their win-
dow lengths (e.g. a very small one and a large one) to support your an-
swer.
4. (Optional) One option to improve the results even further is to create an
ensemble using kNN-cw. Several ensemble algorithms are available in
both MOA and river; some of them are independent of the base learner,
such as Online Bagging (OB) or StreamingRandomPatches (SRP). Choose
one of these ensembles and try to improve the results in comparison to
a single kNN-cw. You will need to find a lightweight configuration of
kNN-cw; otherwise, it might be too slow to run.
3.3 Preparing your report
The report should present the results followed by the answers to the guiding
questions. You can add more comments or experiments that you find mean-
ingful.
Present your results. Create a table to report the results of each experiment,
such as Table 3.3.
Organize your experiment. Add meaningful identifiers to each model be-
ing tested, so that you can easily refer to them and understand what they are
without constantly looking at a list of acronyms. For example, notice how the
various executions of knn on Table 3.3 can be interpreted (k = number of neigh-
bors, w = width of the sliding window). Even though it is expected that your
identifiers are explicit, also create a list for the acronyms you are using just
to make sure there are no acronyms undefined (for example, HT = Hoeffding
Tree). You do not have to use exactly the same acronyms as in Table 3.3, but
pick something that can be easily interpreted.
Prepare your PDF report. You can use whatever you want as long as your
report is submitted as a PDF file. However, one suggestion is that you use
either markdown or LATEXto prepare your report. For LATEX, overleaf is a good
option.
5
Algorithm Accuracy Recall 0 Recall 1 Time (s)
knn(k10,w1000) 68.02 82.65 38.75 3.554754
knn-cw(k5,w1000) 68.31 78.465 47.99 3.428505
knn(k10,w1000) 68.62 78.94 47.99 3.885672
... ... ... ... ...
HT 66.74 96.045 8.14 0.140724
NB 66.656 99.98 0.01 0.07592
Table 1: Results for dataset “XYZ” using Interleaved Test-Then-Train evalua-
tion. Best results are highlighted in bold.
Executing your experiments in MOA or river. See the Appendix for sug-
gestions on how to prepare your experiments.
6