Technique for effectively instantiating attributes in association rules

• US 5,946,683 A
• Filed: 11/25/1997
• Issued: 08/31/1999
• Est. Priority Date: 11/25/1997
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Shim, Kyuseok, Rastogi, Rajeev
• Primary Examiner(s): Lintz, Paul R.
• Assistant Examiner(s): ALAM, SHAHID AL
• Application Number:
  US08/977,878
• Time in Patent Office: 644 Days
• Field of Search: 707/2, 707/6, 707/1, 707/3, 707/5, 705/10
• US Class Current: 1/1
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

In a data processing system, association rules are used to determine correlations of attributes of collected data, thereby extracting insightful information therefrom. In solving an optimized association rule problem where multiple instantiations for at least one uninstantiated attribute are required, unlike prior art, not all possible instantiations are considered to realize an optimized set of instantiations. Rather, using inventive pruning techniques, only selected instantiations need to be considered to realize same. In accordance with the invention, instantiations are assigned weights and are subject to pruning in an order dependent upon their weight. The weighted instantiations are tested based on selected criteria to identify, for example, those instantiations, consideration of which for the optimized set would be redundant in view of other instantiations to be considered. The identified instantiations are disregarded to increase the efficiency of determining the optimized set.

Claims

1. A system for processing data based on an association rule including at least one uninstantiated attribute of the data comprising:

a data manipulator for assigning weights to a plurality of instantiations for the uninstantiated attribute, each weight being assigned to a respective one of the plurality of instantiations, each instantiation being positioned in an array based on the weight assigned thereto; and

a processor for selecting a subset of instantiations in the array.

2. The system of claim 1 further comprising means for computing a confidence measure of each of the plurality of instantiations, wherein the weight assigned to the instantiation is a function of at least the confidence measure of the instantiation.

3. The system of claim 1 further comprising means for computing a support measure of each of the plurality of instantiations, wherein the weight assigned to the instantiation is a function of at least the support measure of the instantiation.

4. The system of claim 1 wherein the instantiations are positioned in the array in decreasing order by weight.

5. The system of claim 1 wherein the uninstantiated attribute comprises a categorical attribute.

6. The system of claim 1 further comprising means for maintaining a set of instantiations from the array, wherein the processor selects the subset of instantiations from the set of instantiations, the set of instantiations being extended to include at least one additional instantiation in the array based on at least one value which is a function of the selected subset of instantiations.

7. The system of claim 6 further comprising means for computing a confidence measure of the selected subset of instantiations, wherein the value includes the confidence measure.

8. The system of claim 6 further comprising means for computing a support measure of the selected subset of instantiations, wherein the value includes the support measure.

9. The system of claim 1 further comprising means for computing a confidence measure of a given subset of instantiations from the array, wherein the number of the instantiations in the selected subset is at most k, where k is greater than zero, the selected subset of instantiations having a relatively high confidence measure with respect to that of any other subset having at most k instantiations from the array.

10. The system of claim 9 further comprising means for computing a support measure of the selected subset of instantiations, wherein the support measure is at least a predetermined value greater than zero.

11. The system of claim 1 further comprising means for computing a support measure of a given subset of instantiations from the array, wherein the number of the instantiations in the selected subset is at most k, where k is greater than zero, the selected subset of instantiations having a relatively high support measure with respect to that of any other subset having at most k instantiations from the array.

12. The system of claim 11 further comprising means for computing a confidence measure of the selected subset of instantiations, wherein the confidence measure is at least a predetermined value greater than zero.

13. The system of claim 12 further comprising a data manipulator for assigning a weight to the second instantiation when the first instantiation is disregarded.

14. The system of claim 13 wherein the second instantiation is positioned in an array based on the weight assigned thereto.

15. The system of claim 1 wherein the processor includes the data manipulator.

16. A system for processing data based on an association rule including at least one uninstantiated attribute of the data comprising:

means for assigning weights to a plurality of instantiations for the uninstantiated attribute, each weight being assigned to a respective one of the plurality of instantiations;

means for positioning each instantiation in an array based on the weight assigned thereto; and

means for selecting a subset of instantiations in the array.

17. Software including machine readable instructions stored in a tangible medium for performing a process for processing data based on an association rule which includes at least one uninstantiated attribute of the data, the process comprising the steps of:

assigning weights to a plurality of instantiations for the uninstantiated attribute, each weight being assigned to a respective one of the plurality of instantiations;

positioning each instantiation in an array based on the weight assigned thereto; and

selecting a subset of instantiations in the array.

18. A system for processing data based on an association rule including at least one uninstantiated attribute of the data, a set of instantiations being selected for the uninstantiated attribute based on the data, comprising:

a mechanism for deriving from the data at least a first intermediate set and a second different intermediate set of instantiations for the uninstantiated attribute, the number of instantiations in the second intermediate set being at least the number of instantiations in the first intermediate set; and

a processor for determining whether to disregard the second intermediate set, the first intermediate set being a candidate for the selected set when the second intermediate set is disregarded.

19. The system of claim 18 wherein the uninstantiated attribute comprises a categorical attribute.

20. The system of claim 18 further comprising means for computing a confidence measure of a given set of instantiations, wherein the selected set of instantiations is required to have a confidence measure at least as high as that of the first intermediate set and that of the second intermediate set, the processor determining to disregard the second intermediate set based on at least whether the confidence measure of the first intermediate set is at least that of the second intermediate set.

21. The system of claim 20 further comprising means for computing a support measure of the selected set of instantiations, wherein the support measure is at least a predetermined value greater than zero.

22. The system of claim 18 further comprising means for computing a support measure of a given set of instantiations, wherein the selected set of instantiations is required to have a support measure at least as high as that of the first intermediate set and that of the second intermediate set, the processor determining to disregard the second intermediate set based on at least whether the support measure of the first intermediate set is at least that of the second intermediate set.

23. The system of claim 22 further comprising means for computing a confidence measure of the selected set of instantiations, wherein the confidence measure is at least a predetermined value greater than zero.

24. A system for processing data based on an association rule including at least one uninstantiated attribute of the data, an instantiation being selected for the at least one uninstantiated attribute based on the data, comprising:

a mechanism for determining a size of subspace defined by an instantiation for the at least one uninstantiated attribute, the subspace being disposed in an m-dimensional space, where m is not greater than the number of the at least one uninstantiated attribute, the size of a first subspace defined by a first instantiation for the at least one uninstantiated attribute being determined to be larger than the size of a second subspace defined by a second instantiation for the at least one uninstantiated attribute; and

a processor for determining whether to disregard the first instantiation, the second instantiation being a candidate for the selected instantiation when the first instantiation is disregarded.

25. The system of claim 24 wherein the at least one uninstantiated attribute comprises one or more numeric attributes, and m equals the number of the numeric attributes.

26. The system of claim 24 wherein the at least one uninstantiated attribute comprises one or more categorical attributes.

27. The system of claim 24 wherein the processor determines to disregard the first instantiation based on at least whether the second subspace is contained in the first subspace.

28. The system of claim 24 further comprising means for computing a confidence measure of a given instantiation, wherein the selected instantiation is required to have a confidence measure at least as high as that of the first instantiation and that of the second instantiation, the processor determining to disregard the first instantiation based on at least whether the confidence measure of the second instantiation is at least that of the first instantiation.

29. The system of claim 28 further comprising means for computing a support measure of the second instantiation, wherein the support measure is at least a predetermined value greater than zero.

30. A method for processing data based on an association rule including at least one uninstantiated attribute of the data, the method comprising the steps of:

assigning weights to a plurality of instantiations for the uninstantiated attribute, each weight being assigned to a respective one of the plurality of instantiations, each instantiation being positioned in an array based on the weight assigned thereto; and

selecting a subset of instantiations in the array.

31. The method of claim 30 further comprising the step of computing a confidence measure of each of the plurality of instantiations, wherein the weight assigned to the instantiation is a function of at least the confidence measure of the instantiation.

32. The method of claim 30 further comprising the step of computing a support measure of each of the plurality of instantiations, wherein the weight assigned to the instantiation is a function of at least the support measure of the instantiation.

33. The method of claim 30 wherein the instantiations are positioned in the array in decreasing order by weight.

34. The method of claim 30 wherein the uninstantiated attribute comprises a categorical attribute.

35. The method of claim 30 further comprising the step of maintaining a set of instantiations from the array, wherein the subset of instantiations is selected from the set of instantiations, the set being extended to include at least one additional instantiation in the array based on at least one value which is a function of the selected subset of instantiations.

36. The method of claim 35 further comprising the step of computing a confidence measure of the selected subset of instantiations, wherein the value includes the confidence measure.

37. The method of claim 35 further comprising the step of computing a support measure of the selected subset of instantiations, wherein the value includes the support measure.

38. The method of claim 30 further comprising the step of computing a confidence measure of a given subset of instantiations from the array, wherein the number of the instantiations in the selected subset is at most k, where k is greater than zero, the selected subset of instantiations having a relatively high confidence measure with respect to that of any other subset having at most k instantiations from the array.

39. The method of claim 38 further comprising the step of computing a support measure of the selected subset of instantiations from the array, wherein the support measure is at least a predetermined value greater than zero.

40. The method of claim 30 further comprising the step of computing a support measure of a given subset of instantiations from the array, wherein the number of the instantiations in the selected subset is at most k, where k is greater than zero, the selected subset of instantiations having a relatively high support measure with respect to that of any other subset having at most k instantiations from the array.

41. The method of claim 40 further comprising the step of computing a confidence measure of the selected subset of instantiations, wherein the confidence measure is at least a predetermined value greater than zero.

42. A method for processing data based on an association rule including at least one uninstantiated attribute of the data, a set of instantiations being selected for the uninstantiated attribute based on the data, the method comprising the steps of:

deriving from the data at least a first intermediate set and a second different intermediate set of instantiations for the uninstantiated attribute, the number of instantiations in the second intermediate set being at least the number of instantiations in the first intermediate set; and

determining whether to disregard the second intermediate set, the first intermediate set being a candidate for the selected set when the second intermediate set is disregarded.

43. The method of claim 42 wherein the uninstantiated attribute comprises a categorical attribute.

44. The method of claim 42 further comprising the step of computing a confidence measure of a given set of instantiations, wherein the s elected set of instantiations is required to have a confidence measure at least as high as that of the first intermediate set and that of the second intermediate set, a determination to disregard the second intermediate set being based on at least whether the confidence measure of the first intermediate set is at least that of the second intermediate set.

45. The method of claim 44 further comprising the step of computing a support measure of the selected set of instantiations, wherein the support measure is at least a predetermined value greater than zero.

46. The method of claim 42 further comprising the step of computing a support measure of a given set of instantiations, wherein the selected set of instantiations is required to have a support measure at least as high as that of the first intermediate set and that of the second intermediate set, a determination to disregard the second intermediate set being based on at least whether the support measure of the first intermediate set is at least that of the second intermediate set.

47. The method of claim 46 further comprising the step of computing a confidence measure of the selected set of instantiations, wherein the confidence measure is at least a predetermined value greater than zero.

48. A method for processing data based on an association rule including at least one uninstantiated attribute of the data, an instantiation being selected for the at least one uninstantiated attribute based on the data, the method comprising the steps of:

determining a size of subspace defined by an instantiation for the at least one uninstantiated attribute, the subspace being disposed in an m-dimensional space, where m is not greater than the number of the at least one uninstantiated attribute, the size of a first subspace defined by a first instantiation for the at least one uninstantiated attribute being determined to be larger than the size of a second subspace defined by a second instantiation for the at least one uninstantiated attribute; and

determining whether to disregard the first instantiation, the second instantiation being a candidate for the selected instantiation when the first instantiation is disregarded.

49. The method of claim 48 wherein the at least one uninstantiated attribute comprises one or more numeric attributes, and m equals the number of the numeric attributes.

50. The method of claim 48 wherein the at least one uninstantiated attribute comprises one or more categorical attributes.

51. The method of claim 48 wherein a determination to disregard the first instantiation is based on at least whether the second subspace is contained in the first subspace.

52. The method of claim 48 further comprising the step of computing a confidence measure of a given instantiation, wherein the selected instantiation is required to have a confidence measure at least as high as that of the first instantiation and that of the second instantiation, a determination to disregard the first instantiation being based on at least whether the confidence measure of the second instantiation is at least that of the first instantiation.

53. The method of claim 52 further comprising the step of computing a support measure of the second instantiation, wherein the support measure is at least a predetermined value greater than zero.

54. The method of claim 48 further comprising the step of assigning a weight to the second instantiation when the first instantiation is disregarded.

55. The method of claim 54 wherein the second instantiation is positioned in an array based on the weight assigned thereto.