zbMATH — the first resource for mathematics

Optimal hierarchical clustering with order constraint. (English) Zbl 0922.92042
Diday, Edwin (ed.) et al., Ordinal and symbolic data analysis. Proceedings of the international conference, OSDA 95, Paris, June 20–23, 1995. Berlin: Springer. Studies in Classification, Data Analysis, and Knowledge Organization. 265-276 (1996).
The authors consider the problem of hierarchical clustering with order constraints. They give two new efficient algorithms for its solution based on dynamic programming. Both methods provide saturated clustering. The second one gives in addition intermediate hierarchies which are saturated up to a given number of “bushes” (clusters with special properties within an hierarchy). This is useful when looking for a large scale structure in lots of objects. The criterion used for comparison of different hierarchies is increasing and associative functions of the qualities of its clusters.
For the entire collection see [Zbl 0866.00054].
91C20 Clustering in the social and behavioral sciences
90C90 Applications of mathematical programming
90C27 Combinatorial optimization