Outlier Identification and Handling in Computational Geometry Problems

计算几何问题中的异常值识别和处理

• 批准号: 0430366
• 负责人: Ovidiu Daescu
• 金额: --
• 依托单位: University of Texas at Dallas
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-08-15 至 2006-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0430366&HistoricalAwards=false
• 关键词: Outlier; Identification; Handling; Computational; Geometry

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.

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