DEvIANT: discovering significant exceptional (dis-)agreement within groups

Adnene Belfodil; Wouter Duivesteijn; Marc Plantevit; Sylvie Cazalens; Philippe Lamarre

doi:10.1007/978-3-030-46150-8_1

DEvIANT: discovering significant exceptional (dis-)agreement within groups

Adnene Belfodil, Wouter Duivesteijn, Marc Plantevit, Sylvie Cazalens, Philippe Lamarre

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Citation (Scopus)

Abstract

We strive to find contexts (i.e., subgroups of entities) under which exceptional (dis-)agreement occurs among a group of individuals, in any type of data featuring individuals (e.g., parliamentarians, customers) performing observable actions (e.g., votes, ratings) on entities (e.g., legislative procedures, movies). To this end, we introduce the problem of discovering statistically significant exceptional contextual intra-group agreement patterns. To handle the sparsity inherent to voting and rating data, we use Krippendorff’s Alpha measure for assessing the agreement among individuals. We devise a branch-and-bound algorithm, named DEvIANT, to discover such patterns. DEvIANT exploits both closure operators and tight optimistic estimates. We derive analytic approximations for the confidence intervals (CIs) associated with patterns for a computationally efficient significance assessment. We prove that these approximate CIs are nested along specialization of patterns. This allows to incorporate pruning properties in DEvIANT to quickly discard non-significant patterns. Empirical study on several datasets demonstrates the efficiency and the usefulness of DEvIANT.

Original language	English
Title of host publication	Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2019, Proceedings
Subtitle of host publication	European Conference, ECML PKDD 2019, Würzburg, Germany, September 16–20, 2019, Proceedings, Part I
Editors	Ulf Brefeld, Elisa Fromont, Andreas Hotho, Arno Knobbe, Marloes Maathuis, Céline Robardet
Place of Publication	Cham
Publisher	Springer Nature
Pages	3-20
Number of pages	18
ISBN (Electronic)	978-3-030-46150-8
ISBN (Print)	978-3-030-46149-2
DOIs	https://doi.org/10.1007/978-3-030-46150-8_1
Publication status	Published - 2020
Event	2019 European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD 2019) - Wurzburg, Germany Duration: 16 Sep 2019 → 20 Sep 2019 Conference number: 19 http://ecmlpkdd2019.org/

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11906 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	2019 European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD 2019)
Abbreviated title	ECML PKDD 2019
Country/Territory	Germany
City	Wurzburg
Period	16/09/19 → 20/09/19
Internet address	http://ecmlpkdd2019.org/

Access to Document

10.1007/978-3-030-46150-8_1

Cite this

Belfodil, A., Duivesteijn, W., Plantevit, M., Cazalens, S., & Lamarre, P. (2020). DEvIANT: discovering significant exceptional (dis-)agreement within groups. In U. Brefeld, E. Fromont, A. Hotho, A. Knobbe, M. Maathuis, & C. Robardet (Eds.), Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2019, Proceedings: European Conference, ECML PKDD 2019, Würzburg, Germany, September 16–20, 2019, Proceedings, Part I (pp. 3-20). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11906 LNAI). Springer Nature. https://doi.org/10.1007/978-3-030-46150-8_1

Belfodil, Adnene ; Duivesteijn, Wouter ; Plantevit, Marc ; Cazalens, Sylvie ; Lamarre, Philippe. / DEvIANT : discovering significant exceptional (dis-)agreement within groups. Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2019, Proceedings: European Conference, ECML PKDD 2019, Würzburg, Germany, September 16–20, 2019, Proceedings, Part I. editor / Ulf Brefeld ; Elisa Fromont ; Andreas Hotho ; Arno Knobbe ; Marloes Maathuis ; Céline Robardet. Cham : Springer Nature, 2020. pp. 3-20 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{935bb738b0844f3a9003864358e12491,

title = "DEvIANT: discovering significant exceptional (dis-)agreement within groups",

abstract = "We strive to find contexts (i.e., subgroups of entities) under which exceptional (dis-)agreement occurs among a group of individuals, in any type of data featuring individuals (e.g., parliamentarians, customers) performing observable actions (e.g., votes, ratings) on entities (e.g., legislative procedures, movies). To this end, we introduce the problem of discovering statistically significant exceptional contextual intra-group agreement patterns. To handle the sparsity inherent to voting and rating data, we use Krippendorff{\textquoteright}s Alpha measure for assessing the agreement among individuals. We devise a branch-and-bound algorithm, named DEvIANT, to discover such patterns. DEvIANT exploits both closure operators and tight optimistic estimates. We derive analytic approximations for the confidence intervals (CIs) associated with patterns for a computationally efficient significance assessment. We prove that these approximate CIs are nested along specialization of patterns. This allows to incorporate pruning properties in DEvIANT to quickly discard non-significant patterns. Empirical study on several datasets demonstrates the efficiency and the usefulness of DEvIANT.",

author = "Adnene Belfodil and Wouter Duivesteijn and Marc Plantevit and Sylvie Cazalens and Philippe Lamarre",

year = "2020",

doi = "10.1007/978-3-030-46150-8_1",

language = "English",

isbn = "978-3-030-46149-2",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Nature",

pages = "3--20",

editor = "Ulf Brefeld and Elisa Fromont and Andreas Hotho and Arno Knobbe and Marloes Maathuis and C{\'e}line Robardet",

booktitle = "Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2019, Proceedings",

address = "Singapore",

note = "2019 European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD 2019), ECML PKDD 2019 ; Conference date: 16-09-2019 Through 20-09-2019",

url = "http://ecmlpkdd2019.org/",

}

Belfodil, A, Duivesteijn, W, Plantevit, M, Cazalens, S & Lamarre, P 2020, DEvIANT: discovering significant exceptional (dis-)agreement within groups. in U Brefeld, E Fromont, A Hotho, A Knobbe, M Maathuis & C Robardet (eds), Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2019, Proceedings: European Conference, ECML PKDD 2019, Würzburg, Germany, September 16–20, 2019, Proceedings, Part I. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11906 LNAI, Springer Nature, Cham, pp. 3-20, 2019 European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD 2019), Wurzburg, Germany, 16/09/19. https://doi.org/10.1007/978-3-030-46150-8_1

DEvIANT : discovering significant exceptional (dis-)agreement within groups. / Belfodil, Adnene; Duivesteijn, Wouter; Plantevit, Marc; Cazalens, Sylvie; Lamarre, Philippe.

Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2019, Proceedings: European Conference, ECML PKDD 2019, Würzburg, Germany, September 16–20, 2019, Proceedings, Part I. ed. / Ulf Brefeld; Elisa Fromont; Andreas Hotho; Arno Knobbe; Marloes Maathuis; Céline Robardet. Cham : Springer Nature, 2020. p. 3-20 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11906 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - DEvIANT

T2 - 2019 European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD 2019)

AU - Belfodil, Adnene

AU - Duivesteijn, Wouter

AU - Plantevit, Marc

AU - Cazalens, Sylvie

AU - Lamarre, Philippe

N1 - Conference code: 19

PY - 2020

Y1 - 2020

N2 - We strive to find contexts (i.e., subgroups of entities) under which exceptional (dis-)agreement occurs among a group of individuals, in any type of data featuring individuals (e.g., parliamentarians, customers) performing observable actions (e.g., votes, ratings) on entities (e.g., legislative procedures, movies). To this end, we introduce the problem of discovering statistically significant exceptional contextual intra-group agreement patterns. To handle the sparsity inherent to voting and rating data, we use Krippendorff’s Alpha measure for assessing the agreement among individuals. We devise a branch-and-bound algorithm, named DEvIANT, to discover such patterns. DEvIANT exploits both closure operators and tight optimistic estimates. We derive analytic approximations for the confidence intervals (CIs) associated with patterns for a computationally efficient significance assessment. We prove that these approximate CIs are nested along specialization of patterns. This allows to incorporate pruning properties in DEvIANT to quickly discard non-significant patterns. Empirical study on several datasets demonstrates the efficiency and the usefulness of DEvIANT.

AB - We strive to find contexts (i.e., subgroups of entities) under which exceptional (dis-)agreement occurs among a group of individuals, in any type of data featuring individuals (e.g., parliamentarians, customers) performing observable actions (e.g., votes, ratings) on entities (e.g., legislative procedures, movies). To this end, we introduce the problem of discovering statistically significant exceptional contextual intra-group agreement patterns. To handle the sparsity inherent to voting and rating data, we use Krippendorff’s Alpha measure for assessing the agreement among individuals. We devise a branch-and-bound algorithm, named DEvIANT, to discover such patterns. DEvIANT exploits both closure operators and tight optimistic estimates. We derive analytic approximations for the confidence intervals (CIs) associated with patterns for a computationally efficient significance assessment. We prove that these approximate CIs are nested along specialization of patterns. This allows to incorporate pruning properties in DEvIANT to quickly discard non-significant patterns. Empirical study on several datasets demonstrates the efficiency and the usefulness of DEvIANT.

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

U2 - 10.1007/978-3-030-46150-8_1

DO - 10.1007/978-3-030-46150-8_1

M3 - Conference contribution

SN - 978-3-030-46149-2

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 3

EP - 20

BT - Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2019, Proceedings

A2 - Brefeld, Ulf

A2 - Fromont, Elisa

A2 - Hotho, Andreas

A2 - Knobbe, Arno

A2 - Maathuis, Marloes

A2 - Robardet, Céline

PB - Springer Nature

CY - Cham

Y2 - 16 September 2019 through 20 September 2019

ER -

Belfodil A, Duivesteijn W, Plantevit M, Cazalens S, Lamarre P. DEvIANT: discovering significant exceptional (dis-)agreement within groups. In Brefeld U, Fromont E, Hotho A, Knobbe A, Maathuis M, Robardet C, editors, Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2019, Proceedings: European Conference, ECML PKDD 2019, Würzburg, Germany, September 16–20, 2019, Proceedings, Part I. Cham: Springer Nature. 2020. p. 3-20. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-030-46150-8_1

DEvIANT: discovering significant exceptional (dis-)agreement within groups

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this