Classification Using Heuristics for Computing Hyperplanes

Classification is the process of learning relationships between a set of attributes and a set of predetermined classes using a given data set. Two methods for classification are presented
in this paper. Both methods use the same heuristics to compute hyperplanes for separating regions of different classes but differ substantially in the form of the solution and the computational requirements. The first method (COGS) classifies by optimizing geometric shapes.
A COGS solution consists of a set of convex regions, each of which contains points predominantly from one class. The heuristically computed hyperplanes form {\em tight} boundaries for the convex regions. COGS produces a classification solution using a randomized search procedure to
minimizes the number of regions given an upper limit on the training set classification error.
In contrast to the computationally intensive COGS, the second method (HOT) generates oblique decision trees using a novel and simple algorithm. HOT also differs from COGS by using the
heuristically computed hyperplanes as candidates for discriminating regions of
different classes in the nodes of the decision trees generated. Experimental results on various benchmarks indicate that the decision trees generated are well suited for some
problem domains. HOT is simple and easy to incorporate into most decision tree packages,
yet its results compare well with much more complex schemes for oblique trees.