From centralized to distributed decision tree induction using CHAID and fisher's linear discriminant function algorithms

Article type: Research Article

Authors: Ouyang, Jie | Patel, Nilesh | Sethi, Ishwar K.

Affiliations: Department of System Engineering and Computer Science, Oakland University, Rochester, MI, USA. E-mail: [email protected], [email protected], [email protected]

Abstract: 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 extends two well-known decision tree methods for centralized data to distributed data settings. The first method is an extension of CHAID algorithm and generates single feature based multi-way split decision trees. The second method is based on Fisher's linear discriminant (FLD) function and generates multifeature binary trees. Both methods aim to generate compact trees and are able to handle multiple classes. The suggested extensions for distributed environment are compared to their centralized counterparts and also to each other. Theoretical analysis and experimental tests demonstrate the effectiveness of the extensions. In addition, the side-by-side comparison highlights the advantages and deficiencies of these methods under different settings of the distribution environments.

Keywords: Data mining, distributed computing, chi-square test, chaid, fisher's linear discriminant analysis, decision tree

DOI: 10.3233/IDT-2011-0102

Journal: Intelligent Decision Technologies, vol. 5, no. 2, pp. 133-149, 2011