Attribute reduction is a very important task in Rough Set Theory. In this context, in recent years several attribute reduction algorithms based on the discernibility matrix have been proposed. In this paper, we go back to the binary discernibility matrix and reformulate some basic concepts that allow us to build on them an algorithm for computing reducts. The proposed algorithm takes advantage of the binary representation used for the discernibility matrix and depending on the fulfillment of certain pruning properties several candidates can be jumped (pruned). In this way, the number of candidates to be tested is reduced. Additionally, from the binary discernibility matrix, we define a more compact and ordered matrix, which allows reducing even more the amount of candidates to be evaluated, and the cost of verifying each one of them.
The proposed algorithm is able to compute all the reducts of an information table, but it can also be used to find a reduct, or a certain number of them. Experiments over standard datasets show that our algorithm has a good performance.
AgrawalR. and SrikantR., Fast algorithms for mining association rules in large databases, Morgan Kaufmann, San Francisco, CA, 1994, pp. 487-499.
2.
BacheK. and LichmanM., UCI machine learning repository [http://archive.ics.uci.edu/ml]. Irvine, CA, University of California, School of Information and Computer Science, 2013.
3.
BaiX., ZhangM., QiuY. and WuQ., Algorithm for decision rules reduction in incomplete information system based on binary discernibility matrix, Int Conf on Mechatronics and Automation ICMA 2009, (2009), 4061-4066.
4.
BazanJ.G., NguyenH.S., NguyenS.H., SynakP. and WróblewskiJ., Rough set algorithms in classification problems, in: Rough Set Methods and Applications: New Developments in Knowledge Discovery in Information Systems, Studies in Fuzziness and Soft Computing, Vol. 56, L. Polkowski, T.Y. Lin and S. Tsumoto, eds, Springer-Verlag/Physica-Verlag, Heidelberg, 2000, pp. 49-88.
5.
BazanJ.G. and SzczukaM.S., RSES and RSESlib - a collection of tools for rough set computations, Proc of 2nd Int Conf Rough Sets and Current Trends in Computing, (2000), 106-113.
6.
ChenD.G., WangC.Z. and HuQ.H., A new approach to attribute reduction of consistent and inconsistent covering decision systems with covering rough sets, Information Sciences177(17) (2007), 3500-3518.
7.
ChenH., PeiZ. and ZhangL., Knowledge reduction based on binary discernibility matrix in variable precision rough set, Int Symp on Communications and Information Technologies ISCIT6 (2006), 949-954.
8.
ChenW.C., TsengS.S. and HongT.P., An efficient bit-based feature selection method, Expert Systems with Applications34(4) (2008), 2858-2869.
9.
FelixR. and UshioT., Rough sets-based machine learning using a binary discernibility matrix, Proc 2th on Intelligent Processing and Manufacturing of Materials (1999), 299-305.
10.
HuX. and CerconeN., Learning in relational databases: A rough set approach, Computation Intelligence, An International Journal11(2) (1995), 323-338.
11.
JensenR. and ShenQ., A rough set-aided system for sorting WWW bookmarks, in: Web Intelligence: Research and Development, N. Zhong, Y. Yao, J. Liu and S. Ohsuga, eds, LNAI 2198, Springer-Verlag Berlin Heidelberg, 2001, pp. 95-105.
12.
KahramanliS., HacibeyogluM. and ArslanA., A boolean function approach to feature selection in consistent decision information systems, Expert Systems with Applications38(7) (2011), 8229-8239.
13.
LeungY., WuW.Z. and ZhangW.X., Knowledge acquisition in incomplete information systems: A rough set approach, European Journal of Operational Research168(1) (2006), 164-180.
14.
LiJ., WangX. and FanX., Improved binary discernibility matrix attribute reduction algorithm in customer relationship management, Procedia Engineering7 (2010), 473-476.
15.
MiJ.S., WuW.Z. and ZhangW.X., Approaches to knowledge reduction based on variable precision rough set model, Information Sciences159(3) (2004), 255-272.
16.
NguyenH.S., On the decision table with maximal number of reducts, Electronic Notes in Theoretical Computer Science82(4) (2003), 198-205.
17.
NguyenH.S., Approximate Boolean reasoning: Foundations and applications in data mining, in: Transactions on Rough Sets V, J.F. Peters and A. Skowron, eds, LNCS 4100, Springer-Verlag Berlin Heidelberg, 2006, pp. 334-506.
18.
NguyenS.H. and NguyenH.S., Some efficient algorithms for rough set methods, Proc Sixth Int Conf on Information Processing and Management of Uncertainty on Knowledge Based Systems (1996), 1451-1456.
19.
OhrnA., KomorowskiJ., SkowronA. and SynakP., The ROSETTA software system, Rough Sets in Knowledge Discovery 1: Methodology and Applications19 (1998), 572-576.
20.
PawlakZ., Rough sets, International Journal of Computer and Information Sciences11(5) (1982), 341-356.
21.
PawlakZ., Rough Sets: Theoretical aspects of reasoning about data, system theory, Knowledge Engineering and Problem Solving, 9, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1991.
22.
PawlakZ. and SkowronA., Rough sets and boolean reasoning, Information Sciences177(1) (2007), 41-73.
23.
QuafafouM., α-RST: A generalization of rough set theory, Information Sciences124(1-4) (2000), 301-316.
24.
ShenQ. and ChouchoulasA., A modular approach to generating fuzzy rules with reduced attributes for the monitoring of complex systems, Engineering Applications of Artificial Intelligence13(3) (2000), 263-278.
25.
SkowronA., BazanJ., SzczukaM. and WróblewskiJ., Rough set exploration system (version 2.2.1), http://logic.mimuw. edu.pl/∼rses/.
26.
SkowronA. and RauszerC., The discernibility matrices and functions in information systems, in: Intelligent Decision Support, Handbook of Applications and Advances of the Rough Sets Theory, System Theory, Knowledge Engineering and Problem Solving, Vol. 11, R. Sƚowiński, ed., Kluwer Academic Publishers, Dordrecht, The Netherlands, 1992, pp. 331-362.
27.
SwiniarskiR.W., Rough sets methods in feature reduction and classification, International Journal of Applied Mathematics and Computer Science11 (2001), 565-582.
28.
TerleckiP., On the relation between jumping emerging patterns and rough set theory with application to data classification, in: Transactions on Rough Sets XII, J.F. Peters, A. Skowron, R. Sƚowiński, P. Lingras, D. Miao and S. Tsumoto, eds, LNCS 6190, Springer-Verlag Berlin Heidelberg, 2010, pp. 236-338.
29.
TiwariK.S., KothariA.G. and KeskarA.G., Reduct generation from binary discernibility matrix: an hardware approach, International Journal of Future Computer and Communication1(3) (2012), 270-272.
30.
WangJ. and MiaoD., Analysis on attribute reduction strategies of rough set, Journal of Computer Science and Technology13(2) (1998), 189-192.
31.
WangJ. and WangJ., Reduction algorithms based on discernibility matrix: the ordered attributes method, Journal of Computer Science and Technology16(6) (2001), 489-504.
32.
WróblewskiJ., Finding minimal reducts using genetic algorithm (extended version), in: Proceedings of the International Workshop on Rough Sets Soft Computing at Second Annual Joint Conference on Information Sciences (JCIS'95), P.P. Wang, ed., Wrightsville Beach, NC, USA, 1995, pp. 186-189. See also: ICS Research Report 16/95, Warsaw University of Technology.
33.
YaoY.Y., ZhaoY., WangJ. and HanS., A model of machine learning based on user preference of attributes, in: Rough Sets and Current Trends in Computing, S. Greco, Y. Hata, S. Hirano, M. Inuiguchi, S. Miyamoto, H.S. Nguyen and R. Sƚowiński, eds, LNAI 4259, Springer-Verlag Berlin Heidelberg, 2006, pp. 587-596.
34.
YaoY. and ZhaoY., Discernibility matrix simplification for constructing attribute reducts, Information Sciences179(7) (2009), 867-882.
35.
YangM. and YangP., A novel condensing tree structure for rough set feature selection, Neurocomputing71(4-6) (2008), 1092-1100.
36.
YangP., LiJ. and HuangY., An attribute reduction algorithm by rough set based on binary discernibility matrix, Proc Fifth Int Conf on Fuzzy Systems and Knowledge Discovery IEEE2 (2008), 276-280.
37.
ZhaoK. and WangJ., A reduction algorithm meeting users' requirements, Journal of Computer Science and Technology17(5) (2002), 578-593.
38.
ZiarkoW., Rough set approaches for discovering rules and attribute dependencies, in: Handbook of Data Mining and Knowledge Discovery, Vol. 271, W. Klösgen and J.M. Żytkow, eds, Oxford University Press, Inc., New York, NY, USA, 2002, pp. 328-339.
