Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Data Mining and Knowledge Discovery
Erschienen in: Data Mining and Knowledge Discovery 4/2023

06.05.2023

ROhAN: Row-order agnostic null models for statistically-sound knowledge discovery

verfasst von: Maryam Abuissa, Alexander Lee, Matteo Riondato

Erschienen in: Data Mining and Knowledge Discovery | Ausgabe 4/2023

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We introduce a novel class of null models for the statistical validation of results obtained from binary transactional and sequence datasets. Our null models are Row-Order Agnostic (ROA), i.e., do not consider the order of rows in the observed dataset to be fixed, in stark contrast with previous null models, which are Row-Order Enforcing (ROE). We present ROhAN, an algorithmic framework for efficiently sampling datasets from ROA models according to user-specified distributions, which is a necessary step for the resampling-based statistical hypothesis tests employed to validate the results. ROhAN uses Metropolis-Hastings or rejection sampling to build on top of existing or future ROE sampling procedures. Our experimental evaluation shows that ROA models are very different from ROE ones, impacting the statistical validation, and that ROhAN is efficient, mixes fast, and scales well as the dataset grows.
Vorheriger Artikel A combinatorial multi-armed bandit approach to correlation clustering

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Fußnoten
1
Throughout this work, we use “significant” to mean “statistically significant”.
 
2
We drop “binary” and just use “transactional” in the rest of this work.
 
3
When considering the order of transactions as fixed, as ROE models do, there is a 1:1 correspondence between transactional datasets and binary matrices. The row sums correspond to the transaction lengths, and the column sum to the supports of single items.
 
4
Preserving properties exactly can partially be incorporated in these null models, but they usually make it impossible to derive a closed form for \(\pi\), with relevant computational consequences. The same is also true for many complex in-expectation constraints (Cimini et al. 2019).
 
5
We do not indicate this fact in the notation, to keep it light.
 
6
Gionis et al. (2007) focus on the case where \(\pi\) is the uniform distribution, but extending their discussion to a generic \(\pi\) is straightforward.
 
7
If not even earlier.
 
8
Some presentations of the algorithms mention a “transaction identifier” associated to each transaction, but this identifier is used only to uniquely label transactions, not for the purpose of ordering the rows, and it is in part a leftover of the idea that a transactional dataset is stored in a table in a relational database.
 
9
We assume \(\left( {\begin{array}{c}0\\ 0,\dotsc , 0\end{array}}\right) = 1\).
 
10
Other definitions of Q are possible. Deriving, for example, a tight lower bound \(b \le \min _{\mathcal {D}\in \mathcal {Z}_{\textrm{A}}} \textsf{c}(\mathcal {D})\) can be used to define \(Q \doteq {\left| {\mathcal {Z}_{\textrm{E}}}\right| }/{(\left| {\mathcal {Z}_{\textrm{A}}}\right| b)}\), which would lead to more samples being accepted. We leave this derivation to future work.
 
12
The other parameters of the generator were left to their default values.
 
Literatur
Agrawal R, Srikant R (1994) Fast algorithms for mining association rules in large databases. In: Proc. 20th Int. Conf. Very Large Data Bases. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, VLDB ’94, pp 487–499
Casella G, Robert CP, Wells MT (2004) Generalized accept-reject sampling schemes. In: A Festschrift for Herman Rubin, IMS Lecture Notes - Monograph Series, vol 45. IMS, p 342–347
Chen Y, Diaconis P, Holmes SP et al. (2005) Sequential monte carlo methods for statistical analysis of tables. J Am Stat Assoc 100(469):109–120MathSciNetCrossRefMATH
Cimini G, Squartini T, Saracco F et al. (2019) The statistical physics of real-world networks. Nature Rev Phys 1(1):58–71CrossRef
Connor EF, Simberloff D (1979) The assembly of species communities: chance or competition? Ecology 60(6):1132–1140CrossRef
Dalleiger S, Vreeken J (2022) Discovering significant patterns under sequential false discovery control. In: Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. ACM, KDD ’22
Fout AM (2022) New methods for fixed-margin binary matrix sampling, Fréchet covariance, and MANOVA tests for random objects in multiple metric spaces. PhD thesis, Colorado State University
Gionis A, Mannila H, Mielikäinen T et al. (2007) Assessing data mining results via swap randomization. ACM Trans Knowl Dis from Data (TKDD) 1(3):14CrossRef
Gwadera R, Crestani F (2010) Ranking sequential patterns with respect to significance. In: Pacific-Asia Conference on Knowledge Discovery and Data Mining, Springer, pp 286–299
Hrovat G, Fister IJr, Yermak K, et al. (2015) Interestingness measure for mining sequential patterns in sports. Journal of Intelligent & Fuzzy Systems 29(5):1981–1994
Jenkins S, Walzer-Goldfeld S, Riondato M (2022) SPEck: mining statistically-significant sequential patterns efficiently with exact sampling. Data Min Knowl Disc 36(4):1575–1599MathSciNetCrossRefMATH
Lehmann EL, Romano JP (2022) Testing Statistical Hypotheses, 4th edn. Springer, BerlinCrossRefMATH
Low-Kam C, Raïssi C, Kaytoue M, et al. (2013) Mining statistically significant sequential patterns. In: 2013 IEEE 13th International Conference on Data Mining, IEEE, pp 488–497
Méger N, Rigotti C, Pothier C (2015) Swap randomization of bases of sequences for mining satellite image times series. In: Joint European Conference on Machine Learning and Knowledge Discovery in Databases, Springer, pp 190–205
Megiddo N, Srikant R (1998) Discovering predictive association rules. In: Proceedings of the 4th International Conference on Knowledge Discovery and Data Mining, KDD ’98, pp 274–278
Mitzenmacher M, Upfal E (2005) Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press
Pei J, Han J, Mortazavi-Asl B et al. (2004) Mining sequential patterns by pattern-growth: the PrefixSpan approach. IEEE Trans Knowl Data Eng 16(11):1424–1440CrossRef
Pellegrina L, Riondato M, Vandin F (2019) Hypothesis testing and statistically-sound pattern mining. In: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM, New York, NY, USA, KDD ’19, pp 3215–3216, https://​doi.​org/​10.​1145/​3292500.​3332286,
Pinxteren S, Calders T (2021) Efficient permutation testing for significant sequential patterns. In: Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), SIAM, pp 19–27
Preti G, De Francisci Morales G, Riondato M (2022) Alice and the caterpillar: A more descriptive null models for assessing data mining results. In: Proceedings of the 22nd IEEE International Conference on Data Mining, pp 418–427
Stanley RP (2011) Enumerative Combinatorics, vol 1, 2nd edn. Cambridge University Press
Tonon A, Vandin F (2019) Permutation strategies for mining significant sequential patterns. In: 2019 IEEE International Conference on Data Mining (ICDM), IEEE, pp 1330–1335
Vreeken J, Tatti N (2014) Interesting patterns. In: Frequent pattern mining. Springer, p 105–134
Wang G (2020) A fast MCMC algorithm for the uniform sampling of binary matrices with fixed margins. Electron J Statistics 14(1):1690–1706MathSciNetCrossRefMATH
Westfall PH, Young SS (1993) Resampling-based multiple testing: Examples and methods for p-value adjustment. John Wiley & Sons
Zimmermann A (2014) The data problem in data mining. SIGKDD Explor 16(2):38–45CrossRef
Metadaten
Titel
ROhAN: Row-order agnostic null models for statistically-sound knowledge discovery
verfasst von
Maryam Abuissa
Alexander Lee
Matteo Riondato
Publikationsdatum
06.05.2023
Verlag
Springer US
Erschienen in
Data Mining and Knowledge Discovery / Ausgabe 4/2023
Print ISSN: 1384-5810
Elektronische ISSN: 1573-756X
DOI
https://doi.org/10.1007/s10618-023-00938-4

Weitere Artikel der Ausgabe 4/2023

Data Mining and Knowledge Discovery 4/2023 Zur Ausgabe

OriginalPaper

Making clusterings fairer by post-processing: algorithms, complexity results and experiments

OriginalPaper

A spatiotemporal deep neural network for fine-grained multi-horizon wind prediction

OriginalPaper

Differentially private tree-based redescription mining

OriginalPaper

A combinatorial multi-armed bandit approach to correlation clustering

OriginalPaper

A graph convolutional fusion model for community detection in multiplex networks

OriginalPaper

On the evaluation of outlier detection and one-class classification: a comparative study of algorithms, model selection, and ensembles

Premium Partner

    Bildnachweise