Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

How search works, and which algorithm to choose

With many descriptor attributes, enumerating all conjunctions becomes expensive. Search algorithms organize this enumeration and try to exclude branches that cannot improve the result. Exhaustive and heuristic methods differ in what they guarantee about unvisited descriptions.

Exhaustive algorithms guarantee the optimal top-k quality values within the configured search space, depth, constraints, and quality function. They need not evaluate every description: safe pruning can rule out branches without changing the answer.

For the same task, all compatible exhaustive algorithms produce the same optimal quality values; they differ in runtime, not in solution quality. Choosing between them is therefore a computational decision. Their exploration order, pruning effectiveness, and evaluation machinery affect runtime; memory requirements can differ too. Equal-quality descriptions at the cutoff may differ because a branch whose bound equals the current threshold can be pruned.

Heuristic algorithms do not guarantee the optimal result. They may discard a branch that contains a better subgroup. Their search settings can therefore affect both runtime and the quality of the returned results. In this package, BeamSearch and DSSD are heuristic; all the other searches listed below are exhaustive in their supported settings.

The comparison always assumes the same task and description language. A numeric measure, a generalization-aware measure, and a diversity objective ask different questions; matching guarantees do not make their scores comparable.

A search tree

Starting at the empty description, a search adds a condition at each step:

whole dataset
├── plan=monthly
│   ├── plan=monthly AND contacts>2
│   └── plan=monthly AND tenure≤12
├── contacts>2
│   └── contacts>2 AND tenure≤12
└── tenure≤12

Each conjunction is generated once under a canonical condition ordering. Adding a condition can only remove rows, although it may increase the quality. Pruning by the current quality alone is therefore generally unsafe.

Optimistic estimates

An optimistic estimate oe(G)oe(G) bounds the quality of every permitted refinement HH below GG:

q(H)≤oe(G).q(H)\le oe(G).

It may consider row subsets that no legal description can express. This makes the estimate optimistic: it solves an easier problem than the actual search.

For positive-direction WRAcc, if GG contains t>0t>0 positives, the best arbitrary subset retains those positives and discards every negative. Its bound is

oe(G)=tN(1−p).oe(G)=\frac{t}{N}(1-p).

For example, take N=100N=100 and p=0.2p=0.2. A branch with only two remaining positives has bound 0.016. Once the current top-k threshold is 0.03, no refinement of that branch can enter the results, even if it becomes perfectly pure.

Parent quality: 0.010000000000000002
Refinement bound: 0.016

Bounds can be looser than the best legal refinement. A tighter bound may prune more, but also cost more to compute. This trade-off is particularly important for numeric targets.

General-purpose algorithms

AlgorithmGuaranteeExploration ideaScientific sourcePractical consideration
DFSExhaustiveDepth-first with boundsLemmerich (2014), Chapter 3: subgroup-search strategy reference Lemmerich, 2014Straightforward exhaustive baseline
BestFirstSearchExhaustiveExpand the best estimated open nodeLemmerich (2014), Chapter 3: subgroup-search strategy reference Lemmerich, 2014Can find strong candidates early; stores an open frontier
OPUSExhaustiveReorder active operators and remove pruned operators from siblingsWebb (1995), OPUS_o, Figure 10 Webb, 1995Branch-local operator management
DpSubgroupExhaustiveScore children before descending; choose exploration orderingGrosskreutz et al. (2008), Algorithm 1 and Section 3 Grosskreutz et al., 2008Look-ahead and ordering influence when the threshold rises
AprioriExhaustiveLevel-wise generation using promising sub-conjunctionsAgrawal and Srikant (1994), original Apriori algorithm Agrawal & Srikant, 1994Broad levels can consume substantial memory
SDMapExhaustiveFP-growth conditional treesAtzmueller and Puppe (2006), SD-Map—A Fast Algorithm for Exhaustive Subgroup Discovery Atzmueller & Puppe, 2006Useful alternative organization of the same fixed candidates
SDMapStarExhaustiveFP-growth with bounds, header pruning, and estimate orderingAtzmueller and Lemmerich (2009); Lemmerich et al. (2016), Section 5.3.1 Atzmueller & Lemmerich, 2009Lemmerich et al., 2016Can reduce conditional-tree work
VLSDExhaustiveVertical lists and equivalence classesLopez-Martinez-Carrasco et al. (2023), Algorithms 1–3 Lopez-Martinez-Carrasco et al., 2023Scalar CPU evaluation
BeamSearchHeuristicRetain only a beam of promising descriptions per levelDuivesteijn et al. (2016), Algorithm 1: a subgroup/EMM beam-search reference Duivesteijn et al., 2016Can discard a branch containing a later optimum

DFS, best-first search, and beam search are general search strategies with no single subgroup-discovery invention paper. Their entries cite scientific treatments of the strategy in this setting, rather than claim those works invented the general method. The package’s baseline DFS, best-first, Apriori, and beam-search implementations were adapted from pysubgroup 0.x; its scientific package reference is Lemmerich and Becker (2018) Lemmerich & Becker, 2018.

The original Apriori paper concerns frequent itemsets. Here its level-wise candidate-generation principle is adapted to subgroup discovery, using constraints and optimistic quality bounds. Likewise, the beam-search reference illustrates the strategy; this package’s general BeamSearch uses the task’s fixed candidate conditions, rather than the reference’s EMM-specific numeric refinement behavior.

Algorithms for specific settings

Specialized search does not mean approximate search. NumBSD, GP-growth, and the generalization-aware searches preserve exhaustive guarantees for their supported tasks:

AlgorithmGuaranteeSetting and exploration ideaScientific sourceFurther reading
NumBSDExhaustiveNumeric targets with supported measures; look-ahead DFS over target-ordered bitsets, using ordering-based boundsLemmerich, Atzmueller, and Puppe (2016), Algorithm 1 Lemmerich et al., 2016Numeric targets
GPGrowth (GP-growth)ExhaustivePattern-tree search with aggregated valuation bases, particularly useful for EMM; uses condensed statistics when possible and row sets otherwiseLemmerich, Becker, and Atzmueller (2012), Generic Pattern Trees for Exhaustive Exceptional Model Mining Lemmerich et al., 2012Exceptional Model Mining
GeneralizationAwareAprioriExhaustiveGeneralization-aware measures; level-wise search propagating the largest generalization valueLemmerich (2014), Section 6.3 Lemmerich, 2014Generalization awareness
GeneralizationAwareDFSExhaustiveGeneralization-aware measures; reverse DFS processes the necessary generalizations first and retains their reference valuesLemmerich (2014), Algorithm 4, Section 3.2.1, applied to the measures of Chapter 6 Lemmerich, 2014Generalization awareness
DSSDHeuristicDiverse subgroup sets; diverse beam selection, a candidate pool, dominance pruning, and final set selectionvan Leeuwen and Knobbe (2012), Diverse Subgroup Set Discovery, Algorithm 1 Leeuwen & Knobbe, 2012Diverse subgroup sets

GP-growth is not restricted to EMM: its automatic valuation selection also works with other compatible measures. It changes how subgroup statistics are stored and aggregated, not the measure being optimized. For a supported ordinary task, it therefore agrees in optimal quality with other exhaustive searches.

Generalization-aware measures require a reference computed from simpler descriptions. GeneralizationAwareApriori and GeneralizationAwareDFS supply that reference; ordinary Apriori and DFS do not. The two dedicated searches find the same optimal quality values for the same generalization-aware task. For the DFS variant, the dissertation proposes reverse DFS for these measures but does not evaluate that combination; the package adds the per-node reference tables and batching described in the generalization-awareness chapter.

DSSD is heuristic even with selection="top_k". Its default on-the-fly numeric cuts and its allowance for certain repeated conditions on one feature can also make its search space different from the standard searches’ language. Distinguish this language difference from the absence of an exhaustive guarantee.

Compare searches on the same task

Loading...

In this example, BeamSearch happens to return the same quality values as the other algorithms. That agreement is a coincidence of this dataset, search space, and beam width, not a guarantee of beam search. On another task it may miss a better subgroup.

The first four algorithms—DFS, OPUS, Apriori, and SDMapStar—must agree on the optimal quality values, because they all perform exhaustive search on the same task. Tied descriptions at the cutoff may differ across algorithms: an estimate equal to the current threshold can be pruned. Keep candidate order fixed when checking reproducibility.

If a measure has no optimistic estimate, exhaustive search can still enumerate the space, but cannot prune by quality. Minimum-size pruning may still help. For model-fitting measures, start with a small space or a beam and assess the computational cost.

A practical starting rule

Begin with DFS, a shallow depth, and a useful minimum size. Compare OPUS or another exhaustive method on your actual task if search cost becomes material. Use beam search when a bounded heuristic exploration is acceptable; increasing beam width improves coverage but does not create an exhaustive guarantee.

The beam width must be at least task.result_set_size in this implementation. Use beam_width_adaptive=True to set it to the requested result count.

Experiment. Set both beam_width=1 and result_set_size=1, and increase the depth. Can beam search match the exhaustive best score? Explain why agreement in one experiment cannot establish a guarantee for other data or quality functions.

References
  1. Lemmerich, F. (2014). Novel Techniques for Efficient and Effective Subgroup Discovery [Phdthesis]. University of Würzburg.
  2. Webb, G. I. (1995). OPUS: An Efficient Admissible Algorithm for Unordered Search. Journal of Artificial Intelligence Research, 3, 431–465. 10.1613/jair.227
  3. Grosskreutz, H., Rueping, S., Shaabani, N., & Wrobel, S. (2008). Optimistic Estimate Pruning Strategies for Fast Exhaustive Subgroup Discovery [Techreport]. Fraunhofer IAIS. 10.24406/publica-fhg-293834
  4. Agrawal, R., & Srikant, R. (1994). Fast Algorithms for Mining Association Rules. Proceedings of the 20th International Conference on Very Large Data Bases, 487–499. https://www.vldb.org/conf/1994/P487.PDF
  5. Atzmueller, M., & Puppe, F. (2006). SD-Map—A Fast Algorithm for Exhaustive Subgroup Discovery. Knowledge Discovery in Databases: PKDD 2006, 4213, 6–17. 10.1007/11871637_6
  6. Atzmueller, M., & Lemmerich, F. (2009). Fast Subgroup Discovery for Continuous Target Concepts. Foundations of Intelligent Systems: ISMIS 2009, 5722, 35–44. 10.1007/978-3-642-04125-9_7
  7. Lemmerich, F., Atzmueller, M., & Puppe, F. (2016). Fast Exhaustive Subgroup Discovery with Numerical Target Concepts. Data Mining and Knowledge Discovery, 30(3), 711–762.
  8. Lopez-Martinez-Carrasco, A., Juárez, J. M., Campos, M., & Cánovas-Segura, B. (2023). VLSD—An Efficient Subgroup Discovery Algorithm Based on Equivalence Classes and Optimistic Estimate. Algorithms, 16(6), 274. 10.3390/a16060274
  9. Duivesteijn, W., Feelders, A. J., & Knobbe, A. (2016). Exceptional Model Mining: Supervised Descriptive Local Pattern Mining with Complex Target Concepts. Data Mining and Knowledge Discovery, 30, 47–98.
  10. Lemmerich, F., & Becker, M. (2018). pysubgroup: Easy-to-Use Subgroup Discovery in Python. Machine Learning and Knowledge Discovery in Databases: ECML PKDD 2018, 11053, 658–662. 10.1007/978-3-030-10997-4_46
  11. Lemmerich, F., Becker, M., & Atzmueller, M. (2012). Generic Pattern Trees for Exhaustive Exceptional Model Mining. Machine Learning and Knowledge Discovery in Databases.
  12. van Leeuwen, M., & Knobbe, A. (2012). Diverse Subgroup Set Discovery. Data Mining and Knowledge Discovery, 25, 208–242.