• Articles • Previous Articles     Next Articles

Tree Expressions for Information Systems

Min Zhao1, Su-Qing Han2, and Jue Wang3   

  1. 1NEC Research China, Beijing 100080, China 2Department of Mathematics, Taiyuan Normal University, Taiyuan 030012, China 3Institute of Automation, Chinese Academy of Sciences, Beijing 100080, China
  • Received:2006-09-04 Revised:2007-01-29 Online:2007-03-10 Published:2007-03-10

The discernibility matrix is one of the most important approaches to computing positive region, reduct, core and value reduct in rough sets. The subject of this paper is to develop a parallel approach of it, called tree expression. Its computational complexity for positive region and reduct is $O(m^{2}\tm n)$ instead of $O(m\tm n^{2})$ in discernibility-matrix-based approach, and is not over $O(n^{2}$) for other concepts in rough sets, where $m$ and $n$ are the numbers of attributes and objects respectively in a given dataset (also called an ``{\it information system}'' in rough sets). This approach suits information systems with $n\gg m$ and containing over one million objects.

Key words: feedforward neural network; mean square classifiers; outer-supervised signal; classification;

[1] Pawlak Z. Rough Set---Theoretical Aspects of Reasoning About Data. Dorderecht, Kluwer Academic Publishers, 1991.

[2] Wang J, Zhao M, Zhao K, Han S. Multilevel data summarization from information system: A ``rule + exception'' approach, \it AI Communications, \rm 2003, 16(1): 17--39.

[3] Wang F. Intelligence and security informatics: An emerging interdisciplinary field based on computational intelligence. \it International Journal of Intelligent Control and Systems, \rm 2003, 18(4): 476--483.

[4] Hu X, Cercone N. Learning in relational databases: A rough set approach. \it International Journal of Computational Intelligence, \rm 1995, 11(2): 323--338.

[5] Miao D, Wang J. Information-based algorithm for reduction of knowledge. In -\it Proc. IEEE ICIPS'97}, Beijing, 1997, pp.1155--1158.

[6] Wr\'oblewski J. Finding minimal reducts using genetic algorithms. In -\it Proc. the Second Annual Join Conference on Information Sciences}, 1995, pp.186--189.

[7] Skowron A, Rauszer C. The discernibility matrices and functions in information systems. Intelligent Decision Support---Handbook of Applications and Advances of the Rough Sets Theory, Slowinski R (ed.), Kluwer Academic Publishers, 1992, pp.331--362.

[8] Wang J, Wang J. Reduction algorithms based on discernibility matrix: The ordered attributes method. -\it Journal of Computer Science and Technology}, 2001, 16(6): 489--504.

[9] Zhao M. Data description based on reduct theory
[Dissertation]. Institute of Automation, Chinese Academy of Sciences, 2004.

[10] Quinlan J. Induction of decisions trees. \it Machine Learning, \rm 1986, 1: 81--106.

[11] Ye D, Chen Z. Inconsistency classification and discernibility---Matrix-based approaches for computing an attribute core. In -\it Proc. RSFDGrC}, Chongqing, China, 2003, pp.269--273.

[12] Han S, Wang J. Reduct and attribute order. -\it J. Computer Science and Technology}, 2004, 19(4): 429--449.
[1] Zhi-Xin Qi, Hong-Zhi Wang, An-Jie Wang. Impacts of Dirty Data on Classification and Clustering Models: An Experimental Evaluation [J]. Journal of Computer Science and Technology, 2021, 36(4): 806-821.
[2] Jing-Xuan Zhang, Chuan-Qi Tao, Zhi-Qiu Huang, Xin Chen. Discovering API Directives from API Specifications with Text Classification [J]. Journal of Computer Science and Technology, 2021, 36(4): 922-943.
[3] Jun Gao, Paul Liu, Guang-Di Liu, Le Zhang. Robust Needle Localization and Enhancement Algorithm for Ultrasound by Deep Learning and Beam Steering Methods [J]. Journal of Computer Science and Technology, 2021, 36(2): 334-346.
[4] Hua Chen, Juan Liu, Qing-Man Wen, Zhi-Qun Zuo, Jia-Sheng Liu, Jing Feng, Bao-Chuan Pang, Di Xiao. CytoBrain: Cervical Cancer Screening System Based on Deep Learning Technology [J]. Journal of Computer Science and Technology, 2021, 36(2): 347-360.
[5] Xia-An Bi, Zhao-Xu Xing, Rui-Hui Xu, Xi Hu. An Efficient WRF Framework for Discovering Risk Genes and Abnormal Brain Regions in Parkinson's Disease Based on Imaging Genetics Data [J]. Journal of Computer Science and Technology, 2021, 36(2): 361-374.
[6] Bo-Wei Zou, Rong-Tao Huang, Zeng-Zhuang Xu, Yu Hong, Guo-Dong Zhou. Language Adaptation for Entity Relation Classification via Adversarial Neural Networks [J]. Journal of Computer Science and Technology, 2021, 36(1): 207-220.
[7] Punit Kumar, Atul Gupta. Active Learning Query Strategies for Classification, Regression, and Clustering: A Survey [J]. Journal of Computer Science and Technology, 2020, 35(4): 913-945.
[8] Yi-Min Wen, Shuai Liu. Semi-Supervised Classification of Data Streams by BIRCH Ensemble and Local Structure Mapping [J]. Journal of Computer Science and Technology, 2020, 35(2): 295-304.
[9] Yang Li, Wen-Zhuo Song, Bo Yang. Stochastic Variational Inference-Based Parallel and Online Supervised Topic Model for Large-Scale Text Processing [J]. Journal of Computer Science and Technology, 2018, 33(5): 1007-1022.
[10] Tong Shen, Da-Fang Zhang, Gao-Gang Xie, Xin-Yi Zhang. Optimizing Multi-Dimensional Packet Classification for Multi-Core Systems [J]. Journal of Computer Science and Technology, 2018, 33(5): 1056-1071.
[11] Xian-Hua Zeng, Bang-Gui Liu, Meng Zhou. Understanding and Generating Ultrasound Image Description [J]. Journal of Computer Science and Technology, 2018, 33(5): 1086-1100.
[12] Qian Wang, You-Dong Ding. A Novel Fine-Grained Method for Vehicle Type Recognition Based on the Locally Enhanced PCANet Neural Network [J]. , 2018, 33(2): 335-350.
[13] Li Zhang, Xin-Yue Huang, Jing Jiang, Ya-Kun Hu. CSLabel:An Approach for Labelling Mobile App Reviews [J]. , 2017, 32(6): 1076-1089.
[14] Bei-Ji Zou, Yao Chen, Cheng-Zhang Zhu, Zai-Liang Chen, Zi-Qian Zhang. Supervised Vessels Classification Based on Feature Selection [J]. , 2017, 32(6): 1222-1230.
[15] Meng Chen, Lin-Lin Zhang, Xiaohui Yu, Yang Liu. Weighted Co-Training for Cross-Domain Image Sentiment Classification [J]. , 2017, 32(4): 714-725.
Full text



[1] Ma Jun; Ma Shaohan;. Efficient Parallel Algorithms for Some Graph Theory Problems[J]. , 1993, 8(4): 76 -80 .
[2] Tang Weiqing; Wen Sili; Liu Shenquan;. An Object-Oriented Model ofUser Interface Generation Tool[J]. , 1994, 9(3): 275 -284 .
[3] Zheng Fang; Wu Wenhu; Fang Ditang;. A Log-Index Weighted Cepstral Distance Measure for Speech Recognition[J]. , 1997, 12(2): 177 -184 .
[4] Shen Yidong;. Extracting Schema from an OEM Database[J]. , 1998, 13(4): 289 -299 .
[5] KONG Fanjia; WANG Guangxing;. Computing the SKT Reliability of Acyclic Directed Networks Using Factoring Method[J]. , 1999, 14(1): 56 -63 .
[6] SHAO Zhiqing; SUN Yongqiang; SONG Guoxin; YU Huiqun;. Deciding Quasi-Reducibility Using Witnessed Test Sets[J]. , 1999, 14(2): 146 -152 .
[7] Sheng-Zhi Du, Zeng-Qiang Chen, and Zhu-Zhi Yuan. Evolutionary Pseudo-Relaxation Learning Algorithm for Bidirectional Associative Memory[J]. , 2005, 20(4): 559 -566 .
[8] Ming Li, Xiao-Shan Gao,and Jin-San Cheng. Generating Symbolic Interpolants for Scattered Data with Normal Vectors[J]. , 2005, 20(6): 861 -874 .
[9] Min Liu, Zhong-Cheng Li, and Xiao-Bing Guo. An Efficient Handoff Decision Algorithm for Vertical Handoff Between WWAN and WLAN[J]. , 2007, 22(1): 114 -120 .
[10] Feng-Xi Song, David Zhang, Cai-Kou Chen, and Jing-Yu Yang. Facial Feature Extraction Method Based on Coefficients of Variances[J]. , 2007, 22(4): 626 -632 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved