Decision trees are widely used in machine learning due to their simplicity in
construction and interpretability. However, as data sizes grow, traditional
methods for construction and retraining decision trees become increasingly
slow, scaling polynomially with the number of training examples. In this work,
we introduce a novel quantum algorithm, named $Des$-$q$, for constructing and
retraining decision trees in regression and binary classification tasks.
Assuming the data stream produces small increments of new training examples, we
demonstrate that our $Des$-$q$ algorithm significantly reduces the time
required for tree retraining, achieving a poly-logarithmic time complexity in
the number of training examples, even accounting for the time needed to load
the new examples into quantum-accessible memory. Our approach involves building
a decision tree algorithm to perform k-piecewise linear tree splits at each
internal node. These splits simultaneously generate multiple hyperplanes,
dividing the feature space into k distinct regions. To determine the k suitable
anchor points for these splits, we develop an efficient quantum-supervised
clustering method, building upon the q-means algorithm of Kerenidis $et$ $al$.
$Des$-$q$ first efficiently estimates each feature weight using a novel quantum
technique to estimate the Pearson correlation. Subsequently, we employ weighted
distance estimation to cluster the training examples in k disjoint regions and
then proceed to expand the tree using the same procedure. We benchmark the
performance of the simulated version of our algorithm against the
state-of-the-art classical decision tree for regression and binary
classification on multiple data sets with numerical features. Further, we
showcase that the proposed algorithm exhibits similar performance to the
state-of-the-art decision tree while significantly speeding up the periodic
tree retraining.

介绍一种名为 $Des$-$q$ 的新型量子算法，用于构建和重新训练用于回归和二分类任务的决策树，并通过开发高效的量子监督聚类方法实现聚类分割。该算法在训练样本数量的对数时间复杂度范围内显著减少了重新训练决策树所需的时间，同时展示了与现有决策树相似的性能并加快了定期树的重新训练。