Abstract
Frequent approximate subgraph (FAS) mining and graph clustering are important techniques in Data Mining with great practical relevance. In FAS mining, some approximations in data are allowed for identifying graph patterns, which could be used for solving other pattern recognition tasks like supervised classification and clustering. In this paper, we explore the use of the patterns identified by a FAS mining algorithm on a graph collection for image clustering. Some experiments are performed on image databases for showing that by using the FASs mined from a graph collection under the bag of features image approach, it is possible to improve the clustering results reported by other state-of-the-art methods.
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
Flores-Garrido, M., Carrasco-Ochoa, J.A., Martínez-Trinidad, J.F.: Graph clustering via inexact patterns. In: Bayro-Corrochano, E., Hancock, E. (eds.) CIARP 2014. LNCS, vol. 8827, pp. 391–398. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-12568-8_48
Morales-González, A., Acosta-Mendoza, N., Gago-Alonso, A., García-Reyes, E., Medina-Pagola, J.: A new proposal for graph-based image classification using frequent approximate subgraphs. Pattern Recogn. 47(1), 169–177 (2014)
Herrera-Semenets, V., Acosta-Mendoza, N., Gago-Alonso, A.: A Framework for intrusion detection based on frequent subgraph mining. In: The 2nd SDM Workshop on Mining Networks and Graphs: A Big Data Analytic Challenge (SDM-Networks 2015), Vancouver, BC, Canada (2015)
Bai, L., Cheng, X., Liang, J., Guo, Y.: Fast graph clustering with a new description model for community detection. Inf. Sci. 388–389, 37–47 (2017)
Yan, Y., Liu, G., Wang, S., Zhang, J., Zheng, K.: Graph-based clustering and ranking for diversified image search. Multimed. Syst. 23, 41–52 (2017)
Viet-Vu, V., Hong-Quan, D.: Graph-based clustering with background knowledge. In: Proceedings of the Eighth International Symposium on Information and Communication Technology, SoICT 2017, pp. 167–172. ACM, New York (2017)
Ye, W., Zhou, L., Sun, X., Plant, C., Böhm, C.: Attributed graph clustering with unimodal normalized cut. In: Ceci, M., Hollmén, J., Todorovski, L., Vens, C., Džeroski, S. (eds.) ECML PKDD 2017. LNCS (LNAI), vol. 10534, pp. 601–616. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-71249-9_36
Rao, B., Mishra, B.: An approach to clustering of text documents using graph mining techniques. Int. J. Rough Sets Data Anal. (IJRSDA) 4(1), 18 (2017)
Jia, Y., Zhang, J., Huan, J.: An efficient graph-mining method for complicated and noisy data with real-world applications. Knowl. Inf. Syst. 28(2), 423–447 (2011)
Flores-Garrido, M., Carrasco-Ochoa, J., Martínez-Trinidad, J.: AGraP: an algorithm for mining frequent patterns in a single graph using inexact matching. Knowl. Inf. Syst. 42(2), 1–22 (2015)
Chen, C., Yan, X., Zhu, F., Han, J.: gApprox: mining frequent approximate patterns from a massive network. In: International Conference on Data Mining (ICDM 2007), pp. 445–450 (2007)
González, J., Holder, L., Cook, D.: Graph-based concept learning. In: Proceedings of the Fourteenth International Florida Artificial Intelligence Research Society Conference, pp. 377–381. AAAI Press, Key West (2001)
Acosta-Mendoza, N., Gago-Alonso, A., Medina-Pagola, J.: Frequent approximate subgraphs as features for graph-based image classification. Knowl. Based Syst. 27, 381–392 (2012)
Emmert-Streib, F., Dehmer, M., Shi, Y.: Fifty years of graph matching, network alignment and network comparison. Inf. Sci. 346, 1–22 (2016)
Gutierrez-Rodríguez, A., Martínez-Trinidad, J.F., García-Borroto, M., Carrasco-Ochoa, J.: Mining patterns for clustering on numerical datasets using unsupervised decision trees. Knowl. Based Syst. 82, 70–79 (2015)
Gutierrez-Rodríguez, A., Martínez-Trinidad, J.F., García-Borroto, M., Carrasco-Ochoa, J.: Mining patterns for clustering using unsupervised decision trees. Intell. Data Anal. 19(6), 1297–1310 (2015)
Flores-Garrido, M., Carrasco-Ochoa, J., Martínez-Trinidad, J.: Mining maximal frequent patterns in a single graph using inexact matching. Knowl. Based Syst. 66, 166–177 (2014)
Ambauen, R., Fischer, S., Bunke, H.: Graph edit distance with node splitting and merging, and its application to diatom identification. In: Hancock, E., Vento, M. (eds.) GbRPR 2003. LNCS, vol. 2726, pp. 95–106. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-45028-9_9
Neuhaus, M., Bunke, H.: A probabilistic approach to learning costs for graph edit distance. In: Kittler, J., Petrou, M., Nixon, M. (eds.) Proceedings 17th International Conference on Pattern Recognition, Cambridge, United Kingdom, vol. 3, pp. 389–393 (2004)
Neuhaus, M., Bunke, H.: Automatic learning of cost functions for graph edit distance. Inf. Sci. 177(1), 239–247 (2007)
Kuramochi, M., Karypis, G.: An efficient algorithm for discovering frequent subgraphs. Technical report, IEEE Transactions on Knowledge and Data Engineering (2002)
Gago-Alonso, A., Puentes-Luberta, A., Carrasco-Ochoa, J., Medina-Pagola, J., Martínez-Trinidad, J.: A new algorithm for mining frequent connected subgraphs based on adjacency matrices. Intell. Data Anal. 14, 385–403 (2010)
O’Hara, S., Draper, B.: Introduction to the bag of features paradigm for image classification and retrieval. Computing Research Repository (CoRR) abs/1101.3354 (2011)
Acosta-Mendoza, N.: Clasificación de imágenes basada en subconjunto de subgrafos frecuentes aproximados. Master’s thesis, The National Institute of Astrophysics, Optics and Electronics of Mexico (INAOE), July 2013
Pinilla-Buitrago, L.A., Martínez-Trinidad, J.F., Carrasco-Ochoa, J.A.: New penalty scheme for optimal subsequence bijection. In: Ruiz-Shulcloper, J., Sanniti di Baja, G. (eds.) CIARP 2013. LNCS, vol. 8258, pp. 206–213. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-41822-8_26
Rand, M.: Objective criteria for the evaluation of clustering methods. J. Am. Stat. Assoc. 66(336), 846–850 (1971)
McQueen, J.: 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. University of California Press (1967)
Arthur, D., Vassilvitskii, S.: K-means: the advantages of carefull seeding. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1027–1035. ACM (2007)
Lazebnik, S., Schmid, C., Ponce, J.: Beyond bags of features: spatial pyramid matching for recognizing natural scene categories. In: IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), pp. 1–8. IEEE (2006)
Acknowledgment
This work was partly supported by the National Council of Science and Technology of Mexico (CONACyT) through the scholarship grant 287045.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Acosta-Mendoza, N., Carrasco-Ochoa, J.A., Martínez-Trinidad, J.F., Gago-Alonso, A., Medina-Pagola, J.E. (2018). Image Clustering Based on Frequent Approximate Subgraph Mining. In: Martínez-Trinidad, J., Carrasco-Ochoa, J., Olvera-López, J., Sarkar, S. (eds) Pattern Recognition. MCPR 2018. Lecture Notes in Computer Science(), vol 10880. Springer, Cham. https://doi.org/10.1007/978-3-319-92198-3_19
Download citation
DOI: https://doi.org/10.1007/978-3-319-92198-3_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-92197-6
Online ISBN: 978-3-319-92198-3
eBook Packages: Computer ScienceComputer Science (R0)