On Efficient Handling of Continuous Attributes in Large Data Bases

Article type: Research Article

Authors: Nguyen, Hung Son

Affiliations: Institute of Mathematics, Warsaw University, ul. Banacha 2, 02-097, Warsaw, Poland

Abstract: Some data mining techniques, like discretization of continuous attributes or decision tree induction, are based on searching for an optimal partition of data with respect to some optimization criteria. We investigate the problem of searching for optimal binary partition of continuous attribute domain in case of large data sets stored in relational data bases (RDB). The critical for time complexity of algorithms solving this problem is the number of I/O database operations necessary to construct such partitions. In our approach the basic operators are defined by queries on the number of objects characterized by means of real value intervals of continuous attributes. We assume the answer time for such queries does not depend on the interval length. The straightforward approach to the optimal partition selection (with respect to a given measure) requires O(N) basic queries, where N is the number of preassumed partition parts in the searching space. We show properties of the basic optimization measures making possible to reduce the size of searching space. Moreover, we prove that using only O(\log N) simple queries, one can construct a partition very close to optimal.

Keywords:

Journal: Fundamenta Informaticae, vol. 48, no. 1, pp. 61-81, 2001