arrow
Return

Supervised classification using graph-based space partitioning

delete2019-12-01
delete3
PRE
AI
N
Nicola Yanev
V
Ventzeslav Valev
A
Adam Krzyżak *
K
Karima Ben Suliman
DOI:10.1016/j.patrec.2019.07.024delete
deleteOriginal
deleteShare
deleteSave
Abstract

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

Pattern Recognition Letters cover
Pattern Recognition Letters
IF:
3.3
Papers:
8.0K
Citations:
2.0W

Organization

C
concordia university - canada
Scholars:
8.0K
Papers: 8.9K
Citations: 1.1W
B
Bulgarian Academy of Sciences
Scholars:
235
Papers: 90
Citations: 2.3K
Cited Papers

Cited Papers

A flexible annealing chaotic neural network to maximum clique problem
err2011-11-21
err6
PREAI
errYang, Gang; Tang, Zheng; Zhang, Zhiqiang; Zhu, Yunyi
errShare
errSave
A review of technical solutions and simulation approaches for ship collisions with lock gates
err2015-05-02
err0
errOAAI
errS. Ehlers; H. Le Sourne; L. Buldgen; J. Ollero; C. Robertson; P. Rigo
errShare
errSave
errShare
errSave
A New Organotypic 3D Slice Culture of Mouse Meibomian Glands Reveals Impact of Melanocortins
err2022-11-29
err0
errOAAI
errIngrid Zahn; Fabian Garreis; Martin Schicht; Vera Rötzer; Jens Waschke; Yuqiuhe Liu; Valerian L. Altersberger; Friedrich Paulsen; Jana Dietrich
errShare
errSave
no more