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.

From a top-k list to a diverse subgroup set

Top-k search optimizes individual scores. If one relationship is especially strong, many small variations can fill the list. A diverse result set aims to communicate several themes or to cover different rows. Diversity must therefore be defined as carefully as individual quality Leeuwen & Knobbe, 2012.

Post-process a larger candidate list

Loading...

overlap_filter visits candidates in their given order and accepts one only if its similarity to every previously accepted group is at most the threshold. The default similarity is Jaccard. similarity="overlap" uses intersection divided by the smaller size, and equals one whenever one cover contains the other.

Two other helpers offer different selection criteria:

Different feature sets: 5
Count and lift filter: 5

unique_attributes keeps the first description per set of descriptor features, regardless of their values. statistic_filter uses inclusive bounds on reported statistics. None of these operations searches for replacements outside the candidate list. Start with a larger pool if the filtered list is too short.

Diversity during search: DSSD

DSSD uses diverse beam selection, pools promising descriptions across depths, removes redundant conditions through dominance pruning, and selects a final diverse set. Since its search is heuristic, diversity can change which branches are explored, not merely the final presentation.

Loading...

n_bins=None keeps the supplied numeric conditions. By default, DSSD computes equal-frequency cuts inside the subgroup being refined, with n_bins=6. Its operator also allows multiple negated conditions, or multiple threshold conditions, on one feature. Consequently, it can explore descriptions outside the standard searches’ one-condition-per-feature language.

Selection strategies

selectionDiversity idea
"top_k"Ordinary beam ranking by quality
"description"Avoid almost-identical descriptions with exactly equal quality
"var_description"Limit repeated attribute use
"cover"Discount rows already covered by selected groups
"var_cover"Cover-based selection with a stopping fraction
"compression"Select groups that improve a discrete distribution code
"var_compression"Stop when no candidate shortens the encoding

Cover-based selection multiplies quality by an average row discount. With alpha=0.9, a row already covered cc times receives factor 0.9c0.9^c. These strategies select only positive-quality groups, so results or beams can be smaller than the requested size. Variable-size strategies are also capped by the final result_set_size.

Compression strategies require binary, multiclass, or nominal model attributes. Their connection to WKL is distributional: describing rows with a subgroup-specific code can save bits relative to the global code. The last selected subgroup covering a row determines its code in the package’s compression selection. WKG/Krimp is not implemented.

Measure the set, not just its best member

Loading...

Cover redundancy summarizes uneven/repeated coverage, with lower values indicating less redundancy under its definition. Joint entropy describes the diversity of membership combinations, in bits. Neither replaces the original quality or a domain assessment. Compare sets with their number of subgroups, individual effects, and distinct coverage visible.

Experiment. Change the overlap cutoff from 0.9 to 0.3 and compare the number of retained groups. Can a stricter diversity requirement reduce the best remaining overall coverage even when it reduces repeated themes?

References
  1. van Leeuwen, M., & Knobbe, A. (2012). Diverse Subgroup Set Discovery. Data Mining and Knowledge Discovery, 25, 208–242.