Combinatorial Data Analysis Based on Dynamic Programming

这个项目的重点是数据表示策略的发展时，可用的数据是（或已首先减少到）的形式，从一组正在研究的对象之间的数字指定的接近信息。 要强调的表示方法都涉及离散的结构模型，这些模型的基础是识别对象分组、分区或对象序列的某种最佳形式的要求。 这些基于组合的模型的拟合可以通过通用动态规划范式（GDPP）来实现，该范式允许递归优化例程的构建，以解决各种感兴趣的表示结构的基础上的各种组合任务。该研究计划将在四个广泛的主题领域开发和扩展GDPP：（a）在统计范围内对使用全球数据处理方案所获得的结果进行定位和评价;这将包括界定特定对象的诊断影响以及在确定具体的全球最佳结果时可能存在的独特性（缺乏独特性）;（B）结合待优化的拟合的替代测量;这将包括传统最小二乘损失函数的替代，以及在给定邻近信息的水平上或更早地和在进行邻近计算之前结合最优缩放;（c）超度量的形式思想的一般化，其表征由任何分级聚类技术拟合的结构;这将包括允许分层中的分区不是完美嵌套的替代方案，或者以其他方式削弱分层表示的条件但仍然允许方便的图形表示的替代方案;（d）当面对太大的对象集而不能在合理的计算限制内保证所识别的结构的绝对最优性时，评估GDPP的启发式扩展;这将包括与其他几种广泛使用的启发式组合优化方法的比较，例如迭代（局部）改进方法。

This project focuses on the development of data representation strategies when the available data are given in (or have been first reduced to) the form of numerically specified proximity information between the objects from a set under study. The representation methods to be emphasized all involve discrete structural models that have at their basis the requirement for identifying some optimal form of object grouping, partition, or object sequence. The fitting of these combinatorially based models can be approached through a general dynamic programming paradigm (GDPP) that allows the construction of recursive optimization routines to solve the wide range of combinatorial tasks that underlie the various representation structures of interest.This research program will develop and extend the GDPP in four broad topic areas: (a) the placement and evaluation of the results obtained from the use of the GDPP within a statistical context; this will include defining the diagnostic influence of particular objects and the (lack of) uniqueness that may be present in the identification of a specific globally optimal result; (b) the incorporation of alternative measures of fit to be optimized; this will include alternatives to traditional least-squares loss functions and the incorporation of optimal scaling either at the level of the given proximity information, or earlier and before the proximity calculations are taken; (c) generalizations of the formal idea of an ultrametric which characterizes the structure fitted by any hierarchical clustering technique; this will include alternatives allowing partitions in a hierarchy to be less than perfectly nested, or that weaken in other ways the condition of hierarchical representation but which still allow convenient graphical representation; (d) evaluating heuristic extensions of the GDPP when faced with object sets too large to guarantee, within reasonable computational limits, absolute optimality for the identified structures; this will include comparisons to several other widely used heuristic combinatorial optimization approaches, such as iterative (local) improvement methods.