Random Decision Hashing for Massive Data Learning

Xiatian Zhang, Wei Fan, Nan DuBigMine 2015 · OpenReview

Abstract

In the era of Big Data, the iterative nature of most traditional learning algorithms renders them increasingly inefficient to address large learning problems. Random decision trees algorithm is an efficient and decent learning algorithm, but the complexity of tree structure makes the algorithm inefficient for the big data problems. Inspired by the theoretical analyses of random decision trees, we propose a randomized algorithm for big data classification tasks based on unsupervised locality sensitive hashing. Our algorithm is essentially non-iterative, very flexible to deploy over clusters of machines, and thus able to handle large datasets efficiently. Experiments on real datasets demonstrate that the proposed algorithm can easily scale up to millions of data samples and features while still achieves at most 17% and 800% improvement in accuracy and efficiency respectively with moderate memory consumption over existing algorithms.

Introduction

Traditional machine learning mainstays—such as Logistic Regression (LR), Support Vector Machines (SVM), and standard Decision Trees—face a fundamental "Achilles heel" in the era of Big Data: iteration. These algorithms typically require multiple passes over the data to converge, leading to super-linear time complexity. When datasets grow to millions of samples and features, keeping data in memory for these iterations becomes impossible, and disk-based iterations are painfully slow.

While Random Decision Trees (RDT) offered a faster, randomized alternative, they brought their own baggage. Maintaining complex tree structures in a distributed environment (like Spark or Hadoop) is memory-intensive and difficult to scale. This paper introduces Random Decision Hashing (RDH), a non-iterative, randomized algorithm designed for massive-scale classification. By replacing the complex tree structures of RDTs with efficient Locality Sensitive Hashing (LSH), RDH achieves significant speedups and accuracy gains while maintaining a tiny memory footprint.

Methodology

The core innovation of RDH is the realization that the effectiveness of RDTs stems from their ability to randomly partition (or "shatter") the data space, rather than the tree structure itself. RDH leverages this by using unsupervised Locality Sensitive Hashing (LSH) to map data points into buckets, where similar points end up in the same bucket with high probability.

The RDH Framework

  1. Shattering via LSH: Instead of building trees, RDH uses LSH functions to partition the feature space.
  2. Training: The algorithm performs a single pass over the training data. For each instance, it computes a hash and increments the class frequency counts within the corresponding hash bucket.
  3. Inference: To classify a new point, it is hashed, and the class frequencies of its bucket are retrieved. These frequencies are averaged across multiple hash functions to produce a final probability estimate.
  4. Efficiency Heuristics: To minimize the cost of computing multiple hashes, RDH generates one long hash code and applies multiple random bit masks to create different "partitions" of the data.

Variants for Different Data Types

  • Dense Data: RDH uses a modified Hyperplane Hashing where coefficients are restricted to $\{-1, 0, 1\}$, eliminating expensive multiplication operations.
  • Sparse Data: The algorithm employs SimHash combined with a custom FastHash function to handle high-dimensional integer features efficiently.

Experimental Setup

The authors evaluated RDH against RDT on eight small benchmarks and against LR, SVM, and DT on six massive datasets from the LIBSVM repository, including epsilon (dense), kdda (sparse), kddb (sparse), url (sparse), webspam_tri (sparse), and webspam_uni (dense). These datasets contain up to 20 million samples and nearly 30 million features, with volumes reaching 20GB.

Analysis and Discussion

Theoretical bias-variance analysis confirms that the learning capability of random trees comes from the partitioning mechanism. This justifies replacing trees with hashes, transforming the model into a non-parametric estimation method. Instead of fitting a global model (like a hyperplane), RDH estimates local class distributions.

Because the model only stores bucket counts rather than complex tree nodes or massive weight vectors, it can run on nodes with as little as 1-2GB of memory, even when dealing with 30 million features. Furthermore, since the algorithm is non-iterative and buckets are independent, it is "embarrassingly parallel" and perfectly suited for MapReduce and Spark architectures.

Results

  • Accuracy: RDH outperformed LR, SVM, and DT on 5 out of 6 large datasets. Notably, on the url dataset, it improved AUC by 17% over the next best competitor.
  • Speed: RDH is significantly faster. On the webspam_tri dataset, RDH converged in 153 seconds, while Logistic Regression took 1418 seconds—a roughly 9x (800%) speedup.
  • Resource Usage: While traditional algorithms often failed due to "out of memory" errors on high-dimensional data, RDH remained stable with a constant, low memory overhead.
  • Scalability: Training time scales linearly with the number of bit masks used, allowing for a flexible trade-off between speed and accuracy.

Conclusion

RDH provides a robust solution for massive-scale classification by moving away from iterative optimization and complex tree structures. While it requires tuning parameters like the number of masks and hash code length, its implementation is uniquely robust compared to other non-iterative methods like Naive Bayes. Future work will explore extending the RDH framework to regression and multi-label classification tasks.

Summary updated

Abstract

In the era of Big Data, the iterative nature of most traditional learning algorithms renders them increasingly inefficient to address large learning problems. Random decision trees algorithm is an efficient and decent learning algorithm, but the complexity of tree structure makes the algorithm inefficient for the big data problems. Inspired by the theoretical analyses of random decision trees, we propose a randomized algorithm for big data classification tasks based on unsupervised locality sensitive hashing. Our algorithm is essentially non-iterative, very flexible to deploy over clusters of machines, and thus able to handle large datasets efficiently. Experiments on real datasets demonstrate that the proposed algorithm can easily scale up to millions of data samples and features while still achieves at most 17% and 800% improvement in accuracy and efficiency respectively with moderate memory consumption over existing algorithms.
BibTeX
@inproceedings{zhang2015random,
  author = {Xiatian Zhang and Wei Fan and Nan Du},
  title = {{Random Decision Hashing for Massive Data Learning}},
  booktitle = {BigMine},
  year = {2015},
  url = {https://openreview.net/forum?id=BkW16VbdbB},
}
Figure