association_rule_miner

Association rule miner deriving confidence- and lift-scored rules from frequent itemsets and sequential patterns, with leverage, Jaccard similarity, cosine similarity, and Kulczynski similarity available on demand. The source mined result and its original dataset are both required. Dataset access allows exact support counts to be recovered when source mining options omit shorter patterns and when the source is a closed sequential pattern result.

API documentation

Open the ../../apis/library_index.html#association-rule-miner link in a web browser.

Loading

To load this library, load the loader.lgt file:

| ?- logtalk_load(association_rule_miner(loader)).

Testing

To test this library predicates, load the tester.lgt file:

| ?- logtalk_load(association_rule_miner(tester)).

Supported source miners

The following frequent itemset miners are supported:

  • apriori_pattern_miner

  • eclat_pattern_miner

  • fp_growth_pattern_miner

For an itemset(Items, Support) source pattern, every partition into a nonempty antecedent and a nonempty consequent defines a candidate rule.

The following sequential pattern miners are supported:

  • gsp_pattern_miner

  • prefix_span_pattern_miner

  • spade_pattern_miner

  • clo_span_pattern_miner

For a sequence_pattern(Pattern, Support) source pattern, candidates are generated by splitting a nonempty sequence prefix from a nonempty sequence suffix. Splits occur only at event boundaries. Items in the same event are not interpreted as temporally ordered, and arbitrary subsequence partitions are not generated.

Rule metrics

For antecedent A, consequent C, full source pattern P, and dataset size N, the metrics are:

Confidence = Support(P) / Support(A)

Lift = N * Support(P) / (Support(A) * Support(C))

Leverage is available as an on-demand metric using the rule_metric/3 predicate and is computed as:

Leverage = Support(P) / N - (Support(A) / N) * (Support(C) / N)

For example, rule_metric(AssociationRuleMiner, Rule, leverage(Value)) computes the leverage of a rule stored in the association rule miner result. This calculation uses only the stored support counts and dataset size and does not access the original dataset.

Jaccard similarity is also available on demand and is computed as:

Jaccard = Support(P) / (Support(A) + Support(C) - Support(P))

For example, rule_metric(AssociationRuleMiner, Rule, jaccard(Value)) computes the Jaccard similarity between the antecedent and consequent of a stored rule.

Cosine similarity is available on demand and is computed as:

Cosine = Support(P) / sqrt(Support(A) * Support(C))

For example, rule_metric(AssociationRuleMiner, Rule, cosine(Value)) computes the cosine similarity between the antecedent and consequent of a stored rule.

Kulczynski similarity is available on demand and is computed as:

Kulczynski = 0.5 * (Support(P) / Support(A) + Support(P) / Support(C))

For example, rule_metric(AssociationRuleMiner, Rule, kulczynski(Value)) computes the average confidence in both directions between the antecedent and consequent of a stored rule. Calling rule_metric/3 with an unbound metric argument enumerates all supported on-demand metrics.

Sequential support counts each dataset sequence at most once, independently of how many embeddings of the pattern occur in that sequence.

Options

The mine/4 predicate accepts the following options:

  • minimum_confidence/1: Inclusive confidence threshold in the interval [0.0, 1.0]. The default is 0.5.

  • minimum_lift/1: Inclusive nonnegative lift threshold. The default is 0.0.

  • maximum_rule_length/1: Maximum total number of items in both rule sides. The default is 1000.

  • minimum_consequent_length/1: Minimum number of consequent items. The default is 1.

  • maximum_consequent_length/1: Maximum number of consequent items. The default is 1000.

Association rule miner representation

The result is represented by:

association_rule_miner(SourceMiner, ItemDomain, DatasetSize, CandidateRuleCount, Rules, Options)

Each rule is represented by:

association_rule(Antecedent, Consequent, Support, AntecedentSupport, ConsequentSupport, Confidence, Lift)

Rules are ordered by total rule length, antecedent, and consequent. The candidate count is stored separately because confidence and lift filtering removes information needed to reconstruct it from the retained rules.

Limitations

  • Rules are generated only from patterns present in the source mined result. Support counts for omitted antecedents and consequents are recovered from the dataset, but rules for omitted full patterns are not reconstructed. Consequently, rules derived from a closed-pattern result can be fewer than those derived from the complete frequent-pattern result.

  • Generating all itemset rules is exponential in the itemset length because every proper nonempty partition is considered. Use pattern- and rule-length limits to control the candidate count.

  • Exact support recovery traverses the supplied dataset once but tests every distinct source pattern, antecedent, and consequent against each dataset record. Large datasets or pattern collections can therefore still make rule derivation expensive.

  • Sequential rules use only event-boundary prefix-to-suffix splits. Same-event implications, arbitrary sequential partitions, time windows, and gap constraints are not supported.

  • The available quality metrics are confidence, lift, leverage, Jaccard similarity, cosine similarity, and Kulczynski similarity. Additional metrics, statistical significance tests, redundancy pruning, and top-k selection are not provided.

  • Only the source miners listed above and datasets implementing their corresponding transaction or sequence dataset protocols are supported.

References

  1. Agrawal, R. and Srikant, R. (1994) - “Fast algorithms for mining association rules in large databases”.