We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Reliable detection of episodes in event sequences.
- Authors
Gwadera, Robert; Atallah, Mikhail J.; Szpankowski, Wojciech
- Abstract
Suppose one wants to detect bad or suspicious subsequences in event sequences. Whether an observed pattern of activity (in the form of a particular subsequence) is significant and should be a cause for alarm depends on how likely it is to occur fortuitously. A long-enough sequence of observed events will almost certainly contain any subsequence, and setting thresholds for alarm is an important issue in a monitoring system that seeks to avoid false alarms. Suppose a long sequence,T, of observed events contains a suspicious subsequence pattern,S, within it, where the suspicious subsequenceSconsists ofmevents and spans a window of sizewwithinT. We address the fundamental problem: Is a certain number of occurrences of a particular subsequence unlikely to be generated by randomness itself (i.e. indicative of suspicious activity)? If the probability of an occurrence generated by randomness is high and an automated monitoring system flags it as suspicious anyway, then such a system will suffer from generating too many false alarms. This paper quantifies the probability of such anSoccurring inTwithin a window of sizew, the number of distinct windows containingSas a subsequence, the expected number of such occurrences, its variance, and establishes its limiting distribution that allows setting up an alarm threshold so that the probability of false alarms is very small. We report on experiments confirming the theory and showing that we can detect bad subsequences with low false alarm rate.
- Subjects
FALSE alarms; PROBABILITY theory; DATA mining; QUANTITATIVE research
- Publication
Knowledge & Information Systems, 2005, Vol 7, Issue 4, p415
- ISSN
0219-1377
- Publication type
Article
- DOI
10.1007/s10115-004-0174-5