Abstract
Let O denote a set of N entities and D = (dkl) a matrix of dissimilarities defined on OxO. The diameter of a partition of O into M clusters is defined as the maximum dissimilarity between entities in the same cluster, and the split of such a partition as the minimum dissimilarity between entities in different clusters. A partition of O into M clusters is called efficient if and only if there is no partition of O into not more clusters with smaller diameter and not smaller split or with larger split and not larger diameter. A graph-theoretic algorithm which allows to obtain a complete set of efficient partitions is described. Then are presented some experiments, designed to evaluate the potential of bicriterion cluster analysis as a tool for the exploration of data sets, i.e. for detecting the underlying structure of O, if and when it exists. Both real data sets on psychological tests and on stock prices, and artificial data sets are considered. The ability of bicriterion cluster analysis to detect the best clusterings in many cases and to show whether or not there are some natural clusterings is clearly evidenced.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Anderberg, M.R., “Cluster Analysis for Applications”, New-York: Academic Press (1973).
Baker, F.B. and L. Hubert, “Measuring the Power of Hierarchical Cluster Analysis”, J. Amer. Stat. Assoc., 70 (1975) 31–38.
Baker, F.B. and L. Hubert, “A Graph-Theoretic Approach to Good-ness-of-Fit in Complete-Link Hierarchical Clustering”, J. Amer. Stat. Assoc., 71 (1976) 870–878.
Benzecri, J.P. (et collaborateurs), “L’Analyse de données, 1. La Taxinomie”, Paris: Dunod (1973).
Berge, C., “Graphes et hypergraphes”, Paris: Dunod (1970), English translation, Amsterdam: North-Holland (1973).
Delattre, M. et P. Hansen, “Classification d’homogénéité maximum”, Actes des Journées “Analyse de données et Informatique”, Versailles, septembre 1977, I, 99–104.
Delattre, M. and P. Hansen, “Bicriterion Cluster Analysis”, submitted.
Hansen, P. and M. Delattre, “Complete-Link Cluster Analysis by Graph Coloring”, J. Amer. Stat. Assoc. (forthcoming).
Harman, H.H., “Modern Factor Analysis”, Chicago: University of Chicago Press (1967).
Hartigan, J.A., “Clustering Algorithms”, New-York: Wiley (1975).
Hubert, L., “Approximate Evaluation Techniques for the Single Link and Complete Link Hierarchical Clustering Procedures”, J. Amer. Stat. Assoc. 69 (1974) 698–704.
Jardine, N. and R. Sibson, “Mathematical Taxonomy”, London: Wiley (1971).
Johnson, S.C., “Hierarchical Clustering Schemes”, Psychometrika, 32 (1967) 241–254.
King, B.F., “Market and Industry Factors in Stock Price Behaviour”, Journal of Business, 39 (1966) 139–190.
Ling, R.F., “A Probability Theory of Cluster Analysis”, J. Amer. Stat. Assoc., 66 (1973) 159–164.
Ling, R.F. and C.G. Killough, “Probability Tables for Cluster Analysis Based on a Theory of Random Graphs”, J. Amer. Stat. Assoc., 77 (1976) 293–299.
Rao, M.R., “Cluster Analysis and Mathematical Programming”, J. Amer. Stat. Assoc., 66 (1971) 622–626.
Ruspini, E.H., “A New Approach to Clustering”, Information and control, 15 (1969) 22–32.
Sneath, P.H. and R.R. Sokal, “Numerical Taxonomy”, San Francisco: W.H. Freeman and Company (1973).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1978 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hansen, P., Delattre, M. (1978). Bicriterion Cluster Analysis as an Exploration Tool. In: Zionts, S. (eds) Multiple Criteria Problem Solving. Lecture Notes in Economics and Mathematical Systems, vol 155. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-46368-6_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-46368-6_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-08661-1
Online ISBN: 978-3-642-46368-6
eBook Packages: Springer Book Archive