A Granular Computing Approach to Symbolic Value Partitioning

• Autorzy: Wen L.-Y. , Min F.

Identyfikatory

DOI

10.3233/FI-2015-1297

• Języki publikacji: EN

Abstrakty

EN

Symbolic value partitioning is a knowledge reduction technique in the field of data mining. In this paper, we propose a granular computing approach for the partitioning task that includes granule construction and granule selection algorithms. The granule construction algorithm takes advantage of local information associated with each attribute. A binary attribute value taxonomy tree is built to merge these attribute values in a bottom-up manner using information-loss heuristics. The use of a balancing technique enables us to control different nodes in the same level to have approximately the same size. The granule selection algorithm uses global information about all of the attributes in the decision system. Hence, nodes across the taxonomy forest of all attributes are selected and expanded using information-gain heuristics. We present a series of experimental results that demonstrate the effectiveness of the proposed approach in terms of reducing the data size and improving the resulting classification accuracy.

Słowa kluczowe

EN

attribute taxonomy tree; granular computing; information entropy; symbolic value partition

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 142, nr 1-4
• Strony: 337--371
• Opis fizyczny: Bibliogr. 51 poz., rys., tab., wykr.

Twórcy

autor

Wen L.-Y.

• School of Computer Science Southwest Petroleum University Chengdu 610500, China

autor

Min F.

• School of Computer Science Southwest Petroleum University Chengdu 610500, China

Bibliografia

• [1] AdelsonVelskii, M., Landis, E. M.: An algorithm for the organization of information, Technical report, DTIC Document, 1963.
• [2] Bargiela, A., Pedrycz, W.: Granular Computing: An Introduction, Kluwer Academic Publishers, Boston, 2002.
• [3] Bargiela, A., Pedrycz, W.: The roots of granular computing., IEEE Granular Computing, IEEE, 2006.
• [4] Bayer, R.: Symmetric binary B-trees: Data structure and maintenance algorithms, Acta informatica, 1(4), 1972, 290–306.
• [5] Bazan, J. G., Skowron, A.: Dynamic reducts as a tool for extracting laws from decision tables, 8th International Symposium on Methodologies for Intelligent Systems, Springer, 1994.
• [6] Bazan, J. G., Szczuka, M.: The RSES homepage, http://alfa.mimuw.edu.pl/˜rses, 1994–2005.
• [7] Blake, C. L., Merz, C. J.: UCI Repository of machine learning databases, http://www.ics.uci.edu/˜mlearn/MLRepository.html, 1998.
• [8] Boussouf, M., Quafafou, M.: Scalable feature selection using rough set theory, Rough Sets and Current Trends in Computing, 2005, Springer, 2000.
• [9] Chen, Y. H., Yao, Y. Y.: Multiview intelligent data analysis based on granular computing, IEEE Granular Computing, IEEE, 2006.
• [10] Du, Y., Hu, Q. H., Zhu, P., Ma, P.: Rule learning for classification based on neighborhood covering reduction, Information Sciences, 181(24), 2011, 5457–5467.
• [11] Elena, C., Michela, B., Elisa, B.: Multigranular spatio-temporal models: implementation challenges, 16th ACM SIGSPATIAL international conference on Advances in geographic information systems, ACM, 2008.
• [12] Ester, M., Pei, J., Wang, K.: The DDM Lab homepage, http://ddm.cs.sfu.ca/.
• [13] Fang, Y., Liu, Z. H., Min, F.: Multi-objective cost-sensitive attribute reduction on data with error ranges, International Journal of Machine Learning and Cybernetics, 2014, 1–11.
• [14] He, X., Min, F., Zhu, W.: Comparison of Discretization Approaches for Granular Association Rule Mining, Canadian Journal of Electrical and Computer Engineering, 37(3), 2014, 157–167.
• [15] Hu, Q. H., Pan, W., An, S., Ma, P. J., Wei, J. M.: An efficient gene selection technique for cancer recognition based on neighborhood mutual information, International Journal of Machine Learning and Cybernetics, 1(1-4), 2010, 63–74.
• [16] Hu, Q. H., Pedrycz,W., Yu, D. R., Lang, J.: Selecting discrete and continuous features based on neighborhood decision error minimization, IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics, 40(1), 2010, 37–50.
• [17] Janusz, A., ´Ślęzak, D.: Rough set methods for attribute clustering and selection, Applied Artificial Intelligence, 28(3), 2014, 220–242.
• [18] Jensen, R., Cornelis, C., Shen, Q.: Hybrid fuzzy-rough rule induction and feature selection, IEEE International Conference on Fuzzy Systems, IEEE, 2009.
• [19] Jia, X. Y., Liao, W. H., Tang, Z. M., Shang, L.: Minimum cost attribute reduction in decision-theoretic rough set model, Information Sciences, 219, 2013, 151–167.
• [20] K, P. S., Uma, S. B., Pabitra, M.: Granular computing, rough entropy and object extraction, Pattern Recognition Letters, 26(16), 2005, 2509–2517.
• [21] Krasuski, A., Krenski, K.,Wasilewski, P., Lazowy, S.: Granular approach in knowledge discovery, in: Rough Sets and Knowledge Technology, Springer, 2012, 416–421.
• [22] Krasuski, A., ´Ślezak, D., Krenski, K., Lazowy, S.: Granular knowledge discovery framework, in: New Trends in Databases and Information Systems, Springer, 2013, 109–118.
• [23] Li, H. X., Zhou, X. Z.: Risk decision making based on decision-theoretic rough set: a three-way view decision model, International Journal of Computational Intelligence Systems, 4(1), 2011, 1–11.
• [24] Lin, T. Y.: Granular computing on binary relations-analysis of conflict and chinese Wall security policy, Rough Sets and Current Trends in Computing, 2475, Springer, 2002.
• [25] Lin, T. Y.: Granular computing - structures, representations, and applications, Lecture Notes in Artificial Intelligence, 2639, Springer, 2003.
• [26] Min, F., He, H., Qian, Y., Zhu, W.: Test-cost-sensitive attribute reduction, Information Sciences, 181, 2011, 4928–4942.
• [27] Min, F., Hu, Q. H., Zhu, W.: Feature selection with test cost constraint, International Journal of Approaximate Reasoning, 55(1), 2014, 167–179.
• [28] Min, F., Liu, Q. H., Fang, C. L.: Rough sets approach to symbolic value partition, International Journal of Approximate Reasoning, 49, 2008, 689–700.
• [29] Murai, T., Resconi, G., Nakata, M., Sato, Y.: Granular Reasoning Using Zooming In & Out, in: Rough sets, Fuzzy sets, Data mining, and Granular Computing, Springer, 2003, 421–424.
• [30] Nguyen, H. S.: Discretization of Real Value Attributes, Boolean Reasoning Approach, Ph.D. Thesis,Warsaw University, Warsaw, Poland, 1997.
• [31] Nguyen, H. S.: Discretization problem for rough sets methods, Rough Sets and Current Trends in Computing, 1424, Springer, 1998.
• [32] Nguyen, S. H.: Regularity Analysis and its Applications in Data Mining, Ph.D. Thesis, Warsaw University, Warsaw, Poland, 1999.
• [33] Pawlak, Zdzislaw: Rough sets, International Journal of Computer & Information Sciences, 11(5), 1982, 341–356.
• [34] Pedrycz, W., Skowron, A., Kreinovich, V.: Handbook of granular computing, John Wiley & Sons, 2008.
• [35] Polkowski, L., Skowron, A.: Rough mereological calculi of granules: A rough set approach to computation, Computational Intelligence, 17(3), 2001, 472–492.
• [36] Skowron, A., Rauszer, C.: The discernibility matrices and functions in information systems, in: Intelligent Decision Support, Springer, 1992, 331–362.
• [37] Su, L. R., Zhu, W.: Closed-set lattice and modular matroid induced by covering-based rough sets, International Journal of Machine Learning and Cybernetics, 2014, 1–11.
• [38] Wang, G. Y., Yu, H., Yang, D. C.: Decision table reduction based on conditional information entropy, Chinese Journal of Computers, 2(7), 2002, 759–766.
• [39] Wang, S. P., Zhu, Q. X., Zhu, W., Min, F.: Quantitative analysis for covering-based rough sets through the upper approximation number, Information Sciences, 220, 2013, 483–491.
• [40] Wu, W. Z., Leung, Y.: Theory and applications of granular labelled partitions in multi-scale decision tables, Information Sciences, 181(18), 2011, 3878–3897.
• [41] Wu, W. Z., Zhang, W. X.: Neighborhood operator systems and approximations, Information Sciences, 144, 2002, 263–282.
• [42] Yang, X. B., Qi, Y. S., Song, X. N., Yang, J. Y.: Test cost sensitive multigranulation rough set: Model and minimal cost selection, Information Sciences, 250, 2013, 184–199.
• [43] Yao, Y. Y.: On modeling data mining with granular computing, 25th Annual International Computer Software and Applications Conference, IEEE, 2001.
• [44] Yao, Y. Y.: A partition model of granular computing, Transactions on Rough Sets I, 3100, 2004, 232–253.
• [45] Yao, Y. Y.: Granular computing: past, present, and future, Lecture Notes in Computer Science, 5009, 2008, 27–28.
• [46] Yao, Y. Y., Zhao, Y.: Attribute reduction in decision-theoretic rough set models, Information sciences, 178(17), 2008, 3356–3373.
• [47] Yao, Y. Y., Zhao, Y., Wang, J.: On reduct construction algorithms, Rough Sets and Knowledge Technology, 4062, Springer, 2006.
• [48] Ye, M. Q., Wu, X. D., Hu, X. G., Hu, D. H.: Knowledge reduction for decision tables with attribute value taxonomies, Knowledge-Based Systems, 56, 2014, 68–78.
• [49] Zadeh, L. A.: Toward a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic, Fuzzy sets and systems, 90(2), 1997, 111–127.
• [50] Zhang, H. R., Min, F.: Three-way recommender systems based on random forests, Knowledge-Based Systems, 2015, 1–11.
• [51] Zhu, W., Wang, F.: Reduction and axiomization of covering generalized rough sets, Information Sciences, 152(1), 2003, 217–230.