K-NN or matrix factorization for discovering correlated features? I am looking to cluster users together in a database, with each user represented by a number of features that are both discrete and continuous in nature.  "Similar" users should be clustered together in a way that underlying strongly correlated features can be easily discovered.  A few other requirements:


The number of clusters is unknown
The runtime execution time is not a concern
The number of users can be on the order of 100,000 and number of features around 50


There are a number of clustering techniques, from KNN, k-means, matrix factorization, even PCA, but many seem to hide the underlying correlations that tie the users together.  Any advice?
You're asking essentially a modelling question, and so the answer really depends on your data. If you're saying that strong correlations are not being identified by the methods you listed, it's possible that the correlations are non-linear (the above methods with the exception of k-NN are linear), and so you might try something like ICA. 

For something closer to home, have you considered correlation clustering ? you don't say how the data is presented, but if you have similarity and dissimilarity information, then correlation clustering is a good solution, and also does not require you to specify the number of clusters. 

Another idea would be to try spectral methods (if all you have is a distance function) like spectral clustering.