×

Valuations and closure operators on finite lattices. (English) Zbl 1226.06006

Summary: Let \(L\) be a lattice. A function \(f : L \rightarrow \mathbb R\) (usually called evaluation) is submodular if \(f(x \wedge y)+f(x \vee y)\leq f(x)+f(y)\), supermodular if \(f(x \wedge y)+f(x \vee y)\geq f(x)+f(y)\), and modular if it is both submodular and supermodular. Modular functions on a finite lattice form a finite-dimensional vector space. For finite distributive lattices, we compute this (modular) dimension. This turns out to be another characterization of distributivity (Theorem 3.9). We also present a correspondence between isotone submodular evaluations and closure operators on finite lattices (Theorem 5.5). This interplay between closure operators and evaluations should be understood as building a bridge between qualitative and quantitative data analysis.

MSC:

06D05 Structure and representation theory of distributive lattices
06A15 Galois correspondences, closure operators (in relation to ordered sets)

Software:

CLOSET; FooCA
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Aigner, M., Combinatorial theory, (1979), Springer · Zbl 0415.05001
[2] Carpineto, Claudio; Romano, Giovanni, Concept data analysis: theory and applications, ISBN: 978-0-470-85055-8, (2004), Wiley · Zbl 1083.68117
[3] Davey, B.A.; Priestley, H.A., Introduction to lattices and order, (2002), Cambridge · Zbl 1002.06001
[4] Dominich, S., The modern algebra of information retrieval, (2008), Springer-Verlag Berlin Heidelberg · Zbl 1149.68025
[5] Düntsch, I.; Gediga, G., Rough set data analysis, () · Zbl 0983.68194
[6] Ganter, B.; Wille, R., Formal concept analysis. mathematical foundations, (1999), Springer · Zbl 0909.06001
[7] Glivenko, V., Géometrie des systèmes de choses normées, American journal of mathematics, 58, 4, 799-828, (1936) · JFM 62.0647.02
[8] Grabisch, M., Belief functions on lattices, International journal of intelligent systems, 24, 76-95, (2009) · Zbl 1157.68063
[9] Guigues, J.L.; Duquenne, V., Familles minimales d’implications informatives résultant d’un tableau de données binaires, Mathématiques et sciences humaines, 95, 5-18, (1986)
[10] Heilpern, S., Applications of non additive set functions in decision making and insurance, Tatra mountains mathematical publications, 16, 295-310, (1999) · Zbl 0948.28014
[11] B. Koester, FooCA—Web Information Retrieval with Formal Concept Analysis, Verlag Allgemeine Wissenschaft, Mühltal (2006) ISBN 9783-935924-06-1 (3-935924-06-2).
[12] Kung, J.P.S.; Rota, G.C.; Yan, C.H., Combinatorics: the rotaway, (2009), Cambridge University Press
[13] Rough set theory and granular computing, () · Zbl 1030.68087
[14] Monjardet, B., Metrics on partially ordered sets—a survey, Discrete mathematics, 35, 173-184, (1981) · Zbl 0463.46016
[15] Nguyen, H.Q., Semimodular functions and combinatorial geometries, Transactions of the American mathematical society, 238, 355-383, (1978) · Zbl 0411.05029
[16] Pasquier, N.; Bastide, Y.; Taouil, T.; Lakhal, L., Efficient mining of association rules using closed itemset lattices, Information systems, 24, 1, 25-46, (1999)
[17] N. Pasquier, Y. Bastide, R. Taouil, L. Lakhal, Discovering frequent closed itemsets for association rules, in: Database Theory-ICDT’99, 1999, pp. 398-416. · Zbl 0983.68511
[18] Pasquier, N.; Taouil, R.; Bastide, Y.; Stumme, G.; Lakhal, L., Generating a condensed representation for association rules, Journal of intelligent information systems, 24, 1, 29-60, (2005) · Zbl 1071.68022
[19] Pawlak, Z.; Skowron, A., Rudiments of rough sets, Information sciences, 177, 3-27, (2007) · Zbl 1142.68549
[20] Pawlak, Z., ()
[21] Smiley, M.F., A note on measure functions in lattice, Bulletin of the American mathematical society, 46, 4, 239-241, (1940) · Zbl 0024.38601
[22] Stumme, G.; Taouil, R.; Bastide, Y.; Pasquier, N.; Lakhal, L., Computing iceberg concept lattices with titanic, Data & knowledge engineering, 42, 2, 189-222, (2002) · Zbl 0996.68046
[23] Valášková, L.; Struk, P., Preservation of distinguished fuzzy measure classes by distortion, (), 175-182 · Zbl 1109.28303
[24] Wang, Jianyong; Han, Jiawei; Pei, Jian, Closet+: searching for the best strategies for mining frequent closed itemsets, (), 236-245
[25] Wille, R., Restructuring lattice theory: an approach based on hierarchies of concepts, (), 445-470
[26] Mohammed J. Zaki, Mitsunori Ogihara, Theoretical foundations of association rules, in: 3rd ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, 1998.
[27] Mohammed Javeed Zaki, Ching-Jiu Hsiao, Charm: An efficient algorithm for closed itemset mining, in: Proceedings of the Second SIAM International Conference on Data Mining, Arlington, VA, USA, April 11-13, 2002.
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.