Specious rules: An efficient and effective unifying method for removing misleading and uninformative patterns in association rule mining

Wilhelmiina Hämäläinen, Geoffrey I. Webb

    Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

    Abstract

    We present theoretical analysis and a suite of tests and procedures for addressing a broad class of redundant and misleading association rules we call specious rules. Specious dependencies, also known as spurious, apparent, or illusory associations, refer to a well-known phenomenon where marginal dependencies are merely products of interactions with other variables and disappear when conditioned on those variables. The most extreme example is Yule-Simpson's paradox where two variables present positive dependence in the marginal contingency table but negative in all partial tables defined by different levels of a confounding factor. It is accepted wisdom that in data of any nontrivial dimensionality it is infeasible to control for all of the exponentially many possible confounds of this nature. In this paper, we consider the problem of specious dependencies in the context of statistical association rule mining. We define specious rules and show they offer a unifying framework which covers many types of previously proposed redundant or misleading association rules. After theoretical analysis, we introduce practical algorithms for detecting and pruning out specious association rules efficiently under many key goodness measures, including Mutual information and exact hypergeometric probabilities. We demonstrate that the procedure greatly reduces the number of associations discovered, providing an elegant and effective solution to the problem of association mining discovering large numbers of misleading and redundant rules.

    Original languageEnglish
    Title of host publicationProceedings of the 17th SIAM International Conference on Data Mining
    Subtitle of host publicationHouston, Texas, USA, 27 – 29 April , 2017
    EditorsNitesh Chawla, Wei Wang
    Place of PublicationPhiladelphia, PA
    PublisherSociety for Industrial and Applied Mathematics SIAM Publications
    Pages309-317
    Number of pages9
    ISBN (Electronic)9781611974874, 9781611974881
    DOIs
    Publication statusPublished - 2017
    EventSIAM International Conference on Data Mining 2017 - Houston, United States of America
    Duration: 27 Apr 201729 Apr 2017
    Conference number: 17th

    Conference

    ConferenceSIAM International Conference on Data Mining 2017
    Abbreviated titleSDM 2017
    CountryUnited States of America
    CityHouston
    Period27/04/1729/04/17

    Keywords

    • Association rule
    • Birch's test
    • Mutual information
    • Specious dependency
    • Yule-Simpson's paradox

    Cite this

    Hämäläinen, W., & Webb, G. I. (2017). Specious rules: An efficient and effective unifying method for removing misleading and uninformative patterns in association rule mining. In N. Chawla, & W. Wang (Eds.), Proceedings of the 17th SIAM International Conference on Data Mining: Houston, Texas, USA, 27 – 29 April , 2017 (pp. 309-317). Philadelphia, PA: Society for Industrial and Applied Mathematics SIAM Publications. https://doi.org/10.1137/1.9781611974973.35
    Hämäläinen, 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 17th SIAM International Conference on Data Mining: Houston, Texas, USA, 27 – 29 April , 2017. editor / Nitesh Chawla ; Wei Wang. Philadelphia, PA : Society for Industrial and Applied Mathematics SIAM Publications, 2017. pp. 309-317
    @inproceedings{6480c7da705940689bcdf9a68db61ee4,
    title = "Specious rules: An efficient and effective unifying method for removing misleading and uninformative patterns in association rule mining",
    abstract = "We present theoretical analysis and a suite of tests and procedures for addressing a broad class of redundant and misleading association rules we call specious rules. Specious dependencies, also known as spurious, apparent, or illusory associations, refer to a well-known phenomenon where marginal dependencies are merely products of interactions with other variables and disappear when conditioned on those variables. The most extreme example is Yule-Simpson's paradox where two variables present positive dependence in the marginal contingency table but negative in all partial tables defined by different levels of a confounding factor. It is accepted wisdom that in data of any nontrivial dimensionality it is infeasible to control for all of the exponentially many possible confounds of this nature. In this paper, we consider the problem of specious dependencies in the context of statistical association rule mining. We define specious rules and show they offer a unifying framework which covers many types of previously proposed redundant or misleading association rules. After theoretical analysis, we introduce practical algorithms for detecting and pruning out specious association rules efficiently under many key goodness measures, including Mutual information and exact hypergeometric probabilities. We demonstrate that the procedure greatly reduces the number of associations discovered, providing an elegant and effective solution to the problem of association mining discovering large numbers of misleading and redundant rules.",
    keywords = "Association rule, Birch's test, Mutual information, Specious dependency, Yule-Simpson's paradox",
    author = "Wilhelmiina H{\"a}m{\"a}l{\"a}inen and Webb, {Geoffrey I.}",
    year = "2017",
    doi = "10.1137/1.9781611974973.35",
    language = "English",
    pages = "309--317",
    editor = "Chawla, {Nitesh } and Wang, {Wei }",
    booktitle = "Proceedings of the 17th SIAM International Conference on Data Mining",
    publisher = "Society for Industrial and Applied Mathematics SIAM Publications",

    }

    Hämäläinen, W & Webb, GI 2017, Specious rules: An efficient and effective unifying method for removing misleading and uninformative patterns in association rule mining. in N Chawla & W Wang (eds), Proceedings of the 17th SIAM International Conference on Data Mining: Houston, Texas, USA, 27 – 29 April , 2017. Society for Industrial and Applied Mathematics SIAM Publications, Philadelphia, PA, pp. 309-317, SIAM International Conference on Data Mining 2017, Houston, United States of America, 27/04/17. https://doi.org/10.1137/1.9781611974973.35

    Specious rules : An efficient and effective unifying method for removing misleading and uninformative patterns in association rule mining. / Hämäläinen, Wilhelmiina; Webb, Geoffrey I.

    Proceedings of the 17th SIAM International Conference on Data Mining: Houston, Texas, USA, 27 – 29 April , 2017. ed. / Nitesh Chawla; Wei Wang. Philadelphia, PA : Society for Industrial and Applied Mathematics SIAM Publications, 2017. p. 309-317.

    Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

    TY - GEN

    T1 - Specious rules

    T2 - An efficient and effective unifying method for removing misleading and uninformative patterns in association rule mining

    AU - Hämäläinen, Wilhelmiina

    AU - Webb, Geoffrey I.

    PY - 2017

    Y1 - 2017

    N2 - We present theoretical analysis and a suite of tests and procedures for addressing a broad class of redundant and misleading association rules we call specious rules. Specious dependencies, also known as spurious, apparent, or illusory associations, refer to a well-known phenomenon where marginal dependencies are merely products of interactions with other variables and disappear when conditioned on those variables. The most extreme example is Yule-Simpson's paradox where two variables present positive dependence in the marginal contingency table but negative in all partial tables defined by different levels of a confounding factor. It is accepted wisdom that in data of any nontrivial dimensionality it is infeasible to control for all of the exponentially many possible confounds of this nature. In this paper, we consider the problem of specious dependencies in the context of statistical association rule mining. We define specious rules and show they offer a unifying framework which covers many types of previously proposed redundant or misleading association rules. After theoretical analysis, we introduce practical algorithms for detecting and pruning out specious association rules efficiently under many key goodness measures, including Mutual information and exact hypergeometric probabilities. We demonstrate that the procedure greatly reduces the number of associations discovered, providing an elegant and effective solution to the problem of association mining discovering large numbers of misleading and redundant rules.

    AB - We present theoretical analysis and a suite of tests and procedures for addressing a broad class of redundant and misleading association rules we call specious rules. Specious dependencies, also known as spurious, apparent, or illusory associations, refer to a well-known phenomenon where marginal dependencies are merely products of interactions with other variables and disappear when conditioned on those variables. The most extreme example is Yule-Simpson's paradox where two variables present positive dependence in the marginal contingency table but negative in all partial tables defined by different levels of a confounding factor. It is accepted wisdom that in data of any nontrivial dimensionality it is infeasible to control for all of the exponentially many possible confounds of this nature. In this paper, we consider the problem of specious dependencies in the context of statistical association rule mining. We define specious rules and show they offer a unifying framework which covers many types of previously proposed redundant or misleading association rules. After theoretical analysis, we introduce practical algorithms for detecting and pruning out specious association rules efficiently under many key goodness measures, including Mutual information and exact hypergeometric probabilities. We demonstrate that the procedure greatly reduces the number of associations discovered, providing an elegant and effective solution to the problem of association mining discovering large numbers of misleading and redundant rules.

    KW - Association rule

    KW - Birch's test

    KW - Mutual information

    KW - Specious dependency

    KW - Yule-Simpson's paradox

    UR - http://www.scopus.com/inward/record.url?scp=85027873387&partnerID=8YFLogxK

    U2 - 10.1137/1.9781611974973.35

    DO - 10.1137/1.9781611974973.35

    M3 - Conference Paper

    SP - 309

    EP - 317

    BT - Proceedings of the 17th SIAM International Conference on Data Mining

    A2 - Chawla, Nitesh

    A2 - Wang, Wei

    PB - Society for Industrial and Applied Mathematics SIAM Publications

    CY - Philadelphia, PA

    ER -

    Hämäläinen W, Webb GI. Specious rules: An efficient and effective unifying method for removing misleading and uninformative patterns in association rule mining. In Chawla N, Wang W, editors, Proceedings of the 17th SIAM International Conference on Data Mining: Houston, Texas, USA, 27 – 29 April , 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics SIAM Publications. 2017. p. 309-317 https://doi.org/10.1137/1.9781611974973.35