苟光磊，黄丽丰，倪 伟

(重庆理工大学 计算机科学与工程学院，重庆 400054)

从聚类的角度来看，先验知识中规定的某一类中的样本点，依照选定的特征空间和相似性测度，应当聚成一类［1］。现实中，常常遇到的情况却是领域专家认为应该归为一类的样本点，往往在特征空间中距离特别远，从而被划分到不同的类;而那些被认为分属不同类的样本点，距离非常近，从而被划分到相同的类。也就是说，聚类结果和先验知识之间往往存在不协调性。

为了降低这种不协调性，有必要利用已知的部分背景知识。Wagstaff 等提出利用问题的背景信息，即数据对象间的正关联限制(must-link)和负关联限制(cannot-link)来指导聚类［2-8］。随着背景知识的增加，聚类的准确性也得以提高。然而，这些聚类方法始终关注在最“细”的粒度层次上的背景知识，即数据对象间的关联限制，并没有将背景知识进行扩展，因此聚类效率较低。

在聚类过程中，随着数据对象加入到不同的类后，粒度层次也随之发生变化，因此希望将原粒度层次上的背景知识进行扩展，在新的粒度层次上指导聚类过程。在粒层转换的过程中，问题的某些性质不变是粒计算理论中的一个重要原理［9］。本文利用这个原理，证明了粒的负关联限制保持性，对概念聚类算法进行了改进，提出了CO-GrC 算法。通过实验证明CO-GrC 算法是有效的，并在时间效率方面相比以往的算法有所提高。

1 聚类的粒度分析

聚类操作与商空间的划分很相似。因此，聚类的粒度分析可从商空间不同粒度划分的角度来讨论［10］。……