Extracting temporal patterns from interval-based sequences
Résumé
Most of the sequential patterns extraction methods proposed so far deal with patterns composed of events linked by temporal relationships based on simple precedence between instants. In many real situations, some uantitative information about event duration or inter-event delay is necessary to discriminate phenomena. We propose the algorithm QTIPrefixSpan for extracting temporal patterns composed of events to which temporal intervals describing their position in time and their duration are associated. It extends algorithm PrefixSpan with a multi-dimensional interval clustering step for extracting the representative temporal intervals associated to events in patterns. Experiments on simulated data show that our algorithm is efficient for extracting precise patterns even in noisy contexts and that it improves the performance of a former algorithm which used a clustering method based on the EM algorithm.
La fouille de base de données séquentielles a pour objet l'extraction de motifs séquentiels représentatifs. La plupart des méthodes concernent des motifs composés d'événements liés par des relations temporelles basées sur la précédence des instants. Pourtant, dans de nombreuses situations réelles une information quantitative sur la durée des événements ou le délai inter-événements est nécessaire pour discriminer les phénomènes. Nous proposons deux algorithmes, QTIAPriori et QTIPrefixSpan, pour extraire des motifs temporels composés d'événements associés à des intervalles décrivant leur position dans le temps et leur durée. Chacun d'eux ajoute aux algorithmes GSP et PrefixSpan une étape de catégorisation d'intervalles multi-dimensionnels pour extraire les intervalles temporelles représentatifs. Les expérimentations sur des données simulées montrent la capacité des algorithmes à extraire des motifs précis en présence de bruit et montrent l'amélioration des performances en temps de calcul.