New clustering algorithms for the support vector machine based hierarchical classification

This study presents two new clustering algorithms for partition of data samples for the support vector machine (SVM) based hierarchical classification. A divisive (top-down) approach is considered in which a set of classes is automatically separated into two smaller groups at each node of the hierarchy. The first algorithm splits the data samples based on a variation of the normalized cuts (NCuts) clustering algorithm wherein the weights of adjacency matrix are modified to utilize class membership in the process. The second algorithm also uses the NCuts clustering: however, it considers the involved classes rather than the individual data samples. It uses the minimum distances between the convex hulls of classes as a distance measure for determining the weights of the graph. Splits are determined for both algorithms based on the eigenvector corresponding to the second smallest eigenvalue of a Laplacian matrix, and it is observed that the proposed algorithms generate well-separated and well-balanced clusters. Unlike other clustering methods used for this purpose, the methods in the present study are found to be more suitable when SVMs are used as base classifiers. As demonstrated in the experiments, the proposed clustering algorithms are integrated into the hierarchical SVM classifiers, which results in significantly improved testing times with a negligible decrease in classification accuracies as compared to the traditional multi-class SVMs. (C) 2010 Elsevier B.V. All rights reserved.