Method for mining association rules in data

A method for mining an at least partially optimized association rule from a data set for every point of which support, confidence, and gain are available, said at least partially optimized association rule containing at least one uninstantiated condition A, comprising the steps of:

• providing the data set in a form usable by an electronic central processing unit;
• computing in the central processing unit via a dynamic programming algorithm a plurality k of separate regions of interest for particular application of the uninstantiated condition A having optimal gain, each region having at least a minimum confidence, each optimal region maxGainSet(i, j, l), where each interval(i, j) contains at most l non-overlapping intervals, satisfying the following theorem:
• For i < j, optSet(i, j, l) is [Circlesolid] l = 1:
• maxGainSet((i, j,), optSet(i, j-1, 1), optSet(i + 1, j, 1)). [Circlesolid] l > 1:
• maxGainSet((i, j), optSet((i, i, 1) ∪ optSet(i + 1, j, l-1), . . ., optSet (i, j-1, 1) ∪ optSet(i, j, l − 1)),
• the dynamic programming algorithm being:
• procedure optGain1 D(i, j, l) begin 1. if computed (optSet(i, j, l)) = true 2. return optSet(i, j, l) 3. if conf((i, j)) ≧ minConf { 4. optSet(i, j, l):
• = ((i, j)) 5. } 6. tmpSet := 0 7. if i < j { 8. if l = 1 9. tmpSet := maxGainSet(optGain1 D(i, j − 1, 1), optGain1 D(i + 1,j, 1)) 10. else 11. for r:= i to j − 1 do 12. tmpSet := maxGainSet(tempSet, optGain1 D(i, r, 1) ∪ optGain1 D(r + 1, j, l − 1) 13. } 14. optSet(i, j, l) := maxGainSet(optSet(i, j, l), tmpSet) 15. return optSet (i, j, l) end,
• where the algorithm is initially invoked with i=1, J=n, where n is the total number of values of the same type in the data set, k=1 (or other desired value of k), and recursion occurs on i and j for each value of k;
• and
• delivering from the electronic central processing unit to a utilization apparatus a signal useful for sales promotion representing each optSet(i, j, l) for said plurality k of separate regions.

A method for mining an at least partially optimized association rule from a data set of telephone usage for every point of which support, confidence, and gain are available, said at least partially optimized association rule containing at least two uninstantiated conditions A1 and A2, comprising the steps of:

• providing the data set in a form usable by an electronic central processing unit;
• computing in the central processing unit via a dynamic programming algorithm a plurality k of separate regions of interest for particular application of the each of the uninstantiated conditions A1 and A2 having at least approximately optimal support, each region having at least a minimum confidence, each at least approximately optimal region optSet2D((i, j), (p, q), k)), where each interval (i, j), (p, q) contains at most k non-overlapping intervals, providing an optimized set of binary space partitionable rectangles:
• the dynamic programming algorithm being:
• procedure optSup2D((i, j), (p, q), k) begin 1. if computed (optSet2D((i, j), (p, q), k)) = true 2. return optSet2D((i, j), (p, q), k) 3. if conf((i, j), (p, q)) ≧ minConf { 4. optSet2D((i, j), (p, q), k) :
• = ((i, j), (p, q)) 5. return optSet2D((i, j), (p, q), k) 6. } 7. optSet1 :
• = optSet2 :
• = 0 8. if p > i { 9. if k = 1 10. optSet1 := maxSupSet(optSup2D((i, j), (p − 1, q), 1), optSup2D((i + 1,j) (p, q), 1)) 11. else 12. for l := i to p − 1 do 13. for m = 1 to k − 1 do 14. optSet1 := maxSupSet(optSet1, optSup2D((i, j), (l, q), m) ∪ optSup2D((l + 1, j), (p, q), k − m) 15. } 16. if q > j { 17. if k = 1 18. optSet2 := maxSupSet(optSup2D((i, j), (p, q − 1), 1), optSup2D((i, j + 1), (p, q), 1)) 19. else 20. for l := j to q − 1 do 21. for m := 1 to k − 1 do 22. optSet2 := maxSupSet(optSet2, optSup2D((i, j), (p, l), m), ∪ optSup2D((i, l + 1), (p, q), k − m)) 23. } 24. optSet2D((i, j), (p, q), k) := maxSupSet(optSet2D((i, j), (p, q), k), optSet1, optSet2) 25. return optSet2D((i, j), (p, q), k) end
• where the algorithm is initially invoked with i=1, J=n, p=1, and q=n, where n is the total number of values of the same type in the data set, k=1 (or other desired value of k), and recursion occurs on i, j, p, and q for each value of k;
• and
• delivering from the electronic central processing unit to a utilization apparatus a listing for promoting telephoning as a signal representing each optSet2D((i, j), (p, q), k) for said plurality k of separate regions, each optSet2D((i, j), (p, q), k) being approximate if k>3.

A method for mining an at least partially optimized association rule from a data set of telephone usage for every point of which support, confidence, and gain are available, said at least partially optimized association rule containing at least two uninstantiated conditions A1 and A2, comprising the steps of:

• providing the data set in a form usable by an electronic central processing unit;
• computing in the central processing unit via a dynamic programming algorithm a plurality k of separate regions of interest for particular application of each of the uninstantiated conditions A1 and A2 having optimal gain, each region having at least a minimum confidence, each optimal region maxGainSet((i, j), (p, q), k)), where each interval (i, j), (p, q) contains at most k non-overlapping intervals, providing an optimized set of binary space partitionable rectangles:
• the dynamic programming algorithm being:
• procedure optGain2D((i, j), (p, q), k) begin 1. if computed (optSet2D((i, j), (p, q), k)) = true 2. return optSet2D((i, j), (p, q), k) 3. if conf((i, j), (p, q)) ≧ minConf { 4. optSet2D((i, j), (p, q), k) :
• = ((i, j), (p, q)) 5. } 6. optSet1 :
• = optSet2 :
• = 0 7. if p > i { 8. if k = 1 9. optSet1 := maxGainSet(optGain2D((i, j), (p − 1, q), 1), optGain2D((i + 1,j) (p, q), 1)) 10. else 11. for l := i to p − 1 do 12. for m = 1 to k − 1 do 13. optSet1 := maxGainSet(optSet1, optGain2D((i, j), (l, q), m) ∪ optGain2D((l + 1, j), (p, q), k − m) 14. } 15. if q > j { 16. if k = 1 17. optSet2 := maxGainSet(optGain2D((i, j), (p, q − 1), 1), optGain2D((i, j + 1), (p, q), 1)) 18. else 19. for l := j to q − 1 do 20. for m := 1 to k − 1 do 21. optSet2 := maxGainSet(optSet2, optGain2D((i, j), (p, l), m), ∪ optGain2D((i, l + 1), (p, q), k − m)) 22. } 23. optSet2D((i, j), (p, q), k) := maxGainSet(optSet2D((i, j), (p, q), k), optSet1, optSet2) 24. return optSet2D((i, j), (p, q), k) end,
• where the algorithm is initially invoked with i=1, J=n, p=1, and q=n, where n is the total number of values of the same type in the data set, k=1 (or other desired value of k), and recursion occurs on i, j, p, and q for each value of k;
• and
• delivering from the electronic central processing unit to a utilization apparatus a listing for promoting telephoning as a signal representing each optSet2D((i, j), (p, q), k) for said plurality k of separate regions, each optSet2D((i, j), (p, q), k) being approximate if k>3.