Infominer: mining surprising periodic patterns
Infominer: mining surprising periodic patterns
复制标题
DOI：
10.1145/502512.502571
复制
发表时间：
2001-08
期刊：
影响因子：
--
通讯作者：
Jiong Yang;Wei Wang;Philip S. Yu
中科院分区：
文献类型：
--
作者：
Jiong Yang;Wei Wang;Philip S. Yu
在本文中，我们专注于挖掘一系列事件中令人惊讶的周期性模式。在许多应用中，例如计算生物学，如果一个不常见的模式的实际出现频率大大超出了先前的预期，那么它仍然被认为是非常重要的。传统的度量（例如支持度）不一定是衡量这种令人惊讶的模式的理想模型，因为它平等地对待所有模式，即每次发生的情况对于评估模式的重要性都具有相同的权重，而不管发生的概率如何。引入更合适的测量信息，以自然地评估模式每次出现的意外程度，作为其出现概率的连续且单调递减的函数。这将允许无缝处理出现概率截然不同的模式。作为模式所有重复的意外程度的累积，提出了信息增益的概念来衡量数据序列内模式的整体意外程度。确定有界信息增益性质是为了解决信息增益测度违反向下封闭性质所带来的困境，进而为该问题提供了有效的解决方案。实证测试证明了所提出模型的效率和实用性。
In this paper, we focus on mining surprising periodic patterns in a sequence of events. In many applications, e.g., computational biology, an infrequent pattern is still considered very significant if its actual occurrence frequency exceeds the prior expectation by a large margin. The traditional metric, such as support, is not necessarily the ideal model to measure this kind of surprising patterns because it treats all patterns equally in the sense that every occurrence carries the same weight towards the assessment of the significance of a pattern regardless of the probability of occurrence. A more suitable measurement, information, is introduced to naturally value the degree of surprise of each occurrence of a pattern as a continuous and monotonically decreasing function of its probability of occurrence. This would allow patterns with vastly different occurrence probabilities to be handled seamlessly. As the accumulated degree of surprise of all repetitions of a pattern, the concept of information gain is proposed to measure the overall degree of surprise of the pattern within a data sequence. The bounded information gain property is identified to tackle the predicament caused by the violation of the downward closure property by the information gain measure and in turn provides an efficient solution to this problem. Empirical tests demonstrate the efficiency and the usefulness of the proposed model.