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


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}\}$