Structure-driven induction of decision tree classifiers through neural learning

doi:10.1016/S0031-3203(97)00005-8

Pattern Recognition

Volume 30, Issue 11, November 1997, Pages 1893-1904

https://doi.org/10.1016/S0031-3203(97)00005-8 Get rights and content

Abstract

The decision tree classifiers represent a nonparametric classification methodology that is equally popular in pattern recognition and machine learning. Such classifiers are also popular in neural networks under the label of neural trees. This paper presents a new approach for designing these classifiers. Instead of following the common top-down approach to generate a decision tree, a structure-driven approach for induction of decision trees, SDIDT, is proposed. In this approach, a tree structure of fixed size with empty internal nodes, i.e. nodes without any splitting function, and labeled terminal nodes is first assumed. Using a collection of training vectors of known classification, a neural learning scheme combining backpropagation and soft competitive learning is then used to simultaneously determine the splits for each decision tree node. The advantage of the SDIDT approach is that it generates compact trees that have multifeature splits at each internal node which are determined on global rather than local basis; consequently it produces decision trees yielding better classification and interpretation of the underlying relationships in the data. Several well-known examples of data sets of different complexities and characteristics are used to demonstrate the strengths of the SDIDT method.

References (39)

L. Wehenkel et al.
Decision trees and transient stability of electric power systems
Automatica
(1991)
J.L. Talmon
A multiclass nonparametric partitioning algorithm
I.K. Sethi et al.
Design of multicategory multifeature split decision trees using perceptron learning
Pattern Recognition
(1994)
P.E. Utgoff et al.
An incremental method for finding multivariate splits for decision trees
M. Bichsel et al.
Minimum class entropy: A maximum information approach to layered neural networks
Neural Networks
(1989)
J.R. Quinlan
Decision trees as probabilistic classifiers
D.E. Rumelhart et al.
Feature discovery by competitive learning
Cognitive Sci.
(1985)
I.K. Sethi et al.
Symbolic approximation of feedforward neural networks
R.P Gorman et al.
Analysis of hidden units in a layered network trained to classify sonar targets
Neural Networks
(1988)
Q.R. Wang et al.
Analysis and design of a decision tree based on entropy reduction and its application to large character set recognition
IEEE Trans. Pattern Analysis Mach. Intell.
(July 1984)

K. Srinivasan et al.

Machine learning approaches to estimating software-development effort

IEEE Trans. Software Eng.

(1995)

D. Bowserchao et al.

Comparison of the use of binary decision trees and neural networks in top-quark detection

Phys. Rev. D

(1993)

L. Breiman et al.

Classification and Regression Tree

(1984)

S.B. Gelfand et al.

An iterative growing and pruning algorithm for classification tree design

IEEE Trans. Pattern Analysis Mach. Intell.

(1991)

R.M. Goodman et al.

Decision tree design from a communication theory standpoint

IEEE Trans. Inform. Theory

(1988)

X. Li et al.

Tree classifiers with a permutation statistic

Pattern Recognition

(1990)

J.R. Quinlan

Induction of decision trees

Mach. Learning

(1986)

I.K. Sethi et al.

Efficient decision tree design for discrete variable pattern recognition problems

Pattern Recognition

(1978)

I.K. Sethi et al.

Hierarchical classifier design using mutual information

IEEE Trans. Pattern Analysis Mach. Intell.

(1982)

Cited by (27)

A novel acoustic emission detection module for leakage recognition in a gas pipeline valve
2017, Process Safety and Environmental Protection
Citation Excerpt :
Then, the effective features were trained and tested using the SVM to determine the level of valve leakage. To verify the SVM models, the performance of the classifiers, including the accuracy, the Cohen’s kappa number, and the training time, were compared to the corresponding data from the k-nearest neighbor classifier (k-NN) (Liao and Vemuri, 2002), neural network classifier (NN) (Yu and Junsheng, 2006), naive Bayes classifier (NB) (Jiang et al., 2012), and decision tree classifier (DT) (Sethi, 1997). Acoustic emission is a spontaneous release of elastic energy during the deformation of a material and can be detected by an AE sensor in all directions.
Internal valve leakage in a natural gas pipeline seriously impairs the safe operation on pipelines, and the recognition of leakages has therefore been a major concern of the industry. In this study, a novel leakage detection scheme based on kernel principal component analysis (kernel PCA) and the support vector machine (SVM) classifier for the recognition of the leakage level is constructed. Using this approach, the acoustic signal of the leakage is obtained as the feature source using an acoustic emission (AE) sensor. The kernel PCA is used to reduce the dimensionality of the features and extract the optimal features for the classification process, and the SVM is applied to perform the recognition of the leakage levels. The performance of the classification process based on kernel PCA and the classifier are evaluated in terms of the accuracy, Cohen’s kappa number and training time. The experimental results demonstrate that the intelligent recognition model based on kernel PCA and SVM classifier is very effective for recognizing the leakage level of a valve in a natural gas pipeline.
A balanced neural tree for pattern classification
2012, Neural Networks
Citation Excerpt :
On the other hand, one cannot decide an ideal architecture of an NN (number of hidden layers and number of nodes in each hidden layer) for a given training dataset. For this reason, a hybridisation of these two methodologies called neural tree (NT) (Deffuant, 1990; Lippmann, 1987; Sankar & Mammone, 1992; Sethi & Yoo, 1997; Sirat & Nadal, 1990; Utgoff, 1989), has been investigated to combine the advantages of both DTs and NNs. Some approaches to this problem were motivated by the lack of a reliable procedure for defining the appropriate size of feed-forward neural networks in practical applications.
This paper proposes a new neural tree (NT) architecture, balanced neural tree (BNT), to reduce tree size and improve classification with respect to classical NTs. To achieve this result, two main innovations have been introduced: (a) perceptron substitution and (b) pattern removal. The first innovation aims to balance the structure of the tree. If the last-trained perceptron largely misclassifies the given training set into a reduced number of classes, then this perceptron is substituted with a new perceptron. The second novelty consists of the introduction of a new criterion for the removal of tough training patterns that generate the problem of over-fitting. Finally, a new error function based on the depth of the tree is introduced to reduce perceptron training time. The proposed BNT has been tested on various synthetic and real datasets. The experimental results show that the proposed BNT leads to satisfactory results in terms of both tree depth reduction and classification accuracy.
Induction of multiclass multifeature split decision trees from distributed data
2009, Pattern Recognition
The decision tree-based classification is a popular approach for pattern recognition and data mining. Most decision tree induction methods assume training data being present at one central location. Given the growth in distributed databases at geographically dispersed locations, the methods for decision tree induction in distributed settings are gaining importance. This paper describes one such method that generates compact trees using multifeature splits in place of single feature split decision trees generated by most existing methods for distributed data. Our method is based on Fisher's linear discriminant function, and is capable of dealing with multiple classes in the data. For homogeneously distributed data, the decision trees produced by our method are identical to decision trees generated using Fisher's linear discriminant function with centrally stored data. For heterogeneously distributed data, a certain approximation is involved with a small change in performance with respect to the tree generated with centrally stored data. Experimental results for several well-known datasets are presented and compared with decision trees generated using Fisher's linear discriminant function with centrally stored data.
Efficient design of neural network tree using a new splitting criterion
2008, Neurocomputing
Citation Excerpt :
The NNTree is a decision tree with each non-terminal node being a neural network. In [35], Sethi and Yoo have proposed a decision tree whose hierarchy of splits is determined in a global fashion by a neural learning algorithm. Recently, Zhou and Chen [45] have introduced a hybrid learning approach named HDT that embeds neural network in some leaf nodes of a binary decision tree.
This paper presents the design of a hybrid learning model, termed as neural network tree (NNTree). It incorporates the advantages of both decision tree and neural network. An NNTree is a decision tree, where each non-terminal node contains a neural network. The idea of the proposed method is to use the framework of multilayer perceptron to design tree-structured pattern classifier. At each non-terminal node, the multilayer perceptron partitions the dataset into $m$ subsets, $m$ being the number of classes in the dataset present at that node. The NNTree is designed by splitting the non-terminal nodes of the tree by maximizing classification accuracy of the multilayer perceptron. In effect, it produces a reduced height $m$ -ary tree. The versatility of the proposed scheme is illustrated through its application in diverse fields. The effectiveness of the hybrid algorithm, along with a comparison with other related algorithms, has been demonstrated on a set of benchmark datasets. Simulation results show that the NNTree achieves excellent performance in terms of classification accuracy, size of the tree, and classification time.
Geno-fuzzy classification trees
2004, Pattern Recognition
Making the non-terminal nodes of a binary tree classifier fuzzy can mitigate tree brittleness. Using a genetic algorithm, two optimization techniques are explored. In one case, each generation minimizes classification error by optimizing a common fuzzy percent, p_T, used to determine parameters at every node. In the other case, each generation yields a sequence of minimized node-specific parameters. The output value is determined through defuzzification after input vectors, in general, take both paths at each node with a weighting factor determined by the node membership functions. Experiments conducted using this geno-fuzzy approach yield an improvement compared with other classical algorithms.
Neural network induction graph for pattern recognition
2004, Neurocomputing
Citation Excerpt :
This method is now much used in browsing data methods such as knowledge retrieval from the data (also called data-mining [7]). Many works use a tree structure to build either a neural tree [19] (the nodes of the tree being neurons which are used as non-linear binary decision functions), or neural networks trees [17,18] (nodes of the tree being neural networks which are used as non-linear n-ary decision functions). We propose to define a new structure based on a graph of neural networks which is called an NNIG.
This paper presents a novel architecture of neural networks designed for pattern recognition. The concept of induction graphs coupled with a divide-and-conquer strategy defines a neural network induction graph (NNIG). First, the NNIG concept is described and its properties detailed. It is based on a set of several little neural networks, each one discriminating only two classes. The specialization of each neural network simplifies their structure and improves the classification. The principle used to perform the decision of classification on an input pattern is explained. The latter enables to take into account dubious decisions identified by the NNIG. The last section presents experimental results. A significant gain in the global classification rate can be obtained by using an NNIG. The discussion is illustrated by tests on databases from the UCI machine learning database repository. The experimental results show that an NNIG can achieve a better learning, simpler neural networks and an improved performance in classification. A final illustration is presented on a real microscopical imaging problem for the classification of cells in serous cytology.

View all citing articles on Scopus

View full text

Structure-driven induction of decision tree classifiers through neural learning

Abstract

Automatica

Pattern Recognition

Neural Networks

Cognitive Sci.

Neural Networks

Analysis and design of a decision tree based on entropy reduction and its application to large character set recognition

IEEE Trans. Pattern Analysis Mach. Intell.

Machine learning approaches to estimating software-development effort

IEEE Trans. Software Eng.

Comparison of the use of binary decision trees and neural networks in top-quark detection

Phys. Rev. D

Classification and Regression Tree

An iterative growing and pruning algorithm for classification tree design

IEEE Trans. Pattern Analysis Mach. Intell.

Decision tree design from a communication theory standpoint

IEEE Trans. Inform. Theory

Tree classifiers with a permutation statistic

Pattern Recognition

Induction of decision trees

Mach. Learning

Efficient decision tree design for discrete variable pattern recognition problems

Pattern Recognition

Hierarchical classifier design using mutual information

IEEE Trans. Pattern Analysis Mach. Intell.