Hyperbolic Classification and Regression Trees

双曲分类和回归树

• 批准号: 0442178
• 负责人: Robert Grossman
• 金额: --
• 依托单位: University of Illinois at Chicago
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-09-15 至 2006-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0442178&HistoricalAwards=false
• 关键词: Hyperbolic; Classification; Regression; Trees

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.

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