×

zbMATH — the first resource for mathematics

A rough set-based incremental approach for learning knowledge in dynamic incomplete information systems. (English) Zbl 1433.68449
Summary: With the rapid growth of data sets nowadays, the object sets in an information system may evolve in time when new information arrives. In order to deal with the missing data and incomplete information in real decision problems, this paper presents a matrix based incremental approach in dynamic incomplete information systems. Three matrices (support matrix, accuracy matrix and coverage matrix) under four different extended relations (tolerance relation, similarity relation, limited tolerance relation and characteristic relation), are introduced to incomplete information systems for inducing knowledge dynamically. An illustration shows the procedure of the proposed method for knowledge updating. Extensive experimental evaluations on nine UCI datasets and a big dataset with millions of records validate the feasibility of our proposed approach.

MSC:
68T37 Reasoning under uncertainty in the context of artificial intelligence
Software:
RRIA; LERS
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bang, W. C.; Bien, Z., New incremental learning algorithm in the framework of rough set theory, Int. J. Fuzzy Syst., 1, 25-36, (1999)
[2] Bazan, J.; Nguyen, H. S.; Nguyen, S. H.; Synak, P.; Wroblewski, J., Rough set algorithms in classification problems, (Polkowski; etal., Rough Set Methods and Applications: New Developments in Knowledge Discovery in Information Systems, Studies in Fuzziness and Soft Computing, (2000)), 49-88
[3] Blaszczynski, J.; Slowinski, R., Incremental induction of decision rules from dominance-based rough approximations, Electron. Notes Theor. Comput. Sci., 82, 40-51, (2003) · Zbl 1270.68308
[4] Cattaneo, G.; Ciucci, D., Investigation about time monotonicity of similarity and preclusive rough approximations in incomplete information systems, (Proceedings of 4th International Conference on Rough Sets and Current Trends in Computing, LNAI, vol. 3066, (2004)), 38-48 · Zbl 1103.68835
[5] Chan, C. C., Incremental learning of production rules from examples under uncertainty: a rough set approach, Int. J. Softw. Eng. Knowl. Eng., 1, 439-461, (1991)
[6] Chan, C. C., A rough set approach to attribute generalization in data mining, Inf. Sci., 107, 177-194, (1998)
[7] Chen, H. M.; Li, T. R.; Qiao, S. J.; Ruan, D., A rough set based dynamic maintenance approach for approximations in coarsening and refining attribute values, Int. J. Intell. Syst., 25, 1005-1026, (2010) · Zbl 1211.68420
[8] Chen, H. M.; Li, T. R.; Ruan, D.; Lin, J. H.; Hu, C. X., A rough-set based incremental approach for updating approximations under dynamic maintenance environments, IEEE Trans. Knowl. Data Eng., 25, 274-284, (2013)
[9] Cheng, Y., The incremental method for fast computing the rough fuzzy approximations, Data Knowl. Eng., 70, 84-100, (2011)
[10] Ciucci, D., Classification of dynamics in rough sets, (Proceedings of 7th International Conference on Rough Sets and Current Trends in Computing, LNAI, vol. 6086, (2010)), 257-266
[11] Ciucci, D., Temporal dynamics in rough sets based on covering, (Proceedings of 5th International Conference on Rough Sets and Knowledge Technology, LNAI, vol. 6401, (2010)), 126-133
[12] Ciucci, D., Attribute dynamics in rough sets, (Proceedings of ISMIS11, LNCS, vol. 6804, (2011)), 43-51
[13] Ciucci, D., Temporal dynamics in information tables, Fundam. Inform., 115, 57-74, (2012) · Zbl 1237.68212
[14] Fan, Y.; Tseng, T.; Chern, C.; Huang, C., Rule induction based on an incremental rough set, Expert Syst. Appl., 36, 11439-11450, (2009)
[15] Grzymala-Busse, J. W., Knowledge acquisition under uncertainty - a rough set approach, J. Intell. Robot. Syst., 1, 3-16, (1988)
[16] Grzymala-Busse, J. W., A new version of the rule induction system LERS, Fundam. Inform., 31, 27-39, (1997) · Zbl 0882.68122
[17] Grzymala-Busse, J. W.; Siddhaye, S., Rough set approaches to rule induction from incomplete data, (International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems, (2004)), 923-930
[18] Grzymala-Busse, J. W., Data with missing attribute values: generalization of indiscernibility relation and rule induction, Trans. Rough Sets I, 78-95, (2004) · Zbl 1104.68759
[19] Grzymala-Busse, J. W., Characteristic relations for incomplete data: a generalization of the indiscernibility relation, Trans. Rough Sets, IV, 58-68, (2005) · Zbl 1136.68531
[20] Grzymala-Busse, J. W., Three approaches to missing attribute values: a rough set perspective, Stud. Comput. Intell., 118, 139-152, (2008) · Zbl 1156.68583
[21] Grzymala-Busse, J. W., Inducing better rule sets by adding missing attribute values, (Proceedings of 6th International Conference on Rough Sets and Current Trends in Computing, LNAI, vol. 5306, (2008)), 160-169
[22] Grzymala-Busse, J. W.; Grzymala-Busse, W. J., Increasing incompleteness of data sets - a strategy for inducing better rule sets, Stud. Comput. Intell., 262, 345-365, (2010) · Zbl 1185.68528
[23] Guo, S.; Wang, Z. Y.; Wu, Z. C.; Yam, H. P., A novel dynamic incremental rule extraction algorithm based on rough set theory, (Proceedings of the 4th International Conference on Machine Learning and Cybernetics, (2005), IEEE Press), 1902-1907
[24] Hu, F.; Wang, G. Y.; Huang, H.; Wu, Y., Incremental attribute reduction based on elementary sets, (RSFDGrC2005, LNAI, vol. 3641, (2005)), 185-193 · Zbl 1134.68471
[25] Hu, Y. C.; Tzeng, G. H.; Chen, C. M., Deriving two-stage learning sequences from knowledge in fuzzy sequential pattern mining, Inf. Sci., 159, 69-86, (2004)
[26] Han, J.; Kamber, M., Data mining: concepts and techniques, (2006), Morgan Kaufman · Zbl 1445.68004
[27] Hsu, P. Y.; Chen, Y. L.; Ling, C. C., Algorithms for mining association rules in bag databases, Inf. Sci., 166, 31-47, (2004) · Zbl 1101.68521
[28] Ibrahim, J. G.; Chen, M. H.; Lipsitz, S. R.; Herring, A. H., Missing data methods for generalized linear models: a comparative review, J. Am. Stat. Assoc., 100, 332-346, (2005) · Zbl 1117.62360
[29] Khan, M.; Banerjee, M., Formal reasoning with rough sets in multiple-source approximation systems, Int. J. Approx. Reason., 49, 466-477, (2008) · Zbl 1191.68684
[30] Kryszkiewicz, M., Rough set approach to incomplete information system, Inf. Sci., 112, 39-49, (1998) · Zbl 0951.68548
[31] Kryszkiewicz, M., Rules in incomplete information systems, Inf. Sci., 113, 271-292, (1999) · Zbl 0948.68214
[32] Lagus, K.; Kaski, S.; Kohonen, T., Mining massive document collections by the WEBSOM method, Inf. Sci., 163, 135-156, (2004)
[33] Leung, Y.; Wu, W. Z.; Zhang, W. X., Knowledge acquisition in incomplete information systems: a rough set approach, Eur. J. Oper. Res., 168, 164-180, (2006) · Zbl 1136.68528
[34] Li, H. X.; Wang, M. H.; Zhou, X. Z.; Zhao, J. B., An interval set model for learning rules from incomplete information table, Int. J. Approx. Reason., 53, 24-37, (2012) · Zbl 1242.68235
[35] 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, 149-165, (2013) · Zbl 1266.68172
[36] Li, S. Y.; Li, T. R.; Liu, D., Dynamic maintenance of approximations in dominance-based rough set approach under the variation of the object set, Int. J. Intell. Syst., 28, 729-751, (2013)
[37] Li, S. Y.; Li, T. R.; Liu, D., Incremental updating approximations in dominance-based rough sets approach under the variation of the attribute set, Knowl.-Based Syst., 40, 17-26, (2013)
[38] Li, T. R.; Yang, N.; Xu, Y.; Ma, J., An incremental algorithm for mining classification rules in incomplete information systems, (Proceedings of NAFIPS, (2004), IEEE Press), 446-449
[39] Li, T. R.; Ruan, D.; Geert, W.; Song, J.; Xu, Y., A rough sets based characteristic relation approach for dynamic attribute generalization in data mining, Knowl.-Based Syst., 20, 485-494, (2007)
[40] Li, Y.; Zhu, S.; Wang, X. S.; Jajodia, S., Looking into the seeds of time: discovering temporal patterns in large transaction sets, Inf. Sci., 176, 1003-1031, (2006) · Zbl 1093.68084
[41] Lipski, W. J., On semantic issues connected with incomplete information databases, ACM Trans. Database Syst., 4, 262-296, (1979)
[42] Liu, D.; Hu, P.; Jiang, C. Z., Incremental learning methodology of VPRS based on complete information system, (Proceedings of 2010 International Conference on Rough Sets and Knowledge Technology, (2008)), 276-283
[43] Liu, D.; Li, T. R.; Ruan, D.; Zou, W. L., An incremental approach for inducing knowledge from dynamic information systems, Fundam. Inform., 94, 245-260, (2009) · Zbl 1192.68530
[44] Liu, D.; Li, T. R.; Ruan, D.; Zhang, J. B., Incremental learning optimization on knowledge discovery in dynamic business intelligent systems, J. Glob. Optim., 51, 325-344, (2011) · Zbl 1230.90113
[45] Liu, D.; Li, T. R.; Chen, H. M.; Ji, X. L., Approaches to knowledge incremental learning based on the changes of attribute values, (Proceedings of the 4th International Conference on Intelligent Systems and Knowledge Engineering, (2009)), 94-99
[46] Liu, D.; Li, T. R.; Liu, G. R.; Hu, P., An approach for inducing interesting incremental knowledge based on the change of attribute values, (Proceedings of 2009 IEEE International Conference on Granular Computing, (2009)), 415-418
[47] Liu, D.; Zhang, J. B.; Li, T. R., A probabilistic rough set approach for incremental learning knowledge on the change of attribute, (Proceedings of 2010 International Conference on Foundations and Applications of Computational Intelligence, (2010)), 722-727
[48] Liu, D.; Li, T. R.; Zhang, J. B., An incremental approach for rule induction under coarsening and refining of attribute values in E-business systems, (Proceedings of 2010 International Conference on Electronic-Business Intelligence, (2010)), 541-547
[49] Liu, D.; Li, T. R.; Ruan, D., Probabilistic model criteria with decision-theoretic rough sets, Inf. Sci., 181, 3709-3722, (2011)
[50] Liu, D.; Liang, D. C., Incremental learning researches on rough set theory: status and future, Int. J. Rough Sets. Data Anal., 1, 99-112, (2014)
[51] Liu, D.; Li, T. R.; Liang, D. C., Incorporating logistic regression to decision-theoretic rough sets for classifications, Int. J. Approx. Reason., 55, 197-210, (2014) · Zbl 1316.68185
[52] Luo, C.; Li, T. R.; Chen, H. M.; Liu, D., Incremental approaches for updating approximations in set-valued ordered information systems, Knowl.-Based Syst., 50, 218-233, (2013)
[53] Luo, C.; Li, T. R.; Zhang, J. B., Dynamic maintenance of approximations in set-valued ordered decision systems under the attribute generalization, Inf. Sci., 257, 210-228, (2014) · Zbl 1320.68142
[54] Mesterharm, C.; Pazzani, M. J., Active learning using on-line algorithms, (Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, (2011)), 850-858
[55] Michalski, R. S.; Mozetic, I.; Hong, J.; Lavrac, N., The multi-purpose incremental learning system AQ15 and its testing application on three medical domains, (Proceedings of AAAI-86, (1986)), 1041-1045
[56] Orlowska, E., Dynamic information systems, Fundam. Inform., 5, 101-118, (1982) · Zbl 0525.68014
[57] Pagliani, P., Pretopologies and dynamic spaces, Fundam. Inform., 59, 221-239, (2004) · Zbl 1098.68131
[58] Pawlak, Z., Rough sets, Int. J. Comput. Inf. Sci., 11, 341-356, (1982) · Zbl 0501.68053
[59] Pawlak, Z., Rough sets, theoretical aspects of reasoning about data, (1991), Kluwer Academic Publishers Press Dordrecht · Zbl 0758.68054
[60] Pawlak, Z., Rough sets, decision algorithm and Bayes’ theorem, Eur. J. Oper. Res., 136, 181-189, (2002) · Zbl 1089.68127
[61] Pawlak, Z.; Skowron, A., Rudiments of rough sets, Inf. Sci., 177, 3-27, (2007) · Zbl 1142.68549
[62] Pawlak, Z.; Skowron, A., Rough sets: some extensions, Inf. Sci., 177, 28-40, (2007) · Zbl 1142.68550
[63] Qian, Y. H.; Liang, J. Y.; Yao, Y. Y.; Dang, C. Y., MGRS: a mulit-granulation rough set, Inf. Sci., 180, 949-970, (2010) · Zbl 1185.68695
[64] Qian, Y. H.; Liang, J. Y.; Dang, C. Y., Incomplete multigranulation rough set, IEEE Trans. Syst. Man Cybern., Part A, 40, 420-431, (2010)
[65] Qian, Y. H.; Liang, J. Y.; Witold, P.; Dang, C. Y., Positive approximation: an accelerator for attribute reduction in rough set theory, Artif. Intell., 174, 597-618, (2010) · Zbl 1205.68310
[66] Rauszer, C., Rough logic for multi-agent systems, (Logic at Work 1992, LNCS, vol. 808, (1994)), 161-181
[67] Saar-Tsechansky, M.; Provost, F., Handling missing values when applying classification models, J. Mach. Learn. Res., 8, 1623-1657, (2007) · Zbl 1222.68295
[68] Shan, L.; Ziarko, W., Data-based acquisition and incremental modification of classification rules, Comput. Intell., 11, 357-370, (1995)
[69] Stefanowski, J.; Tsoukias, A., On the extension of rough sets under incomplete information, (Proceedings of the 7th International Workshop on New Directions in Rough Sets, Data Mining, and Granular-Soft Computing, (1999)), 73-81
[70] Stefanowski, J.; Tsoukias, A., Incomplete information tables and rough classification, Comput. Intell., 17, 545-566, (2001)
[71] Tong, L. Y.; An, L. P., An incremental learning of decision rules based on rough set theory, (Proceedings of the World Congress on Intelligent Control and Automation, (2002)), 420-425
[72] Tsumoto, S., Extraction of experts’ decision process from clinical databases using rough set model, (Proceedings of PKDD 1997, (1997)), 58-67
[73] Tsumoto, S., Accuracy and coverage in rough set rule induction, (Proceedings of 3rd International Conference on Rough Sets and Current Trends in Computing, LNAI, vol. 2475, (2002)), 373-380 · Zbl 1013.68567
[74] Wang, G. Y., Extension of rough set under incomplete information systems, (Proceedings of the 2002 IEEE International Conference on Fuzzy System, (2002)), 1098-1103
[75] Wang, G. Y.; Guan, L. H.; Hu, F., Rough set extensions in incomplete information systems, Front. Electr. Electron. Eng. China, 3, 399-405, (2008)
[76] Wong, S. K.M.; Ziarko, W.; Pawlak, Z., Algorithm for inductive learning, Bull. Pol. Acad. Sci., Tech. Sci., 34, 271-276, (1986)
[77] Xu, Y. T.; Wang, L. S.; Zhang, R. Y., A dynamic attribute reduction algorithm based on 0-1 integer programming, Knowl.-Based Syst., 24, 1341-1347, (2011)
[78] Yao, Y. Y., Two views of the theory of rough sets in finite universes, Int. J. Approx. Reason., 15, 291-317, (1996) · Zbl 0935.03063
[79] Yao, Y. Y., Constructive and algebraic methods of the theory of rough sets, Inf. Sci., 109, 21-47, (1998) · Zbl 0934.03071
[80] Zhang, J. B.; Li, T. R.; Ruan, D.; Liu, D., Neighborhood rough sets for dynamic data mining, Int. J. Comput. Intell. Syst., 27, 317-342, (2012)
[81] Zhang, J. B.; Li, T. R.; Ruan, D.; Liu, D., Rough sets based matrix approaches with dynamic attribute variation in set-valued information systems, Int. J. Approx. Reason., 53, 620-635, (2012) · Zbl 1255.68160
[82] Zhang, J. B.; Li, T. R.; Ruan, D.; Gao, Z. Z.; Zhao, C. B., A parallel method for computing rough set approximations, Inf. Sci., 194, 209-223, (2012)
[83] Zhang, J. B.; Li, T. R.; Chen, H. M., Composite rough sets for dynamic data mining, Inf. Sci., 257, 81-100, (2014) · Zbl 1320.68156
[84] Zhang, J. B.; Wong, J. S.; Li, T. R.; Pan, Y., A comparison of parallel large-scale knowledge acquisition using rough set theory on different mapreduce runtime systems, Int. J. Approx. Reason., 55, 896-907, (2014)
[85] Zheng, Z.; Wang, G. Y., RRIA: A rough set and rule tree based incremental knowledge acquisition algorithm, Fundam. Inform., 59, 299-313, (2004) · Zbl 1098.68711
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.