If the data set is mixed (numerical, nominal, and binary) features, for classifying such data we need to define new measure able to handle the three types.
Generally, the combined approach is widely used for this case.
If the new measure is combination between different measures, it is very difficult to fulfill the triangle inequality, so it can be similarity measure or distance but not metric.
My question is:
Is it possible to use such measure with KNN?
as we know KNN requires metric distance.
In general:
Can I use KNN with a non-metric measure for classifying the data?
Instead of metric measures, you can try the cosine measure of dissimilarity. For two points A and B, treated as vectors operating in the center of the coordinate system, the measure of similarity may be the square of the cosine of the angle between these vectors: s(A,B)=cos2(A,B).
Distance is a measure of dissimilarity. The cosine analogon of the distance between points A and B may be the cosine measure of dissimilarity: d(A,B)=1-s2(A,B)=1-cos2(A,B).
For example, in another context, the above measure of dissimilarity was used at https://www.researchgate.net/publication/328345955_On_the_clustering_of_correlated_random_variables/.
check this paper
https://pdfs.semanticscholar.org/b786/6fe2ddf83a2385c83c063e71ed35af1866d1.pdf
.
all hope is not lost with non metric dissimilarities ; see
http://rduin.nl/papers/ssspr_06_disrep.pdf
https://pdfs.semanticscholar.org/5cfe/394cf3b75c54ac1e8cee5e27c40b48a0c95a.pdf
.
Dear Najat,
This is truly an interesting question.
I would add that, if data is even more complex, also containing missing values, for instance, some “metrics” also break the reflectivity property. This happens in fact with some well-known heterogeneous distance metrics (HEOM and HVDM), and yet they are still the current state-of-the-art distance metrics to handle mixed (heterogeneous) data.
Now, to answer your question directly, it seems that KNN has been previously used with pseudo-metrics. However, for heterogeneous data, if you don’t have missing values, HEOM and HVDM respect the metricity (they are metrics) and are perhaps a suitable option in your case.
You may find these papers worthy of consideration (heterogeneous distance functions and some considerations regarding their metricity, properties and behavior):
Wilson, D. R., & Martinez, T. R. (1997). Improved heterogeneous distance functions. Journal of artificial intelligence research, 6, 1-34.
https://arxiv.org/pdf/cs/9701101.pdf
Juhola, M., & Laurikkala, J. (2007). On metricity of two heterogeneous measures in the presence of missing values. Artificial Intelligence Review, 28(2), 163-178.
https://link.springer.com/content/pdf/10.1007/s10462-009-9096-7.pdf
Santos, M. S., Abreu, P. H., Wilk, S., & Santos, J. (2020). How Distance Metrics influence Missing Data Imputation with k-Nearest Neighbours. Pattern Recognition Letters.
Article How Distance Metrics influence Missing Data Imputation with ...
- Badges
- Science topic
- Similar topics
- Books