HARMONY: Efficiently Mining the Best Rules for Classification
HARMONY: Efficiently Mining the Best Rules for Classification
复制标题
DOI：
10.1137/1.9781611972757.19
复制
发表时间：
2005-12
期刊：
影响因子：
--
通讯作者：
Jianyong Wang;G. Karypis
中科院分区：
文献类型：
--
作者：
Jianyong Wang;G. Karypis
许多研究表明，基于规则的分类器在分类分类和稀疏高维数据库方面表现良好。然而，许多基于规则的分类器的一个基本限制是，它们通过采用各种启发式方法来修剪搜索空间来找到规则，并基于顺序数据库覆盖范式来选择规则。因此，他们使用的最终规则集可能不是训练数据库中某些实例的全局最佳规则。更糟糕的是，这些算法无法充分利用一些更有效的搜索空间修剪方法来扩展到大型数据库。在本文中，我们提出了一种新的分类器 HARMONY，它直接挖掘最终的分类规则集。 HARMONY 使用以实例为中心的规则生成方法，它可以确保对于每个训练实例，覆盖该实例的最高置信度规则之一包含在最终规则集中，这有助于提高分类器的整体准确性。通过在规则发现过程中引入多种新颖的搜索策略和剪枝方法，HARMONY还具有高效率和良好的可扩展性。我们对一些大型文本和分类数据库进行的彻底的性能研究表明，HARMONY 在准确性和计算效率方面优于许多著名的分类器，并且可以很好地扩展。数据库大小。
Many studies have shown that rule-based classiers perform well in classifying categorical and sparse high-dimensional databases. However, a fundamental limitation with many rule-based classiers is that they nd the rules by employing various heuristic methods to prune the search space, and select the rules based on the sequential database covering paradigm. As a result, the nal set of rules that they use may not be the globally best rules for some instances in the training database. To make matters worse, these algorithms fail to fully exploit some more eectiv e search space pruning methods in order to scale to large databases. In this paper we present a new classier, HARMONY, which directly mines the nal set of classication rules. HARMONY uses an instance-centric rule-generation approach and it can assure for each training instance, one of the highest-condence rules covering this instance is included in the nal rule set, which helps in improving the overall accuracy of the classier. By introducing several novel search strategies and pruning methods into the rule discovery process, HARMONY also has high eciency and good scalability. Our thorough performance study with some large text and categorical databases has shown that HARMONY outperforms many well-known classiers in terms of both accuracy and computational eciency , and scales well w.r.t. the database size.