intn (Input) Number of (transaction, item) pairs in x.
floatx[] (Input) Array of size n x 2, each row of which represents a transaction id and item id pair.
intmax_num_products (Input) Maximum number of unique items or products that may be present in the transactions. max_num_products must be greater than or equal to the number of items in x.
Return Value
Pointer to an Imsls_f_apriori_itemsets data structure containing the frequent itemsets in the transaction set x. If no value can be computed, then NULL is returned. To release this space, use imsls_free_apriori_itemsets. Please see Data Structures for a description of this data structure.
Synopsis with Optional Arguments
#include<imsls.h>
Imsls_f_apriori_itemsets*imsls_f_apriori (int n, floatx[], intmax_num_products,
IMSLS_MAX_SET_SIZE, intmax_set_size (Input) Maximum size of an itemset. Only frequent itemsets with max_set_size or fewer items are considered in the analysis. Default: max_set_size = 5.
IMSLS_MIN_SUPPORT, floatmin_pct_support (Input) Minimum percentage of transactions in which an item or itemset must be present to be considered frequent. min_pct_support must be in the interval [0,1]. Default: min_pct_support= 0.1.
IMSLS_ASSOCIATION_RULES, floatconfidence, floatlift, Imsls_f_association_rules**assoc_rules (Input/Output) Computes the strong association rules among itemsets.
floatconfidence (Input) The minimum confidence used to determine the strong association rules. confidence must be in the interval [0,1]. lift is the other criterion that determines whether an association is "strong." If either criterion, confidence or lift, is exceeded, the association rule is considered "strong."
floatlift (Input) The minimum lift used to determine the strong association rules. lift must be non-negative. confidence is the other criterion that determines whether an association is "strong." If either criterion, confidence or lift, is exceeded, the association rule is considered "strong."
Imsls_f_association_rules**assoc_rules (Output) Address of a pointer to an Imsls_f_association_rules data structure containing the strong association rules among the itemsets. If no value can be computed, then NULL is returned. To release this space, use imsls_f_free_association_rules.
Description
The function imsls_f_apriori performs the Apriori algorithm for association rule discovery. Association rules are statements of the form, "if X, then Y", given with some measure of confidence. The main application for association rule discovery is market basket analysis, where X and Y are products or groups of products, and the occurrences are individual transactions, or “market baskets." The results help sellers learn relationships between the different products they sell, supporting better marketing decisions. There are other applications for association rule discovery, such as the problem areas of text mining and bioinformatics. The Apriori algorithm (Agrawal and Srikant, 1994) is one of the most popular algorithms for association rule discovery in transactional datasets.
For distributed data or data larger than physical memory, see imsls_f_aggr_apriori.
In the first and most critical stage, the Apriori algorithm mines the transactions for frequent itemsets. An itemset is frequent if it appears in more than a minimum number of transactions. The number of transactions containing an itemset is known as its “support”, and the minimum support (as a percentage of transactions) is a control parameter in the algorithm. The algorithm begins by finding the frequent single items. Then the algorithm generates all two-item sets from the frequent single items and determines which among them are frequent. From the collection of frequent pairs, Apriori forms candidate three-item subsets and determines which are frequent, and so on. The algorithm stops when either a maximum itemset size is reached, or when none of the candidate itemsets are frequent. In this way, the Apriori algorithm exploits the apriori-property: for an itemset to be frequent, all of its proper subsets must also be frequent. At each step the problem is reduced to only the frequent subsets.
In the second stage, the algorithm generates association rules. These are of the form, XY (read, "if X, then Y"), where Y and X are disjoint frequent itemsets. The confidence measure associated with the rule is defined as the proportion of transactions containing X that also contain Y. Denote the support of X (the number of transactions containing X) as SX, and SZ is the support of Z = X∪Y. The confidence of the rule XY is the ratio, SZ/SX. Note that the confidence ratio is the conditional probability
where P[XY] denotes the probability of both X and Y. The probability of an itemset X is estimated by SX/N, where N is the total number of transactions.
Another measure of the strength of the association is known as the lift, which is the ratio (SZN) / (SXSY). Lift values close to 1.0 suggest the sets are independent, and that they occur together by chance. Large lift values indicate a strong association. A minimum confidence threshold and a lift threshold can be specified.
Data Structures
The data structures output by imsls_f_apriori are described below. (For imsls_d_apriori, the structure names are Imsls_d_apriori_itemsets, Imsls_d_association_rules, and Imsls_d_rule_components where type float becomes double).
Structure definitions are provided for informational purposes and may be subject to change.
Table 13.35 — Imsls_f_apriori_itemsets
Field
Description
intn_itemsets
Length of array itemsets containing the Imsls_apriori_items structures.
Imsls_apriori_items*itemsets
Array of Imsls_apriori_items structures containing the set of frequent items and the support for that set.
intn_trans
Number of transactions.
intmax_num_products
Maximum number of products.
intmax_set_size
Maximum itemset size.
floatmin_pct_support
Minimum percentage of transactions.
Table 13.36 — Imsls_apriori_items
Field
Description
intn_items
Length of items.
int*items
Array containing the set of frequent items.
intsupport
The number of transactions in which the item appears.
Table 13.37 — Imsls_f_association_rules
Field
Description
intn_rules
Length of array rules containing the Imsls_f_rule_components structures.
Imsls_f_rule_components*rules
Array containing the association rules.
Table 13.38 — Imsls_f_rule_components
Field
Description
intn_x
Length of x.
int*x
Array containing the X components of the association rule.
intn_y
Length of y.
int*y
Array containing the Y components of the association rule.
intsupport[3]
Support for Z, X and Y components of the association rule.
floatconfidence
Confidence of the association rule.
floatlift
Lift of the association rule.
Example
This example applies Apriori to find the frequent itemsets and strong association rules. The data are 50 transactions involving five different product IDs. The minimum support percentage is set to 0.30, giving a minimum required support of 15 transactions.