www-ai.cs.tu-dortmund.de/LEHRE/SEMINARE/SS09/AKTARBEITENDESDM/LITERATUR/WrobelRuepingSubgroup.pdf
LNAI 5211 - Tight Optimistic Estimates for Fast Subgroup Discovery
max m!
1,...,m! c|%i.m!
i#N+&0'm! i'npi
{ c"
i=1
"i(m!, p0, N)} =
max m!
1,...,m! c|%i.m!
i#{0,npi} {
c"
i=1
"i(m!, p0, N)} (
"
j=1,d+1,2d+1,...,c
max m!
1,...,m! c|%i.m!
i#{0,npi} {
j+d(1"
i=j
"i(m!, p0 [...] resp. m):
oe$q(p1, ..., pc, n, p0, N) := max m!
1,...,m! c|m!
i#{0,npi} {q((m!
1, ..., m ! c)
T , p0, N)} (1)
The above is thus the maximum over the 2c possible combinations of values for m!
1, ..., m ! c [...] most npi rows of class i. Hence, a tight optimistic estimate for a quality function q can be calculated as follows:
max m!
1,...,m! c|%i.m!
i#N+&0'm! i'npi
{q((m! 1, ..., m
! c)
T , p0, N)} (2)
446 H. Grosskreutz …
