Pattern discovery normally carries with it a high risk of finding spurious patterns, patterns that appear to capture interesting associations, but do so only due to chance. The use of statistical tests with corrections for multiple comparisons, such as the Unsound Filter, can guard against this risk. However, the better such measures guard against the risk of finding spurious rules, the greater the risk that they will discard sound rules. Because of the large number of potential patterns that Magnum Opus must consider, adequate control of the risk of finding spurious patterns may entail discarding most patterns that are considered.
Magnum Opus provides unique facilities for statistically sound exploratory data mining. In addition to the Unsound Filter, it also supports holdout evaluation. This requires the use of two sets of data: the exploratory data and the holdout data. The exploratory data are used to find a set of patterns that satisfy the search settings selected by the user. The holdout data are then used to evaluate the risk of these patterns being spurious. Because only a limited set of patterns is evaluated on the holdout data it is possible to provide strong control over the risk of accepting spurious patterns without undue risk of discarding sound rules and itemsets.
The appropriate criteria for assessing whether or not a rule or itemset should be considered spurious will vary from application to application. Magnum Opus provides a suite of holdout evaluation tests from which the user can select. All selected tests are applied to each rule or itemset and any rule or itemset that fails any test is identified as having failed holdout evaluation.
The user also specifies a significance level to be used with the holdout tests. This is adjusted using a Holm adjustment for the number of distinct patterns being tested. This is similar to, but more powerful than, the better known Bonferroni adjustment adjustment. The resulting critical value is applied to all holdout statistical tests. This ensures that the probability of any rule or itemset being accepted if any of the null hypotheses for the tests holds is no higher than the user-specified significance level. See Discovering Significant Patterns for more details. Note that any two rules X -> Y and Y -> X (that is, two rules in which the LHS and RHS are swapped) are counted as a single pattern unless holdout tests are applied for minimum lift, strength or coverage.
The following holdout evaluation tests are supported for rules.
|
Test |
Null Hypothesis |
Statistical technique |
|
Minimum Coverage |
Coverage ≤ Min Coverage |
Binomial sign test |
|
Minimum Support |
Support ≤ Min Support |
Binomial sign test |
|
Minimum Strength |
Strength ≤ Min Strength |
Binomial sign test |
|
Minimum Lift |
Lift ≤ Min Lift |
Binomial sign test |
|
Minimum Leverage |
Leverage ≤ Min Leverage |
Binomial sign test |
| Positive correlation | Support ≤ Coverage × RHS_Coverage | Fisher exact test |
|
Improvement over generalizations |
Strength ≤ the maximum Strength of any generalization of the current rule |
Fisher exact test |
|
Partial with respect to specializations |
There exists another rule GLHS -> RHS in the set of best rules, that has not been rejected by holdout evaluation, that is a specialization of the current rule, and such that the LHS and RHS of the current rule are conditionally independent given the negation of GLHS. |
Fisher exact test |
The tests to be applied can be selected using the Rule Holdout Evaluation Settings Dialog.
The following holdout evaluation tests are supported for itemsets.
|
Test |
Null Hypothesis |
Statistical technique |
|
Minimum Coverage |
Coverage ≤ Min Coverage |
Binomial sign test |
|
Minimum Leverage |
Leverage ≤ Min Leverage |
Binomial sign test |
|
Improvement over generalizations |
Coverage ≤ the maximum of coverage(A) × coverage(B) for any partition of the current itemset into two subsets A and B. |
Fisher exact test |
| Self-sufficient | Coverage ≤ the maximum of coverage(A) × coverage(B) for any partition of the current itemset into two subsets A and B within the set of cases not covered by the difference between the current itemset and any of its productive supersets. | Fisher exact test |
The tests to be applied can be selected using the Itemsets Holdout Evaluation Settings Dialog.
Magnum Opus prints rules and itemsets that fail one or more holdout test after those that pass the holdout evaluation process. A summary line shows the adjusted critical value. Each rule or itemset is then listed. Following each rule, a summary line presents the following information:
For itemsets, the summary line contains the holdout coverage only.
The holdout evaluation summary line is followed by a further line summarizing the result of each test that the rule or itemset failed.
Note, it is often valuable to use holdout evaluation with the Filter-out Insignificant filter. Doing so prevents many patterns that are unlikely to pass the holdout evaluation from being considered, thereby increasing the number of patterns that do pass. It will not generally be a good idea to use holdout evaluation with the Filter-out Unsound, as each one strictly controls the risk of false discoveries without the need for the other and the application of both processes is likely to greatly reduce the number of patterns that are accepted compared to using only one or the other.
If a single data set is to be sampled to form the exploratory and holdout sets, we recommend using a 50% sample so as to create equal size exploratory and holdout sets. Reducing the amount of exploratory data is likely to lead to interesting rules or itemsets being overlooked. Reducing the amount of holdout data increases the risk of rejecting non-spurious rules and itemsets.
If holdout evaluation is to be used, the holdout data must be specified during data import. See Data Import.
For more information on Holdout Evaluation see Discovering Significant Patterns.