Comparaison de deux critères en classification ascendante hiérarchique sous contrainte de contiguïté. Application en imagerie numérique

Israël-César Lerman; Kaddour Bachar

Journal de la société française de statistique (2008)

  • Volume: 149, Issue: 2, page 45-74
  • ISSN: 1962-5197

Abstract

top
We analyse an algorithm of ascendant hierarchical classification under contiguity constraint and using the aggregation principle of reciprocal nearest neighbors. This algorithm is situated in the general framework of quick ascendant hierarchical classification algorithms. Two cluster merging criteria are studied. The former is the classical inertia Ward criterion and the latter consists of the maximal likelihood linkage family criteria. A new contiguity version of this criterion proves its efficiency in image segmentation. One major feature of our algorithm is the linear nature of the computational complexity. New strategies concerning multiple aggregation in the class formation and contiguity notion are positively evaluated in terms of quality and efficiency. We establish mathematically and experimentally how the used criterion influences inversion possibility in the tree building. Finally, comparative results of both types of criteria in image segmentation on satellite pictures are discussed.

How to cite

top

Lerman, Israël-César, and Bachar, Kaddour. "Comparaison de deux critères en classification ascendante hiérarchique sous contrainte de contiguïté. Application en imagerie numérique." Journal de la société française de statistique 149.2 (2008): 45-74. <http://eudml.org/doc/93479>.

@article{Lerman2008,
abstract = {Nous analysons une algorithmique de classification ascendante hiérarchique sous contrainte de contiguïté par agrégation des voisins réciproques en la situant dans le contexte général des algorithmes rapides de classification ascendante hiérarchique. Surtout, nous la déclinons selon deux types de critères. Il s’agit d’une part, du critère de Ward de la variation de l’inertie expliquée et d’autre part, d’une famille paramétrée du critère VL de la vraisemblance du lien maximal. Le contexte applicatif est celui de la segmentation d’image. On souligne la nature linéaire de la complexité algorithmique que nous montrons expérimentalement. L’influence algorithmique de la notion de contiguïté retenue est mise en évidence. Une nouvelle stratégie mettant en oeuvre l’agrégation multiple dans la formation des classes montre tout son intérêt. On étudie aussi bien sur le plan théorique qu’expérimental la possibilité d’inversions compte tenu du type de critère utilisé. Nous terminons en proposant une analyse comparative des résultats sur des données réelles en imagerie satellitaire.},
author = {Lerman, Israël-César, Bachar, Kaddour},
journal = {Journal de la société française de statistique},
keywords = {hierarchical classification; contiguity graph; multiple aggregation; complexity; inversion; image processing},
language = {fre},
number = {2},
pages = {45-74},
publisher = {Société française de statistique},
title = {Comparaison de deux critères en classification ascendante hiérarchique sous contrainte de contiguïté. Application en imagerie numérique},
url = {http://eudml.org/doc/93479},
volume = {149},
year = {2008},
}

TY - JOUR
AU - Lerman, Israël-César
AU - Bachar, Kaddour
TI - Comparaison de deux critères en classification ascendante hiérarchique sous contrainte de contiguïté. Application en imagerie numérique
JO - Journal de la société française de statistique
PY - 2008
PB - Société française de statistique
VL - 149
IS - 2
SP - 45
EP - 74
AB - Nous analysons une algorithmique de classification ascendante hiérarchique sous contrainte de contiguïté par agrégation des voisins réciproques en la situant dans le contexte général des algorithmes rapides de classification ascendante hiérarchique. Surtout, nous la déclinons selon deux types de critères. Il s’agit d’une part, du critère de Ward de la variation de l’inertie expliquée et d’autre part, d’une famille paramétrée du critère VL de la vraisemblance du lien maximal. Le contexte applicatif est celui de la segmentation d’image. On souligne la nature linéaire de la complexité algorithmique que nous montrons expérimentalement. L’influence algorithmique de la notion de contiguïté retenue est mise en évidence. Une nouvelle stratégie mettant en oeuvre l’agrégation multiple dans la formation des classes montre tout son intérêt. On étudie aussi bien sur le plan théorique qu’expérimental la possibilité d’inversions compte tenu du type de critère utilisé. Nous terminons en proposant une analyse comparative des résultats sur des données réelles en imagerie satellitaire.
LA - fre
KW - hierarchical classification; contiguity graph; multiple aggregation; complexity; inversion; image processing
UR - http://eudml.org/doc/93479
ER -

References

top
  1. [1] K. BACHAR. Contributions en analyse factorielle et en classification ascendante hiérarchique sous contrainte de contiguïté. Applications à la segmentation d’images. PhD thesis, Université de Rennes 1, Décembre 1994. 
  2. [2] K. BACHAR and I.C. LERMAN. Statistical conditions for a linear complexity for an algorithm of hierarchical classification under constraint of contiguity. In Bock H.-H. Rizzi A., Vichi M., editor, Advances in Data Science and Classification/ IFCS’98, pages 131-136. Springer-Verlag, 1998. Zbl1052.62525MR1675044
  3. [3] K. BACHAR and I.C. LERMAN. Étude d’un comportement paramétré de CAHCVR sur des données réelles en imagerie numérique. In Melfi G. Dodge Y., editor, Méthodes et Perspectives en Classification, pages 63-66. Presses Académique Neuchâtel, 2003. 
  4. [4] K. BACHAR and I.C. LERMAN. Fixing parameters in the constrained hierarchical classification method : Application to digital image segmentation. In Banks D. et al., editor, Classification Clustering and Data Mining Applications, pages 85-94. Springer, 2004. MR2113600
  5. [5] J.P. BARTHELEMY and A. GUENOCHE. Trees and Proximity Representations. J. Wiley, 1991. Zbl0790.05021MR1138723
  6. [6] J.P. BENZECRI. Construction d’une classification ascendante hiérarchique par la recherche en chaîne des voisins réciproques. Les Cahiers de l’Analyse des Données, (VII) : 209-218, 1982. Zbl0492.62049
  7. [7] M. BRUYNOOGHE. Classification ascendante hiérarchique des grands ensembles de données ; un algorithme rapide fondé sur la construction des voisinages réductibles. Les Cahiers de l’Analyse des Données, (III) : 7-33, 1978. 
  8. [8] M. BRUYNOOGHE. Nouveaux algorithmes en classification automatique applicables aux très grands ensembles de données, rencontrés en traitement d’images et en reconnaissance des formes. PhD thesis, Thèse d’État, Université de Paris 6, janvier 1989. 
  9. [9] C. DE RAHM. La classification hiérarchique ascendante selon la méthode des voisins réciproques. Les Cahiers de l’Analyse des Données, (V, no 2) : 135-144, 1980. 
  10. [10] A.D. GORDON. A survey of constrained classification. Computational Statistics and Data Analysis, (1) : 17-29, 1996. Zbl0900.62313MR1380831
  11. [11] P. HANSEN, B. JAUMARD, C. MEYER, B. SIMEONE, and V. DORING. Maximum split clustering under connectivity constraints. Journal of Classification, (20) : 143-180, 2003. Zbl1083.91063MR2026474
  12. [12] J. JUAN. Programme de classification hiérarchique par l’algorithme de recherche en chaîne des voisins réciproques. Les Cahiers de l’Analyse des Données, (VII) : 219-225, 1982. Zbl0505.62042
  13. [13] G.N. LANCE and W.T. WILLIAMS. A general theory of classification sorting strategies : clustering systems. Computer Journal, (10) : 271-277, 1967. 
  14. [14] L. LEBART. Programme d’agrégation avec contraintes. Les Cahiers de l’Analyse des Données, (III(3)) : 275-287, 1978. 
  15. [15] I.C. LERMAN. Sur l’analyse des données préalable à une classification automatique. proposition d’une nouvelle mesure de similarité. Mathématiques et Sciences Humaines, (32) : 5-15, 1970. Zbl0221.62021MR303794
  16. [16] I.C. LERMAN. Classification et analyse ordinale des données. Dunod, 1981. MR645150
  17. [17] I.C. LERMAN. Sur la signification des classes issues d’une classification automatique. In J. Felsenstein, editor, Numerical Taxonomy, pages 179-198. Springer-Verlag, 1983. 
  18. [18] I.C. LERMAN. Construction d’un indice de similarité entre objets décrits par des variables d’un type quelconque. application au problème du consensus en classification. Revue de Statistique Appliquée, (XXXV(2)) : 39-60, 1987. Zbl0615.62068MR896003
  19. [19] I.C. LERMAN. Formules de réactualisation en cas d’agrégations multiples. RAIRO, série R.O., (vol 23, no 2) : 151-163, 1989. Zbl0674.62042MR1016137
  20. [20] I.C. LERMAN. Foundations of the likelihood linkage analysis(lla) classification method. Applied Stochastic Models and Data Analysis, (vol 7,1) : 6376, march 1991. Zbl0800.62320MR1105871
  21. [21] I.C. LERMAN. Conception et analyse de la forme limite d’une famille de coefficients statistiques d’association entre variables relationnelles I. Revue Mathématiques Informatique et Sciences Humaines, (118) : 35-52, 1992. Zbl0851.62039MR1182251
  22. [22] I.C. LERMAN. Conception et analyse de la forme limite d’une famille de coefficients statistiques d’association entre variables relationnelles II. Revue Mathématique Informatique et Sciences Humaines, (119) : 75-100, 1992. Zbl0851.62040MR1195699
  23. [23] I.C. LERMAN and K. BACHAR. Agrégations multiples et contraintes de contiguïté dans la classification ascendante hiérarchique utilisant les voisins réciproques et le critère de la vraisemblance des liens. In 8-èmes Rencontres de la Société Francophone de Classification, pages 232-237. Université Pointe-à-Pitre, 2001. 
  24. [24] I.C. LERMAN and K. BACHAR. Construction et justification d’une méthode de classification ascendante hiérarchique accélérée fondée sur le critère de la vraisemblance du lien maximal en cas de données de contiguïté. Application en imagerie numérique. Rapport de Recherche 1616, IRISA, avril 2004. 
  25. [25] I.C. LERMAN and Ph. PETER. Indice probabiliste de vraisemblance du lien entre objets quelconques ; analyse comparative entre deux approches. Revue de Statistique Appliquée, (LI(1)) : 5-35, 2003. 
  26. [26] I.C. LERMAN, Ph. PETER, and H. LEREDDE. Principes et calculs de la méthode implantée dans le programme CHAVL 1-ère partie. La Revue de Modulad, (12) : 33-70, Décembre 1993. 
  27. [27] I.C. LERMAN, J.F. PINTO da COSTA, and H. SILVA. Validation of very large data sets clustering by means of a nonparametric criterion. In A. Sokolowski K. Jajuga and H.-H. Bock, editors, Classification, Clustering and Data Analysis, Recent Advances and Applications, pages 147-157. Springer-Verlag, 2002. Zbl1032.62061MR2010433
  28. [28] P. MONESTIEZ. Méthode de classification automatique sous contraintes spatiales. Statistique et Analyse des Données, (3) : 75-84, 1977. 
  29. [29] F. MURTAGH. A survey of algorithms for contiguity-constrained clustering and related problems. The Computer Journal, (28) : 82-88, 1985. 
  30. [30] F.C. NICOLAÜ and H. BACELAR-NICOLAÜ. Some trends in the classification of variables. In Data Science, Classification and Related Methods, IFCS’96, pages 89-98. Springer-Verlag, 1996. Zbl0894.62075
  31. [31] M. OUALI-ALLAH. Analyse en préordonnance des données qualitatives. Application aux données numériques et symboliques. PhD thesis, Université de Rennes 1, Décembre 1991. 
  32. [32] E.J. PAUWELS and G. FREDERIX. Finding salient regions in images. Computer Vision and Image Understanding, (75) : 73-85, 1999. 
  33. [33] C. PERRUCHET. Constrained agglomerative hierarchical classification. Pattern Recognition, (16(2)) : 213-217, 1983. 
  34. [34] P. PETER, H. LEREDDE, and I.C. LERMAN. Notice du programme CHAVLH (Classification Hiérarchique par Analyse de la Vraisemblance des Liens en cas de variables Hétérogènes). Dépôt APP (Agence pour la Protection des Programmes) IDDN.FR.001.240016.000.S.P.2006.000.20700, Université de Rennes 1, Décembre 2005. 
  35. [35] A. PRODHOMME. Indices d’explication des classes obtenues par une méthode de classification hiérarchique respectant la contrainte de contiguïté spatiale. Application à la viticulture Girondine et à la construction de logements dans les Bouches-du Rhône. PhD thesis, Université de Rennes 1, Décembre 1980. 
  36. [36] M. TABB and N. AHUJIA. Multiscale image segmentation by integrated edge and region detection. IEEE Trans. Image Processing, (6) : 642-655, 1997. 
  37. [37] J.H. WARD. Hierarchical grouping to optimise an objective function. Journal of the American Statistical Association, (58) : 238-244, 1963. MR148188

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.