<jupyter_start><jupyter_text>SML-17 Workshop 2: 2b Evaluation of classifiers  This week we'll be using the *SPAM base* dataset from the UCI machine learning dataset repository. This dataset comprises a few thousand emails that have been annotated as being spam or not, and the several features have been created from the email text (e.g., presence of certain important words and characters, too many CAPITALS etc.) Note that for many practical applications defining the features is one of the hardest and most important steps. Thankfully this has already been done for us, so we can deploy and evaluate our machine learning algorithms directly. Please see http://archive.ics.uci.edu/ml/datasets/Spambase for a full description of the dataset and feature definitions. Please follow the instructions from the previous lab for importing numpy etc, e.g.,<jupyter_code>%pylab inline
import numpy as np
import matplotlib.pyplot as plt<jupyter_output>Populating the interactive namespace from numpy and matplotlib<jupyter_text>Loading the SPAM data The first step is to load the data, which we'll download fromhttp://archive.ics.uci.edu/ml/machine-learning-databases/spambase/spambase.data<jupyter_code># download the datafile

import sys 
if sys.version_info[0] >= 3:
    from urllib.request import urlretrieve
else:
    from urllib import urlretrieve

#url = "https://staffwww.dcs.shef.ac.uk/people/T.Cohn/campus_only/mlai13/spambase.data.data"
url = "http://archive.ics.uci.edu/ml/machine-learning-databases/spambase/spambase.data"
urlretrieve(url, 'spambase.data.data')


# load the CSV file as an array
Xandt = np.loadtxt('spambase.data.data', delimiter=',')
# randomly shuffle the rows, so as to remove any order bias 
np.random.shuffle(Xandt)

# the last column are the response labels (targets), 0 = not spam, 1 = spam
# remap into -1 and +1 and take only the first 500 examples
t = Xandt[:500,-1] * 2 - 1
# and the remaining columns are the data
X = Xandt[:500,:-1]

print("Loaded", X.shape, "data points, and", t.shape, "labels,",  t.min() , t.max())<jupyter_output>Loaded (500, 57) data points, and (500,) labels, -1.0 1.0<jupyter_text>The data has many different types of features, operating on different ranges and with overall very different distributions. Therefore, it is important to standardise each feature. Also, assumptions about the distributions of the input features are central to proofs of the generalisation bounds of several machine learning algorithms.Inspect the minimum, maximum, mean and standard deviation for each column, using `np.mean` and `np.std`. Note that you'll need to supply an axis if you're just interested in columns, e.g.,<jupyter_code>tmp = np.mean(X, 0)
print(tmp)
print('Num of features : ' , len(tmp))<jupyter_output>[  9.42800000e-02   1.95880000e-01   2.45160000e-01   1.02960000e-01
   3.52620000e-01   9.27400000e-02   1.06260000e-01   1.05520000e-01
   8.64200000e-02   2.55020000e-01   6.41800000e-02   5.12120000e-01
   1.03400000e-01   4.53200000e-02   5.36000000e-02   2.30900000e-01
   1.71320000e-01   1.83580000e-01   1.64204000e+00   9.26600000e-02
   7.88040000e-01   1.11720000e-01   7.70800000e-02   1.18020000e-01
   6.91400000e-01   2.94920000e-01   7.35640000e-01   1.39220000e-01
   7.10400000e-02   1.19480000e-01   6.06000000e-02   5.40000000e-02
   1.43780000e-01   5.40000000e-02   1.44020000e-01   9.03800000e-02
   1.54980000e-01   2.63000000e-02   1.05000000e-01   7.77800000e-02
   4.88800000e-02   5.91000000e-02   4.00800000e-02   5.75800000e-02
   3.51980000e-01   2.09920000e-01   3.12000000e-03   3.90200000e-02
   2.57700000e-02   1.72592000e-01   1.36400000e-02   2.48130000e-01
   7.16240000e-02   4.71880000e-02   4.35990800e+00   6.45600000e+01
   2.65692000e+02]
Num of features[...]<jupyter_text>Note that the last three features have mean orders of magnitude greater than the other features. (Take a look at their definitions.) Thus, we will standardise all features to have mean 0 and standard deviation 1.<jupyter_code>X = (X - np.mean(X, 0)) / np.std(X, 0)<jupyter_output><empty_output><jupyter_text>Note that in previous labs we've plotted the data to get a feeling for how easily the data might be modelled, e.g., if it's linearly separable or requires polynomial basis functions etc. This technique is fine for data with 1 or 2 dimensions, but isn't so straight-forward for 57 dimensional data. (Note that dimensionality reduction methods, such as PCA, can be used to find the most important dimensions for viewing or exploiting in other learning algorithms.).   K-nearest neighbour classifier To mix things up, for this session we will use a k-NN classifier. This classifier is incredibly simple: for each test point find the closest few ($k$) points in the training sets and return the majority label from these points. We will compare the setting of $k$, to try and find the *best* classifier. Let's start by defining a function *euclidean* to calculate the euclidean distance, $d(\mathbf{x}, \mathbf{z}) = \sqrt{(\mathbf{x} - \mathbf{z})^T (\mathbf{x} - \mathbf{z})}$.<jupyter_code>def euclidean(x, z):
    d = x - z
    if len(d.shape) > 1 and d.shape[1] > 1:
        return np.sqrt(np.diag(np.dot(d, d.T)))
    else:
        return np.sqrt(np.dot(d, d))<jupyter_output><empty_output><jupyter_text>Next, define a function to find nearby training points for a given test point under the euclidean distance. You may want to use `np.argsort` which returns the sort order (as an array indices) for an input array.<jupyter_code>def neighbours(x, train_x, k):
    dists = euclidean(train_x, x)
    return np.argsort(dists)[:k]<jupyter_output><empty_output><jupyter_text>Note that this returns the indices of the training points, which can be used to look up the label. Now define the *k-NN* prediction algorithm, which processes each test point and finds the majority class of its neighbours in the training set.<jupyter_code>def knn(test_x, train_x, train_t, k):
    predict = np.zeros(test_x.shape[0])
    for i in range(test_x.shape[0]):
        ns = neighbours(train_x, test_x[i], k)
        predict[i] = np.sign(np.sum(train_t[ns]))
    return predict<jupyter_output><empty_output><jupyter_text>Heldout evaluation We have a large dataset of 500 examples. If we were to use all of these for training, we would have nothing left with which to evaluate the *generalisation error*. Recall that models often *overfit* the training sample, and therefore their performance on this set is often misleading: we have no way of telling if this is due to modelling the true problem or just fitting noise and other idiosyncracies of the training sample. To illustrate, compute the *training error* of the approach with a few different values of $k$, `[1,3,9,15,33,77]`. We'll later see if other evaluation methods lead to different conclusions.<jupyter_code>for k in [1,3,9,15,33,77]:
    # IMPLEMENT ME to compute the training error using each k<jupyter_output>1-nn 0.0
3-nn 0.09
9-nn 0.126
15-nn 0.122
33-nn 0.148
77-nn 0.212<jupyter_text>What is going on? Which value of k is best?  Attempt 1: fixed validation set Now we'll try evaluating on *heldout validation* data. This has been excluded from training, so the model cannot *overfit*. Instead this serves as a fresh data sample, which reflects the intended usage of the classifier in a live scenario (i.e., processing new emails as they arrive in your inbox).One of the easiest methods is to slice the data into two parts. We'll half for training and half for testing. Note that these numbers are fairly arbitrary, but we do want enough test data to get a reliable error estimate.<jupyter_code>N = X.shape[0]
cut = int(N/2)
Xtrain = X[:cut,:]
ttrain = t[:cut]
Xtest = X[cut:,:]
ttest = t[cut:]
print("There are", Xtrain.shape, "training samples, and", Xtest.shape, "heldout test samples")
print("Test split: for class label 1: ", np.sum(ttest ==1), "and class label -1", np.sum(ttest ==-1))
print("Train split: for class label 1: ", np.sum(ttrain ==1), "and class label -1", np.sum(ttrain ==-1))<jupyter_output>Test split: for class label 1:  100 and class label -1 150
Train split: for class label 1:  96 and class label -1 154<jupyter_text>Now your job is to apply $k$-NN on this data for the various values of $k$, and evaluate their training and heldout error.<jupyter_code>for k in [1,3,9,15,33,77]:
    # IMPLEMENT ME to compute both training and heldout errors using each k<jupyter_output>1-nn training error 0.0 heldout error 0.2
3-nn training error 0.108 heldout error 0.176
9-nn training error 0.132 heldout error 0.168
15-nn training error 0.128 heldout error 0.188
33-nn training error 0.192 heldout error 0.208
77-nn training error 0.284 heldout error 0.304<jupyter_text>Is the heldout error similar to the training error, or do you notice consistent differences?  Can you explain why? What classifier might you select now, and does this match your earlier choice? Good going. We now have a decent spam classifier, similar to the ones in Google and other email providers (which are trained on *much* more data). You could fairly easily take this approach and the feature definitions and plug this into your own email inbox to classify incoming mails.  Note that scaling this up to the full dataset would require a bit of engineering (or patience!), but otherwise would be straightforward.  Attempt 2: Leave-one-out cross validation Another validation method is *cross-validation*, which is particularly suitable when you have only a small amount of data. This technique divides the data into parts, called *folds*. Then each fold is used for evaluation, and the model is trained on all other folds. This is repeated, such that we have heldout predictions for the entire dataset.The leave-one-out method is the most extreme version of cross-validation, and defines each fold as a single data-point. Implement k-NN to work using the leave-one-out method. This only requires a small change from the `knn()` method in order exclude the current point from consideration in the inner loop. Hint: start by taking the $k+1$ nearest neighbours, and then correct the result.<jupyter_code>def knn_LOO(x, t, k):
    predict = np.zeros(x.shape[0])
    for i in range(x.shape[0]):
        # IMPLEMENT ME to find the label of each sample using leave one out approach
    return predict<jupyter_output><empty_output><jupyter_text>Try this out for a few values of k, and compare their error rates. How do these values compare to your results from using a fixed validation set? Are they more reliable, and would you expect the cross-validation error to be higher or lower?<jupyter_code>for k in [1,3,9,15,33,77]:
    print('%d-nn' % k, 
          'LOO error', np.sum(knn_LOO(X, t, k) != t) / float(X.shape[0]))<jupyter_output>1-nn LOO error 0.158
3-nn LOO error 0.156
9-nn LOO error 0.148
15-nn LOO error 0.146
33-nn LOO error 0.158
77-nn LOO error 0.218<jupyter_text>Error types and ROC analysis Spam classification is an interesting test case. Consider the impact on an email user of various errors:1. misclassifying a spam email as good 1. misclassifying a good email as spam We need to balance annoyance (1) with missing potentially important information (2). These two errors are referred to as Type I and Type II errors, and are treated uniformly when measuring accuracy (and 0/1 loss). In this case it is more informative to evaluate the outputs by counting each of the four categories: true positives (true spam which was classified as spam), false positives (good classified as spam), true negatives (good classified as good), and false negatives (spam classified as good).<jupyter_code>pred = knn_LOO(X, t, 9)
print('true positives ', np.sum(t[pred == 1] == 1))
print('false positives', # IMPLEMENT ME
print('true negatives ', # IMPLEMENT ME
print('false negatives', # IMPLEMENT ME<jupyter_output>true positives  154
false positives 32
true negatives  272
false negatives 42<jupyter_text>This shows that the data are skewed, i.e. there are more negatives than positives. Are the numbers of the two types of error are closely balanced? The ROC curve gives a better view of the compromise between the two error types. This graph shows the relationship between the *false positive rate* and *true positive rate*. Each point on the curve represents a different classifier. In our case we can vary the value of k, recording the FPR and TPR at each point. Randomly guessing will give us a straight line in ROC space, and we seek to do better by being above and left (higher TPR for a given FPR; lower FPR for a given TPR). For a thorough description please read the wikipedia page on ROC analysis http://en.wikipedia.org/wiki/Receiver_operating_characteristic<jupyter_code>fprs = []
tprs = []

for k in [1,2,3,5,9,15,33,77]:
    pred = knn_LOO(X, t, k)
    
    tp = np.sum(t[pred==1] == 1)
    fp = np.sum(t[pred==1] == -1)
    tn = np.sum(t[pred==-1] == -1)
    fn = np.sum(t[pred==-1] == 1)
    
    # now compute the TPR and FPR
    fpr = fp / float(fp + tn)
    tpr = tp / float(tp + fn)
    
    
    fprs.append(fpr)
    tprs.append(tpr)

plot(fprs, tprs, 'r*')
xlabel('FPR')
ylabel('TPR')<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.08652385293223944, 'fraction_numerical': 0.0685202066241264, 'mean_word_length': 4.226280269948393, 'pattern_counts': {'":': 0, '<': 49, '<?xml version=': 0, '>': 52, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 2, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '14', 'dir': 'jupyter-structured-clean-dedup', 'id': '299621', 'license': 'MIT', 'n_tokens_mistral': 4643, 'n_tokens_neox': 4018, 'n_words': 1734, 'path': '1_KNN_CrossHalidation_LeaveOneOut_HeldOut/notebook/2b_performance_evaluation.ipynb', 'repo_name': 'inverthermit/machine-learning-playboard', 'size': '13164'}