System and method of using clustering to find personalized associations

• US 6,408,295 B1
• Filed: 06/16/1999
• Issued: 06/18/2002
• Est. Priority Date: 06/16/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Aggarwal, Charu C., Yu, Philip Shi-lung
• Primary Examiner(s): Mizrahi, Diane D.
• Application Number:
  US09/334,764
• Time in Patent Office: 1,098 Days
• Field of Search: 707/2, 707/3, 707/6, 707/7, 706/47
• US Class Current: 707/694
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A system and method for developing association rules which are personalized for a customer. The method includes partitioning (clustering) a set of records corresponding to transactions of items into discrete segments so that different parts of the data show different kinds of trends. The clustering is used in order to create a segmentation of the data such that these trends are captured in each segment. Consequently, a different set of association rules are relevant for each segment. For a given customer, the segment to which he/she belongs most closely may be readily determined, and the trends in that segment may be used for generating the association rules.

Claims

1. A system for generating personalized associations of items organized as a plurality of transactions, each transaction comprising itemnsets having one or more items capable of forming said associations, said system comprising:

(a) means for clustering itemsets from said plurality of transactions according to a user-specified number of cluster segments and a minimum density of each itemset in the segment;

(b) means for receiving requests for a given customer, a request including a customer'"'"'s buying patter; and

,

(c) means for generating personalized association rules in accordance with a received request, said personalized association rules generated from the cluster segment having items most relevant to the customer buying pattern provided in the received request.

2. The system according to claim 1, wherein said clustering means includes a computing device for implementing a partitioning algorithm, said algorithm invoking an iterative process for determining the different segments.

3. The system according to claim 2, wherein the generating means includes means for finding a centroid of a cluster segment that most closely matches a customer buying pattern, said generating means generating the itemsets and association rules which are most specific to this segment.

4. The system according to claim 3, wherein said iterative process consists of determining an initial set of seeds, each seed comprising a randomly selected transaction around which a cluster is to be built, determining similarity of a transaction to a seed and assigning a transaction to a most closely matched seed, and iteratively refining sets of seeds for building said cluster segments.

5. The system according to claim 4, wherein the process of refining sets of seed includes projecting out the least frequent items from the seed.

6. The system according to claim 5, wherein a number of the least frequent items to be projected from a seed is a function of the iteration.

7. The system according to claim 4, wherein said clustering means further imposes a minimum mass requirement for retaining cluster segments, and discarding all those cluster segments which do not satisfy said minimum mass requirement.

8. The system according to claim 4, wherein the itemsets in each segment are used in order to determine a centroid of that segment and refine the seeds in an iterative process.

9. The system according to claim 1, wherein said received request includes a specified support and confidence measure, said personalized association rules generated in accordance with said specified support and confidence measure.

10. A method for generating personalized associations of items organized as a plurality of transactions, each transaction comprising itemsets having one or more items capable of forming said associations, said method comprising:

(a) clustering itemsets from said plurality of transactions according to a users specified number of cluster segments and a minimum density of each itemset in the segment;

(b) receiving requests for a given customer, a request including a customer'"'"'s buying pattern; and

,

(c) generating personalized association rules in accordance with said received request said personalized association rules generated from the cluster segment having items most relevant to the customer buying pattern provided in the received request.

11. The method according to claim 10, wherein said clustering step includes implementing an iterative process for determining the different segments.

12. The method according to claim 11, wherein the generating step includes finding a centroid of a cluster segment that most closely matches a customer buying pattern, and generating the itemsets and association rules which are most specific to this segment.

13. The method according to claim 12, wherein said iterative process comprises steps of:

determining an initial set of seeds, each seed comprising a randomly selected transaction around which a cluster is to be built,

determining similarity of a transaction to a seed;

assigning a transaction to a most closely matched seed; and

iteratively refining sets of seeds for building said cluster segments.

14. The method according to claim 13, wherein said refining step includes the step of projecting out the least frequent items from the seed.

15. The method according to claim 14, wherein a number of the least frequent items to be projected from a seed is a function of the iteration.

16. The method according to claim 13, wherein said clustering step includes retaining cluster segments according to a minimum mass requirement, and discarding all those cluster segments which do not satisfy said minimum mass requirement.

17. The method according to claim 13, further including determining a centroid of a segment using itemsets contained in said segment and refining the seeds in an iterative process.

18. The method according to claim 16, wherein said refining step includes the step of redistributing transactions in cluster segments below said minimum mass requirement to different clusters exceeding said minimum mass requirement.

19. The method according to claim 10, wherein said received request includes a specified support and confidence measure, said personalized association rules generated in accordance with said specified support and confidence measure.

20. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for generating personalized associations of items organized as a plurality of transactions, each transaction comprising itemsets having one or more items capable of forming said associations, said method steps comprising:

(a) clustering itemsets from said plurality of transactions according to a user-specified number of cluster segments and a minimum density of each itemset in the segment;

(b) receiving requests for a given customer, a request including a customer'"'"'s buying pattern; and

,

(c) generating personalized association rules in accordance with said received request, said personalized association rules generated from the cluster segment having items most relevant to tire customer buying pattern provided in the received request.

21. The program storage device readable by a machine according to claim 20, wherein said clustering step includes implementing an iterative process for determining the different segments.

22. The program storage device readable by a machine according to claim 21, wherein the generating step includes finding a centroid of a cluster segment that most closely matches a customer buying pattern, and generating the itemsets and association rules which are most specific to this segment.

23. The program storage device readable by a machine according to claim 22, wherein said iterative process comprises steps of:

determining an initial set of seeds, each seed comprising a randomly selected transaction around which a cluster is to be built,

determining similarity of a transaction to a seed;

assigning a transaction to a most closely matched seed; and

iteratively refining sets of seeds for building said cluster segments.

24. The program storage device readable by a machine according to claim 23, wherein said refining step includes the step of projecting out the least frequent items from the seed.

25. The program storage device readable by a machine according to claim 24, wherein a number of the least frequent items to be projected from a seed is a function of the iteration.

26. The program storage device readable by a machine according to claim 23, wherein said clustering step includes retaining cluster segments according to a minimum mass requirement, and discarding all those cluster segments which do not satisfy said minimum mass requirement.

27. The program storage device readable by a machine according to claim 23, further including determining a centroid of a segment using itemsets contained in said segment and refining the seeds in an iterative process.

28. The program storage device readable by a machine according to claim 26, wherein said refining step includes the step of redistributing transactions in cluster segments below said minimum mass requirement to different clusters exceeding said minimum mass requirement.

29. The program storage device readable by a machine according to claim 20, wherein said received request includes a specified support and confidence measure, said personalized association rules generated in accordance with said specified support and confidence measure.