JACIII Vol.11 No.9 pp. 1136-1143
doi: 10.20965/jaciii.2007.p1136


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

October 2, 2006
August 16, 2007
November 20, 2007
clustering, arbitrarily shaped cluster, one-dimensional data mapping, histogram segmentation, discriminant threshold selection

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.

Cite this article as:
Seiji Hotta, Senya Kiyasu, and Sueharu Miyahara, “Arbitrary-Shaped Cluster Separation Using One-Dimensional Data Mapping and Histogram Segmentation,” J. Adv. Comput. Intell. Intell. Inform., Vol.11, No.9, pp. 1136-1143, 2007.
Data files:
  1. [1] 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.
  2. [2] 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.
  3. [3] 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.
  4. [4] 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.
  5. [5] 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.
  6. [6] 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.
  7. [7] J. Shi and J. Malik, “Normalized Cuts and Image Segmentation,” IEEE trans. on PAMI, Vol.22, No.8, pp. 888-905, 2000.
  8. [8] 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.
  9. [9] A. Ben-Hur, D. Horn, H. T. Siegelmann, and V. Vapnik, “Support Vector Clustering,” J. Machine Learning Research, Vol.2, pp. 125-137, 2001.
  10. [10] M. Girolami, “Mercer Kernel-Based Clustering in Feature Space,” Neural Networks, Vol.13, No.3, pp. 780-784, 2002.
  11. [11] 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.
  12. [12] 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.
  13. [13] 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.
  14. [14] S. T. Roweis and L. K. Saul, “Nonlinear Dimensionality Reduction by Locally Linear Embedding,” Science, Vol.290-5500, pp. 2323-2326, 2000.
  15. [15] 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.
  16. [16] 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.
  17. [17] C. Tomasi and R. Manduchi, “Bilateral Filtering for Gray and Color Images,” Proc. of ICCV, Vol.1, pp. 839-846, 1998.
  18. [18] X. D. Sun and M. S. Kankanhalli, “Video Summarization using Rsequences,” J. Real-Time Imaging, Vol.6, No.6, pp. 449-459, 2000.
  19. [19] H. S. Sawney and J. L. Hafner, “Efficient Color Histogram Indexing,” Proc. of ICIP-94, Vol.2, pp. 66-70, 1994.

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

Last updated on Feb. 25, 2021