The Quantum Version Of Classification Decision Tree Constructing Algorithm C5.0
In the paper, we focus on complexity of C5.0 algorithm for constructing decision tree classifier that is the models for the classification problem from machine learning. In classical case the decision tree is constructed in $O(hd(NM+N \log N))$ running time, where $M$ is a number of classes, $N$ is the size of a training data set, $d$ is a number of attributes of each element, $h$ is a tree height. Firstly, we improved the classical version, the running time of the new version is $O(h\cdot d\cdot N\log N)$. Secondly, we suggest a quantum version of this algorithm, which uses quantum subroutines like the amplitude amplification and the D{\"u}rr-H{\o}yer minimum search algorithms that are based on Grover's algorithm. The running time of the quantum algorithm is $O\big(h\cdot \sqrt{d}\log d \cdot N \log N\big)$ that is better than complexity of the classical algorithm.
Code (0)
등록된 구현이 없습니다.
Tasks
ClassificationGeneral ClassificationSimilar Papers 제목 키워드 기반
Efficient Quantum Agnostic Improper Learning of Decision Trees
The agnostic setting is the hardest generalization of the PAC model since it is akin to learning with adversarial noise. In this paper, we give a poly$(n,t,{\frac{1}{\varepsilon}})$ quantum algorithm for learning size $t…
Ensemble LearningThe Improvement of Decision Tree Construction Algorithm Based On Quantum Heuristic Algorithms
This work is related to the implementation of a decision tree construction algorithm on a quantum simulator. Here we consider an algorithm based on a binary criterion. Also, we study the improvement capability with quant…
Des-q: a quantum algorithm to provably speedup retraining of decision trees
Decision trees are widely adopted machine learning models due to their simplicity and explainability. However, as training data size grows, standard methods become increasingly slow, scaling polynomially with the number …
Binary ClassificationRepresentation of binary classification trees with binary features by quantum circuits
We propose a quantum representation of binary classification trees with binary features based on a probabilistic approach. By using the quantum computer as a processor for probability distributions, a probabilistic trave…
Binary ClassificationRecent advances for quantum classifiers
Machine learning has achieved dramatic success in a broad spectrum of applications. Its interplay with quantum physics may lead to unprecedented perspectives for both fundamental research and commercial applications, giv…
BIG-bench Machine LearningQuantum Machine Learning