A data mining formalization to improve hypergraph minimal transversal computation

被引:1
作者
Hebertt, Celine [1 ]
Bretto, Alain [1 ]
Cremilleux, Bruno [1 ]
机构
[1] Univ Caen, Dept Informat, F-14032 Caen, France
关键词
data mining; hypergraph minimal transversals; levelwise framework; condensed representations;
D O I
暂无
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
Finding hypergraph transversals is a major algorithmic issue which was shown having many connections with the data mining area. In this paper, by defining a new Galois connection, we show that this problem is closely related to the mining of the so-called condensed representations of frequent patterns. This data mining formalization enables us to benefit from efficient algorithms, dedicated to the extraction of condensed representations. More precisely, we demonstrate how it is possible to use the levelwise framework to improve the hypergraph minimal transversal computation by exploiting an anti-monotone constraint to safely prune the search space. We propose a new algorithm MTMINER to extract minimal transversals and provide experiments showing that our method is efficient in practice.
引用
收藏
页码:415 / 433
页数:19
相关论文
共 23 条
  • [1] BAILEY J, 2003, P 3 IEEE INT C DAT M
  • [2] Berge C., 1989, Hypergraphs: Combinatorics of Finite Sets
  • [3] BOROS E, 2003, LNCS, V2832
  • [4] Free-sets: A condensed representation of Boolean data for the approximation of frequency queries
    Boulicaut, JF
    Bykowski, A
    Rigotti, C
    [J]. DATA MINING AND KNOWLEDGE DISCOVERY, 2003, 7 (01) : 5 - 22
  • [5] CALDERS T, 2003, LNAI, V2838
  • [6] DAMASCHKE P, 2004, LNCS, V3162
  • [7] DENECKE K, 2000, UNIVERSAL ALGEBRA AP
  • [8] DURAND N, 2006, LNAI, V4203
  • [9] EITER T, 2002, LNCS, V2424
  • [10] On the complexity of dualization of monotone disjunctive normal forms
    Fredman, ML
    Khachiyan, L
    [J]. JOURNAL OF ALGORITHMS, 1996, 21 (03) : 618 - 628