Newer
Older
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# *k*-Nearest Neighbor\n",
"\n",
"We'll implement *k*-Nearest Neighbor (*k*-NN) algorithm for this assignment. We will use the **madelon** dataset as in Programming Assignment 0. \n",
"\n",
"A skeleton of a general supervised learning model is provided in \"model.ipynb\". The functions that will be implemented there will be indicated in this notebook. \n",
"\n",
"### Assignment Goals:\n",
"In this assignment, we will:\n",
"* implement 'Euclidean' and 'Manhattan' distance metrics \n",
"* use the validation dataset to find a good value for *k*\n",
"* evaluate our model with respect to performance measures:\n",
" * accuracy, generalization error\n",
" * confusion matrix\n",
" * Receiver Operating Characteristic (ROC) curve\n",
"* try to assess if *k*-NN is suitable for the dataset\n",
"\n",
"You are not required to follow this exact template. You can change what parameters your functions take or partition the tasks across functions differently. However, make sure there are outputs and implementation for items listed in the rubric for each task. Also, indicate in code with comments which task you are attempting."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# GRADING\n",
"\n",
"You will be graded on parts that are marked with **TODO** comments. Read the comments in the code to make sure you don't miss any.\n",
"\n",
"### Mandatory for 478 & 878:\n",
"\n",
"| | Tasks | 478 | 878 |\n",
"|---|----------------------------|-----|-----|\n",
"| 1 | Implement `distance` | 15 | 15 |\n",
"| 2 | Implement `k-NN` methods | 35 | 30 |\n",
"| 5 | ROC curve analysis | 25 | 25 |\n",
"\n",
"### Mandatory for 878, bonus for 478\n",
"\n",
"| | Tasks | 478 | 878 |\n",
"|---|----------------|-----|-----|\n",
"| 4 | Optimizing *k* | 10 | 10 |\n",
"\n",
"### Bonus for 478/878\n",
"\n",
"| | Tasks | 478 | 878 |\n",
"|---|----------------|-----|-----|\n",
"| 6 | Assess suitability of *k*-NN | 10 | 10 |\n",
"\n",
"Points are broken down further below in Rubric sections. The **first** score is for 478, the **second** is for 878 students. There are a total of 100 points in this assignment and extra 20 bonus points for 478 students and 10 bonus points for 878 students."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# YOUR GRADE\n",
"\n",
"### Group Members:\n",
"\n",
"| | Tasks | Points |\n",
"|---|----------------------------|-----|\n",
"| 1 | Implement `distance` | |\n",
"| 2 | Implement `k-NN` methods | |\n",
"| 3 | Model evaluation | |\n",
"| 4 | Optimizing *k* | |\n",
"| 5 | ROC curve analysis | |\n",
"| 6 | Assess suitability of *k*-NN| |\n",
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You can use numpy for array operations and matplotlib for plotting for this assignment. Please do not add other libraries."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import numpy as np\n",
"import matplotlib.pyplot as plt"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Following code makes the Model class and relevant functions available from model.ipynb."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"%run 'model.ipynb'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## TASK 1: Implement `distance` function"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Choice of distance metric plays an important role in the performance of *k*-NN. Let's start with implementing a distance method in the \"distance\" function in **model.ipynb**. It should take two data points and the name of the metric and return a scalar value."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Rubric:\n",
"* Euclidean +7.5, +7.5\n",
"* Manhattan +7.5, +7.5"
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Test `distance`"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"x = np.array(range(100))\n",
"y = np.array(range(100, 200))\n",
"dist_euclidean = distance(x, y, 'Euclidean')\n",
"dist_manhattan = distance(x, y, 'Manhattan')\n",
"print('Euclidean distance: {}, Manhattan distance: {}'.format(dist_euclidean, dist_manhattan))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can start implementing our *k*-NN classifier. *k*-NN class inherits Model class. Use the \"distance\" function you defined above. \"fit\" method takes *k* as an argument. \"predict\" takes as input an *mxd* array containing *d*-dimensional *m* feature vectors for examples and for each input point outputs the predicted class and the ratio of positive examples in *k* nearest neighbors."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Rubric:\n",
"* correct implementation of fit method +10, +10\n",
"* correct implementation of predict method +25, +20"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"class kNN(Model):\n",
" '''\n",
" Inherits Model class. Implements the k-NN algorithm for classification.\n",
" '''\n",
" \n",
" def fit(self, training_features, training_labels, k, distance_f,**kwargs):\n",
" '''\n",
" Fit the model. This is pretty straightforward for k-NN.\n",
" Args:\n",
" training_features: ndarray\n",
" training_labels: ndarray\n",
" k: int\n",
" distance_f: function\n",
" kwargs: dict\n",
" Contains keyword arguments that will be passed to distance_f\n",
" '''\n",
" # TODO\n",
" # set self.train_features, self.train_labels, self.k, self.distance_f, self.distance_metric\n",
" \n",
" raise NotImplementedError\n",
"\n",
" return\n",
" \n",
" \n",
" def predict(self, test_features):\n",
" '''\n",
" Args:\n",
" test_features: ndarray\n",
" mxd array containing features for the points to be predicted\n",
" Returns: \n",
" mx1 array containing proportion of positive class among k nearest neighbors of each test point\n",
" # use your implementation of distance function\n",
" # distance_f(..., distance_metric)\n",
" # to find the labels of k-nearest neighbors. \n",
"\n",
" # You'll need proportion of positive examples\n",
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
" "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## TASK 3: Build and Evaluate the Model"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Rubric:\n",
"* Reasonable accuracy values +10, +5\n",
"* Reasonable confidence intervals on the error estimate +10, +10\n",
"* Reasonable confusion matrix +5, +5"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Preprocess the data files and partition the data."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# initialize the model\n",
"my_model = kNN()\n",
"# obtain features and labels from files\n",
"features, labels = preprocess(feature_file=..., label_file=...)\n",
"# get class names (unique entries in labels)\n",
"classes = np.unique(labels)\n",
"# partition the data set\n",
"val_indices, test_indices, train_indices = partition(size=..., t = 0.3, v = 0.1)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Assign a value to *k* and fit the *k*-NN model."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# pass the training features and labels to the fit method\n",
"kwargs_f = {'metric': 'Euclidean'}\n",
"my_model.fit(training_features=..., training_labels-..., k=10, distance_f=..., **kwargs_f)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Computing the confusion matrix for *k* = 10\n",
"Now that we have the true labels and the predicted ones from our model, we can build a confusion matrix and see how accurate our model is. Implement the \"conf_matrix\" function (in model.ipynb) that takes as input an array of true labels (*true*) and an array of predicted labels (*pred*). It should output a numpy.ndarray. You do not need to change the value of the threshold parameter yet."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# TODO\n",
"\n",
"# get model predictions\n",
"pred_ratios = my_model.predict(features[test_indices])\n",
"\n",
"# For now, we will consider a data point as predicted in positive class if more than 0.5 \n",
"# of its k-neighbors are positive examples.\n",
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
"threshold = 0.5\n",
"# convert predicted ratios to predicted labels\n",
"pred_labels = None\n",
"\n",
"# show the distribution of predicted and true labels in a confusion matrix\n",
"confusion = conf_matrix(...)\n",
"confusion"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Evaluate your model on the test data and report your **accuracy**. Also, calculate and report the 95% confidence interval on the generalization **error** estimate."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# TODO\n",
"# Calculate and report accuracy and generalization error with confidence interval here. Show your work in this cell.\n",
"\n",
"print('Accuracy: {}'.format(accuracy))\n",
"print('Confidence interval: {}-{}'.format(lower_bound, upper_bound))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Rubric:\n",
"* Accuracies reported with various *k* values +5, +5\n",
"* Confusion matrix for new *k* +5, +5"
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can use the validation set to come up with a *k* value that results in better performance in terms of accuracy.\n",
"\n",
"Below calculate the accuracies for different values of *k* using the validation set. Report a good *k* value and use it in the analyses that follow this section. Report confusion matrix for the new value of *k*."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# TODO\n",
"\n",
"# Change values of k. \n",
"# Calculate accuracies for the validation set.\n",
"# Report a good k value.\n",
"# Calculate the confusion matrix for new k."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## TASK 5: ROC curve analysis\n",
"* Correct implementation +25, +25"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"ROC curves are a good way to visualize sensitivity vs. 1-specificity for varying cut off points. Now, implement, in **model.ipynb**, a \"ROC\" function. \"ROC\" takes a list containing different threshold values to try and returns two arrays; one where each entry is the sensitivity at a given threshold and the other where entries are 1-specificities."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Use the *k* value you found above, if you completed TASK 4, else use *k* = 10 to plot the ROC curve for values between 0.1 and 1.0."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# TODO\n",
"# ROC curve\n",
"roc_sens, roc_spec_ = ROC(true_labels=..., preds=..., np.arange(0.1, 1.0, 0.1))\n",
"plt.plot(roc_spec_, roc_sens)\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## TASK 6: Assess suitability of *k*-NN to your dataset\n",
"* +10, +10"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Insert a cell below to write about your understanding of why *k*-NN performed well if it did or why not if it didn't. What properties of the dataset could have affected the performance of the algorithm?"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.6.4"
}
},
"nbformat": 4,
"nbformat_minor": 2
}