III: Small: Fast Subset Scan for Anomalous Pattern Detection

III：小：用于异常模式检测的快速子集扫描

• 批准号: 0916345
• 负责人: Daniel Neill
• 金额: $ 50万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-08-01 至 2013-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0916345&HistoricalAwards=false
• 关键词: III; Small; Fast; Subset; Scan

This work will develop new methods for fast and scalable detection of anomalous patterns (subsets of the data that are interesting or unexpected) in massive, multivariate datasets. There will be a focus on real-world applications such as an emerging disease outbreak or a pattern of smuggling activity with complex, subtle, and probabilistic patterns that are difficult to spot with existing techniques. The research is based on two key insights. First, the pattern detection problem can be framed as a search over all subsets of the data, in which can be defined a measure of the "anomalousness" of a subset and then maximize this measure over all potentially relevant subsets. Second, it has been discovered that, for many spatial detection methods (including Kulldor's spatial scan statistic and many recently proposed variants), one can perform an exact search which efficiently maximizes the measure of anomalousness over all subsets of the data. The research team will explore this new combinatorial optimization method, investigate how it can be extended to constrained subset scans and to more general multivariate pattern detection problems, and examine how it can be incorporated into a subset scan framework, enabling the creation a variety of fast, scalable, and useful methods for anomalous pattern detection. Intellectual MeritThe research team will develop, implement, and evaluate a general probabilistic framework for efficient detection of anomalous patterns in both spatial and non-spatial datasets. The proposed work will address these challenging and important research questions:1)How can one define a useful measure of the "anomalousness" of a subset of the data, and efficiently optimize this measure over all subsets to find the most anomalous patterns?2) What are the necessary and sufficient conditions for a set function F (S ) to satisfy the "linear- time subset scanning" (LTSS) property, enabling exact unconstrained optimization of F (S ) over all 2 N subsets of N records while only requiring O(N ) subsets to be evaluated?3) How can one extend fast subset scanning methods to general multivariate datasets, and incorporate search constraints such as proximity, connectivity, and self-similarity?4) How can one deal with uncertainty about the effects of an anomalous pattern by searching over subsets of "input" and "output" attributes as well as subsets of records? Broader ImpactDevelopment and testing will be prioritized in three areas: 1) early detection of disease outbreaks, 2) detecting illicit container shipments, and 3) identifying anomalous trends in social networks. These applications will allow the demonstration the value of these methods across a wide spectrum of domains. Through existing collaborations, the algorithms will be incorporated into deployed systems for health and crime surveillance that contribute directly to the public good. The Principle Investigator's lab has over 5 years of history offering free machine learning software, and the software implementations of all algorithms developed through this grant will be made publicly available. The bulk of the funding will go to training graduate students who will become the next generation of researchers to explore new methods for anomalous pattern detection. Key Words: anomalous patterns; pattern detection; fast subset scan; scan statistics; optimization.

这项工作将开发新的方法，用于快速和可扩展地检测大规模多变量数据集中的异常模式（有趣或意外的数据子集）。将重点关注现实世界的应用，例如新出现的疾病爆发或具有复杂，微妙和概率模式的走私活动模式，这些模式很难用现有技术发现。这项研究基于两个关键的见解。首先，模式检测问题可以被定义为在数据的所有子集上的搜索，其中可以定义子集的“不确定性”的度量，然后在所有潜在相关子集上最大化该度量。其次，已经发现，对于许多空间检测方法（包括Kulldor的空间扫描统计和许多最近提出的变体），可以执行精确搜索，其有效地最大化所有数据子集上的不确定性的测量。研究团队将探索这种新的组合优化方法，研究如何将其扩展到受约束的子集扫描和更一般的多元模式检测问题，并研究如何将其纳入子集扫描框架，从而创建各种快速，可扩展和有用的异常模式检测方法。该研究小组将开发，实施和评估一个通用的概率框架，用于有效检测空间和非空间数据集中的异常模式。所提出的工作将解决这些具有挑战性和重要的研究问题：1）如何定义一个有用的测量数据的一个子集的“异常性”，并有效地优化这个措施在所有子集，以找到最异常的模式？2)什么是集合函数F（S）满足“线性时间子集扫描”（LTSS）性质的必要和充分条件，使F（S）在N个记录的所有2N个子集上精确无约束优化，同时只需要O（N）个子集被评估？3)如何将快速子集扫描方法扩展到一般的多变量数据集，并结合搜索约束，如邻近性，连通性和自相似性？4)如何通过搜索“输入”和“输出”属性的子集以及记录的子集来处理异常模式影响的不确定性？更广泛的影响开发和测试将优先考虑三个领域：1）早期发现疾病爆发，2）发现非法集装箱运输，3）识别社交网络中的异常趋势。这些应用程序将允许演示这些方法在广泛领域的价值。通过现有的合作，这些算法将被纳入已部署的健康和犯罪监测系统，直接为公共利益做出贡献。首席研究员的实验室有超过5年的历史，提供免费的机器学习软件，并通过此赠款开发的所有算法的软件实现将公开提供。大部分资金将用于培训研究生，他们将成为下一代研究人员，探索异常模式检测的新方法。关键词：异常模式;模式检测;快速子集扫描;扫描统计;优化。