Pruning decision trees and lists

Frank, Eibe

Pruning decision trees and lists

dc.contributor.advisor	Witten, Ian H.
dc.contributor.author	Frank, Eibe
dc.date.accessioned	2022-06-01T21:06:27Z
dc.date.available	2022-06-01T21:06:27Z
dc.date.issued	2000
dc.date.updated	2022-06-01T20:55:36Z
dc.description.abstract	Machine learning algorithms are techniques that automatically build models describing the structure at the heart of a set of data. Ideally, such models can be used to predict properties of future data points and people can use them to analyze the domain from which the data originates. Decision trees and lists are potentially powerful predictors and embody an explicit representation of the structure in a dataset. Their accuracy and comprehensibility depends on how concisely the learning algorithm can summarize this structure. The final model should not incorporate spurious effects-patterns that are not genuine features of the underlying domain. Given an efficient mechanism for determining when a particular effect is due to chance alone, non-predictive parts of a model can be eliminated or “pruned.” Pruning mechanisms require a sensitive instrument that uses the data to detect whether there is a genuine relationship between the components of a model and the domain. Statistical significance tests are theoretically well-founded tools for doing exactly that. This thesis presents pruning algorithms for decision trees and lists that are based on significance tests. We explain why pruning is often necessary to obtain small and accurate models and show that the performance of standard pruning algorithms can be improved by taking the statistical significance of observations into account. We compare the effect of parametric and non-parametric tests, analyze why current pruning algorithms for decision lists often prune too aggressively, and review related work-in particular existing approaches that use significance tests in the context of pruning. The main outcome of this investigation is a set of simple pruning algorithms that should prove useful in practical data mining applications.
dc.format.mimetype	application/pdf
dc.identifier.uri	https://hdl.handle.net/10289/14883
dc.language.iso	en
dc.publisher	The University of Waikato
dc.rights	All items in Research Commons are provided for private study and research purposes and are protected by copyright with all rights reserved unless otherwise indicated.
dc.title	Pruning decision trees and lists
dc.type	Thesis
pubs.place-of-publication	Hamilton, New Zealand	en_NZ
thesis.degree.grantor	The University of Waikato
thesis.degree.level	Doctoral
thesis.degree.name	Doctor of Philosophy (PhD)