We consider mean-field models for data–clustering problems starting from a generalization of the bounded confidence model for opinion dynamics. The microscopic model includes information on the position as well as on additional features of the particles in order to develop specific clustering effects. The corresponding mean–field limit is derived and properties of the model are investigated analytically. In particular, the mean–field formulation allows the use of a random subsets algorithm for efficient computations of the clusters. Applications to shape detection and image segmentation on standard test images are presented and discussed.
Citation: Michael Herty, Lorenzo Pareschi, Giuseppe Visconti. Mean field models for large data–clustering problems[J]. Networks and Heterogeneous Media, 2020, 15(3): 463-487. doi: 10.3934/nhm.2020027
We consider mean-field models for data–clustering problems starting from a generalization of the bounded confidence model for opinion dynamics. The microscopic model includes information on the position as well as on additional features of the particles in order to develop specific clustering effects. The corresponding mean–field limit is derived and properties of the model are investigated analytically. In particular, the mean–field formulation allows the use of a random subsets algorithm for efficient computations of the clusters. Applications to shape detection and image segmentation on standard test images are presented and discussed.
| [1] |
G. Albi, N. Bellomo, L. Fermo, S.-Y. Ha and J. Kim, et al., Vehicular traffic, crowds, and swarms.: From kinetic theory and multiscale methods to applications and research perspectives, Math. Models Methods Appl. Sci., 29 (2019), 1901-2005. |
| [2] |
Binary interaction algorithms for the simulation of flocking and swarming dynamics. Multiscale Model. Simul. (2013) 11: 1-29. 
|
| [3] |
Modeling of self-organized systems interacting with a few individuals: From microscopic to macroscopic dynamics. Appl. Math. Lett. (2013) 26: 397-401.
|
| [4] |
G. Albi, L. Pareschi, G. Toscani and M. Zanella, Recent advances in opinion modeling: Control and social influence, in Active Particles, Vol. 1, Model. Simul. Sci. Eng. Technol., Birkhäuser/Springer, Cham, 2017, 49–98. |
| [5] |
Opinion dynamics over complex networks: Kinetic modeling and numerical methods. Kinet. Relat. Models (2017) 10: 1-32.
|
| [6] |
Contour detection and hierarchical image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. (2011) 33: 898-916.
|
| [7] |
On Krauses's multi-agent consensus model with state-dependent connectivity. IEEE Trans. Automat. Control (2009) 54: 2586-2597.
|
| [8] |
Continuous time average-preserving opinion dynamics with opinion-dependent communications. SIAM J. Control Optim. (2010) 48: 5214-5240.
|
| [9] |
Asymptotic analysis of continuous opinion dynamics models under bounded confidence. Commun. Pure Appl. Anal. (2013) 12: 1487-1499.
|
| [10] |
L. Boudin, R. Monaco and F. Salvarani, Kinetic model for multidimensional opinion formation, Phys. Rev. E, 81 (2010), 9pp. |
| [11] |
Opinion dynamics: Kinetic modelling with mass media, application to the Scottish independence referendum. Phys. A (2016) 444: 448-457.
|
| [12] |
A well-posedness theory in measures for some kinetic models of collective motion. Math. Models Methods Appl. Sci. (2011) 21: 519-539.
|
| [13] |
An Eulerian approach to the analysis of rendez-vous algorithms. IFAC Proceedings Volumes (2008) 41: 9039-9044.
|
| [14] |
C. Canuto, F. Fagnani and P. Tilli, An Eulerian approach to the analysis of Krause's consensus models, SIAM J. Control Optim., 50 (2012), 243–265. |
| [15] |
An analytical framework for consensus-based global optimization method. Math. Models Methods Appl. Sci. (2018) 28: 1037-1066.
|
| [16] |
J. A. Carrillo, M. Fornasier, G. Toscani and F. Vecil, Particle, kinetic, and hydrodynamic models of swarming, in Mathematical Modeling of Collective Behavior in Socio-Economic and Life Sciences, Model. Simul. Sci. Eng. Technol., Birkhäuser Boston, Boston, MA, 2010, 297–336. |
| [17] |
DeepLab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected CRFs. IEEE Trans. Pattern Anal. Machine Intelligence (2018) 40: 834-848.
|
| [18] |
Effective leadership and decision-making in animal groups on the move. Nature (2005) 433: 513-516.
|
| [19] |
Emergent behavior in flocks. IEEE Trans. Automat. Control (2007) 52: 852-862.
|
| [20] |
A macroscopic model for a system of swarming agents using curvature control. J. Stat. Phys. (2011) 143: 685-714.
|
| [21] |
F. Dietrich, S. Martin and M. Jungers, Transient cluster formation in generalized Hegselmann-Krause opinion dynamics, 2016 European Control Conference (ECC), Aalborg, Denmark, 2016. |
| [22] |
Consensus formation under bounded confidence. Nonlinear Anal. (2001) 47: 4615-4622.
|
| [23] |
Boltzmann and Fokker-Planck equations modelling opinion formation in the presence of strong leaders. Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci. (2009) 465: 3687-3708.
|
| [24] |
S. Gould, R. Fulton and D. Koller, Decomposing a scene into geometric and semantically consistent regions, 2009 IEEE 12th International Conference on Computer Vision, Kyoto, Japan, 2009. |
| [25] |
R. Hegselmann and U. Krause, Opinion dynamics and bounded confidence: Models, analysis and simulation, J. Artifical Societies Social Simulation, 5 (2002). |
| [26] |
J. M. Hendrickx, Graphs and Networks for the Analysis of Autonomous Agent Systems, Ph.D thesis, Ecole Polytechnique de Louvain, 2008. |
| [27] |
Clustering and asymptotic behavior in opinion formation. J. Differential Equations (2014) 257: 4165-4187.
|
| [28] |
J. Kennedy and R. Eberhart, Particle swarm optimization, Proc. Internat. Conference Neural Networks, Perth, Australia, 1995. |
| [29] |
Color image segmentation based on modified Kuramoto model. Procedia Comp. Sci. (2016) 88: 245-258.
|
| [30] |
A stabilization theorem for dynamics of continuous opinions. Phys. A (2005) 355: 217-223.
|
| [31] |
J. MacQueen, Some methods for classification and analysis of multivariate observations, Proc. Fifth Berkeley Sympos. Math. Statist. and Probability, Vol. Ⅰ: Statistics, Univ. California Press, Berkeley, CA, 1967, 281-297. |
| [32] |
D. Martin, C. Fowlkes, D. Tal and J. Malik, A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics, Proc. Eighth IEEE Internat. Conference Comp. Vision, Vancouver, Canada, 2001. |
| [33] |
Kernel possibilistic fuzzy $c$-means clustering with local information for image segmentation. Internat. J. Fuzzy Syst. (2019) 21: 321-332.
|
| [34] |
A new model for self-organized dynamics and its flocking behavior. J. Stat. Phys. (2011) 144: 923-947.
|
| [35] |
Heterophilious dynamics enhances consensus. SIAM Review (2014) 56: 577-621.
|
| [36] |
A. Nedić and B. Touri, Multi-dimensional Hegselmann-Krause dynamics, 2012 IEEE 51st IEEE Conference on Decision and Control (CDC), Maui, HI, 2012. |
| [37] |
Oscillatory neural networks based on the Kuramoto model for cluster analysis. Pattern Recognition Image Anal. (2014) 24: 365-371.
|
| [38] |
G. Oliva, D. La Manna, A. Fagiolini and R. Setola, Distributed data clustering via opinion dynamics, Internat. J. Distributed Sensor Networks, 11 (2015). |
| [39] |
Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations. J. Comput. Phys. (1988) 79: 12-49.
|
| [40] |
L. Pareschi and G. Toscani, Interacting Multiagent Systems. Kinetic Equations and Monte Carlo Methods, Oxford University Press, 2013. |
| [41] |
A consensus-based model for global optimization and its mean-field limit. Math. Models Methods Appl. Sci. (2017) 27: 183-204.
|
| [42] |
Kinetic models for traffic flow resulting in a reduced space of microscopic velocities. Kinet. Relat. Models (2017) 10: 823-854.
|
| [43] |
J. A. Sethian, Level Set Methods and Fast Marching Methods. Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science, Cambridge Monographs on Applied and Computational Mathematics, 3, Cambridge University Press, Cambridge, 1999. |
| [44] |
P. Shan, Image segmentation method based on K-mean algorithm, EURASIP J. Image Video Processing, 81 (2018). |
| [45] |
Research on image segmentation based on clustering algorithm. Internat. J. Signal Process. Image Process. Pattern Recognition (2016) 9: 1-12.
|
| [46] |
Representative discovery of structure cues for weakly-supervised image segmentation. IEEE Transac. Multimedia (2014) 16: 470-479.
|
| [47] |
X. Zheng, Q. Lei, R. Yao, Y. Gong and Q. Yin, Image segmentation based on adaptive $K$-means algorithm, EURASIP J. Image Video Processing, 68 (2018). |
Figures(15) / Tables(2)
Michael Herty, Lorenzo Pareschi, Giuseppe Visconti. Mean field models for large data–clustering problems[J]. Networks and Heterogeneous Media, 2020, 15(3): 463-487. doi: 10.3934/nhm.2020027
Trend to the steady–state of the one–dimensional Hegselmann–Krause model (1) with
Evolution in time of the first moment (left) and of the second moment (right) for the two values of the bounded confidence level
Left: trend to the steady–state of the mean–field model (12) computed with Algorithm 1 with
Particle solution (left plots) with
Evolution in time of the two–dimensional first moments (left) and second moments (right) for the bounded confidence level
Top row: particles and kinetic density at initial time (left plot) and at equilibrium (right plot). Bottom row: at left, analysis of the distances between clusters in
Particle and kinetic density at equilibrium with confidence levels
Shape detection of the letter "A" initialized with
Shape detection of the letter "A" initialized with
Left panel: initial image of
Image segmentation of
Image segmentation of
Image segmentation of
Image segmentation of
Image segmentation of
DownLoad: