Combinatorial Data Analysis Based on Dynamic Programming

本项目的重点是当现有数据以(或首先被简化为)所研究的一组对象之间的数字指定的邻近信息的形式给出时，制定数据表示策略。要强调的表示方法都涉及离散结构模型，其基础是识别对象分组、划分或对象序列的某种最佳形式的要求。这些基于组合的模型的拟合可以通过通用动态规划范例(GDPP)来实现，该范例允许构建递归优化例程以解决作为各种兴趣表示结构基础的广泛的组合任务。该研究计划将在四个广泛的主题领域开发和扩展GDPP：(A)在统计环境中放置和评估通过使用GDPP获得的结果；这将包括定义特定对象的诊断影响以及在识别特定的全局最优结果时可能存在的唯一性；(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.