Efficient Constrained Pattern Mining Using Dynamic Item Ordering for Explainable Classification
Efficient Constrained Pattern Mining Using Dynamic Item Ordering for Explainable Classification
复制标题
使用动态项目排序进行有效的约束模式挖掘以进行可解释的分类
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Hiroki Arimura
中科院分区：
文献类型：
--
作者：
H. Iwashita;Takuya Takagi;Hirofumi Suzuki;Keisuke Goto;Kotaro Ohori;Hiroki Arimura
近年来，可解释分类模型的学习一直备受关注。发现能够突出两个类之间的差异的简洁和对比模式非常重要。这种模式对人类专家很有用，可以用来构建强大的分类器。在本文中，我们考虑在监督设置下，在各种约束条件下从高维数据集中挖掘最小的新模式。我们关注的是一个扩展，在这个扩展中，模式可以包含否定项，表示缺少一个项。在这种情况下，数据库变得高度密集，这使得挖掘更具挑战性，因为流行的模式挖掘技术（如fp-tree和occurrence deliver）不能有效地工作。为了解决这一困难，我们提出了一种有效的挖掘最小新模式的算法，该算法结合了两种技术：在模式搜索过程中动态变量排序以增强修剪效果，以及使用基于指针的动态数据结构（称为跳舞链接）来有效地维护出现列表。在基准数据集上的实验表明，我们的算法比基于LCM的新兴模式挖掘方法取得了显著的加速，LCM是一种使用静态变量排序的非常快速的深度优先频繁项集挖掘器。
Learning of interpretable classification models has been attracting much attention for the last few years. Discovery of succinct and contrasting patterns that can highlight the differences between the two classes is very important. Such patterns are useful for human experts, and can be used to construct powerful classifiers. In this paper, we consider mining of minimal emerging patterns from high-dimensional data sets under a variety of constraints in a supervised setting. We focus on an extension in which patterns can contain negative items that designate the absence of an item. In such a case, a database becomes highly dense, and it makes mining more challenging since popular pattern mining techniques such as fp-tree and occurrence deliver do not efficiently work. To cope with this difficulty, we present an efficient algorithm for mining minimal emerging patterns by combining two techniques: dynamic variable-ordering during pattern search for enhancing pruning effect, and the use of a pointer-based dynamic data structure, called dancing links, for efficiently maintaining occurrence lists. Experiments on benchmark data sets showed that our algorithm achieves significant speed-ups over emerging pattern mining approach based on LCM, a very fast depth-first frequent itemset miner using static variable-ordering.