I am working on a new metric measure. I tested it against Euclidean and Manhattan distances and it gives better results w.r.t KNN algorithm. How to make sure that a certain function can be considered as metric function and how to prove it?
Is it enough to compare it with other metrics such as Euclidean and Manhattan?
Could you please list some metric measures or direct me to a complete list including all known metric measures?
The answer from Christopher Farah is certainly solid. Depending on specifics of your (proposed) metric, there may be straightforward ways to determine if it in fact satisfies the requirements he lists. If you can give a simple explanation/definition maybe someone can say more in that direction.
On a slightly different topic, I am curious to understand what you mean by "better results w.r.t KNN algorithm" Do you use your distance, and some implementation of k-nearest, and get results that are better for some class of problem(s) than those obtained for Euclidean or Manhattan? Or do you find neighbors in the Euclidean metric, but use your metric under the hood in the k-nearest implementation?
@Christopher and @Daniel, thank guys very much, you are very helpfull.
"Do you use your distance, and some implementation of k-nearest, and get results that are better for some class of problem(s) than those obtained for Euclidean or Manhattan?"
yes, i implemented the KNN with the new distance one time and with Euclidean and Manhattan, using 20 different real life data, the results are encouraging, most of times there is improvement, some times significant improvement, the accuracy improved from 74% to 90%, in few cases no change or less accuracy, but not significant.
The used databases are:
australian
balance
cancer
diabetes
german
glass
heart
ionosphere
led17
liver
monkey1
phoneme
segmen
sonar
vehicle
vote
vowel
waveform21
waveform40
wine
I would like to add that the choice of the "right" distance metric is highly dependent on the data, especially its dimensionality and its spareseness. To get a visual idea of a distance metric, I often take a random sample of maybe 1000 elements from my data and for each of those elements I calculate the distances to all other elements in the data set and put the resulting values in a two-dimensional histogram (one axis are my 1000 samples, the other axis are the distances). For example, if you create such a histogram for the euclidian distance on high-dimensional, sparse data vectors, you will see how all distances agglomerate near 0 for all sample elements illustrating that the euclidian distance is in fact not a good distance measure for high-dimensional, sparse data.
Hi. Please, correct me if I am wrong, but kNN does not require the distance function to be a valid metric. It does not have to statisfy symmetry, triangle inequality, d(x,x) = 0, and it does not even have to be positive. Even a function which violates all of those could work well in kNN. Is there some benefit in knowing your function is a metric?
@Michal your are absolutely right, the metric is found by chance while tuning the accuracy of KNN on different data sets, i want to publish a paper about it as a metric, that why asked the question, KNN is used to compare it with other measures, could you please direct me to another methodology to compare the performance of metric distances?
Ahmad, the number of existing publications on distance learning is huge. Many publications target classification in some way. I suggest you look at https://sites.google.com/site/yiqunhu/Home/distance-metric-learning. The page looks like a comprehensive sorted list of publications.
Note that condition (ii) should in fact be: d(x, y) = 0 if and only if x = y
Only satisfying d(x,x) = 0 results in a pseudo-metric, where two distinct elements x and y can be at distance 0.
Dear @Ahmad,
It is an interesting question. I would like to mention the following remarks:
1. All norms are equivalent, i.e. there exist constants A, B such that
First Norm
There are many usual metrics (it depends on the purposes they are used for). A general method of fabricating new metrics from usual ones is the following: if d is a metric on S X S, Y is a set and f is an injective mapping from Y into S, then d_1(x,y)=d(f(x),f(y)), (x,y in Y) defines a metric on Y X Y. Usually, f might be a concrete mapping. Observe that in general, if Y , S are vector spaces, and d is associated to a norm on S (d(x,y)=norm(x-y)), then d_1 might be not associated to any norm on Y. In the particular case of an injective linear operator f, norm_1(y)=norm(f(y)) defines a norm on Y. If f is a linear isomorphism, then the norms on S and Y can be obtained one from the other by composing the norms with f, respectively with the inverse of f.
Dear muhammad Omar
I already done all these points to got this distance:
Article Dimensionality Invariant Similarity Measure
and compared with applications:
https://www.researchgate.net/publication/319135278_Distance_and_Similarity_Measures_Effect_on_the_Performance_of_K-Nearest_Neighbor_Classifier_-_A_Review
what do you think about it?
Dear Hassanat,
Your question is related mainly to K Nearest Neighbor (KNN) Classifier and that is the purpose of your paper I congratulate you on this work and I urge you to work on a general new metric that can be applied to all kind of classifier whether they are unsupervised or supervised one.
Best wishes
Yes Mohammad, we have not tested on clustering yet, we have done on KNN and CBIR so far, so be my guest, I will give you the code and let us start a new project if you want.
- Badges
- Science topic
- Similar topics
- Mathematics
- Applied Mathematics