# A Fast Parallel Random Forest Algorithm Based on Spark
## 3 Improved Random Forest Algorithm
### Approximate Equal-Frequency Binning Method  
For a continuous data set, the traditional random forest algorithms have to discretize the continuous value and average all adjacent feature values to set candidate split points. Assuming that a continuous feature \(a\) has \(m\) different sample values, arranged from small to large \(a_{1},a_{2},\dots,a_{m}\), the traditional CART algorithm has to calculate the average of adjacent two sample values to obtain \(m-1\) candidate split points, where the \(i\)th candidate split point \(T_{i}\) is expressed as \(T_{i}=(a_{i}+a_{i+1})/2\). This means that it has to calculate \(m-1\) Gini coefficients for feature \(a\) to find out the optimal split point. Obviously, when dealing with \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Age** & **Have a Job** & **Credit Status** & **Label** \\ \hline youth & no & generally & no \\ youth & no & good & no \\ youth & yes & good & yes \\ youth & yes & generally & yes \\ youth & no & generally & no \\ middle aged & no & generally & no \\ middle aged & no & good & no \\ middle aged & yes & good & yes \\ middle aged & no & very good & yes \\ middle aged & no & very good & yes \\ old age & no & very good & yes \\ old age & no & good & yes \\ old age & yes & good & yes \\ old age & no & generally & no \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Credit data example. massive data, these candidate split points will cause lots of Gini coefficient calculations and reduce the efficiency of operation. To reduce the number of candidate split points, improve training efficiency, and ensure that classification accuracy is not significantly reduced, we propose an approximate equal-frequency binning method to optimize the number of candidate split points. The approximate equal-frequency binning method places the values of continuous features into different bins and continuously takes the average of the maximum value in the previous bin and the minimum value in the next bin to obtain all candidate split points. This method mainly includes two steps. In the first step, the feature values are sorted in ascending order, and the number of occurrences of each value is counted. Additionally, the total number of bins is usually set to the square root of the number of different values. In the second step, the feature values are classified into different bins one by one, and the boundaries between each bin are calculated to obtain all candidate split points. Algorithm 1 provides the specific steps of the approximate equal-frequency binning method. ```
Input: Continuous values of feature \(a\)\(\{a_{1},a_{2},\ldots,a_{n-1},a_{n}\}\) Output: All candidate split points of feature \(a\) Step 1: All feature values are sorted in ascending order; Step 2: Obtain all distinct values \(\Lambda^{\prime}=\{a^{\prime}1,a^{\prime}2,\ldots,a^{\prime}m-1,a^{\prime}m\}\) and the number of each value \(counts=\{count1,count2,\ldots,countm\}\); Step 3: Set the number of boxes \(bins=\text{int(sqrt(A^{\prime}))}\); Step 4: The size of the current bin is set to a constant \(S=\text{sum(}counts)/bins\); Step 5: The binning operation. All feature values are processed sequentially; Step 5.1 If \(count_{i}>=S\) then \(a^{\prime}_{i}\) is treated as a large number and boxed individually, set the average of this feature value and the next feature value as the candidate split point; Step 5.2 If \(count_{i}<S\) then add the remaining feature value in order until the number of feature value is greater than or equal to \(S\). At this time, the average of the largest feature value in the box and the next feature value not in the box is set as the candidate split point; Step 5.3 \(bins=bins-1\); if \(bins=1\), go to step 6, or jump to step 4. Step 6: Put all remaining feature value into the last bin and the algorithm ends. ```  
**Algorithm 1**Approximate equal frequency binning algorithm  
A simple example is described in Figure 1 to show the process of Algorithm 1.