Hyperbolic Classification and Regression Trees

基于树的分类算法已被证明对广泛的数据挖掘应用非常有用，但对于非常大的数据集或非常高维的数据集，它们的性能有时会受到影响。在这些情况下，有两个基本挑战需要克服：第一，随着属性空间的维数增加，数据点的稀疏性急剧增加。其次，随着属性空间的维度数目的增加，标准欧几里得度量对于许多实际感兴趣的问题变得不那么相关。基于树的分类器可以看作是将特征空间分解成n维矩形。如果我们认为这些立方体隐含地基于欧几里得距离函数，那么考虑基于其他距离函数将特征空间分解成n维矩形是很自然的，例如在双曲几何中出现的那些。在本研究中，研究者利用这一原理开发了基于树的分类算法和基于双曲距离函数的聚类算法。他开发了新的方法，用于将基于树的分类器和其他基于分区的分类方法扩展到非常大的数据集和非常大维度的数据集。在实际应用中，由于目前的网络协议难以在广域网上传输高带宽延迟产品的大容量数据流，限制了对大容量数据流的分类算法的应用。为了克服这一点，研究人员开发了适用于大容量数据流的双曲线聚类和分类算法的版本，方法是将这些算法分层在他的实验室专门为具有高带宽延迟产品的广域网络开发的新的应用层网络协议上。根据陆军的一份报告，可行动情报的目标是通过以快速、准确和及时的方式为指挥官和士兵提供高水平的态势了解，从而使他们有能力进行成功的行动。实现这一点的一项重要技术是能够对源自世界任何地方的大容量数据流进行实时分类、集成和路由。由于数据量巨大，今天的数据挖掘算法很难扩展到感兴趣的数据集。今天的大多数数据挖掘都是使用欧几里得度量完成的，尽管也可以使用许多其他度量。为了开发可伸缩性极强的数据挖掘算法，研究者开发了基于双曲度量的新数据挖掘算法。由于当今许多网络的容量有限，数据挖掘应用程序很难在远距离处理非常大的数据集。利用他实验室最近开发的非常高性能的网络协议，他开发了用于高性能网络的数据挖掘应用程序，这些应用程序对甚至非常大的数据集都是有效的。他正在准备这些算法的开源实现，以便学生和其他感兴趣的团体可以很容易地使用它们。该奖项由NSF和情报社区共同支持。数学和物理科学局的反恐办法方案支持基础研究和劳动力发展方面的新概念，有可能对国家安全作出贡献。

Tree-based classification algorithms have proven very useful for a wide variety of data mining applications, but their performance sometimes suffers for very large data sets or data sets in very high dimensions. There are two fundamental challenges to overcome in these situations: First, as the number of dimensions of the attribute space increases, the sparseness of the data points increases dramatically. Second, as the number of dimensions of the attribute space increases, the standard Euclidian metric becomes less relevant for many problems of practical interest. Tree-based classifiers can be viewed as decomposing feature space into n-dimensional rectangles. If we view these cubes as being based implicitly on a Euclidean distance function, it becomes natural to consider decomposing feature space into n-dimensional rectangles based upon other distance functions, such as those that arise in hyperbolic geometry. In this research, the investigator uses this principle to develop tree-based classification algorithms and clustering algorithms based upon hyperbolic distance functions. He develops novel methods for scaling tree-based classifiers and other partition-based classification methods to very large data sets and to data sets in very large dimensions. In practice, applying classification algorithms to high volume data streams is limited by the difficulty that current network protocols have transporting high volume data flows over wide area networks with high bandwidth delay products. To overcome this, the investigator develops versions of hyperbolic clustering and classification algorithms suitable for high volume data streams by layering these algorithms over a new application layer network protocol developed in his laboratory specifically for wide area networks with high bandwidth delay products. According to an Army report, the goal of actionable intelligence is to give commanders and soldiers the ability to conduct successful operations by providing them with a high level of situational understanding in a manner that is rapid, accurate, and timely. An important enabling technology for this is the ability to classify, integrate, and route high volume data streams in real time that originate anywhere in the world. Because of the volume of the data, today's data mining algorithms have trouble scaling to the data sets of interest. Most data mining today is done using Euclidean metrics, although there are many other metrics that might be used. The investigator develops new data mining algorithms based upon hyperbolic metrics in order to develop extremely scalable data mining algorithms. Because of the limited capacities of many of today's networks, data mining applications have difficulty working with very large data sets over long distances. Using recent work in his laboratory which developed very high performance network protocols, he develops data mining applications for high performance networks which are effective with even very large data sets. He is preparing open source implementations of these algorithms so that they may be easily used by students and other interested parties.This award is supported jointly by the NSF and the Intelligence Community. The Approaches to Terrorism program in the Directorate for Mathematics and Physical Sciences supports new concepts in basic research and workforce development with the potential to contribute to national security.