Mining Temporal Partial Orders from Event Sequences

Jian Pei, Simon Fraser University, Canada

Joint work with Haixun Wang (IBM), Jian Liu (eFrontier), Ke Wang
(Simon Fraser University), Jianyong Wang (Tsinghua University), and
Philip S. Yu (IBM)

Abstract

Mining knowledge about temporal ordering from event sequences has a few important applications, such as bioinformatics, web mining, network management and intrusion detection. For example, if many customers follow a partial order in their purchases of a series of products, the temporal order can be used to predict other related customers' future purchases and develop marketing campaigns. Moreover, some biological sequences (e.g., microarray data) can be clustered based on the partial orders shared by the sequences.

Given a set of items, a total order of a subset of items can be represented as a sequence. In this talk, I shall review our recent study on a novel problem of mining temporal closed partial orders.  Frequent closed partial orders capture the non-redundant and interesting temporal ordering information from string databases. Importantly, mining frequent closed partial orders can discover meaningful knowledge that cannot be disclosed by previous data mining techniques. However, the problem of mining frequent closed partial orders is challenging. To tackle the problem, we develop Frecpo (for Frequent closed partial order), a practically efficient algorithm for mining the complete set of frequent closed partial orders from large databases. Several interesting pruning techniques are devised to speed up the search. We report an extensive performance study on both real data sets and synthetic data sets to illustrate the effectivenessand the efficiency of our approach.