Bonjour,
L'agrégation autour des centres mobiles est en fait une heuristique
spécialisée pour un problème d'optimisation combinatoire NP-complet qui
consiste à trouver la répartition optimale de n objets dans k classes au
sens d'un certain critère (généralement l'inertie). Il existe donc des
précurseurs, des ré-inventions et des variantes. Les anglo-saxons parlent de
k-means, les francophones d'agrégation autour de centres mobiles ou de nuées
dynamiques (c'est en fait à la fois une ré-invention et une généralisation
par Diday en 1970-1971).
Les références classiques :
MacQueen, J. 1967. Some methods for classification and analysis of
multivariate obervations. 281-297 in: L.M. Le Cam & J. Neyman [eds.]
Proceedings of the fifth Berkeley symposium on mathematical statistics and
probability. Vol. 1. University of California Press, Berkeley.
Lance G.N. & W.T. Williams. 1967. A general theory of classificatory sorting
strategies. II. Clustering systems. Comput. J. 10 : 271-277.
Par la suite on trouve autant de références que l'on veut (ou presque)
Cordialement
Philippe Aubry
PS.
A noter que la solution exacte peut être obtenue en temps polynomial dans le
cas limite d'une seule dimension, grâce à un algorithme de programmation
dynamique (algorithme publié en 1958). Cela dit, si le nombre d'objets et le
nombre de classes sont élevés, cela peut prendre tout de même un temps non
négligeable.
> Quelqu'un aurait-il une ou quelques références en Anglais d'article
> "fondateur" ou d'ouvrage de référence pour la méthode d'agrégation autour
> des centres mobiles. La doc ADE module cluster/compute partition propose
> une référence de bouquin généraliste en français.
>
> Merci d'avance
> Michel VENNETIER
> Cemagref
> BP 31, Le Tholonet,
> 13612 Aix-en-Provence Cedex 1
>
> tel : (33) 04.42.66.99.22 (dir)
> (33) 04.42.66.99.15 / 99.62 (secret)
> FAX : (33) 04.42.66.99.71
> mail to : michel.vennetier@cemagref.fr
> web national http://www.cemagref.fr
> web local http://www.aix.cemagref.fr
>
> pour s'y rendre/access :
> Cemagref
> 3275 route Cézanne
> 13100 le Tholonet
This archive was generated by hypermail 2b30 : Fri Feb 14 2003 - 14:36:11 MET