Name
Abstract | ||
|---|---|---|
Sequences of events are an important type of data arising in various applications, including telecommunications, bio-statistics, web access analysis, etc. A basic approach to modeling such sequences is to find the underlying intensity functions describing the expected number of events per time unit. Typically, the intensity functions are assumed to be piecewise constant. We therefore consider different ways of fitting intensity models to event sequence data. We start by considering a Bayesian approach using Markov chain Monte Carlo (MCMC) methods with varying number of pieces. These methods can be used to produce posterior distributions on the intensity functions and they can also accomodate covariates. The drawback is that they are computationally intensive and thus are not very suitable for data mining applications in which large numbers of intensity functions have to be estimated. We consider dynamic programming approaches to finding the change points in the intensity functions. These methods can find the maximum likelihood intensity function in O(n2k) time for a sequence of n events and k different pieces of intensity. We show that simple heuristics can be used to prune the number of potential change points, yielding speedups of several orders of magnitude. The results of the improved dynamic programming method correspond very closely with the posterior averages produced by the MCMC methods. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1145/502512.502562 | KDD |
Keywords | Field | DocType |
bayesian approach,varying number,underlying intensity function,expected number,fitting intensity model,maximum likelihood intensity function,large number,event sequence data,intensity function,simple intensity description,data mining application,mcmc,web accessibility,posterior distribution,markov chain monte carlo,maximum likelihood | Data mining,Markov chain Monte Carlo,Computer science,Heuristics,Artificial intelligence,Piecewise,Dynamic programming,Covariate,Pattern recognition,Algorithm,Expected value,Unit of time,Bayesian probability | Conference |
ISBN | Citations | PageRank |
1-58113-391-X | 12 | 2.47 |
References | Authors | |
1 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Heikki Mannila | 1 | 6595 | 1495.69 |
| Marko Salmenkivi | 2 | 161 | 13.42 |