This chapter considers the problem of “conditional contrast pattern mining.” It is related to contrast mining, where one considers the mining of patterns/models that contrast two or more datasets, classes, conditions, time periods, and so forth. Roughly speaking, conditional contrasts capture situations where a small change in patterns is associated with a big change in the matching data of the patterns. More precisely, a conditional contrast is a triple (B, F1, F2) of three patterns; B is the condition/context pattern of the conditional contrast, and F1 and F2 are the contrasting factors of the conditional contrast. Such a conditional contrast is of interest if the difference between F1 and F2 as itemsets is relatively small, and the difference between the corresponding matching dataset of B?F1 and that of B?F2 is relatively large. It offers insights on “discriminating” patterns for a given condition B. Conditional contrast mining is related to frequent pattern mining and analysis in general, and to the mining and analysis of closed pattern and minimal generators in particular. It can also be viewed as a new direction for the analysis (and mining) of frequent patterns. After formalizing the concepts of conditional contrast, the chapter will provide some theoretical results on conditional contrast mining. These results (i) relate conditional contrasts with closed patterns and their minimal generators, (ii) provide a concise representation for conditional contrasts, and (iii) establish a so-called dominance-beam property. An efficient algorithm will be proposed based on these results, and experiment results will be reported. Related works will also be discussed.
TopIntroduction
This chapter formalizes the notions of conditional contrast patterns (C2Ps) and conditional contrast factors (C2Fs), and studies the associated data mining problem. These concepts are formulated in the abstract space of patterns and their matching datasets.
Roughly speaking, C2Ps are aimed at capturing situations or contexts (the conditional contrast bases or C2Bs) where small changes in patterns to the base make big differences in matching datasets. The small changes are the C2Fs and their cost is measured by the average number of items in the C2Fs. The big differences are the differences among the matching datasets of the C2Fs; we use the average size of the differences to measure the impact (of the C2Fs). Combining cost and impact allows us to find those C2Fs which are very effective difference makers. In formula, a C2P is a pair 〈B, {F1, ..., Fk}〉, where k >1, and B and Fi are itemsets; B is the C2B and the Fi’s are the C2Fs.
For k=2, Figure 1 (a) shows that F1 and F2 are small itemset changes to B. Panel (b) shows that the matching datasets of B∪F1 and B∪F2 are significantly different from each other. The k>2 case is similar.1
Figure 1. Conditional contrast patterns/factors: (a) F1 and F2 are small itemset changes to B, and (b) the matching dataset of B ∪F1 is very different from that of B ∪F2.
We use the impact-to-cost ratio, defined as the impact divided by the cost, as well as other measures, to evaluate the goodness of C2Ps and C2Fs. Observe that one can also consider other factors involving class, financial benefit or utility in defining this ratio.
Example 1.1C2Ps can give new insights to many, especially medical/business, applications. We illustrate the concepts using a medical dataset. From a microarray gene expression dataset used in acute lymphoblastic leukemia subtype study [Yeoh et al, 2002], we got a number of C2Ps, including the following2:
PL=〈{gene-38319-at≥15975.6}, {{gene-33355-at < 10966}, {gene-33355-at ≥ 10966}}〉
Here {gene-38319-at ≥15975.6} is the C2B, {gene-33355-at < 10966} is F1, and {gene-33355-at ≥ 10966} is F2. This C2P says that the samples that satisfy gene-38319-at ≥ 15975.6 (which are the samples of B-lineage type) are split into two disjoint parts: the first part are the E2A-PBX1 subtype (18 samples), and the other part are the other B-lineage subtypes (169 samples). Expressed as a rule, PL says: Among the samples satisfying gene-38319-at ≥ 15975.6, if the expression of gene-33355-at is less than 10966, then the sample is E2A-PBX1; otherwise, it belongs to the other types of B-lineage.
This C2P nicely illustrates how the regulation of gene-38319-at and gene-33355-at splits patients into different acute lymphoblastic leukemia subtypes. □
Typically, an individual C2F of a C2P does not make the big differences between matching datasets; the differences are made by two or more C2Fs of the C2P. For example, in a C2P with two C2Fs F1 and F2, the set of items in F1∪F2 makes the differences.