Technique for Effectively Instantiating Attributes in Association Rules

The invention relates to data processing systems and methods, and more particularly to systems and methods for managing databases using association rules.

In running day-to-day business, many companies use database systems to collect large amounts of data. Data mining techniques have been developed to help these companies to effectively manage the data, and extract insightful information therefrom to improve their business. For example, in a service or retail business, a favorable promotional period may be determined by applying one such data mining technique to sales data collected over time.

Data mining techniques normally use association rules to determine correlations between attributes of the collected data. Each rule has support and confidence measures associated therewith. In accordance with one such technique, a problem of identifying, say, a favorable promotional period may be formulated using an optimized association rule containing at least one uninstantiated attribute, namely, an unknown time interval for the promotional period. In solving the problem, the attribute is instantiated, i.e., the time interval is identified, such that either the support or confidence of the optimized association rule is maximized.

In prior art, application of an optimized association rule to determine an optimal interval is described in T. Fukuda et al., "Mining Optimized Association Rules for Numeric Attributes," Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Jun. 1996, pp. 182-191. However, in this prior art application, only a single optimal interval can be determined, which is inadequate in many applications where multiple favorable intervals are required. The deficiency of the prior art technique may stem from the general belief that fulfillment of an optimized association rule containing an arbitrary number of uninstantiated attributes by exhausting all possible instantiations therefor based on a large amount of data is impractical.

Accordingly, in data mining where an optimized association rule containing a multiplicity of uninstantiated attributes is used, a methodology for effectively instantiating such attributes is needed.

In accordance with the invention, weights are assigned to instantiations for an uninstantiated attribute in an association rule. Each instantiation is positioned in an array based on the weight assigned thereto. A temporary optimized set of instantiations is identified from the array. This temporary optimized set is recursively updated to obtain the ultimate optimized set, and is used to limit the number of instantiations from the array to be considered in obtaining the ultimate optimized set.

In accordance with an aspect of the invention, where the uninstantiated attribute comprises a categorical attribute which needs to be instantiated by an object or a discrete numeric value, in addition to the temporary optimized set, a first intermediate set and a second different intermediate set of instantiations for the attribute are recursively identified from the array. Assuming that the number of the instantiations in the second intermediate set is at least the number of the first intermediate set, the second intermediate set is disregarded in favor of the first intermediate set based on certain predetermined criteria. Advantageously, the number of instantiations from the array is further limited for the consideration of the ultimate optimized set.

In accordance with another aspect of the invention, where an association rule has one or more uninstantiated numeric attributes which need to be instantiated by a range of numeric values, instantiations are pre-screened before they are inducted into the above array. The pre-screening involves determining the size of a subspace defined by each instantiation for the numeric attributes in an m-dimensional space, where m represents the number of the numeric attributes. For two given instantiations, if the size of a subspace defined by a first instantiation is larger than that defined by a second instantiation, the first instantiation is disregarded in favor of the second instantiation based on other predetermined criteria. Thus, only selected instantiations, as opposed to all possible instantiations, are inducted into the array for the optimized instantiation consideration.

In the drawing,

FIG. 1 is a block diagram of a data processing system in accordance with the invention;

FIG. 2 illustrates a segment of a database in the system of FIG. 1;

FIG. 3 illustrates a routine for finding a range of values satisfying certain constraints in identifying an optimized confidence set of instantiations in system of FIG. 1;

FIG. 4 is a table for determining the range of values in the routine of FIG. 3;

FIG. 5 illustrates a routine for determining the optimized confidence set of instantiations using the routine of FIG. 3;

FIG. 6 illustrates a routine for pruning intermediate sets of instantiations in identifying an optimized confidence set of instantiations in accordance with the invention;

FIG. 7 illustrates a routine for determining the optimized confidence set of instantiations using the routine of FIG. 6; and

FIG. 8 illustrates a routine for screening instantiations of numeric attributes to be considered in a determination of an optimized confidence set of instantiations in accordance with the invention.

FIG. 1 illustrates data processing system 100 embodying the principles of the invention. System 100 includes processor 105, instantiation manipulator 107, and memory 110 which contains, inter alia, database 115. Illustratively, system 100 is used by a telecom company providing telecommunications services to manage telephone call data collected in database 115. Memory 110 also contains routines for instructing processor 105 to process the collected data using optimized association rules in accordance with the invention.

In general, association rules provide a mechanism for determining correlations between attributes of collected data. An association rule defines a relation of attributes A's formulated in atomic conditions, either in the form of A=p representing a categorical object or a numeric value, or A .di-elect cons.›u, v! representing a range of numeric values from u to v. If p is a specified object or value from a pre-defined domain of A, the attribute A=p is said to be instantiated. Otherwise, if p is a variable, the attribute is said to be uninstantiated. Likewise, the attribute A .ANG.›u, v! is instantiated or uninstantiated depending on whether u and v are specified values or variables.

The atomic conditions can be combined to yield a complex condition using operators "" and "", denoting the logical "AND" and logical "OR" operators, respectively. An association rule R assumes a general form C.sub.a .fwdarw.C.sub.b, where C.sub.a and C.sub.b are each atomic or complex conditions involving one or more attributes, and in a conjunctive relation. Each rule has support and confidence measures associated therewith.

Let sup(C) represent the support measure of a condition C, which is a ratio of the number of tuples or data records satisfying the condition C to the total number of tuples in the relation. The support of rule R: C.sub.a .fwdarw.C.sub.b, denoted sup(R), is defined to be the same as the support of C.sub.a, i.e.,

The confidence of rule R, denoted conf(R), is defined to be a ratio of the support of the condition C.sub.a C.sub.b to that of C.sub.a, i.e., ##EQU1##

FIG. 2 tabulates a segment of database 115 in rows 201, 203 and 205, which summarize certain telephone call data derived from a total number of 2,000 calls handled by the telecom company in a selected week period. Specifically, row 201 enumerates the dates in that week, denoted 1-7. Row 203 enumerates the number of those calls originated from New York on date j, where j=1, 2, . . . , 7. Row 205 enumerates the number of those calls made from New York to France on date j. Consider, for example, an association rule R1 representing a relation involving attributes "date" representing a date in the week, "src.sub.-- city" representing a call origination city, and "dst.sub.-- country" representing a call destination country. In particular, rule R1 focuses on the relation of the number of telephone calls made from src.sub.-- city=NY to dst.sub.-- country=France on a particular date j. In short, ##EQU2## Rows 209 and 211 in FIG. 2 respectively enumerate the measures of the support and confidence of rule R1, i.e., sup(R1) and conf(R1). These measures are readily determined by setting above C.sub.a =›(date=j)(src.sub.-- city =NY)!, and C.sub.b =(dst.sub.-- country=France) in expressions ›1! and ›2!. For example, in column 130 where j=7, sup(R1)=sup(C.sub.a)=number of calls from NY on date 7/total number of calls in the week=180/2,000=0.09. In addition, in column 130, conf(R1)=sup(C.sub.a **C.sub.b)/sup(C.sub.a), where sup(C.sub.a C.sub.b)=number of calls from NY to France on date 7/total number of calls in the week=95/2000=0.0475. Thus, conf(R1)=0.0475/0.09=0.53.

Typically, an optimized association rule problem requires an optimal instantiation for an association rule in the general form of UC.sub.1 .fwdarw.C.sub.2, where U represents a conjunction of m atomic conditions on m uninstantiated attributes, respectively, where m.gtoreq.1; and C.sub.1 and C.sub.2 represent conditions on instantiated attributes. Let U.sub.i represent an instantiation of U, which contains instantiated objects or values of the m respective uninstantiated attributes. Mathematically, U.sub.i can be mapped to a subspace in an m-dimensional space in which each uninstantiated attribute corresponds to one of the m dimensions, and the co-ordinates of the subspace are defined by the instantiated objects or values in U.sub.i. Two instantiations U.sub.i 's are said to be non-overlapping when the subspaces defined thereby do not intersect.

The aforementioned optimized association rule problem may further be framed as an optimized confidence problem or an optimized support problem. The optimized confidence problem is formulated as follows:

Given k.gtoreq.1 and an uninstantiated rule UC.sub.1 .fwdarw.C.sub.2, determine non-overlapping instantiations U.sub.1, . . . , U.sub.q of U with q.ltoreq.k such that sup().gtoreq.minSup and conf() is maximum, where represents the optimized confidence rule (U.sub.1 . . . U.sub.q)C.sub.1 .fwdarw.C.sub.2, and minSup represents a predetermined minimum support of the uninstantiated rule.

On the other hand, the optimized support problem is formulated as follows:

Given k.gtoreq.1 and an uninstantiated rule UC.sub.1 .fwdarw.C.sub.2, determine non-overlapping instantiations U.sub.1, . . . , U.sub.q of U with q.ltoreq.k such that conj().gtoreq.minConf and sup() is maximum, where represents the optimized support rule (U.sub.1 . . . U.sub.q)C.sub.1 .fwdarw.C.sub.2, and minConf represents a predetermined minimum confidence of the uninstantiated rule.

Continuing the above example, if periods having a heavy call volume from NY to France are of interest, the uninstantiated rule (date .di-elect cons.›x, y!)(src.sub.-- city=NY).fwdarw.(dst.sub.-- country=France) may be used, where the attribute "date" is uninstantiated, and x and y are variables respectively representing numeric values of the beginning and end dates of the period, which comprises a range of consecutive days. Thus, such an uninstantiated rule assumes the above general form, with U consisting of the uninstantiated attribute date .di-elect cons.›x, y!, C.sub.1 consisting of the instantiated condition src.sub.-- city=NY, and C.sub.2 consisting of the instantiated condition dst.sub.-- country=France. Assuming that minConf=0.5 and minSup=0.27 in this instance, and at most 2 instantiations of U, i.e., k=2, are of interest here, by instantiating the uninstantiated attribute with selected instantiations U.sub.1 and U.sub.2 to attain the maximum confidence, the following optimized confidence rule 1 results: ##EQU3## i.e., U.sub.1 =date .di-elect cons.›1, 1! and U.sub.2 =date .di-elect cons.›6, 7! in this instance.

U.sub.1 U.sub.2 satisfies 1 as sup(1)=the number of calls from NY during periods ›1, 1! and ›6, 7! is at least 2000 * 0.27=540, and conf(1)=the percentage of those calls to France is 46% which can be shown to be maximum with respect to any single or other pair of periods satisfying the support requirement.

In addition, by instantiating the uninstantiated attribute with selected instantiations U.sub.3 and U.sub.4 to attain the maximum support, the following optimized support rule 2 results: ##EQU4## i.e., U.sub.3 =date .di-elect cons. ›3, 4! and U.sub.4 =date .di-elect cons.›6, 7! in this instance.

U.sub.3 U.sub.4 satisfies 2 as conf(2)=the percentage of those calls from NY that are destined to France during periods ›3, 4! and ›6, 7! is at least 50%, and it can be shown that sup(2)=the number of calls from NY in those two periods is maximum with respect to any single or other pair of periods satisfying the confidence requirement.

Thus, the above optimized association rule problem requires instantiations U.sub.1, . . . , U.sub.q such that the optimized rule : (U.sub.1 . . . U.sub.q)C.sub.1 .fwdarw.C.sub.2 satisfies certain predetermined constraints, where =1 or 2. However, we have recognized a way of simplifying such a problem by defining an instantiated rule I.sub.i for each instantiation U.sub.i of U, where I.sub.i represents U.sub.i C.sub.1 .fwdarw.C.sub.2. In addition, let S be the set {I.sub.l. . . , I.sub.q }, and let sup(S) and conf(S) be defined as follows: ##EQU5## It can be shown that sup(S)=sup() and conf(S)=conf(). It should be pointed out at this juncture that since I.sub.i defines the corresponding U.sub.i based on their relation described above, and vice versa, I.sub.i hereinafter is conveniently referred to as an "instantiation" as well. With this new nomenclature, the term "non-overlapping instantiations" involving I.sub.i 's accordingly refers to those I.sub.i 's having non-overlapping U.sub.i 's corresponding thereto. Mindful of such new nomenclature, we can restate the above optimized confidence problem simply as follows:

Given k, and sup(I.sub.i) and conf(I.sub.i) for every instantiation I.sub.i, determine an optimized confidence set containing at most k non-overlapping instantiations such that sup(S).gtoreq.minSup and conf(S) is maximized.

Similarly, we can restate the above optimized support problem simply as follows:

Given k, and sup(I.sub.i) and conf(I.sub.i) for every instantiation I.sub.i, determine an optimized support set containing at most k non-overlapping instantiations such that conj(S).gtoreq.minConf and sup(S) is maximized.

The restatement of the optimized confidence and support problems sets the proper stage for the ensuing description of methodologies for effectively determining optimized support and confidence sets of instantiations in accordance with the invention. Those methodologies involving association rules containing uninstantiated categorical attributes A's formulated in an atomic condition A=p will now be described, where p as mentioned before is a variable representing an object or numeric value, as opposed to a range of numeric values ›u, v!. Thus, attribute date=j in the above example is one such categorical attribute. Due to the current restriction that an uninstantiated attribute is categorical, any two arbitrary instantiations for the attribute are always non-overlapping.

A traditional way of solving the optimized confidence and support problems where k instantiations for an uninstantiated attribute, e.g., multiple favorable promotional dates, are sought requires enumeration of all possible sets of 1 up to k instantiations for the attribute, from which the optimized sets are selected. Such resolution is impractical especially when a large amount of data needs to be considered.

In accordance with a pruning technique pursuant to the invention, a set denoted curSet is devised to contain instantiations which are current candidates for an optimized set of instantiations. In solving the optimized confidence problem for example, as soon as the confidence of any set satisfying minSup, which set is obtained by extending curSet, cannot exceed the confidence of the current optimized set, denoted optSet, the extension of curSet is immediately stopped. Otherwise, curSet is further extended, from which new optSet is derived. As curSet represents only a limited search space from which optSet is sought, the prior art requirement of exploring the entire search space by considering of all possible instantiations is obviated.

In order for the inventive pruning technique described below to be effective, it is desirable that a set close to the optimized set is identified as early as possible, which can then be used to eliminate a large number of sub-optimal sets. It may seem logical that in solving the optimized confidence problem, considering those instantiations with high confidences first may cause the search to converge on the optimized set rapidly. However, this may not be the case since the support of the optimized confidence set has to be at least minSup. For a large minimum support, it may be better to explore instantiations in decreasing order by support. Thus, the determination of the order in which instantiations are considered in a search is a non-trivial problem. In solving this problem, instantiation manipulator 107 in accordance with the invention assigns, to each possible instantiation I initially generated by processor 105 for the uninstantiated attribute, a weight w(I) which is defined as follows:

where w.sub.1 and w.sub.2 are real constants greater than zero. Thus, the weight of an instantiation w(I) is the weighted sum of the confidence and support of the instantiation. Manipulator 107 then arranges the weighted instantiations in an array denoted instArray in decreasing order by weight so that instantiations having higher weights are considered first in the search for the optimized set of instantiations. By varying the values of w.sub.1 and w.sub.2, the strategy for identifying curSet containing instantiations to be considered in the search can accordingly be varied. Manipulator 107 provides instArray to memory 110 for further processing by processor 105 in a manner to be described. In addition, parameters maxConf and maxSup are identified and stored in memory 110, which denote maximum confidence and maximum support of all the instantiations in instArray, respectively. Thus, in the above example where the uninstantiated attribute date=j is of interest, by referring to rows 209 and 211 in FIG. 2, maxConf=0.57 and maxSup=0.1.

For example, in identifying the optimized confidence set including at most k instantiations, the aforementioned curSet is only extended with a set (S+) of instantiations taken from instArray one by one starting from its i.sup.th instantiation (instArray›i!), where i=1, 2 . . . n; n denotes the total number of instantiations in instArray. The extension of curSet is stopped as soon as it is determined that S+ no longer satisfies (a) sup(curSet .orgate. S+).gtoreq.minSup, and (b) conf(curSet .orgate. S+).gtoreq.conf(optSet), where ".orgate." represents a standard set "UNION" operator.

Let s and c denote Sup(S+) and conf(S+), respectively, and h=k-the number of instantiations in curSet. Constraints on s that must be satisfied by any set S+ that can be used to extend curSet such that conditions (a) and (b) hold are defined as follows:

The requirement of condition (b) results in the following constraint: ##EQU6## which can be rewritten as: ##EQU7## In addition, curSet .orgate. S+ must satisfy the minimum support, and S+ is allowed to include at most h instantiations, thus resulting in the following two constraints:

and

Since the confidence of set S+ can be at most maxConf, i.e., c.ltoreq.maxConf. Combining this constraint with constraint ›I! results in the following constraint which, if satisfied by s, ensures that there exists a c that does not exceed maxConf and, at the same time, causes the confidence of curSet .orgate. S+ to be at least conf(optSet): ##EQU8## Because of the fact that the instantiations are sorted in decreasing order by weight and only instArray›i! and the instantiations following it in instArray are used to extend curSet, S+ contains only instantiations with weights at most w(insArray›i!). In addition, S+ can contain at most h instantiations as mentioned before. As a result, the following constraint on s and c emerges: ##EQU9## By rearranging the terms in constraint ›Va!, the following constraint is realized: ##EQU10## Since c, the confidence of S+, must be at least 0, substituting 0 for c in constraint ›Vb! results in the following constraint that prevents s from getting so large that c would have to become negative to satisfy the constraint. ##EQU11## Finally, constraints ›I! and ›Vb! can be combined to form the following constraint to limit s to values for which a corresponding value of c can be determined such that the confidence of curSet .orgate. S+ does not fall below conf(optSet), and the weight of the instantiations in S+ do not exceed w(instArray›i!): ##EQU12##

FIG. 3 illustrates routine 300 for extending curSet with instantiations in instArray subject to constraints ›II! through ›VII!. Routine 300 is stored in memory 110 and includes instructions for processor 105 to execute. Routine 300 including procedure optConfRange is illustrated using conventional code. In accordance with this procedure, only if there exists a value of s satisfying constraints ›II! through ›VII!, would curSet be extended. To that end, a range ›minS, maxS! is computed, in which s satisfies the above constraints, where minS and maxS represent the minimum value and the maximum value of s in that range, respectively. If there does not exist an s that satisfies constraints ›II!-›VII!, then a range for which minS>maxS, e.g., ›minS, maxS!=›1, 0! is returned for convenience. Thus, if the range ›minS, maxS!, with minS>maxS, is returned by procedure optConfRange, the extension of curSet is stopped.

Routine 300 takes as inputs curSet and index i for instArray›i! representing the instantiation being considered to extend curSet. The variable optSet is used to keep track of the optimized set of instantiations identified in routine 500 described below. Specifically, in step 301, if current optSet has the maximum possible confidence, curSet does not need to be extended. As such, ›minS, maxS!=›1, 0! is returned, as indicated in step 302. Otherwise, in steps 303-307, the range ›minS, maxS! in which s satisfies constraint ›VII! is computed. This computation involves solving a quadratic inequality in s in the form of A*s.sup.2 +B*s+C.ltoreq.0, where A=w.sub.2, B=(w.sub.1 * conf(optSet)-w(instArray›i!)) * h, and C=(conf(optSet)-conf(curSet)) * sup(curSet) * w.sub.1 * h. The ranges of values of s limited by ›0, 1! that satisfy A*s.sup.2 +B*s+C.ltoreq.0 based on different values of A, B and C are provided in FIG. 4, and are denoted range.sub.1 (A, B, C) and range.sub.2 (A, B, C) in columns 401 and 403, respectively. For most cases, only one range of values for s exists. However, for certain values of A, B, and C such as those listed in row 405, two distinct ranges from range.sub.1 (A, B, C) and range.sub.2 (A, B, C) are possible, although only the range from range.sub.1 (A, B, C) are used in routine 300. In addition, for some values of A, B and C such as those listed in rows 407 and 409, there does not exist an s that satisfies the quadratic inequality. In such cases, range.sub.1 (A, B, C) is assigned ›1, 0! for convenience. For cases in which the quadratic inequality is satisfied for all values of s, e.g., A=0, B=0 and C.ltoreq.0, range.sub.1 (A, B, C) is assigned ›0, 1!.

Referring back to FIG. 3, to meet constraints ›II! through ›IV! in addition to constraint ›VII!, minS in step 308 is set to the following: ##EQU13## where max(a1, a2, . . . ) is a standard function which selects the largest value of the arguments "a1," "a2,". . . .

Similarly, to further meet constraints ›II!, ›III! and ›VI!, maxS in step 309 is set to the following: ##EQU14## where min(b1, b2, . . . ) is a standard function which selects the smallest value of the arguments "b1," "b2,". . . .

FIG. 5 illustrates routine 500 for identifying the optimized confidence set of at most k instantiations, e.g., multiple favorable promotional dates including date=j.sub.1, date=j.sub.2, . . . up to date=j.sub.k. Routine 500 comprising procedure optConfPurneOpt is stored in memory 110, and includes instructions executable by processor 105. This procedure includes arguments curSet, and curLoc representing the index of the first instantiation in instArray to be considered for extending curSet. Initially, curSet=.phi. and curLoc=0. Specifically, in step 502, procedure optConfRange described above is invoked to determine whether curSet can be extended with any S+ including instantiations from instArray to yield the optimized confidence set. To that end, the range ›minS, maxS! returned by procedure optConfRange is checked by comparing minS with maxS. If minS>maxS, extension of curSet is stopped, as indicated in steps 503 and 504. In step 505, the extended set is stored as ES. The aforementioned variable optSet is used to keep track of the optimized set of instantiations encountered during the execution of routine 500. In steps 506 and 507, optSet is assigned with ES if the latter has a support at least equal to minSup, and a greater confidence than the current optimized set. In steps 508 and 509, procedure optConfPruneOpt enumerates all possible subsets of size k or less by recursively invoking itself, subject, however, to the condition set forth in steps 502-504 described above. After routine 500 is executed, optSet in this instance contains the optimized confidence set of up to k instantiations as required.

The above methodology for identifying the optimized confidence set is similarly applicable to obtaining the optimized support set. In identifying the optimized support set, constraints ›I!-›VII! on s remain the same except that conf(optSet) and minSup need to be replaced by minConf and sup(optSet), respectively. This stems from the requirement that the confidence of curSet .orgate. S+ be at least minConf and the support of curSet .orgate. S+ cannot be less than that of optSet. Thus, by replacing conf(optSet) and minSup with minConf and sup(optSet) respectively in all occurrences in procedures optConfRange and optConfPruneOpt described above, the corresponding procedures optSupRange and optSupPruneOpt applicable to the derivation of the optimized support set engender. Accordingly, procedure optSupRange is invoked in procedure optSupPruneOpt.

The above-described pruning technique relies on the current optimized set of instantiations to reduce the search space. A second pruning technique will now be described, whereby a list of intermediate sets of instantiations is maintained and pruned. In accordance with the invention, not only the current optimized set but also the intermediate sets are used for pruning the search space.

For example, in identifying the optimized confidence set of instantiations using a routine described below, the routine keeps track of (a) the current optimized set, and (b) intermediate sets each including a different subset of instantiations having the highest weight from instArray, where the subset is identified in the course of obtaining the current optimized set. We have recognized that these intermediate sets may be further extended with the remaining instantiations in instArray to potentially yield the optimized set. As such, the intermediate sets are each extended with the instantiation having the next highest weight in instArray, thereby generating new intermediate sets. If any of the new intermediate sets is better than the current optimized set, optSet is replaced thereby. In addition, since instantiations in instArray are stored in decreasing order by weight, procedure optConfRange in routine 300 can be used to eliminate those intermediate sets which are not destined to become the optimized set.

Consider two intermediate sets S.sub.1 and S.sub.2 for which numInst(S.sub.1).ltoreq.numInst(S.sub.2), and for each set S++ of instantiations selected to extend S.sub.2, sup(S.sub.1 .orgate. S++).gtoreq.minSup and conf(S.sub.1 .orgate. S++).gtoreq.conf(S.sub.2 .orgate. S++). Because of the assumption that numInst(S.sub.1).ltoreq.numInst(S.sub.2), S.sub.1 .orgate. S++ contains no more instantiations than S.sub.2 .orgate. S++. Since any two arbitrary instantiations are non-overlapping due to the consideration of only uninstantiated categorical attributes here, for some set S++ if S.sub.2 .orgate. S++ could become the optimized confidence set, S.sub.1 .orgate. S++ could become the optimized set as well. That is, deleting S.sub.2 from the list of intermediate sets does not affect result of the optimized confidence set identification process, and actually improves its efficiency.

Specifically, procedure optConfRange in routine 300 can be used to determine a first range of supports for an S++ which can be used to extend S.sub.2 to yield a set having a support equal to at least minSup and confidence as good as the current optimized set. Let s denote sup›S++!, c denote conf(›S++!, h=k-numInst(S.sub.2), and i be the index of the instantiation instArray›i! to be considered for extending the intermediate sets. Based on above constraints ›I! and ›Vb!, the following constraint on c emerges: ##EQU15##

Suppose a second range of supports can be determined for another S++ used to extend S.sub.1 to yield a set whose support is at least minSup, and for all values of c satisfying constraint ›VIII!, the confidence of S.sub.1 .orgate. S++ is at least that of S.sub.2 .orgate. S++. If the first range of supports is contained within the second range of supports, it follows from the above that each set S++ which can be used to extend S.sub.2 to yield an optimized set can also be used to extend S.sub.1 to yield a set having a support at least minSup and confidence at least that of S.sub.2 .orgate. S++. In that case, intermediate set S.sub.2 can be discarded in favor of S.sub.1 in accordance with the invention. In determining the second range of supports, the above requirement that the support of S.sub.1 .orgate. S++ be at least minSup translates to the following constraint on s:

In addition, the requirement that for all values of c satisfying constraint ›VIII!, conf(S.sub.1 .orgate. S++).gtoreq.conf(S.sub.2 .orgate. S++) translates to the following constraint on s for all such c values: ##EQU16## It can be shown that if sup(S.sub.1).ltoreq.sup(S.sub.2), then for a given value of s, constraint ›X! is satisfied for all values of c if it is satisfied with c=c.sub.min, where c.sub.min equals the inequality portion on the right of the first ".ltoreq." in constraint ›VIII!. Similarly, it can be shown that if sup(S.sub.1)>sup(S.sub.2), then for a given value of s, constraint ›X! is satisfied for all values of c if it is satisfied with c=c.sub.max, where c.sub.max equals the inequality portion on the left of the second ".ltoreq." in constraint ›VIII!. This being so, the above second range of supports for S++ includes those s values which satisfy constraint (IX) and, either constraint (X) with c=c.sub.min if sup(S.sub.1).ltoreq.sup(S.sub.2) or constraint (X) with c=c.sub.max otherwise.

FIG. 6 illustrates routine 600 including procedure optConfCanPrune for determining whether of intermediate sets S.sub.1 and S.sub.2 to be extended with instantiation instArray›i!, S.sub.2 can be pruned in favor of S.sub.1. This procedure returns "true" if S.sub.2 can indeed be pruned based on the analysis described above. Otherwise, it returns "false". For example, in step 603, as mentioned before procedure optConfRange in routine 300 is invoked to provide ›minS.sub.2, maxS.sub.2 ! representing the range of s for instArray›i! which may be used to extend S.sub.2, where minS.sub.2 and maxS.sub.2 respectively denote the minimum and maximum s values in that range. The determination of the range of s for instArray›i! which may be used to extend S.sub.1 subject to constraint ›X! requires solving two inequalities in the form of A*s.sup.2 +B*s+C.ltoreq.0, corresponding to sup(S.sub.1).ltoreq.sup(S.sub.2) with c=c.sub.min and sup(S.sub.1)>sup(S.sub.2) with c=c.sub.max, respectively. The values of A, B and C of the two inequalities are specified in steps 606-608 and steps 612-614, respectively. The range satisfying the inequalities having specific values of A, B and C is determined using the table in FIG. 4 described before. The range thus determined is stored as ›minS.sub.1, maxS.sub.1 ! in step 616, where minS.sub.1 and maxS.sub.1 respectively denote the minimum and maximum s values in that range. To additionally satisfy constraint ›IX!, minS.sub.1 in step 617 is set to the following:

If ›minS.sub.2, maxS.sub.2 ! is contained in ›minS.sub.1, maxS.sub.1 !, i.e., minS.sub.1 .ltoreq.minS.sub.2 and max S.sub.2 .ltoreq.maxS.sub.1, maxS.sub.2 can be pruned as discussed before, as indicated in steps 618 and 619.

Since when sup(S.sub.1)>sup(S.sub.2), the A, B and C values may satisfy the condition set forth in row 405 of FIG. 4, the range ›minS.sub.1, maxS.sub.1 ! may take on range.sub.2 (A, B, C) in addition to range.sub.1 (A, B, C). As such, steps 621-624 are repetitive of steps 616-619 for the case ›minS.sub.1, max S.sub.1 !=range.sub.2 (A, B, C).

FIG. 7 illustrates routine 700 comprising procedure optConfPruneInt for computing the optimized confidence set, taking advantage of the pruning of any intermediate sets in procedure optConfCanPrune just described. As shown in FIG. 7, procedure optConfPruneInt accepts as input parameters "intList" consisting of a list of intermediate sets for the first (curLoc-1) instantiations in instArray, and "curLoc" representing the index of the instantiation in instArray to be considered for extending the intermediate sets in intList. The procedure is initially invoked with intList=.phi. and curLoc=1, and it recursively invokes itself with successively increasing the value of curLoc.

Specifically, in steps 702-704, every set in intList is extended with instArray›curLoc! and a new list "newList" is formed to contain the extended set. If an extended set in newList is found in step 705 to have support at least minSup and higher confidence than that of the currently stored optimized set optSet, the latter is set to the extended set, as indicated in step 706. In steps 710-724, those intermediate sets that cannot be extended further to result in the optimized set are deleted from intList. Such intermediate sets include those sets already containing k instantiations plus those other sets for which above procedure optConfRange returns an empty range, i.e., minS>maxS. In addition, as discussed before, of any two intermediate sets S.sub.1 and S.sub.2 in intList that can be extended to potentially yield an optimized set, one can be pruned if calling of above procedure optConfCanPrune on S.sub.1 and S.sub.2 returns "true", as indicated in steps 714-721. In steps 725-727, an exit condition is instituted to terminate routine 700 early even though the value of curLoc may be smaller than n. The exit condition is met when there is no intermediate set to expand, i.e., intList=.phi., and the weight of instArray›curLoc+1! is less than minweight representing the minimum weight required to generate the optimized set, which is specified as follows in accordance with above constraint ›Va!: ##EQU17##

The above methodology for identifying the optimized confidence set based on the alternative intermediate set pruning technique is similarly applicable to obtaining the optimized support set. In an optimized support set problem where intermediate set S.sub.1 has fewer instantiations than S.sub.2, and each set S++ which can be used to extend S.sub.2 to yield an optimized set can also be used to extend S.sub.1 to yield a set having a confidence at least minSup and support at least that of S.sub.2 .orgate. S++, intermediate set S.sub.2 can be discarded in favor of S.sub.1 in accordance with the invention. To that end, a first range of supports for set S++ which can be used to extend S.sub.2 is similarly obtained using procedure optSupRange described above. In addition, the confidence of S++ is required to meet the following constraint, derived form constraint ›I! by replacing conf(optset) with minConf: ##EQU18## A second range of supports for S++ is computed such that sup(S.sub.1 .orgate. S++).gtoreq.sup(S.sub.2 .orgate. S++) and, for all c satisfying constraint ›XI!, conf(S.sub.1 .orgate. S++).gtoreq.minConf. If the first range of supports is contained within the second range of supports, S.sub.2 can be pruned as mentioned before. The second range of supports consists of all values of s which satisfy the following two constraints, wherein all values of c satisfying constraint ›XI!:

and ##EQU19## For a given s, constraint ›XIII! is satisfied for all c.gtoreq.c.sub.min if it is satisfied with c=c.sub.min, where c.sub.min equals the inequality portion on the right of ".gtoreq." in constraint ›XI!. As such, the second range of supports can be easily determined, which consists of all those s values satisfying constraints ›XII! and ›XIII!, with c=c.sub.min. Since based on the disclosure heretofore, a person skilled in the art is readily able to derive procedures optSupCanPrune and optSupPruneInt corresponding to above-described procedures optConfCanPrune and optConfPruneInt, respectively, the description of the former procedures is thus omitted here.

As mentioned before, the above inventive pruning techniques are applicable to solving the optimized association rule problems involving uninstantiated categorical attributes only. Determination of the optimized sets of instantiations for an association rule containing uninstantiated numeric attributes will now be described. A numeric attribute A in an association rule is one expressed in the form A .di-elect cons. ›u, v!, such as date .di-elect cons. ›x, y! in the above example. Thus, the numeric attribute needs to be instantiated with an interval or a range of values, as opposed to an object or a discrete value in the case of a categorical attribute. Mathematically, each instantiation for m numeric attributes in an association rule corresponds to a subspace in an m-dimensional space while each instantiation for m categorical attributes corresponds to a point in the m-dimensional space.

An optimized association rule problem involving uninstantiated numeric attributes is much more complex than its counterpart involving uninstantiated categorical attributes only. This principally stems from the fact that any two instantiations for a categorical attribute do not overlap as each instantiation corresponds to a point, while two instantiations for a numeric attribute may overlap as each instantiation here corresponds to a subspace. As a result, for example, the above intermediate set pruning technique is not applicable to the uninstantiated numeric attribute problem at hand.

In addition, the number of instantiations for numeric attributes to be considered in an optimized association rule problem increases significantly with the number of the attributes involved. To tackle this problem, instantiations are pre-screened by instantiation manipulator 107 in accordance with the invention before they are inducted into instArray. Without loss of generality, the determination of the optimized confidence set for two uninstantiated numeric attributes, e.g., two favorable promotional periods, utilizing the inventive pre-screening technique will now be described.

Each instantiation ›(x.sub.1, y.sub.1), (x.sub.2, y.sub.2)! for the two numeric attributes in question corresponds to a rectangle in a 2-dimensional space which is bounded by x.sub.1 and x.sub.2 on the x axis, and by y.sub.1 and y.sub.2 on the y axis. The size of the instantiation is defined to be the sum of the lengths of the rectangle along the two axes. Furthermore, these lengths are defined to be .vertline.x.sub.2 -x.sub.1 .vertline.+1 and .vertline.y.sub.2 -y.sub.1 .vertline.+1 along the x and y axes, respectively. Thus, for example, the size of an instantiation ›(1, 1), (3, 4)! is 7 as the rectangle defined thereby has a length of 3 along the x axis and a length of 4 along the y axis. It can be shown that an instantiation I.sub.1 =›(x.sub.1, y.sub.1), (x.sub.2, y.sub.2)! of size z can be pruned in favor of instantiations I.sub.2 having a size z-1 or less, provided that they are contained in I.sub.1 and have a support at least minSup and a confidence at least that of I.sub.1 's.

FIG. 8 illustrates routine 800 for inducting instantiations into instArray in accordance with the invention. Routine 800 comprising procedure pruneInstArray includes instructions executable by instantiation manipulator 107. Routine 800 is an iterative process wherein instantiations of increasing size are considered in successive iterations. During each iteration, maximum confidence values for instantiations of size z-1 determined during the previous iteration are used to prune the current enumerated instantiations of size z, and to determine the current maximum confidence.

The smallest and largest sizes of the instantiations to be pruned are 2 and n.sub.1 +n.sub.2, respectively, where n.sub.1 and n.sub.2 represent the upper bounds on x.sub.1 and y.sub.1, respectively. Thus, using the first for-loop in step 802 in FIG. 8, with size z varying from 2 to n.sub.1 +n.sub.2, instantiations of size z are generated for each point (x.sub.1, y.sub.1) serving as the lower coordinate of the instantiations.

The two for-loops in respective steps 803 and 804 determine the point (x.sub.1, y.sub.1) with which at least one instantiation of size z can be generated. Since the minimum values of x.sub.1 and y.sub.1 are 1, only values of 1 or higher for x.sub.1 and y.sub.1 are considered in those for-loops. If an instantiation having its lower x coordinate=x.sub.1 and a size z exists, the largest instantiation having its lower x coordinate between x=1 and x=x.sub.1, and a size at least z must exist. Thus, by requiring that the size of the largest instantiation ›(x.sub.1, 1), (n.sub.1, n.sub.2)! be at least z, the following condition results:

By rearranging the terms of the condition, the condition x.sub.1 .ltoreq.(n.sub.1 +n.sub.2)-z+1 comes into being. In addition, x.sub.1 can be at most n.sub.1. As a result, x.sub.1 can vary from 1 to min(n.sub.1, n.sub.1 +n.sub.2 +1-z), as indicated in the for-loop in step 803. Similarly, for a given x.sub.1, by requiring the size of the largest instantiation ›(x.sub.1, y.sub.1), (n.sub.1, n.sub.2)! to be at least z, the following condition on y.sub.1 results:

In addition, y.sub.1 can be at most n.sub.2. As a result, y.sub.1 can vary from 1 to min(n.sub.2, n.sub.1 +n.sub.2 +2-x.sub.1 -z), as indicated in the for-loop in step 804.

Once the values for x.sub.1 and y.sub.1 have been determined, values for x.sub.2 and y.sub.2 are enumerated such that the resulting instantiations are of size z. The lower and upper limits on x.sub.2 can be derived similarly to those for x.sub.1 and y.sub.1 described above, and are found to be max(x.sub.1, x.sub.1 +z-1(n.sub.2 -y.sub.1 +1)) and min(n.sub.1, x.sub.1 +z-2), respectively, as indicated in the for-loop in step 805. Once the values for x.sub.1 , y.sub.1 and x.sub.2 are identified, the value of y.sub.2 is determined to be y.sub.1 +z-1-(x.sub.2 -x.sub.1 +1) as indicated in the for-loop in step 806 such that the instantiation ›(x.sub.1, y.sub.1), (x.sub.2, y.sub.2)! is of size z.

If the support of the instantiation ›(x.sub.1, y.sub.1), (x.sub.2, y.sub.2)! of size z is determined to be less than minSup in step 813, the instantiation is added to instArray, as indicated in step 814. Otherwise, the instantiation ›(x.sub.1, y.sub.1), (x.sub.2, y.sub.2)! of size z is added to instArray only if its confidence is greater than that of each instantiation of size z-1 which has a support at least minSup and which is contained in the instantiation ›(x.sub.1, y.sub.1), (x.sub.2, y.sub.2)!. The instantiation of size z-1 is said to be contained in the instantiation ›(x.sub.1, y.sub.1), (x.sub.2, y.sub.2)! when the rectangle representing the former is within the rectangle representing the latter in the 2-dimensional space. In any event, there are only four instantiations of size z-1 which are contained in the instantiation ›(x.sub.1, y.sub.1), (x.sub.2, y.sub.2)!, namely, ›(x.sub.1, y.sub.1), (x.sub.2 -1, y.sub.2)!, ›(x.sub.1, y.sub.1), (x.sub.2, y.sub.2 -1, y.sub.1), (x.sub.2, y.sub.2)!, and ›(x.sub.1, y.sub.1 +1), (x.sub.2, y.sub.2)!. The variable maxConf››(x.sub.1, y.sub.1), (x.sub.2, y.sub.2)!! in step 812 is used to store the greatest of the confidences of any of these four instantiations whose support is at least minSup. Such confidences were generated in the previous iteration concerning instantiations of size z-1. Thus, for an instantiation ›(x.sub.1, y.sub.1), (x.sub.2, y.sub.2)! whose support is less than minSup, it is pruned and thus not inducted into instArray unless its confidence is greater than maxConf››(x.sub.1, y.sub.1), (x.sub.2, y.sub.2)!!, as indicated in steps 818 and 819. To ensure that only confidences of the instantiations of size z whose support is at least minSup are considered in the maxConf determination in the next iteration, maxConf››(x.sub.1, y.sub.1), (x.sub.2, y.sub.2)!! is set to conf(›(x.sub.1, y.sub.1), (x.sub.2, y.sub.2)!) if sup›(x.sub.1, y.sub.1), (x.sub.2, y.sub.2)! is at least minSup, as indicated in step 820. Otherwise, if sup›(x.sub.1, y.sub.1), (x.sub.2, y.sub.2)! is greater than minSup, maxConf››(x.sub.1, y.sub.1), (x.sub.2, y.sub.2)!! is set to zero, as indicated in step 815. After all the eligible instantiations are inducted into instArray, in step 824 each instantiation is assigned a weight in a manner described before. The weighted instantiations are then sorted in decreasing order by weight in step 825.

Procedure optConfPruneOpt in above routine 500 can be slightly modified to compute the required optimized confidence set based on instArray obtained from procedure pruneInstArray just described. Since the optimized set can contain only non-overlapping instantiations, curSet in routine 500 should not be extended with an overlapping instantiation from instArray. To that end, let's make up a function overlap(S, I) for a set of instantiations S and an instantiation I, which returns "true" if the rectangle representing some instantiation in S and the rectangle representing I overlap. Thus, the modified procedure optConfPruneOpt in question includes an inserted step "if overlap(curSet, instArray›i!)=false" between steps 501 and 502 in routine 500, with the body of this if-statement covering steps 502-507.

When association rules contain both uninstantiated categorical and numeric attributes, the modified procedure optConfPruneOpt for numeric attributes can still be used. Instantiations in instArray are obtained by instantiating each categorical attribute with an object or a numeric value in its domain while each numeric attribute is instantiated with an interval in its domain. Furthermore, for association rules containing, for example, two uninstantiated numeric attributes and an arbitrary number of uninstantiated categorical attributes, procedure pruneInstArray can still be used to induct instantiations into instArray. In that case, the set of instantiations is first partitioned such that each instantiation in a partition has the respective categorical attributes instantiated identically to every other instantiation in the partition. Procedure pruneInstArray is then applied to each partition, independent of the remaining partitions, and enumerates all the rectangles in the partition in increasing size which represent the instantiations of the numeric attributes only.

The foregoing merely illustrates the principles of the invention. It will thus be appreciated that a person skilled in the art will be able to devise numerous arrangements which, although not explicitly shown or described herein, embody the principles of the invention and are thus within its spirit and scope.

For example, data processing system 100 is disclosed herein in a form in which various system functions are performed by discrete functional blocks. However, any one or more of these functions could equally well be embodied in an arrangement in which the functions of any one or more of those blocks or indeed, all of the functions thereof, are realized, for example, by one or more appropriately programmed processors.