  Decision tree (and its extensions such as Gradient Boosting Decision Trees
and Random Forest) is a widely used machine learning algorithm, due to its
practical effectiveness and model interpretability. With the emergence of big
data, there is an increasing need to parallelize the training process of
decision tree. However, most existing attempts along this line suffer from high
communication costs. In this paper, we propose a new algorithm, called
\emph{Parallel Voting Decision Tree (PV-Tree)}, to tackle this challenge. After
partitioning the training data onto a number of (e.g., $M$) machines, this
algorithm performs both local voting and global voting in each iteration. For
local voting, the top-$k$ attributes are selected from each machine according
to its local data. Then, globally top-$2k$ attributes are determined by a
majority voting among these local candidates. Finally, the full-grained
histograms of the globally top-$2k$ attributes are collected from local
machines in order to identify the best (most informative) attribute and its
split point. PV-Tree can achieve a very low communication cost (independent of
the total number of attributes) and thus can scale out very well. Furthermore,
theoretical analysis shows that this algorithm can learn a near optimal
decision tree, since it can find the best attribute with a large probability.
Our experiments on real-world datasets show that PV-Tree significantly
outperforms the existing parallel decision tree algorithms in the trade-off
between accuracy and efficiency.
