Lakhasly

If a high quality subgroup is present, it is very likely that several variants of this subgroup exist, which are also evaluated as good subgroups (e.g., by adding a constraint A = v for some attribute A and a rare feature v).Furthermore, deviation analysis typically focusses on a target variable rather than associations between any attributes, which offers some optimization potential [6].If it is possible to transform the database such that association mining (e.g., via the Apriori algorithm) can be applied, the validation and ranking of the patterns found are merely a post-processing step [15].Thus, it may happen that 198 7 Finding Patterns many of the subgroups in the beam are variations of a single scheme, which prevents the beam search from focussing on other parts of the dataspace--a small number of diverse subgroups would be preferable.A subset of diverse subsets can be extracted from the beam by selecting successively those subgroups that cover most of the data.Exhaustive searching is prohibitive unless intelligent pruning techniques are applied that prevent us from losing to much time with redundant, uninteresting subgroups.For nominal target variables, efficient algorithms from association rule mining can be utilized.If most of the subgroups in the beam are variations of one core subgroup, only a few diversive subgroups will be selected.Thereby subgroups cannot be rediscovered, but the method has to focus on different parts of the dataspace. 8).

If a high quality subgroup is present, it is very likely that several variants of this
subgroup exist, which are also evaluated as good subgroups (e.g., by adding a constraint
A = v for some attribute A and a rare feature v). Thus, it may happen that
198 7 Finding Patterns
many of the subgroups in the beam are variations of a single scheme, which prevents
the beam search from focussing on other parts of the dataspace—a small number of
diverse subgroups would be preferable. A subset of diverse subsets can be extracted
from the beam by selecting successively those subgroups that cover most of the
data. Once a subgroup has been selected, the covered data is excluded from the subsequent
selection steps [24]. If most of the subgroups in the beam are variations of
one core subgroup, only a few diversive subgroups will be selected. A better approach
is a sequential covering search, where good subgroups are discovered one
after the other. Over several runs, only a few or a single best subgroup is identified,
and the data covered by this subgroup is then excluded from subsequent runs.
Thereby subgroups cannot be rediscovered, but the method has to focus on different
parts of the dataspace. Similar techniques are applied for learning sets of classification
rules (see Chap. 8). It is also possible to generate a new sample from the
original dataset that no longer exhibits the unusualness that has been discovered by
a given subgroup [48]. If this subsampling is applied before any subsequent run,
new subgroups rather than known subgroups will be discovered.
Another issue is the efficiency of search, the scalability to large datasets. Exhaustive
searching is prohibitive unless intelligent pruning techniques are applied
that prevent us from losing to much time with redundant, uninteresting subgroups.
On the other hand, any kind of heuristic search (like beam search) bears the risk of
missing the most interesting subgroups. There are multiple directions how to attack
this problem.
For nominal target variables, efficient algorithms from association rule mining
can be utilized. If it is possible to transform the database such that association mining
(e.g., via the Apriori algorithm) can be applied, the validation and ranking of
the patterns found are merely a post-processing step [15]. Missing values require
special care in this approach, as the case of missing data is usually not considered
in market basket analysis. Furthermore, deviation analysis typically focusses on a
target variable rather than associations between any attributes, which offers some
optimization potential [6].
If the dataset size becomes an issue, one may use a subsample to test and rank
subgroups rather than the full dataset. For a broad range of quality measures, one
can derive upper bounds for the size of the sample with guaranteed upper bounds
on the subgroup quality estimation error [47]. This speeds up the discovery process
considerably, because there is no need for a full database scan.