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

一种基于图着色的集成局部和全局约束的聚类方法

• 批准号: 20500123
• 负责人: YOSHIDA Tetsuya
• 金额: $ 2.83万
• 依托单位: Hokkaido University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2008
• 资助国家: 日本
• 起止时间: 2008 至 2010
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20500123/
• 关键词: グラフ; クラスタリング; 彩色; 制約

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.

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

项目成果

A Graph-Based Projection Approach for Semi-supervised Clustering

• DOI: 10.1007/978-3-642-15037-1_1
• 发表时间: 2010-08
• 作者: Tetsuya Yoshida;Kazuhiro Okatani

Toward finding hidden communities based on user profile

• DOI: 10.1007/s10844-011-0175-2
• 发表时间: 2010-12
• 期刊: Journal of Intelligent Information Systems
• 影响因子: 3.4
• 作者: Tetsuya Yoshida

Message Correlation and Web Service Protocol Mining from Inaccurate Logs

不准确日志中的消息关联和 Web 服务协议挖掘

• 发表时间: 2010
• 作者: Musaraj;K;Yoshida;T.;Daniel;F.;Hacid;M.S.;Casati,F.;Benatallah;B.
• 通讯作者: B.

An Integrated Graph and Probability Based Clustering Framework for Sequential Data

一种基于集成图和概率的序列数据聚类框架

• 发表时间: 2008
• 期刊: Lecture Notes in Artificial Intelligence 5255
• 作者: Elghazel;H.;Yoshida;T.;et.al.
• 通讯作者: et.al.

Neighborhood Graphs for Indexing and Retrieving Multi-dimensional Data

用于索引和检索多维数据的邻域图

• 发表时间: 2009
• 期刊: Journal of Intelligent Information System accepted
• 作者: Hacid;H.;Yoshida;T.
• 通讯作者: T.