Review: Neighborhood Preservation in Nonlinear Projection Methods: An Experimental Study¶
Citation
- Venna, J., & Kaski, S. (2001). Neighborhood preservation in nonlinear projection methods: An experimental study. In Artificial Neural Networks, ICANN 2001, Lecture Notes in Computer Science 2130, 485–491. Springer.
- DOI
Abstract¶
Several measures have been proposed for comparing nonlinear projection methods but so far no comparisons have taken into account one of their most important properties, the trustworthiness of the resulting neighborhood or proximity relationships. One of the main uses of nonlinear mapping methods is to visualize multivariate data, and in such visualizations it is crucial that the visualized proximities can be trusted upon: If two data samples are close to each other on the display they should be close-by in the original space as well. A local measure of trustworthiness is proposed and it is shown for three data sets that neighborhood relationships visualized by the Self-Organizing Map and its variant, the Generative Topographic Mapping, are more trustworthy than visualizations produced by traditional multidimensional scaling-based nonlinear projection methods.
Venna and Kaski (2001) introduce the two measures Hifuku uses to score an ordination. Section 2 provides the definitions; the remainder of the paper compares Self-Organizing Maps against multidimensional scaling on three benchmark data sets, and is not used here.
Two classes of projection error¶
Section 2 defines a neighborhood as the set of the \( k \) closest data vectors, for small \( k \). A projection can fail in two ways. A vector that was not a neighbor may enter the neighborhood on the display, so that points which appear close are in fact dissimilar. Alternatively, a vector that was a neighbor may be projected away, which introduces a discontinuity in the mapping.
The authors observe that these errors are not equally serious. The second had already received attention as neighborhood preservation. The first, which they term a loss of trustworthiness, had not previously been measured, and they argue it is the more damaging of the two, because a reader of the display has no way to distinguish an introduced proximity from a genuine one.
Definition of the measures¶
Let \( C_k(\mathbf{x}_i) \) denote the \( k \) nearest vectors in the original space, \( \hat{C}_k(\mathbf{x}_i) \) the \( k \) nearest after projection, \( r(\mathbf{x}_i, \mathbf{x}_j) \) the rank of \( \mathbf{x}_j \) from \( \mathbf{x}_i \) in the original space, and \( \hat{r}(\mathbf{x}_i, \mathbf{x}_j) \) that rank after projection.
With \( U_k(\mathbf{x}_i) \) the set of vectors that entered the neighborhood, trustworthiness is
With \( V_k(\mathbf{x}_i) \) the set of vectors that left it, preservation of the original neighborhoods, elsewhere termed continuity, is
Two properties of these definitions govern their implementation. First, the penalty is weighted by rank rather than counted: each offending vector contributes \( r - k \), the amount by which its true rank exceeds the neighborhood size. A false neighbor whose true rank is 16 therefore contributes little, while one whose true rank is 1000 contributes heavily. A measure based on counts would treat the two alike. Second, the scaling term \( 2 / \bigl(Nk(2N - 3k - 1)\bigr) \), which maps each measure onto \( [0, 1] \), is stated in footnote 1 for neighborhoods of size \( k < N/2 \) only. Hifuku's default of \( k = 15 \) against clouds of several thousand trees lies well inside that range, but the restriction is recorded in the implementation.
Relevance to Hifuku¶
Section 2 states the underlying tradeoff directly: where the data manifold has higher dimension than the display, both classes of error cannot be avoided simultaneously, and every projection method must balance one against the other.
This tradeoff determines the design of Hifuku's synthesis step. A cloud of elite trees occupies considerably more than two dimensions, so no plane preserves both its distances and its neighborhoods. The choice between them is a statement about the purpose of the map. Hifuku preserves neighborhoods, on the grounds that two trees drawn together are read as agreement, and a projection that introduces proximity therefore asserts a relationship the trees do not support.
\( M_1 \) and \( M_2 \) render that choice measurable. Hifuku reports both, together with a per-point quantity the paper does not define: the mean true rank of the neighbors a map places around each tree, which identifies where a projection is untrustworthy in addition to the degree.
In-document navigation¶
| Section | Content |
|---|---|
| Section 1 | Nonlinear projection methods, from PCA and MDS to SOM and GTM |
| Section 2 | The two error classes, Table 1 notation, and equations 1 and 2 |
| Section 3 | Test setting: Glass, Ionosphere and Phonetic data sets |
| Section 4 | Results, and the effect of mapping stiffness on each measure |
| Section 5 | Conclusions |