Vasudha Bhatnagar (University of Delhi, India), Anamika Gupta (University of Delhi, India) and Naveen Kumar (University of Delhi, India)

DOI: 10.4018/978-1-59904-849-9.ch012

Chapter Preview

TopLet *I = {i _{1}, i_{2},…, i_{n}}* denote a set of items and

An item-set having support greater than the user specified support threshold (ms) is known as *frequent item-set.*

An *association rule* is an implication of the form *X →Y* [*Support, Confidence*] where *X* ⊂ *I, Y*⊂ *I* and *X*∩*Y =*∅, where *Support* and *Confidence* are rule evaluation metrics. *Support* of a rule *X → Y* in *D* is ‘S'’ if S% of transactions in *D* contain *X* ∪ *Y*. It is computed as:

*Support* indicates the prevalence of a rule. In a typical market basket analysis application, rules with very low support values represent rare events and are likely to be uninteresting or unprofitable. *Confidence* of a rule measures its strength and provides an indication of the reliability of prediction made by the rule. A rule *X → Y* has a confidence ‘C'‘ in *D* if C % of transactions in *D* that contain *X*, also contain *Y*. Confidence is computed, as the conditional probability of *Y* occuring in a transaction, given *X* is present in the same transaction, i.e.

Frequent Closed Item-Set: An item-set X is a closed item-set if there exists no item-set X’ such that i. X’ is a proper superset of X, ii. Every transaction containing X also contains X’. A closed item-set X is frequent if its support exceeds the given support threshold.

Generator Item-Set: A generator p of a closed item-set c is one of the smallest item-sets such that h(p) = c.

Association Rule: An Association rule is an implication of the form X?Y where X ? I, Y? I and XnY =Ø, I denotes the set of items.

Galois Connection: Let D = (O,I,R) be a data mining context where O and I are finite sets of objects (transactions) and items respectively. R ? O x I is a binary relation between objects and items. For O ? O, and I ? I, we define as shown in Exhibit C. f(O) associates with O the items common to all objects o ? O and g(I) associates with I the objects related to all items i ? I. The couple of applications (f,g) is a Galois connection between the power set of O (i.e. 2O) and the power set of I (i.e. 2I). The operators h = f o g in 2I and h’ = g o f in 2o are Galois closure operators. An item-set C ? I from D is a closed item-set iff h(C) = C.

Formal Concept: A formal context K = (G,M,I) consists of two sets G (objects) and M (attributes) and a relation I between G and M. For a set A?G of objects, A’={meM | gIm for all geA} (the set of all attributes common to the objects in A). Correspondingly, for a set B of attributes we define, B’ = {geG | gIm for all meB} (the set of objects common to the attributes in B). A formal concept of the context (G,M,I) is a pair (A,B) with A?G,B?M, A’=B and B’=A, A is called the extent and B is the intent of the concept (A,B).

Data Mining: Extraction of interesting, non-trivial, implicit, previously unknown and potentially useful information or patterns from data in large databases.

Non-Redundant Association Rules: Let Ri denote the rule X1i?X2i, where X1,X2 ? I. Rule R1 is more general than rule R2 provided R2 can be generated by adding additional items to either the antecedent or consequent of R1. Rules having the same support and confidence as more general rules are the redundant association rules. Remaining rules are non-redundant rules.

Search this Book:

Reset