Outlier Identification and Handling in Computational Geometry Problems

计算几何问题在计算机视觉、机器学习、数据挖掘、分类、数据压缩、地理信息系统、集群和设施选址等所有科学和工程领域中都会出现计算几何问题。计算几何的进步可以带来机器人学、基因组学和蛋白质组学的进步，这三个领域是人们最感兴趣的。计算几何问题中越来越多的人关注孤立点，即输入数据中的异常值，去除这些孤立点可以显著改善目标函数的可达最优值。最近关注离群值的治疗方法都很吸引人，效果很好，但这些都是临时的解决方案，具体的局部问题背景和限制性的假设。最好是以系统的方式从一般原则和准则中得出这些办法，并在此基础上评价和比较异常程序。然而，到目前为止，还没有系统的方法来处理计算几何问题中的离群点，也没有提出一套特定的标准来满足离群点过程。通过计算机科学家和统计科学家之间的跨学科合作，这个项目将开发一种离群点识别和处理方法，作为计算几何中一种新的通用工具。将制定有效离群点标识符的一般性质的结构。将制定要满足的标准和所需的质量特征。将解决离群值识别符的稳健性等问题。将开发高效的计算算法。对现有方法的重大限制将被放宽。该项目将专注于形状拟合和降维问题中的离群值处理。深度函数将是一个领先的工具，这是非参数多元数据分析中的一种新兴方法，有助于描述分布和数据集，并内在地支持数据输入中点的异常特征的表征。作为副产品，该项目还将在深度函数方法方面取得进展。其中一个提出者一直在开发计算几何中的高效算法，另一个提出者正在开发多元数据分析中的深度和离群值方法。一个提出者和两个提出者都参加了最近由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.