SAME: Similarity-Aware Monotonic Entropy for FWER-controlled association-rule mining without a minimum-support threshold

Abstract

Every classical frequent-itemset miner asks the user for one number it cannot supply with confidence: the minimum support σ. Pick it too low and the output drowns in trivial associations;pick it too high and rare but meaningful patterns disappear; and whatever value is chosen, thereturned rules carry no control over how many are false positives. We present SAME (SimilarityAdaptive Monotonic Entropy), an unsupervised miner for binary data that does away with σand instead derives its support threshold from the information content of each candidate, thenattaches a Tarone–Bonferroni family-wise-error-rate (FWER) bound to every rule it reports.SAME is not parameter-free in the strict sense: it keeps a few internal constants, a Hoeffdingfraction and a persistence threshold, both with data-derived defaults, but it asks the user for nominimum-support value. A strictly monotonic transform of the binary Shannon entropy givesan information gain on [0,1]; from it we build a single adaptive threshold valid for every itemsetsize, prove that the resulting early-exit prunes safely under a non-monotone threshold surface,and prove that the adaptive pre-filter leaves Tarone’s testability bound intact so the FWERguarantee survives. A Matthews-rescaled cohesion keeps the threshold honest on data wheresymmetric co-occurrence measures collapse. The implementation uses Roaring bitmaps andships as the same-fim package on PyPI, with a script that rebuilds every table and figure. Weevaluate on five public datasets and fourteen baselines, four of them significance-aware methodsreproduced inside Docker, and we are explicit about where SAME is the right tool and whereit is not: it suits moderate-to-dense binary matrices with a modest number of columns, and weleave very sparse or very wide transactional data to classical σ-based miners. On the dense-tomoderate datasets SAME returns rule inventories comparable to a supervised significance minerwhile needing no label, and 200 of its rules reach macro-F1 = 0.777 on ABIDE against 0.627 formatched Apriori rules.