title: Detecting rare incidents from multivariate time series intervals
body: <p>Given a time series of sensor state intervals, how do I implement a classifier which learns from supervised training data to detect an incident based on a sequence of state intervals? To simplify the problem, sensor states are reduced to either <code>true</code> or <code>false</code>.</p>
  
  <p><strong>Update:</strong> I've found <a href="http://fuzzy.cs.uni-magdeburg.de/wiki/uploads/Mitarbeiter.Kempe/Mining_Sequences_of_Temporal_Intervals.pdf">this paper (PDF)</a> on <em>Mining Sequences of Temporal Intervals</em> which addresses a similar problem. <a href="http://docs.google.com/viewer?a=v&amp;q=cache%3azBDmsljfWmUJ%3aciteseerx.ist.psu.edu/viewdoc/download%3Fdoi%3D10.1.1.88.603%26rep%3Drep1%26type%3Dpdf+Mining+Hierarchical+Temporal+Patterns+in+Multivariate+Time+Series+site%3a.edu&amp;hl=en&amp;pid=bl&amp;srcid=ADGEESivIUmQ69g2JVOM0G07NVLuehGh8Nn95DkffNcctH6_u8xti38b7WQadxgfEX8Nh1gvOcRHha_QRpDqGuf1uM8wZeZCcVFzC-MjNXxmC-GhEWCxLadKiBApOx-6BRjxD-8UU5i0&amp;sig=AHIEtbRcfxh9KxfqyOMxfePG7aXtRPpQVA">Another paper (Google Docs)</a> on <em>Mining Hierarchical Temporal Patterns in Multivariate Time Series</em> takes a novel approach, but deals with hierarchical data.</p>
  
  <h2>Example Training Data</h2>
  
  <p>The following data is a training example for an incident, represented as a graph over time, where <code>/¯¯¯\</code> represents a <code>true</code> state interval and <code>\___/</code> a <code>false</code> state interval for a sensor.</p>
  
  <pre><code> Sensor   |  Sensor State over time
            |  0....5....10...15...20...25...  // timestamp
   ---------|--------------------------------
   A        |  ¯¯¯¯¯¯¯¯¯¯¯¯\________/¯¯¯¯¯¯¯¯
   B        |  ¯¯¯¯¯\___________________/¯¯¯¯
   C        |  ______________________________  // no state change
   D        |  /¯\_/¯\_/¯\_/¯\_/¯\_/¯\_/¯\_/¯
   E        |  _________________/¯¯¯¯¯¯¯¯\___
  </code></pre>
  
  <h2>Incident Detection vs Sequence Labeling vs Classification</h2>
  
  <p>I initially generalised my problem as a two-category sequence labeling problem, but my categories really represented "normal operation" and a rare "alarm event" so I have rephrased my question as incident detection. Training data is available for "normal operation" and "alarm incident".</p>
  
  <p>To reduce problem complexity, I have discretized sensor events to boolean values, but this need not be the case.</p>
  
  <h2>Possible Algorithms</h2>
  
  <p>A hidden Markov model seems to be a possible solution, but would it be able to use the state intervals? If a sequence labeler is not the best approach for this problem, alternative suggestions would be appreciated.</p>
  
  <h2>Bayesian Probabilistic Approach</h2>
  
  <p>Sensor activity will vary significantly by time of day (busy in mornings, quiet at night). My initial approach would have been to measure normal sensor state over a few days and calculate state probability by time of day (hour). The combined probability of sensor states at an unlikely hour surpassing an "unlikelihood threshold" would indicate an incident. But this seemed like it would raise a false alarm if the sensors were noisy. I have not yet implemented this, but I believe that approach has merit.</p>
  
  <h2>Feature Extraction</h2>
  
  <p>Vector states could be represented as state interval changes occurring at a specific time and lasting a specific duration.</p>
  
  <pre><code>struct StateInterval
  {
      int sensorID;
      bool state;
      DateTime timeStamp;
      TimeSpan duration; 
  }
  </code></pre>
  
  <p>eg. Some State Intervals from the process table:</p>
  
  <pre><code>[ {D, true, 0, 3} ]; [ {D, false, 4, 1} ]; ...
  [ {A, true, 0, 12} ]; [ {B, true, 0, 6} ]; [ {D, true, 0, 3} ]; etc.
  </code></pre>
  
  <p>A good classifier would take into account state-value intervals and recent state changes to determine if a combination of state changes closely matches training data for a category.</p>
  
  <p><strong>Edit:</strong> Some ideas after sleeping on how to extract features from multiple sensors' alarm data and how to compare it to previous data...</p>
  
  <p>Start by calculating the following data for each sensor for each hour of the day:</p>
  
  <ul>
  <li>Average state interval length (for <code>true</code> and <code>false</code> states)</li>
  <li>Average time between state changes</li>
  <li>Number of state changes over time</li>
  </ul>
  
  <p>Each sensor could then be compared to every other sensor in a matrix with data like the following:</p>
  
  <ul>
  <li>Average time taken for sensor B to change to a true state after sensor A did. If an average value is 60 seconds, then a 1-second wait would be more interesting than a 120-second wait.</li>
  <li>Average number of state changes sensor B underwent while sensor A was in one state</li>
  </ul>
  
  <p>Given two sets of training data, the classifier should be able to determine from these feature sets which is the most likely category for classification.</p>
  
  <p>Is this a sensible approach and what would be a good algorithm to compare these features?</p>
  
  <hr>
  
  <p><strong>Edit:</strong> the direction of a state change (<code>false-&gt;true</code> vs <code>true-false</code>) is significant, so any features should take that into account.</p>