# Heuristic Approaches to Attribute Reduction for Generalized Decision Preservation
## 4 Experimental Analyses
### Efficiency of Proposed Attribute Reduction Algorithms  
In this subsection, we will validate the efficiency of Algorithms 2 and 3. The running times of DMRAG, FGRAG, and BGRAG on the eight data sets are shown in Table 4, where \(|Q|\) denotes the number of the attributes in an attribute reduct \(Q\). For DMRAG, \(|Q|\) denotes the average number of the attributes of all reducts. Figures 2 and 3 demonstrate the change trends of the running times of three algorithms (DMRAG, FGRAG, and BGRAG) with increasing size of data set. From Table 4, it is easy to see that the running time of DMRAG was the maximum among those of the three algorithms. In other words, both FGRAG and BGRAG were more efficient than DMRAG on the eight data sets. The running time of FGRAG (BGRAG) was much less than that of DMRAG. For example, DMRAG on the data set Tic-Tac-Toe Endgame (Number 7) took 2888 ms, whereas FGRAG and BGRAG took 795 ms and 187 ms, respectively. The running time of DMRAG was about 3 times and 15 times than those of FGRAG and BGRAG, respectively. From Table 4, it is clear that both FGRAG and BGRAG had higher efficiencies than DMRAG. Due to avoiding calculating the core, BGRAG was usually more efficient than FGRAG. In Table 4, the running time of BGRAG was the minimum among those of the three algorithms on seven data sets (namely, Breast Cancer Wisconsin, Diabetic Retinopathy Debrecen, House, Liver Disorders, Seismic Bumps, Tic-Tac-Toe Endgame, and Wilt). Figure 2 indicates the change trends of the running times of three algorithms (DMRAG, FGRAG and BGRAG) with the number of the attributes increasing. In Figure 2a-h, the x-axis represents the number of the attributes, while the y-axis represents the time consumption of the three algorithms. The curves of FGRAG and BGRAG are totally under that of DMRAG. The r \begin{table}
\begin{tabular}{l l l l l l l l l} \hline \hline \multirow{2}{*}{**Data Sets**} & \multirow{2}{*}{**Objects**} & \multirow{2}{*}{**Attributes**} & \multicolumn{2}{c}{**FGRAG**} & \multicolumn{2}{c}{**BGRAG**} & \multicolumn{2}{c}{**DMRG**} \\ \cline{3-8}  & & & \(|Q_{1}|\) & **t/ms** & \(|Q_{2}|\) & **t/ms** & \(|Q_{3}|\) & **t/ms** \\ \hline
1 & 748 & 4 & 2 & 46 & 2 & 46 & 2 & 234 \\
2 & 699 & 9 & 4 & 312 & 4 & 140 & 4.6 & 1029 \\
3 & 1151 & 19 & 16 & 1687 & 16 & 1029 & 16 & 5678 \\
4 & 506 & 13 & 11 & 405 & 11 & 202 & 11 & 920 \\
5 & 345 & 6 & 5 & 109 & 5 & 46 & 5 & 218 \\
6 & 2584 & 15 & 13 & 3123 & 13 & 1484 & 13 & 11,140 \\
7 & 958 & 9 & 8 & 795 & 8 & 187 & 8 & 2888 \\
8 & 4339 & 5 & 5 & 592 & 5 & 353 & 5 & 34,264 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Time consumption comparison of three algorithms. BGRAG were much less than that of DMRAG when dealing with the same amount of attributes. The curve of DMRAG rises rapidly when the number of the attributes increases, while those of FGRAG and BGRAG rise slowly. For example, in Figure 2a, the running time of DMRAG increased by 242 ms when the number of the attributes varied from 0 to 1, whereas the running times of FGRAG and BGRAG increased by only 10 and 6 ms, respectively. For Figure 2b, the running time of DMRAG increased by 796 ms when the number of the attributes varied from 0 to 2, whereas the running times of FGRAG and BGRAG increased by only 23 and 13 ms. It is obvious that Figure 2h is different from the others in Figure 2. The running time of FGRAG or BGRAG was much less than that of DMRAG when dealing with the same number of attributes. The differences between FGRAG and BGRAG in time consumption were much less than the differences between FGRAG (BGRAG) and DMRAG. Thus, the curves of FGRAG and BGRAG were relatively similar and very close to the x-axis. The running times of the three algorithms (DMRAG, FGRAG, and BGRAG) all increased with the number of the attributes. Nevertheless, the relationship between the number of the attributes and the running time was not strictly monotonic. For example, in Figure 2f, the running times of DMRAG were 14,126 ms and 13,907 ms, respectively, when the numbers of attributes were 7 and 8.