Classifying handwritten digits using PCA

Question

Classify handwritten digits using PCA. Use 200 digits for the train phase and 20 for the test.

I have no idea how PCA works as a classification method. I've learned to use it as a dimension reduction method where we subtract the original data from its mean, then we calculate the covariance matrix, eigenvalues and eigenvectors. From there, we're able to choose principal components and ignore the rest. How should I classify a bunch of handwritten digits? How to distinguish data from different classes?

Answer 1

If you plot the scores you obtained from PCA, you will see that certain classes will yield to a cluster.

Simple R script:

data <- readMat(file.path("testzip.mat"))$testzip
pca <- princomp(t(data))
plot(pca$scores)

Would yield to a plot like this:

I can't color it, because the mat file contained no outcome of a vector to a digit class. However you see at least a single cluster that helps you classifying that single class against the others (the other stuff seems like noise?).

Also Olivier Grisel (contributer to scikit-learn) answered your question on metaoptimize:

How to use PCA for classification?

He tells that it is actually an unsupervised method for dimensionality reduction, however it is possible to classify with some fancy methods:

Actually I have found another way to do "classification with PCA" in this talk by Stéphane Mallat: each class is approximated by a affine manifold with the first component as direction and the centroid as offset and new samples are classified by measuring distance to the nearest manifold with an orthogonal projection.

Talk: https://www.youtube.com/watch?v=lFJ7KdSdy0k (very interesting for CV people)

Related papers: http://www.cmap.polytechnique.fr/scattering/

But I think this is an overkill for you. If you have the class labels, you can use any classifier to fit this problem on the PCA output. If not, pick a density based clustering like DBSCAN and see if it finds the cluster you see there and use it to classify new images (e.g. by the distance from the mean of the cluster).

Answer 2

Yes, as Thomas Point out, basically PCA and related techniques are tools for doing dimensionality reduction. The idea is to fight the "curse of dimensionality" by only getting the most important information and putting mapping it into a low dimension subspace. In this subspace, you can use more simple techniques to actually classify or cluster the data.

You could you from the simple K nearest neighbors to Support Vector Machines to do the classification. For that, you would need also the labels of the data.

Let's try the simplest method (not necessarily the best one) using the kNN:

Now in order to perform the classification you will need another vector with actual labeling. Say you have 100 16x16 pixels images. Of those 100 you have 10 of the digit "0", 10 of digit "2" and so on.

Take the images and make it a vector of 1x1600 put those. Also create a 100x1 vector with the "labels". In matlab is something like:

labels = kron([0:1:9],ones(1,10))

Now apply PCA to your data (assuming each images is a column of the matrix sampleimgs - so 256x100 matrix), you can also do this with svd:

[coeff,scores]= pca(sampleimgs');

To send them onto a low dimensional space you want (say R^2) - so only choose the two first principal components:

   scatter(scores(:,1),scores(:,2))

Now you can apply K-NN on those and classify a new incoming image newimg after sending it to the same PC subspace:

 mdl = ClassificationKNN.fit(scores(1:100,[1 2]),labels);

 %get the new image:
 newimgmap = coef(:,1:2)'*newimg
 result = predict(mdl,newimgmap)

Hope it helps.

Answer 3

Ding and He (2004) have shown that dimensionality reduction via PCA and clustering via k-means are closely related. Clustering a.k.a. unsupervised learning is still not classification a.k.a. supervised learning, but as others have pointed out, clustering might help to identify groups of data points belonging to different digits.