A Clustering Method based on graph Coloring for integrating Local and Global Constraints

在图论中，我们提出了一种基于图的b-染色的聚类方法。这种着色要求在给图着色时应满足两种约束。通过将一种约束作为局部约束，另一种作为全局约束，我们提出了一种统一反映两种约束的聚类方法。对于给定的数据集，我们定义了一种基于成对相异度的图结构，这样数据集的着色就可以在图上进行。所开发的算法对图进行着色，以进行数据集的聚类。该算法已作为原型系统实现，并在多个数据集上进行了实验。实验结果表明了所提出的聚类算法的有效性。

We have developed a clustering method based on b-coloring of a graph in Graph Theory. This coloring requires that two kinds of constraints should be satisfied in the coloring of a graph. By regarding one kind of constraint as a local constraint and the other as a global constraint, we have developed a clustering method which reflects both constraints in a unified manner. For a given dataset, we define a graph structure based on the pairwise dissimilarities so that the coloring of the dataset can be conducted over the graph. The developed algorithm conducts the coloring of the graph for conducting the clustering of the dataset. The algorithm has been implemented as a prototype system, and experiments using the prototype system were conducted over several datasets. The results of the experiments indicate the effectiveness of the developed clustering algorithm.