Mining sequential patterns across multiple sequence databases

In this paper, given a set of sequence databases across multiple domains, we aim at mining multi-domain sequential patterns, where a multi-domain sequential pattern is a sequence of events whose occurrence time is within a pre-defined time window. We first propose algorithm Naive in which multiple sequence databases are joined as one sequence database for utilizing traditional sequential pattern mining algorithms (e.g., PrefixSpan). Due to the nature of join operations, algorithm Naive is costly and is developed for comparison purposes. Thus, we propose two algorithms without any join operations for mining multi-domain sequential patterns. Explicitly, algorithm IndividualMine derives sequential patterns in each domain and then iteratively combines sequential patterns among sequence databases of multiple domains to derive candidate multi-domain sequential patterns. However, not all sequential patterns mined in the sequence database of each domain are able to form multi-domain sequential patterns. To avoid the mining cost incurred in algorithm IndividualMine, algorithm PropagatedMine is developed. Algorithm PropagatedMine first performs one sequential pattern mining from one sequence database. In light of sequential patterns mined, algorithm PropagatedMine propagates sequential patterns mined to other sequence databases. Furthermore, sequential patterns mined are represented as a lattice structure for further reducing the number of sequential patterns to be propagated. In addition, we develop some mechanisms to allow some empty sets in multi-domain sequential patterns. Performance of the proposed algorithms is comparatively analyzed and sensitivity analysis is conducted. Experimental results show that by exploring propagation and lattice structures, algorithm PropagatedMine outperforms algorithm IndividualMine in terms of efficiency (i.e., the execution time).     

Clustering spatial data with a geographic constraint: exploring local search

Spatial data objects that possess attributes in the optimization domain and the geographic domain are now widely available. For example, sensor data are one kind of spatial data objects. The location of a sensor is an attribute in the geographic domain, while its reading is an attribute in the optimization domain. Previous studies discuss dual clustering problems that attempt to partition spatial data objects into several groups, such that objects in the same group have similar values in their optimization attributes and form a compact region in the geographic domain. However, previous studies do not clearly define compact regions. Therefore, this paper formulates a connective dual clustering problem with an explicit connected constraint given. Objects with a geographic distance smaller than or equal to the connected constraint are connected. The goal of the connective dual clustering problem is to derive clusters that contain objects with similar values in the optimization domain and are connected in the geographic domain. This study further proposes an algorithm CLS (Clustering with Local Search) to efficiently derive clusters. This algorithm consists of two phases: the ConGraph (standing for Connective Graph) transformation phase and the clustering phase. In the ConGraph transformation phase, CLS first transforms the data objects into a ConGraph that captures geographic constraints among data objects and selects initial seeds for clustering. Then, the initial seeds selected nearby data objects and formed coarse clusters by exploring local search in the clustering phase. Moreover, coarse clusters are merged and finely turned. Experiments show that CLS algorithm is more efficient and scalable than existing methods.