0
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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 240.000.000.000 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.

Improve this answer
$\endgroup$
2
  • $\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, 2019 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$
    – Has QUIT--Anony-Mousse
    Dec 12, 2019 at 23:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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