# A Fast Parallel Random Forest Algorithm Based on Spark
## 4 Parallelization of Random Forest Based on Spark
### Gini Coefficient Calculation Optimization  
According to formula (3), the Gini coefficient of each candidate split point depends on two subsets \(D_{1}\), \(D_{2}\), and their class distribution. This means that the traditional random forest algorithm has to traverse the entire data set when dealing with continuous features. If there were \(n-1\) candidate split points for a certain feature, then it is necessary to traverse (\(n-1\)) training subsets. Obviously, the computational efficiency is low for a big data set.  
In this paper, we declare two dictionaries named _left_ and _right_ to optimize the Gini coefficient calculation. The dictionary is expressed as \(\{\emph{key1:value1},\emph{key2:value2},\ldots,\emph{key n:value n}\}\), where _key_ is the feature value category, and _value_ is the number of categories. _Left_ and _right_ are used to store the information of each category in the left and right subsets after splitting, respectively.  
At the initial state, _left_ is an empty dictionary, and _right_ contains all categories and their corresponding number of occurrences in the local data set. Next, for each candidate split point, the feature value smaller than the split point is divided into the left subset, and the other feature values still remain in the right subset. On this basis, the additional category and numbers in the left subset are accumulated into the _left_ dictionary, and are subtracted from the _right_ dictionary. At this time, the _left_ and _right_, respectively, represent the category distribution of the left and right subsets. The Gini coefficient of this candidate split point can be directly calculated based on the _left_ and _right_ dictionaries. In detail, _value_\(\_k\) represents \(\mid\)\(C_{k}\)\(\mid\), which means the number of _k_th sample categories. The sum of all _value_ in the _left_ dictionary means \(\mid\)\(D_{1}\)\(\mid\), and the sum of all _value_ in the _right_ dictionary represents \(\mid\)\(D_{2}\)\(\mid\). Therefore, the related Gini coefficient can be easily calculated based on the two dictionaries, and it is unnecessary to traverse the entire data set. A simple example is given here to illustrate this optimization process.  
Table 2 shows a feature column and its corresponding categories. Initialize _left_ = {} and traverse the entire data set to obtain _right_ = {1:3, 2:1, 3:1}. For the first candidate split point 0.2, the states of two dictionaries are altered as _left_ = {1:1} and _right_ = {1:2, 2:1, 3:1}. At this point, the number of samples in the left subset is \(\mid\)\(D_{1}\)\(\mid\) = 1, and the number of samples in the right subset is the sum of _value of right_ dictionary \(\mid\)\(D_{2}\)\(\mid\) = 4. In addition, the number of sample categories in the left subset is \(\mid\)\(C_{1}\)\(\mid\)\(=\) 1, and the number of sample categories in the right subset is \(\mid\)\(C_{1}\)\(\mid\)\(=\) 2, \(\mid\)\(C_{2}\)\(\mid\)\(=\) 1,\(\mid\)\(C_{3}\)\(\mid\) = 1. According to formula (3), the Gini coefficient of this candidate split point is 0.45. Similarly, for the second split point 0.5, the states of two dictionaries are updated to _left_ = {1:1, 2:1} and _right_ = {1:2, 3:1}, \(\mid\)\(D_{1}\)\(\mid\) = 2, \(\mid\)\(D_{2}\)\(\mid\) = 3, \(\mid\)\(C_{1}\)\(\mid\)\(=\) 1, \(\mid\)\(C_{2}\)\(\mid\)\(=\) 1 in the left subset, and \(\mid\)\(C_{1}\)\(\mid\)\(=\) 2, \(\mid\)\(C_{3}\)\(\mid\) = 1 in the right subset, then the Gini coefficient is 0.53. Repeat the above process until the Gini coefficients of all candidate points are calculated. Obviously, the new Gini coefficient calculation method only traverses the original data set once in the initialization process. In contrast, the traditional method requires to traverse data set \(n-1\) times.