COSC-288: Machine Learning

Project 2
Fall 2018

Due: M 10/15 W 10/17 @ 5:00 P.M.
10 points

Building upon your implementation for p1, implement k-NN and naive Bayes for nominal attributes. Also implement routines for evaluating classifiers using k-fold cross-validation.

The implementations should be general in the sense that they should work for all data sets with nominal attributes and nominal class labels. Our convention is that the last attribute of the attribute declarations is the class label.


  1. We will design and implement a class hierarchy for classifiers for this and subsequent projects. Methods common to all classifiers include

  2. Implement k-NN as the class IBk. Derive IBk from Classifier. Your implementation does not have to use a fixed-capacity min-heap, but the data structure you use to determine the k-closest neighbors must use O(k) space. The implementation of k-NN should process the command-line switch -k to let users specify the value of k. Use 3 as the default.

  3. Implement naive Bayes as the class NaiveBayes. Derive NaiveBayes from Classifier. It should use add-one smoothing for nominal attributes. Implement Estimator and derive CategoricalEstimator. The derived class must implement methods that add values to the estimator and get the probability of values.

  4. Implement the Evaluator class that evaluates the performance of any Classifier using training and testing sets or using k-fold cross-validation. Use the option -x to let users specify the number of folds, with 10 as the default. Use the option -s to let users specify a seed for the random-number generator.

  5. To help you get started, I put some class and method declarations in

    Implement two separate executables: NaiveBayes and IBk. No windows. No menus. No prompts. Just do it.

    The logic of each executable should be as follows. The user must provide a training set using the -t switch; a testing set is optional. If the user runs a learner and provides only a training set, then the program should evaluate the method on the training set using cross-validation and output the results. Naturally, the user can use the -x switch to change the default number of folds. The output should consist of the average accuracy and some measure of dispersion, such as variance, standard error, or a 95% confidence interval.

    Otherwise, if the user provides training and testing sets using the -t and -T switches, respectively, then the program should build a model from the training set, evaluate it on the testing set, and output the results. The output should consist of the accuracy.

Instructions for Submission

In a file named HONOR, please include the statement:
In accordance with the class policies and Georgetown's Honor Code,
I certify that, with the exceptions of the class resources and those
items noted below, I have neither given nor received any assistance
on this project.
Include this file in your zip file

Submit p2 exactly like you submitted p1.

Plan B

If Autolab is down, upload your zip file to Canvas.

Copyright © 2019 Mark Maloof. All Rights Reserved. This material may not be published, broadcast, rewritten, or redistributed.