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.