For a decision table, it is firstly proved that the effective pair is equivalent to improved discernibility matrix to guarantee that the attribute reduction based on discernibility matrix can be calculated by effective pair. To get the attribute reduction more quickly, a parallel radix sort model is proposed. Then a simple decision table and effective pair are obtained. Taking the length of distinguishable or indistinguishable elements string among the effective pair as heuristic information, an attribute reduction algorithm based on parallel Logical OR is proposed. Finally, the examples and experiments are shown to verify the effectiveness and feasibility of the proposed algorithm.
PawlakZ. and SkowronA., Rough sets: Some extensions, Information Sciences177(1) (2007), 28–40.
2.
PawlakZ. and SkowronA., Rudiments of rough sets, Information Sciences177(1) (2007), 3–27.
3.
WangX.Z., WangT.T. and ZhaiJ.H., An attribute reduction algorithm based on instance selection, Journal of Computer Research and Development49(11) (2012), 2305–2310.
4.
KimK., ChuY.Y., WatadaJ.Z., et al., A DNA-based algorithm for minimizing decision rules: A rough sets approach, IEEE Trans Nanobiosci10(3) (2011), 139.
5.
QianY., LiangJ., PedryczW. and DangC., An efficient accelerator for attribute reduction from incomplete data in rough set framework, Pattern Recognition44(8) (2011), 1658–1670.
6.
HuQ., PedryczW., YuD. and LangJ., Selecting discreteand continuous features based on neighborhood decision error minimization, Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on40(1) (2010), 137–150.
7.
QianY., LiangJ., PedryczW. and DangC., Positive approximation: An accelerator for attribute reduction in rough set theory, Artificial Intelligence174(9-10) (2010), 597–618.
8.
WongS.K.M. and ZiarkoW., On optimal decision rules in decision tables, Bulletin of the Polish Academy of Sciences33(11-12) (1985), 693–696.
9.
ZhangJ.B. and LiT.R., PLAR: Parallel large-scale attribute reduction on cloud systems, In: Proceedings of PDCAT, 2013, pp. 184–191.
10.
XuF.F., WeiL., BiZ.Q., etc., Research on fuzzy rough parallel reduction based on mutual information, Journal of Computational Information Systems10(12) (2014), 5391–5401.
11.
PawlakZ., Rough sets, International Journal of Computer & Information Sciences11(5) (1982), 341–356.
12.
SunL.L., HouX.P., ZhuB., etc. Merge sort algorithm design based on multi thread, Journal of Jilin University(Information Science Edition)33(1) (2015), 105–110.
13.
XuZ.Y., LiuZ.P., YangB.R. and SongW., A quick attribute reduction algorithm with complexity Max (O (|C||U|) , O (|C|2|U/C|)), Chinese Journal of Computers3(29) (2006), 391–399.
14.
HuangG.S., ZengF.Z., ChenG.Y., etc., An algorithm of attribute reduction based on HU’s discernibility matrix by distinguishing capability, Journal of Chinese Computer Systems33(8) (2012), 1800–1804.
15.
YangC.J., GeH. and LiL.S., Attribute reduction of vertically partitioned binary discernibility matrix, Control and Decision28(4) (2013), 563–568.
