Data Mining: The Textbook

15.4. OUTLIER DETECTION IN SEQUENCES

509

Just as regression modeling of continuous streams uses small windows of past history, discrete sequence prediction also uses small windows of the symbols. It is assumed that the prediction of the values at a position depends upon this short history. This is known as the short memory property of discrete sequences, and it generally holds true across a wide variety of temporal application domains.

Definition		15.4.2 (Short Memory Property) For	a sequence of	symbols V	=
a1 . . . ai . . .	,	the value of the probability P (ai|a1 . . .	ai−1) is well	approximated	by
P (ai|ai−k . .		. ai−1) for some small value of k.

After the value of P (a _i|a_i−k . . . a_i−1) is estimated, a position in a test sequence can be flagged as an outlier, if it has very low probability on the basis of the models derived from the training sequences. Alternatively, if a different symbol (than one present in the test sequence) is predicted with very high probability, then that position can be flagged as an outlier.

This section will discuss the use of Markovian models for the position outlier detection problem. This model exploits the short memory property of sequences to explicitly model the sequences as a set of states in a Markov Chain. These models represent the sequence-generation process with the use of transitions in a Markov Chain defined on the alphabet

• 
  This is a special kind of Finite State Automaton, in which the states are defined by a short (immediately preceding) history of the sequences generated. Such models correspond to a set of states A that represent the different kinds of memory about the system events. For example, in first-order Markov Models, each state represents the last symbol from the alphabet Σ that was generated in the sequence. In kth order Markov Models, each state corresponds to the subsequence of the last k symbols a_n−k . . . a_n−1 in the sequence. Each transition in this model represents an event a_n, the transition probability of which from the state a_n−k . . . a_n−1 to the state a_n−k+1 . . . a_n is given by the conditional probability P (a_n|a_n−k . . . a_n−1). A Markov Model can be depicted as a set of nodes representing the states and a set of edges representing the events that cause movement from one state to another. The probability of an edge provides the conditional probability of the corresponding event. Clearly, the order of the model encodes the memory length of the string segment retained for the modeling process. First-order models correspond to the least amount of retained memory.
  

To understand how Markov Models work, the previous example of tracking items with RFID tags will be revisited. The actions performed an item can be viewed as a sequence

drawn on the alphabet Σ = {P, R, C, E }. The semantic meaning of each of these symbols is illustrated in Fig. 15.4. A state of an order-k Markov model corresponds to the previous

• 
  (action) symbols of the sequence drawn on the alphabet Σ = {P, R, C, E}. Examples of different states along with transitions are illustrated in Fig. 15.4. Both a first-order and a second-order model have been illustrated in the figure. The edge transition probabilities are also illustrated in the figure. These are typically estimated from the training data. The transitions that correspond to the shoplifting anomaly are marked in both models. In each case, it is noteworthy that the corresponding transition probability for the actual shoplifting event is very low. This is a particularly simple example, in which a memory of one event is sufficient to completely represent the state of an item. This is not the case in general. For example, consider the case of a Web log in which the Markov Models correspond to sequences of Web pages visited by users. In such a case, the probability distribution of the next Web page visited depends not just on the last page visited, but also on the other preceding visits by the user.
  

510		CHAPTER 15. MINING DISCRETE SEQUENCES