1
$\begingroup$

After standardizing my dataset, I perform a principal component analysis. Then I do a nearest neighbour search.

I observed then after performing the PCA, even though I kept (for testing purposes) all resulting dimensions (so the input dataset has the same number of features as the PCA-transformed one), my nearest neighbour results drop.

As a distance metric in the nearest neighbour search I use the cosine distance. My intuitive assumption was, that this distant metric should not be influenced by the PCA in the case I don't reduce the dimensionality of my dataset.

How can the performance drop be explained? Did I probably do something wrong?

Here is how I perform the PCA. I use Eigen and C++. traindata is my untouched input dataset where each row is a sample and each column a feature:

  // Mean centering data.
  featureMeans = traindata.colwise().mean();
  Eigen::MatrixXf centered = traindata.rowwise() - featureMeans;
  // Compute featurewise standard deviations.
  Eigen::MatrixXf cov = centered.adjoint() * centered;
  Eigen::VectorXf variances = cov.diagonal();
  stdDevs = variances.cwiseSqrt();
  // Normalize each feature with standard deviation.
  for (size_t i = 0; i < centered.rows(); i++) {
    centered.row(i) = centered.row(i).array() / stdDevs.array().transpose();
  }

  // Compute SVD.
  Eigen::JacobiSVD<Eigen::MatrixXf> svd(centered, Eigen::ComputeThinV);
  // Transformation matrix.
  pcaTransform = svd.matrixV();
  // Project the dataset.
  traindata = centered * pcaTransform;

And later when I get a new datapoint, I transform it in the space of the principal components like this:

Eigen::VectorXf NearestNeighbour::transform(Eigen::VectorXf& vec) {
  vec -= featureMeans;
  vec = vec.array() / stdDevs.array();
  vec = vec.transpose() * pcaTransform;
  return vec;
}

Then in the nearest neighbour algorithm I compute the cosine similarity like this:

float NearestNeighbour::calcCosineSimilarity(Eigen::VectorXf& vecOne, Eigen::VectorXf& vecTwo) {
  float dot = vecOne.dot(vecTwo);
  float cosine = dot / (vecOne.norm() * vecTwo.norm());
  return cosine;
}

I wrote a test script in python using my dataset. The input vector is randomly created as I only wanted to test the concept:

inpvec = [[ 0.73977109,  0.03620438,  0.25417753,  0.11561778,  0.82897718,
         0.13585422,  0.16245644,  0.97201561,  0.68201026,  0.52702283,
         0.21245685,  0.246901  ,  0.72042289,  0.52233973,  0.89980493,
         0.3394559 ,  0.92817351,  0.64084039,  0.73594745,  0.825488  ,
         0.87527608,  0.02777485,  0.30630228,  0.26867405,  0.10130528,
         0.43129711,  0.41076364,  0.22625131,  0.2616146 ,  0.52088176,
         0.23174206,  0.1674724 ,  0.81184377,  0.68945395,  0.12719359,
         0.97440578,  0.18162815,  0.29054626,  0.22535362,  0.44556911,
         0.15830425,  0.15641608,  0.00425475,  0.77260893,  0.84462181,
         0.98222192,  0.12986739,  0.16809029,  0.58549871,  0.38430837,
         0.39776035,  0.76900314]]


def loadTrainingData(path):
  f = open(path)
  tData = []
  for line in f:
    lsplit = line.split(",")
    datapoint = []
    for feature in lsplit:
      datapoint.append(float(feature))

    tData.append(datapoint)
  data = np.array(tData) 
  X = np.delete(data, data.shape[1] - 1, 1) # Strip class.
  return X


inpvec = np.array(inpvec)
X = loadTrainingData("trainingfile.csv")


normalizer = Normalizer()
X_norm = normalizer.fit_transform(X)
cosdists = []
for datapoint in X_norm:
  cosdists.append(cosine(normalizer.transform(inpvec)[0], datapoint))
value = min(cosdists)
index = [i for i, j in enumerate(cosdists) if j == value]
print "min dist at " + str(index) + " with " + str(value)


# PCA
pipeline = Pipeline([('scaling', StandardScaler()), ('pca', PCA(n_components=X.shape[1]))])
X_reduced = pipeline.fit_transform(X)

inpVecReduced = pipeline.transform(inpvec)[0]
cosdistsTwo = []
for datapointPCA in X_reduced:
  cosdistsTwo.append(cosine(inpVecReduced, datapointPCA))
valuePCA = min(cosdistsTwo)
indexPCA = [i for i, j in enumerate(cosdistsTwo) if j == valuePCA]
print "min dist at " + str(indexPCA) + " with " + str(valuePCA)

The output of this is:

min dist at [462] with 0.322760977886
min dist at [304] with 0.461332258519

My assumption was that it should output the same index in both cases. Why is this happening?

$\endgroup$
  • $\begingroup$ Was there a performance drop? Can you add more information about what you did & what happened? $\endgroup$ – gung - Reinstate Monica Nov 11 '15 at 17:59
  • $\begingroup$ I compute the nearest neighbour compared to a dataset based on cosine similarity. After I perform the pca my algorithm finds different datapoints as the the nearest neighbour. $\endgroup$ – Chris Nov 12 '15 at 11:31
  • $\begingroup$ In your Python code, what is matrix t? It is certainly not a rotation matrix, so why would the angles be preserved? $\endgroup$ – amoeba says Reinstate Monica Nov 12 '15 at 13:47
  • $\begingroup$ You're right, that was my mistake, it's not orthogonal vectors. I get rid of it as it only adds confusion. I exchange it with another example which also didn't work out. $\endgroup$ – Chris Nov 12 '15 at 13:50
  • $\begingroup$ If you use a rotation (i.e. orthogonal) matrix, is has to work out. $\endgroup$ – amoeba says Reinstate Monica Nov 12 '15 at 13:59
3
$\begingroup$

PCA is a linear transformation, and if you are keeping every dimension, then your data should have the same distance function. Supposing that your original data was some matrix $X$ and your resulting data is some transformed matrix $Y = AX$, then the distance should be unchanged:

$$ d(y_i, y_j) = d(A x_i, A x_j) $$

and if you are using the cosine distance,

$$ d(A x_i, A x_j) = 1 - ((A x_i)^T (A x_j)) / (\|A x_i\| \| A x_j \|) $$

and since the $\| A x_i \| = \| x_i \|$,

$$ = 1 - (x_i^T A^T A x_j) / (\| x_i \| \| x_j \|) $$

and since $A^T A = I$,

$$ = 1 - (x_i^T x_j) / (\| x_i \| \| x_j \|) = d(x_i, x_j) $$

so all this was a very roundabout way to say that distance calculations should not be affected.

Edit, once code appeared: in the calculation of centered, you are normalizing the features for unit variance. This might be a good idea in general, but it's going to change the distances between points since essentially you are weighting some dimensions to be more or less important than others. In that case, your resulting data is some transformed matrix $Y = ANX$ where $A$ is some orthogonal basis (so $A^T A = I$ as before), but $N$ is just a diagonal matrix that is not necessarily $I$. In that case you can't show that $d(y_i, y_j) = d(x_i, x_j)$. However, you can show that $d(y_i, y_j) = d(N x_i, N x_j)$. That means that if you were to transform your input data to have unit variance in each dimension, then the distance would be the same as the post-PCA data.

$\endgroup$
  • $\begingroup$ Thank you! Maybe I made some mistake in the actual transformation step. If I have a clue but aren't sure I might add it to the question. For now I accept your answer :). $\endgroup$ – Chris Nov 11 '15 at 23:40
  • 1
    $\begingroup$ Yeah, I can't help point out what the issue might be unless there's some code, unfortunately. $\endgroup$ – ryan Nov 12 '15 at 1:10
  • $\begingroup$ Added some code. $\endgroup$ – Chris Nov 12 '15 at 9:43
  • $\begingroup$ In accordance, I've added an update to my answer. $\endgroup$ – ryan Nov 12 '15 at 15:31
  • 1
    $\begingroup$ You're right, there is no standard answer. I don't understand what you're doing well enough to provide any advice here. If you're doing PCA before nearest neighbor classification (or some other classifier), the typical use (at least in my world) would be for dimensionality reduction. In your code here, you keep all the dimensions. If you dropped the irrelevant dimensions with small eigenvalues, and worked in a lower-dimensional space, this might boost the accuracy of your classifier. But of course, the pairwise distances between points are going to be different if you do that. $\endgroup$ – ryan Nov 12 '15 at 19:32

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.