Hierarchical multi-class LAD based on OvA-binary tree using genetic algorithm. Issue 21 (30th November 2015) - Kim, Hwang Ho; Choi, Jin Young
Highlights: We propose a hierarchical multi-class classification method using LAD based on OvA-binary tree. We suggest an efficient node partitioning method for constructing an OvA-binary tree. We design an efficient genetic algorithm to generate OvA-type LAD patterns for hierarchical multi-class classification. We develop the procedures to build and explore OvA-binary tree for multi-class classification. We show the superiority of the suggested algorithm through a numerical experiment. Abstract: Recently, logical analysis of data (LAD) using a classifier based on a linear combination of patterns has been introduced, providing high classification accuracy and pattern-based interpretability on classification results. However, it is known that most of LAD-based multi-classification algorithms have conflicts between classification accuracy and computational complexity because they are based on class decomposition method such as one versus all or one versus one. Furthermore, it is difficult to explain the decision rule in the classification procedure because they only use the final scores calculated by classifiers. To overcome this issue, in this paper, we propose a hierarchical multi-class classification method using LAD based on a one versus all (OvA)-binary tree, called hierarchical multi-class LAD (HMC-LAD). It constructs an OvA-binary tree by partitioning a node with K ( ⩾ 2 ) classes into two sub-nodes by identifying one distinct class from the remaining ( K - 1 ) classes repeatedly. Specifically, we suggest a node partition method for constructing an efficient OvA-binary tree, genetic algorithm for generating patterns for a node under consideration, and OvA-binary tree exploration method for performing multi-class classification. Through a numerical experiment using benchmark datasets from the UCI machine-learning repository, we confirm that (i) the suggested node partition method is efficient compared to a random partition method, and (ii) the classification performance of HMC-LAD is superior to existing multi-class LAD algorithms and other supervised learning approaches. The proposed HMC-LAD can be applied to expert and intelligent systems to effectively categorize large amount of data in knowledge base and perform inference for decision making.