Fraunhofer-Gesellschaft

Publica

Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Optimistic estimate pruning strategies for fast exhaustive subgroup discovery

 
: Grosskreutz, H.; Rüping, S.; Shabaani, N.; Wrobel, S.

:
Volltext urn:nbn:de:0011-n-723406 (223 KByte PDF)
MD5 Fingerprint: fb20d1a6bb12dc06aee8bca505fcb7fa
Erstellt am: 29.4.2008


Sankt Augsutin: Fraunhofer IAIS, 2008, 9 S.
Englisch
Bericht, Elektronische Publikation
Fraunhofer IAIS ()

Abstract
Subgroup discovery is the task of finding subgroups of a population which exhibit both distributional unusualness and high generality at the same time. Since the corresponding evaluation functions are not monotonic, the standard pruning techniques from monotonic problems such as frequent set discovery cannot be used. In this paper, we show that optimistic estimate pruning, previously considered only in a very simple and heuristic way, can be developed into a sound and highly effective pruning approach for subgroup discovery. We present and prove new optimistic estimates for several commonly used subgroup quality functions, describe a subgroup discovery algorithm with novel exploration strategies based on optimistic estimates, and show that this algorithm significantly outperforms previous algorithms by a wide margin of an order of magnitude or more.

: http://publica.fraunhofer.de/dokumente/N-72340.html