Mean field models for large data–clustering problems

Michael Herty; Lorenzo Pareschi; Giuseppe Visconti

doi:10.3934/nhm.2020027

Article Contents

2020, Volume 15, Issue 3: 463-487. Doi: 10.3934/nhm.2020027

This issue Previous Article Nonlinear stability of stationary solutions to the Kuramoto-Sakaguchi equation with frustration Next Article Bounded confidence dynamics and graph control: Enforcing consensus

Mean field models for large data–clustering problems

1.
RWTH Aachen University, Institut für Geometrie und Praktische Mathematik, Templergraben 55, 52062 Aachen, Germany
2.
University of Ferrara, Mathematics and Computer Science Department, Via Machiavelli 35, 44121 Ferrara, Italy

^* Corresponding author: Lorenzo Pareschi
^* Corresponding author: Lorenzo Pareschi

Received: July 2019

Revised: March 2020

Early access: September 2020

Published: September 2020

Abstract / Introduction Full Text(HTML) Figure(15) / Table(2) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 82C40, 94A08; Secondary: 68U10.

Citation:

FullText(HTML)

Figure 1. Trend to the steady–state of the one–dimensional Hegselmann–Krause model (1) with $ n = 100 $ agents equally spaced at initial time and non–symmetric interactions (top row) and of the mean–field model (12) computed with Algorithm 1 (bottom row) up to final time $ T = 20 $. Left panels show the case for $ \epsilon_1 = 0.5 $, the right panels show the case for $ \epsilon_1 = 0.15 $

Download: Full-size image PowerPoint slide

Figure 2. Evolution in time of the first moment (left) and of the second moment (right) for the two values of the bounded confidence level $ \epsilon_1 = 0.5 $ (dashed lines) and $ \epsilon_1 = 0.15 $ (solid lines)

Download: Full-size image PowerPoint slide

Figure 3. Left: trend to the steady–state of the mean–field model (12) computed with Algorithm 1 with $ N = 2\times10^4 $, $ M = 2 $, $ \epsilon_1 = 0.15 $ and up to final time $ T = 20 $. Right: energy decay of the mean–field model (12) for several values of interacting particles $ M $

Download: Full-size image PowerPoint slide

Figure 4. Particle solution (left plots) with $ N = 10000 $ and kinetic density (right plots). Results are provided at time $ t = 4 $ (top row) and final time $ T = 50 $ (bottom row). The bounded confidence level is $ \epsilon_1 = 0.15 $

Download: Full-size image PowerPoint slide

Figure 5. Evolution in time of the two–dimensional first moments (left) and second moments (right) for the bounded confidence level $ \epsilon_1 = 0.15 $

Download: Full-size image PowerPoint slide

Figure 6. 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 $ x $ (blue line with circle markers) and $ c $ direction (red line with triangle markers); at right, plot of the marginals. Confidence levels are $ \epsilon_1 = 0.15 $ and $ \epsilon_2 = 0.025 $

Download: Full-size image PowerPoint slide

Figure 7. Particle and kinetic density at equilibrium with confidence levels $ \epsilon_1 = 0.15 $, $ \epsilon_2 = 0.1 $ (left) and $ \epsilon_1 = 1 $, $ \epsilon_2 = 0.025 $ (right)

Download: Full-size image PowerPoint slide

Figure 8. Shape detection of the letter "A" initialized with $ 10\% $ of a uniform additive noise. Top left panel shows the initial condition. We show clusters obtained with bounded confidence values $ \epsilon_1 = 0.06 $ (top right), $ \epsilon_1 = 0.08 $ (bottom left) and $ \epsilon_1 = 0.1 $ (bottom right)

Download: Full-size image PowerPoint slide

Figure 9. Shape detection of the letter "A" initialized with $ 5.5\% $ of a Gaussian additive noise. Top left panel shows the initial condition. We show clusters obtained with bounded confidence values $ \epsilon_1 = 0.05 $ (top right), $ \epsilon_1 = 0.0675 $ (bottom left) and $ \epsilon_1 = 0.08 $ (bottom right)

Download: Full-size image PowerPoint slide

Figure 10. Left panel: initial image of $ 4096 $ pixels with four regions with different gray intensity. Middle panel: red dots show the positions of the clusters at equilibrium. Right panel: segmentation of the initial image in two regions

Download: Full-size image PowerPoint slide

Figure 11. Image segmentation of $ 174\times73 $ gray scale image taken by the data–set [6]

Download: Full-size image PowerPoint slide

Figure 12. Image segmentation of $ 93\times93 $ gray scale image taken by the data–set [24]

Download: Full-size image PowerPoint slide

Figure 13. Image segmentation of $ 128\times94 $ gray scale image taken by the data–set [32]

Download: Full-size image PowerPoint slide

Figure 14. Image segmentation of $ 67\times67 $ gray scale image taken by the data–set [32]

Download: Full-size image PowerPoint slide

Figure 15. Image segmentation of $ 132\times106 $ gray scale image taken by the data–set [32]

Download: Full-size image PowerPoint slide

Table 1. Number of clusters and errors depending on the bounded confidence value and the percentage of the noise when uniformly distributed

$ \alpha = 5\% $			$ \alpha = 7.5\% $			$ \alpha = 10\% $
$ \epsilon_1 $	$ \mathcal{E} $	$ \tilde{n} $	$ \epsilon_1 $	$ \mathcal{E} $	$ \tilde{n} $	$ \epsilon_1 $	$ \mathcal{E} $	$ \tilde{n} $
0.03	1.25e-02	30	0.03	3.47e-02	51	0.06	2.64e-02	11
0.04	4.10e-03	16	0.05	1.21e-02	14	0.07	1.48e-02	8
0.05	4.00e-03	12	0.07	7.70e-03	8	0.08	1.12e-02	8
0.06	4.60e-03	9	0.09	7.90e-03	8	0.09	1.63e-02	5
0.07	5.40e-03	8	0.11	1.66e-02	3	0.10	1.63e-02	5

| Show Table

DownLoad: CSV

Table 2. Number of clusters and errors depending on the bounded confidence value and the percentage of the noise when normally distributed

$ \alpha = 5\% $			$ \alpha = 5.5\% $			$ \alpha = 6\% $
$ \epsilon_1 $	$ \mathcal{E} $	$ \tilde{n} $	$ \epsilon_1 $	$ \mathcal{E} $	$ \tilde{n} $	$ \epsilon_1 $	$ \mathcal{E} $	$ \tilde{n} $
0.05	4.44e-02	23	0.05	4.73e-02	24	0.05	6.37e-02	30
0.06	1.36e-02	11	0.06	2.62e-02	13	0.06	4.16e-02	16
0.065	6.40e-03	9	0.065	1.63e-02	11	0.07	2.12e-02	9
0.07	6.70e-03	7	0.0675	7.40e-03	10	0.075	9.70e-03	7
0.08	8.50e-03	7	0.07	8.00e-03	9	0.08	9.20e-03	7
0.09	1.00e-02	6	0.08	9.80e-03	7	0.085	1.10e-02	5

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[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. doi: 10.1142/S0218202519500374.
[2]	G. Albi and L. Pareschi, Binary interaction algorithms for the simulation of flocking and swarming dynamics, Multiscale Model. Simul., 11 (2013), 1-29. doi: 10.1137/120868748.
[3]	G. Albi and L. Pareschi, Modeling of self-organized systems interacting with a few individuals: From microscopic to macroscopic dynamics, Appl. Math. Lett., 26 (2013), 397-401. doi: 10.1016/j.aml.2012.10.011.
[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. doi: 10.1007/978-3-319-49996-3_2.
[5]	G. Albi, L. Pareschi and M. Zanella, Opinion dynamics over complex networks: Kinetic modeling and numerical methods, Kinet. Relat. Models, 10 (2017), 1-32. doi: 10.3934/krm.2017001.
[6]	P. Arbeláez, M. Maire, C. Fowlkes and J. Malik, Contour detection and hierarchical image segmentation, IEEE Trans. Pattern Anal. Mach. Intell., 33 (2011), 898-916. doi: 10.1109/TPAMI.2010.161.
[7]	V. D. Blondel, J. M. Hendrickx and J. N. Tsitsiklis, On Krauses's multi-agent consensus model with state-dependent connectivity, IEEE Trans. Automat. Control, 54 (2009), 2586-2597. doi: 10.1109/TAC.2009.2031211.
[8]	V. D. Blondel, J. M. Hendrickx and J. N. Tsitsiklis, Continuous time average-preserving opinion dynamics with opinion-dependent communications, SIAM J. Control Optim., 48 (2010), 5214-5240. doi: 10.1137/090766188.
[9]	D. Borra and T. Lorenzi, Asymptotic analysis of continuous opinion dynamics models under bounded confidence, Commun. Pure Appl. Anal., 12 (2013), 1487-1499. doi: 10.3934/cpaa.2013.12.1487.
[10]	L. Boudin, R. Monaco and F. Salvarani, Kinetic model for multidimensional opinion formation, Phys. Rev. E, 81 (2010), 9pp. doi: 10.1103/PhysRevE.81.036109.
[11]	L. Boudin and F. Salvarani, Opinion dynamics: Kinetic modelling with mass media, application to the Scottish independence referendum, Phys. A, 444 (2016), 448-457. doi: 10.1016/j.physa.2015.10.014.
[12]	J. A. Cañizo, J. A. Carrillo and J. Rosado, A well-posedness theory in measures for some kinetic models of collective motion, Math. Models Methods Appl. Sci., 21 (2011), 519-539. doi: 10.1142/S0218202511005131.
[13]	C. Canuto, F. Fagnani and P. Tilli, An Eulerian approach to the analysis of rendez-vous algorithms, IFAC Proceedings Volumes, 41 (2008), 9039-9044. doi: 10.3182/20080706-5-KR-1001.01526.
[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. doi: 10.1137/100793177.
[15]	J. A. Carrillo, Y.-P. Choi, C. Totzeck and O. Tse, An analytical framework for consensus-based global optimization method, Math. Models Methods Appl. Sci., 28 (2018), 1037-1066. doi: 10.1142/S0218202518500276.
[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. doi: 10.1007/978-0-8176-4946-3_12.
[17]	L.-C. Chen, P. G., I. Kokkinos, K. Murphy and A. Loddon Yuille, DeepLab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected CRFs, IEEE Trans. Pattern Anal. Machine Intelligence, 40 (2018), 834-848. doi: 10.1109/TPAMI.2017.2699184.
[18]	I. D. Couzin, J. Krause, N. R. Franks and S. A. Levin, Effective leadership and decision-making in animal groups on the move, Nature, 433 (2005), 513-516. doi: 10.1038/nature03236.
[19]	F. Cucker and S. Smale, Emergent behavior in flocks, IEEE Trans. Automat. Control, 52 (2007), 852-862. doi: 10.1109/TAC.2007.895842.
[20]	P. Degond and S. Motsch, A macroscopic model for a system of swarming agents using curvature control, J. Stat. Phys., 143 (2011), 685-714. doi: 10.1007/s10955-011-0201-3.
[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. doi: 10.1109/ECC.2016.7810339.
[22]	J. C. Dittmer, Consensus formation under bounded confidence, Nonlinear Anal., 47 (2001), 4615-4622. doi: 10.1016/S0362-546X(01)00574-0.
[23]	B. Düring, P. Markowich, J.-F. Pietschmann and M.-T. Wolfram, Boltzmann and Fokker-Planck equations modelling opinion formation in the presence of strong leaders, Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 465 (2009), 3687-3708. doi: 10.1098/rspa.2009.0239.
[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. doi: 10.1109/ICCV.2009.5459211.
[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]	P.-E. Jabin and S. Motsch, Clustering and asymptotic behavior in opinion formation, J. Differential Equations, 257 (2014), 4165-4187. doi: 10.1016/j.jde.2014.08.005.
[28]	J. Kennedy and R. Eberhart, Particle swarm optimization, Proc. Internat. Conference Neural Networks, Perth, Australia, 1995. doi: 10.1109/ICNN.1995.488968.
[29]	X. Liu, Y. Qiao, X. Chen, J. Miao and L. Duan, Color image segmentation based on modified Kuramoto model, Procedia Comp. Sci., 88 (2016), 245-258. doi: 10.1016/j.procs.2016.07.432.
[30]	J. Lorenz, A stabilization theorem for dynamics of continuous opinions, Phys. A, 355 (2005), 217-223. doi: 10.1016/j.physa.2005.02.086.
[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. doi: 10.1109/ICCV.2001.937655.
[33]	K. H. Memon, S. Memon, M. A. Qureshi, M. B. Alvi, D. Kumar and R. A. Shah, Kernel possibilistic fuzzy $c$-means clustering with local information for image segmentation, Internat. J. Fuzzy Syst., 21 (2019), 321-332. doi: 10.1007/s40815-018-0537-9.
[34]	S. Motsch and E. Tadmor, A new model for self-organized dynamics and its flocking behavior, J. Stat. Phys., 144 (2011), 923-947. doi: 10.1007/s10955-011-0285-9.
[35]	S. Motsch and E. Tadmor, Heterophilious dynamics enhances consensus, SIAM Review, 56 (2014), 577-621. doi: 10.1137/120901866.
[36]	A. Nedić and B. Touri, Multi-dimensional Hegselmann-Krause dynamics, 2012 IEEE 51st IEEE Conference on Decision and Control (CDC), Maui, HI, 2012. doi: 10.1109/CDC.2012.6426417.
[37]	A. V. Novikov and E. N. Benderskaya, Oscillatory neural networks based on the Kuramoto model for cluster analysis, Pattern Recognition Image Anal., 24 (2014), 365-371. doi: 10.1134/S1054661814030146.
[38]	G. Oliva, D. La Manna, A. Fagiolini and R. Setola, Distributed data clustering via opinion dynamics, Internat. J. Distributed Sensor Networks, 11 (2015). doi: 10.1155/2015/753102.
[39]	S. Osher and J. A. Sethian, Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations, J. Comput. Phys., 79 (1988), 12-49. doi: 10.1016/0021-9991(88)90002-2.
[40]	L. Pareschi and G. Toscani, Interacting Multiagent Systems. Kinetic Equations and Monte Carlo Methods, Oxford University Press, 2013.
[41]	R. Pinnau, C. Totzeck, O. Tse and S. Martin, A consensus-based model for global optimization and its mean-field limit, Math. Models Methods Appl. Sci., 27 (2017), 183-204. doi: 10.1142/S0218202517400061.
[42]	G. Puppo, M. Semplice, A. Tosin and G. Visconti, Kinetic models for traffic flow resulting in a reduced space of microscopic velocities, Kinet. Relat. Models, 10 (2017), 823-854. doi: 10.3934/krm.2017033.
[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). doi: 10.1186/s13640-018-0322-6.
[45]	L. Tian, L. Han and J. Yue, Research on image segmentation based on clustering algorithm, Internat. J. Signal Process. Image Process. Pattern Recognition, 9 (2016), 1-12. doi: 10.14257/ijsip.2016.9.2.01.
[46]	L. Zhang, Y. Gao, Y. Xia, K. Lu, J. Shen and R. Ji, Representative discovery of structure cues for weakly-supervised image segmentation, IEEE Transac. Multimedia, 16 (2014), 470-479. doi: 10.1109/TMM.2013.2293424.
[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). doi: 10.1186/s13640-018-0309-3.