2
$\begingroup$

I am looking to compare the distance preserved during dimension reductions for several techniques. I have read some papers on similar topics here and here.

For example, I would like to use the Euclidean Distance to measure the distance preserved during PCA's dimension reduction. However, my point of confusion what are $X$ and $Y$ in $$d(X, Y) = \sqrt{\sum^n_{i=1}\left(x_i - y_i\right)^2}$$ I understand how to calculate $d\left(X, Y\right)$ given two vectors/matrices, but I don't understand with context to PCA. Let me try to explain.

Let $W_{d \times k}$ be the matrix of $k$ leading eigenvectors, $X_{d\times n}$ be the original data, and $Z_{k\times n}$ be the projection of $X$ onto the reduced subspace.

$Z = W^{T}X$

Back to calculating $d\left(X, Y\right)$. My guess is that the PCA's $X$ correspond to $X$ and $Y$ can correspond to $Z$. But how does this work since $X$ and $Y$ have different dimensions? I have to be oblivious to something here.

Also, I am not concerned if a Euclidean Distance measure is not a good choice for measuring PCA's distance preservation (unless they are incompatible). This is simply exploration.

Edit: For example, if I have $$X_{d\times n} = \begin{bmatrix} x_{11} & \dots & x_{1n} \\ x_{21} & \dots & x_{2n} \\ x_{31} & \dots & x_{3n} \\ \end{bmatrix} $$ and say I choose to retain $k = 2$ principal components which are then projected onto $$Z_{k \times n} = \begin{bmatrix} z_{11} & \dots & z_{1n} \\ z_{21} & \dots & z_{2n} \\ \end{bmatrix} $$

$\endgroup$
  • $\begingroup$ Welcome to SE.DataScience! I think, here, distance preservation is about comparing the distance of two points X and Y in space1 to that of space2, so they have the same dimension in both cases. We want to see whether two close points in space1 are also close in space2. $\endgroup$ – Esmailian Apr 21 '19 at 10:47
  • $\begingroup$ @Esmailian Ok, so space 1 would correspond to $W$ (eigenvector matrix) and space 2 would correspond to $Z$? (I realize which one is space 1 and space 2 doesn't matter in the euclidean formula. I was just originally though that I should be comparing $X$ to $Z$ instead of $W$ to $Z$) $\endgroup$ – riley.finn Apr 21 '19 at 21:25
  • $\begingroup$ @Esmailian I still don't understand how I am supposed to compare a point in 𝑋 to a point in 𝑍, because 𝑍 would be a shorter vector than 𝑋, right? Or, are you not supposed to reduce the dimension before measuring the distance? $\endgroup$ – riley.finn Apr 23 '19 at 4:02
1
$\begingroup$

The confusion

The point of confusion is probably the use of variable $n$ to denote the dimension in Euclidean distance, which is later re-used for the number of points. Euclidean distance is better to be written as $$d_X(\boldsymbol{x}_1, \boldsymbol{x}_2)=\sqrt{\sum_{i=1}^{\color{red}{d}}(x_1^i - x_2^i)^2}$$ in the original space, and $$d_Z(\boldsymbol{z}_1, \boldsymbol{z}_2)=\sqrt{\sum_{i=1}^{\color{red}{k}}(z_1^i - z_2^i)^2}$$ in the reduced space. Where $\boldsymbol{z}_a=(z_a^1,\cdots,z_a^k)$ is the transformation of point $\boldsymbol{x}_a=(x_a^1,\cdots,x_a^d)$ by $W$. EDIT: in your notation, $Z[:, a]$ is the transformation of $X[:, a]$.

Distance preservation measure

A measure of distance preservation for transformation $W$ should be defined in such a way that compares the distance of two points in the original space with the distance of the same two points in the reduced space.

Accordingly, a measure that compares all $\binom{n}{2}$ pairwise distances could be defined as: $$DP(W) = \frac{2}{n(n-1)}\sum_{a=1}^{n} \sum_{b=a+1}^{n} |d_X(\boldsymbol{x}_a, \boldsymbol{x}_b) - d_Z(\boldsymbol{z}_a, \boldsymbol{z}_b)|$$

where for a constant $k$, smaller $DP(W)$ implies better distance preservation by $W$.

Note that various measures of distance preservation can be defined based on this foundation. For example,

  1. Restricting the comparison to only $K$ nearest neighbors of a point in the original space, leading to $nK$ comparisons instead of $\binom{n}{2}$, or
  2. Using the Pearson correlation of distances rather than their difference, since we generally want close (distant) points in the original space to be also close (distant) in the reduced space, or
  3. Measuring the distance to point's tangent space instead of the point itself, etc.
| improve this answer | |
$\endgroup$
  • $\begingroup$ Please see my edit where I included an example. I still don't understand how I know which points in $k$ dimensional space are the same two points in $d$ dimensional space. For example, what points in $Z$ would l compare to the points in $x_3$ (the bottom row). Or can I not measure the distance preserved of the $x_3$. Sorry for being so dense. $\endgroup$ – riley.finn Apr 23 '19 at 15:19
  • $\begingroup$ @qq3254 Note that "distance preservation" is not about measuring the distance between a point in X and a point in Z, this is undefined and meaningless. $\endgroup$ – Esmailian Apr 23 '19 at 15:26
1
$\begingroup$

I think there is an easier way to compare distance preservations:

1) In case your original dataframe is big, sample let's say random N=10,000 points from there.

2) Fit all your dimensionality reduction algorithms and transform this newly sampled dataframe.

3) Obtain euclidean distances between points in originally sampled dataframe, then other newly produced transformed dataframes in step 2. For example:

dist_orig = np.square(euclidean_distances(X_sampled, X_sampled)).flatten()
dist_pca = np.square(euclidean_distances(pca, pca)).flatten()
dist_tsne = np.square(euclidean_distances(tsne, tsne)).flatten()
dist_umap = np.square(euclidean_distances(umap, umap)).flatten()

4) Run spearman or other correlation metric by comparing original sampled euclidean space vs each of the reduced spaces. For instance:

coef_pca, p_pca = spearmanr(dist_orig, dist_pca)
coef_tsne, p_tsne = spearmanr(dist_orig, dist_tsne)
coef_umap, p_umap = spearmanr(dist_orig, dist_umap)

5) See which method has the highest correlation coefficient and, hence, preserves the best distances between points in original space.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.