The Quantum Version Of Classification Decision Tree Constructing Algorithm C5.0
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2019
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913290812129280 |
|---|---|
| author | Khadiev, Kamil Mannapov, Ilnaz Safina, Liliya |
| author_facet | Khadiev, Kamil Mannapov, Ilnaz Safina, Liliya |
| contents | 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{ü}rr-Hø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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1907_06840 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | The Quantum Version Of Classification Decision Tree Constructing Algorithm C5.0 Khadiev, Kamil Mannapov, Ilnaz Safina, Liliya Machine Learning Quantum Physics 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{ü}rr-Hø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. |
| title | The Quantum Version Of Classification Decision Tree Constructing Algorithm C5.0 |
| topic | Machine Learning Quantum Physics |
| url | https://arxiv.org/abs/1907.06840 |