Outlier Identification and Handling in Computational Geometry Problems

计算几何问题出现在科学和工程的所有领域，在计算机视觉，机器学习，数据挖掘，分类，数据压缩，地理信息系统，聚类和设施定位等背景下。计算几何学的进步可以带来机器人学、基因组学和蛋白质组学的进步，这三个领域是人们迫切感兴趣的。计算几何问题中越来越多的关注点是离群点，即输入数据中的点，去除这些点可以显著提高目标函数的可达最优值。最近的治疗给予关注离群值涉及相当有吸引力的方法与良好的效果，但这些都是特设的解决方案，具体到特定的问题背景和限制性的假设。从一般原则和准则中系统地推导出这些方法，并在此基础上评价和比较离群值程序，这将是可取的。然而，到目前为止，还没有系统的方法来处理计算几何问题中的异常值，也没有提出一套特定的标准来满足异常值的程序，通过计算机科学家和数学家之间的跨学科合作，本项目将开发一个异常值识别和处理方法，作为一个新的和通用的工具，计算几何。有效离群值标识符的一般性质的结构将被制定。应满足的标准和理想的质量特征将被制定。诸如离群值标识符的稳健性等问题将得到解决。将开发有效的计算算法。本计画将放宽现有方法的限制，并将著重于形状拟合与降维问题中的异常值处理。一个领先的工具将是深度函数，一个新兴的方法在nonparametricmultivariate数据分析，是有用的分布和数据集的描述和内在的支持outlyingness在数据输入点的表征。作为一个副产品，该项目也将获得深度函数方法的进展。一个提议者已经开发了计算几何中的有效算法，另一个开发了多变量数据分析中的深度和离群值方法。一个提议者共同组织，两个提议者都参加了最近NSF赞助的关于数据深度的研讨会：稳健的多变量分析，计算几何和应用（DIMACS，2003），这促进了这个研究项目的合作。这个项目的主要智力价值是通过提供一个通用的和基本的方法来代替临时的方法来处理离群值，从而推进计算机科学的基础。此外，研究结果将推动统计科学领域的非参数多元数据分析。该项目的更广泛影响包括加强计算机科学和统计科学之间的接口，以及研究生和本科生作为学术经验的一部分参与团队方法。通过其广泛的适用性，该项目的研究结果将对科学，工程和政府的许多领域具有直接和核心的相关性。项目研究员将维持一个网站，向公众公布项目结果。

OUTLIER IDENTIFICATION AND HANDLING IN COMPUTATIONAL GEOMETRYPROBLEMSComputational geometry problems arise in all areas of science and engineering, in contextssuch as computer vision, machine learning, data mining, classification, data compression,geographic information systems, clustering, and facility location. Advances in computationalgeometry can yield advances in robotics, genomics, and proteomics, to mention three areasof pressing interest.Increasing concern in computational geometry problems is being devoted to outliers,points in the input data whose removal can yield significant improvements in attainableoptimal values of objective functions. Recent treatments giving attention to outliers involvequite appealing methods with good results, but these have been ad hoc solutions, specific toparticular problem contexts and entailing restrictive assumptions. It would be desirable toderive such approaches in a systematic manner from general principles and guidelines, andto evaluate and compare outlier procedures on such a basis. To date, however, no systematicapproach for handling outliers in computational geometry problems has been set forth, norhas there been advanced a set of specific criteria to be satisfied by outlier procedures.Through interdisciplinary collaboration between a computer scientist and a statisticalscientist, this project will develop an outlier identification and handling approach as a newand versatile tool in computational geometry. Structures of a general nature for effectiveoutlier identifiers will be formulated. Criteria to be satisfied and desirable qualitative featureswill be formulated. Issues such as robustness of outlier identifiers will be addressed. Efficientcomputing algorithms will be developed. Significant restrictions on current approaches willbe relaxed.The project will focus on outlier handling in shape fitting and dimension reduction prob-lems. A leading tool will be depth functions, an emerging methodology in nonparametricmultivariate data analysis that is useful for description of distributions and data sets and in-herently supports characterization of outlyingness for points in a data input. As a byproduct,the project will obtain advances in depth function methods as well.One proposer has been developing efficient algorithms in computational geometry, theother developing depth and outlier methods in multivariate data analysis. One proposer co-organized, and both proposers participated in, the recent NSF-sponsored Workshop on DataDepth: Robust Multivariate Analysis, Computational Geometry and Applications (DIMACS,2003), which fostered the collaboration for this research project.The leading intellectual merit of this project is to advance the foundations of computerscience by providing a general and fundamental method that replaces ad hoc approaches tooutlier handling. Also, the findings will advance the field of statistical science in the area ofnonparametric multivariate data analysis.Broader impacts of the project include strengthening of the interface between computerscience and statistical science and involvement of graduate and undergraduate studentswithin a team approach as part of their academic experience. Through its wide applica-bility the findings of this project will have immediate and central relevance to many areasof science, engineering and government. The PIs will maintain a web site on which projectresults are made known and available to the public at large.