Mining Subgroups with Exceptional Transition Behavior
Mining Subgroups with Exceptional Transition Behavior
复制标题
DOI：
10.1145/2939672.2939752
复制
发表时间：
2016-08
期刊：
影响因子：
--
通讯作者：
F. Lemmerich;Martin Becker;Philipp Singer;D. Helic;A. Hotho;M. Strohmaier
中科院分区：
文献类型：
--
作者：
F. Lemmerich;Martin Becker;Philipp Singer;D. Helic;A. Hotho;M. Strohmaier
本文提出了一种新的方法来检测序列数据中具有异常迁移行为的可解释子群。识别这种模式具有许多潜在的应用，例如，用于研究人类移动性或分析互联网用户的行为。为了解决这一任务，我们采用异常模型挖掘，这是一种通用的方法，用于识别可解释的数据子集，这些数据子集表现出一组目标属性之间的不寻常的相互作用，相对于某个模型类。虽然异常模型挖掘为我们的问题提供了一个非常适合的框架，以前研究的模型类不能捕捉过渡行为。为此，我们引入了一阶马尔可夫链作为一种新的模型类异常模型挖掘，并提出了一个新的兴趣度量，量化的过渡子群的异常性。该度量将子组的马尔可夫转移矩阵与整个数据的相应矩阵之间的距离与随机数据集样本的距离进行比较。此外，我们的方法可以适用于找到子组匹配或矛盾给定的过渡假设。我们证明，我们的方法是一贯能够恢复特殊的过渡模型从合成数据的子群，并说明其潜力在两个应用程序中的例子。我们的工作是相关的研究人员和从业人员有兴趣在检测异常过渡行为的序列数据。
We present a new method for detecting interpretable subgroups with exceptional transition behavior in sequential data. Identifying such patterns has many potential applications, e.g., for studying human mobility or analyzing the behavior of internet users. To tackle this task, we employ exceptional model mining, which is a general approach for identifying interpretable data subsets that exhibit unusual interactions between a set of target attributes with respect to a certain model class. Although exceptional model mining provides a well-suited framework for our problem, previously investigated model classes cannot capture transition behavior. To that end, we introduce first-order Markov chains as a novel model class for exceptional model mining and present a new interestingness measure that quantifies the exceptionality of transition subgroups. The measure compares the distance between the Markov transition matrix of a subgroup and the respective matrix of the entire data with the distance of random dataset samples. In addition, our method can be adapted to find subgroups that match or contradict given transition hypotheses. We demonstrate that our method is consistently able to recover subgroups with exceptional transition models from synthetic data and illustrate its potential in two application examples. Our work is relevant for researchers and practitioners interested in detecting exceptional transition behavior in sequential data.