Unified fast algorithms for building concept lattices

Xifeng Wang; Jianqin Zhou; Sichun Yang

doi:10.3934/mfc.2023037

Article Contents

2025, Volume 8, Issue 1: 50-63. Doi: 10.3934/mfc.2023037

This issue Previous Article On interval-valued vector variational-like inequalities and vector optimization problems with generalized approximate invexity via convexificators Next Article A generalization of szász operators with the help of new kind Appell polynomials

Unified fast algorithms for building concept lattices

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

^*Corresponding author: Jianqin Zhou
^*Corresponding author: Jianqin Zhou

Received: September 2022

Revised: April 2023

Early access: September 5, 2023

Published online: September 5, 2023

Abstract / Introduction Full Text(HTML) Figure(0) / Table(8) Related Papers Cited by

Abstract

There are various algorithms for computing various concepts from a formal context. In this paper, based on the logical representations of various concepts, we first prove that the following concepts are all equivalent to formal concept in some forms: object oriented concept, object-induced three-way concept, object-induced three-way attribute-oriented concept, attribute-induced three-way dual concept and common-possible concept. Second, based on the fast In-Close4 algorithm for computing formal concept lattice, much concise and unified algorithms are proposed to construct all five different kinds of concept lattice respectively. Both theoretical analysis and experiment results demonstrate that every proposed algorithm is simple and effective. As far as we know, various concepts are all equivalent to some form of formal concepts, which provides a new perspective for us to study these concepts and their applications.

Keywords:

Mathematics Subject Classification: Primary: 68T35, 68T30.

Citation:

Full Text(HTML)

Table 1. $(U, A, \mathbb{I})$

$U$	$ 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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Table 3. $(U, B, J)$

$U$	$ b_1 $	$ b_2 $	$ b_3 $	$ b_4 $	$ b_5$
1	1	0	0	1	1
2	0	0	1	1	1
3	0	1	1	1	1
4	1	1	1	1	0
5	1	1	1	0	0
6	1	1	0	0	0
7	0	0	0	1	1

| Show Table

DownLoad: CSV

Table 4. $(U, A, I, B, J)$

$U$	$ a_1 $	$ a_2 $	$ a_3 $	$ a_4 $	$ a_5$	$ b_1 $	$ b_2 $	$ b_3 $	$ b_4 $	$ b_5$
1	0	1	1	0	0	1	0	0	1	1
2	1	1	0	0	0	0	0	1	1	1
3	1	0	0	0	0	0	1	1	1	1
4	0	0	0	0	1	1	1	1	1	0
5	0	0	0	1	1	1	1	1	0	0
6	0	0	1	1	1	1	1	0	0	0
7	1	1	1	0	0	0	0	0	1	1

| Show Table

DownLoad: CSV

Table 5. Time (in seconds) comparison under different fill ratios

	data7_01	data7_02	data7_03	data7_04	data7_05
$\|G\|\times \|M\|$	$26\times 6$	$26\times 6$	$26\times 6$	$26\times 6$	$26\times 6$
Fill ratio	0.494	0.532	0.513	0.468	0.474
#concepts	38	43	38	45	38
Qi's method	242.3	271.9	324.1	520.4	483.9
Qian's method	18.68	21.96	22.01	20.09	18.65
Yang's method	3.442	3.457	3.451	3.406	3.518
Algorithm 2	0.029	0.039	0.030	0.036	0.033

| Show Table

DownLoad: CSV

Table 6. Compound context $(U, I, V, J, A)$

$U$	$ 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
$v_1$	1	0	0	1	1
$v_2$	0	0	1	1	1
$v_3$	0	1	1	1	1
$v_4$	1	1	1	1	0
$v_5$	1	1	1	0	0
$v_6$	1	1	0	0	0
$v_7$	0	0	0	1	1

| Show Table

DownLoad: CSV

Table 7. Time (in seconds) comparison under different fill ratios

	data7_01	data7_02	data7_03	data7_04	data7_05
$\|G\|\times \|M\|$	$26\times 6$	$26\times 6$	$26\times 6$	$26\times 6$	$26\times 6$
Fill ratio	0.494	0.532	0.513	0.468	0.474
#concepts	77	84	66	94	92
Algorithm 4	0.032	0.029	0.037	0.030	0.028

| Show Table

DownLoad: CSV

Table 8. $(U, A, I, B, J)$ based on the formal context $K$ in Table 1 [27]

$U$	$ a_1 $	$ a_2 $	$ a_3 $	$ a_4 $	$ a_5$	$ b_1 $	$ b_2 $	$ b_3 $	$ b_4 $	$ b_5 $
1	1	0	0	1	0	0	1	1	0	1
2	1	1	0	0	0	0	0	1	1	1
3	0	0	1	0	1	1	1	0	1	0
4	0	0	0	1	1	1	1	1	0	0
5	1	0	1	0	0	0	1	0	1	1

| Show Table

DownLoad: CSV

Related Papers

Cited by

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]	W. C. Cho and W. Richards, Improvement of precision and recall for information retrieval in a narrow domain: Reuse of concepts by formal concept analysis, In: IEEE/WIC/ACM International Conference on Web Intelligence(WI04), (2004), 370-376.
[4]	B. Ganter and R. Wille, Formal Concept Analysis: Mathematical Foundations, Springer-Verlag, New York, 1999. doi: 10.1007/978-3-642-59830-2.
[5]	J. Li and Z. Liu, Granule description in knowledge granularity and representation, Knowledge-Based Systems, 203 (2020), 106160.
[6]	J. Li, C. Mei and Y. Lv, Incomplete decision contexts: Approaching concept construction, rule acquisition and knowledge reduction, Int. J. Approx. Reason, 54 (2013), 149-165. doi: 10.1016/j.ijar.2012.07.005.
[7]	J. Li, C. Mei, L. Wang and J. Wang, On inference rules in decision formal contexts, Int. J. Comput. Intell. Syst, 8 (2015), 175-186.
[8]	J. Li, C. Mei, J. Wang and X. Zhang, Rule-preserved object compression in formal decision contexts using concept lattices, Knowl.-Based Syst, 71 (2014), 435-445.
[9]	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.
[10]	Z. Pawlak, Rough sets, International Journal of Computer and Information Sciences, 11 (1982), 341-356. doi: 10.1007/BF01001956.
[11]	J. Qi, T. Qian and L. Wei, The connections between three-way and classical concept lattices, Knowl.-Based Syst, 91 (2016), 143-151.
[12]	J. Qi, L. Wei and Z. Li, A Partitional View of Concept Lattice, Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing, Proceedings of the 10th International Conference, RSFDGrC 2005, Regina, Canada, (2005), 74–83 (Part Ⅰ).
[13]	J. Qi, L. Wei and Y. Yao, Three-way formal concept analysis, Lecture Notes in Computer Science, 8818 (2014), 732-741.
[14]	T. Qian, L. Wei and J. Qi, Decomposition methods of formal contexts to construct concept lattices, International Journal of Machine Learning and Cybernetics, 8 (2017), 95-108.
[15]	T. Qian, L. Wei and J. Qi, Constructing three-way concept lattices based on apposition and subposition of formal contexts, Knowledge-Based Systems, 116 (2017), 39-48.
[16]	T. Qian, L. Wei and J. Qi, A theoretical study on the object (property) oriented concept lattices based on three-way decisions, Soft Computing, 23 (2019), 9477-9489.
[17]	R. Ren and L. Wei, The attribute reductions of three-way concept lattices, KKnowledge-Based Systems, 99 (2016), 92-102.
[18]	M. Shao, H. Yang and W. Wu, Knowledge reduction in formal fuzzy contexts, Knowledge-Based Systems, 73 (2015), 265-275.
[19]	X. D. Tu, Y. L. Wang, M. L. Zhang, et al., Using formal concept analysis to identify negative correlations in gene expression data, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 13 (2016), 380-391.
[20]	Q. Wan and L. Wei, Approximate concepts acquisition based on formal contexts, Knowledge-Based Systems, 75 (2015), 78-86.
[21]	X. Wu and J. L. Zhang, Attribute logical formulas description of object granules based on the property-oriented (object-oriented) concepts (in Chinese), Pattern Recognition and Artificial Intelligence, 33 (2020), 767-775.
[22]	S. Yang, Y. Lu, X. Jia, et al., Constructing three-way concept lattice based on the composite of classical lattices, International Journal of Approximate Reasoning, 121 (2020), 174-186. doi: 10.1016/j.ijar.2020.03.007.
[23]	Y. Yao, A comparative study of formal concept analysis and rough set theory in data analysis, Rough Sets and Current Trends in Computing, 3066 (2004), 59-68. doi: 10.1007/978-3-540-25929-9_6.
[24]	L. A. Zadeh, Fuzzy sets, Information and Control, 8 (1965), 338-353.
[25]	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.
[26]	H.-L. Zhi and J.-H. Li, Granule description based on necessary attribute analysis, Chinese Journal of Computers, 41 (2018), 2702-2719.
[27]	H. Zhi and J.-J. Qi, Common-possible concept analysis: A granule description viewpoint, Applied Intelligence, 52 (2022), 2975-2986.
[28]	H.-L. Zhi, J. Qi, T. Qian, et al., Three-way dual concept analysis, International Journal of Approximate Reasoning, 114 (2019), 151-165. doi: 10.1016/j.ijar.2019.08.010.
[29]	J.-Q. Zhou, S.-C. Yang and X.-F. Wang, Concept and attribute reduction based on rectangle theory of formal concept, Mathematical Foundations of Computing, 6 (2023), 178-189.
[30]	C.-F. Zou, D.-Q. Zhang, J.-F. Wan, et al., Using concept lattice for personalized recommendation system design, IEEE Systems Journal, 11 (2017), 305-314.