Hyperbolic Classification and Regression Trees

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

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.