Feature set decomposition for decision trees

Article type: Research Article

Authors: Rokach, Lior | Maimon, Oded

Affiliations: Department of Industrial Engineering, Tel-Aviv University, Israel. E-mail: liorr@eng.tau.ac.il, maimon@eng.tau.ac.il

Abstract: This paper presents practical aspects of feature set decomposition in classification problems using decision trees. Feature set decomposition generalizes the task of feature selection which is extensively used in data mining. Feature selection aims to provide a representative set of features from which a classifier is constructed. On the other hand, feature set decomposition decomposes the original set of features into several subsets, and builds a classifier for each subset. The classifiers are then combined for classifying new instances. In order to examine the idea, a general framework that searches for helpful decomposition structures is proposed. This framework nests many algorithms, two of which are tested empirically over a set of benchmark datasets. The first algorithm performs a serial search while using a new Vapnik-Chervonenkis dimension bound for multiple oblivious trees as an evaluating schema. The second algorithm performs a multi-search while using wrapper evaluating schema. This work indicates that feature set decomposition can increase the accuracy of decision trees.

Keywords: decision trees, naïve Bayes, Vapnik-Chervonenkis, decomposition

DOI: 10.3233/IDA-2005-9202

Journal: Intelligent Data Analysis, vol. 9, no. 2, pp. 131-158, 2005