Skip to main content

2016 | OriginalPaper | Buchkapitel

10. Building a Classification Tree

verfasst von : Israël César Lerman

Erschienen in: Foundations and Methods in Combinatorial and Statistical Data Analysis and Clustering

Verlag: Springer London

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The basic data consists of a finite set E provided with a dissimilarity or a similarity function. The elements of E are of the same nature. As seen in Chap. 3, E can be a set of attributes, a set of objects or a set of categories. Tables 3.​4 and 3.​5 of Chap. 3 give a precise idea of the possible different versions of E. On the other hand, the set E may be weighted by a positive numerical measure \(\mu _{E}\), assigning to each of its elements x (\(x \in E\)) a weight \(\mu _{x}\). \(\mu _{x}\) defines the “importance” with which x has to be considered. The dissimilarity or similarity function on E is mostly numerical. However, it might be ordinal. In Chaps. 47, facets of building a similarity index or association coefficient on E have been minutely examined in relation to the descriptive nature of E.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Fußnoten
1
Two total preorders \(\omega \) and \(\omega '\) on a given set are comparable if the graph of one of both total preorders is included in the other one.
 
Literatur
1.
Zurück zum Zitat Abbassi, N.: Identification de familles protéiques. Master 2, Research report, IRISA-INRIA, June 2013 Abbassi, N.: Identification de familles protéiques. Master 2, Research report, IRISA-INRIA, June 2013
2.
Zurück zum Zitat Aczel, J., Forte, B., Ng, C.T.: Why the Shannon and Hartley entropies are “natural”. Adv. Appl. Probab. 6, 131–146, Printed in Israel (1974) Aczel, J., Forte, B., Ng, C.T.: Why the Shannon and Hartley entropies are “natural”. Adv. Appl. Probab. 6, 131–146, Printed in Israel (1974)
3.
Zurück zum Zitat Bachar, K., Lerman, I.-C.: Statistical conditions for an algorithm of hierarchical classification under constraint of contiguiuty. In: Rizzi, A., Bock, H.-H., Vichi, M. (eds.) Advances in Data Science and Classification, pp. 131–136. Springer, Berlin (1998) Bachar, K., Lerman, I.-C.: Statistical conditions for an algorithm of hierarchical classification under constraint of contiguiuty. In: Rizzi, A., Bock, H.-H., Vichi, M. (eds.) Advances in Data Science and Classification, pp. 131–136. Springer, Berlin (1998)
4.
Zurück zum Zitat Bachar, K., Lerman, I.-C.: Fixing parameters in the constrained hierarchical classification method: application to digital image segmentation. In: Banks, D., et al. (eds.) Classification Clustering and Data Mining Applications, pp. 85–94. Springer, New York (2004) Bachar, K., Lerman, I.-C.: Fixing parameters in the constrained hierarchical classification method: application to digital image segmentation. In: Banks, D., et al. (eds.) Classification Clustering and Data Mining Applications, pp. 85–94. Springer, New York (2004)
5.
Zurück zum Zitat Benzécri, J.-P.: 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 7, 209–218 (1982) Benzécri, J.-P.: 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 7, 209–218 (1982)
6.
Zurück zum Zitat Benzécri, J.-P.: L’analyse des données, tomes I et II. Dunod (1973) Benzécri, J.-P.: L’analyse des données, tomes I et II. Dunod (1973)
7.
Zurück zum Zitat Bock, H.H.: Automatische Klassifikation Vandenhoeck und Rupprecht. Gottingen (1974) Bock, H.H.: Automatische Klassifikation Vandenhoeck und Rupprecht. Gottingen (1974)
8.
Zurück zum Zitat Bruynooghe, M.: Classification ascendante hiérarchique des grands ensembles de données; un algorithme rapide fondé sur la construction des voisinages réductibles. Cahiers de l’Analyse des Données III(1), 7–33 (1978) Bruynooghe, M.: Classification ascendante hiérarchique des grands ensembles de données; un algorithme rapide fondé sur la construction des voisinages réductibles. Cahiers de l’Analyse des Données III(1), 7–33 (1978)
9.
Zurück zum Zitat Bruynooghe, M.: Nouveaux algorithmes en classification automatique applicables aux très grands ensembles de données, rencontrés en traitement d’images et en reconnaissance de formes. Ph.D. thesis, Thèse d’Etat, Université de Paris 6, Jan 1989 Bruynooghe, M.: Nouveaux algorithmes en classification automatique applicables aux très grands ensembles de données, rencontrés en traitement d’images et en reconnaissance de formes. Ph.D. thesis, Thèse d’Etat, Université de Paris 6, Jan 1989
10.
Zurück zum Zitat Bruynooghe, M.: Recent results in hierarchical clustering. I—the reducible neighborhoods clustering algorithm. Int. J. Pattern Recognit. Artif. Intell. 7(3), 541–571 (1993) Bruynooghe, M.: Recent results in hierarchical clustering. I—the reducible neighborhoods clustering algorithm. Int. J. Pattern Recognit. Artif. Intell. 7(3), 541–571 (1993)
11.
Zurück zum Zitat Costa Nicolau, F., Bacelar-Nicolau, H.: Some trends in the classification of variables.In: Hayashi, C., et al. (eds.) Data Science, Classification and Related Methods, pp. 89–98.Springer, New York (1998) Costa Nicolau, F., Bacelar-Nicolau, H.: Some trends in the classification of variables.In: Hayashi, C., et al. (eds.) Data Science, Classification and Related Methods, pp. 89–98.Springer, New York (1998)
12.
Zurück zum Zitat Cutting, D., Karger, D., Pederson, J., Tukey, J.: Scatter/gather: a cluster-based approach to browsing large document collections. In: Belkin, N., et al. (eds.) International ACM SIGIR Conference on Research and Development in Information Retrevial, pp. 318–339. ACM Press (1992) Cutting, D., Karger, D., Pederson, J., Tukey, J.: Scatter/gather: a cluster-based approach to browsing large document collections. In: Belkin, N., et al. (eds.) International ACM SIGIR Conference on Research and Development in Information Retrevial, pp. 318–339. ACM Press (1992)
13.
Zurück zum Zitat de Rham, C.: La classification hiérarchique ascendante selon la méthode des voisins réciproques. Les Cahiers de l’Analyse des Données V(2), 135–144 (1980) de Rham, C.: La classification hiérarchique ascendante selon la méthode des voisins réciproques. Les Cahiers de l’Analyse des Données V(2), 135–144 (1980)
14.
Zurück zum Zitat Diday, E.: Inversions en classification hiérarchique: application à la construction adaptative d’indices d’agrégation. Revue de Statistique Appliquée 31(1), 45–62 (1983) Diday, E.: Inversions en classification hiérarchique: application à la construction adaptative d’indices d’agrégation. Revue de Statistique Appliquée 31(1), 45–62 (1983)
15.
Zurück zum Zitat Edwards, W.F., Cavalli-Sforza, L.L.: A method for cluster analysis. Biometrics 21, 363–375 (1965)CrossRef Edwards, W.F., Cavalli-Sforza, L.L.: A method for cluster analysis. Biometrics 21, 363–375 (1965)CrossRef
16.
Zurück zum Zitat Feller, W.: An Introduction to Probability Theory and Its Applications, vol. II, 2nd edn. Wiley, New York (1971)MATH Feller, W.: An Introduction to Probability Theory and Its Applications, vol. II, 2nd edn. Wiley, New York (1971)MATH
17.
Zurück zum Zitat Florek, K.J., Lukaszewick, J., Perkal, J., Steinhaus, H., Zubrzycki, S.: Sur la liaison et la division des points d’un ensemble fini. In: Colloquium Mathematics, vol. 2, pp. 282–285 (1951) Florek, K.J., Lukaszewick, J., Perkal, J., Steinhaus, H., Zubrzycki, S.: Sur la liaison et la division des points d’un ensemble fini. In: Colloquium Mathematics, vol. 2, pp. 282–285 (1951)
18.
Zurück zum Zitat Florek, K.J., Lukaszewick, J., Perkal, J., Steinhaus, H., Zubrzycki, S.: Taksonomia wroclawska (in polish with english summary). Przegl. antrop. 17, 193–217 (1951) Florek, K.J., Lukaszewick, J., Perkal, J., Steinhaus, H., Zubrzycki, S.: Taksonomia wroclawska (in polish with english summary). Przegl. antrop. 17, 193–217 (1951)
19.
Zurück zum Zitat Ghazzali, N.: Comparaison et réduction d’arbres de classification, en relation avec des problèmes de quantification en imagerie numérique. Ph.D. thesis, Université de Rennes 1, May 1992 Ghazzali, N.: Comparaison et réduction d’arbres de classification, en relation avec des problèmes de quantification en imagerie numérique. Ph.D. thesis, Université de Rennes 1, May 1992
20.
Zurück zum Zitat Ghazzali, N., Léger, A., Lerman, I.C.: Rôle de la classification statistique dans la compression du signal d’image: Panoram et étude spécifique de cas. La Revue de Modulad 14, 51–91 (1994) Ghazzali, N., Léger, A., Lerman, I.C.: Rôle de la classification statistique dans la compression du signal d’image: Panoram et étude spécifique de cas. La Revue de Modulad 14, 51–91 (1994)
21.
Zurück zum Zitat Gordon, A.D.: A review of hierarchical classification. J. R. Stat. Soc. 150(2), 119–137 (1987)MathSciNetMATH Gordon, A.D.: A review of hierarchical classification. J. R. Stat. Soc. 150(2), 119–137 (1987)MathSciNetMATH
22.
Zurück zum Zitat Govaert, G.: La classification croisée. La Revue de Modulad 4, 9–36 (1989) Govaert, G.: La classification croisée. La Revue de Modulad 4, 9–36 (1989)
23.
Zurück zum Zitat Gras, R., Larher, A.: L’implication statistique, une nouvelle méthode d’analyse des données. Mathématiques, Informatique et Sciences Humaines 120, 5–31 (1993) Gras, R., Larher, A.: L’implication statistique, une nouvelle méthode d’analyse des données. Mathématiques, Informatique et Sciences Humaines 120, 5–31 (1993)
24.
Zurück zum Zitat Jambu, M.: Classification Automatique pour l’Analyse des Données. Dunod (1978) Jambu, M.: Classification Automatique pour l’Analyse des Données. Dunod (1978)
25.
Zurück zum Zitat Jardine, N., Sibson, R.: Mathematical Taxonomy. Wiley, New York (1971)MATH Jardine, N., Sibson, R.: Mathematical Taxonomy. Wiley, New York (1971)MATH
26.
Zurück zum Zitat Kojadinovic, I.: Hierarchical clustering of continuous variables based on the empirical copula process and permutation linkages. Comput. Stat. Data Anal. 54, 90–108 (2010)MathSciNetCrossRefMATH Kojadinovic, I.: Hierarchical clustering of continuous variables based on the empirical copula process and permutation linkages. Comput. Stat. Data Anal. 54, 90–108 (2010)MathSciNetCrossRefMATH
27.
Zurück zum Zitat Lance, G.N., Williams, W.T.: A general theory of classificatory sorting strategies. I. Hierarchical systems. Comput. J. 9, 373–380 (1967)CrossRef Lance, G.N., Williams, W.T.: A general theory of classificatory sorting strategies. I. Hierarchical systems. Comput. J. 9, 373–380 (1967)CrossRef
28.
Zurück zum Zitat Lee, A., Willcox, B.: Minkowski generalizations of Ward’s method in hierarchical clustering. J. Classif. 31, 194–218 (2014)MathSciNetCrossRef Lee, A., Willcox, B.: Minkowski generalizations of Ward’s method in hierarchical clustering. J. Classif. 31, 194–218 (2014)MathSciNetCrossRef
29.
Zurück zum Zitat Leredde, H.: La méthode des pôles d’attraction; La méthode des pôles d’agrégation : deux nouvelles familles d’algorithmes en classification automatique et sériation. Ph.D. thesis, Université de Paris 6, Oct 1979 Leredde, H.: La méthode des pôles d’attraction; La méthode des pôles d’agrégation : deux nouvelles familles d’algorithmes en classification automatique et sériation. Ph.D. thesis, Université de Paris 6, Oct 1979
30.
Zurück zum Zitat Lerman, I.-C., Bachar, K.: Contruction et justification d’une méthode de classification ascendante hiérarchique accélérée fondée fondée sur le critère de la vraisemblance du lien en cas de données de contiguïté. application en imagerie numérique. Publication Interne 1616, IRISA-INRIA, April 2004 Lerman, I.-C., Bachar, K.: Contruction et justification d’une méthode de classification ascendante hiérarchique accélérée fondée fondée sur le critère de la vraisemblance du lien en cas de données de contiguïté. application en imagerie numérique. Publication Interne 1616, IRISA-INRIA, April 2004
31.
Zurück zum Zitat Lerman, I.-C., Bachar, K.: 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), 45–74 (2008) Lerman, I.-C., Bachar, K.: 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), 45–74 (2008)
32.
Zurück zum Zitat Lerman, I.-C., Peter, Ph.: Analyse d’un algorithme de classification hiérarchique en parallèle pour le traitement de gros ensembles, aspects méthodologiques et programmation. Publication Interne IRISA et Rapport de Recherche INRIA 232, IRISA-INRIA, Aug 1984 Lerman, I.-C., Peter, Ph.: Analyse d’un algorithme de classification hiérarchique en parallèle pour le traitement de gros ensembles, aspects méthodologiques et programmation. Publication Interne IRISA et Rapport de Recherche INRIA 232, IRISA-INRIA, Aug 1984
33.
Zurück zum Zitat Lerman, I.C.: Les bases de la classification automatique. Gauthier-Villars (1970) Lerman, I.C.: Les bases de la classification automatique. Gauthier-Villars (1970)
34.
Zurück zum Zitat Lerman, I.C.: Analyse du phénomène de la “sériation”. Revue mathématique et Sciences Humaines 38 (1972) Lerman, I.C.: Analyse du phénomène de la “sériation”. Revue mathématique et Sciences Humaines 38 (1972)
36.
Zurück zum Zitat Lerman, I.C.: Formules de réactualisation en cas d’agrégations multiples. Recherche Opérationnele, Operations Research 23(2), 151–163 (1989) Lerman, I.C.: Formules de réactualisation en cas d’agrégations multiples. Recherche Opérationnele, Operations Research 23(2), 151–163 (1989)
37.
Zurück zum Zitat Lerman, I.C.: Foundations of the likelihood linkage analysis (LLA) classification method. Appl. Stoch. Models Data Anal. 7, 63–76 (1991)MathSciNetCrossRefMATH Lerman, I.C.: Foundations of the likelihood linkage analysis (LLA) classification method. Appl. Stoch. Models Data Anal. 7, 63–76 (1991)MathSciNetCrossRefMATH
38.
Zurück zum Zitat Lerman, I.C.: Likelihood linkage analysis (LLA) classification method: an example treated by hand. Biochimie 75, 379–397 (1993)CrossRef Lerman, I.C.: Likelihood linkage analysis (LLA) classification method: an example treated by hand. Biochimie 75, 379–397 (1993)CrossRef
39.
Zurück zum Zitat Lerman, I.C.: Analyse logique, combinatoire et statistique de la construction d’une hiérarchie binaire; niveaux et noeuds significatifs. Mathématiques et Sciences Humaines, Mathematics and Social Sciences 184, 47–103 (2008) Lerman, I.C.: Analyse logique, combinatoire et statistique de la construction d’une hiérarchie binaire; niveaux et noeuds significatifs. Mathématiques et Sciences Humaines, Mathematics and Social Sciences 184, 47–103 (2008)
40.
Zurück zum Zitat Lerman, I.C., Kuntz, P.: Directed binary hierarchies and directed ultrametrics. J. Classif. 28, 272–296 (2011)MathSciNetCrossRef Lerman, I.C., Kuntz, P.: Directed binary hierarchies and directed ultrametrics. J. Classif. 28, 272–296 (2011)MathSciNetCrossRef
41.
Zurück zum Zitat Lerman, I.C., Leredde, H.: La méthode des pôles d’attraction. In: Diday, E., et al. (eds.) Journées Analyse des Données et Informatique. IRIA (1977) Lerman, I.C., Leredde, H.: La méthode des pôles d’attraction. In: Diday, E., et al. (eds.) Journées Analyse des Données et Informatique. IRIA (1977)
42.
Zurück zum Zitat Lerman, I.C., Peter, Ph.: Organisation et consultation d ’ une banque de petites annonces à partir d ’ une méthode de classification hiérarchique en parallèle. In: Data Analysis and Informatics IV, pp. 121–136. North Holland (1986) Lerman, I.C., Peter, Ph.: Organisation et consultation d ’ une banque de petites annonces à partir d ’ une méthode de classification hiérarchique en parallèle. In: Data Analysis and Informatics IV, pp. 121–136. North Holland (1986)
43.
Zurück zum Zitat Loughin, T.M.: A systematic comparison of methods for combining \(p\)-values from independent tests. Comput. Stat. Data Anal. 47, 467–485 (2004)MathSciNetCrossRefMATH Loughin, T.M.: A systematic comparison of methods for combining \(p\)-values from independent tests. Comput. Stat. Data Anal. 47, 467–485 (2004)MathSciNetCrossRefMATH
44.
Zurück zum Zitat McQuitty, L.L.: Similarity analysis by reciprocal pairs for discrete and continuous data. Educ. Psychol. Meas. 26, 825–831 (1966) McQuitty, L.L.: Similarity analysis by reciprocal pairs for discrete and continuous data. Educ. Psychol. Meas. 26, 825–831 (1966)
45.
Zurück zum Zitat McQuitty, L.L.: Elementary linkage analysis for isolating orthogonal and oblique types and typal relevancies. Educ. Psychol. Meas. 17, 207–229 (1957) McQuitty, L.L.: Elementary linkage analysis for isolating orthogonal and oblique types and typal relevancies. Educ. Psychol. Meas. 17, 207–229 (1957)
46.
Zurück zum Zitat Murtagh, F.: A survey of recent advances in hierarchical clustering. Comput. J. 26, 354–359 (1983)CrossRefMATH Murtagh, F.: A survey of recent advances in hierarchical clustering. Comput. J. 26, 354–359 (1983)CrossRefMATH
47.
Zurück zum Zitat Murtagh, F.: A survey of algorithms for contiguity constrained clustering and related problems. Comput. J. 28, 82–88 (1985)CrossRef Murtagh, F.: A survey of algorithms for contiguity constrained clustering and related problems. Comput. J. 28, 82–88 (1985)CrossRef
48.
Zurück zum Zitat Murtagh, F.: Clustering massive data sets. In: Handbook of Massive Data Sets, pp. 501–543. Kluwer Academic Publishers, Norwell (2002) Murtagh, F.: Clustering massive data sets. In: Handbook of Massive Data Sets, pp. 501–543. Kluwer Academic Publishers, Norwell (2002)
49.
Zurück zum Zitat Nicolau, F.: Criterios de análise classificatoria hierarquica baseados na funçao de distribuiçao. Ph.D. thesis, Faculty of Science of Lisboa University, Feb 1981 Nicolau, F.: Criterios de análise classificatoria hierarquica baseados na funçao de distribuiçao. Ph.D. thesis, Faculty of Science of Lisboa University, Feb 1981
51.
Zurück zum Zitat Orloci, L.: Information theory models for hierarchic and non-hierarchic classifications. In: Cole, A.J. (ed.) Numerical Taxonomy, pp. 148–164. Academic Press, New York (1968) Orloci, L.: Information theory models for hierarchic and non-hierarchic classifications. In: Cole, A.J. (ed.) Numerical Taxonomy, pp. 148–164. Academic Press, New York (1968)
52.
Zurück zum Zitat Peter, Ph.: Méthodes de classification hiérarchique et problèmes de structuration et de recherche d ’ informations assistée par ordinateur. Ph.D. thesis, Université de Rennes 1, mars 1987 Peter, Ph.: Méthodes de classification hiérarchique et problèmes de structuration et de recherche d ’ informations assistée par ordinateur. Ph.D. thesis, Université de Rennes 1, mars 1987
53.
Zurück zum Zitat Roux, M.: Deux algorithmes récents en classification automatique. Revue de Statistique Appliquée 18(4), 35–40 (1970) Roux, M.: Deux algorithmes récents en classification automatique. Revue de Statistique Appliquée 18(4), 35–40 (1970)
54.
Zurück zum Zitat Scott, A.J., Symons, M.J.: On the Edwards and Cavalli Sforza method of cluster analysis. Biometrics 27, 217–219 (1971)CrossRef Scott, A.J., Symons, M.J.: On the Edwards and Cavalli Sforza method of cluster analysis. Biometrics 27, 217–219 (1971)CrossRef
55.
Zurück zum Zitat Sneath, P.H.A.: The application of computers to taxonomy. J. Gen. Microbiol. 17, 201–226 (1957)CrossRef Sneath, P.H.A.: The application of computers to taxonomy. J. Gen. Microbiol. 17, 201–226 (1957)CrossRef
56.
Zurück zum Zitat Sneath, P.H.A., Sokal, R.R.: Numerical Taxonomy. Freeman, San Francisco (1973)MATH Sneath, P.H.A., Sokal, R.R.: Numerical Taxonomy. Freeman, San Francisco (1973)MATH
57.
Zurück zum Zitat Sokal, R.R., Michener, C.D.: A statistical method for evaluating systematic relationships. Kansas Univ. Sci. Bull. 38, 1409–1438 (1958) Sokal, R.R., Michener, C.D.: A statistical method for evaluating systematic relationships. Kansas Univ. Sci. Bull. 38, 1409–1438 (1958)
58.
Zurück zum Zitat Sorensen, T.: A method of establishing groups of equal amplitude in plant sociology based on similarity of species content. K. danske Vidensk. Selsk. Skr. (biol) 5, 1–34 (1948) Sorensen, T.: A method of establishing groups of equal amplitude in plant sociology based on similarity of species content. K. danske Vidensk. Selsk. Skr. (biol) 5, 1–34 (1948)
59.
Zurück zum Zitat Ward, J.H.: Hierarchical grouping to optimise an objective function. J. Am. Stat. Assoc. 58, 238–244 (1963)CrossRef Ward, J.H.: Hierarchical grouping to optimise an objective function. J. Am. Stat. Assoc. 58, 238–244 (1963)CrossRef
Metadaten
Titel
Building a Classification Tree
verfasst von
Israël César Lerman
Copyright-Jahr
2016
Verlag
Springer London
DOI
https://doi.org/10.1007/978-1-4471-6793-8_10