Spring 2009 CSC 466: Knowledge Discovery from Data Alexander Dekhtyar Data Mining: Mining Association Rules Definitions

Market Baskets. Consider a set I = {i1,..., im}. We call the elements of I, items. A market basket is any subset S of I: S ⊂ I. A market basket dataset or a set of market basket transactions is a collection T = {t1,..., tn} of market baskets. Association Rules. Let I be a set of items. An association rule is an implication of the form X − → Y, where X ⊂ I, Y ⊂ I and X ∩ Y = ∅. We refer to X and Y as itemsets. Support and confidence for association rules. Let I be a set of items and T = {t1,..., tn} be a market basket dataset. Let R: X − → Y be an association rule. The support ofR in the dataset T is the percentage of market baskets ti ∈ T which contain X ∪ Y: supportT (X − → Y) = |{ti ∈ T |X ∪ Y ⊆ ti}| n The confidence of R in the dataset T is the percentage of market baskets ti ∈ T that contain X, which also contain Y: confidenceT (X − → Y) = |{ti ∈ T |X ∪ Y ⊆ ti}| |{tj ∈ T |X ⊆ tj}