Arbitrary-Shaped Cluster Separation Using One-Dimensional Data Mapping and Histogram Segmentation
Seiji Hotta*, Senya Kiyasu**, and Sueharu Miyahara**
*Tokyo University of Agriculture and Technology, 2-24-16 Naka-cho, Koganei, Tokyo 184-8588, Japan
**Department of Computer and Information Sciences, Nagasaki University, 1-14 Bunkyo-machi, Nagasaki-shi, Nagasaki 852-8521, Japan
Of the many clustering methods proposed for separating arbitrarily shaped clusters, most had drawbacks in parameter sensitivity and high-computational cost requiring large amounts of memory. We propose one-dimensional (1D) mapping for separating arbitrarily shaped clusters using a list of neighbors. After mapping, we apply a discriminant threshold selection to the histogram of the data distribution in 1D space. We verified the feasibility of performance in experiments on synthetic toy data, image, and video segmentation.
-  A. K. Jain, A. Topchy, M. H. C. Law, and J. M. Buhmann, “Landscape of Clustering Algorithms,” Proc. of ICPR2004, Vol.1, pp. 260-263, 2004.
-  R. A. Jarvis and E. A. Patrick, “Clustering Using a Similarity Measure Based on Shared Near Neighbors,” IEEE trans. on Comp., Vol.C-22, No.11, pp. 1025-1034, 1973.
-  K. C. Gowda and G. Krishna, “Agglomerative Clustering Using the Concept of Mutual Nearest Neighbourhood,” Patt. Recog., Vol.10, No.2, pp. 105-112, 1978.
-  J. C. Gower and G. J. S. Ross, “Minimum Spanning Trees and Single Linkage Cluster Analysis,” Appl. Stats., Vol.18, No.1, pp. 54-64, 1969.
-  K. Fukunaga and L. D. Hostetler, “The Estimation of the Gradient of a Density Function, with Applications in Pattern Recognition,” IEEE Trans. on Information Theory, Vol.21, pp. 32-40, 1975.
-  D. Comaniciu and P. Meer, “Mean Shift: A Robust Approach Toward Feature Space Analysis,” IEEE trans. on PAMI, Vol.24, No.5, pp. 603-619, 2002.
-  J. Shi and J. Malik, “Normalized Cuts and Image Segmentation,” IEEE trans. on PAMI, Vol.22, No.8, pp. 888-905, 2000.
-  A. Y. Ng, M. I. Jordan, and Y. Weiss, “On Spectral Clustering: Analysis and an Algorithm,” Proc. of NIPS, Vol.14, pp. 849-856, 2002.
-  A. Ben-Hur, D. Horn, H. T. Siegelmann, and V. Vapnik, “Support Vector Clustering,” J. Machine Learning Research, Vol.2, pp. 125-137, 2001.
-  M. Girolami, “Mercer Kernel-Based Clustering in Feature Space,” Neural Networks, Vol.13, No.3, pp. 780-784, 2002.
-  B. Fischer and J. M. Buhmann, “Path-Based Clustering for Grouping of Smooth Curves and Texture Segmentation,” IEEE trans. on PAMI, Vol.25, No.4, pp. 513-518, 2003.
-  I. Dhillon, Y. Guan, and B. Kulis, “Kernel k-means, Spectral Clustering, and Normalized Cuts,” Proc. 10th ACM SIGKDD Int’l. Conf. on Knowledge Discovery and Data Mining, pp. 551-556, 2004.
-  M. Terashima, F. Shiratani, and K. Yamamoto, “Unsupervised Cluster Segmentation Method Using Data Density Histogram on Self-Organizing Feature Map,” IEICE Trans. Inf. & Syst. (Japanese Edition), Vol.J79-D-II, No.7, pp. 1280-1290, 1996.
-  S. T. Roweis and L. K. Saul, “Nonlinear Dimensionality Reduction by Locally Linear Embedding,” Science, Vol.290-5500, pp. 2323-2326, 2000.
-  B. Schölkopf, A. J. Smola, and K.-R. Müller, “Nonlinear Component Analysis as a Kernel Eigenvalue Problem,” Neural Computation, Vol.10, pp. 1299-1319, 1998.
-  N. Otsu, “A Threshold Selection Method from Gray-Level Histograms,” IEEE Trans. on System, Man, and Cybernetics, Vol.SMC-9, No.1, pp. 62-66, 1979.
-  C. Tomasi and R. Manduchi, “Bilateral Filtering for Gray and Color Images,” Proc. of ICCV, Vol.1, pp. 839-846, 1998.
-  X. D. Sun and M. S. Kankanhalli, “Video Summarization using Rsequences,” J. Real-Time Imaging, Vol.6, No.6, pp. 449-459, 2000.
-  H. S. Sawney and J. L. Hafner, “Efficient Color Histogram Indexing,” Proc. of ICIP-94, Vol.2, pp. 66-70, 1994.