Hierarchical clustering is a critical task in numerous domains. Many approaches are based on heuristics and the properties of the resulting clusterings are studied post hoc. However, in several applications, there is a natural cost function that can be used to characterize the quality of the clustering. In those cases, hierarchical clustering can be seen as a combinatorial optimization problem. To that end, we introduce a new approach based on A* search. We overcome the prohibitively large search space by combining A* with a novel \emph{trellis} data structure. This combination results in an exact algorithm that scales beyond previous state of the art, from a search space with $10^{12}$ trees to $10^{15}$ trees, and an approximate algorithm that improves over baselines, even in enormous search spaces that contain more than $10^{1000}$ trees. We empirically demonstrate that our method achieves substantially higher quality results than baselines for a particle physics use case and other clustering benchmarks. We describe how our method provides significantly improved theoretical bounds on the time and space complexity of A* for clustering.


翻译:在多个领域,等级分组是一项关键的任务。 许多方法基于超自然学, 由此产生的组群的特性在事后研究。 但是, 在若干应用中, 自然成本功能可以用来描述组群的质量。 在这些应用中, 等级分组可以被视为组合优化问题。 为此, 我们根据 A* 搜索引入了一种新的方法。 我们通过将 A* 和新颖的\ emph{ trelis} 数据结构相结合, 克服了令人望而却步的大搜索空间。 这种组合的结果就是, 精确的算法超越了以往的先进水平, 从10 12 美元树的搜索空间到10 15美元树木, 以及超过基线的近似算法。 即便在含有10 10 000美元以上树的巨大搜索空间, 我们从经验上证明, 我们的方法比粒子物理案例和其他组群集基准的基线质量要高得多。 我们描述我们的方法如何大大改进了A* 组合的时间和空间复杂性的理论界限 。

0
下载
关闭预览

相关内容

层次聚类(Hierarchical Clustering)是聚类算法的一种,通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。在聚类树中,不同类别的原始数据点是树的最低层,树的顶层是一个聚类的根节点。
【NeurIPS 2020】大规模分布式鲁棒优化方法
专知会员服务
25+阅读 · 2020年10月13日
【斯坦福大学】矩阵对策的协调方法,89页pdf
专知会员服务
25+阅读 · 2020年9月18日
专知会员服务
52+阅读 · 2020年9月7日
异质信息网络分析与应用综述,软件学报-北京邮电大学
【Manning新书】现代Java实战,592页pdf
专知会员服务
99+阅读 · 2020年5月22日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年6月8日
Arxiv
0+阅读 · 2021年6月4日
Arxiv
5+阅读 · 2017年12月14日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员