DocumentCode :
594939
Title :
Classification using graph partitioning
Author :
Valev, Ventzeslav ; Yanev, N.
Author_Institution :
Inst. of Math. & Inf., Sofia, Bulgaria
fYear :
2012
fDate :
11-15 Nov. 2012
Firstpage :
1261
Lastpage :
1264
Abstract :
This paper explores the classification problem based on parallel feature partitioning. This formulation leads to a new problem in computational geometry. While this new problem appears to be NP-complete, it is shown that the proposed graph theoretical platform makes it semi-tractable, allowing the use of conventional tools for its solution. Here, by conventional, we mean any exact or heuristic algorithm for partitioning a graph into a minimal number of cliques or for finding the clique of maximum cardinality while seeking an efficient heuristic algorithm. An important advantage of this approach is the decomposition of a problem involving l classes into l optimization problems involving a single class. The computational complexity of the method, computational procedures, and classification rules are discussed. A geometrical interpretation of the solution is also given. Using the proposed approach, the geometrical structure of the training set is utilized in the best possible way.
Keywords :
computational complexity; computational geometry; graph theory; optimisation; pattern classification; NP-complete problem; classification problem; classification rules; computational complexity; computational geometry; exact algorithm; geometrical structure; graph partitioning; heuristic algorithm; l-classes; l-optimization problems; maximum cardinality clique; parallel feature partitioning; semitractable graph theory; Clustering algorithms; Color; Heuristic algorithms; Optimization; Partitioning algorithms; Pattern recognition; Training;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Pattern Recognition (ICPR), 2012 21st International Conference on
Conference_Location :
Tsukuba
ISSN :
1051-4651
Print_ISBN :
978-1-4673-2216-4
Type :
conf
Filename :
6460368
Link To Document :
بازگشت