Maximizing pattern separation in discretizing continuous features for classification purposes

Discretization is a fundamental phase for many classification algorithms: it aims at finding a proper set of cutoffs that subdivide a continuous domain into homogeneous intervals; the points in each interval should have a high probability of belonging to the same class. This paper proposes two different approaches for discretization: the first one consists in retrieving the optimal set of separation points through the solution of a proper linear programming problem. Since the optimal solution may require an excessive computational burden, an alternative technique, based on the iterative addition of separation points, is described. The greedy algorithm is evaluated on some artificial datasets and compared with other well-known discretization techniques such as EntMDL. The results of the simulations show the good performances of the novel algorithm in terms both of accuracy of the solution and of computational effort required for its generation.