Association discovery encompasses a broad family of related tasks that identify key interactions between entities or elements within data. These include association mining, pattern mining, association rule discovery, subgroup discovery, emerging pattern discovery and contrast discovery.
My pioneering association discovery techniques seek the most useful associations, rather than applying the minimum-support constraint more commonly used in the field. Many of these techniques are included in my Magnum Opus software, which is now incorporated in BigML. Magnum Opus has been widely used in scientific research.
Due to the large numbers of patterns that are considered in association discovery, most techniques suffer large risk of type-1 error. That is, they are likely to find patterns that appear interesting only due to chance artifacts of the process by which the sample data were generated. Most attempts to control this risk do so at the cost of high risk of type-2 error. That is, they are likely to falsely reject non-spurious patterns. I have pioneered strategies for statistically sound pattern discovery, strictly controlling type-1 error during association discovery without the level of risk of type-2 error suffered by previous approaches.
The OPUSMiner statistically sound itemset discovery software can be downloaded here. An R package is available here.
The Skopus statistically sound sequential pattern discovery software can be downloaded here.
An implementation of impact rules can be downloaded here: https://github.com/501856869/Significant_impact_rule.
ACM SIGKDD 2014 Tutorial on Statistically Sound Pattern Discovery, with Wilhelmiina Hämäläinen.
Publications
Boley, Mario; Teshuva, Simon; Bodic, Pierre Le; Webb, Geoffrey I
Better Short than Greedy: Interpretable Models through Optimal Rule Boosting
Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pp. 351-359, SIAM 2021.
@inproceedings{boley2021better,
title = {Better Short than Greedy: Interpretable Models through Optimal Rule Boosting},
author = {Mario Boley and Simon Teshuva and Pierre Le Bodic and Geoffrey I Webb},
url = {https://arxiv.org/abs/2101.08380},
year = {2021},
date = {2021-01-01},
booktitle = {Proceedings of the 2021 SIAM International Conference on Data Mining (SDM)},
pages = {351-359},
organization = {SIAM},
abstract = {Rule ensembles are designed to provide a useful trade-off between predictive accuracy and model interpretability. However, the myopic and random search components of current rule ensemble methods can compromise this goal: they often need more rules than necessary to reach a certain accuracy level or can even outright fail to accurately model a distribution that can actually be described well with a few rules. Here, we present a novel approach aiming to fit rule ensembles of maximal predictive power for a given ensemble size (and thus model comprehensibility). In particular, we present an efficient branch-and-bound algorithm that optimally solves the per-rule objective function of the popular second-order gradient boosting framework. Our main insight is that the boosting objective can be tightly bounded in linear time of the number of covered data points. Along with an additional novel pruning technique related to rule redundancy, this leads to a computationally feasible approach for boosting optimal rules that, as we demonstrate on a wide range of common benchmark problems, consistently outperforms the predictive performance of boosting greedy rules.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Rule ensembles are designed to provide a useful trade-off between predictive accuracy and model interpretability. However, the myopic and random search components of current rule ensemble methods can compromise this goal: they often need more rules than necessary to reach a certain accuracy level or can even outright fail to accurately model a distribution that can actually be described well with a few rules. Here, we present a novel approach aiming to fit rule ensembles of maximal predictive power for a given ensemble size (and thus model comprehensibility). In particular, we present an efficient branch-and-bound algorithm that optimally solves the per-rule objective function of the popular second-order gradient boosting framework. Our main insight is that the boosting objective can be tightly bounded in linear time of the number of covered data points. Along with an additional novel pruning technique related to rule redundancy, this leads to a computationally feasible approach for boosting optimal rules that, as we demonstrate on a wide range of common benchmark problems, consistently outperforms the predictive performance of boosting greedy rules.
Hamalainen, Wilhelmiina; Webb, Geoffrey I.
A tutorial on statistically sound pattern discovery
Data Mining and Knowledge Discovery, vol. 33, no. 2, pp. 325-377, 2019, ISSN: 1573-756X.
@article{HamalainenWebb2019,
title = {A tutorial on statistically sound pattern discovery},
author = {Wilhelmiina Hamalainen and Geoffrey I. Webb},
url = {https://rdcu.be/bd2MI},
doi = {10.1007/s10618-018-0590-x},
issn = {1573-756X},
year = {2019},
date = {2019-03-01},
journal = {Data Mining and Knowledge Discovery},
volume = {33},
number = {2},
pages = {325-377},
abstract = {Statistically sound pattern discovery harnesses the rigour of statistical hypothesis testing to overcome many of the issues that have hampered standard data mining approaches to pattern discovery. Most importantly, application of appropriate statistical tests allows precise control over the risk of false discoveries\textemdashpatterns that are found in the sample data but do not hold in the wider population from which the sample was drawn. Statistical tests can also be applied to filter out patterns that are unlikely to be useful, removing uninformative variations of the key patterns in the data. This tutorial introduces the key statistical and data mining theory and techniques that underpin this fast developing field. We concentrate on two general classes of patterns: dependency rules that express statistical dependencies between condition and consequent parts and dependency sets that express mutual dependence between set elements. We clarify alternative interpretations of statistical dependence and introduce appropriate tests for evaluating statistical significance of patterns in different situations. We also introduce special techniques for controlling the likelihood of spurious discoveries when multitudes of patterns are evaluated. The paper is aimed at a wide variety of audiences. It provides the necessary statistical background and summary of the state-of-the-art for any data mining researcher or practitioner wishing to enter or understand statistically sound pattern discovery research or practice. It can serve as a general introduction to the field of statistically sound pattern discovery for any reader with a general background in data sciences.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Statistically sound pattern discovery harnesses the rigour of statistical hypothesis testing to overcome many of the issues that have hampered standard data mining approaches to pattern discovery. Most importantly, application of appropriate statistical tests allows precise control over the risk of false discoveries—patterns that are found in the sample data but do not hold in the wider population from which the sample was drawn. Statistical tests can also be applied to filter out patterns that are unlikely to be useful, removing uninformative variations of the key patterns in the data. This tutorial introduces the key statistical and data mining theory and techniques that underpin this fast developing field. We concentrate on two general classes of patterns: dependency rules that express statistical dependencies between condition and consequent parts and dependency sets that express mutual dependence between set elements. We clarify alternative interpretations of statistical dependence and introduce appropriate tests for evaluating statistical significance of patterns in different situations. We also introduce special techniques for controlling the likelihood of spurious discoveries when multitudes of patterns are evaluated. The paper is aimed at a wide variety of audiences. It provides the necessary statistical background and summary of the state-of-the-art for any data mining researcher or practitioner wishing to enter or understand statistically sound pattern discovery research or practice. It can serve as a general introduction to the field of statistically sound pattern discovery for any reader with a general background in data sciences.
Shi, Wenzhong; Zhang, Anshu; Webb, Geoffrey I.
Mining significant crisp-fuzzy spatial association rules
International Journal of Geographical Information Science, vol. 32, no. 6, pp. 1247-1270, 2018.
@article{doi:10.1080/13658816.2018.1434525,
title = {Mining significant crisp-fuzzy spatial association rules},
author = {Wenzhong Shi and Anshu Zhang and Geoffrey I. Webb},
url = {http://www.tandfonline.com/eprint/aMdSMrAGuEHsHWSzIuqm/full},
doi = {10.1080/13658816.2018.1434525},
year = {2018},
date = {2018-01-01},
journal = {International Journal of Geographical Information Science},
volume = {32},
number = {6},
pages = {1247-1270},
publisher = {Taylor \& Francis},
abstract = {Spatial association rule mining (SARM) is an important data mining task for understanding implicit and sophisticated interactions in spatial data. The usefulness of SARM results, represented as sets of rules, depends on their reliability: the abundance of rules, control over the risk of spurious rules, and accuracy of rule interestingness measure (RIM) values. This study presents crisp-fuzzy SARM, a novel SARM method that can enhance the reliability of resultant rules. The method firstly prunes dubious rules using statistically sound tests and crisp supports for the patterns involved, and then evaluates RIMs of accepted rules using fuzzy supports. For the RIM evaluation stage, the study also proposes a Gaussian-curve-based fuzzy data discretization model for SARM with improved design for spatial semantics. The proposed techniques were evaluated by both synthetic and real-world data. The synthetic data was generated with predesigned rules and RIM values, thus the reliability of SARM results could be confidently and quantitatively evaluated. The proposed techniques showed high efficacy in enhancing the reliability of SARM results in all three aspects. The abundance of resultant rules was improved by 50% or more compared with using conventional fuzzy SARM. Minimal risk of spurious rules was guaranteed by statistically sound tests. The probability that the entire result contained any spurious rules was below 1%. The RIM values also avoided large positive errors committed by crisp SARM, which typically exceeded 50% for representative RIMs. The real-world case study on New York City points of interest reconfirms the improved reliability of crisp-fuzzy SARM results, and demonstrates that such improvement is critical for practical spatial data analytics and decision support.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Spatial association rule mining (SARM) is an important data mining task for understanding implicit and sophisticated interactions in spatial data. The usefulness of SARM results, represented as sets of rules, depends on their reliability: the abundance of rules, control over the risk of spurious rules, and accuracy of rule interestingness measure (RIM) values. This study presents crisp-fuzzy SARM, a novel SARM method that can enhance the reliability of resultant rules. The method firstly prunes dubious rules using statistically sound tests and crisp supports for the patterns involved, and then evaluates RIMs of accepted rules using fuzzy supports. For the RIM evaluation stage, the study also proposes a Gaussian-curve-based fuzzy data discretization model for SARM with improved design for spatial semantics. The proposed techniques were evaluated by both synthetic and real-world data. The synthetic data was generated with predesigned rules and RIM values, thus the reliability of SARM results could be confidently and quantitatively evaluated. The proposed techniques showed high efficacy in enhancing the reliability of SARM results in all three aspects. The abundance of resultant rules was improved by 50% or more compared with using conventional fuzzy SARM. Minimal risk of spurious rules was guaranteed by statistically sound tests. The probability that the entire result contained any spurious rules was below 1%. The RIM values also avoided large positive errors committed by crisp SARM, which typically exceeded 50% for representative RIMs. The real-world case study on New York City points of interest reconfirms the improved reliability of crisp-fuzzy SARM results, and demonstrates that such improvement is critical for practical spatial data analytics and decision support.
Hamalainen, Wilhelmiina; Webb, Geoffrey I
Specious rules: an efficient and effective unifying method for removing misleading and uninformative patterns in association rule mining
Proceedings of the 2017 SIAM International Conference on Data Mining, pp. 309-317, SIAM 2017.
@inproceedings{HamalainenWebb17,
title = {Specious rules: an efficient and effective unifying method for removing misleading and uninformative patterns in association rule mining},
author = {Wilhelmiina Hamalainen and Geoffrey I Webb},
year = {2017},
date = {2017-01-01},
booktitle = {Proceedings of the 2017 SIAM International Conference on Data Mining},
pages = {309-317},
organization = {SIAM},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Petitjean, Francois; Li, Tao; Tatti, Nikolaj; Webb, Geoffrey I.
Skopus: Mining top-k sequential patterns under leverage
Data Mining and Knowledge Discovery, vol. 30, no. 5, pp. 1086-1111, 2016, ISSN: 1573-756X.
@article{PetitjeanEtAl16b,
title = {Skopus: Mining top-k sequential patterns under leverage},
author = {Francois Petitjean and Tao Li and Nikolaj Tatti and Geoffrey I. Webb},
url = {http://rdcu.be/tsDo},
doi = {10.1007/s10618-016-0467-9},
issn = {1573-756X},
year = {2016},
date = {2016-01-01},
journal = {Data Mining and Knowledge Discovery},
volume = {30},
number = {5},
pages = {1086-1111},
abstract = {This paper presents a framework for exact discovery of the top-k sequential patterns under Leverage. It combines (1) a novel definition of the expected support for a sequential pattern\textemdasha concept on which most interestingness measures directly rely\textemdashwith (2) Skopus: a new branch-and-bound algorithm for the exact discovery of top-k sequential patterns under a given measure of interest. Our interestingness measure employs the partition approach. A pattern is interesting to the extent that it is more frequent than can be explained by assuming independence between any of the pairs of patterns from which it can be composed. The larger the support compared to the expectation under independence, the more interesting is the pattern. We build on these two elements to exactly extract the k sequential patterns with highest leverage, consistent with our definition of expected support. We conduct experiments on both synthetic data with known patterns and real-world datasets; both experiments confirm the consistency and relevance of our approach with regard to the state of the art.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
This paper presents a framework for exact discovery of the top-k sequential patterns under Leverage. It combines (1) a novel definition of the expected support for a sequential pattern—a concept on which most interestingness measures directly rely—with (2) Skopus: a new branch-and-bound algorithm for the exact discovery of top-k sequential patterns under a given measure of interest. Our interestingness measure employs the partition approach. A pattern is interesting to the extent that it is more frequent than can be explained by assuming independence between any of the pairs of patterns from which it can be composed. The larger the support compared to the expectation under independence, the more interesting is the pattern. We build on these two elements to exactly extract the k sequential patterns with highest leverage, consistent with our definition of expected support. We conduct experiments on both synthetic data with known patterns and real-world datasets; both experiments confirm the consistency and relevance of our approach with regard to the state of the art.
Webb, Geoffrey I.; Petitjean, Francois
A multiple test correction for streams and cascades of statistical hypothesis tests
Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD-16, pp. 1255-1264, ACM Press, 2016.
@inproceedings{WebbPetitjean16,
title = {A multiple test correction for streams and cascades of statistical hypothesis tests},
author = {Geoffrey I. Webb and Francois Petitjean},
url = {http://dl.acm.org/authorize?N19100},
doi = {10.1145/2939672.2939775},
year = {2016},
date = {2016-01-01},
booktitle = {Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD-16},
pages = {1255-1264},
publisher = {ACM Press},
abstract = {Statistical hypothesis testing is a popular and powerful tool for inferring knowledge from data. For every such test performed, there is always a non-zero probability of making a false discovery, i.e.~rejecting a null hypothesis in error. Familywise error rate (FWER) is the probability of making at least one false discovery during an inference process. The expected FWER grows exponentially with the number of hypothesis tests that are performed, almost guaranteeing that an error will be committed if the number of tests is big enough and the risk is not managed; a problem known as the multiple testing problem. State-of-the-art methods for controlling FWER in multiple comparison settings require that the set of hypotheses be pre-determined. This greatly hinders statistical testing for many modern applications of statistical inference, such as model selection, because neither the set of hypotheses that will be tested, nor even the number of hypotheses, can be known in advance.
This paper introduces Subfamilywise Multiple Testing, a multiple-testing correction that can be used in applications for which there are repeated pools of null hypotheses from each of which a single null hypothesis is to be rejected and neither the specific hypotheses nor their number are known until the final rejection decision is completed.
To demonstrate the importance and relevance of this work to current machine learning problems, we further refine the theory to the problem of model selection and show how to use Subfamilywise Multiple Testing for learning graphical models.
We assess its ability to discover graphical models on more than 7,000 datasets, studying the ability of Subfamilywise Multiple Testing to outperform the state of the art on data with varying size and dimensionality, as well as with varying density and power of the present correlations. Subfamilywise Multiple Testing provides a significant improvement in statistical efficiency, often requiring only half as much data to discover the same model, while strictly controlling FWER.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Statistical hypothesis testing is a popular and powerful tool for inferring knowledge from data. For every such test performed, there is always a non-zero probability of making a false discovery, i.e.~rejecting a null hypothesis in error. Familywise error rate (FWER) is the probability of making at least one false discovery during an inference process. The expected FWER grows exponentially with the number of hypothesis tests that are performed, almost guaranteeing that an error will be committed if the number of tests is big enough and the risk is not managed; a problem known as the multiple testing problem. State-of-the-art methods for controlling FWER in multiple comparison settings require that the set of hypotheses be pre-determined. This greatly hinders statistical testing for many modern applications of statistical inference, such as model selection, because neither the set of hypotheses that will be tested, nor even the number of hypotheses, can be known in advance.
This paper introduces Subfamilywise Multiple Testing, a multiple-testing correction that can be used in applications for which there are repeated pools of null hypotheses from each of which a single null hypothesis is to be rejected and neither the specific hypotheses nor their number are known until the final rejection decision is completed.
To demonstrate the importance and relevance of this work to current machine learning problems, we further refine the theory to the problem of model selection and show how to use Subfamilywise Multiple Testing for learning graphical models.
We assess its ability to discover graphical models on more than 7,000 datasets, studying the ability of Subfamilywise Multiple Testing to outperform the state of the art on data with varying size and dimensionality, as well as with varying density and power of the present correlations. Subfamilywise Multiple Testing provides a significant improvement in statistical efficiency, often requiring only half as much data to discover the same model, while strictly controlling FWER.
This paper introduces Subfamilywise Multiple Testing, a multiple-testing correction that can be used in applications for which there are repeated pools of null hypotheses from each of which a single null hypothesis is to be rejected and neither the specific hypotheses nor their number are known until the final rejection decision is completed.
To demonstrate the importance and relevance of this work to current machine learning problems, we further refine the theory to the problem of model selection and show how to use Subfamilywise Multiple Testing for learning graphical models.
We assess its ability to discover graphical models on more than 7,000 datasets, studying the ability of Subfamilywise Multiple Testing to outperform the state of the art on data with varying size and dimensionality, as well as with varying density and power of the present correlations. Subfamilywise Multiple Testing provides a significant improvement in statistical efficiency, often requiring only half as much data to discover the same model, while strictly controlling FWER.
Zhang, Anshu; Shi, Wenzhong; Webb, Geoffrey I.
Mining significant association rules from uncertain data
Data Mining and Knowledge Discovery, vol. 30, no. 4, pp. 928-963, 2016.
@article{ZhangEtAl16,
title = {Mining significant association rules from uncertain data},
author = {Anshu Zhang and Wenzhong Shi and Geoffrey I. Webb},
doi = {10.1007/s10618-015-0446-6},
year = {2016},
date = {2016-01-01},
journal = {Data Mining and Knowledge Discovery},
volume = {30},
number = {4},
pages = {928-963},
publisher = {Springer},
abstract = {In association rule mining, the trade-off between avoiding harmful spurious rules and preserving authentic ones is an ever critical barrier to obtaining reliable and useful results. The statistically sound technique for evaluating statistical significance of association rules is superior in preventing spurious rules, yet can also cause severe loss of true rules in presence of data error. This study presents a new and improved method for statistical test on association rules with uncertain erroneous data. An original mathematical model was established to describe data error propagation through computational procedures of the statistical test. Based on the error model, a scheme combining analytic and simulative processes was designed to correct the statistical test for distortions caused by data error. Experiments on both synthetic and real-world data show that the method significantly recovers the loss in true rules (reduces type-2 error) due to data error occurring in original statistically sound method. Meanwhile, the new method maintains effective control over the familywise error rate, which is the distinctive advantage of the original statistically sound technique. Furthermore, the method is robust against inaccurate data error probability information and situations not fulfilling the commonly accepted assumption on independent error probabilities of different data items. The method is particularly effective for rules which were most practically meaningful yet sensitive to data error. The method proves promising in enhancing values of association rule mining results and helping users make correct decisions.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
In association rule mining, the trade-off between avoiding harmful spurious rules and preserving authentic ones is an ever critical barrier to obtaining reliable and useful results. The statistically sound technique for evaluating statistical significance of association rules is superior in preventing spurious rules, yet can also cause severe loss of true rules in presence of data error. This study presents a new and improved method for statistical test on association rules with uncertain erroneous data. An original mathematical model was established to describe data error propagation through computational procedures of the statistical test. Based on the error model, a scheme combining analytic and simulative processes was designed to correct the statistical test for distortions caused by data error. Experiments on both synthetic and real-world data show that the method significantly recovers the loss in true rules (reduces type-2 error) due to data error occurring in original statistically sound method. Meanwhile, the new method maintains effective control over the familywise error rate, which is the distinctive advantage of the original statistically sound technique. Furthermore, the method is robust against inaccurate data error probability information and situations not fulfilling the commonly accepted assumption on independent error probabilities of different data items. The method is particularly effective for rules which were most practically meaningful yet sensitive to data error. The method proves promising in enhancing values of association rule mining results and helping users make correct decisions.
Petitjean, F.; Webb, G. I.
Scaling log-linear analysis to datasets with thousands of variables
Proceedings of the 2015 SIAM International Conference on Data Mining, pp. 469-477, 2015.
@inproceedings{PetitjeanWebb15,
title = {Scaling log-linear analysis to datasets with thousands of variables},
author = {F. Petitjean and G. I. Webb},
url = {http://epubs.siam.org/doi/pdf/10.1137/1.9781611974010.53},
year = {2015},
date = {2015-01-01},
booktitle = {Proceedings of the 2015 SIAM International Conference on Data Mining},
pages = {469-477},
abstract = {Association discovery is a fundamental data mining task. The primary statistical approach to association discovery between variables is log-linear analysis. Classical approaches to log-linear analysis do not scale beyond about ten variables. We have recently shown that, if we ensure that the graph supporting the log-linear model is chordal, log-linear analysis can be applied to datasets with hundreds of variables without sacrificing the statistical soundness [21]. However, further scalability remained limited, because state-of-the-art techniques have to examine every edge at every step of the search. This paper makes the following contributions: 1) we prove that only a very small subset of edges has to be considered at each step of the search; 2) we demonstrate how to efficiently find this subset of edges and 3) we show how to efficiently keep track of the best edges to be subsequently added to the initial model. Our experiments, carried out on real datasets with up to 2000 variables, show that our contributions make it possible to gain about 4 orders of magnitude, making log-linear analysis of datasets with thousands of variables possible in seconds instead of days.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Association discovery is a fundamental data mining task. The primary statistical approach to association discovery between variables is log-linear analysis. Classical approaches to log-linear analysis do not scale beyond about ten variables. We have recently shown that, if we ensure that the graph supporting the log-linear model is chordal, log-linear analysis can be applied to datasets with hundreds of variables without sacrificing the statistical soundness [21]. However, further scalability remained limited, because state-of-the-art techniques have to examine every edge at every step of the search. This paper makes the following contributions: 1) we prove that only a very small subset of edges has to be considered at each step of the search; 2) we demonstrate how to efficiently find this subset of edges and 3) we show how to efficiently keep track of the best edges to be subsequently added to the initial model. Our experiments, carried out on real datasets with up to 2000 variables, show that our contributions make it possible to gain about 4 orders of magnitude, making log-linear analysis of datasets with thousands of variables possible in seconds instead of days.
Petitjean, F.; Allison, L.; Webb, G. I.
A Statistically Efficient and Scalable Method for Log-Linear Analysis of High-Dimensional Data
Proceedings of the 14th IEEE International Conference on Data Mining, pp. 480-489, 2014.
@inproceedings{PetitjeanEtAl14a,
title = {A Statistically Efficient and Scalable Method for Log-Linear Analysis of High-Dimensional Data},
author = {F. Petitjean and L. Allison and G. I. Webb},
url = {http://dx.doi.org/10.1109/ICDM.2014.23},
year = {2014},
date = {2014-01-01},
booktitle = {Proceedings of the 14th IEEE International Conference on Data Mining},
pages = {480-489},
abstract = {Log-linear analysis is the primary statistical approach to discovering conditional dependencies between the variables of a dataset. A good log-linear analysis method requires both high precision and statistical efficiency. High precision means that the risk of false discoveries should be kept very low. Statistical efficiency means that the method should discover actual associations with as few samples as possible. Classical approaches to log-linear analysis make use of Chi-square tests to control this balance between quality and complexity. We present an information-theoretic approach to log-linear analysis. We show that our approach 1) requires significantly fewer samples to discover the true associations than statistical approaches \textendash statistical efficiency \textendash 2) controls for the risk of false discoveries as well as statistical approaches \textendash high precision - and 3) can perform the discovery on datasets with hundreds of variables on a standard desktop computer \textendash computational efficiency.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Log-linear analysis is the primary statistical approach to discovering conditional dependencies between the variables of a dataset. A good log-linear analysis method requires both high precision and statistical efficiency. High precision means that the risk of false discoveries should be kept very low. Statistical efficiency means that the method should discover actual associations with as few samples as possible. Classical approaches to log-linear analysis make use of Chi-square tests to control this balance between quality and complexity. We present an information-theoretic approach to log-linear analysis. We show that our approach 1) requires significantly fewer samples to discover the true associations than statistical approaches – statistical efficiency – 2) controls for the risk of false discoveries as well as statistical approaches – high precision - and 3) can perform the discovery on datasets with hundreds of variables on a standard desktop computer – computational efficiency.
Webb, G. I.; Vreeken, J.
Efficient Discovery of the Most Interesting Associations
ACM Transactions on Knowledge Discovery from Data, vol. 8, no. 3, 2014.
@article{WebbVreeken13,
title = {Efficient Discovery of the Most Interesting Associations},
author = {G. I. Webb and J. Vreeken},
url = {http://dl.acm.org/authorize?N80829},
doi = {10.1145/2601433},
year = {2014},
date = {2014-01-01},
journal = {ACM Transactions on Knowledge Discovery from Data},
volume = {8},
number = {3},
publisher = {ACM},
abstract = {Self-sufficient itemsets have been proposed as an effective approach to summarizing the key associations
in data. However, their computation appears highly demanding, as assessing whether an itemset is selfsufficient
requires consideration of all pairwise partitions of the itemset into pairs of subsets as well as
consideration of all supersets. This paper presents the first published algorithm for efficiently discovering
self-sufficient itemsets. This branch-and-bound algorithm deploys two powerful pruning mechanisms
based on upper-bounds on itemset value and statistical significance level. It demonstrates that finding top-k
productive and non-redundant itemsets, with post processing to identify those that are not independently
productive, can efficiently identify small sets of key associations. We present extensive evaluation of the
strengths and limitations of the technique including comparisons with alternative approaches to finding the
most interesting associations.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Self-sufficient itemsets have been proposed as an effective approach to summarizing the key associations
in data. However, their computation appears highly demanding, as assessing whether an itemset is selfsufficient
requires consideration of all pairwise partitions of the itemset into pairs of subsets as well as
consideration of all supersets. This paper presents the first published algorithm for efficiently discovering
self-sufficient itemsets. This branch-and-bound algorithm deploys two powerful pruning mechanisms
based on upper-bounds on itemset value and statistical significance level. It demonstrates that finding top-k
productive and non-redundant itemsets, with post processing to identify those that are not independently
productive, can efficiently identify small sets of key associations. We present extensive evaluation of the
strengths and limitations of the technique including comparisons with alternative approaches to finding the
most interesting associations.
in data. However, their computation appears highly demanding, as assessing whether an itemset is selfsufficient
requires consideration of all pairwise partitions of the itemset into pairs of subsets as well as
consideration of all supersets. This paper presents the first published algorithm for efficiently discovering
self-sufficient itemsets. This branch-and-bound algorithm deploys two powerful pruning mechanisms
based on upper-bounds on itemset value and statistical significance level. It demonstrates that finding top-k
productive and non-redundant itemsets, with post processing to identify those that are not independently
productive, can efficiently identify small sets of key associations. We present extensive evaluation of the
strengths and limitations of the technique including comparisons with alternative approaches to finding the
most interesting associations.
Hamalainen, Wilhelmiina; Webb, Geoffrey I.
Statistically sound pattern discovery
KDD '14: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 1976, 2014.
@inproceedings{HamalainenKDD2014,
title = {Statistically sound pattern discovery},
author = {Wilhelmiina Hamalainen and Geoffrey I. Webb},
doi = {10.1145/2623330.263081},
year = {2014},
date = {2014-01-01},
booktitle = {KDD '14: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining},
pages = {1976},
abstract = {Pattern discovery is a core data mining activity. Initial approaches were dominated by the frequent pattern discovery paradigm \textendash only patterns that occur frequently in the data were explored. Having been thoroughly researched and its limitations now well understood, this paradigm is giving way to a new one, which can be called statistically sound pattern discovery. In this paradigm, the main impetus is to discover statistically significant patterns, which are unlikely to have occurred by chance and are likely to hold in future data. Thus, the new paradigm provides a strict control over false discoveries and overfitting.
This tutorial covers both classic and cutting-edge research topics on pattern discovery combined to statistical significance testing. We start with an advanced introduction to the relevant forms of statistical significance testing, including different schools and alternative models, their underlying assumptions, practical issues, and limitations. We then discuss their application to data mining specific problems, including evaluation of nested patterns, the multiple testing problem, algorithmic strategies and real-world considerations. We present the current state-of-the art solutions and explore in detail how this approach to pattern discovery can deliver efficient and effective discovery of small sets of interesting patterns.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Pattern discovery is a core data mining activity. Initial approaches were dominated by the frequent pattern discovery paradigm – only patterns that occur frequently in the data were explored. Having been thoroughly researched and its limitations now well understood, this paradigm is giving way to a new one, which can be called statistically sound pattern discovery. In this paradigm, the main impetus is to discover statistically significant patterns, which are unlikely to have occurred by chance and are likely to hold in future data. Thus, the new paradigm provides a strict control over false discoveries and overfitting.
This tutorial covers both classic and cutting-edge research topics on pattern discovery combined to statistical significance testing. We start with an advanced introduction to the relevant forms of statistical significance testing, including different schools and alternative models, their underlying assumptions, practical issues, and limitations. We then discuss their application to data mining specific problems, including evaluation of nested patterns, the multiple testing problem, algorithmic strategies and real-world considerations. We present the current state-of-the art solutions and explore in detail how this approach to pattern discovery can deliver efficient and effective discovery of small sets of interesting patterns.
This tutorial covers both classic and cutting-edge research topics on pattern discovery combined to statistical significance testing. We start with an advanced introduction to the relevant forms of statistical significance testing, including different schools and alternative models, their underlying assumptions, practical issues, and limitations. We then discuss their application to data mining specific problems, including evaluation of nested patterns, the multiple testing problem, algorithmic strategies and real-world considerations. We present the current state-of-the art solutions and explore in detail how this approach to pattern discovery can deliver efficient and effective discovery of small sets of interesting patterns.
Petitjean, F.; Webb, G. I.; Nicholson, A. E.
Scaling log-linear analysis to high-dimensional data
Proceedings of the 13th IEEE International Conference on Data Mining, pp. 597-606, 2013.
@inproceedings{PetitjeanEtAl13,
title = {Scaling log-linear analysis to high-dimensional data},
author = {F. Petitjean and G. I. Webb and A. E. Nicholson},
doi = {10.1109/ICDM.2013.17},
year = {2013},
date = {2013-01-01},
booktitle = {Proceedings of the 13th IEEE International Conference on Data Mining},
pages = {597-606},
abstract = {Association discovery is a fundamental data mining task. The primary statistical approach to association discovery between variables is log-linear analysis. Classical approaches to log-linear analysis do not scale beyond about ten variables. We develop an efficient approach to log-linear analysis that scales to hundreds of variables by melding the classical statistical machinery of log-linear analysis with advanced data mining techniques from association discovery and graphical modeling.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Association discovery is a fundamental data mining task. The primary statistical approach to association discovery between variables is log-linear analysis. Classical approaches to log-linear analysis do not scale beyond about ten variables. We develop an efficient approach to log-linear analysis that scales to hundreds of variables by melding the classical statistical machinery of log-linear analysis with advanced data mining techniques from association discovery and graphical modeling.
Webb, G. I.
Filtered-top-k Association Discovery
WIREs Data Mining and Knowledge Discovery, vol. 1, no. 3, pp. 183-192, 2011.
@article{Webb11,
title = {Filtered-top-k Association Discovery},
author = {G. I. Webb},
doi = {10.1002/widm.28},
year = {2011},
date = {2011-01-01},
journal = {WIREs Data Mining and Knowledge Discovery},
volume = {1},
number = {3},
pages = {183-192},
publisher = {Wiley},
abstract = {Association mining has been one of the most intensively researched areas of data mining. However, direct uptake of the resulting technologies has been relatively low. This paper examines some of the reasons why the dominant paradigms in association mining have not lived up to their promise, and argues that a powerful alternative is provided by top-k techniques coupled with appropriate statistical and other filtering.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Association mining has been one of the most intensively researched areas of data mining. However, direct uptake of the resulting technologies has been relatively low. This paper examines some of the reasons why the dominant paradigms in association mining have not lived up to their promise, and argues that a powerful alternative is provided by top-k techniques coupled with appropriate statistical and other filtering.
Webb, G. I.
ACM Transactions on Knowledge Discovery from Data, vol. 4, iss. 1, 2010.
@article{Webb10,
title = {Self-Sufficient Itemsets: An Approach to Screening Potentially Interesting Associations Between Items},
author = {G. I. Webb},
url = {http://dl.acm.org/authorize?270473},
doi = {10.1145/1644873.1644876},
year = {2010},
date = {2010-01-01},
journal = {ACM Transactions on Knowledge Discovery from Data},
volume = {4},
issue = {1},
publisher = {ACM},
abstract = {Self-sufficient itemsets are those whose frequency cannot explained solely by the frequency of either their subsets or of their
supersets. We argue that itemsets that are not
self-sufficient will often be of little interest to the data
analyst, as their frequency should be expected once that of the
itemsets on which their frequency depends is known. We present
statistical tests for statistically sound discovery of
self-sufficient itemsets, and computational techniques that allow
those tests to be applied as a post-processing step for any itemset
discovery algorithm. We also present a measure for assessing the degree of potential interest in an itemset that complements these statistical measures.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Self-sufficient itemsets are those whose frequency cannot explained solely by the frequency of either their subsets or of their
supersets. We argue that itemsets that are not
self-sufficient will often be of little interest to the data
analyst, as their frequency should be expected once that of the
itemsets on which their frequency depends is known. We present
statistical tests for statistically sound discovery of
self-sufficient itemsets, and computational techniques that allow
those tests to be applied as a post-processing step for any itemset
discovery algorithm. We also present a measure for assessing the degree of potential interest in an itemset that complements these statistical measures.
supersets. We argue that itemsets that are not
self-sufficient will often be of little interest to the data
analyst, as their frequency should be expected once that of the
itemsets on which their frequency depends is known. We present
statistical tests for statistically sound discovery of
self-sufficient itemsets, and computational techniques that allow
those tests to be applied as a post-processing step for any itemset
discovery algorithm. We also present a measure for assessing the degree of potential interest in an itemset that complements these statistical measures.
Novak, P.; Lavrac, N.; Webb, G. I.
Journal of Machine Learning Research, vol. 10, pp. 377-403, 2009.
@article{NovakLavracWebb09,
title = {Supervised Descriptive Rule Discovery: A Unifying Survey of Contrast Set, Emerging Pattern and Subgroup Mining},
author = {P. Novak and N. Lavrac and G. I. Webb},
url = {http://www.jmlr.org/papers/volume10/kralj-novak09a/kralj-novak09a.pdf},
year = {2009},
date = {2009-01-01},
journal = {Journal of Machine Learning Research},
volume = {10},
pages = {377-403},
abstract = {This paper gives a survey of contrast set mining (CSM), emerging pattern mining (EPM), and subgroup discovery (SD) in a unifying framework named supervised descriptive rule discovery. While all these research areas aim at discovering patterns in the form of rules induced from labeled data, they use different terminology and task definitions, claim to have different goals, claim to use different rule learning heuristics, and use different means for selecting subsets of induced patterns. This paper contributes a novel understanding of these subareas of data mining by presenting a unified terminology, by explaining the apparent differences between the learning tasks as variants of a unique supervised descriptive rule discovery task and by exploring the apparent differences between the approaches. It also shows that various rule learning heuristics used in CSM, EPM and SD algorithms all aim at optimizing a trade off between rule coverage and precision. The commonalities (and differences) between the approaches are showcased on a selection of best known variants of CSM, EPM and SD algorithms. The paper also provides a critical survey of existing supervised descriptive rule discovery visualization methods.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
This paper gives a survey of contrast set mining (CSM), emerging pattern mining (EPM), and subgroup discovery (SD) in a unifying framework named supervised descriptive rule discovery. While all these research areas aim at discovering patterns in the form of rules induced from labeled data, they use different terminology and task definitions, claim to have different goals, claim to use different rule learning heuristics, and use different means for selecting subsets of induced patterns. This paper contributes a novel understanding of these subareas of data mining by presenting a unified terminology, by explaining the apparent differences between the learning tasks as variants of a unique supervised descriptive rule discovery task and by exploring the apparent differences between the approaches. It also shows that various rule learning heuristics used in CSM, EPM and SD algorithms all aim at optimizing a trade off between rule coverage and precision. The commonalities (and differences) between the approaches are showcased on a selection of best known variants of CSM, EPM and SD algorithms. The paper also provides a critical survey of existing supervised descriptive rule discovery visualization methods.
Webb, G. I.
Layered Critical Values: A Powerful Direct-Adjustment Approach to Discovering Significant Patterns
Machine Learning, vol. 71, no. 2-3, pp. 307-323, 2008.
@article{Webb08,
title = {Layered Critical Values: A Powerful Direct-Adjustment Approach to Discovering Significant Patterns},
author = {G. I. Webb},
doi = {10.1007/s10994-008-5046-x},
year = {2008},
date = {2008-01-01},
journal = {Machine Learning},
volume = {71},
number = {2-3},
pages = {307-323},
publisher = {Springer},
address = {Netherlands},
abstract = {Standard pattern discovery techniques, such as association rules, suffer an extreme risk of finding very large numbers of spurious patterns for many knowledge discovery tasks. The direct-adjustment approach to controlling this risk applies a statistical test during the discovery process, using a critical value adjusted to take account of the size of the search space. However, a problem with the direct-adjustment strategy is that it may discard numerous true patterns. This paper investigates the assignment of different critical values to different areas of the search space as an approach to alleviating this problem, using a variant of a technique originally developed for other purposes. This approach is shown to be effective at increasing the number of discoveries while still maintaining strict control over the risk of false discoveries.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Standard pattern discovery techniques, such as association rules, suffer an extreme risk of finding very large numbers of spurious patterns for many knowledge discovery tasks. The direct-adjustment approach to controlling this risk applies a statistical test during the discovery process, using a critical value adjusted to take account of the size of the search space. However, a problem with the direct-adjustment strategy is that it may discard numerous true patterns. This paper investigates the assignment of different critical values to different areas of the search space as an approach to alleviating this problem, using a variant of a technique originally developed for other purposes. This approach is shown to be effective at increasing the number of discoveries while still maintaining strict control over the risk of false discoveries.
Webb, G. I.
Discovering Significant Patterns
Machine Learning, vol. 68, no. 1, pp. 1-33, 2007.
@article{Webb07,
title = {Discovering Significant Patterns},
author = {G. I. Webb},
doi = {10.1007/s10994-007-5006-x},
year = {2007},
date = {2007-01-01},
journal = {Machine Learning},
volume = {68},
number = {1},
pages = {1-33},
publisher = {Springer},
address = {Netherlands},
abstract = {Exploratory pattern discovery techniques, such as association rule discovery, explore large search spaces of potential patterns to find those that satisfy some user-specified constraints. Due to the large number of patterns considered, they suffer from an extreme risk of type-1 error, that is, of finding patterns that appear due to chance alone to satisfy the constraints on the sample data. This paper proposes techniques to overcome this problem by applying well-established statistical practices. These allow the user to enforce a strict upper limit on the risk of experimentwise error. Empirical studies demonstrate that standard exploratory pattern discovery techniques can discover numerous spurious patterns when applied to random data and when applied to real-world data result in large numbers of patterns that are rejected when subjected to statistical evaluation on holdout data. They also reveal that modification of the pattern discovery process to anticipate subsequent statistical evaluation can increase the number of patterns that are accepted by statistical evaluation on holdout data.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Exploratory pattern discovery techniques, such as association rule discovery, explore large search spaces of potential patterns to find those that satisfy some user-specified constraints. Due to the large number of patterns considered, they suffer from an extreme risk of type-1 error, that is, of finding patterns that appear due to chance alone to satisfy the constraints on the sample data. This paper proposes techniques to overcome this problem by applying well-established statistical practices. These allow the user to enforce a strict upper limit on the risk of experimentwise error. Empirical studies demonstrate that standard exploratory pattern discovery techniques can discover numerous spurious patterns when applied to random data and when applied to real-world data result in large numbers of patterns that are rejected when subjected to statistical evaluation on holdout data. They also reveal that modification of the pattern discovery process to anticipate subsequent statistical evaluation can increase the number of patterns that are accepted by statistical evaluation on holdout data.
Butler, S.; Webb, G. I.
Wang, John (Ed.): The Encyclopedia of Data Warehousing and Mining, pp. 795-799, Idea Group Inc., Hershey, PA, 2006.
@incollection{ButlerWebb05,
title = {Mining Group Differences},
author = {S. Butler and G. I. Webb},
editor = {John Wang},
doi = {10.4018/978-1-60566-010-3.ch199},
year = {2006},
date = {2006-01-01},
booktitle = {The Encyclopedia of Data Warehousing and Mining},
pages = {795-799},
publisher = {Idea Group Inc.},
address = {Hershey, PA},
keywords = {},
pubstate = {published},
tppubtype = {incollection}
}
Huang, S.; Webb, G. I.
Efficiently Identifying Exploratory Rules' Significance
LNAI State-of-the-Art Survey series, 'Data Mining: Theory, Methodology, Techniques, and Applications', pp. 64-77, Springer, Berlin/Heidelberg, 2006, (An earlier version of this paper was published in S.J. Simoff and G.J. Williams (Eds.), Proceedings of the Third Australasian Data Mining Conference (AusDM04) Cairns, Australia. Sydney: University of Technology, pages 169-182.).
@inproceedings{HuangWebb05b,
title = {Efficiently Identifying Exploratory Rules' Significance},
author = {S. Huang and G. I. Webb},
doi = {10.1007/11677437_6},
year = {2006},
date = {2006-01-01},
booktitle = {LNAI State-of-the-Art Survey series, 'Data Mining: Theory, Methodology, Techniques, and Applications'},
pages = {64-77},
publisher = {Springer},
address = {Berlin/Heidelberg},
abstract = {How to efficiently discard potentially uninteresting rules in exploratory rule discovery is one of the important research foci in data mining. Many researchers have presented algorithms to automatically remove potentially uninteresting rules utilizing background knowledge and user-specified constraints. Identifying the significance of exploratory rules using a significance test is desirable for removing rules that may appear interesting by chance, hence providing the users with a more compact set of resulting rules. However, applying statistical tests to identify significant rules requires considerable computation and data access in order to obtain the necessary statistics. The situation gets worse as the size of the database increases. In this paper, we propose two approaches for improving the efficiency of significant exploratory rule discovery. We also evaluate the experimental effect in impact rule discovery which is suitable for discovering exploratory rules in very large, dense databases.},
note = {An earlier version of this paper was published in S.J. Simoff and G.J. Williams (Eds.), Proceedings of the Third Australasian Data Mining Conference (AusDM04) Cairns, Australia. Sydney: University of Technology, pages 169-182.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
How to efficiently discard potentially uninteresting rules in exploratory rule discovery is one of the important research foci in data mining. Many researchers have presented algorithms to automatically remove potentially uninteresting rules utilizing background knowledge and user-specified constraints. Identifying the significance of exploratory rules using a significance test is desirable for removing rules that may appear interesting by chance, hence providing the users with a more compact set of resulting rules. However, applying statistical tests to identify significant rules requires considerable computation and data access in order to obtain the necessary statistics. The situation gets worse as the size of the database increases. In this paper, we propose two approaches for improving the efficiency of significant exploratory rule discovery. We also evaluate the experimental effect in impact rule discovery which is suitable for discovering exploratory rules in very large, dense databases.
Webb, G. I.
Ungar, L.; Craven, M.; Gunopulos, D.; Eliassi-Rad, T. (Ed.): Proceedings of the Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2006), pp. 434-443, The Association for Computing Machinery, Philadelphia, PA, 2006.
@inproceedings{Webb06a,
title = {Discovering Significant Rules},
author = {G. I. Webb},
editor = {L. Ungar and M. Craven and D. Gunopulos and T. Eliassi-Rad},
url = {http://dl.acm.org/authorize?N00546},
year = {2006},
date = {2006-01-01},
booktitle = {Proceedings of the Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2006)},
pages = {434-443},
publisher = {The Association for Computing Machinery},
address = {Philadelphia, PA},
abstract = {In many applications, association rules will only be interesting if they represent non-trivial correlations between all constituent items. Numerous techniques have been developed that seek to avoid false discoveries. However, while all provide useful solutions to aspects of this problem, none provides a generic solution that is both flexible enough to accommodate varying definitions of true and false discoveries and powerful enough to provide strict control over the risk of false discoveries. This paper presents generic techniques that allow definitions of true and false discoveries to be specified in terms of arbitrary statistical hypothesis tests and which provide strict control over the experimentwise risk of false discoveries.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
In many applications, association rules will only be interesting if they represent non-trivial correlations between all constituent items. Numerous techniques have been developed that seek to avoid false discoveries. However, while all provide useful solutions to aspects of this problem, none provides a generic solution that is both flexible enough to accommodate varying definitions of true and false discoveries and powerful enough to provide strict control over the risk of false discoveries. This paper presents generic techniques that allow definitions of true and false discoveries to be specified in terms of arbitrary statistical hypothesis tests and which provide strict control over the experimentwise risk of false discoveries.
Huang, S.; Webb, G. I.
Pruning Derivative Partial Rules During Impact Rule Discovery
Ho, T. B.; Cheung, D.; Liu, H. (Ed.): Lecture Notes in Computer Science Vol. 3518: Proceedings of the 9th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining (PAKDD 2005), pp. 71-80, Springer, Hanoi, Vietnam, 2005.
@inproceedings{HuangWebb05a,
title = {Pruning Derivative Partial Rules During Impact Rule Discovery},
author = {S. Huang and G. I. Webb},
editor = {T. B. Ho and D. Cheung and H. Liu},
year = {2005},
date = {2005-01-01},
booktitle = {Lecture Notes in Computer Science Vol. 3518: Proceedings of the 9th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining (PAKDD 2005)},
pages = {71-80},
publisher = {Springer},
address = {Hanoi, Vietnam},
abstract = {Because exploratory rule discovery works with data that is only a sample of the phenomena to be investigated, some resulting rules may appear interesting only by chance. Techniques are developed for automatically discarding statistically insignificant exploratory rules that cannot survive a hypothesis with regard to its ancestors. We call such insignificant rules derivative extended rules. In this paper, we argue that there is another type of derivative exploratory rules, which is derivative with regard to their children. We also argue that considerable amount of such derivative partial rules can not be successfully removed using existing rule pruning techniques. We propose a new technique to address this problem. Experiments are done in impact rule discovery to evaluate the effect of this derivative partial rule filter. Results show that the inherent problem of too many resulting rules in exploratory rule discovery is alleviated.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Because exploratory rule discovery works with data that is only a sample of the phenomena to be investigated, some resulting rules may appear interesting only by chance. Techniques are developed for automatically discarding statistically insignificant exploratory rules that cannot survive a hypothesis with regard to its ancestors. We call such insignificant rules derivative extended rules. In this paper, we argue that there is another type of derivative exploratory rules, which is derivative with regard to their children. We also argue that considerable amount of such derivative partial rules can not be successfully removed using existing rule pruning techniques. We propose a new technique to address this problem. Experiments are done in impact rule discovery to evaluate the effect of this derivative partial rule filter. Results show that the inherent problem of too many resulting rules in exploratory rule discovery is alleviated.
Huang, S.; Webb, G. I.
Discarding Insignificant Rules During Impact Rule Discovery in Large, Dense Databases
Kargupta, H.; Kamath, C.; Srivastava, J.; Goodman, A. (Ed.): Proceedings of the Fifth SIAM International Conference on Data Mining (SDM'05) [short paper], pp. 541-545, Society for Industrial and Applied Mathematics, Newport Beach, CA, 2005.
@inproceedings{HuangWebb05,
title = {Discarding Insignificant Rules During Impact Rule Discovery in Large, Dense Databases},
author = {S. Huang and G. I. Webb},
editor = {H. Kargupta and C. Kamath and J. Srivastava and A. Goodman},
year = {2005},
date = {2005-01-01},
booktitle = {Proceedings of the Fifth SIAM International Conference on Data Mining (SDM'05) [short paper]},
pages = {541-545},
publisher = {Society for Industrial and Applied Mathematics},
address = {Newport Beach, CA},
abstract = {Considerable progress has been made on how to reduce the number of spurious exploratory rules with quantitative attributes. However, little has been done for rules with undiscretized quantitative attributes. It is argued that propositional rules can not effectively describe the interactions between quantitative and qualitative attributes. Aumann and Lindell proposed quantitative association rules to provide a better description of such relationship, together with a rule pruning techniques . Since their technique is based on the frequent itemset framework, it is not suitable for rule discovery in large, dense databases. In this paper, an efficient technique for automatically discarding insignificant rules during rule discovery is proposed, based on the OPUS search algorithm. Experiments demonstrate that the algorithm we propose can efficiently remove potentially uninteresting rules even in very large, dense databases.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Considerable progress has been made on how to reduce the number of spurious exploratory rules with quantitative attributes. However, little has been done for rules with undiscretized quantitative attributes. It is argued that propositional rules can not effectively describe the interactions between quantitative and qualitative attributes. Aumann and Lindell proposed quantitative association rules to provide a better description of such relationship, together with a rule pruning techniques . Since their technique is based on the frequent itemset framework, it is not suitable for rule discovery in large, dense databases. In this paper, an efficient technique for automatically discarding insignificant rules during rule discovery is proposed, based on the OPUS search algorithm. Experiments demonstrate that the algorithm we propose can efficiently remove potentially uninteresting rules even in very large, dense databases.
Webb, G. I.
K-Optimal Pattern Discovery: An Efficient and Effective Approach to Exploratory Data Mining
Zhang, S.; Jarvis, R. (Ed.): Lecture Notes in Computer Science 3809: Advances in Artificial Intelligence, Proceedings of the 18th Australian Joint Conference on Artificial Intelligence (AI 2005)[Extended Abstract], pp. 1-2, Springer, Sydney, Australia, 2005.
@inproceedings{Webb05a,
title = {K-Optimal Pattern Discovery: An Efficient and Effective Approach to Exploratory Data Mining},
author = {G. I. Webb},
editor = {S. Zhang and R. Jarvis},
doi = {10.1007/11589990_1},
year = {2005},
date = {2005-01-01},
booktitle = {Lecture Notes in Computer Science 3809: Advances in Artificial Intelligence, Proceedings of the 18th Australian Joint Conference on Artificial Intelligence (AI 2005)[Extended Abstract]},
pages = {1-2},
publisher = {Springer},
address = {Sydney, Australia},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Webb, G. I.; Zhang, S.
Data Mining and Knowledge Discovery, vol. 10, no. 1, pp. 39-79, 2005.
@article{WebbZhang05,
title = {k-Optimal-Rule-Discovery},
author = {G. I. Webb and S. Zhang},
doi = {10.1007/s10618-005-0255-4},
year = {2005},
date = {2005-01-01},
journal = {Data Mining and Knowledge Discovery},
volume = {10},
number = {1},
pages = {39-79},
publisher = {Springer},
address = {Netherlands},
abstract = {K-most-interesting rule discovery finds the k rules that optimize a user-specified measure of interestingness with respect to a set of sample data and user-specified constraints. This approach avoids many limitations of the frequent itemset approach of association rule discovery. This paper presents a scalable algorithm applicable to a wide range of k-most-interesting rule discovery tasks and demonstrates its efficiency.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
K-most-interesting rule discovery finds the k rules that optimize a user-specified measure of interestingness with respect to a set of sample data and user-specified constraints. This approach avoids many limitations of the frequent itemset approach of association rule discovery. This paper presents a scalable algorithm applicable to a wide range of k-most-interesting rule discovery tasks and demonstrates its efficiency.
Thiruvady, D. R.; Webb, G. I.
Mining Negative Rules using GRD
Dai, H.; Srikant, R.; Zhang, C. (Ed.): Lecture Notes in Computer Science Vol. 3056: Proceedings of the Eighth Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD 04) [Short Paper], pp. 161-165, Springer, Sydney, Australia, 2004.
@inproceedings{ThiruvadyWebb04,
title = {Mining Negative Rules using GRD},
author = {D. R. Thiruvady and G. I. Webb},
editor = {H. Dai and R. Srikant and C. Zhang},
year = {2004},
date = {2004-01-01},
booktitle = {Lecture Notes in Computer Science Vol. 3056: Proceedings of the Eighth Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD 04) [Short Paper]},
pages = {161-165},
publisher = {Springer},
address = {Sydney, Australia},
abstract = {GRD is an algorithm for k-most interesting rule discovery. In contrast to association rule discovery, GRD does not require the use of a minimum support constraint. Rather, the user must specify a measure of interestingness and the number of rules sought (k). This paper reports efficient techniques to extend GRD to support mining of negative rules. We demonstrate that the new approach provides tractable discovery of both negative and positive rules.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
GRD is an algorithm for k-most interesting rule discovery. In contrast to association rule discovery, GRD does not require the use of a minimum support constraint. Rather, the user must specify a measure of interestingness and the number of rules sought (k). This paper reports efficient techniques to extend GRD to support mining of negative rules. We demonstrate that the new approach provides tractable discovery of both negative and positive rules.
Webb, G. I.
Preliminary Investigations into Statistically Valid Exploratory Rule Discovery
Simoff, S. J.; Williams, G. J.; Hegland, M. (Ed.): Proceedings of the Second Australasian Data Mining Conference (AusDM03), pp. 1-9, University of Technology, Canberra, Australia, 2003.
@inproceedings{Webb03a,
title = {Preliminary Investigations into Statistically Valid Exploratory Rule Discovery},
author = {G. I. Webb},
editor = {S. J. Simoff and G. J. Williams and M. Hegland},
year = {2003},
date = {2003-01-01},
booktitle = {Proceedings of the Second Australasian Data Mining Conference (AusDM03)},
pages = {1-9},
publisher = {University of Technology},
address = {Canberra, Australia},
abstract = {Exploratory rule discovery, as exemplified by association rule discovery, has proven very popular. In this paper I investigate issues surrounding the statistical validity of rules found using this approach and methods that might be employed to deliver statistically sound exploratory rule discovery.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Exploratory rule discovery, as exemplified by association rule discovery, has proven very popular. In this paper I investigate issues surrounding the statistical validity of rules found using this approach and methods that might be employed to deliver statistically sound exploratory rule discovery.
Webb, G. I.
Association Rules
Ye, Nong (Ed.): The Handbook of Data Mining, Chapter 2, pp. 25-39, Lawrence Erlbaum Associates, 2003.
@incollection{Webb03,
title = {Association Rules},
author = {G. I. Webb},
editor = {Nong Ye},
year = {2003},
date = {2003-01-01},
booktitle = {The Handbook of Data Mining, Chapter 2},
pages = {25-39},
publisher = {Lawrence Erlbaum Associates},
keywords = {},
pubstate = {published},
tppubtype = {incollection}
}
Webb, G. I.; Butler, S.; Newlands, D.
On Detecting Differences Between Groups
Domingos, P.; Faloutsos, C.; Senator, T.; Kargupta, H.; Getoor, L. (Ed.): Proceedings of The Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2003), pp. 256-265, The Association for Computing Machinery, Washington, DC, 2003.
@inproceedings{WebbButlerNewlands03,
title = {On Detecting Differences Between Groups},
author = {G. I. Webb and S. Butler and D. Newlands},
editor = {P. Domingos and C. Faloutsos and T. Senator and H. Kargupta and L. Getoor},
year = {2003},
date = {2003-01-01},
booktitle = {Proceedings of The Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2003)},
pages = {256-265},
publisher = {The Association for Computing Machinery},
address = {Washington, DC},
abstract = {Understanding the differences between contrasting groups is a fundamental task in data analysis. This realization has led to the development of a new special purpose data mining technique, em contrast-set mining. We undertook a study with a retail collaborator to compare contrast-set mining with existing rule-discovery techniques. To our surprise we observed that straightforward application of an existing commercial rule-discovery system, Magnum Opus, could successfully perform the contrast-set-mining task. This led to the realization that contrast-set mining is a special case of the more general rule-discovery task. We present the results of our study together with a proof of this conclusion},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Understanding the differences between contrasting groups is a fundamental task in data analysis. This realization has led to the development of a new special purpose data mining technique, em contrast-set mining. We undertook a study with a retail collaborator to compare contrast-set mining with existing rule-discovery techniques. To our surprise we observed that straightforward application of an existing commercial rule-discovery system, Magnum Opus, could successfully perform the contrast-set-mining task. This led to the realization that contrast-set mining is a special case of the more general rule-discovery task. We present the results of our study together with a proof of this conclusion
Zhang, C.; Zhang, S.; Webb, G. I.
Identifying Approximate Itemsets of Interest In Large Databases
Applied Intelligence, vol. 18, pp. 91-104, 2003.
@article{ZhangZhangWebb03,
title = {Identifying Approximate Itemsets of Interest In Large Databases},
author = {C. Zhang and S. Zhang and G. I. Webb},
url = {http://link.springer.com/content/pdf/10.1023%2FA%3A1020995206763.pdf},
year = {2003},
date = {2003-01-01},
journal = {Applied Intelligence},
volume = {18},
pages = {91-104},
publisher = {Springer},
address = {Netherlands},
abstract = {This paper presents a method for discovering approximate frequent itemsets of interest in large scale databases. This method uses the central limit theorem to increase efficiency, enabling us to reduce the sample size by about half compared to previous approximations. Further efficiency is gained by pruning from the search space uninteresting frequent itemsets. In addition to improving efficiency, this measure also reduces the number of itemsets that the user need consider. The model and algorithm have been implemented and evaluated using both synthetic and real-world databases. Our experimental results demonstrate the efficiency of the approach},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
This paper presents a method for discovering approximate frequent itemsets of interest in large scale databases. This method uses the central limit theorem to increase efficiency, enabling us to reduce the sample size by about half compared to previous approximations. Further efficiency is gained by pruning from the search space uninteresting frequent itemsets. In addition to improving efficiency, this measure also reduces the number of itemsets that the user need consider. The model and algorithm have been implemented and evaluated using both synthetic and real-world databases. Our experimental results demonstrate the efficiency of the approach
Webb, G. I.; Zhang, S.
Removing Trivial Associations in Association Rule Discovery
Proceedings of the First International NAISO Congress on Autonomous Intelligent Systems (ICAIS 2002), NAISO Academic Press, Geelong, Australia, 2002.
@inproceedings{WebbZhang02,
title = {Removing Trivial Associations in Association Rule Discovery},
author = {G. I. Webb and S. Zhang},
year = {2002},
date = {2002-01-01},
booktitle = {Proceedings of the First International NAISO Congress on Autonomous Intelligent Systems (ICAIS 2002)},
publisher = {NAISO Academic Press},
address = {Geelong, Australia},
abstract = {Association rule discovery has become one of the most widely applied data mining strategies. Techniques for association rule discovery have been dominated by the frequent itemset strategy as exemplified by the Apriori algorithm. One limitation of this approach is that it provides little opportunity to detect and remove association rules on the basis of relationships between rules. As a result, the association rules discovered are frequently swamped with large numbers of spurious rules that are of little interest to the user. This paper presents association rule discovery techniques that can detect and discard one form of spurious association rule: trivial associations.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Association rule discovery has become one of the most widely applied data mining strategies. Techniques for association rule discovery have been dominated by the frequent itemset strategy as exemplified by the Apriori algorithm. One limitation of this approach is that it provides little opportunity to detect and remove association rules on the basis of relationships between rules. As a result, the association rules discovered are frequently swamped with large numbers of spurious rules that are of little interest to the user. This paper presents association rule discovery techniques that can detect and discard one form of spurious association rule: trivial associations.
Webb, G. I.; Zhang, S.
Further Pruning for Efficient Association Rule Discovery
Stumptner, M.; Corbett, D.; Brooks, M. J. (Ed.): Lecture Notes in Computer Science Vol. 2256: Proceedings of the 14th Australian Joint Conference on Artificial Intelligence (AI'01), pp. 605-618, Springer, Adelaide, Australia, 2001.
@inproceedings{WebbZhang01,
title = {Further Pruning for Efficient Association Rule Discovery},
author = {G. I. Webb and S. Zhang},
editor = {M. Stumptner and D. Corbett and M. J. Brooks},
year = {2001},
date = {2001-01-01},
booktitle = {Lecture Notes in Computer Science Vol. 2256: Proceedings of the 14th Australian Joint Conference on Artificial Intelligence (AI'01)},
pages = {605-618},
publisher = {Springer},
address = {Adelaide, Australia},
abstract = {The Apriori algorithm's frequent itemset approach has become the standard approach to discovering association rules. However, the computation requirements of the frequent itemset approach are infeasible for dense data and the approach is unable to discover infrequent associations. OPUS_AR is an efficient algorithm for rule discovery that does not utilize frequent itemsets and hence avoids these problems. It can reduce search time by using additional constraints on the search space as well as constraints on itemset frequency. However, the effectiveness of the pruning rules used during search will determine the efficiency of its search. This paper presents and analyzes pruning rules for use with OPUS_AR. We demonstrate that application of OPUS_AR is feasible for a number of datasets for which application of the frequent itemset approach is infeasible and that the new pruning rules can reduce compute time by more than 40%.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
The Apriori algorithm's frequent itemset approach has become the standard approach to discovering association rules. However, the computation requirements of the frequent itemset approach are infeasible for dense data and the approach is unable to discover infrequent associations. OPUS_AR is an efficient algorithm for rule discovery that does not utilize frequent itemsets and hence avoids these problems. It can reduce search time by using additional constraints on the search space as well as constraints on itemset frequency. However, the effectiveness of the pruning rules used during search will determine the efficiency of its search. This paper presents and analyzes pruning rules for use with OPUS_AR. We demonstrate that application of OPUS_AR is feasible for a number of datasets for which application of the frequent itemset approach is infeasible and that the new pruning rules can reduce compute time by more than 40%.
Webb, G. I.
Discovering Associations with Numeric Variables
Provost, F.; Srikant, R. (Ed.): Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2001)[short paper], pp. 383-388, The Association for Computing Machinery, San Francisco, CA, 2001.
@inproceedings{Webb01a,
title = {Discovering Associations with Numeric Variables},
author = {G. I. Webb},
editor = {F. Provost and R. Srikant},
url = {http://dl.acm.org/authorize?19861},
year = {2001},
date = {2001-01-01},
booktitle = {Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2001)[short paper]},
pages = {383-388},
publisher = {The Association for Computing Machinery},
address = {San Francisco, CA},
abstract = {This paper further develops Aumann and Lindell's [3] proposal for a variant of association rules for which the consequent is a numeric variable. It is argued that these rules can discover useful interactions with numeric data that cannot be discovered directly using traditional association rules with discretization. Alternative measures for identifying interesting rules are proposed. Efficient algorithms are presented that enable these rules to be discovered for dense data sets for which application of Auman and Lindell's algorithm is infeasible.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
This paper further develops Aumann and Lindell's [3] proposal for a variant of association rules for which the consequent is a numeric variable. It is argued that these rules can discover useful interactions with numeric data that cannot be discovered directly using traditional association rules with discretization. Alternative measures for identifying interesting rules are proposed. Efficient algorithms are presented that enable these rules to be discovered for dense data sets for which application of Auman and Lindell's algorithm is infeasible.
Webb, G. I.
Efficient Search for Association Rules
Ramakrishnan, R.; Stolfo, S. (Ed.): Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2000), pp. 99-107, The Association for Computing Machinery, Boston, MA, 2000.
@inproceedings{Webb00b,
title = {Efficient Search for Association Rules},
author = {G. I. Webb},
editor = {R. Ramakrishnan and S. Stolfo},
year = {2000},
date = {2000-01-01},
booktitle = {Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2000)},
pages = {99-107},
publisher = {The Association for Computing Machinery},
address = {Boston, MA},
abstract = {This paper argues that for some applications direct search for association rules can be more efficient than the two stage process of the Apriori algorithm which first finds large item sets which are then used to identify associations. In particular, it is argued, Apriori can impose large computational overheads when the number of frequent itemsets is very large. This will often be the case when association rule analysis is performed on domains other than basket analysis or when it is performed for basket analysis with basket information augmented by other customer information. An algorithm is presented that is computationally efficient for association rule analysis during which the number of rules to be found can be constrained and all data can be maintained in memory.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
This paper argues that for some applications direct search for association rules can be more efficient than the two stage process of the Apriori algorithm which first finds large item sets which are then used to identify associations. In particular, it is argued, Apriori can impose large computational overheads when the number of frequent itemsets is very large. This will often be the case when association rule analysis is performed on domains other than basket analysis or when it is performed for basket analysis with basket information augmented by other customer information. An algorithm is presented that is computationally efficient for association rule analysis during which the number of rules to be found can be constrained and all data can be maintained in memory.
Webb, G. I.
Inclusive Pruning: A New Class of Pruning Rule for Unordered Search and its Application to Classification Learning
Ramamohanarao, K. (Ed.): Australian Computer Science Communications Vol. 18 (1): Proceedings of the Nineteenth Australasian Computer Science Conference (ACSC'96), pp. 1-10, ACS, Royal Melbourne Insitute of Technology, Australia, 1996.
@inproceedings{Webb96e,
title = {Inclusive Pruning: A New Class of Pruning Rule for Unordered Search and its Application to Classification Learning},
author = {G. I. Webb},
editor = {K. Ramamohanarao},
year = {1996},
date = {1996-01-01},
booktitle = {Australian Computer Science Communications Vol. 18 (1): Proceedings of the Nineteenth Australasian Computer Science Conference (ACSC'96)},
pages = {1-10},
publisher = {ACS},
address = {Royal Melbourne Insitute of Technology, Australia},
abstract = {This paper presents a new class of pruning rule for unordered search. Previous pruning rules for unordered search identify operators that should not be applied in order to prune nodes reached via those operators. In contrast, the new pruning rules identify operators that should be applied and prune nodes that are not reached via those operators. Specific pruning rules employing both these approaches are identified for classification learning. Experimental results demonstrate that application of the new pruning rules can reduce by more than 60% the number of states from the search space that are considered during classification learning.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
This paper presents a new class of pruning rule for unordered search. Previous pruning rules for unordered search identify operators that should not be applied in order to prune nodes reached via those operators. In contrast, the new pruning rules identify operators that should be applied and prune nodes that are not reached via those operators. Specific pruning rules employing both these approaches are identified for classification learning. Experimental results demonstrate that application of the new pruning rules can reduce by more than 60% the number of states from the search space that are considered during classification learning.
Webb, G. I.
OPUS: An Efficient Admissible Algorithm For Unordered Search
Journal of Artificial Intelligence Research, vol. 3, pp. 431-465, 1995.
@article{Webb95,
title = {OPUS: An Efficient Admissible Algorithm For Unordered Search},
author = {G. I. Webb},
doi = {10.1613/jair.227},
year = {1995},
date = {1995-01-01},
journal = {Journal of Artificial Intelligence Research},
volume = {3},
pages = {431-465},
publisher = {AAAI Press},
address = {Menlo Park, CA},
abstract = {OPUS is a branch and bound search algorithm that enables efficient admissible search through spaces for which the order of search operator application is not significant. The algorithm's search efficiency is demonstrated with respect to very large machine learning search spaces. The use of admissible search is of potential value to the machine learning community as it means that the exact learning biases to be employed for complex learning tasks can be precisely specified and manipulated. OPUS also has potential for application in other areas of artificial intelligence, notably, truth maintenance.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
OPUS is a branch and bound search algorithm that enables efficient admissible search through spaces for which the order of search operator application is not significant. The algorithm's search efficiency is demonstrated with respect to very large machine learning search spaces. The use of admissible search is of potential value to the machine learning community as it means that the exact learning biases to be employed for complex learning tasks can be precisely specified and manipulated. OPUS also has potential for application in other areas of artificial intelligence, notably, truth maintenance.