组合数据分析 : 通过动态规划进行优化

preface

1 introduction

2 general dynamic programming paradigm

2.1 an introductory example: linear assignment

2.2 the gdpp

3 cluster analysis

3.1 partitioning

3.1.1 admissibility restrictions on partitions

3.1.2 partitioning based on two-mode proximity matrices

3.2 hierarchical clustering

3.2.1 hierarchical clustering and the optimal fitting of

ultrametrics

3.2.2 constrained hierarchical clustering

4 object sequencing and seriation

4.1 optimal sequencing of a single object set

4.1.1 symmetric one-mode proximity matrices

preface

1 introduction

2 general dynamic programming paradigm

2.1 an introductory example: linear assignment

2.2 the gdpp

3 cluster analysis

3.1 partitioning

3.1.1 admissibility restrictions on partitions

3.1.2 partitioning based on two-mode proximity matrices

3.2 hierarchical clustering

3.2.1 hierarchical clustering and the optimal fitting of

ultrametrics

3.2.2 constrained hierarchical clustering

4 object sequencing and seriation

4.1 optimal sequencing of a single object set

4.1.1 symmetric one-mode proximity matrices

4.1.2 skew-symmetric one-mode proximity matrices

4.1.3 two-mode proximity matrices

4.1.4 object sequencing for symmetric one-mode proximity matrices

based on the construction of optimal paths

4.2 sequencing an object set subject to precedence

constraints

4.3 construction of optimal ordered partitions

5 heuristic applications of the gdpp

5.1 cluster analysis

5.2 object sequencing and seriation

6 extensions and generalizations

6.1 introduction

6.1.1 multiple data sources

6.1.2 multiple structures

6.1.3 uses for the information in the sets ω1,...,ωk

6.1.4 a priori weights for objects and/or proximities

6.2 prospects

appendix: available programs

bibliography

author index

subject index

combinatorial data analysis (cda) refers to a wide class of
methods for the study of relevant data sets in which the
arrangement of a collection of objects is absolutely central.
combinatorial data analysis: optimization by dynamic programming
focuses on the identification of arrangements, which are then
further restricted to where the combinatorial search is carried out
by a recursive optimization process based on the general principles
of dynamic programming (dp).
the authors provide a comprehensive and self-contained review
delineating a very general dp paradigm, or schema, that can serve
two functions. first, the paradigm can be applied in various
special forms to encompass all previously proposed applications
suggested in the classification literature. second, the paradigm
can lead directly to many more novel uses. an appendix is included
as a user's manual for a collection of programs available as
freeware.
the incorporation of a wide variety of cda tasks under one common
optimization framework based on dp is one of this book's strongest
points. the authors include verifiably optimal solutions to
nontrivially sized problems over the array of data analysis tasks
discussed.
this monograph provides an applied documentation source, as well as
an introduction to a collection of associated computer programs,
that will be of interest to applied statisticians and data analysts
as well as notationally sophisticated users.