Abstract
In data analysis clustering is one of the core processes to find groups in otherwise unstructured data. Determining the number of clusters or finding clusters of arbitrary shape whose convex hulls overlap is in general a hard problem. In this paper we present a method for clustering data points by iteratively shrinking the convex hull of the data set. Subdividing the created hulls leads to shape descriptors of the individual clusters. We tested our algorithm on several data sets and achieved high degrees of accuracy. The cluster definition employed uses a notion of spatial separation. We also compare our algorithm against a similar algorithm that automatically detects the boundaries and the number of clusters. The experiments show that our algorithm yields the better results.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Barber, C.B., Dobkin, D.P., Huhdanpaa, H.: The quickhull algorithm for convex hulls. ACM Trans. Math. Softw. (TOMS) 22(4), 469–483 (1996)
Braune, C., Besecke, S., Kruse, R.: Density based clustering: alternatives to DBSCAN. In: Celebi, E.B. (ed.) Partitional Clustering Algorithms, pp. 193–213. Springer, Heidelberg (2015)
Chan, T.M.: Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete Comput. Geom. 16(4), 361–368 (1996)
Delaunay, B.: Sur la sphere vide. Izv. Akad. Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk, 7(793–800), 1–2 (1934)
Deng, M., Liu, Q., Cheng, T., Shi, Y.: An adaptive spatial clustering algorithm based on Delaunay triangulation. Comput. Environ. Urban Syst. 35(4), 320–332 (2011)
Duckham, M., Kulik, L., Worboys, M., Galton, A.: Efficient generation of simple polygons for characterizing the shape of a set of points in the plane. Pattern Recogn. 41(10), 3224–3236 (2008)
Edelsbrunner, H., Kirkpatrick, D.G., Seidel, R.: On the shape of a set of points in the plane. IEEE Trans. Inf. Theory 29(4), 551–559 (1983)
Estivill-Castro, V., Lee, I.: Autoclust: automatic clustering via boundary extraction for mining massive point-data sets. In: Proceedings of the 5th International Conference on Geocomputation, pp. 23–25 (2000)
Graham, R.L.: An efficient algorithm for determining the convex hull of a finite planar set. Inf. Process. Lett. 1(4), 132–133 (1972)
Höppner, F., Klawonn, F., Kruse, R., Runkler, T.: Fuzzy Cluster Analysis: Methods for Classification, Data Analysis and Image Processing. Wiley, London (1999)
Hubert, L., Arabie, P.: Comparing partitions. J. Classif. 2(1), 193–218 (1985)
Jarvis, R.A.: On the identification of the convex hull of a finite set of points in the plane. Inf. Process. Lett. 2(1), 18–21 (1973)
Klawonn, F., Kruse, R., Winkler, R.: Fuzzy clustering: more than just fuzzification. Fuzzy Sets Syst. 281, 272–279 (2015)
Kruse, R., Borgelt, C., Klawonn, F., Moewes, C., Steinbrecher, M., Held, P.: Computational Intelligence: A Methodological Introduction. Springer Science & Business Media, London (2013)
Liparulo, L., Proietti, A., Panella, M.: Fuzzy clustering using the convex hull as geometrical model. Adv. Fuzzy Syst. 2015 (2015). Article No. 6
Liu, D., Nosovskiy, G.V., Sourina, O.: Effective clustering and boundary detection algorithm based on Delaunay triangulation. Pattern Recogn. Lett. 29(9), 1261–1273 (2008)
Moreira, A., Santos, M.Y.: Concave hull: a k-nearest neighbours approach for the computation of the region occupied by a set of points. In: Proceedings of the International Conference on Computer Graphics Theory and Applications, GRAPP 2007 (2007)
Rosén, E., Jansson, E., Brundin, M.: Implementation of a fast and efficient concave hull algorithm. Technical report, University of Uppsala, Sweden (2014)
Rosenberg, A., Hirschberg, J.: V-measure: a conditional entropy-based external cluster evaluation measure. In: EMNLP-CoNLL, vol. 7, pp. 410–420 (2007)
Yang, X., Cui, W.: A novel spatial clustering algorithm based on Delaunay triangulation. In: International Conference on Earth Observation Data Processing and Analysis, p. 728530. International Society for Optics and Photonics (2008)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing AG
About this paper
Cite this paper
Braune, C., Dankel, M., Kruse, R. (2016). Obtaining Shape Descriptors from a Concave Hull-Based Clustering Algorithm. In: Boström, H., Knobbe, A., Soares, C., Papapetrou, P. (eds) Advances in Intelligent Data Analysis XV. IDA 2016. Lecture Notes in Computer Science(), vol 9897. Springer, Cham. https://doi.org/10.1007/978-3-319-46349-0_6
Download citation
DOI: https://doi.org/10.1007/978-3-319-46349-0_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-46348-3
Online ISBN: 978-3-319-46349-0
eBook Packages: Computer ScienceComputer Science (R0)