Abstract
In this paper, we study a new type of competitive learning scheme realized on large-scale networks. The model consists of several agents walking within the network and competing with each other to occupy as many nodes as possible, while attempting to reject intruder agents. In the end of the process, each agent dominates a community (a strongly connected subnetwork). Here, the model is described by a stochastic dynamical system. In this paper, a mathematical analysis for uncovering the system’s properties is presented. In addition, the model is applied to solve handwritten digits and letters clustering problems. An interesting feature is that the model is able to group the same digits or letters even with considerable distortions into the same cluster. Computer simulations reveal that the proposed technique presents high precision of cluster detections, as well as low computational complexity.
Similar content being viewed by others
References
Arenas, A., Diáz-Guilera, A., Pérez-Vicente, C.J.: Synchronization reveals topological scales in complex networks. Phys. Rev. Lett. 96(11), 114102 (2006)
Berkhin, P.: Survey of clustering data mining techniques. Tech. rep, Accrue Software (2002)
Bishop, C.M.: Pattern Recognition and Machine Learning. Information Science and Statistics. Springer, New York (2006)
Çinlar, E.: Introduction to Stochastic Processes. Prentice-Hall, Englewood Cliffs (1975)
Cinque, L., Foresti, G., Lombardi, L.: A clustering fuzzy approach for image segmentation. Pattern Recognit. 37, 1797–1807 (2004)
Danon, L., Díaz-Guilera, A., Duch, J., Arenas, A.: Comparing community structure identification. J. Stat. Mech. P09008 (2005)
Demšar, J.: Statistical comparisons of classifiers over multiple data sets. J. Mach. Learn. Res. 7, 1–30 (2006)
Duda, R.O., Hart, P.E., Stork, D.G.: Unsupervised learning and clustering. In: Pattern Classification, 2nd edn. Wiley-Interscience, New York (2001)
Fortunato, S.: Community detection in graphs. Phys. Rep. 486, 75–174 (2010)
Fortunato, S., Latora, V., Marchiori, M.: Method to find community structures based on information centrality. Phys. Rev. E 70(5), 056104 (2004)
Gan, G.: Data Clustering: Theory, Algorithms, and Applications vol. 20. SIAM, Philadelphia (2007)
Goldhirsch, L., Orszag, S.A., Maulik, B.K.: An efficient method for computing leading eigenvalues and eigenvectors of large asymmetric matrices. J. Sci. Comput. 2, 33–58 (1987)
Govindan, V., Shivaprasad, A.: Character recognition: a review. Pattern Recognit. 23, 671–683 (1990)
Hull, J.J.: A database for handwritten text recognition research. IEEE Trans. Pattern Anal. Mach. Intell. 16, 550–554 (1994)
Husek, D., Pokorny, J., Rezankova, H., Snasel, V.: Data clustering: from documents to the web. In: Web Data Management Practices: Emerging Techniques and Technologies, pp. 1–33. IGI Global, Hershey (2006)
Jain, A.K.: Data clustering: 50 years beyond K-means. Pattern Recognit. Lett. 31, 651–666 (2010)
Jain, A.K., Murty, M.N., Flynn, P.J.: Data clustering: a review. ACM Comput. Surv. 31(3), 264–323 (1999)
Jolliffe, I.T.: In: Principal Component Analysis, 1 edn. Springer Series in Statistics (2002)
Karypis, G., Han, E.H., Kumar, V.: Chameleon: hierarchical clustering using dynamic modeling. IEEE Computer 32(8), 68–75 (1999)
Liu, C.L., Sako, H., Fujisawa, H.: Performance evaluation of pattern classifiers for handwritten character recognition. Int. J. Doc. Anal. Recognit. 4, 191–204 (2002)
Liu, J., Cai, D., He, X.: Gaussian mixture model with local consistency. In: AAAI’10, vol. 1, pp. 512–517 (2010)
MacQueen, J.B.: Some methods for classification and analysis of multivariate observations. In: Proc. of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, vol. 1, pp. 281–297. University of California Press, Berkeley (1967)
Mori, S., Suen, C., Kamamoto, K.: Historical review of ocr research and development. Proc. IEEE 80, 1029–1058 (1992)
Newman, M.: Fast algorithm for detecting community structure in networks. Phys. Rev. E 69(6), 066133 (2004)
Newman, M.: Finding and evaluating community structure in networks. Phys. Rev. E 69(2), 026113 (2004)
Newman, M.: Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E 74(3), 036104 (2006)
Pradeep, J., Srinivasan, E., Himavathi, S.: Diagonal based feature extraction for handwritten alphabets recognition system using neural network. Int. J. Comput. Sci. Inf. Technol. 3, 27–38 (2011)
Quiles, M.G., Zhao, L., Alonso, R.L., Romero, R.A.F.: Particle competition for complex network community detection. Chaos 18(3), 033107 (2008). doi:10.1063/1.2956982
Ratle, F., Weston, J., Miller, M.L.: Large-scale clustering through functional embedding. In: Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases—Part II, ECML PKDD’08, pp. 266–281. Springer, Berlin (2008)
Reichardt, J., Bornholdt, S.: Detecting fuzzy community structures in complex networks with a potts model. Phys. Rev. Lett. 93(21), 218701 (2004)
Shi, J., Malik, J.: Normalized cut and image segmentation. Tech. rep., Berkeley, CA, USA (1997)
Silva, T.C., Zhao, L.: Stochastic competitive learning applied to handwritten digit and letter clustering. In: XXIV SIBGRAPI: Conference on Graphics, Patterns and Images, pp. 313–320 (2011)
Silva, T.C., Zhao, L.: Stochastic competitive learning in complex networks. IEEE Trans. Neural Networks Learn. Syst. 23(3), 385–398 (2012)
Theodoridis, S., Koutroumbas, K.: Pattern Recognition, 4th edn. Academic Press, New York (2008)
Tsai, S.H., Lee, C.Y., Wu, Y.K.: Efficient calculation of critical eigenvalues in large power systems using the real variant of the Jacobi-Davidson qr method. IET Gener. Transm. Distrib. 4, 467–478 (2010)
Zhou, H.: Distance, dissimilarity index, and network community structure. Phys. Rev. E 67(6), 061901 (2003)
Acknowledgements
This work is supported by the São Paulo State Research Foundation (FAPESP) and by the Brazilian National Research Council (CNPq).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
C Silva, T., Zhao, L. & Cupertino, T.H. Handwritten Data Clustering Using Agents Competition in Networks. J Math Imaging Vis 45, 264–276 (2013). https://doi.org/10.1007/s10851-012-0353-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10851-012-0353-z