doi: 10.3934/mfc.2022016
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

Concept and attribute reduction based on rectangle theory of formal concept

Department of Computer Science, Anhui University of Technology, Ma'anshan 243002, China

*Corresponding author: Jianqin Zhou

Received  September 2021 Revised  November 2021 Early access June 2022

Fund Project: The authors are supported by NSF grant of Anhui Province(No.1808085MF178), China

Based on rectangle theory of formal concept and set covering theory, the concept reduction preserving binary relations is investigated in this paper. It is known that there are three types of formal concepts: core concepts, relative necessary concepts and unnecessary concepts. First, we present the new judgment theorems for relative necessary concepts and unnecessary concepts. Second, we derive the bounds for both the maximum number of relative necessary concepts and the maximum number of unnecessary concepts. Third, based on rectangle theory of formal concept, a fast algorithm for reducing attributes while preserving the extensions for a set of formal concepts is proposed using the extension bit-array technique, which allows multiple context cells to be processed by a single 32-bit or 64-bit operator. Technically, the new algorithm could store both formal context and extension of a concept as bit-arrays, and we can use bit-operations to process set operations "or" as well as "and". One more merit is that the new algorithm does not need to consider other concepts in the concept lattice, thus the algorithm is explicit to understand and fast. Experiments demonstrate that the new algorithm is effective in the computation of attribute reductions.

Citation: Jianqin Zhou, Sichun Yang, Xifeng Wang. Concept and attribute reduction based on rectangle theory of formal concept. Mathematical Foundations of Computing, doi: 10.3934/mfc.2022016
References:
[1]

S. Andrews, A 'Best-of-Breed' approach for designing a fast algorithm for computing fixpoints of Galois Connections, Information Sciences, 295 (2015), 633-649.  doi: 10.1016/j.ins.2014.10.011.

[2]

S. Andrews, In-Close4 Program, 2017, https://sourceforge.net/projects/inclose/files/In-Close/.

[3]

L. CaoL. Wei and J. J. Qi, Concept reduction preserving binary relations, Pattern Recogn Artif Intell, 31 (2018), 516-524. 

[4]

C. Carpineto and G. Romano, A lattice conceptual clustering system and its application to browsing retrieval, Machine Learning, 24 (1996), 95-122.  doi: 10.1007/BF00058654.

[5]

A. Frank and A. Asuncion, UCI Machine Learning Repository, 2010, http://archive.ics.uci.edu/ml.

[6]

B. Ganter and R. Wille, Formal Concept Analysis: Mathematical Foundations, Springer-Verlag, Berlin, 1999. doi: 10.1007/978-3-642-59830-2.

[7]

S. O. Kuznetsov, On computing the size of a lattice and related decision problems, Order, 18 (2001), 313-321.  doi: 10.1023/A:1013970520933.

[8]

J. LiC. MeiL. Wang and J. Wang, On inference rules in decision formal contexts, International Journal of Computational Intelligence Systems, 8 (2015), 175-186. 

[9]

L. LiJ. Mia and B. Xie, Attribute reduction based on maximal rules in decision formal context, International Journal of Computational Intelligence Systems, 7 (2014), 1044-1053.  doi: 10.1080/18756891.2014.963972.

[10]

P. H. P. Nguyen and D. Corbett, A basic mathematical framework for conceptual graphs, IEEE Transactions on Knowledge and Data Engineering, 18 (2006), 261-271. 

[11]

Z. Pawlak, Rough sets, Internat. J. Comput. Inform. Sci., 11 (1982), 341-356.  doi: 10.1007/BF01001956.

[12]

R. Ren and L. Wei, The attribute reductions of three-way concept lattices, Knowl.-Based Syst., 99 (2016), 92-102. 

[13]

M. ShaoH. Yang and W. Wu, Knowledge reduction in formal fuzzy contexts, Knowl.-Based Syst., 73 (2015), 265-275. 

[14]

X. D. TuY. L. Wang and M. L. Zhang, Using formal concept analysis to identify negative correlations in gene expression data, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 13 (2006), 380-391. 

[15]

Q. Wan and L. Wei, Approximate concepts acquisition based on formal contexts, Knowl.-Based Syst., 75 (2015), 78-86. 

[16]

L. WeiL. CaoJ. J. Qi and W. Zhang, Concept reduction and concept characteristics in formal concept analysis (in Chinese), Sci. Sin. Inform., 50 (2020), 1817-1833.  doi: 10.1360/N112018-00272.

[17]

L. A. Zadeh, Fuzzy sets, Information and Control, 8 (1965), 338-353.  doi: 10.1016/S0019-9958(65)90241-X.

[18]

L. A. Zadeh, Toward a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic, Fuzzy Sets and Systems, 90 (1997), 111-127.  doi: 10.1016/S0165-0114(97)00077-8.

[19]

W. X. ZhangL. Wei and J. J. Qi, Attribute reduction in concept lattice based on discernibility matrix, Lecture Notes in Computer Science, 3642 (2005), 157-165. 

[20]

W. X. ZhangL. Wei and J. J. Qi, Attribute reduction theory and approach to concept lattice, Sci. China Ser. F, 48 (2005), 713-726.  doi: 10.1360/122004-104.

[21]

H. L. ZhiJ. J. QiT. Qian and L. Wei, Three-way dual concept analysis, International Journal of Approximate Reasoning, 114 (2019), 151-165.  doi: 10.1016/j.ijar.2019.08.010.

[22]

C. F. ZouD. Q. Zhang and J. F. Wan, Using concept lattice for personalized recommendation system design, IEEE Systems Journal, 11 (2017), 305-314. 

show all references

References:
[1]

S. Andrews, A 'Best-of-Breed' approach for designing a fast algorithm for computing fixpoints of Galois Connections, Information Sciences, 295 (2015), 633-649.  doi: 10.1016/j.ins.2014.10.011.

[2]

S. Andrews, In-Close4 Program, 2017, https://sourceforge.net/projects/inclose/files/In-Close/.

[3]

L. CaoL. Wei and J. J. Qi, Concept reduction preserving binary relations, Pattern Recogn Artif Intell, 31 (2018), 516-524. 

[4]

C. Carpineto and G. Romano, A lattice conceptual clustering system and its application to browsing retrieval, Machine Learning, 24 (1996), 95-122.  doi: 10.1007/BF00058654.

[5]

A. Frank and A. Asuncion, UCI Machine Learning Repository, 2010, http://archive.ics.uci.edu/ml.

[6]

B. Ganter and R. Wille, Formal Concept Analysis: Mathematical Foundations, Springer-Verlag, Berlin, 1999. doi: 10.1007/978-3-642-59830-2.

[7]

S. O. Kuznetsov, On computing the size of a lattice and related decision problems, Order, 18 (2001), 313-321.  doi: 10.1023/A:1013970520933.

[8]

J. LiC. MeiL. Wang and J. Wang, On inference rules in decision formal contexts, International Journal of Computational Intelligence Systems, 8 (2015), 175-186. 

[9]

L. LiJ. Mia and B. Xie, Attribute reduction based on maximal rules in decision formal context, International Journal of Computational Intelligence Systems, 7 (2014), 1044-1053.  doi: 10.1080/18756891.2014.963972.

[10]

P. H. P. Nguyen and D. Corbett, A basic mathematical framework for conceptual graphs, IEEE Transactions on Knowledge and Data Engineering, 18 (2006), 261-271. 

[11]

Z. Pawlak, Rough sets, Internat. J. Comput. Inform. Sci., 11 (1982), 341-356.  doi: 10.1007/BF01001956.

[12]

R. Ren and L. Wei, The attribute reductions of three-way concept lattices, Knowl.-Based Syst., 99 (2016), 92-102. 

[13]

M. ShaoH. Yang and W. Wu, Knowledge reduction in formal fuzzy contexts, Knowl.-Based Syst., 73 (2015), 265-275. 

[14]

X. D. TuY. L. Wang and M. L. Zhang, Using formal concept analysis to identify negative correlations in gene expression data, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 13 (2006), 380-391. 

[15]

Q. Wan and L. Wei, Approximate concepts acquisition based on formal contexts, Knowl.-Based Syst., 75 (2015), 78-86. 

[16]

L. WeiL. CaoJ. J. Qi and W. Zhang, Concept reduction and concept characteristics in formal concept analysis (in Chinese), Sci. Sin. Inform., 50 (2020), 1817-1833.  doi: 10.1360/N112018-00272.

[17]

L. A. Zadeh, Fuzzy sets, Information and Control, 8 (1965), 338-353.  doi: 10.1016/S0019-9958(65)90241-X.

[18]

L. A. Zadeh, Toward a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic, Fuzzy Sets and Systems, 90 (1997), 111-127.  doi: 10.1016/S0165-0114(97)00077-8.

[19]

W. X. ZhangL. Wei and J. J. Qi, Attribute reduction in concept lattice based on discernibility matrix, Lecture Notes in Computer Science, 3642 (2005), 157-165. 

[20]

W. X. ZhangL. Wei and J. J. Qi, Attribute reduction theory and approach to concept lattice, Sci. China Ser. F, 48 (2005), 713-726.  doi: 10.1360/122004-104.

[21]

H. L. ZhiJ. J. QiT. Qian and L. Wei, Three-way dual concept analysis, International Journal of Approximate Reasoning, 114 (2019), 151-165.  doi: 10.1016/j.ijar.2019.08.010.

[22]

C. F. ZouD. Q. Zhang and J. F. Wan, Using concept lattice for personalized recommendation system design, IEEE Systems Journal, 11 (2017), 305-314. 

Table 1.  Formal context $ (G, M, I) $
$ G $ $ a_1 $ $ a_2 $ $ a_3 $ $ a_4 $ $ a_5 $
1 0 1 1 0 0
2 1 1 0 0 0
3 1 0 0 0 0
4 0 0 0 0 1
5 0 0 0 1 1
6 0 0 1 1 1
7 1 1 1 0 0
$ G $ $ a_1 $ $ a_2 $ $ a_3 $ $ a_4 $ $ a_5 $
1 0 1 1 0 0
2 1 1 0 0 0
3 1 0 0 0 0
4 0 0 0 0 1
5 0 0 0 1 1
6 0 0 1 1 1
7 1 1 1 0 0
Table 2.  Formal concepts in Table 1
$ C_0=(\{1, 2, 3, 4, 5, 6, 7\}, \emptyset) $
$ C_4=(\{2, 3, 7\}, \{a_1\}) $ $ C_3=(\{1, 2, 7\}, \{a_2\}) $ $ C_2=(\{1, 6, 7\}, \{a_3\}) $ $ C_1=(\{4, 5, 6\}, \{a_5\}) $
$ C_5=(\{2, 7\}, \{a_1, a_2\}) $ $ C_6=(\{1, 7\}, \{a_2, a_3\}) $ $ C_7=(\{5, 6\}, \{a_4, a_5\}) $
$ C_9=(\{7\}, \{a_1, a_2, a_3\}) $ $ C_8=(\{6\}, \{a_3, a_4, a_5\}) $
$ C_{10}=(\emptyset, \{a_1, a_2, a_3 , a_4, a_5\}) $
$ C_0=(\{1, 2, 3, 4, 5, 6, 7\}, \emptyset) $
$ C_4=(\{2, 3, 7\}, \{a_1\}) $ $ C_3=(\{1, 2, 7\}, \{a_2\}) $ $ C_2=(\{1, 6, 7\}, \{a_3\}) $ $ C_1=(\{4, 5, 6\}, \{a_5\}) $
$ C_5=(\{2, 7\}, \{a_1, a_2\}) $ $ C_6=(\{1, 7\}, \{a_2, a_3\}) $ $ C_7=(\{5, 6\}, \{a_4, a_5\}) $
$ C_9=(\{7\}, \{a_1, a_2, a_3\}) $ $ C_8=(\{6\}, \{a_3, a_4, a_5\}) $
$ C_{10}=(\emptyset, \{a_1, a_2, a_3 , a_4, a_5\}) $
Table 3.  Formal context $ (G, M, I) $
$ G $ $ a_1 $ $ a_2 $ $ a_3 $ $ a_4 $ $ a_5 $
1 1 1 1 0 0
2 1 1 1 0 0
3 1 1 1 0 0
4 0 1 1 1 1
5 0 1 1 1 1
6 0 1 1 1 1
$ G $ $ a_1 $ $ a_2 $ $ a_3 $ $ a_4 $ $ a_5 $
1 1 1 1 0 0
2 1 1 1 0 0
3 1 1 1 0 0
4 0 1 1 1 1
5 0 1 1 1 1
6 0 1 1 1 1
Table 4.  Formal context $ (G, M, I) $
$ G $ $ a_1 $ $ a_2 $ $ a_3 $ $ a_4 $ $ a_5 $
1 1 1 1 0 0
2 1 1 1 0 0
3 1 1 1 0 0
4 0 1 1 1 1
5 0 1 1 1 1
6 0 1 1 1 1
7 1 1 0 0 0
8 1 0 1 0 0
$ G $ $ a_1 $ $ a_2 $ $ a_3 $ $ a_4 $ $ a_5 $
1 1 1 1 0 0
2 1 1 1 0 0
3 1 1 1 0 0
4 0 1 1 1 1
5 0 1 1 1 1
6 0 1 1 1 1
7 1 1 0 0 0
8 1 0 1 0 0
Table 5.  Formal context $ (G, M, I) $
$ G $ $ a_1 $ $ a_2 $ $ a_3 $ $ a_4 $ $ a_5 $
1 1 1 0 0 0
2 1 0 1 0 0
3 1 0 0 1 0
4 1 0 0 0 1
5 0 1 1 0 0
6 0 1 0 1 0
7 0 1 0 0 1
8 0 0 1 1 0
9 0 0 1 0 1
10 0 0 0 1 1
$ G $ $ a_1 $ $ a_2 $ $ a_3 $ $ a_4 $ $ a_5 $
1 1 1 0 0 0
2 1 0 1 0 0
3 1 0 0 1 0
4 1 0 0 0 1
5 0 1 1 0 0
6 0 1 0 1 0
7 0 1 0 0 1
8 0 0 1 1 0
9 0 0 1 0 1
10 0 0 0 1 1
Table 6.  Formal context $ (G, M, I ) $
$ G $ $ a_1 $ $ a_2 $ $ a_3 $ $ a_4 $
1 1 1 0 0
2 1 0 1 0
3 1 0 0 1
4 0 1 1 0
5 0 1 0 1
6 0 0 1 1
7 1 1 1 0
8 1 1 0 1
9 1 0 1 1
10 0 1 1 1
$ G $ $ a_1 $ $ a_2 $ $ a_3 $ $ a_4 $
1 1 1 0 0
2 1 0 1 0
3 1 0 0 1
4 0 1 1 0
5 0 1 0 1
6 0 0 1 1
7 1 1 1 0
8 1 1 0 1
9 1 0 1 1
10 0 1 1 1
Table 7.  Computation of attribute reductions with the new algorithm
Mushroom Nursery
$ |G|\times |M| $ $ 8,124\times 115 $ $ 12,960\times 30 $
Number of concepts 512 512
Time in seconds 4.218 0.582
Number of reduced columns 19 2
Mushroom Nursery
$ |G|\times |M| $ $ 8,124\times 115 $ $ 12,960\times 30 $
Number of concepts 512 512
Time in seconds 4.218 0.582
Number of reduced columns 19 2
[1]

Shiri Artstein-Avidan and Vitali Milman. A characterization of the concept of duality. Electronic Research Announcements, 2007, 14: 42-59. doi: 10.3934/era.2007.14.42

[2]

Sergio R. López-Permouth, Benigno R. Parra-Avila, Steve Szabo. Dual generalizations of the concept of cyclicity of codes. Advances in Mathematics of Communications, 2009, 3 (3) : 227-234. doi: 10.3934/amc.2009.3.227

[3]

Aram Arutyunov, Dmitry Karamzin, Fernando L. Pereira. On a generalization of the impulsive control concept: Controlling system jumps. Discrete and Continuous Dynamical Systems, 2011, 29 (2) : 403-415. doi: 10.3934/dcds.2011.29.403

[4]

G. Bellettini, Giorgio Fusco, Nicola Guglielmi. A concept of solution and numerical experiments for forward-backward diffusion equations. Discrete and Continuous Dynamical Systems, 2006, 16 (4) : 783-842. doi: 10.3934/dcds.2006.16.783

[5]

Sang-Heon Lee. Development of concurrent structural decentralised discrete event system using bisimulation concept. Numerical Algebra, Control and Optimization, 2016, 6 (3) : 305-317. doi: 10.3934/naco.2016013

[6]

Marco Sarich, Natasa Djurdjevac Conrad, Sharon Bruckner, Tim O. F. Conrad, Christof Schütte. Modularity revisited: A novel dynamics-based concept for decomposing complex networks. Journal of Computational Dynamics, 2014, 1 (1) : 191-212. doi: 10.3934/jcd.2014.1.191

[7]

Hsien-Chung Wu. Solving the interval-valued optimization problems based on the concept of null set. Journal of Industrial and Management Optimization, 2018, 14 (3) : 1157-1178. doi: 10.3934/jimo.2018004

[8]

Seigan Hayashi, Chris J. Cameron, Stefanie Gutschmidt. A novel sensing concept utilizing targeted, complex, nonlinear MEMS dynamics. Journal of Computational Dynamics, 2022, 9 (3) : 483-503. doi: 10.3934/jcd.2022012

[9]

Thomas Espitau, Antoine Joux. Certified lattice reduction. Advances in Mathematics of Communications, 2020, 14 (1) : 137-159. doi: 10.3934/amc.2020011

[10]

Éder Rítis Aragão Costa. An extension of the concept of exponential dichotomy in Fréchet spaces which is stable under perturbation. Communications on Pure and Applied Analysis, 2019, 18 (2) : 845-868. doi: 10.3934/cpaa.2019041

[11]

Palash Sarkar, Subhadip Singha. Classical reduction of gap SVP to LWE: A concrete security analysis. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021004

[12]

Hiroaki Yoshimura, Jerrold E. Marsden. Dirac cotangent bundle reduction. Journal of Geometric Mechanics, 2009, 1 (1) : 87-158. doi: 10.3934/jgm.2009.1.87

[13]

Katarzyna Grabowska, Paweƚ Urbański. Geometry of Routh reduction. Journal of Geometric Mechanics, 2019, 11 (1) : 23-44. doi: 10.3934/jgm.2019002

[14]

Inês Cruz, M. Esmeralda Sousa-Dias. Reduction of cluster iteration maps. Journal of Geometric Mechanics, 2014, 6 (3) : 297-318. doi: 10.3934/jgm.2014.6.297

[15]

Laura Luzzi, Ghaya Rekaya-Ben Othman, Jean-Claude Belfiore. Algebraic reduction for the Golden Code. Advances in Mathematics of Communications, 2012, 6 (1) : 1-26. doi: 10.3934/amc.2012.6.1

[16]

Jean-François Babadjian, Francesca Prinari, Elvira Zappale. Dimensional reduction for supremal functionals. Discrete and Continuous Dynamical Systems, 2012, 32 (5) : 1503-1535. doi: 10.3934/dcds.2012.32.1503

[17]

Martins Bruveris, David C. P. Ellis, Darryl D. Holm, François Gay-Balmaz. Un-reduction. Journal of Geometric Mechanics, 2011, 3 (4) : 363-387. doi: 10.3934/jgm.2011.3.363

[18]

Hayato Chiba, Georgi S. Medvedev. The mean field analysis of the kuramoto model on graphs Ⅱ. asymptotic stability of the incoherent state, center manifold reduction, and bifurcations. Discrete and Continuous Dynamical Systems, 2019, 39 (7) : 3897-3921. doi: 10.3934/dcds.2019157

[19]

Marc Massot. Singular perturbation analysis for the reduction of complex chemistry in gaseous mixtures using the entropic structure. Discrete and Continuous Dynamical Systems - B, 2002, 2 (3) : 433-456. doi: 10.3934/dcdsb.2002.2.433

[20]

Georg Vossen, Stefan Volkwein. Model reduction techniques with a-posteriori error analysis for linear-quadratic optimal control problems. Numerical Algebra, Control and Optimization, 2012, 2 (3) : 465-485. doi: 10.3934/naco.2012.2.465

 Impact Factor: 

Metrics

  • PDF downloads (69)
  • HTML views (35)
  • Cited by (0)

Other articles
by authors

[Back to Top]