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

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

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.