×

A fast attribute reduction method for large formal decision contexts. (English) Zbl 1456.68189

Summary: Attribute reduction in formal decision contexts is an important issue in formal concept analysis, which can help us to discover the knowledge hidden in formal decision contexts. However, most reduction methods in formal decision contexts are very time-consuming due to two main problems. The first is that one needs to construct a discernibility matrix after generating all the formal concepts of formal decision contexts. This is not an easy task because it requires much more storage space and computation time. Another problem is that most reduction methods are based on the Boolean reasoning and the computational complexity of which is exponential in the worst case. To overcome these problems, we propose a new attribute reduction method for formal decision contexts in this paper. A more simplified discernibility matrix which does not need to generate all the formal concepts is first constructed. It shows that the storage space and computation time are far less than the original method. Furthermore, different from the Boolean reasoning method, an approximation algorithm for obtaining a minimum reduct in formal decision contexts based on graph theory is designed. Finally, experiments are carried out to verify the effectiveness of the proposed method. The results, on 22 large data sets, demonstrate that the proposed method not only produces smaller subset of attributes but also has better performance in both storage space and speed.

MSC:

68T30 Knowledge representation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aswani Kumar, Ch.; Dias, S. M.; Newton, J. V., Knowledge reduction in formal contexts using non-negative matrix factorization, Math. Comput. Simul., 109, 46-63 (2015) · Zbl 07313329
[2] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), Elsevier Science Publishing Co., Inc. · Zbl 1226.05083
[3] Bondy, J. A.; Murty, U. S.R., Graph Theory (2008), Springer: Springer Berlin · Zbl 1134.05001
[4] Carpineto, C.; Romano, G., A lattice conceptual clustering system and its application to browsing retrieval, Mach. Learn., 10, 95-122 (1996)
[5] Chen, J.; Li, J.; Lin, Y.; Lin, G.; Ma, Z., Relations of reduction between covering generalized rough sets and concept lattices, Inf. Sci., 304, 16-27 (2015) · Zbl 1360.68803
[6] Chen, J.; Mi, J.; Lin, Y., A graph approach for knowledge reduction in formal contexts, Knowl.-Based Syst., 148, 177-188 (2018)
[7] Dias, S. M.; Vieira, N. J., Concept lattices reduction: definition, analysis and classification, Expert Syst. Appl., 42, 20, 7084-7097 (2015)
[8] Dong, C. Z., Attribute Reduction of Strongly Harmonious Decision Formal Contexts (2016), Yanshan University: Yanshan University Hebei, Dissertation for the Master Degree (in Chinese)
[9] Ganter, B.; Wille, R., Formal Concept Analysis, Mathematical Foundations (1999), Springer: Springer Berlin · Zbl 0909.06001
[10] Godin, R., Incremental concept formation algorithm based on Galois (concept) lattices, Comput. Intell., 11, 246-267 (1995)
[11] Gomes, F. C.; Meneses, C. N.; Pardalos, P. M.; Vianaa, G. V.R., Experimental analysis of approximation algorithms for the vertex cover and set covering problems, Comput. Oper. Res., 33, 12, 3520-3534 (2006) · Zbl 1110.90083
[12] Guo, L. K.; Huang, F. P.; Li, Q. G.; Zhang, G. Q., Power contexts and their concept lattices, Discrete Math., 311, 18-19, 2049-2063 (2011) · Zbl 1233.68207
[13] Hao, S. F.; Shi, C. Y.; Niu, Z. D.; Cao, L. B., Concept coupling learning for improving concept lattice-based document retrieval, Eng. Appl. Artif. Intell., 69, 65-75 (2018)
[14] Huang, C.; Li, J.; Mei, C.; Wu, W. Z., Three-way concept learning based on cognitive operators: an information fusion viewpoint, Int. J. Approx. Reason., 83, 218-242 (2017) · Zbl 1404.68107
[15] Kent, R. E., Rough concept analysis, (Ziarko, W. P., Rough Sets, Fuzzy Sets and Knowledge Discovery (1994), Springer-Verlag: Springer-Verlag London), 248-255 · Zbl 0819.06006
[16] Konecny, J., On attribute reduction in concept lattices: methods based on discernibility matrix are outperformed by basic clarification and reduction, Inf. Sci., 415-416, 199-212 (2017) · Zbl 1435.68321
[17] Konecny, J.; Krupka, M., Block relations in formal fuzzy concept analysis, Int. J. Approx. Reason., 73, 27-55 (2016) · Zbl 1352.68232
[18] Lang, G.; Miao, D.; Cai, M.; Zhang, Z., Incremental approaches for updating reducts in dynamic covering information systems, Knowl.-Based Syst., 134, 85-104 (2017)
[19] Lang, G.; Miao, D.; Cai, M., Three-way decision approaches to conflict analysis using decision-theoretic rough set theory, Inf. Sci., 406-407, 185-207 (2017) · Zbl 1431.91113
[20] Lang, G.; Cai, M.; Fujita, H.; Xiao, Q., Related families-based attribute reduction of dynamic covering decision information systems, Knowl.-Based Syst. (2018)
[21] Li, T. J.; Wu, W. Z., Attribute reduction in formal contexts: a covering rough set approach, Fundam. Inform., 111, 15-32 (2011) · Zbl 1237.68214
[22] Li, J. H.; Mei, C. L.; Lv, Y. J., A heuristic knowledge-reduction method for decision formal contexts, Comput. Math. Appl., 61, 4, 1096-1106 (2011) · Zbl 1217.68208
[23] Li, J. H.; Mei, C. L.; Lv, Y. J., Knowledge reduction in decision formal contexts, Knowl.-Based Syst., 24, 5, 709-715 (2011)
[24] Li, J. H.; Mei, C. L.; Aswani Kumar, Ch.; Zhang, X., On rule acquisition in decision formal contexts, Int. J. Mach. Learn. Cybern., 4, 6, 721-731 (2013)
[25] Li, J. H.; Mei, C. L.; Lv, Y. J., Incomplete decision contexts: approximate concept construction, rule acquisition and knowledge reduction, Int. J. Approx. Reason., 54, 1, 149-165 (2013) · Zbl 1266.68172
[26] Li, J. H.; Aswani Kumar, Ch.; Mei, C. L.; Wang, X. Z., Comparison of reduction in formal decision contexts, Int. J. Approx. Reason., 80, 100-122 (2017) · Zbl 1400.68208
[27] Li, K. W.; Shao, M. W.; Wu, W. Z., A data reduction method in formal fuzzy contexts, Int. J. Mach. Learn. Cybern., 8, 4, 1145-1155 (2017)
[28] Li, W. T.; Xu, W. H., Double-quantitative decision-theoretic rough set, Inf. Sci., 316, 54-67 (2015) · Zbl 1390.68666
[29] Li, J. X.; Wang, X.; Wu, W. Z.; Xu, Y. H., Attribute reduction in inconsistent formal decision contexts based on congruence relations, Int. J. Mach. Learn. Cybern., 8, 1, 81-94 (2017)
[30] Lin, Y. J.; Li, J. J.; Lin, P. R.; Lin, G. P.; Chen, J. K., Feature selection via neighborhood multi-granulation fusion, Knowl.-Based Syst., 67, 162-168 (2014)
[31] Lin, Y. J.; Hu, Q. H.; Zhang, J.; Wu, X. D., Multi-label feature selection with streaming labels, Inf. Sci., 372, 256-275 (2016)
[32] Lin, Y. J.; Hu, Q. H.; Liu, J. H.; Li, J. J.; Wu, X. D., Streaming feature selection for multilabel learning based on fuzzy mutual information, IEEE Trans. Fuzzy Syst., 25, 6, 1491-1507 (2017)
[33] Listrovoy, S.; Minukhin, S., The solution algorithms for problems on the minimal vertex cover in networks and the minimal cover in Boolean matrixes, Int. J. Comput. Sci. Issues, 9, 5, 8-15 (2012)
[34] Ma, J. M.; Zhang, W. X.; Leung, Y.; Song, X. X., Granular computing and dual Galois connection, Inf. Sci., 177, 23, 5365-5377 (2007) · Zbl 1126.68043
[35] Ma, J. M.; Leung, Y.; Zhang, W. X., Attribute reductions in object-oriented concept lattices, Int. J. Mach. Learn. Cybern., 5, 5, 789-813 (2014)
[36] Ma, J. M.; Cai, M. J.; Zou, C. J., Concept acquisition approach of object-oriented concept lattices, Int. J. Mach. Learn. Cybern., 8, 1, 123-134 (2017)
[37] Medina, J., Relating attribute reduction in formal, object-oriented and property-oriented concept lattices, Comput. Math. Appl., 64, 6, 1992-2002 (2012) · Zbl 1268.06007
[38] Mi, J. S.; Leung, Y.; Wu, W. Z., Approaches to attribute reduction in concept lattices induced by axialities, Knowl.-Based Syst., 23, 504-511 (2010)
[39] Nourine, L.; Raynaud, O., A fast algorithm for building lattices, Inf. Process. Lett., 71, 199-204 (1999) · Zbl 0998.06005
[40] Pei, D.; Mi, J. S., Attribute reduction in decision formal context based on homomorphism, Int. J. Mach. Learn. Cybern., 2, 4, 289-293 (2011)
[41] Qi, J. J.; Qian, T.; Wei, L., The connections between three-way and classical concept lattices, Knowl.-Based Syst., 91, 143-151 (2016)
[42] Qian, Y.; Liang, X.; Lin, G.; Guo, Q.; Liang, J., Local multigranulation decision-theoretic rough sets, Int. J. Approx. Reason., 82, 119-137 (2017) · Zbl 1404.68172
[43] Qiao, S. Y.; Wen, S. P.; Chen, C. Y.; Li, Z. G., A fast algorithm for building concept lattice, (International Conference Machine Learning Cybernetics, vol. 1 (2003), IEEE), 163-167
[44] Rajapakse, R. K.; Denham, M., Text retrieval with more realistic concept matching and reinforcement learning, Inf. Process. Manag., 42, 1260-1275 (2006)
[45] Shao, M. W.; Leung, Y., Relations between granular reduct and dominance reduct in formal contexts, Knowl.-Based Syst., 65, 1-11 (2014)
[46] Shao, M. W.; Leung, Y.; Wu, W. Z., Rule acquisition and complexity reduction in formal decision contexts, Int. J. Approx. Reason., 55, 1, 259-274 (2014) · Zbl 1316.68163
[47] Shao, M. W.; Li, K. W., Attribute reduction in generalized one-sided formal contexts, Inf. Sci., 378, 317-327 (2017) · Zbl 1429.68279
[48] Shi, L. L.; Yang, H. L., Object granular reduction of fuzzy formal contexts, J. Intell. Fuzzy Syst., 34, 1, 633-644 (2018)
[49] Skowron, A., Boolean reasoning for implication rules generation, (Methodologies for Intelligent Systems (1993), Springer-Verlag), 295-305
[50] Tan, A. H.; Li, J. J.; Lin, G. P., Connections between covering-based rough sets and concept lattices, Int. J. Approx. Reason., 56, 43-58 (2015) · Zbl 1388.68260
[51] Valtchev, P.; Missaoui, R.; Godin, R., Formal concept analysis for knowledge discovery and data mining: the new challenge, (Proceedings of the 2nd International Conference on Formal Concept Analysis (2004), Sydney: Sydney Australia), 352-371 · Zbl 1198.68246
[52] Vychodil, V., Closure structures parameterized by systems of isotone Galois connections, Int. J. Approx. Reason., 91, 1-21 (2017) · Zbl 1419.68150
[53] Wang, L. D.; Liu, X. D., Concept analysis via rough set and AFS algebra, Inf. Sci., 178, 21, 4125-4137 (2008) · Zbl 1170.68038
[54] Wang, H.; Zhang, W. X., Approaches to knowledge reduction in generalized consistent decision formal context, Math. Comput. Model., 48, 11-12, 1677-1684 (2008) · Zbl 1187.91044
[55] Wei, L.; Qi, J. J.; Zhang, W. X., Attribute reduction theory of concept lattice based on decision formal contexts, Sci. China, Ser. F, 51, 7, 910-923 (2008) · Zbl 1291.68391
[56] Wei, L.; Qi, J. J., Relation between concept lattice reduction and rough set reduction, Knowl.-Based Syst., 23, 934-938 (2010)
[57] Wei, L.; Wan, Q., Granular transformation and irreducible element judgment theory based on pictorial diagrams, IEEE Trans. Cybern., 46, 2, 380-387 (2016)
[58] Wille, R., Restructuring lattice theory: an approach based on hierarchies of concepts, (Rival, I., Ordered Sets (1982), Reidel: Reidel Dordrecht-Boston), 445-470
[59] Wille, R., Why can concept lattices support knowledge discovery in databases?, J. Exp. Theor. Artif. Intell., 14, 2-3, 81-92 (2002) · Zbl 1022.68042
[60] Wu, W. Z.; Leung, Y.; Mi, J. S., Granular computing and knowledge reduction in formal context, IEEE Trans. Knowl. Data Eng., 21, 10, 1461-1474 (2009)
[61] Xu, W. H.; Li, W. T., Granular computing approach to two-way learning based on formal concept analysis in fuzzy datasets, IEEE Trans. Cybern., 46, 2, 366-379 (2016)
[62] Yao, Y. Y., Concept lattices in rough set theory, (Dick, S.; Kurgan, L.; Pedrycz, W.; Reformat, M., Proceedings of 2004 Annual Meeting of the North American Fuzzy Information Processing Society. Proceedings of 2004 Annual Meeting of the North American Fuzzy Information Processing Society, NAFIPS (2004)), 796-801
[63] Yang, B.; Hu, B. Q., Matrix representations and interdependency on L-fuzzy covering-based approximation operators, Int. J. Approx. Reason., 96, 57-77 (2018) · Zbl 1446.03098
[64] Zhang, W.; Wei, L.; Qi, J., Attribute reduction in concept lattice based on discernibility matrix, Lect. Notes Comput. Sci., 3642, 157-165 (2005) · Zbl 1155.68525
[65] Zhang, W. X.; Ma, J. M.; Fan, S. Q., Variable threshold concept lattices, Inf. Sci., 177, 22, 4883-4892 (2007) · Zbl 1130.06004
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.