PaperlayerView exact revision on arXiv

Source-linked AI summary

A Parallel Random Forest Algorithm for Big Data in a Spark Cloud Computing Environment

Jianguo Chen, Kenli Li, Zhuo Tang, Kashif Bilal, Shui Yu, Chuliang Weng, Keqin Li

arXiv:1810.07748v1cs.DC

TL;DR

Large-scale, high-dimensional, and noisy data create a need for efficient and accurate mining methods. The paper proposes PRF on Spark, combining accuracy optimization with data- and task-parallel Random Forest execution. Experiments report advantages over other algorithms in classification accuracy, performance, and scalability.

  • Problem

    Large-scale data mining requires efficient and accurate processing, while high dimensionality, complexity, and noise challenge classification performance.

  • Method

    PRF combines dimension reduction and weighted voting with vertical partitioning, data multiplexing, and task-parallel training on Spark’s RDD and DAG models.

  • Results

    PRF shows advantages over other algorithms in classification accuracy, performance, and scalability.

  • Takeaways & Limitations

    The proposed approach reduces training-data volume and data transmission cost while improving PRF performance without decreasing algorithm accuracy.

  • Takeaways & Limitations

    The method assumes training datasets with N records and M feature variables, and Spark execution can involve disk storage when data are not applicable in memory.

Abstract

from arXiv · show

With the emergence of the big data age, the issue of how to obtain valuable knowledge from a dataset efficiently and accurately has attracted increasingly attention from both academia and industry. This paper presents a Parallel Random Forest (PRF) algorithm for big data on the Apache Spark platform. The PRF algorithm is optimized based on a hybrid approach combining data-parallel and task-parallel optimization. From the perspective of data-parallel optimization, a vertical data-partitioning method is performed to reduce the data communication cost effectively, and a data-multiplexing method is performed is performed to allow the training dataset to be reused and diminish the volume of data. From the perspective of task-parallel optimization, a dual parallel approach is carried out in the training process of RF, and a task Directed Acyclic Graph (DAG) is created according to the parallel training process of PRF and the dependence of the Resilient Distributed Datasets (RDD) objects. Then, different task schedulers are invoked for the tasks in the DAG. Moreover, to improve the algorithm's accuracy for large, high-dimensional, and noisy data, we perform a dimension-reduction approach in the training process and a weighted voting approach in the prediction process prior to parallelization. Extensive experimental results indicate the superiority and notable advantages of the PRF algorithm over the relevant algorithms implemented by Spark MLlib and other studies in terms of the classification accuracy, performance, and scalability.

1 INTRODUCTION

The paper addresses efficient and accurate mining of large, high-dimensional, and noisy datasets by proposing a Parallel Random Forest algorithm on Spark. PRF combines accuracy-oriented optimization with data- and task-parallel methods.

  • 1.1 Motivation: Big data mining must obtain valuable information efficiently and accurately despite high dimensionality, complexity, and noise.
  • 1.1 Motivation: Spark supports memory-based RDD and DAG computation, reducing disk I/O compared with Hadoop’s iterative HDFS-based processing.
  • 1.1 Motivation: Random Forest is suitable for big-data mining because its decision trees can be trained concurrently.
  • 1.2 Our Contributions: PRF is implemented on Apache Spark and combines data-parallel and task-parallel optimization for Random Forest.
  • 1.2 Our Contributions: PRF improves accuracy through dimension reduction during training and weighted voting during prediction.
  • 1.2 Our Contributions: PRF constructs a training task DAG from the RDD model and invokes different schedulers for DAG tasks.

2 RELATED WORK

Prior work addressed high-dimensional, noisy, large-scale data through improved classifiers, random forests, distributed tree learning, and resource-aware scheduling. However, Spark-MLRF has accuracy and parallel-execution drawbacks, motivating a hybrid RF optimization based on Spark RDD and DAG models.

  • Traditional data-processing and data-mining techniques struggle with large-scale, complex, high-dimensional datasets.Their accuracy and performance significantly decline as dataset complexity, dimensionality, and size increase.
  • Researchers have developed dimension-reduction, classification, boosting, bagging, and random-forest methods for high-dimensional, noisy, or imbalanced data.RF has been applied to tasks including multi-class action detection and facial feature detection.
  • Distributed-learning studies have combined tree-model training with MapReduce or other parallel-computing strategies to address speed, memory, and large-scale classification requirements.Examples include distributed RF ensembles and boosted decision-tree ranking.
  • Other parallel-processing research has focused on dynamic resource allocation, energy-aware scheduling, and robust allocation under heterogeneous or uncertain workloads.
  • Spark-MLRF uses data-parallel RF training, but sampling continuous-feature partitions reduces accuracy and the approach has additional drawbacks.The passage identifies reduced accuracy as the cost of sampling to reduce data transmission operations.
  • The paper proposes a hybrid data-parallel and task-parallel RF approach based on Spark RDD and DAG models to reduce training-data volume and mitigate communication and workload-imbalance problems.The claimed optimization combines data reuse and partitioning with parallel task execution.

3 RANDOM FOREST ALGORITHM OPTIMIZATION

The paper optimizes Random Forest accuracy for high-dimensional data through dimension reduction and weighted voting, then analyzes the resulting computational complexity. It also describes the standard RF construction from bootstrap samples and concurrently trained decision trees.

  • 3.1 Random Forest Algorithm: Random Forest constructs k bootstrap training subsets, trains one decision tree per subset, and combines the k trees into an ensemble.Out-of-Bag datasets are retained to evaluate individual tree accuracy after training.
  • 3.1 Random Forest Algorithm: Each decision tree randomly selects m feature variables from M variables during node splitting and chooses the feature with the best gain ratio.The splitting process repeats until a leaf node is generated.
  • 3.2 Dimension Reduction for High-Dimensional Data: Dimension reduction ranks features by gain-ratio-based importance, retains the top k variables, randomly selects m − k additional variables, and reduces dimensionality from M to m.The selected variables are used during training while preserving feature-selection diversity.
  • 3.2 Dimension Reduction for High-Dimensional Data: The proposed dimension-reduction method maintains the original computational complexity while balancing feature-selection accuracy and ensemble diversity and preventing classification overfitting.The method selects the m feature variables considered optimal according to variable importance.
  • 3.3 Weighted Voting Method: Weighted voting assigns each decision tree a voting weight based on its classification or regression accuracy to address errors from noisy trees.The method is intended to improve testing-data accuracy and reduce generalization error.
  • 3.4 Computational Complexity: The original RF has complexity O(kMN log N), whereas PRF-DR has total complexity O(k(MN + mN log N)) after reducing features from M to m.Here, m ≪ M, and the dimension-reduction stage contributes O(MN).

4 PARALLELIZATION OF THE RANDOM FOREST ALGORITHM ON SPARK

PRF combines data-parallel and task-parallel optimization on Spark to reduce data movement, improve workload balance, and maximize parallel training performance.

  • 4 PARALLELIZATION OF THE RANDOM FOREST ALGORITHM ON SPARK: PRF combines vertical data partitioning and data multiplexing with dual-parallel training on Spark.The design reduces data volume and transmission operations while maximizing training parallelization.
  • 4 PARALLELIZATION OF THE RANDOM FOREST ALGORITHM ON SPARK: A task DAG based on RDD dependencies coordinates PRF training tasks, after which different schedulers execute the DAG tasks.The schedulers further reduce communication costs and improve workload balance across the Spark cluster.
  • 4 PARALLELIZATION OF THE RANDOM FOREST ALGORITHM ON SPARK: Vertical partitioning and data multiplexing reduce data volume and transmission operations without reducing algorithm accuracy.These are the data-parallel components of the hybrid optimization.

4.1 Data-Parallel Optimization

PRF combines vertical data partitioning, data multiplexing, and static allocation to reduce data volume and communication while reusing feature subsets across tree-training tasks.

  • Data-Multiplexing Method: The data-parallel optimization reduces data volume and transmission operations without reducing algorithm accuracy.Increasing PRF scale does not change data size or storage location under this optimization.
  • Vertical Data Partitioning: Vertical partitioning splits the training dataset into independent feature subsets, each containing one input feature and the target variable.The subsets are loaded as independent RDD objects before dimension reduction.
  • Data-Multiplexing Method: Data multiplexing records sampled-data indexes in a DSI table instead of copying sampled records for every tree.Training tasks retrieve records from shared feature subsets using the corresponding indexes.
  • Data-Multiplexing Method: Gain-ratio tasks are dispatched to slaves holding the required feature subsets, while their intermediate results support subsequent tree-node splitting.Tasks for different trees can reuse the same feature subset on a slave.
  • Static Data Allocation: Static allocation places feature subsets across Spark slaves according to subset volume and available storage capacity.Large subsets may span multiple nearby slaves, exact-capacity subsets occupy one node, and smaller subsets can share a node.

4.2 Task-Parallel Optimization

PRF exploits parallelism across decision trees and feature variables, organizing dependent training operations in a task DAG and assigning task types to different schedulers.

  • Parallel Training Process: PRF trains k decision trees in parallel, while the M −1 feature variables within each tree are calculated concurrently for node splitting.This dual-parallel design follows from the independence of trees and tree sub-node splits.
  • Task Types: Gain-ratio-computing tasks calculate feature statistics and submit their results to node-splitting tasks.The calculations include entropy, self-split information, information gain, and gain ratio.
  • Task Types: Node-splitting tasks collect relevant gain-ratio results, select the highest-gain split, and distribute results for the next training stage.These tasks operate on tree nodes after receiving the corresponding TGR outputs.
  • Task DAG: The training process is divided into stages whose dependencies form a task DAG based on job stages and RDD-object dependencies.DAG stages correspond to levels of the decision tree model.
  • Task Scheduling: LocalScheduler handles node-local TGR tasks, whereas ClusterScheduler allocates TNS tasks across suitable Spark workers.TGR tasks remain near their feature subsets, while TNS tasks depend on collected TGR results.

4.3 Parallel Optimization Method Analysis

The hybrid optimization improves PRF’s communication, storage, workload balance, and scalability by combining partitioned data reuse with parallel task execution.

  • Overall Analysis: PRF’s hybrid parallel optimization is reported to improve performance, workload balance, and scalability relative to Spark-MLRF and other parallel RF methods.The analysis evaluates these three dimensions together.
  • Data Volume and Communication: The PRF sampled-training volume is approximately 2NM, compared with NMk for original RF and Spark-MLRF.PRF stores indexes and feature-subset data rather than copying the sampled dataset for each tree.
  • Data Volume and Communication: Vertical partitioning and static allocation mitigate distributed data communication and address a performance bottleneck of traditional parallel methods.Communication is reduced by locating tasks with required feature subsets when possible.
  • Resource and Workload Balance: Feature-subset allocation by volume distributes large subsets across multiple slaves and schedules corresponding TGR tasks on those nodes.This design targets storage and workload balance across the Spark cluster.
  • Resource and Workload Balance: Shared feature subsets remain useful across different trees, reducing resource waste and supporting overall workload balance after some tree splits become inactive.A subset unusable for one tree may still serve other trees.
  • Stability and Scalability: When PRF scale increases, feature-subset data size and storage locations remain unchanged, while computing tasks and intermediate-result communication increase.This behavior is presented as a scalability advantage of data multiplexing.

5.1 Experiment Setup

Experiments use a 101-node Spark cloud platform and two groups of large, high-dimensional datasets from UCI and a medical project.

  • Computing Environment: The experimental Spark platform contains one master node and 100 slave nodes.The nodes run Ubuntu 12.04.4 with Pentium Dual-Core 3.20GHz CPUs and 8GB memory.
  • Computing Environment: All cluster nodes are connected by a Gigabit network and configured with Hadoop 2.5.0 and Spark 1.1.0.The implementation uses Scala 2.10.4.
  • Datasets: The evaluation uses two dataset groups with large scale and high dimensionality: UCI repository datasets and data from an actual medical project.Tables 3 and 4 describe the respective dataset groups.
  • Dataset Measures: Datasize(Maximum) denotes the peak sampled-data size across all comparison algorithms, while Datasize(Original) denotes the original dataset size.These definitions apply to the datasets reported in Tables 3 and 4.
  • Execution Assumption: Spark can process datasets larger than total cluster memory because training data are not loaded into memory as a whole.RDD data may be buffered or discarded after iteration when caching is not required.

5.2 Classification Accuracy

PRF achieves higher classification accuracy than RF, DRF, and Spark-MLRF across different decision-tree scales and dataset sizes. Its OOB error rate also declines as the number of trees increases.

  • Classification Accuracy for Different Tree Scales: PRF's average classification accuracy exceeds RF by 8.9%, DRF by 6.1%, and Spark-MLRF by 4.6%.The best-case improvements are 10.6% over RF, 7.3% over DRF, and 5.8% over Spark-MLRF.
  • Classification Accuracy for Different Data Sizes: Across every tested data scale, PRF has higher classification accuracy than RF, DRF, and Spark-MLRF.The reported comparisons show PRF outperforming the three alternatives for each dataset scale.
  • Classification Accuracy for Different Data Sizes: PRF exceeds Spark-MLRF by 8.1% on average and by 11.3% in the best case at 3,000,000 samples.The paper attributes Spark-MLRF's declining accuracy with larger datasets to its partition-level sampling method.
  • OOB Error Rates: The average OOB error rate decreases from 0.138 with 500 trees to 0.089 with 1,000 trees.The error rate declines gradually and tends toward convergence as the number of decision trees increases.

5.3 Performance Evaluation

PRF improves large-scale execution performance through Spark parallelization, data reuse, and reduced communication costs. Its speedup increases with cluster size, while execution gains and speedup become less pronounced under some larger cluster configurations.

  • Execution Time: When datasets exceed 1.0GB, PRF and Spark-MLRF have lower average execution times than RF across four cases.For datasets smaller than 1.0GB, PRF and Spark-MLRF are slower because of fixed Spark submission and configuration time.
  • Execution Time for Different Cluster Scales: Increasing Spark slave nodes from 10 to 50 reduces PRF's average execution time from 405.4 to 182.6 seconds in Gas and from 174.8 to 78.3 seconds in Medicine.The experiments increase the number of slave nodes from 10 to 100.
  • Speedup: At 100 slave nodes, PRF's speedup factor ranges from 60.0 to 87.3, below the theoretical value of 100.The paper identifies data communication and fixed application submission and configuration time as contributors to the gap.
  • Speedup: PRF speedup grows rapidly below 50 slave nodes but grows slowly above 50 as data allocation, task scheduling, and communication operations increase.At 50 nodes, the reported speedup factors are 65.5 for Gas and 61.5 for Patient.
  • Training Data Volume: With data multiplexing, PRF's total training feature-subset volume is 2 times the original training-dataset size despite increasing RF scale beyond two trees.RF and Spark-MLRF training volumes increase linearly with model scale under the same horizontal sampling method.
  • Data Communication Cost: PRF's data communication cost is lower than Spark-MLRF's in all cases, with the difference increasing as the number of slave nodes grows.Spark-MLRF's communication cost rises from 350.0MB to 2180.0MB as slave nodes increase from 5 to 50.

6 CONCLUSIONS

The paper proposes PRF for big data on Apache Spark, combining accuracy optimization with data-parallel and task-parallel optimization. Experiments report advantages in classification accuracy, performance, and scalability, while future work targets streaming, data allocation, and task scheduling.

  • Conclusions: PRF combines dimension reduction and weighted voting with data-parallel and task-parallel optimization on Apache Spark.The data-parallel approach reuses training data and reduces data volume, while task parallelism reduces transmission cost and improves performance.
  • Conclusions: Experimental results indicate PRF's advantages over other algorithms in classification accuracy, performance, and scalability.The conclusion presents these as the main reported strengths of the proposed algorithm.
  • Conclusions: Future work will address incremental parallel random forests for cloud data streams and improve distributed data allocation and task scheduling.These directions are stated as planned extensions of the current work.
Loading 1810.07748v1…