A density-based method for the identification of disjoint and non-disjoint clusters with arbitrary and non-spherical shapes

• Autorzy: Ben Ncir Chiheb-Eddine

Identyfikatory

DOI

doi.org/10.7494/csci.2021.22.2.4002

• Języki publikacji: EN

Abstrakty

EN

The ability of clustering methods to build both disjoint and non-disjoint partitionings of data has become an important issue in unsupervised learning. Although this problem has been studied during the last decades resulting in several proposed overlapping clustering methods in the literature, most of existing methods fail to look for clusters having arbitrary and non-spherical shapes. In addition, most of these existing methods require to pre-configure the number of clusters in prior, which is not a trivial task in real life application of clustering. To solve all these issues, we propose in this work a new density based overlapping clustering method, referred to as OC-DD, which is able to detect both disjoint and non-disjoint partitioning even when boundaries between clusters have complex separations with arbitrary forms and shapes. The proposed method is based on density and distances to detect highly dense regions and connected groups in data without the necessity to pre-configure the number of clusters. Experiments performed on artificial and real multi-labeled datasets have shown the effectiveness of the proposed method compared to the existing ones.

Słowa kluczowe

EN

overlapping clustering; non-disjoint clusters; density-based methods; clusters with non-spherical shapes

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2021
• Tom: T. 22 (2)
• Strony: 169–190
• Opis fizyczny: Bibliogr. 29 poz., rys., tab.

Twórcy

autor

Ben Ncir Chiheb-Eddine

• University of Jeddah, College of Business, Saudi Arabia & University of Tunis,LARODEC Laboratory, Tunisia

Bibliografia

• [1] Afridi M.K., Azam N., Yao J.: Variance based three-way clustering approaches for handling overlapping clustering, International Journal of Approximate Reasoning, vol. 118, pp. 47–63, 2020. doi: 10.1016/j.ijar.2019.11.011.
• [2] Amigó E., Gonzalo J., Artiles J., Verdejo F.: A comparison of extrinsic clustering evaluation metrics based on formal constraints, Information Retrieval, vol. 12(4), pp. 461–486, 2009.
• [3] Ankerst M., Breunig M., Kriegel H.P., Sander J.: OPTICS: ordering points to identify the clustering structure, ACM Sigmod Record, vol. 28(2), pp. 49–60, 1999. doi: 10.1145/304181.304187.
• [4] Banerjee A., Krumpelman C., Ghosh J., Basu S., Mooney R.: Model-based Overlapping Clustering. In: Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, Chicago, USA, pp. 532–537, ACM, 2005.
• [5] Ben N’Cir C.E., Cleuziou G., Essoussi N.: Generalization of c-means for identifying non-disjoint clusters with overlap regulation, Pattern Recognition Letters, vol. 45, pp. 92–98, 2014.
• [6] Ben N’Cir C.E., Essoussi N., Limam M.: Kernel-Based Methods to Identify Overlapping Clusters with Linear and Nonlinear Boundaries, Journal of Classification, vol. 32(2), pp. 176–211, 2015. doi: 10.1007/s00357-015-9181-3.
• [7] Bertrand P., Janowitz M.F.: The k-weak Hierarchical Representations: An Extension of the Indexed Closed Weak Hierarchies, Discrete Applied Mathematics, vol. 127, pp. 199–220, 2003.
• [8] Celleux G., Govaert G.: A classification EM algorithm for clustering and two stochastic versions, Computational Statistics and Data Analysis, pp. 315–332, 1992.
• [9] Cheng Y.: Mean shift, mode seeking, and clustering, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 17(8), pp. 790–799, 1995. doi: 10.1109/34.400568.
• [10] Cleuziou G.: An extended version of the k-means method for overlapping clustering. In: 2008 19th International Conference on Pattern Recognition, pp. 1–4, 2008. doi: 10.1109/ICPR.2008.4761079.
• [11] Cleuziou G., Moreno J.G.: Kernel methods for point symmetry-based clustering, Pattern Recognition, vol. 48(9), pp. 2812–2830, 2015.
• [12] Depril D., Van Mechelen I., Mirkin B.: Algorithms for additive clustering of rectangular data tables, Computational Statistics & Data Analysis, vol. 52(11), pp. 4923–4938, 2008.
• [13] Diday E.: Orders and overlapping clusters by pyramids, 1987. Technical Report 730, INRIA, France. https://hal.inria.fr/inria-00075822.
• [14] Ester X., Kriegel M., Xu X.: Knowledge discovery in large spatial databases: Focusing techniques for efficient class identification. In: Advances in Spatial Databases. SSD 1995, Lecture Notes In Computer Science, vol. 951, pp. 67–82, Springer, Berlin–Heidelberg, 1995.
• [15] Fisher R.A.: The use of multiple measurements in taxonomic problems, Annals of Eugenics, vol. 7(2), pp. 179–188, 1936.
• [16] Fukunaga K., Hostetler L.: The estimation of the gradient of a density function, with applications in pattern recognition, IEEE Transactions on Information Theory, vol. 21(1), pp. 32–40, 1975.
• [17] Hinneburg A., Gabriel H.H.: Denclue 2.0: Fast Clustering Based on Kernel Density Estimation. In: In Proceedings of the 7th International Symposium on Intelligent Data Analysis, pp. 70–80, 2007.
• [18] Hinneburg A., Keim D.: An efficient approach to clustering large multimedia databases with noise. In: KDD’98: Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining, pp. 58–65, 1998.
• [19] Jain A., Dubes R.: Algorithms for Clustering Data, Prentice-Hall, Englewood Cliffs, NJ, 1988.
• [20] Jardine N., Sibson R.: Mathematical Taxonomy, John Wiley and Sons Ltd., London, 1971.
• [21] Khanmohammadi S., Adibeig N., Shanehbandy S.: An improved overlapping k-means clustering method for medical applications, Expert Systems with Applications, vol. 67, pp. 12–18, 2016. doi: 10.1016/j.eswa.2016.09.025.
• [22] Lee S.H., Jeong Y.S., Kim J.Y., Jeong M.K.: A new clustering validity index for arbitrary shape of clusters, Pattern Recognition Letters, vol. 112, pp. 263–269, 2018. doi: 10.1016/j.patrec.2018.08.005.
• [23] Lutov A., Khayati M., Cudr´e-Mauroux P.: Accuracy Evaluation of Overlapping and Multi-Resolution Clustering Algorithms on Large Datasets. In: IEEE International Conference on Big Data and Smart Computing, BigComp 2019, Kyoto, Japan, February 27 – March 2, 2019, pp. 1–8, IEEE, 2019. doi: 10.1109/ BIGCOMP.2019.8679398.
• [24] MacQueen J.B.: Some methods for classification and analysis of multivariate observations. In: Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Statistics, pp. 281–297, 1967.
• [25] Maiza M.I., Ben N’Cir C.E., Essoussi N.: Overlapping Community Detection Method for Social Networks. In: R. Jallouli, O.R. Za¨iane, M.A. Bach Tobji, R. Srarfi Tabbane, A. Nijholt (eds.), Digital Economy. Emerging Technologies and Business Innovation, pp. 143–151, Springer International Publishing, 2017.
• [26] Mirzaie M., Barani A., Nematbakkhsh N., Mohammad-Beigi M.: Bayesian- -OverDBC: A Bayesian Density-Based Approach for Modeling Overlapping Clusters, Mathematical Problems in Engineering, vol. 2015, 2015.
• [27] Sharan R., Shamir R.: CLICK: a clustering algorithm with applications to gene expression analysis. In: Proceedings of International Conference on Intelligent Systems for Molecular Biology, vol. 8, pp. 307–316, 2000.
• [28] Wang M., Zuo W., Wang Y.: An improved density peaks-based clustering method for social circle discovery in social networks, Neurocomputing, vol. 179, pp. 219–227, 2016.
• [29] Zhou X., Liu Y., Wang J., Li C.: A density based link clustering algorithm for overlapping community detection in networks, Physica A: Statistical Mechanics and its Applications, vol. 486, pp. 65–78, 2017.

Uwagi

PL

„Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).”