Fast algorithms for computing rough approximations in set-valued decision systems while updating criteria values. (English) Zbl 1360.68842
Summary: Rough set theory is advocated as a framework for conceptualizing and analyzing various types of data, which is a powerful tool for discovering patterns in a given data set through a pair of concepts, namely, upper and lower approximations. Strategic behaviors need to be reinforced continuously under the dynamic decision environment where data in the decision process can change over time. Incremental learning is an effective technique to deal with dynamic learning tasks since it can make full use of previous knowledge. Set-valued data, in which a set of values are associated with an individual, is common in real-world data sets. Motivated by the needs of knowledge updating due to the dynamic variation of criteria values in the set-valued decision system, in this paper, we present the updating properties for dynamic maintenance of approximations when the criteria values in the set-valued decision system evolve with time. Then, two incremental algorithms for computing rough approximations are proposed corresponding to the addition and removal of criteria values, respectively. Experimental results show our incremental algorithms work successfully on datasets from UCI as well as artificial datasets, and achieve better performance than the traditional non-incremental method.
MSC:
| 68T37 | Reasoning under uncertainty in the context of artificial intelligence |
| 68T05 | Learning and adaptive systems in artificial intelligence |
References:
| [1] | Altiparmak, F.; Tuncel, E.; Ferhatosmanoglu, H., Incremental maintenance of online summaries over multiple streams, IEEE Trans. Knowl. Data Eng., 20, 2, 216-229 (2008) |
| [2] | Ananthanarayana, V. S.; Narasimha, M. M.; Subramanian, D. K., Tree structure for efficient data mining using rough sets, Pattern Recogn. Lett., 24, 851-862 (2003) · Zbl 1053.68036 |
| [3] | Chan, C., A rough set approach to attribute generalization in data mining, Inform. Sci., 107, 1-4, 169-176 (1998) |
| [4] | Chen, H. M.; Li, T. R.; Luo, C.; Horng, S. J.; Wang, G. Y., A rough set-based method for updating decision rules on attribute values’ coarsening and refining, IEEE Trans. Knowl. Data Eng. (2014) |
| [5] | Chen, H. M.; Li, T. R.; Ruan, D., Dynamic maintenance of approximations under a rough-set based variable precision limited tolerance relation, J. Multi-valued Logic Soft Comput., 18, 577-598 (2012) · Zbl 1394.68382 |
| [6] | Chen, H. M.; Li, T. R.; Ruan, D., Maintenance of approximations in incomplete ordered decision systems while attribute values coarsening or refining, Knowl.-Based Syst., 31, 140-161 (2012) |
| [7] | 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, 2, 274-284 (2013) |
| [8] | Dey, P.; Dey, S.; Datta, S.; Sil, J., Dynamic discreduction using rough sets, Appl. Soft Comput., 11, 5, 3887-3897 (2011) |
| [9] | Fan, Y. N.; Tseng, T. L.; Chern, C. C.; Huang, C. C., Rule induction based on an incremental rough set, Expert Syst. Appl., 36, 9, 11439-11450 (2009) |
| [10] | Greco, S.; Matarazzo, B.; Slowinski, R., Rough set theory for multicriteria decision analysis, Eur. J. Oper. Res., 129, 1-47 (2001) · Zbl 1008.91016 |
| [11] | Huang, C. C.; Tseng, T. L.; Fan, Y. N.; Hsu, C. H., Alternative rule induction methods based on incremental objet using rough set theory, Appl. Soft Comput., 13, 1, 372-389 (2013) |
| [13] | Kou, G.; Miettinen, K.; Shi, Y., Multiple criteria decision making: challenges and advancements, J. Multi-Criteria Decis. Anal., 18, 1-4 (2011) |
| [14] | Luo, C.; Li, T. R.; Chen, H. M., Dynamic maintenance of approximations in set-valued ordered decision systems under the attribute generalization, Inform. Sci., 257, 210-228 (2014) · Zbl 1320.68142 |
| [15] | 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) |
| [16] | 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) |
| [17] | 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, 8, 729-751 (2013) |
| [18] | Li, T. R.; Ruan, D.; Geert, W.; Song, J.; Xu, Y., A rough sets based characteristic relation approach for dynamic attribute generalization in data ming, Knowl.-Based Syst., 20, 485-494 (2007) |
| [19] | Lin, W. Y.; Alvarez, S. A.; Ruiz, C., Efficient adaptive-support association rule mining for recommender systems, Data Min. Knowl. Discovery, 6, 1, 83-105 (2002) |
| [20] | (Polkowski, L.; Tsumoto, S.; Lin, T. Y., Rough Set Methods and Applications (2000), Physica-Verlag: Physica-Verlag Berlin) |
| [21] | Pedrycz, W., Granular Computing: Analysis and Design of Intelligent Systems (2013), CRC Press/Francis Taylor: CRC Press/Francis Taylor Boca Raton |
| [22] | Pedrycz, W., Allocation of information granularity in optimization and decision making models: towards building the foundations of granular computing, Eur. J. Oper. Res., 232, 1, 137-145 (2014) |
| [23] | Pedrycz, W.; Homenda, W., Building the fundamentals of granular computing: a principle of justifiable granularity, Appl. Soft Comput., 13, 10, 4209-4218 (2013) |
| [24] | Pawlak, Z., Rough sets, Int. J. Comput. Inform. Sci., 11, 341-356 (1982) · Zbl 0501.68053 |
| [25] | Pawlak, Z., Rough set theory and its application to data analysis, Cybernet. Syst.: Int. J., 29, 661-668 (1998) · Zbl 1008.03526 |
| [26] | Qian, Y. H.; Dang, C. Y.; Liang, J. Y.; Tang, D. W., Set-valued ordered information systems, Inform. Sci., 179, 2809-2832 (2009) · Zbl 1192.68805 |
| [27] | Qian, Y. H.; Liang, J. Y.; Song, P.; Dang, C. Y., On dominance relations in disjunctive set-valued ordered information systems, Int. J. Inform. Technol. Decis. Making, 9, 9-33 (2010) · Zbl 1192.68804 |
| [28] | Qian, Y. H.; Liang, J. Y.; Dang, C. Y., Interval ordered information systems, Comput. Math. Appl., 56, 1994-2009 (2008) · Zbl 1165.68513 |
| [29] | Raghavan, V.; Hafez, A., Dynamic data mining, (Loganantharaj, R.; Palm, G.; Ali, M., Intelligent Problem Solving-Methodologies and Approaches: Proc. of Thirteenth International Conference on Industrial Engineering Applications of AI & Expert Systems (2000), Springer: Springer New York), 220-229 |
| [31] | Sun, L.; Xu, J. C.; Tian, Y., Feature selection using rough entropy-based uncertainty measures in incomplete decision systems, Knowl.-Based Syst., 36, 206-216 (2012) |
| [32] | Swiniarski, R. W.; Skowron, A., Rough set methods in feature selection and recognition, Pattern Recogn. Lett., 24, 6, 833-849 (2003) · Zbl 1053.68093 |
| [33] | Shao, M. W.; Zhang, W. X., Dominance relation and rules in an incomplete ordered information system, Int. J. Intell. Syst., 20, 13-27 (2005) · Zbl 1089.68128 |
| [34] | Tsumoto, S., Automated extraction of medical expertsystem rules from clinical databases based on roughset theory, Inform. Sci., 112, 67-84 (1998) |
| [35] | Wang, F.; Liang, J. Y.; Qian, Y. H., Attribute reduction: a dimension incremental strategy, Knowl.-Based Syst., 39, 95-108 (2013) |
| [36] | Xu, W. H.; Liu, Y. F.; Li, T. J., Intuitionistic fuzzy ordered information system, Int. J. Uncert. Fuzziness Knowl.-Based Syst., 21, 3 (2013) · Zbl 1323.68516 |
| [37] | Xu, W. H.; Li, Y.; Liao, X. W., Approaches to attribute based on rough set and matrix computation in inconsistent ordered information systems, Knowl.-Based Syst., 27, 78-91 (2012) |
| [38] | Xu, Y. T.; Wang, L. S.; Zhang, R. Y., A dynamic attribute reduction algorithm based on 0-1 integer programming, Knowl.-Based Syst., 24, 8, 1341-1347 (2011) |
| [39] | Yang, M., An incremental updating algorithm of the computation of a core based on the improved discernibility matrix, Chinese J. Comput., 29, 3, 407-413 (2006) |
| [40] | Yang, X. B.; Yu, D. J.; Yang, J. Y.; Wei, L. H., Dominance-based rough set approach to incomplete interval-valued information system, Data Knowl. Eng., 68, 11, 1331-1347 (2009) |
| [41] | Yang, X. B.; Yang, J. Y.; Wu, C.; Yu, D. J., Dominance-based rough set approach and knowledge reductions in incomplete ordered information system, Inform. Sci., 178, 4, 1219-1234 (2008) · Zbl 1134.68057 |
| [44] | Yao, Y. Y., Three-way decisions with probabilistic rough sets, Inform. Sci., 180, 341-353 (2010) |
| [45] | Yao, Y. Y., Information granulation and rough set approximation, Int. J. Intell. Syst., 16, 1, 87-104 (2001) · Zbl 0969.68079 |
| [47] | Yao, Y. Y., The superiority of three-way decisions in probabilistic rough set models, Inform. Sci., 181, 6, 1080-1096 (2011) · Zbl 1211.68442 |
| [48] | Yao, Y. Y.; Deng, X. F., Quantitative rough sets based on subsethood measures, Inform. Sci., 267, 306-322 (2014) · Zbl 1339.68249 |
| [49] | Yao, Y. Y.; Zhao, Y., Attribute reduction in decision-theoretic rough set models, Inform. Sci., 178, 17, 3356-3373 (2008) · Zbl 1156.68589 |
| [50] | 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 |
| [51] | Zhang, J. B.; Li, T. R.; Ruan, D.; Liu, D., Neighborhood rough sets for dynamic data mining, Int. J. Intell. Syst., 27, 317-342 (2012) |
| [52] | Zhang, J. B.; Wong, J. S.; Pan, Y.; Li, T. R., A parallel matrix-based method for computing approximations in incomplete information systems, IEEE Trans. Knowl. Data Eng. (2014) |
| [53] | 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, 3, 896-907 (2014) |
| [54] | Zhang, J. B.; Li, T. R.; Chen, H. M., Composite rough sets for dynamic data mining, Inform. Sci., 257, 81-100 (2014) · Zbl 1320.68156 |
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.
