Fraunhofer-Gesellschaft

Publica

Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Fast discovery of relevant subgroups using a reduced search space

 
: Grosskreutz, H.; Paurat, D.

:
Volltext urn:nbn:de:0011-n-1509495 (301 KByte PDF)
MD5 Fingerprint: be2f7fd045463e37b151861a77c8b354
Erstellt am: 18.1.2011


Sankt Augsutin: Fraunhofer IAIS, 2010, 12 S.
Englisch
Bericht, Elektronische Publikation
Fraunhofer IAIS ()

Abstract
We consider a modified version of the local pattern discovery task of subgroup discovery, where subgroups dominated by other subgroups are discarded. The advantage of this modified task, known as relevant subgroup discovery, is that it avoids redundancy in the outcome. Although it was considered in many applications, so far no efficient and exact algorithm for this task has been proposed. One particular problem is that the correctness is not guaranteed if the standard pruning approach is applied. In this paper, we devise a new algorithm based on two ideas: For one, we use the theory of closed sets for labeled data to reduce the candidate space; for another we introduce a special search space traversal which allows the use of optimistic estimate pruning while guaranteeing the correctness of the solution. We show that although our algorithm solves a more valuable task than other (classical) approaches, it outperforms all existing subgroup discovery algorithms.

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