RP-Miner: a relaxed prune algorithm for frequent similar pattern mining
RP-Miner: a relaxed prune algorithm for frequent similar pattern mining
复制标题
DOI：
10.1007/s10115-010-0309-9
复制
发表时间：
2011-06-01
影响因子：
2.7
通讯作者：
Ruiz-Shulcloper, Jose
中科院分区：
文献类型：
--
作者：
Yoan Rodriguez-Gonzalez, Ansel;Francisco Martinez-Trinidad, Jose;Ruiz-Shulcloper, Jose
目前大多数频繁模式挖掘算法都假设两个对象子描述相似，但在实际问题中，通常采用其他方法来计算相似度。最近，三个算法（ObjectMiner，STreeDC-Miner和STreeNDC-Miner）挖掘频繁模式允许不同的相似性函数的平等已经提出。为了搜索频繁模式，ObjectMiner和STreeDC-Miner使用了一个名为向下闭合（Downward Closure）的修剪属性，该属性应该由相似性函数保持。对于不满足此性质的相似度函数，提出了STreeNDC-Miner算法。然而，为了搜索频繁模式，该算法探索所有的特征子集，这可能是非常昂贵的。在这项工作中，我们提出了一个频繁的相似模式挖掘算法的相似性函数，不满足向下闭合属性，这是比STreeNDC-矿工更快，失去更少的频繁相似模式比ObjectMiner和STreeNDC-矿工。此外，我们示出了由我们的算法计算的频繁相似模式的集合的质量相对于由其他算法计算的频繁相似模式的集合的质量，在监督分类的上下文中。
Most of the current algorithms for mining frequent patterns assume that two object subdescriptions are similar if they are equal, but in many real-world problems some other ways to evaluate the similarity are used. Recently, three algorithms (ObjectMiner, STreeDC-Miner and STreeNDC-Miner) for mining frequent patterns allowing similarity functions different from the equality have been proposed. For searching frequent patterns, ObjectMiner and STreeDC-Miner use a pruning property called Downward Closure property, which should be held by the similarity function. For similarity functions that do not meet this property, the STreeNDC-Miner algorithm was proposed. However, for searching frequent patterns, this algorithm explores all subsets of features, which could be very expensive. In this work, we propose a frequent similar pattern mining algorithm for similarity functions that do not meet the Downward Closure property, which is faster than STreeNDC-Miner and loses fewer frequent similar patterns than ObjectMiner and STreeDC-Miner. Also we show the quality of the set of frequent similar patterns computed by our algorithm with respect to the quality of the set of frequent similar patterns computed by the other algorithms, in a supervised classification context.