III: Small: Fast Subset Scan for Anomalous Pattern Detection

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

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.