Anisotropic View Distance Metric for High-Dimensional Data: Theory, Geometry, and Fast Computation

Abstract:K-Means clustering algorithm is one of the most commonly used clustering algorithms because of its simplicity and efficiency. K-Means clustering algorithm based on Euclidean distance only pays attention to the linear distance between Euclidean distance is an efficient and interpretable similarity measurement, but its effectiveness may deteriorate in sample spaces with anisotropic structures, redundant features, or complex feature interactions. In this paper, we propose a novel distance metric called View distance. Inspired by orthographic projection, the proposed metric projects the sample space onto $n(n-1)/2$ two-dimensional planes and defines the final distance as the sum of the Euclidean distances across the projected planes. Theoretical derivations verify that the View distance strictly satisfies the metric axioms and norm constraints. Beyond that, the View distance achieves feature coupling through projection and not only enables constant features to indirectly participate in distance calculation, but also suppresses interference from redundant features while exhibiting anisotropic geometric properties. Furthermore, to address the high computational complexity and poor scalability of full-projection View distance, we propose a two-dimensional projection plane selection strategy based on iterative Maximum Weight Matching, which reduces the computational complexity of distance calculation from $\mathcal{O}(n^2)$ to $\mathcal{O}(k)$. Extensive experiments on 12 diverse datasets demonstrate that View distance and the deterministic selection strategy provide competitive or superior performance compared with Euclidean distance and other $L_{p}$ metrics while maintaining strong interpretability and computational efficiency. The View distance provides a new perspective and option for similarity measurements.

Machine Learning (cs.LG); Numerical Analysis (math.NA)

arXiv:2206.05215 [cs.LG]

(or arXiv:2206.05215v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2206.05215 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.