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.