III: Small: Collaborative Research: Finding and Exploiting Hierarchical Structure in Time Series Using Statistical Language Processing Methods

III：小：协作研究：使用统计语言处理方法查找和利用时间序列中的层次结构

• 批准号: 1218325
• 负责人: Jessica Lin
• 金额: $ 25万
• 依托单位: George Mason University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-09-01 至 2016-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1218325&HistoricalAwards=false
• 关键词: III; Small; Collaborative; Research; Finding

Applications as diverse as manufacturing, medicine, earth science, finance, and entomology generate massive amounts of temporal or spatio-temporal data. More specifically, information about moving objects, events, and atmospheric measurements that are geo-referenced may be derived from high-resolution satellites, sensors, ground and aerial imagery, GPS, and RFID. Such data present challenges to current approaches for mining time series data. For example, shape-based similarity measures used for classification and clustering consistently fail to produce satisfactory results for long sequences, or trajectories modeling objects that move in 2D or 3D space which may often exhibit similar motion patterns but differ in locations and orientations. In addition, algorithms for finding frequent patterns and anomalies assume known, fixed pattern lengths. This project aims to address the limitations of current approaches to time series data analysis by adapting statistical language processing algorithms and approaches. Specifically, fast algorithms for learning context-free grammars can expose hierarchical structure in time series and thus enable efficient discovery of variable length patterns and facilitate human understanding of time series structure. Also, using the hierarchy to populate a "bag of patterns" can result in significantly more effective similarity measures for long time series, much like the familiar bag of words representation used with documents is effective for a variety of similarity-based language processing tasks on massive corpora.Given the ubiquitous nature of time series data, advances in algorithms that can help uncover the structure of such data are likely to impact a broad range of applications. All of the results of this research, including publications, algorithms and software, would be made freely available to the broader research and educational community. The project offers enhanced research-based training opportunities for graduate and undergraduate students. The project leverages existing programs at George Mason University and the University of Maryland at Baltimore County to to increase the participation of women members of other groups that are under-represented in Computer Science.

制造、医学、地球科学、金融和昆虫学等各种应用产生了大量的时间或时空数据。更具体地说，可以从高分辨率卫星、传感器、地面和航空图像、GPS和RFID获得关于移动物体、事件和大气测量的地理参考信息。这些数据对当前挖掘时间序列数据的方法提出了挑战。例如，用于分类和聚类的基于形状的相似性测量始终不能对长序列产生令人满意的结果，或者对在2D或3D空间中移动的对象进行轨迹建模，这些对象可能经常表现出相似的运动模式，但在位置和方向上不同。此外，用于发现频繁模式和异常的算法假定已知的固定模式长度。该项目旨在通过采用统计语言处理算法和方法来解决目前时间序列数据分析方法的局限性。具体地说，学习上下文无关文法的快速算法可以揭示时间序列中的层次结构，从而能够有效地发现可变长度模式，促进人类对时间序列结构的理解。此外，使用层次结构填充“模式包”可以为长时间序列带来明显更有效的相似性度量，就像文档中使用的熟悉的词包表示对于大规模语料库上的各种基于相似性的语言处理任务是有效的一样。鉴于时间序列数据的无处不在的性质，能够帮助揭示此类数据结构的算法的进步可能会影响广泛的应用。这项研究的所有成果，包括出版物、算法和软件，都将免费提供给更广泛的研究和教育界。该项目为研究生和本科生提供了更多基于研究的培训机会。该项目利用乔治梅森大学和马里兰大学巴尔的摩县分校的现有项目，以增加在计算机科学领域代表性不足的其他群体的女性成员的参与。