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

我们经常可以通过图表或绘图来看到数据中的趋势或集群--给数据以几何形式。随着数据量和复杂性的增加，给数据赋予几何形式，然后开发计算几何算法，仍然是处理数据分析的一种卓有成效的方法。例如，来自智能手机或健身跟踪器的活动数据可以被视为数千个维度中的一个点，其坐标包括整个测量序列的所有位置、心率等。为了更好的隐私，我们可以共享摘要(大致位置、持续时间等)。作为几十个维度上的点。来自许多人的点数可以聚集在一起，以识别相似的模式，并将模式匹配(带有识别并丢弃的不可靠数据)，以识别数字助理可以采取的行动，以提高生活质量或健康结果。该项目旨在开发一套先进的数据结构和新颖的几何算法来解决三个基本的数据分析问题：(1)高维约束聚类，(2)特定变换下的几何匹配，(3)从不可靠的数据中提取可信信息。前两个问题都是计算几何自然研究的问题，第三个问题有一种新的形式，即高维几何优化问题。我们的目标是为这些问题提供高效和有质量保证的解决方案。该项目引入的新的几何洞察力、先进的数据结构和高效的算法技术将丰富计算几何的进一步发展，并为其他领域带来新的想法，包括机器学习、计算机视觉、数据挖掘和生物信息学。该项目为密歇根州立大学的研究生和本科生(包括女性、少数族裔和其他代表性不足的群体)提供了数据分析方面的研究和教育机会。它还为K-12学生开展外展活动，并编制在线材料，使更多的学生和教师受益。特别是，学生对教师绩效的评价将是问题(3)中使用的数据集之一，从不可靠的数据中提取可靠的信息。

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.