Association rule ranker for web site emulation

• US 6,230,153 B1
• Filed: 06/18/1998
• Issued: 05/08/2001
• Est. Priority Date: 06/18/1998
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation, Johnson & Johnson Industria E Comercio Ltda.
• Original Assignee: International Business Machines Corporation
• Inventors: Howard, Steven Kenneth, Plutowski, Mark Earl Paul, Martin, David Charles
• Primary Examiner(s): Alam, Hosain T.
• Assistant Examiner(s): FLEURANTIN, JEAN B
• Application Number:
  US09/099,538
• Time in Patent Office: 1,055 Days
• Field of Search: 707/1-7, 707/200, 707/205, 705/5, 705/10
• US Class Current: 1/1
• CPC Class Codes: G06F 16/958 Organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking
• CPC Class Codes: G06Q 10/02 Reservations, e.g. for tickets, services or events
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A method and apparatus that allows association rules defining URL-URL relationships, and URL-URL relationships that are strongly influenced by a web site'"'"'s topology, to be identified and respectively qualified. Superfluous association rules may be separated from non-topology affected association rules and discounted as desired. The invention may be implemented in conjunction with a probalistic generative method used to model a web site and simulate the behavior of a visitor traversing the site. The invention further allows randomized web site visitor behavior to be separated into “interesting” and “uninteresting” behavior.

Claims

1. A method for sorting data mining association rules, the method comprising:

identifying statistically significant relationships within a cumulated distribution of data, the significant relationships represented by association rules; and

separating meaningful association rules from unmeaningful association rules using an emulated distribution of the data as a reference, wherein said emulated distribution is based upon emulated events that are different than actual events.

2. The method recited in claim 1, separating meaningful association rules from unmeaningful association rules by sorting the rules by their support within the distribution of data.

3. The method recited in claim 1, separating meaningful association rules from unmeaningful association rules by sorting the rules by their confidence within the distribution of data.

4. The method recited in claim 2, wherein the association rules are sorted in sets of rules for different systems of events, where C represents an emulated system of events for a web site and B represents an actual system of events for the same web site data, and where if K(P_AC:

R_AC)>

K(P_AB;

R_AB), the association rules applied to the emulated system of events C have greater relevance then the association rules applied to the actual system of events B, and where P is a probability distribution for an association rule for the actual system of events, and R is an emulated support for an association rule for the emulated system of events, and wherein K is a constant.

5. The method recited in claim 4, wherein P is measured by an association rule'"'"'s support in a respective system of events.

6. The method recited in claim 5, wherein P_AB=P(A, B₁), P(A, B₂), . . . P(A, B_n) and R_AB=R(A, B₁), R(A, B₂) . . . R(A, B_n), and P_AC=P(A, C₁), P(A, C₂), . . . P(A, B_n).

7. The method recited in claim 2, wherein the association rules are sorted in descending order of support.

8. The method recited in claim 7, where P(A,B₁)/R(A,B₁), P(A,B₂)/R(A,B₂), . . . P(A,B_n)/R(A,B_n), where B represents an event in an actual system of events, and where the association rules pertaining to the actual system of events have equal support as association rules pertaining to an emulated system of events if P_AB/R_AB=1, where P is a probability distribution for an association rule for the actual system of events, and R is an emulated support for an association rule for the emulated system of events, and where P_AB has lesser support than R_AB as P_AB→

0 and R_AB→

∞

, and where P_AB has greater support than R_AB as R_AB→

0 and P_AB→

∞

.

9. The method recited in claim 2, wherein the association rules are sorted in ascending order of support.

10. The method recited in claim 9, where R(A,B₁)/P(A,B₁), R(A,B₂)/P(A,B₂), . . . R(A,B_n)/P(A,B_n), where B represents an actual system of events, and where the association rules pertaining to the actual system of events have equal support as the association rules pertaining to an emulated system of events if R_AB/P_AB=1 where R is an emulated support for an association rule for an emulated system of events, and P is a probability distribution for an association rule for the actual system of events, and where R_AB has lesser support than P_AB as R_AB→

0 and P_AB→

∞

, and where R_AB has greater support than P_AB as P_AB→

0 and R_AB→

∞

.

11. The method recited in claim 2, wherein the association rules are further sorted where P(A,B₁)log(P(A,B₁)/R(A,B₁)), P(A,B₂)log(P(A,B₂)/R(A,B₂)), . . . , P(A,B_n)log(P(A,B_n)/R(A,B_n)).

12. The method recited in claim 8, wherein the association rules are farther sorted where P(A,B₁)log(P(A,B₁)/R(A,B₁), P(A,B₂)log(P(A,B₂)/R(A,B₂)), . . . , P(A,B_n)log(P(A,B_n)/R(A,B_n)).

13. The method recited in claim 10, wherein the association rules are further sorted where P(A,B₁)log(P(A,B₁)/R(A,B₁), P(A,B₂)log(P(A,B₂)/R(A,B₂)), . . . , P(A,B_n)log(P(A,B_n)/R(A,B_n).

14. The method recited in claim 2, wherein event D₁ corresponds to a set of uniform resource locator data, and event D₁ corresponds to all other sets of uniform resource locators not in set D₁, and where D={D₁, D₂, . . . , D_m}, where the uniform resource locator data sets do not comprise a system of events and {(P(A,D_i)/R(A,D_i)÷

P(A,D_i)/R(A,D_i))/2}, i=1, 2, . . . , m, where i=1, 2, . . . , m.

15. The method recited in claim 14, sorting further comprising {P(A,D_i)log(P(A,D_i)/R(A,D_i))÷

P(A,D_i)log(P(A,D_i)/R(A,D_i))}, i=1,2, . . . , m, {P(A,D_i)/R(A,D_i)}, i=1, 2, . . . , m.

16. The method recited in claim 2, wherein association rules having high levels of support compared to the emulated distribution are ranked highest, regardless of whether the association rules are highly supported in the uniform resource locator data as determined by P, and where P is a probability of an occurrence of the association rule.

17. The method recited in claim 16, wherein two association rules with identical P values are further sorted so that the rule with greater support in the emulated data is sorted higher than the rule with the lesser support.

18. A method for sorting data mining association rules, the method comprising:

identifying statistically significant relationships within a cumulated distribution of data, the significant relationships represented by association rules; and

separating meaningful association rules from unmeaningful association rules using an emulated distribution of the data as a reference by sorting the rules by their support within the distribution of data,

wherein the uniform resource locator data does not comprise a system of events and is sorted by m sets of uniform resource locator data, where {P(A,D_i)/R(A,D_i)}, i=], 2, . . . , m, and D_i corresponds to sets of uniform resource locator data 1 to m.

19. The method recited in claim 18, wherein the association rules are further sorted where {P(A,D_i)log(P(A,D_i)/R(A,D_i))}, i=1, 2, . . . , m.

20. A method for sorting data mining association rules, the method comprising:

identifying statistically significant relationships within a cumulated distribution of data, the significant relationships represented by association rules; and

separating meaningful association rules from unmeaningful association rules using an emulated distribution of the data as a reference by sorting the rules by their confidence within the distribution of data,

sorting of the association rules comprising ranking the rules by their confidence, where {P(A|D_i)/R(A|D_i)}, i=1, 2, . . . , m, where P is a probability of an occurrence of an association rule, and where two association rules with identical P values are further sorted so that the rule with greater support in the emulated data is sorted higher than the rule with the lesser support.

21. The method recited in claim 20, wherein the association rules are further sorted where {P(A,D_i)log(P(A|D_i)/R(A|D_i))}, i=1, 2, . . . , m.

22. An article of manufacture comprising a data storage medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method for sorting data mining association rules, the method comprising:

identifying statistically significant relationships within a cumulated distribution of uniform resource locator data, the significant relationships represented by association rules; and

separating meaningful association rules from unmeaningful association rules using an emulated distribution of the uniform resource locator data as a reference, wherein said emulated distribution is based upon emulated events that are different than actual events.

23. The article recited in claim 22, separating meaningful association rules from unmeaningful association rules by sorting the rules by their support within the distribution of uniform resource locator data.

24. The article recited in claim 22, separating meaningful association rules from unmeaningful association rules by sorting the rules by their confidence for support within the distribution of uniform resource locator data.

25. The article recited in claim 22, wherein the association rules are sorted in sets of rules for different systems of events, where C represents an emulated system of events for a web site and B represents an actual system of events for the same web site data, and where if K(P_AC:

R_AC)>

K(P_AB;

R_AB), the association rules applied to the emulated system of events C have greater relevance then the association rules applied to the actual system of events B, and where P is a probability distribution for an association rule for the actual system of events, and R is an emulated support for an association rule for the emulated system of events, and wherein K is a constant.

26. The article recited in claim 25, wherein P is measured by an association rule'"'"'s support in a respective system of events.

27. The article recited in claim 22, wherein P_AB=P(A, B₁), P(A, B₂), . . . P(A, B_n) and R_AB=R(A, B₁), R(A, B₂) . . . R(A, B_n), and P_AC=P(A, C₁), P(A, C₂), . . . P(A, B_n).

28. The article recited in claim 22, wherein the association rules are sorted in descending order of support.

29. The article recited in claim 22, where P(A,B₁)/R(A,B₁), P(A,B₂)/R(A,B₂), . . . P(A,B_n)/R(A,B_n), where B represents an event in an actual system of events, and where the association rules pertaining to the actual system of events have equal support as association rules pertaining to an emulated system of events if P_AB/R_AB=1, where P is a probability distribution for an association rule for the actual system of events, and R is an emulated support for an association rule for the emulated system of events, and where P_AB has lesser support than R_AB as P_AB→

0 and R_AB→

∞

, and where P_AB has greater support than R_AB as R_AB→

0 and P_AB→

∞

.

30. The article recited in claim 22, wherein the association rules are sorted in ascending order of support.

31. The article recited in claim 22, where R(A,B₁)/P(A,B₁), R(A,B₂)/P(A,B₂), . . . R(A,B_n)/P(A,B_n), where B represents an actual system of events, and where the association rules pertaining to the actual system of events have equal support as the association rules pertaining to an emulated system of events if R_AB/P_AB=1 where R is an emulated support for an association rule for an emulated system of events, and P is a probability distribution for an association rule for the actual system of events, and where R_AB has lesser support than P_AB as R_AB→

0 and P_AB→

∞

, and where R_AB has greater support than P_AB as P_AB→

0 and R_AB→

∞

.

32. The article recited in claim 22, wherein the association rules are further sorted where P(A,B₁)log(P(A,B₁)/R(A,B₁)), P(A,B₂)log(P(A,B₂)/R(A,B₂)), . . . , P(A,B_n)log(P(A,B_n)/R(A,B_n)).

33. An article recited in claim 29, wherein the association rules are further sorted where P(A,B₁)log(P(A,B₁)/R(A,B₁)), P(A,B₂)log(P(A,B₂)/R(A,B₂)), . . . , P(A,B_n)log(P(A,B_n)/R(A,B_n).

34. An article recited in claim 31, wherein the association rules are further sorted where P(A,B₁)log(P(A,B₁)/R(A,B₁)), P(A,B₂)log(P(A,B₂)/R(A,B₂)), . . . , P(A,B_n)log(P(A,B_n)/R(A,B_n).

35. The article recited in claim 22, wherein event D₁ corresponds to a set of uniform resource locator data, and event D₁ corresponds to all other sets of uniform resource locators not in set D₁, and where D={D₁, D₂, . . . , D_m}, where the uniform resource locator data sets do not comprise a system of events and {(P(A,D_i)/R(A,D_i)+P(A,D_i)/R(A,D_i))/2}, i=1, 2, . . . , m, where i=1, 2, . . . , m.

36. The article recited in claim 22, the method steps further comprising:

{(P(A,D_i)log(P(A,D_i)/R(A,D_i))÷

P(A,D_i)log(P(A,D_i)/R(A,D_i))}, i=1,2, . . . , m, {P(A,D_i)/R(A,D_i)}, i=1, 2, . . . , m.

37. The article recited in claim 22, wherein association rules having high levels of support compared to the emulated distribution are ranked highest, regardless of whether the association rules are highly supported in the uniform resource locator data as determined by P, and where P is a probability of an occurrence of the association rule.

38. The article recited in claim 22, wherein two association rules with identical P values are further sorted so that the rule with greater support in the emulated data is sorted higher than the rule with the lesser support.

40. The article recited in claim 22, wherein the association rules are further sorted where {P(A,D_i)log(P(A,D_i)/R(A,D_i))}, i=1, 2, . . . , m.

42. The article recited in claim 22, wherein the association rules are further sorted where {P(A,D_i)log(P(A|D_i)/R(A|D_i))}, i=1, 2, . . . , m.

39. An article of manufacture comprising a data storage medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method for sorting data mining association rules, the method comprising:

identifying statistically significant relationships within a cumulated distribution of uniform resource locator data, the significant relationships represented by association rules; and

separating meaningful association rules from unmeaningful association rules using an emulated distribution of the uniform resource locator data as a reference, wherein said emulated distribution is based upon emulated events that are different than actual events;

wherein the uniform resource located data does not comprise a system of events and is sorted by m sets of uniform resource locator data, where {P(A,D_i)/R(A,D_i)}, i=1, 2, . . . , m, and D_i corresponds to sets of uniform resource locator data l to m.

41. An article of manufacture comprising a data storage medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method for sorting data mining association rules, the method comprising:

identifying statistically significant relationships within a cumulated distribution of uniform resource locator data, the significant relationships represented by association rules; and

separating meaningful association rules from unmeaningful association rules using an emulated distribution of the uniform resource locator data as a reference, wherein said emulated distribution is based upon emulated events that are different than actual events;

sorting of the association rules comprising ranking the rules by their confidence, where {P(A\D_i)/R(A\D_i)}, i=1, 2, . . . , m, where P is a probability of an occurrence of an association rule, and where two association rules with identical P values are further sorted so that the rule with greater support in the emulated data is sorted higher than the rule with the lesser support.

43. An apparatus to sort data mining association rules, comprising:

a processor;

a database including URL data;

circuitry to communicatively couple the processor to the database;

storage communicatively accessible by the processor;

the processor sorting mining association rules by;

identifying statistically significant relationships within a cumulated distribution of uniform resource locator data, the significant relationships represented by association rules; and

separating meaningful association rules from unmeaningful association rules using an emulated distribution of the uniform resource locator data as a reference, wherein said emulated distribution is based upon emulated events that are different than actual events.

44. The apparatus recited in claim 43, the processor further sorting by:

separating meaningful association rules from unmeaningful association rules by sorting the rules by their support within the distribution of uniform resource locator data.

45. The apparatus recited in claim 43, separating meaningful association rules from unmeaningful association rules by sorting the rules by their confidence for support within the distribution of uniform resource locator data.

46. The apparatus recited in claim 43, wherein the association rules are sorted in sets of rules for different systems of events, where C represents an emulated system of events for a web site and B represents an actual system of events for the same web site data, and where if K(P_AC:

R_AC)>

K(P_AB;

R_AB), the association rules applied to the emulated system of events C have greater relevance then the association rules applied to the actual system of events B, and where P is a probability distribution for an association rule for the actual system of events, and R is an emulated support for an association rule for the emulated system of events, and wherein K is a constant.

47. The apparatus recited in claim 43, wherein P is measured by an association rule'"'"'s support in a respective system of events.

48. The apparatus recited in claim 43, wherein P_AB=P(A, B₁), P(A, B₂), . . . P(A, B_n) and R_AB=R(A, B₁), R(A, B₂) . . . R(A, B_n, and P_AC=P(A, C₁), P(A, C₂), . . . P(A, B_n).

49. The apparatus recited in claim 43, wherein the association rules are sorted in descending order of support.

50. The apparatus recited in claim 43, where P(A,B₁)/R(A,B₁), P(A,B₂)/R(A,B₂), . . . P(A,B_n)/R(A,B_n), where B represents an event in an actual system of events, and where the association rules pertaining to the actual system of events have equal support as association rules pertaining to an emulated system of events if P_AB/R_AB=1, where P is a probability, distribution for an association rule for the actual system of events, and R is an emulated support for an association rule for the emulated system of events, and where P_AB has lesser support than R_AB as P_AB→

0 and R_AB→

∞

, and where P_AB has greater support than R_AB as R_AB→

0 and P_AB→

∞

.

51. The apparatus recited in claim 43, wherein the association rules are sorted in ascending order of support.

52. The apparatus recited in claim 43, where R(A,B₁)/P(A,B₁), R(A,B₂)/P(A,B₂), . . . R(A,B_n)/P(A,B_n), where B represents an actual system of events, and where the association rules pertaining to the actual system of events have equal support as the association rules pertaining to an emulated system of events if R_AB/P_AB=1 where R is an emulated support for an association rule for an emulated system of events, and P is a probability distribution for an association rule for the actual system of events, and where R_AB has lesser support than P_AB as R_AB→

0 and P_AB→

∞

, and where R_AB has greater support than P_AB as P_AB→

0 and R_AB→

∞

.

53. The apparatus recited in claim 43, wherein the association rules are further sorted where P(A,B₁)log(P(A,B₁)/R(A,B₁)), P(A,B₂)log(P(A,B₂)/R(A,B₂)), . . . , P(A,B_n)log(P(A,B_n)/R(A,B_n)).

54. The apparatus recited in claim 50, wherein the association rules are further sorted where P(A, B₁)log(P(A, B₁)/R(A,B₁)), P(A, B₂)log(P(A, B₂)/R(A, B₂)), . . . , P(A, B_n)log(P(A, B_n)/R(A, B_n)).

55. The apparatus recited in claim 52, wherein the association rules are further sorted where P(A, B₁)log(P(A, B₁)/R(A,B₁)), P(A, B₂)log(P(A, B₂)/R(A, B₂)), . . . , P(A, B_n)log(P(A, B_n)/R(A, B_n)).

56. The apparatus recited in claim 43, wherein event D₁ corresponds to a set of uniform resource locator data, and event D₁ corresponds to all other sets of uniform resource locators not in set D₁, and where D={D₁, D₂, . . . , D_m}, where the uniform resource locator data sets do not comprise a system of events and {(P(A,D_i)/R(A,D_i)÷

P(A,D_i)/R(A,D_i))/2}, i=1, 2, . . . , m, where i=1, 2, . . . , m.

57. The apparatus recited in claim 43, sorting further comprising {P(A,D_i)log(P(A,D_i)/R(A,D_i))÷

P(A,D_i)log(P(A,D_i)/R(A,D_i))}, i =1, 2, . . . , m, {P(A,D_i)/R(A,D_i)}, i=1, 2, . . . , m.

58. The apparatus recited in claim 43, wherein association rules having high levels of support compared to the emulated baseline reference distribution are ranked highest, regardless of whether the association rules are highly supported in the uniform resource locator data as determined by P, and where P is a probability of an occurrence of the association rule.

59. The apparatus recited in claim 43, wherein two association rules with identical P values are further sorted so that the rule with greater support in the emulated data is sorted higher than the rule with the lesser support.

61. The apparatus recited in claim 43, wherein the association rules are further sorted where {P(A,D_i)log(P(A,D_i)/R(A,D_i))}, i=1, 2, . . . , m.

63. The apparatus recited in claim 43, wherein the association rules are further sorted where {P(A,D_i)log(P(A|D_i)/R(A|D_i))}, i =1, 2, . . . , m.

60. An apparatus to sort data mining association rules, comprising:

a processor;

a database including URL data;

circuitry to communicatively couple the processor to the database;

storage communicatively accessible by the processor;

the processor sorting mining association rules by;

identifying statistically significant relationships within a cumulated distribution of uniform resource locator data, the significant relationships represented by association rules; and

separating meaningful association rules from unmeaningful association rules using an emulated distribution of the uniform resource locator data as a reference, wherein said emulated distribution is based upon emulated events that are different than actual events;

where the uniform resource locator data does not comprise a system of events and is sorted by m sets of uniform resource locator data, where {P(A,D_i)/R(A,D_i)}, i=1, 2, . . . , m, and D_i corresponds to sets of uniform resource data l to m.

62. An apparatus to sort data mining association rules, comprising:

a processor;

a database including URL data;

circuitry to communicatively couple the processor to the database;

storage communicatively accessible by the processor;

the processor sorting mining association rules by;

identifying statistically significant relationships within a cumulated distribution of uniform resource locator data, the significant relationships represented by association rules; and

separating meaningful association rules from unmeaningful association rules using an emulated distribution of the uniform resource locator data as a reference, wherein said emulated distribution is based upon emulated events that are different than actual events;

sorting of the association rules comprising ranking the rules by their confidence, where {P(A\D_i)/R(A\D_i)}, i=1,2, . . . , m, where P is a probability of an occurrence of an association rule, and where two association rules with identical P values are further sorted higher than the rule with the lesser support.

64. An apparatus for sorting data mining association rules, comprising:

means for storing URL data;

means for processing the URL data by;

identifying statistically significant relationships within a cumulated distribution of uniform resource locator data, the significant relationships represented by association rules; and

separating meaningful association rules from unmeaningful association rules using an emulated distribution of the uniform resource locator data as a reference, wherein said emulated distribution is based upon emulated events that are different than actual events.

65. The apparatus recited in claim 64, the processing means further sorting data by separating meaningful association rules from unmeaningful association rules by sorting the rules by their support within the distribution of uniform resource locator data.

66. The apparatus recited in claim 64, the processing means further sorting data by separating meaningful association rules from unmeaningful association rules by sorting the rules by their confidence for support within the distribution of uniform resource locator data.

67. The apparatus recited in claim 64, wherein the association rules are sorted in sets of rules for different systems of events, where C represents an emulated system of events for a web site and B represents an actual system of events for the same web site data, and where if K(P_AC:

R_AC)>

K(P_AB;

R_AB), the association rules applied to the emulated system of events C have greater relevance then the association rules applied to the actual system of events B, and where P is a probability distribution for an association rule for the actual system of events, and R is an emulated support for an association rule for the emulated system of events, and wherein K is a constant.

68. The apparatus recited in claim 64, wherein P is measured by an association rule'"'"'s support in a respective system of events.

69. The apparatus recited in claim 64, wherein P_AB=P(A, B₁), P(A, B₂), . . . P(A, B_n) and R_AB=R(A, B₁), R(A, B₂) . . . R(A, B_n), and P_AC=P(A, C₁), P(A, C₂), . . . P(A, B_n).