Clustering algorithm whose results are invariant to data permutation and bootstrap perturbation

Question

I am wondering if there is in the literature a clustering algorithm whose output (partition, dendrogram, soft assignments and so on) is invariant to :

• permutation in the data points (typically many hierarchical agglomerative clustering are not)
• perturbation due to bootstrapping the features

I would be glad to have some entry point in the literature for finding such an algorithm!

To precise my request, I am aware of axiomatic formulation of clustering, e.g. Kleinberg's impossibility theorem (http://machinelearning.wustl.edu/mlpapers/paper_files/LT17.pdf) or a beginning of clustering taxonomy (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.190.5225&rep=rep1&type=pdf),

but they did not seem to have considered these two properties.

Answer 1

You can find here a survey of clustering algorithms invariant under permutation in the data points and invariant under monotone transformation of similarity values:

Batyrshin I., Rudas T. Invariant Hierarchical Clustering Schemes. In: Batyrshin, I.; Kacprzyk, J.; Sheremetov, L.; Zadeh, L.A. (Eds.). Perception-based Data Mining and Decision Making in Economics and Finance. Series: Studies in Computational Intelligence, vol. 36. 2007, 181-206, Springer.