Reverse search is a convenient method for enumerating structured objects, that can be used both to address theoretical issues and to solve data mining problems. This method has already been successfully developed to handle unordered trees. If the literature proposes solutions to enumerate singletons of trees, we study in this article a more general, higher combinatorial problem, the enumeration of sets of trees - forests. By compressing each forest into a Directed Acyclic Graph (DAG), we develop a reverse search like method to enumerate DAG compressing forests. Remarkably, we prove that these DAG are in bijection with the row-Fishburn matrices, a well-studied class of combinatorial objects. In a second step, we derive our forest enumeration to provide algorithms for tackling two related problems : (i) the enumeration of "subforests" of a forest, and (ii) the frequent "subforest" mining problem. All the methods presented in this article enumerate each item uniquely, up to isomorphism.


翻译:反向搜索是计算结构化物体的方便方法,可用于处理理论问题和数据挖掘问题。这种方法已经成功地开发出来,可以处理无序树木。如果文献提出单吨树木的计算方法,我们在本条中研究一个更一般、更高级的组合问题,即树木组群-森林。通过将每个森林压缩成一个定向环形图(DAG),我们开发了一个反向搜索方法,以罗列DAG压缩森林。值得注意的是,我们证明这些DAG与行-Fishburn矩阵是双向的,这是经过仔细研究的组合对象类别。第二步,我们从森林查点中找出方法,为处理两个相关问题提供算法:(一) 森林“子森林”的计数,和(二) 频繁的“子森林”采矿问题。本文章提出的所有方法都列出了每个独特项目,直至无形态学。

0
下载
关闭预览

相关内容

【CVPR2021】用于目标检测的通用实例蒸馏
专知会员服务
23+阅读 · 2021年3月22日
专知会员服务
53+阅读 · 2020年10月11日
专知会员服务
39+阅读 · 2020年9月6日
专知会员服务
159+阅读 · 2020年1月16日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
R文本分类之RTextTools
R语言中文社区
4+阅读 · 2018年1月17日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【 关关的刷题日记47】Leetcode 38. Count and Say
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
35+阅读 · 2021年1月27日
Principal Neighbourhood Aggregation for Graph Nets
Arxiv
17+阅读 · 2020年6月7日
Foreground-aware Image Inpainting
Arxiv
4+阅读 · 2019年1月17日
Arxiv
3+阅读 · 2018年2月20日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
R文本分类之RTextTools
R语言中文社区
4+阅读 · 2018年1月17日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【 关关的刷题日记47】Leetcode 38. Count and Say
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员