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) 性质的必要和充分条件是什么，从而能够在 N 条记录的所有 2 N 个子集上实现 F (S ) 的精确无约束优化，同时只需要要评估的 O(N ) 个子集？3) 如何将快速子集扫描方法扩展到一般多元数据集，并纳入邻近性、连通性和自相似性等搜索约束？4) 如何处理影响的不确定性通过搜索“输入”和“输出”属性的子集以及记录的子集来发现异常模式？更广泛的影响开发和测试将优先考虑三个领域：1）疾病爆发的早期检测，2）检测非法集装箱运输，3）识别社交网络中的异常趋势。这些应用将允许在广泛的领域展示这些方法的价值。通过现有的合作，这些算法将被纳入已部署的健康和犯罪监测系统中，直接为公共利益做出贡献。原理研究员的实验室拥有超过 5 年提供免费机器学习软件的历史，通过这笔资助开发的所有算法的软件实现都将公开。大部分资金将用于培训研究生，他们将成为下一代研究人员，探索异常模式检测的新方法。关键词：异常模式；模式检测；快速子集扫描；扫描统计；优化。