Deep Forest with Hashing Screening and Window Screening

Perceptual hashing [27] is an effective approach for image retrieval in which images are converted into binary sequences for retrieval. The most representative perceptual hashing algorithms are aHash [28], pHash [29], and dHash [30]. To process data efficiently, we employ aHash to screen out redundant feature vectors, using a hashing screening mechanism. The main steps of aHash are as follows:

Step 1: Resize the image (this is a fast way to match an image of any size).

Step 2: Convert the resized image to grayscale.

Step 3: Compute the mean value of the grayed image pixels.

Step 4: Compare each pixel value with the mean value, and set any pixels larger than the mean to one, and the other pixels to zero.

Step 5: Combine the binarization results into binary sequences.

Finally, aHash retrieves images by comparing their binary sequences. The process used by the aHash algorithm is illustrated in Figure 1.

As an improved version of gcForestcs, DBC-Forest adopts a binning confidence screening mechanism to avoid the mispartitioning of instances with low accuracy into high-confidence regions. More specifically, the binning confidence screening mechanism packs all instances into bins, and DBC-Forest then calculates the accuracy of all bins to locate mispartitioned instances. This mechanism can be summarized as follows.

Step 1: Calculate the confidence of each instance at the current level. We utilize confidence as the criterion for selecting instances, and this is generated by the estimated class vector. For example, if the estimated class vector for instance x is (0.5, 0.3, 0.2), its confidence is 0.5.

Step 2: Rank instances based on their confidences. We then obtain instances $(\bm{x}_{s1},\bm{x}_{s2},\cdots,\bm{x}_{sm})$, where $\bm{x}_{s1}$ is the highest confidence instance, and put these instances into $k$ bins. Each bin $\bm{b}_{t}$ (1$\leq t\leq k$ ) can be obtained according to Equation (1):

Step 3: Calculate the accuracy for each bin. The accuracy $\bm{P}_{t}$ of $\bm{b}_{t}$ is calculated according to Equation (2):

where $p({\bm{x}_{si}})$ is the prediction of $\bm{x}_{si}$ at the current level, and $\bm{y}_{si}$ is the label of $\bm{x}_{si}$.

Step 4: Determine the threshold. In DBC-Forest, the accuracy of each bin is compared with the target accuracy $TA$ from 1 to $k$. If $\bm{P}_{j+1}$ is the first bin for which the accuracy is lower than $TA$, then we utilize the confidence of $\bm{x}_{s(m\times\frac{j}{k})}$ as the threshold.

Step 5: Compare the confidences of the instances with the threshold. If the confidence of the instance is larger than the threshold, then the instance is used to produce a final prediction at the current level; otherwise, the instance is passed to the next level.

Multi-grained scanning is a structure for processing high-dimensional data that can achieve excellent performance on image data. However, the time cost of multi-grained scanning is increased by the presence of redundant feature vectors, which are produced by sampling the same features from instances. Figure 2 shows the production of a redundant feature vector by a sliding window.

To reduce the number of redundant feature vectors, we apply the aHash algorithm to evaluate the similarity between feature vectors and eliminate the high similarity feature vectors. This process can be summarized as follows.

Step 1: Group feature vectors according to their locations, which gives $(\bm{v}_{1},\bm{v}_{2},\cdots,\bm{v}_{r})$ according to Equation (3):

The relationships between these vectors are illustrated in Figure 3. For example, $\bm{f}_{1,1}$ and $\bm{f}_{1,2}$ are members of group $\bm{v}_{1}$, and are the first feature vectors of instances $\bm{x}_{1}$ and $\bm{x}_{2}$, respectively.

Step 2: Obtain binary sequences for all feature vectors using aHash. For example, $(b_{r,i}(k_{1}),b_{r,i}(k_{2}),\\ \dots,b_{r,i}(k_{c}))$ is the binary sequence of $b_{r,i}$, where $c$ is the length of the binary sequence and $b_{r,i}(k_{j})$ is obtained by aHash.

Step 3: Calculate the distances between the features in each group. In group $\bm{v}_{r}$, the $j$-th feature distance $\bm{v}_{r}(k_{j})$ can be calculated using Equation (4):

Step 4: Calculate the distance between each pair of groups. This distance represents the differences in the feature vectors in the groups. The larger the distance, the greater the difference in the feature vectors. The distance $d_{r}$ of group $\bm{v}_{r}$ can be calculated using Equation (5):

Step 5: Rank the groups in descending order based on their distances. We then obtain a new instances order $(\bm{w}_{1},\bm{w}_{2},\cdots,\bm{w}_{r})$ and their distances $(e_{1},e_{2},\cdots,e_{r})$, where $e_{1}$ is the largest.

Step 6: Calculate the number of groups contained in each percentage of $D$, where $D$ is the sum of all distances, i.e., $D=\sum_{i=1}^{r}e_{i}$ . We then obtain $(N(100),N(99),\cdots,N(1))$ based on $(e_{1},e_{2},\cdots,e_{r})$. The calculation of $N(g)$ is carried out using Equation (6):

Step 7: Determine the threshold $HT$. We compare $r/50$ with $N(100)-N(99),N(99)-N(98),\cdots,N(2)-N(1)$ in order. If $N(p)-N(p-1)$ is the first term that is lower than or equal to $r/50$, we utilize $e_{h}$ as the threshold $HT$, where $h$ is the value of $N(p)$ and $p\in\{100,99,\cdots,2\}$. $HT$ is calculated using Equation (7):

where $p=max\{u|N(u)-N(u-1)\geq\frac{r}{100},u=100,99,\dots,2\}$.

Step 8: Compare the distances with $HT$. If the distance of a group is lower than the threshold, we eliminate the feature vectors in the group; otherwise, the feature vectors in the group are converted to class vectors and input into the cascade structure.

To illustrate the above steps, we present an example below.

Example 1. Suppose we have four groups $(\bm{v}_{1},\bm{v}_{2},\bm{v}_{3},\bm{v}_{4})$, for which the feature vectors are $(\bm{f}_{1,1}=(0,1)$, $\bm{f}_{1,2}=(0,1))$, ($\bm{f}_{2,1}=(1,1)$, $\bm{f}_{2,2}=(1,1))$, $(\bm{f}_{3,1}=(1,0),\bm{f}_{3,2}=(0,1))$, $(\bm{f}_{4,1}=(0,1),\bm{f}_{4,2}=(1,0))$. We know that the values of $\bm{f}_{1,1}(k_{1})$ and $\bm{f}_{1,2}(k_{1})$ are zero. Hence, according to Equation (4), the value of $\bm{v}_{1}(\bm{k}_{1})=\frac{0+0}{2}=0$. Similarly, the values of ($\bm{v}_{1}(k_{1})$, $\bm{v}_{1}(k_{2})$), ($\bm{v}_{2}(k_{1})$, $\bm{v}_{2}(k_{2})$), ($\bm{v}_{3}(k_{1})$, $\bm{v}_{3}(k_{2})$), and ($\bm{v}_{4}(k_{1})$, $\bm{v}_{4}(k_{2})$) are (0, 0), (0, 0), (0.5, 0.5), and (0.5, 0.5), respectively. Since $\bm{v}_{4}(k_{1})=0.5$ and $\bm{v}_{4}(k_{2})=0.5$, the distance of $\bm{v}_{4}$ is 0.5, i.e., $d_{4}$=$\frac{0.5+0.5}{2}=0.5$. Thus, $(d_{1},d_{2},d_{3},d_{4})$ are (0, 0, 0.5, 0.5). We then rank the groups according to their distances. Finally, we obtain ($\bm{w}_{1}$, $\bm{w}_{2}$, $\bm{w}_{3}$, $\bm{w}_{4}$), for which the values are $(e_{1}=0.5,e_{2}=0.5,e_{3}=0,e_{4}=0)$. Hence, $D=\sum_{i=1}^{4}e_{i}=0.5+0.5+0+0=1$. We now obtain the values of $(N(100),N(99),\cdots,N(1))$. According to Equation (6), the values of $N(100),N(99),\dots,N(51)$ are 2, since $e_{1}+e_{2}\geq 100\times\frac{D}{100}=1$, and $e_{1}+e_{2}\geq 51\times\frac{D}{100}=0.51$. Similarly, the values of $N(50),N(49),\cdots,N(1)$ are 1, since $e_{1}\geq 50\times\frac{D}{100}=0.50$ and $e_{1}\geq 1\times\frac{D}{100}=0.01$. We know that there are four groups, meaning that $r=4$, and $\frac{r}{50}=\frac{4}{50}=0.08$. According to Step 7, $p=100$, since $N(100)-N(99)$ is 0, and this is the first value lower than 0.08. Since $p=100$ and $N(100)=2$, according to Equation (7), we select the second group distance $e_{2}$ as the threshold, i.e., $h=2$. Finally, we eliminate $\bm{w}_{3}$ and $\bm{w}_{4}$, since their distances $e_{3}$ and $e_{4}$ are lower than $e_{2}$. $\bm{w}_{1}$ and $\bm{w}_{2}$ are converted to class vectors, and are input into the cascade structure. Figure 4 illustrates the hashing screening mechanism.

Example 1 verifies that hashing screening can effectively eliminate the redundant feature vectors.

As an improved version of gcForestcs, DBC-Forest avoids the mispartition of instances and thus improves the performance. However, its performance depends on the hyperparameter $k$, which represents the number of bins used to partition instances. Specifically, the smaller the value of $k$, the larger the threshold. Example 2 illustrates this phenomenon.

Example 2. Suppose we have 16 instances sorted by confidence, as illustrated in Figure 5. Of these, instances 1, 2, 4, 5, 6, 7, 8, and 11 are correct predictions, and the others are incorrect. We set two cases with $k$ = 8 and $k$ = 4 under the condition of the hyperparameter $TA$ = 70%. In the case of $k$ = 8, instance 2 is selected as the threshold in DBC-Forest, since the accuracy of bin II is 50%. In the case of $k$ = 4, instance 8 is selected, since the accuracy of bin III is 25%. This example shows that the performance of DBC-Forest depends on the hyperparameter $k$. In other words, DBC-Forest cannot achieve high accuracy if the hyperparameter $k$ is not suitable for the dataset.

To address this drawback of DBC-Forest, we propose a window screening mechanism, in which a self-adaptive approach is used to calculate the threshold. Unlike the fixed window used in DBC-Forest, this approach uses windows with variable size. The mechanism can be summarized as follows.

Step 1: Rank the instances based on their confidences, and obtain $(\bm{x}_{1},\bm{x}_{2},\cdots,\bm{x}_{m})$.

Step 2: Establish a window $\bm{W}$ for which the parameters are $c$, $u$, and $l$, where $c$ is the size of the window, and $u$ and $l$ are the starting and ending points of the window, respectively. Initially, the values of $c$, $u$, and $l$ are $m/2$, 1, and $m/2$, respectively. The window $\bm{W}$ can be defined according to Equation (8):

Step 3: Slide the window $\bm{W}$ using a step size of one (i.e., increase the values of $u$ and $l$), and calculate the accuracy of window $P_{\bm{w}}$ using Equation (9):

where $p(\bm{x}_{i})$ is the prediction $\bm{x}_{i}$, and $\bm{y}_{i}$ is the label of $\bm{x}_{i}$. If the accuracy is larger than the target accuracy $TA$ and the value of $c$ is not two, the window stops sliding.

Step 4: Reset the window parameters: the value of $c$ is reduced by half, $u$ does not change, and $l=u+c-1$.

Step 5: Iterate Steps 3 and 4. Set the first instance in the window as the threshold $WT$ when $c$ is equal to or lower than two.

Step 6: Compare the confidence values of the instances with the threshold. If the confidence of the instance is larger than the threshold, then the instance produces a final prediction at the current level; otherwise, the instance is passed to the next level.

Unlike in the binning confidence screening approach, the threshold in window screening can be obtained by a self-adaptive method. Moreover, the performance of this approach is better than DBC-Forest, since the bin size hyperparameter is not adjusted. An illustrative example is given below.

Example 3. In this example, we set the target accuracy $TA$ to 70%, and employ the same 16 instances as in Example 2. The process of window screening is shown in Figure 6. In stage 1, we set the initial values to $c=8$, $u=1$, and $l=8$. We know that the accuracy of the window is 0.875, which is greater than $TA$. Thus, we slide the window $\bm{W}$ using a step size of one. We know that when $u=2$ and $l=9$, the accuracy of the window is also 0.875. However, when $u=3$ and $l=10$, the accuracy of the window is 0.625, which is less than $TA$. We then enter stage 2, and reset the values to $c=4$, $u=3$, and $l=6$. We know that the accuracy of this window is 0.75, which is greater than $TA$. We then iterate this process until $c=4$, $u=7$, and $l=10$. In this case, the accuracy of the window is 0.50, which is less than $TA$. We then enter stage 3, and reset the values to $c=2$, $u=7$, and $l=8$. In this case, the accuracy of the window is 1.0, which is greater than $TA$. We iterate this process until $c=2$, $u=8$, and $l=9$. In this case, the accuracy of the window is 0.50, which is less than $TA$. Since $c=2$, the window does not shrunk further. Hence, the threshold is the confidence of instance 8, which is the same as for the case of $k=4$ in Example 2.

HW-Forest is an improved version of gcForest which consists of two parts: multi-grained scanning with hashing screening and cascade structure with window screening. Figure 7 illustrates the overall procedure of HW-Forest. In the first part, the instances are input into the multi-grained scanning stage. We then apply hashing screening to eliminate the redundant feature vectors, and the remaining feature vectors are converted into class vectors using a random forest algorithm. The second part is a cascade forest structure with window screening mechanism to reduce the time costs and memory requirements. The class vectors in the form of the original data are input into the first level. A window screening mechanism is used to divide all instances into high-confidence and low-confidence instances at each level. High-confidence instances are used to produce the final prediction at the current level, while low-confidence instances are passed to the next level.

Algorithm 1 shows pseudocode for HW-Forest.

Parameter Settings. In all of our experiments, the models used the same parameters, which were as follows. For the cascade structure, each level was produced by five-fold cross-validation and had a random forest and a completely-random forest. Each forest contained 50 decision trees. The number of cascade levels stopped increasing when the current level did not give an improvement in the accuracy of the previous level. For multi-grained scanning, we established three windows to scan the high-dimensional data, with sizes of 4×4, 6×6, and, 8×8. Each window had a random forest and a completely-random forest, and the number of decision trees in these two forests was 30. $TA$ was set to decrease the error rate by 1/2.

Datasets. We used nine benchmark datasets to verify the performance of HW-Forest. Table 1 summarizes the statistics of these datasets. Of these, MNIST, EMNIST, FASHION-MNIST, and QMNIST were commonly used high-dimensional datasets [31, 32, 33], while ADULT, BANK, YEAST, LETTER, IMDB were low-dimensional datasets.

Evaluation metrics and methodology. In all of our experiments, we used the predictive accuracy as a measure of the classification performance, as it is suitable for balanced datasets. The training time was used to evaluate the efficiency. Statistical tests were also adopted as measurement criteria.

Hardware. In these experiments, we used a machine with 2×2.20 GHz CPUs (10 cores) and 128 GB main memory.

Baseline methods. To validate the performance of HW-Forest, we selected four state-of-the-art algorithms as competitive models: gcForest [9], gcForestcs [12], DBC-Forest [13], and AWDF [25]. To verify the effect of our hashing screening mechanism, we introduced this mechanism into gcForest, gcForestcs, DBC-Forest, and AWDF, to give H-gcForest, H-gcForestcs, HDBC-Forest, and H-AWDF, respectively.

gcForest [9]: This is a deep learning model that is inspired by deep neural networks, and adopts multi-grained scanning and a cascade structure to process the data.

gcForestcs [12]: This is an improved gcForest model in which a confidence screening mechanism is introduced to screen the instances at each level.

DBC-Forest [13]: This is an improved gcForestcs model. To increase the accuracy of gcForestcs, binning confidence screening is used to avoid the mispartitioning of instances at each level.

AWDF [25]: This is an adaptive weighted model in which adaptive weighting is used for every training instance at each level.

H-gcForest, H-gcForestcs, HDBC-Forest, and H-AWDF: To verify the influence of the hashing screening mechanism, we introduced it into gcForest, gcForestcs, DBC-Forest, and AWDF, to give H-gcForest, H-gcForestcs, HDBC-Forest, and H-AWDF, respectively.

H-Forest (H-gcForest) and W-Forest: To validate the influence of two screening mechanisms, we developed H-Forest (H-gcForest) and W-Forest. These are versions of HW-Forest without the window and hashing screening mechanisms, respectively.

To validate the performance of HW-Forest, we developed the following five research questions (RQ).

RQ 1: What is the effect of hashing screening, and can it be adopted in other models?

RQ 2: What is the effect of hashing screening with different window sizes?

RQ 3: Compared with DBC-Forest, what is the effect of HW-Forest at each level?

RQ 4: What is the difference between the thresholds in DBC-Forest and HW-Forest?

RQ 5: Compared with state-of-the-art alternatives, what is the performance of HW-Forest?

To answer RQ 1, we introduced hashing screening into gcForest, gcForestcs, DBC-Forest, and AWDF, and compared their accuracies with the original models to verify the influence of hashing screening. To address RQ 2, we selected 10 instances from FASHION-MINST to investigate the effect of hashing screening with different window sizes, and to explore the performance of HW-Forest with different window sizes. In response to RQ 3, we compared the accuracy and the number of instances between DBC-Forest and HW-Forest at each level. Specifically, we used MNIST, EMNIST, FASHION-MNIST, QMNIST, and IMDB in this experiment. To answer RQ 4, we explored the thresholds used in the window screening and binning confidence screening mechanisms to show the difference. For RQ 5, we compared the performance of HW-Forest with gcForest, gcForestcs, DBC-Forest, AWDF, H-Forest, and W-Forest.

To analyze the effect of the hashing screening mechanism, we conducted four experiments to compare the performance between pairs of models: gcForest and H-gcForest; gcForestcs and H-gcForestcs; gcForestcs and H-gcForestcs; and AWDF and H-AWDF. Experiments were conducted on the MNIST, EMNIST, FASHION-MNIST, and QMNIST datasets, since these need to be processed by multi-grained scanning. The results of this comparison are shown in Tables 2 to 6.

The experimental results give rise to the following observations.

1. Hashing screening effectively decreases the time cost for all datasets. For example, from Table 3, it can be seen that H-gcForestcs has a time cost that is 482.5 s (41.83%) lower than for gcForestcs on the MNIST dataset. This phenomenon can also be seen in the other tables. The reason for this is as follows. We know that the greater the number of feature vectors, the higher the time cost. Hashing screening can effectively eliminate the redundant feature vectors, and hence the time cost is reduced.

2. Hashing screening does not influence the accuracy of the models. The results of 20 experiments are presented in Tables 2 to 6, and it can be seen that the models with hashing screening have better accuracy than the original models in 11 experiments, worse accuracy than the original models in seven experiments, and the same as the original models in two experiments. For example, Table 3 shows that H-gcForestcs has better accuracy than gcForestcs on three datasets (EMNIST, FASHION-MNIST, and QMNIST) and worse accuracy than gcForestcs on MNIST. The reason for this is as follows. Since the important feature vectors have larger distances than the redundant feature vectors, hashing screening effectively screens for important feature vectors based on their distances. More importantly, these redundant feature vectors make lower contributions to the classification accuracy. Hence, the models using hashing screening have almost the same accuracy as the original models.

To further evaluate the influence of hashing screening, we applied a $t$-test for statistical hypothesis test.

To measure the influence of the hashing screening mechanism, we applied a $t$-test to the time cost and accuracy. More specifically, we compared the accuracy and time cost of the models at each fold, and obtained the different values $(D_{1},D_{2},\cdots,D_{k})$. We then calculated the statistics according to $\left|\sqrt{k}\mu/\sigma\right|$, where $k$ is the number of cross-validation folds, $\mu$ is the mean of $(D_{1},D_{2},\cdots,D_{k})$, and $\sigma$ is the standard deviation of $(D_{1},D_{2},\cdots,D_{k})$. The results for the time cost and accuracy are shown in Tables 7 and 8, respectively.

We can reject (R) or accept (A) the null hypothesis based on the statistics. For example, for the MNIST dataset in Table 8, the accuracy of H-gcForest is not significantly different from that of gcForest, since $T_{0.05,4}$ is 2.13, which is larger than the $t$-test statistic of 0.88. Furthermore, for the MNIST dataset, Table 7 shows that the time costs of H-Forest and HW-Forest are significantly different, since the $t$-test statistic is 192.15, which is much larger than 2.13. The results of these statistical hypothesis tests showed that hashing screening effectively reduces the time cost by eliminating redundant feature vectors, without influencing the accuracy. More importantly, when used with other deep forest models, hashing screening can achieve the same accuracy as the original models.

Based on the above experimental results and statistical analysis, we can conclude that hashing screening can reduce the time cost without influencing the accuracy.

In this section, we compared raw instances with instances processed by hashing screening, to explore the effect of the hashing screening mechanism. We conducted experiments with windows of size 2×2, 4×4, 6×6, and 8×8, and selected 10 instances from the FASHION-MNIST dataset. The results are shown in Figure 8.

Two observations can be made from these results.

1. The number of redundant feature vectors produced by a large window is significantly lower than for a small window. For example, the number of redundant feature vectors in Figure 8(f) is two, for a window size of 8×8; however, the number of redundant feature vectors in Figure 8(b) is 55, for a window size of 2×2. The reason for this is that on the FASHION-MNSIT dataset, the difference between the number of redundant feature vectors and important feature vectors is small. As the window size increases, the probability of containing important feature vectors increases, and thus the difference becomes smaller. Hence, with an increase in the window size, the number of redundant feature vectors decreases.

2. Hashing screening reduces the number of redundant feature vectors while retaining important information. For example, as shown in Figure 8(b), hashing screening retains the important features of instances, such as the toes of shoes and the sleeves of coats. The same phenomenon can be seen in the other figures. The reason for this is as follows. Since the important feature vectors are significant different from each other, the distance between them is larger than for the redundant feature vectors. The redundant feature vectors are therefore eliminated and the important feature vectors are retained based on their distances.

To further explore the effect of the hashing screening mechanism, we conducted four experiments with windows of size 2×2, 4×4, 6×6, and 8×8. In each experiment, we compared the accuracy and time cost of W-gcForest and HW-gcForest for different window sizes. The results are shown in Table 9.

Based on these results, two observations can be made.

1. With an increase in the window size, the time required for hash screening decreases. As shown in Table 9, this time is reduced by 227.08 s (29.80%) and 56.83 s (5.57%) when the window sizes are 2×2 and 6×6, respectively. The reason for this is as follows. As in the previous analysis, with an increase in the window size, the number of redundant feature vectors decreases, and hence the time required for hash screening decreases.

2. Hashing screening does not affect the accuracy of the model with different window sizes. For example, HW-Forest has the same accuracy as W-Forest for window sizes of 8×8 and 6×6, and has better accuracy than W-Forest when the window sizes are 4×4 and 2×2. This phenomenon indicates that using the distance of the feature vector as the criterion for eliminating redundant feature vectors can effectively identify redundant feature vectors with different window sizes. In other words, hashing screening is robust under different window sizes.

To validate the effect of window screening, we observed the accuracy and the number of instances at each level. We selected DBC-Forest as a competitive algorithm and used the MNIST, EMNIST, FASHION-MNIST, QMNIST, and IMDB datasets, since our model and competitive algorithm produced more layers for these datasets. Comparisons of the accuracy and numbers of instances for MNIST, EMNIST, FASHION-MNIST, QMNIST, and IMDB are shown in Figures 9 to 13, respectively.

These results give rise to the following observations.

1. HW-Forest achieves higher accuracy than DBC-Forest at each level. For example, it can be seen from Figure 13 that for the IMDB dataset, the accuracy of HW-Forest is 0.09% higher than DBC-Forest at the second level, and 0.19% higher than DBC-Forest at the last level. The reason for this is that window screening is a self-adaptive mechanism, and produces more reasonable thresholds than the binning screening mechanism without the need for hyperparameter tuning. Hence, the instances screened by HW-Forest have higher accuracy than those screened by DBC-Forest at each level.

2. HW-Forest has a lower number of instances than DBC-Forest at each level. For example, on the MNIST dataset, HW-Forest has 1,213 fewer instances than DBC-Forest at the second level, and 146 fewer instances than DBC-Forest at the last level. The reason for this is that since the performance of DBC-Forest depends on the hyperparameters, it is not easy to find high-confidence instances. However, HW-Forest adopts a self-adaptive mechanism to precisely select high-confidence instances.

In this section, we explore the difference between window screening and binning confidence screening. To demonstrate the performance of our approach on different types of datasets, we used MNIST, IMDB, LETTER, and BANK. Comparisons of the thresholds for the MNIST, IMDB, LETTER, and BANK datasets are shown in Figures 14 to 17, respectively.

As shown in Figures 14 to 17, HW-Forest gives a more reasonable threshold than DBC-Forest. For example, on the MNIST dataset, DBC-Forest cannot avoid accuracy fluctuations, and some high-confidence instances screened with this threshold have low accuracy. Using HW-Forest, the screened high-confidence instances have significantly higher accuracy. The reason for this is that unlike the dependence of DBC-Forest on hyperparameter tuning, HW-Forest selects instances at each level without the need for hyperparameter tuning. Hence, HW-Forest gives a more reasonable threshold than DBC-Forest.

In this section, to validate the accuracy of HW-Forest, we used gcForest, gcForestcs, DBC-Forest, AWDF, H-Forest, and W-Forest as competitive algorithms. Experiments were conducted on nine benchmark datasets, and comparisons of the results for accuracy and time cost are shown in Tables 10 and 11, respectively.

From these results, we can make the following observations.

1. As shown in Table 10, HW-Forest achieves the highest accuracy on most datasets. For example, on the QMNIST dataset, HW-Forest achieves the highest accuracy of 99.07%. The same phenomenon can be found for the other datasets. The reason for this is that HW-Forest uses window screening to improve the accuracy of DBC-Forest, and this produces more reasonable thresholds than the binning screening mechanism. Hence, HW-Forest achieves higher accuracy than DBC-Forest, and also achieves higher accuracy than other models. As shown in Table 11, for high-dimensional datasets, HW-Forest runs faster than the competitive models in most cases; for low-dimensional datasets, HW-Forest runs slower than gcForestcs, but faster than the other competitive models. For example, on the MNIST dataset, the time cost for HW-gcForest is 1135.42 s, which is faster than all other models. On the ADULT dataset, the time cost of HW-gcForest is 10.15 s, which is slower than gcForestcs but faster than the other competitive models. The reason for this is that for high-dimensional datasets, deep forest models take a long time to find the classification models. If we can reduce the number of feature vectors, the running time can be significantly reduced. HW-Forest employs hashing screening to effectively eliminate redundant feature vectors, and therefore runs faster than the competitive models for high-dimensional datasets. However, for low-dimensional datasets, the deep forest models take only a short time to find the classification models, and these datasets do not need to be processed by multi-grained scanning. Hence, the running time of precisely selecting instances at each level cannot be neglected, and HW-Forest runs slower than gcForestcs.

2. HW-Forest and W-Forest achieve the same accuracy on most datasets. For example, from Table 10, we can see that for the QMNIST dataset, HW-Forest and W-Forest achieve the same accuracy of 99.13%. The same effect can be seen for the ADULT, BANK, YEAST, IMDB, and LETTER datasets. For the MNIST, FASHION-MNIST, and EMNIST datasets, the results for the accuracy are close. The reason is for this is that low-dimensional datasets do not need to be processed by multi-grained scanning. The results of HW-Forest are therefore the same as those of W-Forest, since W-Forest is simply the HW-Forest model without the hashing screening mechanism. For high-dimensional datasets, as demonstrated in our analysis of the effect of hashing screening in Section 5.3, the hashing screening mechanism does not influence the accuracy of the model. Hence, the accuracies of HW-Forest and W-Forest are almost the same.

To further evaluate the performance of DBC-Forest, we applied Friedman and Nemenyi tests [34] for statistical hypothesis test.

1. Friedman test: This test ranks the models according to their accuracy, where the highest is given a score of one, the second highest has a score of two, and so on. The mean values for the gcForest, gcForestcs, DBC-Forest, AWDF, HW-Forest, H-Forest, and W-Forest models were 5.89, 5.33, 3, 5.11, 1.61, 5.44 and 1.61, respectively. We then calculated the Friedman test statistic according to $(N-1)\times\tau_{\chi^{2}}/(N\times(k-1)-\tau_{\chi^{2}})$, where $\tau_{\chi^{2}}=12\times N\times(\sum_{i=1}^{k}r_{i}^{2}-k\times(k+1)^{2}/4)/k\times(k+1)$, and $N$ and $k$ are the number of datasets and models, respectively. The Friedman statistic was 24.371, which was larger than $T_{0.05,4}$ = 2.132. Hence, we reject the null hypothesis.

2. Nemenyi test: To further compare the models, we adopted the Nemenyi test to calculate the critical difference value. The result was 2.742, according to the formula $q_{0.1,7}\sqrt{k(k+1)/6N}$, where $q_{0.1,7}$ = 2.693. As shown in Figure 18, the accuracy of HW-Forest is the same as for W-Forest, which indicates that HW-Forest is statistically consistent with W-Forest. More importantly, the accuracy of HW-Forest is significantly higher than the other models except W-Forest, meaning that HW-Forest statistically outperformed the other competitive models.