Efficient SQL-Querying Method for Data Mining in Large Data Bases

1 Introduction

The problem of searching for optimal partitions of real value attributes (features), defined by so called cuts, has been studied by many authors (see e.g. [Catlett, 1991; Chmielewski and Grzymala-Busse, 1995; Dougherty at al., 1995; Fayyad and Irani, 1992; Liu and Setiono, 1995; Quinlan, 1993; Nguyen and Skowron, 1995]). The main goal is to discover knowledge in the form of cuts which can be used to synthesize decision trees or decision rules of high quality with respect to some quality measures (e.g. quality of classification of new unseen objects, qual­ ity defined by the decision tree height, support and con­ fidence of decision rules). In general, all those prob­ lems are hard from computational point of view (e.g.

it has been shown in [Nguyen and Skowron, 1995) that the searching problem for minimal and consistent set of cuts is NP-hard). Hence numerous heuristics have been developed searching for approximate solutions of these problems. These heuristics are based on some approxi­ mate measures estimating the quality of extracted cuts. In Section 2.1 we present a short overview of some of these measures. In our approach we use so called dis­ cernibility measures used extensively in rough set ap­ proach [Polkowski and Skowron,1998). All those meth­ ods are very efficient if data sets are stored in executive memory because (after sorting of data) the number of steps to check distribution of objects in intervals defined by consecutive cuts is of order O(N). We consider the problem of searching for optimal partition of real value attributes assuming that the large data table is repre­ sented in relational data base. In this case even the linear complexity is not acceptable because of the time for one step. The critical factor for time complexity of algorithms solving the discussed problem is the number of simple SQL queries like SELECT COUNT FROM ... WHERE attribute BETWEEN ... (related to some inter­ val of attribute values) necessary to construct such par­ titions. We assume that the answer time for such queries does not depend on the interval length (this assumption is satisfied in some existing data base servers). Using straightforward approach to optimal partition selection (with respect to a given measure), the number of neces­ sary queries is of order O(N), where N is the number of preassumed partitions of the searching space. We show some properties of considered optimization measures al­ lowing to reduce the size of searching space. Moreover, we prove that using only O(log N) simple queries, one can construct the partition very close to optimal.

2 Basic Notions

An information system [Pawlak, 1991) is a pair A = (U, A) , where U is a non-empty, finite set called the uni­ verse and A is a non-empty finite set of attributes (or fea­ tures), i.e. a : U -+ Va for a E A, where Va is called the value set of a. Elements of U are called objects or records. Two objects x, y E U are said to be discernible by at­ tributes from A if there exists an attribute a E A such that a(x) f. a(y). Any information system of the form A = (U, AU {dec}) is called decision table where dec ~ A is called decision attribute (or decision for short). With­ out loss of generality we assume that Vdec = {1, ... , d}. Then the set DECk = {x E U : dec(x) = k} will be called the kth decision class of A for 1 ~ k ~ d.

Any pair (a, c), where a is an attribute and cis a real value, is called a cut (if the attribute a E A has been uniquely specified, then cut can be denoted simply by any c E lit We say that "the cut (a, c) discerns a pair of objects x, y" if either a(x) < c ~ a(y) or a(y) < c ~ a(x).

Definition 1 The set of cuts P is A-consistent iff for any pair of objects x, y E U such that dec( x) -1- dec(y) if x and y are discernible by attributes from A then there exists a cut (a, c) E P discerning x andy.

Definition 2 The A-consistent set of cuts P is A­ optimal iff card (P) ~ card (P') for any A-consistent set of cuts P'.

The discretization problem can be defined as a prob­ lem of searching for consistent set of cuts which is opti­ mal with respect to some criteria. Nguyen and Skowron have shown that the problem of searching for discretiza­ tion using minimal number of cuts is hard (see [Nguyen and Skowron, 1995]).

Theorem 1 The problem of searching for the optimal set of cuts P in a given decision table A is N P-hard.

Since the problem of searching for optimal set of cuts is NP-hard (i.e. there is not algorithm solving this prob­ lem in polynomial time, unless P = N P), we can only find a semi-optimal solution using some approximate al­ gorithms. In the next section we shortly describe some methods often used in Machine Learning and Data Min­ ing.

2.1 The Quality Measures

Developing some decision tree induction methods (see [Fayyad and Irani, 1992; Quinlan, 1993]) and some supervised discretization methods (see [Catlett, 1991; Dougherty at al., 1995; Nguyen and Skowron, 1995; Liu and Setiono, 1995; Nguyen, 1998]), we should often solve the following problem:

FOR A GIVEN REAL VALUE ATTRIBUTE a AND SET OF CANDIDATE CUTS {c1 , ... ,CN}, FIND A CUT (a, Ci) BELONGING TO THE SET OF OPTI­ MAL CUTS WITH HIGH PROBABILITY.

For example, the algorithm for decision tree induction can be described as follows:

1. For a given set of objects U, select a cut (a, CBest) of high quality among all possible cuts and all at­ tributes;
2. Induce a partition u1' u2 of u by (a, CBest) ;
3. Recursively apply Step 1 to both sets U1, U2 of ob­ jects until some stopping condition is satisfied.

Usually, we use some measure (or quality functions) F : { c1 , ... , CN} -+ lR to estimate the quality of cuts. For a given measure F, the straightforward searching algo­ rithm for the best cut should compute the values of F for all cuts: F(c1), .. , F(cN ). The cut CBest which opti­ mizes (i.e. maximizes or minimizes) the value offunction F is selected as the result of searching process.

In next sections we recall the most frequently used measures for decision tree induction and discretization like "x 2 Test", "Entropy Function" and "Discernibitity Measure", respectively. First we fix some notations. Let us consider the attribute a and the set of all relevant cuts Ca = {c1, ... ,cN} on a.

Definition 3 The d-tuple of integers (x1 , .. ,xd) is called class distribution of the set of objects X C U iff Xk = card(X n DECk) fork E {1, ... , d}. If the set of objects X is defined by X = {u E U : p ~ a(u) < q} for some p, q E lR then the class distribution of X can be called the class distribution in [p; q).

Any cut c E Ca splits the domain Va = (la, ra) of the attribute a into two intervals: h = (la,c) ;/R = (c,ra)· For a fixed cut (a, c) we use the following notation:

• U L;, U R; - the sets of objects from ih class in h and JR. Let UL = uj UL; and UR = uj UR;;
• (L1 , .. , Ld) and (R1 , .. , Rd) - class distributions in U L and U R· Let L = 2::=1 Lj and R = 2::=1 Rj
• Cj = Lj + Rj - number of objects in the jth class;
• n = '2:~= 1 Cj = L + R- the total number of objects;
• E(UL;) = L:C; expected frequency of UL;
• E(UR;) = R:ci expected frequency of UR; where j E {1, ... , d}.

Statistical test methods

Statistical tests allow to check the probabilistic indepen­ dence between the object partition defined by decision attribute and by the cut c. The independence degree is estimated by the x 2 test given by

Intuitively, if the partition defined by c does not depend on the partition defined by the decision attribute dec then we have x 2 (c) = 0. In opposite case if there exists a cut c which properly separates objects from different decision classes the value of x 2 test for c is very high.

Discretization methods based on x 2 test are choosing only cuts with large value of this test (and delete the cuts with small value of x 2 test). There are different versions of this method (see e.g. ChiMerge [Kerber, 1992] and Chi2 [Liu and Setiono, 1995])

Entropy methods

A number of methods based on entropy measure formed the strong group of works in the domain of decision tree induction and discretization. This concept uses class­ entropy as a criterion to evaluate the list of best cuts which together with the attribute domain induce the desired intervals. The class information entropy of the set of N objects X with class distribution (N1 , ... , Nd), where N1 + ... + Nd = N, is defined by

Hence, the class information entropy of the partition in­ duced by a cut point c on attribute a is defined by

where { ul' u2} is a partition of u defined by c.

For a given feature a, the cut Cmin which minimizes the entropy function over all possible cuts is selected. There is a number of methods based on information entropy theory reported in [Catlett, 1991; Fayyad and Irani, 1992; Chmielewski and Grzymala-Busse, 1995; Quinlan, 1993] .

Boolean reasoning method

In Boolean reasoning methods, cuts are treated as Boolean variables and the problem of searching for opti­ mal set of cuts can be characterized by a Boolean func­ tion fA (where A is a given decision table). Any set of cuts is A-consistent if and only if the corresponding evaluation of variables in fA returns the value True (see [Nguyen and Skowron, 1995]) . Nguyen and Skowron shown that the quality of cuts can be measured by their discernibility properties. Intuitively, energy of th~ set of objects X C U can be defined by the num­ ber of pairs of objects from X to be discerned called conflict(X). Let (N1 , ... , Nd) be a class distribution of X, then conflict(X) can be computed by

The cut c which divides the set of objects U into U1, and u2 is evaluated by

i.e. the more is number of pairs of objects discerned by the cut (a, c), the larger is chance that c can be ~hosen to the optimal set of cut. Hence, in the discretization and decision tree induction algorithms based on Boolean reasoning approach, the quality of a given cut cis defined by number of pairs of objects discerned by c i.e.

This algorithm is called the MD-heuristics 1

3 Algorithm Acceleration Methods

In this section we present some properties discovered us­ ing the Boolean reasoning approach. These properties allow to induce decision trees and make discretization of real value attributes directly from large data base.

1 Maximal-Discernibility heuristics

3.1 Properties of the Discernibility Measure

First, let us consider two cuts C£ < en. Let (£1 , ... , Ld) be the class distribution in ( -oo; cL), (M1 , ... , Md) - the class distribution in [cL; en) and (R1 , .. . , Rd) - the class distribution in [en; oo) (see Figure 1).

Figure 1: The class distributions defined by cuts C£, en

Now we are ready to show how to compute the dif­ ference between the discernibility measures of CL and en using information about class distribution in intervals defined by these cuts. The exact formula is given in the following lemma.

Lemma 1 The following equation holds:

Proof: We have

Analogously,

Hence,

After simplifying of the last formula we obtain (2) . 0

Our goal is to find cuts maximizing the function W(c). Let us recall the notion of boundary cuts and the well known notion in statistics called median( using the nota­ tions presented in Section 2.1):

Definition 4 Any ci E Ca is called the boundary cut if there exist two objects u 1 , u 2 E U such that a( ul) E [ci-liCi)i a(uz) E [ci;ci+l) and dec(u1) :/: dec(uz).

Definition 5 For given set of cuts Ca = { c1 , .. , CN} on a, by median of the kth decision class we mean the cut c E Ca which minimizes the value ILk- Rk I· The median of the kth decision class will be denoted by Median(k).

We will show that it is enough to restrict the search to the set of boundary cuts.

Theorem 2 The cut CBest which maximizes the func­ tion W(c) can be found among boundary cuts.

Proof:Assume that Ca and Cb are consecutive boundary cuts. Then the interval [ca; cb] consists of only one deci­ sion class, say ci. For arbitrary cuts CL and CR such that Ca ::; C£ < CR ::; Cb, we have Mi i: 0 and v#iMj = 0. Then the equation 2 has a form

Thus, function W(c) is monotonic in the interval [ca; cb] because Lj=pi(Rj- Lj) is constant for all sub intervals of [ca; cb]· D

Theorem 2 allows to look for the optimal cuts among boundary cuts only. This property also holds for En­ tropy measures (see [Fayyad and Irani, 1992]). Although it is interesting but can not be used to construct effi­ cient heuristic for the investigated in the paper prob­ lem because of complexity of the algorithm detecting the boundary cuts (in case of data tables stored in RDB) . However, it was possible to find another prop­ erty allowing to eliminate the large number of cuts. Let c1 < cz ... < CN be the set of candidate cuts, and let

This property is formulated in the following theorem.

Theorem 3 The quality function W : { c1, .. ,cN} -+ N defined over the set of cuts is increasing in { c1, ... , Cmin} and decreasing in { Cmax, ... , CN}. Hence

This property is interesting because it states that one can use only 0 ( d log N) queries to determine the me­ dians of decision classes by using Binary Search Algo­ rithm. Hence one can reduce the searching space using O(d log N) SQL queries. Let us also observe that if all decision classes have similar medians then almost all cuts can be eliminated.

3.2 Fast Algorithm

The main idea is to apply the "divide and conquer" strat­ egy to determine the best cut CBest E { c1, ... , cn} with respect to a given quality function.

First we divide the set of possible cuts into k intervals (e.g. k = 2, 3, .. ). Then we choose the interval to which the best cut may belong with the highest probability. We will use some approximating measures to predict the interval which probably contains the best cut with re­ spect to discernibility measure. This process is repeated until the considered interval consists of one cut. Then the best cut can be chosen between all visited cuts.

The problem arises how to define the measure eval­ uating the quality of the interval [cL; cR] having class distributions: (L1, ... ,Ld) in (-oo;cL); (M1, ... ,Md) in [cL;cR) ; and (R1 , ... ,Rd) in [cR;oo) (see Figure 1). This measure should estimate the quality of the best cut among those belonging to the interval [cL; cR]·

Let us consider an arbitrary cut c lying between CL and CR. We have the following theorem (the proof of this theorem is included as an Appendix)

Theorem 4 The mean E(W(c)) of quality W(c) for any cut c E [cL; cR] satisfies

where conflict([cL; cR]) = L i,tj NiNj. For the standard deviation of W(c) we have

One can use formulas (3) and ( 4) to construct the measure estimating quality of the best cut in [cL; cR]

where the real parameter a from [0; 1] can be tuned in learning process. The details of our algorithm can be described as follows:

ALGORITHM: Searching for semi-optimal cut PARAMETERS: kEN and a E [0; 1]. INPUT: attribute a; the set of candidate cuts Ca = {c1, .. ,cN} on a; OUTPUT: The optimal cut c E Ca begin Left +-min; Right+- max; while (Left < Right) {see Theorem 3} !.Divide [Left; Right] into k intervals with ·equal length by (k + 1) boundary points i.e. L f . Right- Left Pi= e t + t * ; k for i = 0, .. , k. 2 . For i= 1, .. ,k compute Eval([cp;_ 1 ;cp.],a) using Formula (5). Let lPi-l;Pi] be the interval with maximal value of Eval(.); 3.Left +- Pi-1; Right+- Pi; endwhile; Return the cut CLeft; end

One can see that to determine the value Eval ([cL; cR], a) we need only O(d) simple SQL queries of the form: SELECT COUNT FROM .. . WHERE attribute BE­ TWEEN . . . . Hence the number of queries necessary for running our algorithm is of order O(dk logk N). In prac­ tice we set k = 3 because the function f ( k) = dk logk N over positive integers is taking minimum for k = 3. For k > 2, instead choosing the best interval lPi-l; Pi], the algorithm can select the best union (pi-m; Pi] of m con­ secutive intervals in every step for a predefined param­ eter m < k. The modified algorithm needs more - but still of order O(log N) - simple questions only.

4 Examples

We consider a data table consisting of 12000 records. Objects are classified into 3 decision classes with the dis­ tribution (5000, 5600, 1400), respectively. One real value attribute has been selected and N = 500 cuts on its do­ main has generated class distributions as shown in Fig­ ure 2.

The medians of classes are c1ss, c414 and c189 , respec­ tively. The median of every decision class has been de­ termined by binary search algorithm using log N = 9 simple queries. Applying Theorem 3 we conclude that it is enough to consider only cuts from {c166 , ... ,c414}. In this way 251 cuts have been eliminated by using 27 simple queries only.

In Figure 3 we show the graph of W(ci) for i E {166, .. . , 414} and we illustrated the outcome of applica­ tion of our algorithm to the reduce set of cuts for k = 2 and a= 0.

First the cut c290 is chosen and it is necessary to deter­ mine to which of the intervals [c1ss , c29o) and [c29o,c414) the best cut belongs. The values of function Eval on these intervals is computed: Eval([c16s, c29o], 0) 23927102, Eval([c29o, c414], 0) = 24374685. Hence, the best cut is predicted to belong to [c29o, c414) and the search process is reduce to the interval [c290 , c414 ). The above procedure is repeated recursively until the selected interval consists of single cut only. For our example, the best cut c2gs has been successfully selected by our al­ gorithm. In general the cut selected by the algorithm is not necessarily the best. However numerous experi­ ments on different large data sets shown that the cut c* returned by the algorithm is close to the best cut CBest (i.e. w~(c*)) · 100% is about 99.9%). CB ~ .st

5 Conclusions

The problem of optimal binary partition of continuous attribute domain for large data sets stored in relational data bases has been investigated. We show that one can reduce the number of simple queries from O(N) to O(log N) to construct the partition very close to the op­ timal one. We plan to extern these results for other measures .