Mining emergent weighted association rules utilizing backlinking reinforcement analysis

• US 6,763,354 B2
• Filed: 05/10/2002
• Issued: 07/13/2004
• Est. Priority Date: 05/10/2002
• Status: Expired due to Term

• Current Assignee: Microsoft Corporation
• Original Assignee: AgentArts Incorporated (Microsoft Corporation)
• Inventors: Hosken, Benjamin E.
• Primary Examiner(s): CHANNAVAJJALA, SRIRAMA T
• Application Number:
  US10/143,381
• Publication Number:
  US 20030212651A1
• Time in Patent Office: 795 Days
• Field of Search: 707/1-10, 707/100-104, 707/200-205, 706/45-50, 706/1-12, 706/56, 706/60-61
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A system and methods providing for the evaluation of transaction data records to first determine forward link associations between items as reference and related items identified by corresponding “expert” users as a basis for establishing expert database item association rules. The forward link associations are then evaluated to identify back link associations between reference and related items. Back link weights, corresponding to the respective back link associations reflecting the depth and strength of the back linked associations are determined and associated with the forward link associations to provide an augmented basis for subsequently evaluating the association rules collected into an expert database.

Claims

1. A method of enhancing the reliability and accuracy of a computer generated expert database, said method comprising the steps of:

a) first establishing a plurality of forward link associations between reference and related items having first respective weights;

b) second establishing a plurality of back link associations between reference and related items having second respective weights, wherein said pluralities of forward and back link associations have a defined correspondence; and

c) storing, to an expert database, data records identifying said forward link associations as association rules including said first and second respective weights.

2. The method of claim 1 wherein said defined correspondence enables combination of said first and second respective weights.

3. The method of claim 2 wherein said plurality of forward link associations are determined from expert sub-populations identified relative to the reference items of said plurality of forward link associations.

4. The method of claim 3 said first respective weights are determined relative to respective expert sub-populations identified by actions taken against reference items.

5. The method of claim 1 wherein said plurality of back link associations correspond to a predetermined subset of said plurality of forward link associations and wherein said second respective weights are combinable with said first respective weights of said predetermined subset.

6. The method of claim 5 wherein said second respective weights include strength and depth terms, wherein each said depth term corresponds to the closure depth of a back link association on a chain series of forward link associations, and wherein said second respective weights are inversely proportional to respective depth terms.

7. The method of claim 6 wherein said strength terms are proportional to the support for respective back link associations relative to respective predetermined chain root forward link associations.

22. The system of claim 2l wherein said selective analytic generation program is responsive to predetermined analysis parameters including a first parameter controlling the size of said item specific expert user sub-populations and a second parameter determining said defined threshold support.

8. A method of preparing an association rules set for an expert database utilizing a computer to analyze a set of data records describing transactions involving users with respect to a predetermined set of items, said method comprising the steps of:

a) selecting, from the set of users identified by a set of transaction data records, sub-populations of expert users for respective reference items;

b) first computing a forward coupling graph of associations between reference items and related items, wherein forward link associations are defined with respect to said sub-populations of expert users, and wherein each said forward link association of said forward coupling graph has a first weighting;

c) second computing back link associations in said forward coupling graph, wherein said back link associations represent closures of chains of forward link associations, wherein each said back link association has a second weighting; and

d) generating an association rule, including a third weight, for a predetermined forward link association wherein said third weight represents a combination of said first and second weightings for said predetermined forward link association.

9. The method of claim 8 wherein each of said sub-populations of expert users has at least a predetermined level of expertise, defined by predetermined criteria, with respect to a corresponding reference item.

10. The method of claim 9 wherein said predetermined level of expertise limits a predetermined sub-population of expert users to less than 50% of said set of users.

11. The method of claim 10 wherein said forward coupling graph excludes associations having less than a predetermined level of support by corresponding said sub-populations of expert users.

12. The method of claim 11 wherein said second weightings are inversely proportional to the respective number of associations between reference and related items necessary to establish said back links.

13. The method of claim 12 wherein said second weightings are further proportional to the strength of the associations coupled through respective each said back link associations.

14. A system for generating association rules for expert databases through the execution of a computer, said system comprising:

a) a first database storing a set of transaction data records;

b) a second database provided to store a set of association rules, wherein each said association rule defines an association weighting; and

c) a computer coupled between said first and second databases, said computer implementing a selective analytic generation program for generating said set of association rules from said set of transaction data records wherein said selective analytic generation program provides for the identification of a set of back link associations within a set of forward link associations defined by said set of transaction data records, a subset of said set of association rules having a defined correspondence with said set of back link associations, the computation of respective back link weightings for said set of back link associations, and the incorporation of said back link weightings as respective components of said association weightings of said subset of said set of association rules.

15. The system of claim 14 wherein said set of transactions define actions by users with respect to items and wherein said computer is further coupled to receive predetermined analysis parameters for controlling the operation of said selective analytic generation program including a first parameter that defines sub-populations of users whose actions with respect to items determine the support for item corresponding association rules and a second parameter that defines of a minimum level of support required for each association rule to be included in said second database.

16. The system of claim 14 wherein said selective analytic generation program provides for identification of limited, item respective expert user sub-populations from which said set of forward link associations are selectively identified from said set of transaction data records.

17. The system of claim 16 wherein said expert user sub-populations include user sub-populations that are less than 50% of the user population identified in said set of transaction data records.

18. The system of claim 17 wherein said set of forward link associations is constrained to forward link associations having defined support determined in relationship to said item respective expert user sub-populations.

19. The system of claim 18 wherein the respective back link weightings for said set of back link associations are determined with respect to a defined threshold support for the back link corresponding forward link associations of said set of forward link associations.

20. The system of claim 19 wherein the respective back link weightings for said set of back link associations are further inversely proportional to the depth of the back links in the respective series of forward link associations.

21. The system of claim 20 wherein the respective back link weightings for said set of back link associations are further proportional to the relative size of the item specific expert user sub-populations corresponding to the back link associations and the user population identified in said set of transaction data records.

23. A process of generating an expert database through the execution of a computer based analysis of a set of transaction records representing user actions taken with respect to a defined set of items, said process comprising the steps of:

a) first identifying, for each of a plurality of reference items, respective expert user sub-populations of the users identified in said set of transactions;

b) second identifying, for each of said expert user sub-populations, sets of related items;

c) constructing an item association data structure representing forward linked associations between said reference items and said sets of related items;

d) pruning said item association data structure to reflect a minimum defined support for respective forward link associations;

e) third identifying back linked associations between reference items and related items within said item association data structure, each said back linked association corresponding to a forward linked association;

f) determining a back link weightings for each of said back linked associations; and

g) generating association rules from said association data structure including associating said back link weightings with the association rules generated from the back linked association corresponding forward linked associations.

24. The process of claim 23 wherein each said expert user sub-population represents a respective minority of the users identified in said set of transactions whose actions taken with respect to corresponding reference items are the most significant.

25. The process of claim 23 wherein said expert user sub-populations are distinguished based on the cumulative weights assigned to the transactions taken by respective users relative to corresponding ones of said reference items.

26. The process of claim 25 wherein said minimum defined support includes a threshold constant.

27. The process of claim 26 wherein said minimum defined support further includes a proportionality of the support to the number of members of a reference item corresponding expert user sub-population.

28. The process of claim 27 wherein said back link weights are proportional to the depth number of forward linked associations identified with said back linked associations and the support for said forward linked associations corresponding to said back linked associations.