CAREER: Knowledge Enhanced Clustering Using Constraints

这个项目解决了一般原则性方法的发展，有效地将领域知识表示为聚类算法的约束。这不仅可以提高聚类质量和算法性能，而且还可以找到关于现有领域专业知识的新颖和有用的见解。例如，使用层次聚类构建的系统发育树应该与现有的领域知识一致，例如几个物种不能相互进化。现有的约束下的聚类工作集中在非层次聚类与连接的必须链接和不能链接的约束，断言两个对象必须或不能在同一个集群。这项工作可以被解释为使用有限的逻辑来表达知识，该逻辑由作为对象的实例、两个二元关系（must-link和cannot-link）和一个连接符（and）组成。首先，它将检查一个更完整的逻辑来表示知识，通过添加新的关系，一套完整的连接词（not，and，or，implications），全称和存在量词和新的对象。这种逻辑可以表达各种各样的知识，例如最小/最大聚类分离，聚类宽度，甚至强制某些对象跨聚类的分布。其次，它将研究将非层次聚类算法之外的约束纳入层次凝聚聚类算法，图和社会网络聚类，以及聚类的特征选择。最后，它将探索使用约束的计算挑战，确定容易满足的约束集，并开发一个框架来解释为什么一些约束集比其他约束集更有用。 该项目将展示和验证其在两个核心应用领域的技术贡献：分析流行病微观模拟结果，以帮助备灾和图像挖掘。长期愿景是将知识有效地以原则性的方式纳入其他数据挖掘任务，如分类，异常检测和关联规则。 高中生和本科生的项目推广将以实践发现学习课程的形式进行，重点是两个核心应用领域。对于研究生和研究人员，该项目生成的教程幻灯片，论文，数据集和软件将免费提供。有关该项目的更多信息，请访问网址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.