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