Practical Machine Learning With Python - Part 3¶
In part-1 and part-2, I explained various supervised learning algorithms. In this part, we will see few unsupervised learning algorithms and the popular supervised learning algorithm called Neural Networks. Check out Github repository of this series for more.
Index
-
K-nearest neighbors
K-means Clustering
Principal Component Analysis
Neural Networks
K-nearest neighbors¶
K-nearest neighbors(KNN for short) is one of the simplest Machine Learning algorithm. KNN is a supervised learning algorithm which can be used for both classification and regression. This is slightly different from the algorithms that we have seen so far. Let me explain this algorithm with an example of classification problem.
First step in KNN is to plot training data in a feature space. For simplicity, let us plot a sample training data in two dimensional space as shown below. Please note, in this example we have two possible classes-green and red.
There is no explicit training phase in KNN. Our model simply memorizes these points. KNN is a lazy learner, that is, it does not use training data to do any generalization. Given any data point in a feature space we classify that point by taking into account the class of k nearest data points. For example, if we want to classify blue point as shown in following figure- we consider k nearest data points and we assign a class by majority role.
Let us take k = 3 as shown below.
As we can see, there are two data points with green class and one data point with red class . Hence, we assign green class to new point(blue).
Just to make it concrete let us take an another example. Let us change the position of new point(blue point) as shown below.
If we take k = 5 then we get four neighbors with red class and one neighbor with green class. Hence, new point will be classified as red point.
In case of regression(when output/dependent variable is any real value), output will be an average of K nearest neighbors.
But wait, How do we decide the value for K? and How to measure the distance between data points?</i>. A small value of k means that noise will have a higher influence on the result and large value makes it computationally expensive. A rule of thumb is to set k equals to the square root of total number of data points. I will recommend to test your model for various K values. You can use cross-validation to find out best k value. For more on choosing best value of k, refer this stackoverflow thread.
There are various options available for distance metric such as euclidian or manhattan distance. Generally used metric is Euclidian distance.
Minkowski is the generalization of Euclidian and Manhattan distance. Now, let us implement KNN algorithm using scikit-learn.
Load the dataset¶
from sklearn.datasets import load_iris
dataset = load_iris()
X = dataset.data
y = dataset.target
Perform preprocessing¶
#standardize the data to make sure each feature contributes equally to the distance
from sklearn.preprocessing import StandardScaler
ss = StandardScaler()
X_processed = ss.fit_transform(X)
#split the dataset into train and test set
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X_processed, y, test_size=0.3, random_state=42)
Fit the dataset¶
from sklearn.neighbors import KNeighborsClassifier
model = KNeighborsClassifier(n_neighbors = 5, metric="minkowski", p=2) #p=2 for euclidian distance
model.fit(X_train, y_train)
model.score(X_test, y_test)
Before moving on to the next topic, let me briefly explain parametric and non-parametric models. In parametric model, we continously update parameters(finite) to learn a function which can classify new data point without requiring the training data(i.e Logistic Regression). In non-parametric model, number of parameters grows with the number of training data(i.e KNN).
K-means Clustering¶
K-means is one of the simplest unsupervised learning algorithm used for clustering problem. Clustering is a process that finds groups of similar objects. So, in clustering our goal is to group objects based on their features similarity. K-means clutering is very easy to understand, very easy to implement and computationally efficient clutering algorithm. Now, let us see how it works.
Basic idea behind K-means is, we define k centroids, that is, one for each cluster. Here, k is the hyperparameter and we should be very careful about it. Usually, you should try range of values to determine best value of k. Where do we place them initially? Common choice is to place them as fas ar possible. Now, assign each data point to the nearest centroid. Once each data point has been assigned to one of the centroids, our next step is to recalculate k new centroids. How do we do that? We do it by moving centroid(old) to the center of the data samples that were assigned to it. And how do we do find center? We find it by taking the mean of data points in a particular cluster.
K-means clutering aims to find positions $ \mu_i $, i=1,2,..,k of the clusters the minimize the distance from the data points to the cluster. Mathematically, we can write this as:
If you are curious and want to know more about K-means, check this out.
from sklearn.datasets import load_digits
from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler
digits = load_digits()
dataset = digits.data
#standardize
ss = StandardScaler()
dataset = ss.fit_transform(dataset)
model = KMeans(n_clusters= 10, init="k-means++", n_init=10)
model.fit(dataset)
model.labels_ #assigned label(cluster) to each data point
model.inertia_ #sum of distances of samples to their closest centroid
model.cluster_centers_
import matplotlib.pyplot as plt
%matplotlib inline
plt.imshow(digits.images[1], cmap='gray')
model.predict(dataset[1].reshape(1,-1)) #should be one
#lets try again
plt.imshow(digits.images[333], cmap='gray')
model.predict(dataset[333].reshape(1,-1)) #should be 2
Principal Component Analysis¶
Principal Component Analysis is a linear dimensionality reduction algorithm. Before moving forward, it's important to mention the curse of dimensionality. Curse of dimensionality refers to how certain algorithms perform poorly on high-dimensional data. High dimensionality makes clustering hard, because having lots of dimensions means that everything is far away from each other. It's hard to know what true distance means when you have so many dimensions.
Reducing the dimensions is same as reducing the features of a dataset. We can do this by feature selection or feature extraction. PCA is a feature extraction technique, that is, we project original dataset(with high-dimensionality) onto a new feature space(with low-dimensionality). We can also think of it as a data compression technique while maintaining the most relevant information. PCA aims to find the directions of maximum variance in high-dimensional data and project it onto a new subspace with fewer dimensions.
Given the input data X(d-dimensional), we want to find a projection matrix (P) such that X.W = N (n-dimensional) and please note n <= d . We construct project matrix P using eigenvectors. Eigenvectors can be calculated by decomposing a covariance matrix or we can perform singular value decomposition. One important thing to note here is that PCA is sensitive to data scale, hence we should standardize data before going through PCA. We can summarize this process as follows:
- Standardize the dataset.
- Find eigenvector and eigenvalues by decomposing a covariance matrix or use singular value decomposition.
- Sort eignevalues in descending order and select n eigenvectors corresponding to n largest eigenvalues.
- Construct the projection matrix P from eigenvectors.
- Project dataset X onto low-dimensional space by multiplying X and W
from sklearn.decomposition import PCA
import numpy as np
#lets create features
x1 = np.random.normal(size=200)
x2 = np.random.normal(size=200)
x3 = x1 + x2 #not useful since its highly correlated with other features.
X = np.c_[x1,x2,x3]
pca = PCA()
pca.fit(X)
pca.explained_variance_ #third feature is clearly useless
pca.n_components_ #still 3, because we have not specify no of components to keep in PCA() method
pca2 = PCA(n_components=2)
pca2.fit(X)
pca2.n_components_
X_processed = pca2.fit_transform(X)
X.shape
X_processed.shape
PCA is not the only Dimensionality Reduction algorithm. Check out Linear Discriminant Analysis.
Neural Networks¶
Neural Networks are very powerful supervised learning algorithms which can be used for Classification as well as Regression problems. In most cases, we have classification problem. It won't be wrong to say Neural Networks are the reason behind the hype of Machine Learning. Neural Networks or Artificial Neural Networks are also known as Universal Function Approximator. Read this chapter of neural networks and deep learning book. In this part, we will see what is neural networks, and how they work. Also, we will implement Neural Network using TensorFlow.
Neural Network is an information processing system, that is, we pass some input to the Neural Network, some processing happens and we get some output. Neural Networks are inspired from biological connection of neurons and how information processing happens in the brain. For more on biological neural networks see here and here. Very simple architecture of a neural network is shown below.
Neural Network is made up of many neurons. We can think of each neuron as a single processing unit which accepts some input and produces some output. As we can see in above figure, there are three layers-input layer, hidden layer and output layer. You might have one question-why it is called hidden? The answer is- it's called hidden because it's not visible(preceded by input layer and followed by output layer). Each edge you see in figure has some weight associated with it. We can think of it as a importance of a particular feature.
We pass input vector/matrix to the input layer then it will be multiplied by a weight matrix. Then it will be passed through an activation function which is used to introduce non-linearity into the network. If we use sigmoid activation function then input value will be squashed in between [0,1] and in case of tanh - [-1,1]. Common choices for activation functions are :
Commonly used activation function is Relu since it has come nice property such as fast to converge and it also helps in regularization. Also, SELU (Scaled Exponential Linear Unit), which recently came into the play, has started getting a lot of buzz. Check out this Github repo for implementation and comparison of SELU with other activation functions.
Now, let us dive deeper into neural networks. Suppose, we have an input vector $ {x_1,x_2,x_3} $ and let us denote hidden units with $ {h_1,h_2,h_3,h_4} $ and output units with ${o_1,o_2} $ then \begin{align} h_1 = f(W_{11} x_1 + W_{21} x_2 + W_{31} x_3) \newline h_2 = f(W_{12} x_1 + W_{22} x_2 + W_{32} x_3) \newline h_3 = f(W_{13} x_1 + W_{23} x_2 + W_{33} x_3) \newline h_4 = f(W_{14} x_1 + W_{24} x_2 + W_{34} x_3) \newline \end{align}
Here, f is the activation function. We will use RELU. These equations are pretty straight forward. Now, we have activations for hidden layer neurons, we need to find the output. In case of classification, we usually have C number of output neurons. Where C is the number of classes and each output neuron gives the probability of input belonging to a particular class. In this example, we have two classes and hence two neurons in output layer. Same way we can find activations for output layer. Now, how do we map output layer activations to the probabilities? For this, we use softmax function. Softmax function squashes K-dimensional vector of real values to K-dimensional vector of real values in range (0,1] that add up to 1. Softmax function can be written as :
Here, denominator acts as a normalizer such that output vector add up to 1. So, now we have our output. Please note, there are two pass in neural network algorithm- forward and backward. In forward pass, we calculate the output and in backward pass- we calculate the gradient of cost function with respect to the parameters of the neural network. But, how does learning work in Neural Network? We use gradient descent for learning in Neural Network and popular backpropagation algorithm to find gradients. Before that we need to define our cost function. Here, we will use cross-entropy as the cost function. We define cross-entropy cost function as:
If you remember, we update our parameters by substracting gradient of the cost function w.r.t a particular parameter multiplied by a learning rate. Here, I am not going into the details of gradient calculation but its easy to understand if you have basic knowledge of derivation and chain rule. Check this out if you are curious. Essentially, what we do is- calculate gradient of cost function with respect to each parameter. Note that, for optimization purpose we do not deal with individual weight/parameter rather we use vectors or matrices. For i.e, we represent weights of input to hidden layer as a vector. Also, I omitted bias term in above equations for simplicity purpose. Now, we will implement a vanilla neural network using TensorFlow. If you haven't used TensorFlow before than check out Github repo
#read the dataset
from tensorflow.examples.tutorials.mnist import input_data
mnist = input_data.read_data_sets("MNIST_data", one_hot=True)
#create placeholders to store input and output data
import tensorflow as tf
X = tf.placeholder(tf.float32, shape=[None, 784]) #28* 28 = 784
y = tf.placeholder(tf.float32, shape=[None, 10]) #10 classes
#create weights and bias
w1 = tf.Variable(tf.truncated_normal([784, 50], stddev=0.5))
b1 = tf.Variable(tf.ones([50]))
#for hidden to output layer
w2= tf.Variable(tf.truncated_normal([50,10], stddev=0.5))
b2= tf.Variable(tf.ones([10]))
h = tf.nn.relu(tf.matmul(X,w1)+b1)
o = tf.nn.relu(tf.matmul(h, w2)+b2)
#cost function
cost = tf.reduce_mean(tf.nn.softmax_cross_entropy_with_logits(labels = y, logits = o))
step = tf.train.GradientDescentOptimizer(0.2).minimize(cost)
#find accuracy
correct_prediction = tf.equal(tf.argmax(o,1), tf.argmax(y,1))
accuracy = tf.reduce_mean(tf.cast(correct_prediction, "float"))
sess = tf.Session()
init = tf.global_variables_initializer()
sess.run(init)
for i in range(30000): #increase the number of iterations
train_data = mnist.train.next_batch(128)
_, t_loss = sess.run([step, cost], feed_dict={X:train_data[0], y:train_data[1]})
if i%500 == 0:
acc = sess.run([accuracy], feed_dict={X:mnist.test.images, y:mnist.test.labels})
print ("Step = {}, Accuracy = {}".format(i,acc))
This was very simple neural network. Please note, we can make few changes in our implementation to get accuracy more than 95%(maybe 99%). Few tweaks to get higher accuracy are- use different optimizer(i.e Adam), use dropout(to prevent overfitting), learning rate decay(see this for more), or use convolutional neural network( CNN Tutorial ).