Trees and Proximity Representations

Name: Trees and Proximity Representations
Price: 1500.00 HUF
Availability: InStock
Author: Jean-Pierre Barthelemy
ISBN: 0471922633

Jean-Pierre Barthelemy, Alain Guenoche - Trees and Proximity Representations, Baffins Lane, Chichester 1991 antikvár könyv

(0 vélemény)

Antikvár könyv

1 500 Ft

3 000 Ft

50%

Állapot

Készleten

Jó

Központi raktár

Kedvezményes

Volt könyvtári példány.

hűségpont

Hogy működik az alku?

Describes the combinatorial analysis of data using trees as the model, and the use of this model in representing proximities. This technique is of great importance in many applications including such fields as computer science, decision theory, artificial intelligence, information theory, experimental sciences and social sciences. At each stage algorithms are provided as well as ready-to-use computer programs, written in Basic.

Mutass kevesebbet

Bővebb leírás

ISBN:	0471922633
Kiadó:	John Wiley & Sons
Kiadás éve:	1991
Kiadás helye:	Baffins Lane, Chichester
Kötés típusa:	egészvászon kiadói borítóban
Terjedelem:	238
Fordítók:	Gregor Lawden
Nyelv:	angol
Méret:	Szélesség: 17.00 cm, Magasság: 24.00 cm
Súly:	0.00 kg
Kategória:	Idegennyelv / Nyelvek / Angol / Műszaki / Számítástechnika, Informatika

Ajánlja ismerőseinek is!

Kívánságlistára teszem ezt a könyvet!

Megnézem a tartalomjegyzéket!

     Preface                                                                        xi 
     Introduction                                                                   xv

1    Trees                                                                          1
     1.1   Terminology of graph thcory                                              1
           1.1.1 Graphs                                                             1
           1.1.2 Trees                                                              3
           1.1.3 Coding and representation of trees                                 6
           1.1.4 Minimal spanning tree in a valued graph                            9
           1.1.5 Construction of a minimal spanning tree                            10
     1.9   The concept of X-tree                                                    12
           1.2.1 The concept of X-trees. Sonie examples                             12
           1.2.2 Definition of an X-tree                                            15
           1.2.3 Enumeration of X-trees                                             16
           1.2.4 Random selection of X-trees                                        19
           1.2.5 Rooted X-trees and hierarchical trees                              22
           1.2.6 Valued X-trees and dendrograms                                     23
           1.2.7 Tree drawing                                                       23
     1.3   Bibliographical notes                                                    31
           1.3.1 Graphs and trees                                                   31
           1.3.2 X-trees and hierarchic.<-11 trees                                  33
           1.3.3 Some remarks on X-trees                                            34
     1.4   References                                                               35

2 Tree distances                                                                    39
     2.1 Proximity measures and their representations                               40
           2.1.1 Remarks on proxinnty measures                                      40
           2.1.2 Pseudo distances and distances. Representations                    41
     2.2 Our data and their acquisition                                             45
           2.2.1 The experimental data                                              45
           2.2.2 Acquisition of data                                                46
     2.3 Tree distances                                                             49
           2.3.1 Additive distances on trees and tree distances                     49
           2.3.2 The four-point condition                                           52
           2.3.3 Tree distances and X-trees. The uniqueness problem                 54
     2.4 Coding of tree distances and degrees of freedom                            56


        2.4.1 Posing the problem                                   56
        2.4.2 The median of three trce vertices                    57
        2.4.3 The diagonal order and the optimal diagonal code     58
   2.5 Approximation by a tree distance: least squares             60
        2.5.1 Mathematical prograrruning methods                   60
        2.5.2 Quadratic approximation on a support tree            62
   2.6 Three heuristic methods                                     66
        2.6.1 Quadruple reduction method                           66
        2.6.2 Method of closest predecessors                       70
        2.6.3 Method of dispersion                                 73
        2.6.4 Applications to Hen.ley's data                       75
   2.7  Bibliographical notes                                      76
        2.7.1 Proximity measures and Euclidean representations     76
        2.7.2 Tree distances                                       77
        2.7.3 Concerning the diagonal code                         82
   2.8 References                                                  83

3 Ultrametric and centroid distances                               87
   3.1  Centroid distances                                         87
        3.1.1 Definition and characterisation                      87
        3.1.2 Some properties of centroid distances                89
        3.1.3 Approximation by a centroid distance                 89
   3.2  Ultrametrics                                               90
        3.2.1 Definition and characterisation of ultrametrics      91
        3.2.2 Ultrametrics and hierarchical classifications        93
        3.2.3 Drawing a dendrogram to represent an ultrametric     95
        3.2.4 Ultrametrics and Euchdean distances                  96
        3.2.5 Minimal spanning trees and ultrametrics              97
        3.2.6 Connected components of threshold graphs             99
        3.2.7 Algorithms for constructing ultrametrics: Single, complete,
             average linkages                                      101
        3.2.8 Program for ascending hierarchical classification    104
        3.2.9 Approximation of a distance index by an ultrametric  109
   3.3 Tree distances, centroid distances and ultrametrics         112
        3.3.1 Decomposition of a tree distance into the sum of a centroid
             distance and an ultrametric                           112
        3.3.2 Some remarks                                         116
        3.3.3 Use of (r,k)-decompositions to construct the valued tree
             representing a tree distance (Brossier)               118
   3.4 Approximation by a tree distance using (r,k)-decompositions 119
        3.4.1 Least squares method                                 119
        3.4.2 A heuristic method: method of decomposition          119
        3.4.3 Henley's data                                        121
   3.5  Bibliographical notes                                      122


         3.5.1 Centroid distances                                            122
         3.5.2 Ultrametrics                                                  123
         3.5.3 Ascending hierarchical classification algorithms (AHC)        125
         3.5.4 Approximation by an ultrametric                               125
         3.5.5 Centroid distances, ultrametrics, tree distances and
              Euclidean distances                                            126
         3.5.6 Decompositions of a tree distance                             126
         3.5.7 The complexity of the problem of approximating a
              dissimilarity by an ultrametric or by a centroid distance      127
   3.6 References                                                            129

4 X-tree topology; scores and groupings                                      133
   4.1 Trees and relations                                                   134
         4.1.1 The fundamental relation in an X-tree                         134
         4.1.2 The case of free, separated X-trees                           137
         4.1.3 Equivalence of X-trees                                        138
   4.2 Scores and groupings                                                  140
         4.2.1 Groupings and pregroupings relative to a 2-relation           140
         4.2.2 Properties of groupings                                       141
         4.2.3 The concept of score                                          142
         4.2.4 Reconstructing a tree                                         143
   4.3 Proximities and 2-relations. Grouping algorithms                      147
         4.3.1 The 2-relation associated with a pseudo distance index        147
         4.3.2 Regrouping algorithms                                         149
         4.3.3 The ADDTREE method of Sattah and Tversky (1977)               149
         4.3.4 The method of groupings                                       151
         4.3.5 Henley's data                                                 156
   4.4 The scores theorem                                                    157
         4.4.1 Reinterpretation of the concept of score and a generalisation 157
         4.4.2 Arithmetic of scores                                          161
         4.4.3 The scores theorem                                            164
   4.5 Bibliographical notes                                                 166
         4.5.1 The fundamental relation in an X-trce                         166
         4.5.2 The concept of grouping                                       167
         4.5.3 The scores theorem                                            168
   4.6 References                                                            168

5 Combinatorial description of X-trees                                       171
   5.1 Global description. Buneman's theory                                  171
         5.1.1 Trees and splits                                              171
         5.1.2 The graph associated with a complemented family               173
         5.1.3 Some examples                                                 176
         5.1.4 Buneman fainilies                                             179
         5.1.5 The equivalence of an X-tree and a Buneman family             181


         5.1.6 Binary variables                                          183
         5.1.7 Archaeological data                                       187
         5.1.8 Enumeration of localisations, construction of G(E)        188
   5.2 Some applications of Buneman's construction                       192
         5.2.1 Reinterpretation of tree distances                        192
         5.2.2 Every tree distance is the square of a Euclidean distance 194
         5.2.3 An ordering of X-trees. The concept of compatibility      194
   5.3 Tree analysis of a set of binary variables                        196
         5.3.1 Recognition of Buneman families and tree decomposition    196
         5.3.2 Tree analysis algorithms                                  200
   5.4 Local study: four-point configurations                            205
         5.4.1 Local study of X-trees                                    205
         5.4.2 Restrictions and configurations                           206
         5.4.3 The 2-relation associated with a complemented family      208
         5.4.4 Local characterisation of Buneman families                209
   5.5 Qualitative invariance                                            211
         5.5.1 Preliminary remarks                                       211
         5.5.2 Invariance and stability                                  212
         5.5.3 The case of tree pseudo distances                         213
   5.6 Bibliographical notes                                             216
         5.6.1 Buneman theory                                            216
         5.6.2 Consequences of Buneman's theory                          217
         5.6.3 Analysis of 0/1 variables                                 217
         5.6.4 Local description: meaningfulness: non-metric algorithms  218
   5.7 References                                                        219

6 Instead of an ending                                                   221
   6.1 Comparison of algorithms                                          221
         6.1.1 Comparison criteria                                       222
         6.1.2 Results                                                   224
         6.1.3 Commentary                                                225
   6.2 Rectangular array data                                            227
         6.2.1 Problem formulation                                       227
         6.2.2 Characterisation of rectangular tree pseudo distances     228
         6.2.3 Algorithms                                                228
   6.3 Some other types of data and representations                      229
         6.3.1 Asymmetric proximities                                    229
         6.3.2 Cubical proximities                                       230
         6.3.3 Generalised trees                                         231
   6.4 References                                                        231

   Index                                                                 233