• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Artificial intelligence >Cost-optimal constrained correlation clustering via weighted partial Maximum Satisfiability
【24h】

Cost-optimal constrained correlation clustering via weighted partial Maximum Satisfiability

机译：通过加权部分最大可满足性的成本最优约束相关性聚类

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Integration of the fields of constraint solving and data mining and machine learning has recently been identified within the AI community as an important research direction with high potential. This work contributes to this direction by providing a first study on the applicability of state-of-the-art Boolean optimization procedures to cost-optimal correlation clustering under constraints in a general similarity-based setting. We develop exact formulations of the correlation clustering task as Maximum Satisfiability (MaxSAT), the optimization version of the Boolean satisfiability (SAT) problem. For obtaining cost-optimal clusterings, we apply a state-of-the-art MaxSAT solver for solving the resulting MaxSAT instances optimally, resulting in cost-optimal clusterings. We experimentally evaluate the MaxSAT-based approaches to cost-optimal correlation clustering, both on the scalability of our method and the quality of the clusterings obtained. Furthermore, we show how the approach extends to constrained correlation clustering, where additional user knowledge is imposed as constraints on the optimal clusterings of interest We show experimentally that added user knowledge allows clustering larger datasets, and at the same time tends to decrease the running time of our approach. We also investigate the effects of MaxSAT-level preprocessing, symmetry breaking, and the choice of the MaxSAT solver on the efficiency of the approach.
机译：约束解决以及数据挖掘和机器学习领域的集成最近在AI社区中被确定为具有高潜力的重要研究方向。这项工作通过提供对最先进的布尔优化程序在基于通用相似性设置的约束下对成本最优相关性聚类的适用性的首次研究，为该方向做出了贡献。我们开发了相关性聚类任务的精确公式，即最大可满足性（SAT）问题的优化版本，即最大可满足性（MaxSAT）。为了获得成本最优的聚类，我们应用了最新的MaxSAT求解器来最优地求解所得的MaxSAT实例，从而得到成本最优的聚类。我们在方法的可扩展性和所获得聚类的质量上，通过实验评估了基于MaxSAT的成本最优相关聚类方法。此外，我们展示了该方法如何扩展到受约束的相关性聚类，其中，将附加的用户知识作为对感兴趣的最佳聚类的约束。我们的方法。我们还研究了MaxSAT级预处理，对称破坏以及MaxSAT求解器的选择对方法效率的影响。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号