Toward Improving Re-coloring Based Clustering with Graph b-Coloring
| Autor: | Hiroki Ogino, Tetsuya Yoshida |
|---|---|
| Rok vydání: | 2010 |
| Předmět: |
Greedy coloring
B-coloring Mathematical optimization Theoretical computer science Search algorithm Correlation clustering ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION Canopy clustering algorithm Graph (abstract data type) Best-first search Cluster analysis ComputingMethodologies_COMPUTERGRAPHICS Mathematics |
| Zdroj: | PRICAI 2010: Trends in Artificial Intelligence ISBN: 9783642152450 PRICAI |
| DOI: | 10.1007/978-3-642-15246-7_21 |
| Popis: | This paper proposes an approach toward improving re-coloring based clustering with graph b-coloring. Previous b-coloring based clustering algorithm did not consider the quality of clusters. Although a greedy re-coloring algorithm was proposed, it was still restrictive in terms of the explored search space due to its greedy and sequential re-coloring process. We aim at overcoming the limitations by enlarging the search space for re-coloring, while guaranteeing b-coloring properties. A best first re-coloring algorithm is proposed to realize nongreedy search for the admissible colors of vertices. A color exchange algorithm is proposed to remedy the problem in sequential re-coloring. These algorithms are orthogonal with respect to the re-colored vertices and thus can be utilized in conjunction. Preliminary evaluations are conducted over several benchmark datasets, and the results are encouraging. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|