<jupyter_start><jupyter_text>![alt text](http://datascience.uci.edu/wp-content/uploads/sites/2/2014/09/data_science_logo_with_image1.png 'UCI_data_science')  Goals of this Lesson- Random Projections for Dimensionality Reduction References - [Random Projections in Dimensionality Reduction](http://www.ime.unicamp.br/~wanderson/Artigos/randon_projection_kdd.pdf)- [*Dropout: A Simple Way to Prevent NNs from Overfitting](http://jmlr.org/papers/volume15/srivastava14a/srivastava14a.pdf)- [SciKit-Learn's documentation on dimensionality reduction](http://scikit-learn.org/stable/modules/decomposition.htmldecompositions) 0.  PreliminariesFirst we need to import Numpy, Pandas, MatPlotLib...<jupyter_code>from IPython.display import Image
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
import time
%matplotlib inline<jupyter_output><empty_output><jupyter_text>Again we need functions for shuffling the data and calculating classification errrors.<jupyter_code>### function for shuffling the data and labels
def shuffle_in_unison(features, labels):
    rng_state = np.random.get_state()
    np.random.shuffle(features)
    np.random.set_state(rng_state)
    np.random.shuffle(labels)
    
### calculate classification errors
# return a percentage: (number misclassified)/(total number of datapoints)
def calc_classification_error(predictions, class_labels):
    n = predictions.size
    num_of_errors = 0.
    for idx in xrange(n):
        if (predictions[idx] >= 0.5 and class_labels[idx]==0) or (predictions[idx] < 0.5 and class_labels[idx]==1):
            num_of_errors += 1
    return num_of_errors/n<jupyter_output><empty_output><jupyter_text>0.1  Load the dataset of handwritten digitsWe are going to use the [MNIST dataset](https://en.wikipedia.org/wiki/MNIST_database) throughout this session.  Let's load the data...<jupyter_code># load the 70,000 x 784 matrix
from sklearn.datasets import fetch_mldata
mnist = fetch_mldata('MNIST original')
idxs_to_keep = []
for idx in xrange(mnist.data.shape[0]): 
    if mnist.target[idx] == 0 or mnist.target[idx] == 1: idxs_to_keep.append(idx)
mnist_x, mnist_y = (mnist.data[idxs_to_keep,:]/255., mnist.target[idxs_to_keep])
shuffle_in_unison(mnist_x, mnist_y)
print "Dataset size: %d x %d"%(mnist_x.shape)

# make a train / test split
x_train, x_test = (mnist_x[:10000,:], mnist_x[10000:,:])
y_train, y_test = (mnist_y[:10000], mnist_y[10000:])

# subplot containing first image
ax1 = plt.subplot(1,2,1)
digit = mnist_x[1,:]
ax1.imshow(np.reshape(digit, (28, 28)), cmap='Greys_r')
plt.show()<jupyter_output><empty_output><jupyter_text>1 Random ProjectionsWe saw in the previous session that simply adding noise to the input of an Autoencoder improves it's performance.  Let's see how far we can stretch this idea.  Can we simply multiply our data by a *random matrix* and reduce its dimensionality while still preserving its structure?  Yes!  The answer is provided in a famous result called the **Johnson-Lindenstrauss Lemma**, for $\epsilon < 1$:$$ (1- \epsilon) || \mathbf{x}_{i} - \mathbf{x}_{j} ||^{2} \le || \mathbf{x}_{i}\mathbf{W} - \mathbf{x}_{j}\mathbf{W}  ||^{2}  \le (1 + \epsilon) || \mathbf{x}_{i} - \mathbf{x}_{j} ||^{2} \text{ where } \mathbf{W} \text{ is a random matrix. }$$  In fact Scikit-Learn has a built in function that can tell you what $\epsilon$ should be for a given dataset.<jupyter_code>from sklearn.random_projection import johnson_lindenstrauss_min_dim

johnson_lindenstrauss_min_dim(n_samples=x_train.shape[0], eps=0.9)<jupyter_output><empty_output><jupyter_text>This is a nice function if we truly care about theoretical guarantees and about preserving distances, but in practice we can just see what works empirically.  Let's next generate a random matrix...<jupyter_code># set the random number generator for reproducability
np.random.seed(49)

# define the dimensionality of the hidden rep.
n_components = 200

# Randomly initialize the Weight matrix
W = np.random.normal(size=(x_train.shape[1], n_components), scale=1./x_train.shape[1])

train_red = np.dot(x_train, W)
test_red = np.dot(x_test, W)
print "Dataset is now of size: %d x %d"%(train_red.shape)<jupyter_output><empty_output><jupyter_text>Let's run a kNN classifier on the projections...<jupyter_code>from sklearn.neighbors import KNeighborsClassifier
from sklearn.linear_model import LogisticRegression

knn = KNeighborsClassifier(n_neighbors=3)
knn.fit(x_train, y_train) 
preds = knn.predict(x_test)
knn_error_orig = calc_classification_error(preds, y_test) * 100

lr = LogisticRegression()
lr.fit(x_train, y_train) 
preds = lr.predict(x_test)
lr_error_orig = calc_classification_error(preds, y_test) * 100
knn = KNeighborsClassifier(n_neighbors=3)
knn.fit(train_red, y_train) 
preds = knn.predict(test_red)
knn_error_red = calc_classification_error(preds, y_test) * 100

lr = LogisticRegression()
lr.fit(train_red, y_train) 
preds = lr.predict(test_red)
lr_error_red = calc_classification_error(preds, y_test) * 100
plt.bar([0,1,2,3], [knn_error_orig, lr_error_orig, knn_error_red, lr_error_red], color=['r','r','b','b'], align='center')
plt.xticks([0,1,2,3], ['kNN - OS', 'Log. Reg - OS', 'kNN - RP', 'Log. Reg. - RP'])
plt.ylim([0,5.])
plt.xlabel("Classifers and Features")
plt.ylabel("Classification Error")
plt.show()<jupyter_output><empty_output><jupyter_text>STUDENT ACTIVITY (until end of session)   Subtask 1: Train an Autoencoder and PCA; Compare kNN Classifer on Compressed Representation<jupyter_code>### TO DO<jupyter_output><empty_output><jupyter_text>Subtask 2: For each model, plot classification error (y-axis) vs dimensionality of compression (x-axis).<jupyter_code>### TO DO

### Shoud see graph trend downward, with classification error decreasing as dimensionality increases.<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12044866264020708, 'fraction_numerical': 0.019499568593615187, 'mean_word_length': 5.966346153846154, 'pattern_counts': {'":': 0, '<': 35, '<?xml version=': 0, '>': 34, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '360727', 'license': 'MIT', 'n_tokens_mistral': 2150, 'n_tokens_neox': 2018, 'n_words': 515, 'path': 'Session 6 - Features_III_RandomProjections .ipynb', 'repo_name': 'dinrker/PredictiveModeling', 'size': '5795'}