| Full text | |
| Author(s): Show less - |
Sapucaia, Allan
;
de Rezende, Pedro J.
;
de Souza, Cid C.
;
Gervasi, O
;
Murgante, B
;
Misra, S
;
Garau, C
;
Blecic, I
;
Taniar, D
;
Apduhan, BO
;
Rocha, AMAC
;
Tarantino, E
;
Torre, CM
Total Authors: 13
|
| Document type: | Journal article |
| Source: | COMPUTATIONAL SCIENCE AND ITS APPLICATIONS, ICCSA 2021, PT V; v. 12953, p. 16-pg., 2021-01-01. |
| Abstract | |
A core problem in machine learning is the classification of points in high dimensions. In an attempt to minimize the resources required and facilitate data visualization, a recent effort has been made to project the points non-linearly onto the plane and apply classification methods. The quality of any such projection can be measured by evaluating how the resulting points of different classes are set apart. In this paper, we study integer linear programming (ILP) models to determine the coarseness of sets of bicolored points in the plane, which measures how well-separated these two classes are. The complexity of computing the coarseness of a point set is unknown, but conjectured to be NP-hard. We present a base ILP model for the problem with an exponential number of variables and constraints, followed by a series of improvements in the quality of its relaxation and close with an efficient column generation implementation. These modifications allow us to solve instances with three times as many points as the base model, within the same time and memory limits. By combining of our preprocessing techniques and a heuristic from the literature, we are even able to solve to proved optimality many instances of our benchmark in polynomial time. A comprehensive experimental study is presented to evaluate the impact of each improvement. (AU) | |
| FAPESP's process: | 14/12236-1 - AnImaLS: Annotation of Images in Large Scale: what can machines and specialists learn from interaction? |
| Grantee: | Alexandre Xavier Falcão |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 18/26434-0 - Exact and heuristic algorithms for solving difficult problems related to computational geometry |
| Grantee: | Pedro Jussieu de Rezende |
| Support Opportunities: | Regular Research Grants |
| FAPESP's process: | 18/14883-5 - Geometric decomposition problems |
| Grantee: | Allan Sapucaia Barboza |
| Support Opportunities: | Scholarships in Brazil - Doctorate (Direct) |