Abstract
Dimensionality reduction is a fundamental task in the field of data mining and machine learning. In many scenes, examples in high-dimensional space usually lie on low-dimensional manifolds; thus, learning the low-dimensional embedding is important. Some well-known methods, such as LPP and LE, adopt a locality-preserving strategy by constructing an adjacent graph and using the graph Laplacian to project raw examples into subspace in order to obtain the low-dimensional representation. Accordingly, in this paper, we propose a novel neighbors-based distance that measures the distance of two examples through their neighbors. To be more specific, we create a virtual bridge point from the neighbors of each example and use it to link with others. Instead of computing their direct Euclidean distance, we derive the distance of any two examples using their bridge points. We note that the introduced metric shows a high discriminative ability for the examples on the boundary, which known to be infamously hard examples. Extensive experiments on classification and clustering demonstrate that our proposed graph construction method can achieve a large margin improvement in spite of its simple form.
Introduction
Dimensionality reduction (DR) is essential for making sense of high-dimensional data by projecting it onto a lower-dimensional manifold. Many popular techniques, like Locality Preserving Projections (LPP) and Laplacian Eigenmaps (LE), rely on building an "adjacency graph" to represent the local structure of the data.
The weak link in these methods is often the distance metric used to build the graph—usually standard Euclidean distance. Euclidean distance is "blind" to the distribution of a point's neighbors. In complex datasets, two points from different classes might be physically close (hard negative pairs), while two points from the same class might be far apart (hard positive pairs). Standard graph construction often fails to distinguish these, leading to poor embeddings where different classes overlap at the boundaries.
The Neighbors-Based Distance Metric
The authors propose a new metric, $\rho$, which incorporates neighborhood information into the distance calculation through three key steps:
- The Neighborhood Vector: For any point, a "neighborhood vector" is calculated as a weighted sum of the vectors pointing to its $k$-nearest neighbors, where closer neighbors exert more influence.
- The Virtual Bridge Point: Instead of measuring the distance from point $A$ to point $B$ directly, the algorithm creates a "bridge." It considers where $A$ is "pulled" by its neighbors and where $B$ is "pulled" by its own neighbors.
- The Metric ($\rho$): The distance is derived from the norms of these neighborhood-influenced paths. Mathematically, it effectively "stretches" the distance between points that are being pulled in different directions by their respective neighborhoods and "shrinks" the distance for those moving in similar directions.
As illustrated above, this metric naturally increases inter-class distance and decreases intra-class distance for the "infamously hard" boundary examples by using neighbors as a proxy for the underlying manifold.
Integration and Workflow
This new metric is designed to be "plug-and-play." The authors integrated it into three classical manifold learning algorithms, creating new variants: NLPP (Neighbors-based LPP), NLE (Neighbors-based LE), and NIsomaps.
Key Results
The proposed NLPP method consistently outperformed standard LPP and even baseline supervised methods like LDA across diverse datasets (YaleB, ORL, UCI Wine Quality):
- Classification Accuracy: On the UCI Wine Quality dataset, NLPP achieved 96.42% accuracy, a massive leap over the standard LPP's 71.43%. On the YaleB face dataset, it improved accuracy from 76.78% to 87.42%.
- Clustering Performance: The neighbors-based variants showed consistent improvements. For instance, on the YaleB dataset, NIsomaps reached a clustering accuracy of 27.24% compared to the baseline 20.63%.
- Stability: Sensitivity analysis showed that the method is relatively stable across different parameter settings, such as the number of neighbors $k$ or the reduced dimension size.
Limitations and Future Work
While effective, constructing the graph with this metric has a time complexity of $O(n^2 d)$, making it difficult to scale to massive datasets without optimization. Future research may explore replacing standard Euclidean distance in modern deep learning contrastive or triplet loss functions with this neighbors-based metric to improve deep embeddings.
Summary updated