SHARQ: Explainability Framework for Association Rules on Relational Data
Hadar Ben-Efraim, Susan B. Davidson, Amit Somech · 2024
Read SHARQ: Explainability Framework for Association Rules on Relational Data by Hadar Ben-Efraim, Susan B. Davidson, Amit Somech (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-18522.txt.
Introduction
Ben-Efraim, Davidson, and Somech present a paper from twenty twenty-four on explaining association rules in large datasets. Such rules link attribute pairs that co-occur in records. Users struggle to tell which elements matter most for a rule set. Their score borrows Shapley values from game theory to rate each element's share. Naive scoring grows exponentially with element count. They give a fast exact method for one element that scales near linearly with rule count. A multi-element version shares that work across many elements at once.
Two added uses rate whole rules and whole attributes for importance. Tests on a new benchmark of mined rule sets back the approach. The authors aim to make rule mining outputs readable to analysts.
Catalog record
| CREATOR | Hadar Ben-Efraim, Susan B. Davidson, Amit Somech |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 74 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-18522
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
SHARQ: Explainability Framework for Association Rules on Relational Data Hadar Ben-Efraim, Susan B. Davidson, Amit Somech Abstract . Association rules are an important technique for gaining insights over large relational datasets consisting of tuples of elements (i.e. attribute-value pairs). However, it is difficult to explain the relative importance of data elements with respect to the rules in which they appear. This paper develops a measure of an element’s contribution to a set of association rules based on Shapley values, denoted SHARQ (ShApley Rules Quantification). As is the case with many Shapely-based computations, the cost of a naive calculation of the score is exponential in the number of elements. To that end, we present an efficient framework for computing the exact SHARQ value of a single element whose running time is practically linear in the number of rules. Going one step further, we develop an efficient multi-element SHARQ algorithm which amortizes the cost of the single element SHARQ calculation over a set of elements. Based on the definition of SHARQ for elements we describe two additional use-cases for association rules explainability: rule importance and attribute importance. Extensive experiments over a novel benchmark dataset containing 45 instances of mined rule sets show the effectiveness of our approach. 1. introduction Rule-based pattern mining over large relational datasets consisting of tuples of elements (i.e. attribute-value pairs) is one of the most popular tools in a data scientist’s toolbox ( Diaz-Garcia et al. 2022 ; Agrawal et al. 1993 ) , as it does not requires training data and produces clear data patterns and insights. It has been proven to be highly useful for analyzing data in many application domains, such as E-commerce ( Suchacka and Chodak 2017 ; Dogan et al. 2022 ) , biology ( Creighton and Hanash 2003 ) , cyber security ( Li et al. 2021 ) , and health ( Alam et al. 2019 ; Chang et al. 2018 ) . In particular, association rules mining was used in several research studies on COVID-19 data, and provided important insights ( Katragadda et al. 2021 ; Tandan et al. 2021 ) . Since rule mining tools often return thousands of association rules, which can be overwhelming for users, various techniques have been developed to help manage rules sets. Solutions for this include ranking rules by different interestingness functions ( Bayardo Jr and Agrawal 1999 ; Brin et al. 1997b ; Zhang et al. 2009 ; Freitas 1998 ) and visualization techniques ( Wong et al. 1999 ; Hahsler and Karpienko 2017 ) to help users examine and browse the resulting rule set. However, none of these techniques help users understand the relative importance of the elements with respect to the rules in which they appear. Understanding the relative importance of elements not only enhances an understanding of the rules, but can also help reduce the number of rules as demonstrated in the following example. Age Educ. num Relationship Gender Hrs-per-week Income 25 7 Own-child Female 40 \leq 50K 28 9 Husband Male 50 \geq 50K 29 9 Unmarried Male 40 \leq 50K 44 10 Husband Male 40 \leq 50K Table 1 . Adult ( Adults Income Dataset (UCI) 2024 ) Dataset Sample Example 1.1. A data analyst, Clarice, is examining the Adults dataset ( Adults Income Dataset (UCI) 2024 ) which provides demographic information on individuals (see Table 1 for a small sample of this dataset). Clarice is interested in the associations between the elements in the dataset, and uses an association rule mining algorithm on the dataset. She then focuses on the top-4 rules ranked by the IS score ( Tan and Kumar 2000 ) , a common interestingness measure for association rules that combines both the frequency with which the rule occurs in the dataset ( support ) as well as strength of the relationship between the left- and right-hand sides ( lift ). The rules, alongside their support, lift, and combined IS scores are depicted in Table 2 . These rules include a total of six dataset elements, e_{1} - e_{6} (see the two left-most columns of Table 3 ). Clarice intuitively notices that element e_{1} , (relationship, unmarried), appears to be less important than the others since if it is omitted from r_{1} and r_{4} then the same patterns still hold in r_{2} and r_{3} , with roughly the same IS score. Furthermore, rule r_{3} has fewer elements than r_{2} , so each of its elements, e_{5} and e_{6} , would appear to proportionally contribute more than e_{2} - e_{4} . Despite their high IS score, rules r_{1} and r_{4} therefore appear to be redundant.∎ In a sense, measuring an element’s contribution to a rule set is an explainability problem, yet unlike in Machine Learning (ML) where there are a plethora of techniques to explain the results of an ML model ( Shrikumar et al. 2017 ; Sundararajan et al. 2017 ; Ribeiro et al. 2016 ; Lundberg and Lee 2017a ; Ribeiro et al. 2018 ) (see ( Linardatos et al. 2021 ) for a survey), to our knowledge no such framework exists to explain association rules mined from the data. Furthermore, generic measures of an element’s contribution to a set of rules, e.g. based on the score of the most interesting rule that contains the element or using causality-based notions such as influence ( Pearl et al. 2009 ; Wu and Madden 2013 ) , do not adequately differentiate between elements. Example 1.2. Continuing with the example, Clarice wishes to gauge the importance of each of e_{1} - e_{6} to the examined rule set. She employs two intuitive, generic measures to assess the contribution of an element e to the rules set: I_{TOP}(e) , which returns the IS score of the most interesting rule that contains the element e , and Influence(e) ( Pearl et al. 2009 ; Wu and Madden 2013 ) , which measures the effect of eliminating the element e from the rules set (see Section 2.1 for exact definitions). She is frustrated to find that these measures give identical scores to e_{1} - e_{6} , as shown in columns 3 and 4 in Table 3 . ∎ ID Rule LHS Rule RHS Support Lift IS score ( \times 10^{2} ) r_{1} (age, 44-53), (hours-per-week, 40-50), (relationship, unmarried) (income, >=50K) 0.2 5.25 105 r_{2} (age, 44-53), (hours-per-week, 40-50) (income, >=50K) 0.25 4.08 102 r_{3} (income, <50K) (age, 31-44) 0.43 2.44 105 r_{4} (income, <50K) (age, 31-44), (relationship, unmarried) 0.21 3.33 70 Table 2 . Example rules from the Adult Dataset with corresponding interestingness scores ID Dataset Element I_{Top} Influence SHARQ e_{1} (relationship, unmarried) 1.05 0 -0.6 e_{2} (hours-per-week, 40-50) 1.05 0 -0.05 e_{3} (age, 44-53) 1.05 0 -0.05 e_{4} (income, >=50) 1.05 0 -0.05 e_{5} (age, 31-44) 1.05 0 4.6 e_{6} (income, <50) 1.05 0 4.6 Table 3 . Element contribution scores for elements e_{1} - e_{6} to the rules set in Table 2 Following ideas in the context of explaining ML models ( Lundberg and Lee 2017b ; Lundberg et al. 2020 ) and database query results ( Livshits et al. 2019 ; Davidson et al. 2022a ; Bertossi et al. 2023 ) , in this paper we develop a notion