Return
Supervised classification using graph-based space partitioning
DOI:10.1016/j.patrec.2019.07.024.png)
Abstract
En 中文
In the paper we consider the supervised classification problem using space partitioning into multidimensional rectangular boxes. We show that the problem at hand can be reduced to computational geometry problem involving heuristic minimum clique cover problem satisfying the k-nearest neighbor rule. We first apply heuristic algorithm for partitioning a graph into a minimal number of maximal cardinality cliques inscribed into the smallest (in volume) rectangular parallelepipeds called boxes. The main advantage of the new classifier called Box algorithm which optimally utilizes the geometrical structure of the training set is decomposition of the l-class problem (1> 2) into l binary classification problems. We discuss computational complexity of the proposed method and the resulting classification rules. The extensive experiments performed on the real and simulated data show that in almost all cases the Box algorithm performs significantly better than k-NN, SVM and decision trees. (C) 2019 Elsevier B.V. All rights reserved.
Keywords:
Supervised classification
Feature space partitioning
Graph partitioning
Nearest neighbor rule
Box algorithm
Journal
IF:
3.3
Papers:
8.0K
Citations:
2.0W
Organization
Cited Papers
no more

