Method and apparatus for deriving an association rule between data

• US 5,812,997 A
• Filed: 10/25/1996
• Issued: 09/22/1998
• Est. Priority Date: 10/26/1995
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Incorporated (International Business Machines Corporation)
• Inventors: Fukuda, Takeshi, Tokuyama, Takeshi, Morishita, Shinichi, Morimoto, Yasuhiko
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Choules, Jack M.
• Application Number:
  US08/735,911
• Time in Patent Office: 697 Days
• Field of Search: 707/2, 707/3, 707/4, 707/5, 707/6, 705/10
• US Class Current: 1/1
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 2216/03 Data mining
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

A method is described for finding correlation between a plurality of data having two kinds of numerical attributes and a true-false attribute. The method comprises the steps of: constituting a plane with two numerical attributes, dividing the plane into meshes, and counting the number of data in each mesh (also called a "bucket") and the number of data whose true-false attribute represents true. If each mesh is assumed to be a pixel, such plane can be considered as a plane image in which the number of data corresponds to brilliance, and the number of data whose true-false attribute represents true corresponds to saturation. The method further includes the step of segmenting an admissible image which is convex along an axis of the plane according to a predetermined condition θ to find an area with strong correlation. If the segmented area as the admissible image satisfies the above-described condition such as the maximized support rule, the method also presents the area to the user. In addition, necessary attributes for data included in the area are also extracted from a database, as required.

Claims

1. A method for deriving an association rule between a plurality of data in a database, each said data including at least two kinds of numerical attributes and one kind of true-false attribute, comprising the steps of:

constituting a plane, said plane having two axes corresponding to said two kinds of numerical attributes, divided into N×

M buckets, and storing a number u(i, j) of data included in each bucket (i, j) and a number v(i, j) of data whose true-false attribute represents true in each bucket;

inputting a condition θ

;

segmenting an area S from the plane, wherein the buckets included in said area S maximize ##EQU23## outputting data included in said segmented area S.

2. The method for deriving an association rule as set forth in claim 1, further comprising the steps of:

inputting a second condition θ

₂ different from said condition θ

;

segmenting a second area S₂ from said plane, wherein the buckets included in said area S₂ maximize ##EQU24## segmenting a third area S₃ from said plane, wherein the buckets included in said area S₃ maximize ##EQU25## with a third condition ##EQU26## where V(S₂) is the number of data included in said area S₂ and whose true-false attribute represents true, V(S) is the number of data included in said area S and whose true-false attribute represents true, U(S₂) is the number of data included in said area S₂, and U(S) is the number of data included in said area S.

3. The method for deriving an association rule as set forth in claim 1, further comprising the steps of:

modifying v(i, j) such that v(i, j)/u(i, j) in each bucket in said segmented area S becomes equal to the ratio of the number of data whose true-false attribute represents true in the whole plane to the number of data in the whole plane; and

segmenting a fourth area S₄, wherein buckets included in said area S₄ maximize ##EQU27## by using said modified v(i, j) according to a condition θ

₄ which is input.

4. The method for deriving an association rule as set forth in claim 1, wherein said plane constituting step comprises the steps of:

randomly sampling X data from said plurality of data;

sorting the sampled data for each of said numerical attributes and storing a value corresponding to the (X*i/N)-th data where i=1, 2, . . . N, and a value corresponding to the (X*n/M)-th data, where n=1, 2, . . . M; and

placing said plurality of data into said N×

M buckets based on said stored values.

5. The method for deriving an association rule as set forth in claim 1, wherein

g(i, j)=v(i, j)-θ

u(i, j) is used as an evaluation value; and

said area segmenting step comprises the steps of;

a) deriving a range in each column in said plane, wherein said range includes at least one bucket and an evaluation value of said range is maximized;

b) when an addition region is defined as a region which includes an area having a first bucket (m-1, l) in a previous column of a second bucket (m, t) in said plane and having a maximum evaluation value up to the previous column and a range, derived by said range deriving step, including said second bucket (m, t) and a third bucket (m, l) on the same row as said first bucket and on the same column as said second bucket and having a maximum evaluation value on the column of the second and third buckets, for each of said second buckets;

i) detecting one of the first buckets whose inclusion with the second bucket in the addition region makes an evaluation value of the addition region maximum, and

ii) storing said evaluation value of said addition region and said one of the first buckets; and

c) detecting one of said second buckets included in said addition region which has a maximum evaluation value on said whole plane, and deriving said area S by using said first bucket detected in said detecting and storing step for said detected one of said second buckets.

6. The method for deriving an association rule as set forth in claim 1, further comprising the steps of:

inputting the minimum support number U_min, wherein U_min is the minimum number of data included in the area to be segmented;

comparing the number of data U(S) included in said segmented area S with the minimum support number U_min ;

if said comparison indicates U_min =U(S), then outputting said area S as the area to be segmented; and

,

if said comparison indicates U_min >

U(S) or U_min <

U(S), then performing said area segmenting step under a new condition θ

₅.

7. The method for deriving an association rule as set forth in claim 1, further comprising the steps of:

inputting minconf, which is the ratio of said number of data whose true-false attribute represents true in the area to be segmented to the number of data in the area to be segmented;

if minconf=V(S)/U(S) for said segmented area S, where U(S) is the number of data included in said area S, V(S) is the number of data included in said area S and whose true-false attribute represents true in the area, then outputting said area S; and

,

if minconf<

V(S)/U(S) or minconf>

V(S)/U(S), then performing said area segmenting step under a new condition θ

₆.

8. The method for deriving an association rule as set forth in claim 1, further comprising the steps of:

for said segmented area S, calculating an entropy by ##EQU28## where U_sum is the number of data over said entire plane, and V_sum is the number of data included in said entire plane whose true-false attribute represents true, and storing the entropy value in correspondence to said area S;

performing said area segmenting step and said entropy calculating step with a modified condition θ

; and

outputting an area S which makes f (U(S), V(S)) maximized.

9. The method for deriving an association rule as set forth in claim 1, further comprising the steps of:

for said segmented area S, calculating an interclass variance by ##EQU29## where U_sum is the number of data over said entire plane, and V_sum is the number of data included in said entire plane whose true-false attribute represents true, and storing the interclass variance value in correspondence to said area S;

performing said area segmenting step and said interclass variance calculating step with a modified the condition θ

; and

outputting an area S which makes f (U(S), V(S)) maximized.

10. An apparatus for deriving an association rule between a plurality of data in a database, each said data including at least two kinds of numerical attributes and one kind of true-false attribute, comprising:

means for constituting a plane, said plane having two axes corresponding to said two kinds of numerical attributes, divided into N×

M buckets, and storing a number u(i, j) of data included in each bucket (i, j) and a number v(i, j) of data whose true-false attribute represents true in each bucket;

means for inputting a condition θ

;

means for segmenting an area S from the plane, wherein the buckets included in said area S maximize ##EQU30## means for outputting data included in said segmented area S.

11. The apparatus for deriving an association rule as set forth in claim 10, wherein said input means inputs a second condition θ

₂ different from said condition θ

, said area segmenting means segments a second area S₂ corresponding to said second condition θ

₂ from said plane, and the apparatus further comprises;

means for outputting to said area segmenting means ##EQU31## as a third condition, where V(S₂) is the number of data included in said area S₂ and whose true-false attribute represents true, V(S) is the number of data included in said area S and whose true-false attribute represents true, U(S₂) is the number of data included in said area S₂, and U(S) is the number of data included in said area S.

12. The apparatus for deriving an association rule as set forth in claim 10, further comprising:

means for modifying v(i,j) such that v(i,j)/u(i,j) in each bucket in said segmented area S becomes equal to the ratio of the number of data whose true-false attribute represents true in the whole plane to the number of data in the whole plane; and

means for directing said area segmenting means to operate under said modified v(i,j) and an input condition θ

₄.

13. The apparatus for deriving an association rule as set forth in claim 10, wherein said plane constituting means comprises:

means for randomly sampling X data from said plurality of data;

means for sorting the sampled data for each of said numerical attributes and storing a value corresponding to the (X*i/N)-th data, where i=1, 2, . . . N, and a value corresponding to the (X*n/M)-th data, where n=1, 2, . . . M; and

means for placing said plurality of data into said N×

M buckets based on said stored values.

14. The apparatus for deriving an association rule as set forth in claim 10, wherein

15. The apparatus for deriving an association rule as set forth in claim 10, further comprising:

means for inputting the minimum support number U_min, wherein U_min is the minimum number of data included in the area to be segmented;

means for comparing the number of data U(S) included in said segmented area S with the minimum support number U_min ;

if said comparison indicates U_min =U(S), then means for outputting said area S as the area to be segmented; and

,

if said comparison indicates U_min >

U(S) or U_min <

U(S), then means for directing said area segmenting means to operate under a new condition θ

₅.

16. The apparatus for deriving an association rule as set forth in claim 10, further comprising:

means for inputting minconf, which is the ratio of said number of data whose true-false attribute represents true in the area to be segmented to the number of data in the area to be segmented;

if minconf=V(S)/U(S) for said segmented area S, where U(S) is the number of data included in said area S, V(S) is the number of data included in said area S and whose true-false attribute represents true, then means for outputting said area S; and

,

if minconf<

V(S)/U(S) or minconf>

V(S)/U(S), then means for directing said area segmenting means to operate under a new condition θ

₈.

17. The apparatus for deriving an association rule as set forth in claim 10, further comprising:

means, for said segmented area S, for calculating an entropy by ##EQU32## where U_sum is the number of data over said entire plane, and V_sum is the number of data included in said entire plane whose true-false attribute represents true, and for storing the entropy value in correspondence to said area S;

means for directing said area segmenting means and said entropy calculating means to operate with a modified condition θ

; and

means for outputting an area S which makes f (U(S), V(S)), stored in said entropy calculating means, maximized.

18. The apparatus for deriving an association rule as set forth in claim 10, further comprising:

means, for said segment area S, for calculating an interclass variance by ##EQU33## where U_sum is the number of data over said entire plane, and V_sum is the number of data included in said entire plane whose true-false attribute represents true, and for storing the interclass variance value in correspondence to said area S;

means for directing said area segmenting means and said interclass variance calculating means to operate with a modified condition θ

;

outputting an area S which makes f (U(S), V(S)), stored in said interclass variance calculation means, maximized.

19. A storage device comprising program code means for causing a computer to derive an association rule between a plurality of data in a database, each said data including at least two kinds of numerical attributes and one kind of true-false attribute, said program code means comprising:

plane constituting program code means, said plane having two axes corresponding to said two kinds of numerical attributes, and divided into N×

M buckets, said plane constituting program code means causing the computer to store a number u(i, j) of data included in each bucket (i, j) and a number v(i, j) of data whose true-false attribute represents true in each bucket;

input program code means for causing the computer to input a condition θ

;

area segmentation program code means for causing the computer to segment an area S from the plane, wherein the buckets included in said area S maximize ##EQU34##

20. The storage device as set forth in claim 19, wherein said input program code means inputs a second condition θ

₂ different from said condition θ

, said area segmenting program code means segments a second area S₂ corresponding to said second condition θ

₂ from said plane, and said storage device further comprises;

program code means for outputting to said area segmenting program code means, ##EQU35## as a third condition, where V(S₂) is the number of data included in said area S₂ and whose true-false attribute represents true, V(S) is the number of data included in said area S and whose true-false attribute represents true, U(S₂) is the number of data included in said area S₂, and U(S) is the number of data included in said area S.

21. The storage device as set forth in claim 19, further comprising:

program code means for causing the computer to modify v(i, j) such that v(i, j)/u(i, j) in each bucket in said segmented area S becomes equal to the ratio of the number of data whose true-false attribute represents true in the whole plane to the number of data in the whole plane; and

program code means for directing the computer and said area segmenting program code means to operate under said modified v(i, j) and an input condition θ

₄.

22. The storage device as set forth in any one of claims 19, wherein said plane constituting program code means comprises:

program code means for causing the computer to randomly sample X data from said plurality of data;

program code means for causing the computer to sort the sampled data for each of said numerical attributes and storing a value corresponding to the (X*i/N)-th data, where i=1, 2, . . . N, and a value corresponding to the (X*n/M)-th data, where n=1, 2, . . . M; and

program code means for causing the computer to place said plurality of data into said N×

M buckets based on said stored values.

23. The storage device as set forth in claim 19, wherein

g (i, j)=v (i, j)-θ

u (i, j) is used as an evaluation value; and

said area segmenting program code means comprises;

a) range deriving program code means for causing the computer to derive a range in each column in said plane, wherein a range includes at least one bucket and the evaluation value of said range is maximized;

b) detecting and storing program code means, when an addition region is defined as a region which includes an area having a first bucket (m-1, l) in a previous column of a second bucket (m, t) in said plane and having a maximum evaluation value up to the previous column and a range, derived by said range deriving program means and the computer, including said second bucket (m, t) and a third bucket (m, l) in the same row as said first bucket and in the same column as said second bucket and having a maximum evaluation value in the column of the second and third buckets, for each of the second buckets, for causing the computer i) to detect one of the first buckets whose inclusion with the one second bucket in the addition region makes the evaluation value of the addition region maximum, and ii) to store said evaluation value of said addition region and said one of the first buckets; and

c) program code means for causing the computer to detect one of said second bucket included in said addition region which has a maximum evaluation value in said whole plane, and to derive an area S by using said first bucket detected in said detecting and storing program code means for said detected one of said second bucket.