JACIII Vol.11 No.6 pp. 554-560
doi: 10.20965/jaciii.2007.p0554


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

December 2, 2006
March 19, 2007
July 20, 2007
unsupervised clustering, semi-supervised clustering, graph-spectral algorithm, fuzzy clustering, image retrieval

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:
Weiwei Du and Kiichi 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:
  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.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Mar. 05, 2021