US5946683A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Technique for effectively instantiating attributes in association rules
Assignee: Nokia of America Corp
•
Filing: 1997-11-25
•
Granted: 1999-08-31
•
Expires: 2017-11-25
Abstract
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.
Inventors
- 👤 Rajeev Rastogi
- 👤 Kyuseok Shim
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 22:31
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99935; Y10S707/99936
Claims Analysis
Total Claims: 63
Claim 1
Independent Claim
73 words
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.
Claim 2
Independent Claim
73 words
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.
Claim 3
Dependent Claim
39 words
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.
Claim 4
Dependent Claim
39 words
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.
Claim 5
Dependent Claim
18 words
The system of claim 1 wherein the instantiations are positioned in the array in decreasing order by weight.
Claim 6
Dependent Claim
13 words
The system of claim 1 wherein the uninstantiated attribute comprises a categorical attribute.
Claim 7
Dependent Claim
62 words
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.
Claim 8
Dependent Claim
26 words
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.
Claim 9
Dependent Claim
26 words
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.
Claim 10
Dependent Claim
69 words
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.
Claim 11
Dependent Claim
32 words
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.
Claim 12
Dependent Claim
69 words
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.
Claim 13
Dependent Claim
32 words
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.
Claim 14
Dependent Claim
24 words
The system of claim 12 further comprising a data manipulator for assigning a weight to the second instantiation when the first instantiation is disregarded.
Claim 15
Dependent Claim
20 words
The system of claim 13 wherein the second instantiation is positioned in an array based on the weight assigned thereto.
Claim 16
Dependent Claim
12 words
The system of claim 1 wherein the processor includes the data manipulator.
Claim 17
Independent Claim
71 words
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.
Claim 18
Independent Claim
71 words
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.
Claim 19
Dependent Claim
83 words
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.
Claim 20
Dependent Claim
83 words
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.
Claim 21
Independent Claim
110 words
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.
Claim 22
Independent Claim
110 words
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.
Claim 23
Dependent Claim
13 words
The system of claim 18 wherein the uninstantiated attribute comprises a categorical attribute.
Claim 24
Dependent Claim
81 words
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.
Claim 25
Dependent Claim
32 words
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.
Claim 26
Dependent Claim
81 words
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.
Claim 27
Dependent Claim
32 words
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.
Claim 28
Independent Claim
146 words
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.
Claim 29
Independent Claim
146 words
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.
Claim 30
Dependent Claim
27 words
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.
Claim 31
Dependent Claim
18 words
The system of claim 24 wherein the at least one uninstantiated attribute comprises one or more categorical attributes.
Claim 32
Dependent Claim
28 words
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.
Claim 33
Dependent Claim
72 words
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.
Claim 34
Dependent Claim
30 words
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.
Claim 35
Independent Claim
71 words
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.
Claim 36
Independent Claim
71 words
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.
Claim 37
Dependent Claim
40 words
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.
Claim 38
Dependent Claim
40 words
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.
Claim 39
Dependent Claim
18 words
The method of claim 30 wherein the instantiations are positioned in the array in decreasing order by weight.
Claim 40
Dependent Claim
13 words
The method of claim 30 wherein the uninstantiated attribute comprises a categorical attribute.
Claim 41
Dependent Claim
60 words
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.
Claim 42
Dependent Claim
27 words
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.
Claim 43
Dependent Claim
27 words
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.
Claim 44
Dependent Claim
70 words
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.
Claim 45
Dependent Claim
36 words
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.
Claim 46
Dependent Claim
70 words
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.
Claim 47
Dependent Claim
33 words
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.
Claim 48
Independent Claim
109 words
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.
Claim 49
Independent Claim
109 words
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.
Claim 50
Dependent Claim
13 words
The method of claim 42 wherein the uninstantiated attribute comprises a categorical attribute.
Claim 51
Dependent Claim
83 words
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.
Claim 52
Dependent Claim
33 words
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.
Claim 53
Dependent Claim
82 words
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.
Claim 54
Dependent Claim
33 words
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.
Claim 55
Independent Claim
145 words
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.
Claim 56
Independent Claim
145 words
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.
Claim 57
Dependent Claim
27 words
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.
Claim 58
Dependent Claim
18 words
The method of claim 48 wherein the at least one uninstantiated attribute comprises one or more categorical attributes.
Claim 59
Dependent Claim
28 words
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.
Claim 60
Dependent Claim
73 words
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.
Claim 61
Dependent Claim
31 words
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.
Claim 62
Dependent Claim
23 words
The method of claim 48 further comprising the step of assigning a weight to the second instantiation when the first instantiation is disregarded.
Claim 63
Dependent Claim
20 words
The method of claim 54 wherein the second instantiation is positioned in an array based on the weight assigned thereto.
References Cited (Backward Citations)
US4674066A
Cited
EP0332427A2
Cited
US5197116A
Cited
US5321423A
Cited
US5341474A
Cited
US5832511A
Cited
US5481718A
Cited
US5664171A
Cited
US5694594A
Cited
US5819266A
Cited
US5842200A
Cited
US5794209A
Cited
US5778195A
Cited
US5812997A
Cited
US5724573A
Cited
US5727129A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-08-30 | 2003-03-01 | 2003-08-31 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-08-30 | 2007-03-01 | 2007-08-31 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-08-30 | 2011-03-01 | 2011-08-31 | $7700.00 | Window Closed / Lapsed |