2015/02/15 by Felipe Llinares López, López, Felipe Llinares, Mahito Sugiyama +5 · 1 citation
Computer Science · Decision Sciences · #Algorithms and Data Compression #Data Mining Algorithms and Applications #Data Quality and Management #FOS: Computer and information sciences #Imbalanced Data Classification Techniques #Machine Learning (stat.ML)
paper · pdf · doi:10.48550/arxiv.1502.04315
openalex publication_date 2015/02/15 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
We present a novel algorithm, Westfall-Young light, for detecting patterns,\nsuch as itemsets and subgraphs, which are statistically significantly enriched\nin one of two classes. Our method corrects rigorously for multiple hypothesis\ntesting and correlations between patterns through the Westfall-Young\npermutation procedure, which empirically estimates the null distribution of\npattern frequencies in each class via permutations. In our experiments,\nWestfall-Young light dramatically outperforms the current state-of-the-art\napproach in terms of both runtime and memory efficiency on popular real-world\nbenchmark datasets for pattern mining. The key to this efficiency is that\nunlike all existing methods, our algorithm neither needs to solve the\nunderlying frequent itemset mining problem anew for each permutation nor needs\nto store the occurrence list of all frequent patterns. Westfall-Young light\nopens the door to significant pattern mining on large datasets that previously\nled to prohibitive runtime or memory costs.\n