L'ultramétrique inférieure maximum d'une dissimilarité à valeurs dans un inf-demi-treillis

Benkaraache, Taoufik

Mathématiques informatique et sciences humaines, Tome 143 (1998), pp. 27-40.

Les dissimilarités sont habituellement à valeurs dans l'ensemble des réels positifs R+. Cet ensemble est riche en propriétés dont, par exemple, celles liées à l'ordre total de R. Plusieurs auteurs ont montré que certains résultats fondamentaux relatifs aux dissimilarités restent valables quand on remplace R+ par un ensemble ordonné L plus général. Dans ce papier nous proposons deux méthodes d'approximation d'une dissimilarité d par l'ultramétrique inférieure maximum (la sous-dominante ultramétrique) quand d est à valeurs dans un inf-demi-treillis fini.

Dissimilarity functions are usually defined to take values in the set R+ of nonnegative reals. This set has various properties as, for instance, those related to the intrinsic linear order of R. But many authors have shown that a number of basic results relative to dissimilarity functions are preserved when R+ is replaced by any partially ordered set. In this paper we propose two methods for the fitting of a given dissimilarity approximation by the subdominant ultrametric when this dissimilarity takes values in a meet semi-lattice.

Barthélemy, J.P., Leclerc, B., Monjardet, B., "Ensembles ordonnés et taxonomie mathématique", in M. Pouzet and D. Richard (eds.), Orders : Description and roles, Annals of Discrete Mathematics, 23, 1984, 523 - 548. | MR | Zbl

Benkaraache, T., "Problèmes de validité en classification et quelques généralisations aux ultramétriques à valeurs dans un ensemble ordonné", Thèse de doctorat, Université Joseph Fourier, Grenoble, 1993.

Benkaraache, T., Van Cutsem, B., "Complexité d'une hiérarchie et comparaison de hiérarchies : une revue et quelques nouvelles idées ", Communication aux Journées de Statistiques de Vannes, 1993.

Benkaraache, T., Van Cutsem, B., "Comparison of hierarchical classifications", Rapport technique du laboratoire LMC-IMAG, RT 100, Grenoble,1994.

Benzecri, J.P., L'analyse des données. I - La taxinomie, Paris, Dunod, 1973. | MR

Critchley, F., Van Cutsem, B., "An order - theoretic unification and generalization of certain fundamental bijections", in Bernard Van Cutsem (ed.), Classification and Dissimilarity Analysis, Lecture Notes in Statistics, vol. 93, New York, Springer Verlag, 1994, 87-148. | MR | Zbl

Davey, B.A., Priestley, H.A., Introduction to lattice and order, Cambridge (U. K.), Cambridge University Press, 1990. | MR | Zbl

Gower, J.C., Ross, J.S., "Minimum Spaning trees and Single Linkage Cluster Analysis", Applied Stat. 18, 1969, 54 - 64. | MR

Janowitz, M.F., "An order theoretic model for cluster analysis", SIAM J. Appl. Math. 34, 1978, 55-72. | MR | Zbl

Jardine, N., Sibson, R., Mathematical taxonomy, London, Wiley, 1971. | MR | Zbl

Johnson, S.C., "Hierarchical clustering schemes", Psychometrika 32,1967, 241-254.

Leclerc, B., "The residuation model for the ordinal construction of dissimilarities and other valued objects", in Bernard Van Cutsem (ed.), Classification and Dissimilarity Analysis, Lecture notes in Statistics 93, New York, Springer Verlag,1994,149-172. | MR | Zbl

Roux, M., "Un algorithme pour construire une hiérarchie particulière", Thèse de 3ème cycle, Université de Paris VI, 1968.

Sibson, R., "Slink : an optimally efficient algorithm for the single link cluster method", Computer Journal 16, n°1, 1972, 30-34. | MR

Van Cutsem, B., "Ultramétriques, distances, ϕ-distances maximales dominées par une dissimilarité", Statistique et Analyse des Données 8, 1983, 42-63. | Numdam | Zbl