SHARQ: Explainability Framework for Association Rules on Relational Data
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916544760512512 |
|---|---|
| author | Ben-Efraim, Hadar Davidson, Susan B. Somech, Amit |
| author_facet | Ben-Efraim, Hadar Davidson, Susan B. Somech, Amit |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_18522 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | SHARQ: Explainability Framework for Association Rules on Relational Data Ben-Efraim, Hadar Davidson, Susan B. Somech, Amit Databases 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. |
| title | SHARQ: Explainability Framework for Association Rules on Relational Data |
| topic | Databases |
| url | https://arxiv.org/abs/2412.18522 |