On critical sets of a finite Moore family. (English) Zbl 1306.62139

Summary: Cluster collections obtained within the framework of most cluster structures studied in data analysis and classification are essentially Moore families. In this paper, we propose a simple intuitive necessary and sufficient condition for some subset of objects to be a critical set of a finite Moore family. This condition is based on a new characterization of quasi-closed sets. Moreover, we provide a necessary condition for a subset containing more than \(k\) objects (\(k\geq 2\)) to be a critical set of a \(k\)-weakly hierarchical Moore family. Finally, as a consequence of this result, we identify critical sets of some \(k\)-weakly hierarchical Moore families and thereby generalize a result earlier obtained by Domenach and Leclerc in the particular case of weak hierarchies.


62H30 Classification and discrimination; cluster analysis (statistical aspects)
06A15 Galois correspondences, closure operators (in relation to ordered sets)
62-07 Data analysis (statistics) (MSC2010)
Full Text: DOI


[1] Armstrong WW (1974) Dependency structures of data base relationships. Inf Process 74: 580–583
[2] Bandelt HJ (1992) Four point characterization of the dissimilarity functions obtained from indexed closed weak hierarchies Mathematisches Seminar. Universität Hamburg, Germany
[3] Bandelt HJ, Dress AWM (1989) Weak hierarchies associated with similarity measures: an additive clustering technique. Bull Math Biol 51: 113–166 · Zbl 0666.62058
[4] Bandelt HJ, Dress AWM (1994) An order theoretic framework for overlapping clustering. Discrete Math 136: 21–37 · Zbl 0832.92032
[5] Barbut M, Monjardet B (1970) Ordre et classification. Hachette, Paris · Zbl 0267.06001
[6] Barthélemy JP, Brucker F (2001) NP-hard approximation problems in overlapping clustering. J Classif 18: 159–183 · Zbl 1040.91084
[7] Benayade M, Diatta J (2008) Cluster structures and collections of galois closed entity sets. Discrete Appl Math 156: 1295–1307 · Zbl 1369.06002
[8] Bertrand P (2008) Set systems for which each set properly intersects at most one other set - Application to cluster analysis. Discrete Appl Math 156(8): 1220–1236 · Zbl 1295.05247
[9] Bertrand P, Janowitz MF (2003) The k-weak hierarchical representations: an extension of the indexed closed weak hierarchies. Discrete Appl Math 127: 199–220 · Zbl 1012.62067
[10] Birkhoff G (1967) Lattice theory, 3rd edn. Coll Publ., XXV, American Mathematical Society, Providence, RI · Zbl 0153.02501
[11] Caspard N (1999) A characterization theorem for the canonical basis of a closure operator. Order 16: 227–230 · Zbl 0959.06005
[12] Caspard N, Monjardet B (2003) The lattices of closure systems, closure operators, and implicational systems on a finite set: a survey. Discrete Appl Math 127: 241–269 · Zbl 1026.06008
[13] Day A (1992) The lattice theory of functional dependencies and normal decompositions. Int J Algebra Comput 2: 409–431 · Zbl 0798.68049
[14] Demetrovics J, Libkin L, Muchnik I (1992) Functional dependencies in relational databases: a lattice point of view. Discrete Appl Math 40: 155–185 · Zbl 0767.68029
[15] Diatta J (1997) Dissimilarités multivoies et généralisations d’hypergraphes sans triangles. Math Inf Sci hum 138: 57–73 · Zbl 0910.62062
[16] Diatta J, Fichet B (1994) From Apresjan hierarchies and Bandelt-Dress weak hierarchies to quasi-hierarchies. In: Diday E, Lechevalier Y, Schader M, Bertrand P, Burtschy B (eds) New approaches in classification and data analysis. Springer, New York, pp 111–118
[17] Diday E (1984) Une représentation visuelle des classes empiétantes: les pyramides. Tech. Rep. 291, INRIA, France
[18] Domenach F, Leclerc B (2004) Closure systems, implicational systems, overhanging relations and the case of hierarchical classification. Math Soc Sci 47: 349–366 · Zbl 1059.93007
[19] Fichet B (1986) Data analysis: geometric and algebraic structures. In: Prohorov YA, Sazonov VV (eds) Proceedings of the first world congress of the BERNOULLI SOCIETY, Tachkent, 1987, vol 2. V.N.U. Science, pp 123–132
[20] Guigues JL, Duquenne V (1986) Famille non redondante d’implications informatives résultant d’un tableau de données binaires. Mathématiques et Sciences humaines 95: 5–18
[21] Koshevoy GA (1999) Choice functions and abstract convex geometries. Math Soc Sci 38: 35–44 · Zbl 0943.91031
[22] Maier D (1983) The theory of relational databases. Computer Science Press, Rockville, MD · Zbl 0519.68082
[23] Morgado J (1962) A characterization of the closure operators by means of one axiom. Port Math 21: 155–156 · Zbl 0107.25203
[24] Plott CR (1973) Path independence, rationality and social choice. Econometrica 41: 1075–1091 · Zbl 0297.90017
[25] Stumme G, Taouil R, Bastide Y, Pasquier N, Lakhal L (2001) Intelligent structuring and reducing of association rules with formal concept analysis. In: Baader F, Brewka G, Eiter T (eds) Advances in artificial intelligence, Springer, San Jose, California, KI 2001, LNAI 2174, pp 335–350 · Zbl 1007.68592
[26] Wille R (1982) Restructuring lattice theory: an approach based on hierarchies of concepts. In: Rival I (eds) Ordered sets. Reidel, Dordrecht-Boston, pp 445–470
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.