Classification and Dissimilarity Analysis

Classifying objects according to their likeness seems to have been a step in the human process of acquiring knowledge, and it is certainly a basic part of many of the sciences. Historically, the scientific process has involved classification and organization particularly in sciences such as botany, geology, astronomy, and linguistics. In a modern context, we may view classification as deriving a hierarchical clustering of objects. Thus, classification is close to factorial analysis methods and to multi-dimensional scaling methods. It provides a mathematical underpinning to the analysis of dissimilarities between objects.

1 Introduction.- 1.1 Classification in the history of Science.- 1.2 Dissimilarity analysis.- 1.3 Organisation of this publication.- 1.4 References.- 2 The partial order by inclusion of the principal classes of dissimilarity on a finite set, and some of their basic properties.- 2.1 Introduction.- 2.1.1 What is dissimilarity analysis?.- 2.1.2 What’s in this chapter?.- 2.2 Preliminaries.- 2.2.1 The vector space D generated by the dissimilarities.- 2.2.2 Some elementary dissimilarities.- 2.2.3 Some general types of dissimilarities.- 2.2.4 Stability under increasing transformations.- 2.2.5 The quotient space of an even dissimilarity.- 2.2.6 Embeddability in a metric space.- 2.2.7 The set of all semi-distances.- 2.2.8 Stability under replication.- 2.3 The general structures of dissimilarity data analysis and their geometrical and topological nature.- 2.3.1 Euclidean semi-distances.- 2.3.2 Semi-distances of L1-type.- 2.3.3 Hypermetric semi-distances.- 2.3.4 Quasi-hypermetric dissimilarities.- 2.3.5 Ultrametric semi-distances.- 2.3.6 Tree semi-distances.- 2.3.7 Star semi-distances.- 2.3.8 Robinsonian dissimilarities.- 2.3.9 Strongly-Robinsonian dissimilarities.- 2.4 Inclusions.- 2.4.1 Some immediate inclusions.- 2.4.2 Other inclusions.- 2.5 The convex hulls.- 2.6 When are the inclusions strict?.- 2.7 The inclusions shown are exhaustive.- 2.8 Discussion.- 2.8.1 Further mathematical study.- 2.8.2 Extensions to other types of data.- 2.8.3 Connections with neighbouring disciplines.- 2.8.4 The future of dissimilarity analysis.- Acknowledgements.- References.- 3 Similarity functions.- 3.1 Introduction.- 3.2 Definitions. Examples.- 3.2.1 Definitions.- 3.2.2 Examples.- 3.2.2.1 Linear function.- 3.2.2.2 Homographic function.- 3.2.2.3 Quadratic function.- 3.2.2.4 Exponential function.- 3.2.2.5 Circular function.- 3.2.2.6 Graphical representations.- 3.3 The WM (DP) forms.- 3.3.1 Definitions and properties.- 3.3.2 The WM(D2) form.- Torgerson form.- 3.3.3 Transformations of D.- D? and the Euclidean distances.- 3.4 The WM(D) form.- 3.4.1 Geometrical interpretations and properties.- 3.4.2 About metric projection.- 3.4.3 WM(D) and “M1-type” distance.- Appendix: Some indices of dissimilarity for categorical variables.- References.- 4 An order-theoretic unification and generalisation of certain fundamental bijections in mathematical classification. I.- 4.1 Introduction and overview.- 4.2 A few notes on ordered sets.- 4.2.1 Introduction.- 4.2.2 Duality and order-isomorphisms.- 4.2.3 Semi-lattices and lattices.- 4.2.4 Residual and residuated mappings.- 4.3 Predissimilarities.- 4.4 Bijections.- 4.4.0 Overview.- 4.4.1 Indexed hierarchies (S finite, L = ?+).- 4.4.2 Dendrograms (S finite, L = ?+).- 4.4.3 Numerically stratified clusterings (S finite, L = ?+).- 4.4.4 Indexed regular generalised hierarchies (S arbitrary, L = ?+).- 4.4.5 Generalised dendrograms (S arbitrary, L = ?+).- 4.4.6 Prefilters (S arbitrary, L = ?+).- 4.4.6 Residual maps (S finite, L obeys LMIN and JSL).- 4.5 The unifying and generalising result.- 4.6 Further properties of an ordered set.- 4.7 Stratifications and generalised stratifications.- 4.8 Residual maps.- 4.9 On the associated residuated maps.- 4.10 Some applications to mathematical classification.- Acknowledgements.- Appendix A: Proofs.- References.- 5 An order-theoretic unification and generalisation of certain fundamental bijections in mathematical classification. II.- 5.1 Introduction and overview.- 5.2 The case E = A × B of theorem 4.5.1.- 5.3 Other aspects of the case E = A × B.- 5.3.1 Duality.- 5.3.2 Multiway data.- 5.3.3 Residual maps.- 5.4 Prefilters.- 5.5 Ultrametrics and reflexive level foliations.- 5.5.1 The main result.- 5.5.2 Remarks on Theorem 5.5.1.- 5.5.3 Variants of Theorem 5.5.1.- 5.6 On generalisations of indexed hierarchies.- 5.6.1 Introduction.- 5.6.2 Benzécri structures.- 5.6.3 Special cases of Benzécri structures.- 5.6.4 The condition LSU.- 5.7 Benzécri structures.- 5.8 Subdominants.- Acknowledgements.- Appendix B: Proofs.- References.- 6 The residuation model for the ordinal construction of dissimilarities and other valued objects.- 6.1 Introduction.- 6.2 Residuated mappings and closure operators.- 6.2.1 Residuated and residual mappings.- 6.2.2 Closure and anticlosure operators.- 6.3 Lattices of objects and lattices of values.- 6.3.1 Lattices.- 6.3.2 Distributivity.- 6.3.3 Lattices of objects: ten examples.- 6.3.4 Lattices of values.- 6.4 Valued objects.- 6.4.1 Consequences of the lattice structures hypothesis.- 6.4.2 Valued objects: definitions and examples.- 6.5 Lattices of valued objects.- 6.6 Notes and conclusions.- Acknowledgements.- References.- 7 On exchangeability-based equivalence relations induced by strongly Robinson and, in particular, by quadripolar Robinson dissimilarity matrices.- 7.1 Overview.- 7.1.1 Preamble.- 7.1.2 Quadripolar, Robinson and strongly Robinson matrices.- 7.1.3 Plan and principal results.- 7.2 Preliminaries.- 7.3 Quadripolar Robinson matrices of order four.- Equivalence relations induced by strongly Robinson matrices.- 7.4.1 Exchangeability and connectedness.- 7.4.2 Internal evenness.- 7.4.3 Logical relationships.- 7.5 Reduced forms.- 7.5.1 External evenness.- 7.5.2 Properties of reduced forms.- 7.6 Limiting r-forms of strongly Robinson matrices.- 7.4 Limiting r-forms of quadripolar Robinson matrices.- References.- 8 Dimensionality problems in L1-norm representations.- 8.1 Introduction.- 8.2 Preliminaries and notations.- 8.2.1 Dissimilarities.- 8.2.2 Some notations.- 8.2.3 Some characterizations.- 8.3 Dimensionality for semi-distances of Lp-type.- 8.4 Dimensionality for semi-distances of L1-type.- 8.5 Numerical characterizations of semi-distances of L1-type.- 8.5.1 Solving the general problem.- 8.5.2 Reducing the problem.- 8.5.3 Approximations.- 8.5.3.1 Least absolute deviations approximations.- 8.5.3.2 Least squares approximation.- 8.5.3.3 The additive constants.- 8.6 Appendices.- 8.6.1 Appendix 1.- 8.6.2 Appendix 2.- 8.6.3 Appendix 3.- 8.6.4 Appendix 4.- References.- Unified reference list.