I have a large-ish dataset (100k samples, ~100 features), that I am trying to cluster, to an unknown number of clusters. I thought of using PCA first, to reduce dimensionality, since I understand that distances (euclidean, cosine) in high-dimensionality might not be actually accurate.

However, I found very little on using PCA before AP, unlike K-Means, which made me wonder - is there any reason to not use PCA and then affinity propagation?


Independent of the number of features, you will obviously need much more than

3 * 100.000 * 100.000 * 8 bytes

of ram (with double precision floats). That is or about 240 GB. Not only is this a lot of RAM to have, but AP will have to do many passes over this RAM, so this will take forever, even after computing the distance matrix.

So clearly PCA won't help. You just cannot afford an algorithm with O(n²) memory and O(n²) runtime. PCA reduces d, but the runtime of AP itself does not depend on d.

  • $\begingroup$ Got it. So does this mean that AP can be used only on significantly smaller data sets (assuming no ultra RAM available)? $\endgroup$
    – guyts
    Dec 12 '19 at 21:55
  • $\begingroup$ Just do an experiment yourself. Generate simple data with n=1000, n=2000, n=4000, n=8000 and then estimate the cost. $\endgroup$ Dec 12 '19 at 23:34

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.