Optimal techniques for class-dependent attribute discretization

Preprocessing of raw data has been shown to improve performance of knowledg e discovery processes. Discretization of quantitative attributes is a key c omponent of preprocessing and has the potential to greatly impact the effic iency of the process and the quality of its outcomes. In attribute discreti zation, the value domain of an attribute is partitioned into a finite set o f intervals so that the attribute can be described using a small number of discrete representations. Discretization therefore involves two decisions, on the number of intervals and the placement of interval boundaries. Previo us approaches for quantitative attribute discretization have used heuristic algorithms to identify partitions of the attribute value domain. Therefore , these approaches cannot be guaranteed to provide the optimal solution for the given discretization criterion and number of intervals. In this paper, we use linear programming (LP) methods to formulate the attribute discreti zation problem. The LP formulation allows the discretization criterion and the number of intervals to be integral considerations of the problem. We co nduct experiments and identify optimal solutions for various discretization criteria and numbers of intervals.