]> Agnieszka.Lawrynowicz@cs.put.poznan.pl,Petra.Kralj.Novak@ijs.si,Anze.Vavpetic@ijs.si,Melanie.Hilario PD.owl. Agnieszka.Lawrynowicz CURRENT VERSION; v0.1.1 (14 Dec.2010). Subgroup descriptions are descriptions of groups of examples in a dataset. Most comonly they are conjunctions of attribute-values, followed by a propery of interest. AssociationRuleDiscoveryAlgorithm discovers patterns in the form of rules that is of the implications X->Y, where X, and Y typically represent sets of items (itemsets). Such rule states: when X occurs, Y occurs with certain probability. M. Morzy. "Efficient Mining of Dissociation Rules", 8th International Conference on Data Warehousing and Knowledge Discovery DaWaK 2006 (LNCS 4081), Krakow, Poland, September 4-8, 2006. Dissociation rules are generated from dissociative itemsets. An itemset X is dissociative if it can be divided into two disjoint frequent itemsets (Y and Z), but the support of the itemset X is very low. Practical interpretation of a dissociation itemset is such that subsets Y and Z individually appear in the transaction database D_T frequently, but they almost never appear together, which suggests that Y and Z are somehow conflicting sets of items. M. Morzy. "Efficient Mining of Dissociation Rules", 8th International Conference on Data Warehousing and Knowledge Discovery DaWaK 2006 (LNCS 4081), Krakow, Poland, September 4-8, 2006. Dissociation rules are generated from dissociative itemsets. An itemset X is dissociative if it can be divided into two disjoint frequent itemsets (Y and Z), but the support of the itemset X is very low. Practical interpretation of a dissociation itemset is such that subsets Y and Z individually appear in the transaction database D_T frequently, but they almost never appear together, which suggests that Y and Z are somehow conflicting sets of items. M. Morzy. "Efficient Mining of Dissociation Rules", 8th International Conference on Data Warehousing and Knowledge Discovery DaWaK 2006 (LNCS 4081), Krakow, Poland, September 4-8, 2006. Dissociation rule in the form of Y-/->Z or Z-/->Y is generated from itemset X if X is a dissociation itemset that is if: i) support(X) < epsilon, where epsilon is a user-defined threshold representing the highest amount of noise in the data allowed, ii) there exists itemsets Y, Z in a set of transactions (or frequent itemsets) such that the set union of itemsets Y and Z is the itemset X. A set of transactions in the form {TID: itemset}, where TID is a transaction id and itemset is the set of items contained in transaction TID. ItemSetDiscoveryAlgorithm discovers sets of items that are related (interacting or dependent). Classically these are sets of items that appear frequently together in one transaction in a transactional data base. But apart from the measure of 'frequency' also other measures can be employed to assess the relationship between items and item sets. SequantialAssociationDiscoveryAlgorithm mines for patterns that have the form of sequences of object (e.g. items, events). Classicially these are the sequences that appear frequently in a dataset. A collection of ordered (stored sequentially) data items or events (for example customer shopping sequences, Web click streams, biological sequences). A subgroup based model is a model which is based on a set of subgroup descriptions. To create a predictive model from a set of subgroup descriptions, the algorithm should include a decision strategy that resolves conflicts when several SD patterns/rules are applicable. A commonly used decision strategy is voting. A substitutive itemset represents items, which can be used interchengeably in many different contexts. A real-world example of a substitutive itemset that could be mined in a retail database is the itemset {cocacola, pepsi}. A set of transactions, where each transaction includes a unique transaction identity number, and a collection of items making up a transaction (such as items purchased in a store). A trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. All the descendants of a node have a common prefix associated with that node, and the root is associated with the empty value. Values are normally not associated with every node, only with leaves and some inner nodes that correspond to keys of interest. The term trie comes from "retrieval." A set of transactions containing items in vertical data format of the form of a set of rows: {item: TID_set}, where TID_set is a set of transactions which contain "item". Called also A-priori property. It says that a set satisfies the support constraint only if all its subsets satisfy this support constraint. Agrawal R., Srikant R. Fast Algorithms for Mining Association Rules. In Proc. 20th Int. Conf. Very Large Data Bases, VLDB, pp. 487–499. Morgan Kaufmann,1994. Iteratively reduces the minimum support until it finds the required number of rules with the given minimum confidence. Bing Liu, Wynne Hsu, Yiming Ma: Integrating Classification and Association Rule Mining. In: Fourth International Conference on Knowledge Discovery and Data Mining, 80-86, 1998. The CN2-SD algorithm is based on the CN2 algorithm. Its idea is in finding the best complex based on current example set and rules. After finding the best complex (subgroup description), example weights of covered examples are multiplicatively decreased and the times covered variable for covered examples is increased. If the value of the times covered variable is greater than a user defined parameter, the example is removed from example set. The stopping criterion is reached when no complex with positive weighted weighted relative accuracy (wWRAcc) can be found. 1.0 Specifies how many times an example is covered. R. Agrawal, T. Imielinski, and A. Swami. Mining associations between sets of items in large databases. In Proc. of the ACM SIGMOD Int'l Conference on Management of Data, pages 207-216, Washington D.C., May 1993. Confidence is the ratio of the number of transactions that include all items in the consequent as well as the antecedent (the support) to the number of transactions that include all items in the antecedent of the association rule. $conf(X\Rightarrow Y) = supp(X \cup Y) / supp(X)$ P. A. Flach, N. Lachiche (1999). Confirmation-Guided Discovery of first-order rules with Tertius. Machine Learning. 42:61-95. $conv(X\Rightarrow Y) = \frac{1-supp(Y)}{1-conf(X\Rightarrow Y)}$ The ratio of the expected frequency that antecedent X of the rule occurs without a consequent Y of the rule (the frequency that the rule makes an incorrect prediction) if X and Y were independent divided by the observed frequency of incorrect predictions. Sergey Brin, Rajeev Motwani, Jeffrey D. Ullman, and Shalom Tsur. Dynamic itemset counting and implication rules for market basket data. In SIGMOD 1997, Proceedings ACM SIGMOD International Conference on Management of Data, pages 255-264, Tucson, Arizona, USA, May 1997. $coverage(X \Rightarrow Y) = supp(X) = P(X)$ Coverage of a rule is sometimes called antecedent support. It measures how often a rule of the form X -> Y is applicable in a database. Alternatively coverage may also be measured in terms of a covering set. For any item i the covering set CS of the item is the collection of all itemsets in the transaction database D_T, with which the given item i forms itemsets. M. Morzy. "Efficient Mining of Dissociation Rules", 8th International Conference on Data Warehousing and Knowledge Discovery DaWaK 2006 (LNCS 4081), Krakow, Poland, September 4-8, 2006. M. Morzy. "Efficient Mining of Dissociation Rules", 8th International Conference on Data Warehousing and Knowledge Discovery DaWaK 2006 (LNCS 4081), Krakow, Poland, September 4-8, 2006. Dissociation rule in the form of Y-/->Z or Z-/->Y is generated from itemset X if X is a dissociation itemset that is if: i) support(X) < epsilon, where epsilon is a user-defined threshold representing the highest amount of noise in the data allowed, ii) there exists itemsets Y, Z in a set of transactions (or frequent itemsets) such that the set union of itemsets Y and Z is the itemset X. Mohammed J. Zaki and Karam Gouda, Fast Vertical Mining Using Diffsets. In 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Aug 2003. Mohammed J. Zaki, Scalable Algorithms for Association Mining. IEEE Transactions on Knowledge and Data Engineering, 12(3):372-390, 2000. J. Han, J. Pei, Y. Yin, "Mining frequent patterns without candidate generation", Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, Dallas, Texas, United States, 1-12, 2000. Absolute (not relative) occurrence frequency of a pattern X (a set of items) is the number of transactions containing X in a database. Srikant R., Agrawal R. (1996). Mining Sequential Patterns: Generalizations and Performance Improvements. The Generalization Quotient is a rule quality estimation function. The higher the g parameter, the more general rules are prefered. It is defined as: q_g = TP / (FP + g) A set of transactions in the form {TID: itemset}, where TID is a transaction id and itemset is the set of items contained in transaction TID. Piatetsky-Shapiro, G., Discovery, analysis, and presentation of strong rules. Knowledge Discovery in Databases, 1991: p. 229-248. $leverage(X\Rightarrow Y) = supp(X\Rightarrow Y)-supp(Y)\times supp(X)$ Leverage measures the difference of rule antecedent X and consequent Y appearing together in the data set and what would be expected if X and Y were statistically dependent. The ratio of the observed support to that expected if antecedent X of a rule and consequent Y were independent. S. Brin, R. Motwani, J. D. Ullman, and S. Tsur. Dynamic itemset counting and implication rules for market basket data. In Proc. of the ACM SIGMOD Int'l Conf. on Management of Data (ACM SIGMOD '97), pages 265-276, 1997. $lift(X\Rightarrow Y) = \frac{supp(X \cup Y)}{supp(Y)\times supp(X)}$ 0.0 1.0 0.0 0.0005 1.0 A user-defined threshold representing the highest amount of noise in the data allowed. Tobias Scheffer: Finding Association Rules That Trade Support Optimally against Confidence. In: 5th European Conference on Principles of Data Mining and Knowledge Discovery, 424-435, 2001. Let D be a database whose individual records r are generated by a static process P, X->Y be an association rule. The predictive accuracy c(X->Y]) = Pr[r satisfies Y|r satisfies X] is the conditional probability of Y ⊆ r given that X ⊆ r when the distribution of r is governed by P. Tobias Scheffer: Finding Association Rules That Trade Support Optimally against Confidence. In: 5th European Conference on Principles of Data Mining and Knowledge Discovery, 424-435, 2001. Desired number of most predictive association rules. Each rule is equiped with a distribution of classes of examples that it covers. When predicting the class of a new example, a voting mechanism is used to obtain the final prediction: the class distributions attached to the rules are summed to determine the most frequent class. If no rule fires, a default rule is invoked which predicts the majority class of uncovered training examples. 0.0 0.0005 1.0 The user-defined threshold of minimum relevance of the recommended item r_i to the recommendation context x. The historical context of the recommendation, that is for example the set of products previously purchased by a customer. 1.0 3 The user-determined the maximum size of the recommendation itemset. An item which constitutes the current context of the recommendation. Given the itemset H representing the history context (e.g. the set of products previously purchased by a customer). Given an item x which constitutes the current context of the recommendation. An itemset R is a recommendation itemset if: 1) it has the size k (specified by the user) 2) any item r_i from R does not appear in H 3) every item r_i in R is frequent 4) support({x, r_i}) > alpha (where alpha is the user-defined threshold of minimum relevance of the recommended item r_i to the recommendation context x) 5) frequent items are added to the recommendation itemset in the decreasing order of the coverage measure, which is recomputed after every iteration (for instance, after adding the first item r_1 to the recommenation set, the next item to be added is the item r_2 which has the highest value of coverage in the collection of frequent itemsets L diminished by those frequent itemsets that contain r_1. Analogously, in the third iteration an item r_3 is selected which has the highest coverage in the collection of frequent itemsets L diminished by frequent itemsets containing either r_1 or r_2. The main rationale behind the above procedure is to construct such a recommendation itemset, which covers the largest possible space of available items. The condition 3) guarantees that the generated recommendations are valid in the transactional database D_T, i.e., that there exist transactions which contain both x and r_i. The SD algorithm is a beam search based algorithm for searching for the best rule by increasingly adding each feature to current rules in the beam. As a feature is added to a rule in the beam, we calculate its support and relevancy in respect to other rules in the new beam and its rule quality. If its support is greater than the defined minimal support and the rule is relevant w.r.t. the other rules in the beam and there exists another rule in new beam, which has lower quality, the worst rule in the beam is replaced by the new rule. The SD algorithm has the following parameters: beam size, g parameter - called generalization parameter, which is used to calculate rule quality, minimal support for each subgroup. 1.0 0.0 Is a measure of generality of a rule and is defined as: TP / (FP + g) where TP is the number of true positives and FP the number of false positives. A collection of ordered (stored sequentially) data items or events (for example customer shopping sequences, Web click streams, biological sequences). A subgroup based model is a model which is based on a set of subgroup descriptions. To create a predictive model from a set of subgroup descriptions, the algorithm should include a decision strategy that resolves conflicts when several SD patterns/rules are applicable. A commonly used decision strategy is voting. 0.0 0.7 1.0 A minimum percent of common items that covering sets of items x and y share. Guarantees that both items (x and y) appear in the database D_T in a similar context, i.e., that items x and y appear in the same patterns independently of each other. Remark: covering set is the set of all discovered itemsets in the database D_T, with which the given item i forms itemsets. A two-element itemset {x, y} is a substitutive itemset, if: -both elements are frequent, -support({x, y}) < epsilon, where epsilon is a user-defined threshold representing the highest amount of noise in the data allowed, and - covering sets of items x and y share at least mincommon percent of common items. Remark: covering set is the set of all discovered itemsets in the database D_T, with which the given item i forms itemsets. A substitutive itemset represents two items, which can be used interchengeably in many different contexts. Both items appear in the database D_T in a similar context, i.e., that items x and y appear in the same frequent patterns independently of each other. The constraint on cooccurrence of x and y serves the puropse of pruning pairs of items that are functionally dependent (e.g. the item y is a popular add-on to the item x). A real-world example of a substitutive itemset that could be mined in a retail database is the itemset {cocacola, pepsi}. A substitutive itemset represents items, which can be used interchengeably in many different contexts. A real-world example of a substitutive itemset that could be mined in a retail database is the itemset {cocacola, pepsi}. The support is the number of transactions that include all items in the antecedent and consequent parts of the association rule. R. Agrawal, T. Imielinski, and A. Swami. Mining associations between sets of items in large databases. In Proc. of the ACM SIGMOD Int'l Conference on Management of Data, pages 207-216, Washington D.C., May 1993. P. A. Flach, N. Lachiche (1999). Confirmation-Guided Discovery of first-order rules with Tertius. Machine Learning. 42:61-95. A set of transactions, where each transaction includes a unique transaction identity number, and a collection of items making up a transaction (such as items purchased in a store). A trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. All the descendants of a node have a common prefix associated with that node, and the root is associated with the empty value. Values are normally not associated with every node, only with leaves and some inner nodes that correspond to keys of interest. The term trie comes from "retrieval." A set of transactions containing items in vertical data format of the form of a set of rows: {item: TID_set}, where TID_set is a set of transactions which contain "item". Trades-off between rule coverage and precision. It is defined as: wWRAcc'(X->Y) = n'(X)/N' ( n'(XY)/n'(X) - n(Y)/N) ) n'(X)/N' is the rule coverage, n'(XY)/n'(X) is the rule accuracy and n(Y)/N is the prior probability of class Y.