Is it legit to run clustering on MDS result of a distance matrix? I am new to the topic of clustering and face the following problem:
I have multiple binary datasets with 10k to 40k entries and 135 features each:
$$
\begin{matrix} \newcommand{\feat}{\text{feat}}
\feat_{1} &  \feat_{2}  & \ldots & \feat_{135}\\
0  &  1 & \ldots & 1\\
\vdots & \vdots & \ddots & \vdots\\
0  &   0       &\ldots & 1
\end{matrix}
$$
After redundance reduction, I calculated the distance matrix, using the simple matching distance as this is the best fitting description between the entries, where d = (1 - s). Therefore, I result in a n x n matrix, where for example $n = 5000$, leading to $5000^2$ entries.  
Next I would like to find and group similar entries, using (unsupervised) clustering.
$$
\begin{matrix} \newcommand{\entr}{\text{entr}}
& \entr_{1} &  \entr_{2}  & \ldots & \entr_{5000}\\
\entr_{1} & 0  &  0.2 & \ldots & 0.87\\
\vdots & \vdots & \ddots & \vdots\\
\entr_{5000} &  0.87 &   0.63       &\ldots & 0
\end{matrix}
$$
I am using R and found out that using the EM Algorithm (package mclust) returns some meaningful clusters. Even when I ran the algorithm on the distance matrix. But the runtime is unacceptable high with large matrices.
For that purpose, I thought of using Multi Dimensional Scaling (MDS) to find the coordinates for every entry in lets say a 2-d space. And then run clustering on the lower space. 
However, I am really unsure if this approach is allowed. I would appreciate any help or references to papers. I could only find examples and papers using MDS in terms of plotting data. Maybe I am just missing the correct question to that topic.
 A: MDS is mostly a visualization tool, it can suggests clusters but it doesn't test if the groupings you see are similar at a certain level. So the other papers you refer to were right at using MDS to only plot their data.
I previously used the software PRIMER to do clustering analysis and the package clustsig seems to be doing pretty much the same thing in R. You may want to look into this package to perform your clustering analysis, maybe it will be faster than mclust?
A: That's certainly valid. You just have to keep in mind the tradeoff. You are forsaking some information to embed your $N$ dimensional data into a lower dimensional space.
Multidimensional Scaling can be seen as a dimensionality reduction algorithm like any other, with the advantage being it tries to keep the hierarchical structure of the data (and it can of course fail on that, no free lunch).
Keep in mind you're not restricted to 2-dimensions with MDS. You can actually test for a feasible and reasonable number of dimensions.
