Tell me more ×
Signal Processing Stack Exchange is a question and answer site for practitioners of the art and science of signal, image and video processing. It's 100% free, no registration required.
up vote 3 down vote favorite

We're supposed to use KNN (K Nearest Neighbor) method for different values of K to classify a handwritten digit data set.

The problem is, this is the first time I want to do a project like that in Matlab. Could someone please explain the normal steps I should do for such problem? What values of K should I use? I read some articles on KNN method and have a rough idea about how the method works but I need help to do this and to be able to go through the following problem we should do after this.

share|improve this question

1 Answer

up vote 4 down vote accepted

The k-NN algorithm all by itself is very simple, and can be used on vectors of any dimensionality to classify them. Let me write it down here for the sake of answer completeness:

  • store all your vectors from the training set
  • store the class of each vector together with them
  • when a new, unclassified, vector arrives, compare it to all the vectors from the training set
  • select the $k$ neighbours that have the smallest distance to the new neighbour
  • the class assigned to the new vector is the most common class among those $k$ closest vectors

Now, that said, the value of $k$ you choose depends greatly on the size of your training set. E.g. if you have a training set of size $100$, and set $k=100$, the result will always be the same, equal to the most frequent class in your training set. If you set $k=1$, the new vector will be classified as the geometrically closest vector (Euclidean distance) every time.

If you're just supposed to present the results for different $k$ for the sake of discussion and learning, I suggest you start from $k=1$ and test for all the $k$'s sequentially: it will make a nice graph and a nice analysis. Maybe you can skip the even values of $k$ (for $k=2$, if you get two different classes as the closest, you're unable to make a decision).

What's really important is how are you going to shape your descriptor vectors. Each component in your descriptor vector is a feature you describe numerically which should be able to help you make a decision. You also have the curse of dimensionality to worry about: more components your vector has, slower the decision making process is.

You have two approaches here:

  • Decide carefully on features that are confirmed to be good at the task (do some research), and limit yourself to a certain number.
  • Work with features you think would be good, but don't worry too much about how good they are. Then, when you have a big number of features, use a method like Principal Component Analysis (PCA) or Fisher's linear discriminant (FLD) to reduce the dimensionality of your descriptor vectors before the k-NN

Lastly, let me give you some ideas about features you might want to use to form your feature vectors. I'm not guaranteeing for any of them, I'm just writing ideas off the top of my head:

  • Down-sample (shrink) your sample images to $3 \times 3$ or $3 \times 4$ pixel black and white images, and take the 0/1 values of all the 9 or 12 pixels as features. You might want to do a morphological thining or get the skeleton of the pen stroke before you shrink your images.

  • Instead of taking each pixel from a down-sampled image, you could take only the count of background/foreground pixels in each row and column in the downsampled image, making for a total of 6 or 7 non-binary features as opposed to 9 or 12 binary ones.

  • Count the number of holes in your (binarized) image. By "hole", I mean a connected component of background pixels not connected to the image border.

  • Take a simple measure such as describing the elongation of the object, e.g. the horizontal distance between two horizontally furthest pixels divided by the vertical distance between two vertically furthest pixels.

  • Use the Hu set of invariant image moments (wikipedia, article) It's very old work, but I've used them while making a letter-recognition project during my studies, and for simple uses such as this they can still be helpfull.

share|improve this answer
1  
A very informative answer, thank you for the time and effort you put into it. – Gigili Oct 27 '12 at 14:41
nice answer, i wonder if you can comment on using k-nn as number of classes moves towards number of training vectors? – geometrikal Oct 27 '12 at 21:40
1  
@geometrikal In the question, evaluation for different values of K is required. The parameter you want to vary (i.e. number of classes) is constant, there are always 10 digits. If it did vary and increase (e.g. through recognition of letters towards recognition of Chinese characters), you would have to use a larger training set. If the training set is not small enough, generalization powers of the trained system are low (i.e. it only works good on the exact samples it trained on) -- and overfitting (SO question) happens – penelope Oct 28 '12 at 12:22
Sorry for being late, but I don't understand this: Each time I change the value of K, do I need to change the formula that we use for k=1? So Euclidean distance doesn't work for $k\geq 2$? – Gigili Oct 28 '12 at 20:22
@Gigili Euclidean distance (or any other measure you choose, e.g. you can take Manhattan - L1 if you want) works for any value of $k$. You just take the $k$ closest distances, and examine their class, and the most frequent class is the answer (if $k=5$ and classes are $1,2,1,4,1$, the answer is class $1$. The problem comes for $k=2$: it's easy to have a tie, i.e. two closest samples were from different classes, so you don't know how to decide. – penelope Oct 28 '12 at 22:33
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.