Unsupervised and Semi-Supervised Graph-Spectral Algorithms for Robust Extraction of Arbitrarily Shaped Fuzzy Clusters

Weiwei Du; Kiichi Urahama

doi:10.20965/jaciii.2007.p0554

single-jc.php

« previous

JACIII Vol.11 No.6 pp. 554-560

doi: 10.20965/jaciii.2007.p0554

(2007)

Paper:

Views over last 60 days: 403

Unsupervised and Semi-Supervised Graph-Spectral Algorithms for Robust Extraction of Arbitrarily Shaped Fuzzy Clusters

Weiwei Du and Kiichi Urahama

Department of Visual Communication Design, Kyushu University, 4-9-1 Shiobaru, Fukuoka 815-8540, Japan

Received:

December 2, 2006

Accepted:

March 19, 2007

Published:

July 20, 2007

Keywords:

unsupervised clustering, semi-supervised clustering, graph-spectral algorithm, fuzzy clustering, image retrieval

Abstract

We present unsupervised and semi-supervised algorithms for extracting fuzzy clusters in weighted undirected regular, undirected bipartite, and directed graphs. We derive the semi-supervised algorithms from the Lagrangian function in unsupervised methods for extracting dominant clusters in a graph. These algorithms are robust against noisy data and extract arbitrarily shaped clusters. We demonstrate applications for similarity searches of data such as image retrieval in face images represented by undirected graphs, quantized color images represented by undirected bipartite graphs, and Web page links represented by directed graphs.

Cite this article as:

W. Du and K. Urahama, “Unsupervised and Semi-Supervised Graph-Spectral Algorithms for Robust Extraction of Arbitrarily Shaped Fuzzy Clusters,” J. Adv. Comput. Intell. Intell. Inform., Vol.11 No.6, pp. 554-560, 2007.

Data files:

References

[1] M. I. Ng, N. I. Jordan, and Y. Weiss, “On spectral clustering: analysis and an algorithm,” NIPS, pp. 849-856, 2002.
[2] Z. Zhu, Z. Ghahrmani, and J. D. Lafferty, “Semi-supervised learning using Gaussian fields and harmonic functions,” ICML, pp. 912-919, 2003.
[3] D. Zhou, B. Scholkopf, and T. Hofmann, “Semi-supervised learning on directed graphs,” NIPS, pp. 1633-1640, 2005.
[4] W. Pedrycz, “Knowledge-based clustering: from data to information granules,” Wiley, 2005.
[5] K. Wagstaff, C. Cardie, S. Rogers, and S. Shroedl, “Constrained k -means clustering with background knowledge,” ICML, pp. 577-584, 2001.
[6] B. Kulis, S. Basu, I. Dhillon, and R. Mooney, “Semi-supervised graph clustering: a kernel approach,” ICML, pp. 457-464, 2005.
[7] S. Hotta, K. Inoue, and K. Urahama, “Extraction of fuzzy clusters from weighted graphs,” PACDD, pp. 442-453, 2000.
[8] K. Inoue and K. Urahama, “Sequential fuzzy cluster extraction by a graph spectral method,” Patt. Recog. Lett., 20, pp. 699-705, 1999.
[9] J. C. Bezdek, “Pattern recognition with fuzzy objective function algorithms,” Plenum Pub Corp, 1981.
[10] J. He, M. Li, H. Zhang, H. Tong, and C. Zhang, “Manifold-ranking based image retrieval,” ACM MM, pp. 9-16, 2004.
[11] J. M. Kleinberg, “Authritative sources in hyperlinked environment,” J. ACM, Vol.46, pp. 604-632, 1999.
[12] M. Swain and D. Ballard, “Colour indexing,” Int. J. Comput. Vision, 7, pp. 11-32, 1991.

This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

[1] [1] M. I. Ng, N. I. Jordan, and Y. Weiss, “On spectral clustering: analysis and an algorithm,” NIPS, pp. 849-856, 2002.

[2] [2] Z. Zhu, Z. Ghahrmani, and J. D. Lafferty, “Semi-supervised learning using Gaussian fields and harmonic functions,” ICML, pp. 912-919, 2003.

[3] [3] D. Zhou, B. Scholkopf, and T. Hofmann, “Semi-supervised learning on directed graphs,” NIPS, pp. 1633-1640, 2005.

[4] [4] W. Pedrycz, “Knowledge-based clustering: from data to information granules,” Wiley, 2005.

[5] [5] K. Wagstaff, C. Cardie, S. Rogers, and S. Shroedl, “Constrained k -means clustering with background knowledge,” ICML, pp. 577-584, 2001.

[6] [6] B. Kulis, S. Basu, I. Dhillon, and R. Mooney, “Semi-supervised graph clustering: a kernel approach,” ICML, pp. 457-464, 2005.

[7] [7] S. Hotta, K. Inoue, and K. Urahama, “Extraction of fuzzy clusters from weighted graphs,” PACDD, pp. 442-453, 2000.

[8] [8] K. Inoue and K. Urahama, “Sequential fuzzy cluster extraction by a graph spectral method,” Patt. Recog. Lett., 20, pp. 699-705, 1999.

[9] [9] J. C. Bezdek, “Pattern recognition with fuzzy objective function algorithms,” Plenum Pub Corp, 1981.

[10] [10] J. He, M. Li, H. Zhang, H. Tong, and C. Zhang, “Manifold-ranking based image retrieval,” ACM MM, pp. 9-16, 2004.

[11] [11] J. M. Kleinberg, “Authritative sources in hyperlinked environment,” J. ACM, Vol.46, pp. 604-632, 1999.

[12] [12] M. Swain and D. Ballard, “Colour indexing,” Int. J. Comput. Vision, 7, pp. 11-32, 1991.