CRII: AF: Novel Geometric Algorithms for Certain Data Analysis Problems

CRII：AF：针对某些数据分析问题的新颖几何算法

基本信息

批准号：
1656905
负责人：
Eric Torng
金额：
$ 17.43万
依托单位：
Michigan State University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2017
资助国家：
美国
起止时间：
2017-05-15 至 2019-04-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1656905&HistoricalAwards=false
关键词：
CRII AF Novel Geometric Algorithms

项目摘要

We can often see trends or clusters in data by graphing or plotting-- giving geometric form to data. As data increases in volume and complexity, giving it geometric form and then developing computational geometry algorithms is still a fruitful way to approach data analysis. For example, activity data from a smartphone or fitness tracker can be viewed as a point in thousands of dimensions whose coordinates include all positions, heart rates, etc. from an entire sequence of measurements. For better privacy, we can share summaries (rough position, duration, etc.) as points in tens of dimensions. Points from many people can be clustered to identify similar patterns, and patterns matched (with unreliable data identified and discarded) to recognize actions that a digital assistant could take to improve quality of life or health outcomes. This project aims to develop a set of advanced data structures and novel geometric algorithms for three fundamental data analysis problems: (1) constrained clustering in high dimensions, (2) geometric matching under certain transformations, and (3) extracting trustworthy information from unreliable data. The first two problems are both naturally studied by computational geometry, and the third has a novel formulation as a geometric optimization problem in high dimensions. The goal is to achieve highly efficient and quality guaranteed solutions for each of these problems. The new geometric insights, advanced data structures, and efficient algorithmic techniques introduced by this project will enrich further development in computational geometry and bring fresh ideas to other areas, including machine learning, computer vision, data mining, and bioinformatics. This project provides research and educational opportunities in data analysis to both graduate and undergraduate students (including women, minorities, and other underrepresented groups) at Michigan State University. It also undertakes outreach activities for students in K-12 outreach activities and prepares online materials to benefit more students and teachers. In particular, student evaluations of teacher performance will be one of the data sets used in problem (3), extracting trustworthy information from unreliable data.

我们通常可以通过绘制或绘图来看到数据中数据中的趋势或簇 - 为数据提供几何形式。随着数据的增加和复杂性的增加，给出几何形式，然后开发计算几何算法仍然是对数据分析的富有成果的方法。例如，来自智能手机或健身追踪器的活动数据可以被视为数千个维度的点，其坐标包括所有位置，心率等。为了获得更好的隐私，我们可以将摘要（粗糙的位置，持续时间等）作为数十个维度分享。可以聚集许多人的要点以识别类似的模式，并且模式与数字助手可以采取的行动相匹配（不可靠的数据和丢弃），以改善生活质量或健康成果。该项目旨在为三个基本数据分析问题开发一组高级数据结构和新颖的几何算法：（1）在高维度中受约束的聚类，（2）在某些转换下进行几何匹配，以及（3）从不可靠的数据中提取值得信赖的信息。前两个问题都是通过计算几何形状自然研究的，第三个问题具有新颖的表述，作为在高维度中的几何优化问题。目的是为每个问题实现高效和质量保证的解决方案。该项目介绍的新几何见解，高级数据结构以及有效的算法技术将丰富计算几何学的进一步发展，并将新的想法带入其他领域，包括机器学习，计算机视觉，数据挖掘和生物信息学。该项目为密歇根州立大学的研究生和本科生（包括妇女，少数民族和其他代表性不足的群体）提供研究和教育机会。它还为K-12外展活动中的学生开展外展活动，并准备在线材料，以使更多的学生和老师受益。特别是，学生对教师表现的评估将是问题（3）中使用的数据集之一，从不可靠的数据中提取可信赖的信息。