Quantization of Rough Set Based Attribute Reduction

Bing Li, Peng Tang, Tommy W. S. Chow

Department of Electronic Engineering, City University of Hong Kong, 83 Tat Chee Avenue, Kowloon, Hong Kong.

DOI: 10.4236/jsea.2012.512B023                

Abstract

We demonstrate rough set based attribute reduction is a sub-problem of propositional satisfiability problem. Since satisfiability problem is classical and sophisticated, it is a smart idea to find solutions of attribute reduction by methods of satisfiability. By extension rule, a method of satisfiability, the distribution of solutions with different numbers of attributes is obtained without finding all attribute reduction. The relation between attribute reduction and missing is also analyzed from computational cost and amount of solutions.

Keywords

attribute reduction; extension rule; distribution of solutions; quantization

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Liu, Y., Dimensionality reduction and main component extraction of mass spectrometry cancer data. Know-ledge-Based Systems, 2011.
[2]	Lu, J., T. Zhao, and Y. Zhang, Feature selection based-on genetic algorithm for image annotation. Knowledge-Based Systems, 2008. 21(8): p. 887-891.
[3]	Chmielewski, M.R., et al., The rule induction system LERS-a version for personal computers. Foundations of Computing and Decision Sciences, 1993. 18(3-4): p. 181-212.
[4]	Booth, D.E., Analysis of Incomplete Multivariate Data. Technome-trics, 2000. 42(2): p. 213-214.
[5]	Hudak, A.T., et al., Nearest neighbor imputation of species-level, plot-scale forest structure attributes from LiDAR data. Remote Sensing of Environment, 2008. 112(5): p. 2232-2245.
[6]	Pelckmans, K., et al., Handling missing values in support vector machine classifiers. Neural Networks, 2005. 18(5-6): p. 684-692.
[7]	Myers, J.W., K.B. Laskey, and T. Levitt. Learning Bayesian networks from incomplete data with stochastic search algorithms. 1999. Morgan Kaufmann Publishers Inc.
[8]	Kryszkiewicz, M., Rough set approach to in-complete information systems. Information sciences, 1998. 112(1): p. 39-49.
[9]	Slowinski, R. and J. Stefa-nowski, Rough classification in incomplete information systems. Mathematical and Computer Modelling, 1989. 12(10-11): p. 1347-1357.
[10]	Pawlak, Z., Rough sets. International Journal of Parallel Programming, 1982. 11(5): p. 341-356.
[11]	Leung, Y. and D. Li, Maximal consistent block technique for rule acquisition in incom-plete information systems. Information sciences, 2003. 153: p. 85-106.
[12]	Meng, Z. and Z. Shi, A fast ap-proach to attribute reduction in incomplete decision sys-tems with tolerance relation-based rough sets. Informa-tion sciences, 2009. 179(16): p. 2774-2793.
[13]	Liang, J., Z. Shi, and D. Li, The information entropy, rough entropy and knowledge granulation in rough set theory. International Journal of Uncertainty Fuzziness and Knowledge-Based Systems, 2004. 12(1): p. 37-46.
[14]	Hai, L., S. Jigui, and Z. Yimin, Theorem proving based on the extension rule. Journal of Auto-mated Reasoning, 2003. 31(1): p. 11-21.
[15]	Hai, L. and S. Jigui, Knowledge compilation using the extension rule. Journal of Automated Reasoning, 2004. 32(2): p. 93-102.
[16]	Grzymala-Busse, J.W., Managing uncer-tainty in expert systems. Vol. 143. 1991: Sprin-ger.
[17]	Kirkpatrick, S. and B. Selman, Critical beha-vior in the satisfiability of random boolean expressions. Science, 1994. 264(5163): p. 1297-1301.