# A Fast Parallel Random Forest Algorithm Based on Spark
## 4 Parallelization of Random Forest Based on Spark
### Parallel Decision Tree Training Strategy Based on a Forest Sampling Index Table  
In the traditional random forest algorithm, it is necessary to obtain a training subset for each decision tree through the random sampling method (bagging) and construct a decision tree based on each training subset. The training process is shown in Figure 2.  
Usually, the size of the training subset is proportional to the size of the original data set. Therefore, when the original data set is large, Spark has to allocate extra space to store the sampled training subset, which causes a large number of disk I/O operations and less computational efficiency. To address this issue, we define a forest sample index table (FSI) to record the indexes of all training subsets to reduce the storage requirement. The detailed definition is as follows.  
Figure 2: Traditional decision tree training process.  
**Definition 3**.: _Given a data set \(D\), the forest sampling index table FSI on \(k\) training subsets is defined as follows:_  
\[FSI=\begin{bmatrix}C_{01},C_{02},\dots,C_{0n}\\ C_{11},C_{12},\dots,C_{1n}\\ \dots\\ C_{(k-1)1},C_{(k-1)2},\dots,C_{(k-1)n}\end{bmatrix}\]  
_FSI is a \(k\times n\) binary matrix. Each row represents the index of a training subset, which can be used to train a decision tree. \(C_{ij}\) represents the sampling situation of sample \(j\) with respect to \(i\)th training subset. If \(C_{ij}\) is \(1\), it means that the \(i\)th subset contains sample \(j\), otherwise sample \(j\) does not participate in the construction process of the \(i\)th decision tree._  
The FSI table records the indexes of all the \(k\) subsets and is allocated to each slave node. During the training process of each decision tree, the related data is loaded from the RDD data partitions according to the FSI table, and the related Gini coefficient is calculated directly in memory. That is, it does not store the training subset repeatedly.  
The detailed parallel decision tree training process based on the FSI table is shown in Figure 3. First, the FSI table is allocated to all slave nodes. At the same time, the original data set is divided into \(k\) RDD data partitions by _mapPartition_ function, and each RDD data partitions is allocated to the corresponding slave nodes to achieve data parallel processing, namely Partition_1, Partition_2,..., and Partition_k, respectively. Next, each slave node processes the corresponding RDD data partition based on the FSI table and calculates the Gini coefficients of the related candidate splitting points. Each Gini coefficient calculation task \(T_{Gini}\) loads data records from the RDD partition according to the indexes in the FSI table. Finally, the candidate splitting points of all slave nodes are compared by _reduceByKey_ function to find out the optimal one for a decision tree.  
For example, tasks \(T_{Gini1,1}\),\(T_{Gini1,2}\) and \(T_{Gini1,3}\) on slave1 calculate the Gini coefficients of decision trees \(1\), \(2\), and \(3\), respectively, and find out the local best split point. Next, these parallel outputs of \(T_{Gini}\) are combined by _reduceByKey_ function to find out the best  
Figure 3: Parallel decision tree training strategy based on the FSI table.  
global split point. In detail, tasks \(\{T_{Gini1.1},T_{Gini1,2},T_{Gini1.3}\}\) are used to construct decision tree 1, tasks \(\{T_{Gini2.1},T_{Gini2,2},T_{Gini2.3}\}\) are used to construct decision tree 2, and tasks \(\{T_{Gini3.1},T_{Gini3.2},T_{Gini3.3}\}\) are used to construct decision tree 3.