Abstract:

In order to solve the low efficiency of optimized geometric ensembles(OGE) caused by a large number of redundant computations in constructing the set of characteristic boundary points, two improved geometric ensembles——Gabriel OGE and heuristics OGE were proposed respectively by applying Gabriel neighboring rule and its heuristics, which could accelerate the computation of characteristic boundary points compared with OGE in experiments. The results showed that although Gabriel OGE had the same time complexity with OGE in computing characteristic boundary points, it became much faster for reducing a number of redundant algorithm computations. Heuristics OGE could not only decreases the average time complexity to O(dM²), but also have the most efficiency when dealing with a large dataset. Gabriel OGE and heuristics OGE could effectively increase the computing speed and greatly reduce the computing time when having the same classification results with OGE.

Key words:  piecewise linear classifier, geometric ensembles, Gabriel neighboring rule, heuristic algorithm, characteristic boundary points