Unfortunately, there is no "best" distance, as the goodness of such parameters always depends on data peculiarities.

However, you might be interested in the so-called tangent distance proposed by Simard et al., which tries to capture invariances with respect to some pattern transformations you expect the data to undergo. In case of OCR, this could be slight rotations, scalings etc.

Unfortunately, the tangent distance is not necessarily a metric. For a simple KNN, it might nevertheless prove valuable.

The original paper "Transformation Invariance in Pattern Recognition – Tangent Distance and Tangent Propagation" about this very distance measure is available on the net. Other nice papers on this topic can be easily found as well.

Moreover, here's already some code for a tangent distance implementation provided by D. Keysers:

http://www-i6.informatik.rwth-aachen.de/~keysers/td/

Unfortunately, there is no "best" distance, as the goodness of such parameters always depends on data peculiarities.

However, you might be interested in the so-called tangent distance proposed by Simard et al., which tries to capture invariances with respect to some pattern transformations you expect the data to undergo. In case of OCR, this could be slight rotations, scalings etc.

Unfortunately, the tangent distance is not necessarily a metric. For a simple KNN, it might nevertheless prove valuable.

The original paper "Transformation Invariance in Pattern Recognition – Tangent Distance and Tangent Propagation" about this very distance measure is available on the net. Other nice papers on this topic can be easily found as well.

Moreover, here's already some code for a tangent distance implementation provided by D. Keysers:

http://www-i6.informatik.rwth-aachen.de/~keysers/td/

Actually, i could find any significant differences between the distance metrics.

But, i found the manhattan metric slightly more effective, in producing successful results. (I have used knn on palmprint images..)

I agree with Michael Kemmler when he said that "there is no 'best' distance, as the goodness of such parameters always depends on data peculiarities".

However, I would rephrase it: there is no 'best' distance, because the distance fundamentally depends on the form of data representation you choose, especially considering various structural representations. That was one of the driving motivations for me in the development of one 'universal' form of representation (ETS).

But even if you stick with the vector representation, because any handwritten character data is highly structural *intrinsically*, any numeric metric will not work optimally for such data. Of course, given a relatively small number of classes (10), you can always hack something. ;--)

What Michael and Lev are commenting is the so-called No Free Lunch theorem. This applies for classification methods but as well for distance functions. You can find a brief description of this theorem in Duda et al. 2002.

Moreover being the distance functions related with geometry in the feature space, one has to take into consideration the so-called 'curse of dimensionality', i.e. geometrical properties depend on the dimensionality of the space.

All in all the best is to take different distance functions and test them with your particular data set. For the selection I would select them 1) following your intuitive understanding of the functions, 2) taking the ones used in the State of the Art in your particular application field, and 3) upon your personal preferences.

Thank you Aureli, yes I learned about the no free lunch theorem in several of our classes: Model Thinking, Machine Learning and Web Intelligence Big Data. The theorem states: Unless you know something about a problem being solved no algorithm or heuristic being used performs better than any other. Euclidean is the most popular of metrics but there are others than can implemented in Python for example to get interesting results as well. However, in this case I am referring to hand written digit recognition, and I am trying to determine what the best value of K would be to gain maximum accuracy with this lazy algorithm--based upon instance learning--thus, we do know something about the data. Thanks again for all the input as I am learning more too.

The "best" distance will vary with the type of images you have and the types of features you've extracted from them, as implied by Michael.

I'd remove redundancy from your feature vectors with a feature selection algorithm, then try several distances, saving the one that is best.

I believe that in OCR tasks like this, the distance measure can be less significant after a good normalization method: if you normalize handwritten letters/numbers into for example a 100x200 rectangle, then you detect the ends and intersections of strokes, and store only the location of these feature points (maybe some other ones as well), you can characterize the digits with only these locations. During classification, these locations have to be matched to the training data. At the first glance, I would suggest euclidean distance, or maybe the comparison in a strongly quantized polar coordinate system...

Since characters are often broken, I have my doubts about that method.

As an aside what I recently learned from getting 50 recent textbooks on the subjects of AI/ML and clusters whhich I learned in school but here is more context some of what I learned: Not only can people use bayes or naive bayes rule to class conditional densities b ut the actual non parametric application of K nearest neighbor IS equivalent to Bayes rule and in math terms it states theta = the integration of v(x) p(x)dx where theta is the probability approximated by the proportion of sample falling within V. If k is the number of samples out of a total of n falling within v (k is a function of x) then theta is equivalent to k/n p(x) is just the probability density function

it is equal to a partial differential equation which in plain language just means it has multiple variables being looked at in the calculus--rate of change in ML we use partial differential equations often in such things as gradient descent which are non-linear now there is also a decision rule for K -nearest neighbor too not covered in class or on facebook groups

it is based upon the prior probabilities like Bayes and extends from the density estimate in reality the density estimate is not a true density because the integral under the curve is infinite, however we can use limits/boundaries to estimate a true desnity

There is no single metric that is best for all data or at all parameter values. However, I found one that considers the distribution of the classes. It yield good results. here is its citation, I dont think its available on the net;

Robert Short, and Keinosuke Fukunaga. The optimal distance measure for nearest neighbor classification. IEEE transactions on information theory, vol IT27, no 5, september, 1981

or

Robert Short and Keinosuke Fukunaga. A new nearest neighbor distance measure. In IEEE conference, pages 81 to 86, 1980.

Veyis thank you:) We have found Mahalanhobis to be very useful too even as we test Euclidean Distance.

If I remember correctly, Mahalanobis distance is best applicable to normal distributions (or something close to them).

Hi, if you have interest in how this algorithm works, please check the following youtube video

http://youtu.be/UqYde-LULfs

Regards

Mahalanobis works almost well, euclidean is less time consuming but works worst

Dear Jacob

I just have published a paper about this issue and I proposed a new distance metric which was invariant to the dimensionality of the feature vector find the paper at the link:

https://www.researchgate.net/publication/264995324_Dimensionality_Invariant_Similarity_Measure?ev=prf_pub

Article Dimensionality Invariant Similarity Measure

Are you planning to apply a distance metric on raw characters or also planing to include some more context in your approach? What I mean is that you can test the following two cases: (i) Case 1: measure the distance with a variety of distance metrics in an online stream of characters this is a straight forward approach, (ii) Case 2: try to cluster a set of similar characters with online stream clustering and then apply a variety of distance metrics between the character and the cluster.   You can also use a variety of distances including what you have already used in the previous case. In any case you should apply a ceiling analysis first in order to decide whether the data you have can be manipulated more sufficiently with either the first or the second case. Moreover I think that there is some other efficient approach with context spaces theory and trajectory context prediction, but for the beginning please try the first two cases and if you please let me know.