logo

SCIENTIA SINICA Informationis, Volume 50 , Issue 12 : 1817(2020) https://doi.org/10.1360/N112018-00272

Concept reduction and concept characteristics in formal concept analysis

More info
  • ReceivedOct 14, 2018
  • AcceptedAug 9, 2019
  • PublishedNov 18, 2020

Abstract

Formal concept analysis, which is based on formal contexts and concept lattices, is a data analysis method. Formal concepts reflect the relationship between objects and attributes and realize a formal description of concepts in philosophy. To simplify the information description, this paper proposes concept reduction in the formal concept analysis framework and studies the related theories on concept reduction preserving binary relations. In addition, characteristics analysis of three types of concepts that play different roles in reduction processing is performed from the perspective of operators and a Boolean matrix. Finally, a method to calculate concept reduction is provided.


Funded by

国家自然科学基金(61772021,11371014)


References

[1] Wille R. Restructuring lattice theory: an approach based on hierarchies of concepts. In: Proceedings of the NATO Advanced Study Institute, 1982. 445--470. Google Scholar

[2] Ganter B, Wille R. Formal Concept Analysis: Mathematical Foundations. Berlin: Springer, 1999. Google Scholar

[3] Yao Y Y. Concept lattices in rough set theory. In: Proceedings of Annual Meeting of the North American Fuzzy Information Processing Society, New York, 2004. 796--801. Google Scholar

[4] Fu H, Nguifo E M. A parallel algorithm to generate formal concepts for large data. In: Proceedings of International Conference on Formal Concept Analysis, Berlin, 2004. 394--401. Google Scholar

[5] Wang D X, Hu X G, Liu X P. Novel attribute induction algorithm based on quantized concept lattice. J Xi'an Jiaotong Univ, 2007, 41: 176--179. Google Scholar

[6] Krajca P, Outrata J, Vychodil V. Advancesin algorithms based on CbO. In: Proceedings of the 7th International Conference on Concept Lattices and Their Applications, Sevilla, 2010. 325--337. Google Scholar

[7] Andrews S. A 'Best-of-Breed' approach for designing a fast algorithm for computing fixpoints of Galois Connections. Inf Sci, 2015, 295: 633-649 CrossRef Google Scholar

[8] Zhang W, Wei L, Qi J J. Attribute reduction theory and approach to concept lattice. Sci China Ser F-Inf Sci, 2005, 48: 713-726 CrossRef Google Scholar

[9] Wei L. Reduction theory and approach to rough set and concept lattice. Dissertation for Ph.D. Degree. Xi'an: Xi'an Jiaotong University. 2005. Google Scholar

[10] Wang X, Ma J M. A novel approach to attribute reduction in concept lattices. In: Proceedings of the 1st International Conference on Rough Sets and Knowledge Technology, Chongqing, 2006. 522--529. Google Scholar

[11] Li T J, Li M Z, Gao Y. ATTRIBUTE REDUCTION OF CONCEPT LATTICE BASED ON IRREDUCIBLE ELEMENTS. Int J Wavelets Multiresolut Inf Process, 2013, 11: 1350046 CrossRef Google Scholar

[12] Wei-Zhi Wu , Yee Leung , Ju-Sheng Mi . Granular Computing and Knowledge Reduction in Formal Contexts. IEEE Trans Knowl Data Eng, 2009, 21: 1461-1474 CrossRef Google Scholar

[13] Wei L, Qi J J, Zhang W X. Attribute reduction theory of concept lattice based on decision formal contexts. Sci China Ser F-Inf Sci, 2008, 51: 910-923 CrossRef Google Scholar

[14] Shao M W, Li K W. Attribute reduction in generalized one-sided formal contexts. Inf Sci, 2017, 378: 317-327 CrossRef Google Scholar

[15] Zhang Q H, Wang G Y, Liu X Q. Rule acquisition algorithm based on maximal granule. Pattern Recogn Artif Intell, 2012, 25: 388--396. Google Scholar

[16] Li J, Mei C, Wang J. Rule-preserved object compression in formal decision contexts using concept lattices. Knowledge-Based Syst, 2014, 71: 435-445 CrossRef Google Scholar

[17] Zhu Z C, Wei L. Two-way rules acquisition based on class contexts. J Northwest Univ (Nat Sci Edit), 2015, 45: 517--524. Google Scholar

[18] Liu L, Wei L, Qian T. Three-way rules extraction in formal decision contexts with confidence. J Shandong Univ (Nat Sci), 2017, 52: 101--110. Google Scholar

[19] Yao Y. Rough-set concept analysis: Interpreting RS-definable concepts based on ideas from formal concept analysis. Inf Sci, 2016, 346-347: 442-462 CrossRef Google Scholar

[20] Qi J J, Wei L, Li Z Z. A partitional view of concept lattice. In: Proceedings of the 10th International Conference on Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing, Regina, 2005. 74--83. Google Scholar

[21] Fuentes-González R, Burusco A. The study of the L-fuzzy concept lattice. Mathware Soft Comput, 1994, 1: 209--218. Google Scholar

[22] B?lohlávek R. Concept lattices and order in fuzzy logic. Ann Pure Appl Logic, 2004, 128: 277-298 CrossRef Google Scholar

[23] Yao Y Y. An outline of a theory of three-way decisions. In: Proceedings of Rough Sets and Current Trends in Computing, Chengdu, 2012. 1--17. Google Scholar

[24] Qi J J, Wei L, Yao Y Y. Three-way formal concept analysis. In: Proceedings of Rough Sets and Knowledge Technology, Shanghai, 2014. 732--741. Google Scholar

[25] Qi J, Qian T, Wei L. The connections between three-way and classical concept lattices. Knowledge-Based Syst, 2016, 91: 143-151 CrossRef Google Scholar

[26] Huang C, Li J, Mei C. Three-way concept learning based on cognitive operators: An information fusion viewpoint. Int J Approximate Reasoning, 2017, 83: 218-242 CrossRef Google Scholar

[27] Qi J J, Wang W W. A multithreaded parallel algorithm for constructing three-way concepts. J Xi'an Jiaotong Univ, 2017, 51: 116--121. Google Scholar

[28] Qian T, Wei L, Qi J. Constructing three-way concept lattices based on apposition and subposition of formal contexts. Knowledge-Based Syst, 2017, 116: 39-48 CrossRef Google Scholar

[29] Chen X, Wei L, Qian T. Attribute reduction in formal decision contexts based on AE-concept lattices. J Shandong Univ (Nat Sci), 2017, 52: 95--103. Google Scholar

[30] Li J, Mei C, Xu W. Concept learning via granular computing: A cognitive viewpoint. Inf Sci, 2015, 298: 447-467 CrossRef Google Scholar

[31] Zhi H, Li J. Granule description based on formal concept analysis. Knowledge-Based Syst, 2016, 104: 62-73 CrossRef Google Scholar

[32] Qi J, Wei L, Wan Q. Multi-level granularity in formal concept analysis. Granul Comput, 2019, 4: 351-362 CrossRef Google Scholar

[33] Li J, Mei C, Lv Y. Incomplete decision contexts: Approximate concept construction, rule acquisition and knowledge reduction. Int J Approximate Reasoning, 2013, 54: 149-165 CrossRef Google Scholar

[34] Djouadi Y, Dubois D, Prade P. Graduality, uncertainty and typicality in formal concept analysis. In: 35 years of fuzzy set theory. Berlin: Springer, 2010. 127--147. Google Scholar

[35] Yao Y. Interval sets and three-way concept analysis in incomplete contexts. Int J Mach Learn Cyber, 2017, 8: 3-20 CrossRef Google Scholar

[36] Ren R, Wei L, Yao Y. An analysis of three types of partially-known formal concepts. Int J Mach Learn Cyber, 2018, 9: 1767-1783 CrossRef Google Scholar

[37] Li M, Wang G. Approximate concept construction with three-way decisions and attribute reduction in incomplete contexts. Knowledge-Based Syst, 2016, 91: 165-178 CrossRef Google Scholar

[38] Zhi H L. Knowledge representation on incomplete formal context. Comput Sci, 2015, 42: 276--278. Google Scholar

[39] Wu W Z, Qian Y, Li T J. On rule acquisition in incomplete multi-scale decision tables. Inf Sci, 2017, 378: 282-302 CrossRef Google Scholar

[40] Ren R, Wei L. The attribute reductions of three-way concept lattices. Knowledge-Based Syst, 2016, 99: 92-102 CrossRef Google Scholar

[41] Wang Z, Wei L. Attribute reduction of partially-known formal concept lattices for incomplete contexts. Comput Sci, 2018, 45: 73--78. Google Scholar

[42] Keprt A, Snasel V. Binary factor analysis with help of formal concepts. In: Proceedings of the International Workshop on Concept Lattices and Their Applications, Ostrava, 2004. 90--101. Google Scholar

[43] Belohlavek R, Vychodil V. On Boolean factor analysis with formal concept as factors. SCIS & ISIS, 2006. 1054--1059. Google Scholar

[44] Belohlavek R, Vychodil V. Discovery of optimal factors in binary data via a novel method of matrix decomposition. J Comput Syst Sci, 2010, 76: 3-20 CrossRef Google Scholar

[45] Belohlavek R, Trnecka M. From-below approximations in Boolean matrix factorization: Geometry and new algorithm. J Comput Syst Sci, 2015, 81: 1678-1697 CrossRef Google Scholar

[46] Trnecka M, Trneckova M. Data reduction for Boolean matrix factorization algorithms based on formal concept analysis. Knowledge-Based Syst, 2018, 158: 75-80 CrossRef Google Scholar

[47] Cao L, Wei L, Qi J J. Concept reduction preserving binary relations. Pattern Recogn Artif Intell, 2018, 31: 516--524. Google Scholar

[48] Kim K H. He S Y, Kong D Y, Huang Z L, et al. Boolean Matrix Theory and Applications. Beijing: Knowledge Publishing House. 1987 [Kim K H, 著. 何善??, 孔德涌, 黄正篱, 等译. 布尔矩阵理论及其应用. 北京: 知识出版社, 1987]. Google Scholar

[49] Glodeanu C. Triadic factor analysis. In: Proceedings of the 7th International Conference on Concept Lattices and Their Applications, Sevilla, 2010. 127--138. Google Scholar

  • Figure 1

    The concept lattice corresponding to example 1

  • Figure 2

    A concept reduct $\mathcal{F}_{1}$ of example 1

  • Table 1   The context of living beings and water $(G,~M,~I)$
    $G$ $a$ $b$ $c$ $d$ $e$ $f$ $g$ $h$ $i$
    $1$$1$$1$ $0$$0$$0$$0$$1$$0$$0$
    $2$$1$$1$ $0$$0$$0$$0$$1$$1$$0$
    $3$$1$$1$ $1$$0$$0$$0$$1$$1$$0$
    $4$$1$$0$ $1$$0$$0$$0$$1$$1$$1$
    $5$$1$$1$ $0$$1$$0$$1$$0$$0$$0$
    $6$$1$$1$ $1$$1$$0$$1$$0$$0$$0$
    $7$$1$$0$ $1$$1$$1$$0$$0$$0$$0$
    $8$$1$$0$ $1$$1$$0$$1$$0$$0$$0$
  • Table 2   The concept lattice corresponding to the formal context in example 1
    Label Concept Label Concept Label ConceptLabel ConceptLabel Concept
    $c_{1}$$(\emptyset,M)$ $c_{5}$$(6,~abcdf)$$c_{9}$$(36,~abc)$$c_{13}$$(234,~agh)$$c_{17}$$(12356,~ab)$
    $c_{2}$$(4,~acghi)$ $c_{6}$$(34,~acgh)$$c_{10}$$(678,~acd)$$c_{14}$$(568,~adf)$$c_{18}$$(5678,~ad)$
    $c_{3}$$(3,~abcgh)$ $c_{7}$$(23,~abgh)$$c_{11}$$(68,~acdf)$$c_{15}$$(1234,~ag)$$c_{19}$$(G,~a)$
    $c_{4}$$(7,~acde)$ $c_{8}$$(123,~abg)$$c_{12}$$(56,~abdf)$$c_{16}$$(34678,~ac)$
  • Table 3   The classification of example 1
    Type Concept
    Core concept $c_{2}$, $c_{4}$
    Relatively necessary concept$c_{3}$, $c_{6}$, $c_{7}$, $c_{8}$, $c_{9}$, $c_{10}$, $c_{11}$, $c_{12}$, $c_{13}$, $c_{14}$, $c_{15}$, $c_{16}$, $c_{17}$
    Unnecessary concept $c_{1}$, $c_{5}$, $c_{18}$, $c_{19}$
  • Table 4   A part of pairs and concepts
    Serial number $k$Pair Concept set ${\rm~CS}_{k}$Serial number $k$Pair Concept set ${\rm~CS}_{k}$
    1$(1,~b)$ $\{c_{8},~c_{17}\}$8$(3,~g)$ $\{c_{3},~c_{6},~c_{7},~c_{8},~c_{13},~c_{15}\}$
    2$(1,~g)$ $\{c_{8},~c_{15}\}$9$(3,~h)$ $\{c_{3},~c_{6},~c_{7},~c_{13}\}$
    3$(2,~b)$ $\{c_{7},~c_{8},~c_{17}\}$10$(5,~b)$$\{c_{12},~c_{17}\}$
    4$(2,~g)$ $\{c_{7},~c_{8},~c_{13},~c_{15}\}$11$(5,~f)$$\{c_{12},~c_{14}\}$
    5$(2,~h)$ $\{c_{7},~c_{13}\}$12$(8,~c)$$\{c_{10},~c_{11},~c_{16}\}$
    6$(3,~b)$ $\{c_{3},~c_{7},~c_{8},~c_{9},~c_{17}\}$13$(8,~f)$$\{c_{11},~c_{14}\}$
    7$(3,~c)$ $\{c_{3},~c_{6},~c_{9},~c_{16}\}$
  • Table 5   Pairs and concepts corresponding to the minimum concept intervals
    Serial number $k$ Minimum concept interval Pair Concept set ${\rm~CS}_{k}$
    1$\mathcal{I}_{1b}$$(1,~b)$ $\{c_{8},~c_{17}\}$
    2$\mathcal{I}_{1g}$$(1,~g)$ $\{c_{8},~c_{15}\}$
    5$\mathcal{I}_{2h}$$(2,~h)$ $\{c_{7},~c_{13}\}$
    7$\mathcal{I}_{3c}$$(3,~c)$ $\{c_{3},~c_{6},~c_{9},~c_{16}\}$
    10$\mathcal{I}_{5b}$$(5,~b)$$\{c_{12},~c_{17}\}$
    11$\mathcal{I}_{5f}$$(5,~f)$$\{c_{12},~c_{14}\}$
    12$\mathcal{I}_{8c}$$(8,~c)$$\{c_{10},~c_{11},~c_{16}\}$
    13$\mathcal{I}_{8f}$$(8,~f)$$\{c_{11},~c_{14}\}$