CAREER: Knowledge Enhanced Clustering Using Constraints

该项目致力于开发通用的原则性方法，以有效地将以约束形式表示的领域知识包含到集群算法中。这不仅可以改进集群质量和算法性能，还可以找到与现有领域专业知识相关的新颖和有用的见解。例如，使用等级聚类构建的系统发育树应该与现有的领域知识一致，例如几个物种不可能从另一个物种进化而来。现有的基于约束的聚类工作主要集中在非层次化的聚类上，这些聚类结合了必须链接和不能链接的约束，这些约束断言两个对象必须或不能在同一群集中。这项工作可以被解释为使用有限的逻辑来表示知识，该逻辑由实例作为对象、两个二元关系(必须链接和不能链接)和单个连接符(AND)组成。首先，它将通过添加新的关系、一组完整的连接词(非、与、或、蕴涵)、通用量词和存在量词以及新的对象来检验表示知识的更完整的逻辑。该逻辑可以表达各种知识，例如最小/最大集群间隔、集群宽度，甚至强制某些对象跨集群分布。其次，它将研究将非层级聚类算法之外的约束融入到层级聚集聚类、图和社会网络聚类以及用于聚类的特征选择算法中。最后，它将通过识别容易满足的约束集并开发一个框架来解释为什么某些约束集比其他约束集更有用，从而探索使用约束的计算挑战。该项目将在两个核心应用领域展示和验证其技术贡献：分析流行病微观模拟结果，以协助备灾和图像挖掘。长期的愿景是以有原则的方式将知识有效地整合到其他数据挖掘任务中，如分类、异常检测和关联规则。针对高中生和本科生的项目推广将以实践探索学习课程的形式进行，重点放在两个核心应用领域。对于研究生和研究人员来说，该项目生成的教程幻灯片、论文、数据集和软件将免费提供。有关该项目的更多信息，请访问URL http://www.constrained-clustering.org和http://www.cs.albany.edu/~davidson.

This project addresses the development of general principled methodsto efficiently include domain knowledge expressed as constraints into clustering algorithms. This not only allows improved clustering quality and algorithm performance but also finding insights that are novel and useful with respect to existing domain expertise. For example, phylogenetic trees built using hierarchical clustering should be consistent with existing domain knowledge such as that several species could not have evolved from one another. Existing clustering under constraints work has focused on non-hierarchical clustering with conjunctions of must-link and cannot-link constraints that assert that two objects must or must not be in the same cluster. This work can be interpreted as expressing knowledge using a limited logic comprised of instances as objects, two binary relations (must-link and cannot-link) and a single connector (and).This project will make three primary contributions. Firstly, it will examine a more complete logic to represent knowledge by adding in new relations, a complete set of connectives (not, and, or, implication), universal and existential quantifiers and new objects. This logic can express a large variety of knowledge such as minimum/maximum cluster separation, cluster width and even forcing distributions of certain objects across clusters. Secondly, it will investigate incorporating constraints beyond non-hierarchical clustering algorithms into algorithms for hierarchical agglomerative clustering, graph and social network clustering, and feature selection for clustering. Lastly, it will explore the computational challenges of using constraints by identifying easy to satisfy sets of constraints and developing a framework to explain why some constraint sets are more useful than others. This project will demonstrate and validate its technical contributions on two core application domains: analysis of pandemic micro-simulations results to aid in disaster preparation and image mining. The long term vision is to incorporate knowledge efficiently in a principled manner into other data mining tasks such as classification, anomaly detection and association rules. Project outreach for high school and undergraduates students will be in the form of hands-on discovery learning courses with emphasis on the two core application domains. For graduate students and researchers the tutorial slides, papers, datasets and software generated from the project will be freely available. Further information on this project may be found at the URLs http://www.constrained-clustering.org and http://www.cs.albany.edu/~davidson.