𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A novel algorithm to optimize classification trees

✍ Scribed by Martin Kröger; Bernd Kröger

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
821 KB
Volume
95
Category
Article
ISSN
0010-4655

No coin nor oath required. For personal study only.

✦ Synopsis

Breiman et al. (1984)

expounded a method called Classification and Regression Trees, or CART, which is of use for nonparametric discrimination and regression. In this paper we present an algorithm which is able to increase the quality of classification trees beyond the quality of trees, which are based on direct evaluation of a splitting criterion. The novel algorithm calculates a large number of possible segments of trees instead of a single tree, and recursively selects the best of these parts to form an optimal tree. The presented method makes use of a (and works for an arbitrary) splitting criterion. But the criterion is only used to speed up the algorithm, not to determine directly the resulting tree. It includes the evaluation of trees resulting from direct splitting as a special case. Examples are given.

📜 SIMILAR VOLUMES

A sufficiently fast algorithm for findin
A sufficiently fast algorithm for finding close to optimal clique trees
✍ Ann Becker; Dan Geiger 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 172 KB

We offer an algorithm that finds a clique tree such that the size of the largest clique is at most (2α + 1)k where k is the size of the largest clique in a clique tree in which this size is minimized and α is the approximation ratio of an α-approximation algorithm for the 3-way vertex cut problem. W

An optimal algorithm to reconstruct tree
An optimal algorithm to reconstruct trees from additive distance data
✍ Jotun J. Hein 📂 Article 📅 1989 🏛 Springer 🌐 English ⚖ 362 KB

In this article the question of reconstructing a phylogeny from additive distance data is addressed. Previous algorithms used the complete distance matrix of the n OTUs (Operational Taxonomic Unit), that corresponds to the tips of the tree. This used O(n2) computing time. It is shown that this is wa

A Simple Optimal Parallel Algorithm for
A Simple Optimal Parallel Algorithm for a Core of a Tree
✍ S.T. Peng; W.T. Lo 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 354 KB

A core of a tree \(T=(V, E)\) is a path in \(T\) which minimizes \(\Sigma_{v \in V}\) \(d(v, P)\), where \(d(v, P)\), the distance from a vertex \(v\) to path \(P\), is defined as \(\min _{u \in P} d(v, u)\). We present an optimal parallel algorithm to find a core of \(T\) in \(O(\log n)\) time usin