Lens depth function and k-relative neighborhood graph: versatile tools for ordinal data analysis
This addresses the challenge of analyzing data with only relative distance comparisons, which is incremental by improving efficiency and practicality over prior approaches.
The paper tackles the problem of performing machine learning tasks like medoid estimation, outlier identification, classification, and clustering using only ordinal distance information, proposing algorithms based on lens depth function and k-relative neighborhood graph that are faster and avoid drawbacks of existing ordinal embedding methods.
In recent years it has become popular to study machine learning problems in a setting of ordinal distance information rather than numerical distance measurements. By ordinal distance information we refer to binary answers to distance comparisons such as $d(A,B)<d(C,D)$. For many problems in machine learning and statistics it is unclear how to solve them in such a scenario. Up to now, the main approach is to explicitly construct an ordinal embedding of the data points in the Euclidean space, an approach that has a number of drawbacks. In this paper, we propose algorithms for the problems of medoid estimation, outlier identification, classification, and clustering when given only ordinal data. They are based on estimating the lens depth function and the $k$-relative neighborhood graph on a data set. Our algorithms are simple, are much faster than an ordinal embedding approach and avoid some of its drawbacks, and can easily be parallelized.