The DOI matches its Crossref record; 26 of the 26 references it cites were found in a registry or an index.
Subtree Replacement in Decision Tree Simplification
Open accessAbstract
The current availability of efficient algorithms for decision tree induction makes intricate post-processing techniques worth to be investigated both for efficiency and effectiveness. We study the simplification operator of subtree replacement, also known as grafting, originally implemented in the C4.5 system. We present a parametric bottom-up algorithm integrating grafting with the standard pruning operator, and analyze its complexity in terms of the number of nodes visited. Immediate instances of the parametric algorithm include extensions of error based, reduced error, minimum error, and pessimistic error pruning. Experimental results show that the computational cost of grafting is paid off by statistically significant smaller trees without accuracy loss.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
UCI Machine Learning Repository
Asuncion, A. (2007) · Medical Entomology and Zoology · Cited by 24,190
(1992) · Cited by 23,431
Statistical Comparisons of Classifiers over Multiple Data Sets
Demšar, J. (2006) · doi:10.5555/1248547.1248548 · Cited by 12,041
Classification And Regression Trees
Breiman, L., Friedman, J. H., Olshen, R. A., & Stone, C. J. (2017) · doi:10.1201/9781315139470 · Cited by 11,417
A Study of Cross-Validation and Bootstrap for Accuracy Estimation and Model Selection
Kohavi, R. (1995) · Zenodo · doi:10.5281/zenodo.19712698 · Cited by 10,909
Estimating classification error rate: Repeated cross-validation, repeated hold-out and bootstrap
Kim, J. (2009) · Computational Statistics & Data Analysis · doi:10.1016/j.csda.2009.04.009 · Cited by 792
A comparative analysis of methods for pruning decision trees
Esposito, F., Malerba, D., Semeraro, G. M., & Kay, J. (1997) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.589207 · Cited by 551
Simplifying decision trees: A survey
Breslow, L. A., & Aha, D. W. (1997) · The Knowledge Engineering Review · doi:10.1017/s0269888997000015 · Cited by 344
Handling Missing Values when Applying Classification Models
Saar‐Tsechansky, M., & Provost, F. J. (2007) · Faculty Digital Archive (New York University Florence) · doi:10.5555/1314498.1314553 · Cited by 315
Quinlan, J. R. (1999) · International Journal of Human-Computer Studies · doi:10.1006/ijhc.1987.0321 · Cited by 272
Pruning decision trees with misclassification costs
Bradford, J. P., Kunz, C., Kohavi, R., Brunk, C., & Brodley, C. E. (1998) · Lecture notes in computer science · doi:10.1007/bfb0026682 · Cited by 197
MDL-based decision tree pruning
Mehta, M., Rissanen, J., & Agrawal, R. (1995) · Cited by 187
Trading Accuracy for Simplicity in Decision Trees
Bohanec, M., & Bratko, I. (1994) · Machine Learning · doi:10.1023/a:1022685808937 · Cited by 170
Decision tree grafting from the all-tests-but-one partition
Webb, G. I. (1999) · Cited by 104
Parallel Formulations of Decision-Tree Classification Algorithms
Srivastava, A., Han, E.-H. S., Kumar, V., & Singh, V. (2006) · Kluwer Academic Publishers eBooks · doi:10.1007/0-306-47011-x_2 · Cited by 60
Wang, T., Qin, Z., Jin, Z. H., & Zhang, S. (2010) · Journal of Systems and Software · doi:10.1016/j.jss.2010.01.002 · Cited by 58
Post-pruning in decision tree induction using multiple performance measures
Osei-Bryson, K.-M. (2006) · Computers & Operations Research · doi:10.1016/j.cor.2005.12.009 · Cited by 54
Parallel formulations of decision-tree classification algorithms
Srivastava, A., Han, E.-H. S., Singh, V., & Kumar, V. (2002) · Proceedings of the International Conference on Parallel Processing · doi:10.1109/icpp.1998.708491 · Cited by 32
YaDT: yet another decision tree builder
Ruggieri, S. (2005) · IEEE International Conference on Tools with Artificial Intelligence (ICTAI) · doi:10.1109/ictai.2004.123 · Cited by 31
Self-citationPorting Decision Tree Algorithms to Multicore Using FastFlow
Aldinucci, M., Ruggieri, S., & Torquati, M. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-15880-3_7 · Cited by 31
Self-citationPorting Decision Tree Algorithms to Multicore Using FastFlow
Aldinucci, M., Ruggieri, S., & Torquati, M. (2010) · UnipiEprints Open Archive (Università di Pisa) · Cited by 26
Self-citationA Decision Tree Plug-In for DataEngine
Borgelt, C. (2004) · Cited by 20
A k-norm pruning algorithm for decision tree classifiers based on error rate estimation
Zhong, M., Georgiopoulos, M., & Anagnostopoulos, G. C. (2008) · Machine Learning · doi:10.1007/s10994-007-5044-4 · Cited by 18
Maximal path length of binary trees
Cameron, H., & Wood, D. (1994) · Discrete Applied Mathematics · doi:10.1016/0166-218x(94)90034-5 · Cited by 9
Simplification Methods for Model Trees with Regression and Splitting Nodes
Ceci, M., Appice, A., & Malerba, D. (2007) · Springer eBooks · doi:10.1007/3-540-45065-3_3 · Cited by 2
Dynamic graphics and model validation: an application to best-practice production functions
Destefanis, S., & Porzio, G. C. (1999) · Applied Stochastic Models in Business and Industry · doi:10.1002/(sici)1526-4025(199910/12)15:4 · Cited by 1
Flagged first, then by citations
Research works printed but not linked: 7
- 1 Hypo Thyroid 0.44 ± 0.37 0.43 ± 0.35 0.43 ± 0.35 30.2 ± 4.0 29.4 ± 3.4 29.4 ± 3.4 2.55 ± 0.04 2.53 ± 0.04 2.53 ± 0.04 2 Blocks 3.13 ± 0.61 3.12 ± 0.63 3.11 ± 0.63 89.7 ± 9.1 85.0 ± 8.3 84.4 ± 8.5 7.04 ± 0.22 7.01 ± 0.22 7.06 ± 0.26 3 Musk Clean2 3.16 ± 0.76 3.14 ± 0.77 3.14 ± 0.77 226 ± 9.6 221 ± 10 219 ± 9.8 11.67 ± 0.41 11.59 ± 0.43 11.58 ± 0.44 4 Mushroom 0.00 ± 0.00 0.00 ± 0.00 0.00 ± 0.00 29.1 ± 0.4 29.1 ± 0.4 29.1 ± 0.2 2.53 ± 0.03 2.53 ± 0.03 2.53 ± 0.02 5 Letter 12.06 ± 0.78 12.03 ± 0.79 12.03 ± 0.79 2394 ± 43 2340 ± 37 2338 ± 36 12.99 ± 0.50 12.86 ± 0.44 12.87 ± 0.44 6 Chess 31.84 ± 0.89 31.28 ± 0.87 31.16 ± 0.85 8644 ± 79 8278 ± 79 8165 ± 75 8.88 ± 0.03 8.86 ± 0.03 8.86 ± 0.03 7 Adult 13.90 ± 0.42 13.92 ± 0.43 13.86 ± 0.43 1013 ± 130 718 ± 108 679 ± 103 6.80 ± 0.16 6.69 ± 0.21 6.79 ± 0.23 8 Statlog Shuttle 0.02 ± 0.02 0.03 ± 0.02 0.03 ± 0.02 55.0 ± 3.4 47.4 ± 3.3 47.2 ± 2.9 6.89 ± 0.45 5.79 ± 0.29 5.86 ± 0.29 9 Connect-4 19.16 ± 0.45 18.98 ± 0.42 18.96 ± 0.44 6442 ± 142 6038 ± 118 5989 ± 116 10.12 ± 0.09 9.98 ± 0.09 9.98 ± 0.09 10 SyD100KP5G0.2 3.72 ± 0.18 3.68 ± 0.18 3.62 ± 0.18 274 ± 17 286 ± 16 296 ± 13 6.26 ± 0.21 6.33 ± 0.20 6.38 ± 0.20 11 Census-Income 4.69 ± 0.09 4.59 ± 0.09 4.59 ± 0.09 2805 ± 581 2559 ± 292 2451 ± 261 5.52 ± 0.09 5.56 ± 0.13 5.59 ± 0.13 12 Forest Cover 5.43 ± 0.10 5.41 ± 0.11 5.41 ± 0.11 29563 ± 240 28530 ± 240 28422 ± 232 30.12 ± 0.14 29.88 ± 0.14 29.89 ± 0.15 13 SyD1MP7G0.1 1.40 ± 0.05 1.38 ± 0.05 1.37 ± 0.05 2820 ± 143 2821 ± 128 2785 ± 126 6.86 ± 0.06 6.87 ± 0.06 6.90 ± 0.06 14 KDD Cup 99 0.01 ± 0.00 0.01 ± 0.00 0.01 ± 0.00 1234 ± 110 1123 ± 123 1068 ± 119 7.15 ± 0.29 6.91 ± 0.23 13.61
- M. Aldinucci, S. Ruggieri, and M. Torquati. Port- ing decision tree algorithms to multicore using Fast- Flow. In Proc. of European Conf. on Machine Learning and Knowledge Discovery in Databases (ECML/PKDD 2010), volume 6321 of LNCS, pages 7-23. Springer, 2010.
- Morgan Kaufmann, 1995.
- Morgan Kaufmann, San Mateo, CA, 1993.
- IEEE, 2004. YaDT version 1.2.5 downloaded from http://www.di.unipi.it/∼ruggieri.
- Morgan Kaufmann, 1999.
- I.H. Witten and E. Frank. Data Mining: Practical Machine Learning Tools and Techniques with Java Implementations. Morgan Kaufmann, 2nd edition, 2005.
Cited by
Sorted by citations
A Survey of Methods for Explaining Black Box Models
Guidotti, R., Monreale, A., Ruggieri, S., Turini, F., Giannotti, F., & Pedreschi, D. (2019) · ACM Computing Surveys · doi:10.1145/3236009 · Cited by 629
“The most well-known simplification method is decision tree pruning, which relies on an error estimation function to compare the errors of the two alternatives: to prune a subtree or not [101].”
MethodSelf-citationTowards low-complexity wireless technology classification across multiple environments
Fontaine, J., Fonseca, E., Shahid, A., Kist, M., DaSilva, L. A., Moerman, I., & Poorter, E. D. (2019) · Ad Hoc Networks · doi:10.1016/j.adhoc.2019.101881 · Cited by 43
Explaining short text classification with diverse synthetic exemplars and counter-exemplars
Lampridis, O., State, L., Guidotti, R., & Ruggieri, S. (2022) · Machine Learning · doi:10.1007/s10994-022-06150-7 · Cited by 13
Self-citationDecision tree building on multi‐core using FastFlow
Aldinucci, M., Ruggieri, S., & Torquati, M. (2013) · Concurrency and Computation Practice and Experience · doi:10.1002/cpe.3063 · Cited by 5
Self-citation
Metadata
- Authors
- Ruggieri, S.
- Affiliations
- University of Pisa (IT)
- Corresponding author
- Ruggieri, Salvatore
- ORCID
- Ruggieri, Salvatore
- Venue
- Proceedings of the 2012 SIAM International Conference on Data Mining
- Published
- 2012-04-26
- Pages
- 379-390
- OpenAlex
- W2396009330
- Cited by
- 5
- References
- 26
- Citations by year
- 2022: 1 · 2019: 2 · 2018: 1 · 2013: 1
- FWCI
- 0.25
- Type
- conference paper
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- SIAM International Conference on Data Mining (publishedVersion)
- CINECA IRIS Institutial research information system (University of Pisa) (submittedVersion)
- Topics
- Physical Sciences › Computer Science › Information Systems › Data Mining Algorithms and Applications
- Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Data Classification
- Physical Sciences › Computer Science › Information Systems › Data Mining and Machine Learning Applications
- Keywords
- grafting, post-processing, pruning, bottom-up algorithm, C4.5, computational complexity, tree size reduction
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
