NTRS - NASA Technical Reports Server

As of October 27, 2023, NASA STI Services will no longer have an embargo for accepted manuscripts. For more information visit NTRS News.

Back to Results
Interpretable Categorization of Heterogeneous Time Series DataWe analyze data from simulated aircraft encounters to validate and inform the development of a prototype aircraft collision avoidance system. The high-dimensional and heterogeneous time series dataset is analyzed to discover properties of near mid-air collisions (NMACs) and categorize the NMAC encounters. Domain experts use these properties to better organize and understand NMAC occurrences. Existing solutions either are not capable of handling high-dimensional and heterogeneous time series datasets or do not provide explanations that are interpretable by a domain expert. The latter is critical to the acceptance and deployment of safety-critical systems. To address this gap, we propose grammar-based decision trees along with a learning algorithm. Our approach extends decision trees with a grammar framework for classifying heterogeneous time series data. A context-free grammar is used to derive decision expressions that are interpretable, application-specific, and support heterogeneous data types. In addition to classification, we show how grammar-based decision trees can also be used for categorization, which is a combination of clustering and generating interpretable explanations for each cluster. We apply grammar-based decision trees to a simulated aircraft encounter dataset and evaluate the performance of four variants of our learning algorithm. The best algorithm is used to analyze and categorize near mid-air collisions in the aircraft encounter dataset. We describe each discovered category in detail and discuss its relevance to aircraft collision avoidance.
Document ID
Document Type
Conference Paper
Lee, Ritchie
(Carnegie-Mellon Univ. Moffett Field, CA, United States)
Kochenderfer, Mykel J.
(Stanford Univ. Stanford, CA, United States)
Mengshoel, Ole J.
(Carnegie-Mellon Univ. Moffett Field, CA, United States)
Silbermann, Joshua
(Johns Hopkins Univ. Laurel, MD, United States)
Date Acquired
October 11, 2017
Publication Date
August 14, 2017
Subject Category
Systems Analysis And Operations Research
Air Transportation And Safety
Report/Patent Number
Meeting Information
Meeting: Knowledge Discovery, Data Mining, and Data Science Research (KDD ''17)
Location: Halifax, NS
Country: Canada
Start Date: August 14, 2017
End Date: August 17, 2017
Sponsors: Association for Computing Machinery
Funding Number(s)
Distribution Limits
Public Use Permitted.
Time Series Analysis
No Preview Available