Given that large tensor streams of time-evolving events (e.g., taxi rides), which contain multiple attributes, how do we obtain intuitive groups and temporal patterns? Also, how do we incrementally capture latent structure to achieve a meaningful summarization? In this paper, we propose a streaming algorithm, namely T C , which is designed to automatically nd both latent groups and temporal patterns in such complex yet huge collections. Our method has the following advantages: (a) It is e ective: it provides compact and interpretable representations that reveal similar features with respect to both attributes and time. (b) It is automatic: it automatically recognizes and summarizes temporal patterns without any parameter tuning. (c) It is scalable: it is incremental yet scalable, and thus requires computational time that is independent of data stream length. Extensive experiments on two real datasets demonstrate that T C provides a summarization that helps us understand the complicated data, and it consistently outperforms the state-of-the-art methods in terms of both execution speed and accuracy.
Countless domains including location-based services [
In practice, we need a summary that o ers interpretability revealing underlying groups, adaptability so that it captures dynamics and switches according to the state of the world, and automaticity that requires no human intervention. For example, taxi rides are continuously recorded with attributes such as pick-up time, pick-up location, drop-o location, taxi type, and customer type. To utilize them to design precise marketing strategies and bene cial business planning while re ecting actual conditions, service providers want to know that there are groups of locations and customers, and the di erence between periods, without any tuning that requires time and human resources.
To realize the above e ective representation, it is necessary to achieve the following two challenging and important tasks: (1) Structure mining: the goal is to provide an interpretable description that includes groups and their participation degrees. Unlike continuous sequences represented by sensor data, event collections turn into a huge yet sparse tensor, since events have numerous categorical features. We refer to such data as “complex events”. (2) Temporal pattern mining: the aim is to discover repeated time-evolving patterns. However, it is di cult because the number of patterns, their characteristic, and their duration are rarely known a priori. Thus it is necessary to learn them through data automatically. We also refer to such a temporal pattern as a “regime”.
There are following related works in terms of the two challenges
to be addressed:
Structure mining. Decomposition employing probability
distributions helps us to discover underlying structures [
In short, none of the previous studies speci cally address both structure mining and temporal pattern mining in complex event streams. We thus aim to tackle an important yet di cult task that is to reveal similar features with respect to both attributes and time simultaneously, moreover in automatic and streaming settings. Informally, if each event has a timestamp and two attributes (i.e., entity1, entity2), the problem we want to solve is as follows.
I P 1. Given triplet collections of streams (entity1, entity2, timestamp), (1) nd the latent groups in complex event collections and (2) summarize all dynamical patterns into models automatically and incrementally, at any point in time. 2
In this section, we formally de ne the concepts behind our model and the problem we want to solve. We mainly focus on a 3rd-order tensor for simplicity throughout this paper. Our method however can be applied to higher-order tensors. Consider that we receive time-stamped event entries of the form (entity1, entity2, timestamp). We then have a collection of entries with D unique entity1, E unique entity2 and = timestamps. We turn them into a 3rd-order tensor, i.e., X 2 ND⇥ E⇥ = .
De nition 2.1 (Complex event tensor). Let X be a 3rd-order tensor of complex time-stamped events. The element G8,9,C of X shows the total number of event entries of the 8-th entity1 and the 9 -th entity2 at time tick C .
We assume that an event entry has a common “latent group”. In that case, the original tensor will be decomposed into three matrices A, B, and C to represent groups with respect to entity1, entity2, and time.
De nition 2.2 (Participation matrix A (D ⇥ :)). Each entry 08,9 shows the participation strength of entity1 8 for group 9 to describe how strongly each entity1 participates in groups #1, #2, . . ., #:. We let any participation weight 08,9 be non-negative, and their total become 1 among : groups, i.e., Õ:9=1 08,9 = 1.
The de nitions ofB and C are analogous, each of them corresponds to entity2 and time. Although the multi-way representation allows us to nd latent groups, it is insu cient for mining tensor streams containing variable patterns; the latent groups and their participants should change following uctuation of dynamics. Thus, we extend the representation by adding another higher-level architecture.
De nition 2.3 (Regime). Let \ be a regime consisting of the three matrices: \ = {A, B, C} to represent a certain pattern, with which we can divide the entire tensor stream into segments. When there are < regimes, a full model set is de ned as⇥ = {\1 . . . \< }.
We adopt all of the above components for dynamic modeling over X. The problem that we want to solve is eventually as follows:
P 1 (S G).iven a tensor stream X ; Find full model set ⇥ that summarizes the whole input tensor X, namely, ⇥ = {\1 . . . \< }, and the number of regimes <, 3
In this section, we proposed a streaming approach, T C , which solves Problem 1. Intuitively, the main idea behind our algorithm is to continuously generate a model parameter set (i.e., regime) from current tensor X⇠ , and to try to update a full model set ⇥ using the generated regime. More speci cally, the algorithm comprises the following two main procedures (Algorithm 1) : (P1) T C C : Estimate a candidate regime \2 from a tensor X⇠ . It is derived by online decomposition while considering past ! temporal dependencies. (P2) T C C : Keep track of two regimes, namely the previous regime \? and the current candidate regime \2 . In this step, the algorithm decides whether or not to employ \2 and selects the optimal regime following our coding scheme.
Also full model set ⇥ is suitably updated to settle streaming. We roughly refer to the event streams of X⇠ as a partial tensor of X, whose length is g ⌧ =, and whose elements are G8,9,C g+1,. . . ,G8,9,C . Our algorithm works when given a non-overlapping stream X⇠ at every time point C with interval g . 3.1
T C Here, our aim is to incrementally obtain matrices A, B, and C as a candidate regime \2 , which summarizes the most recent stream We next tackle the problem of how to optimize full model set ⇥ . We can solve this problem intuitively by monitoring the regime shift and continuously choosing an appropriate model in {\? , \2 } based on their data summarization qualities.
Here, we introduce novel coding scheme to de ne a good
summary for a complex event tensor and determine a optimal compact
description automatically. Our coding scheme composed of model
description cost < ⇥ > and data coding cost < X |⇥ >, which
is based on the minimum description length (MDL) principle [
< X; ⇥ > =< \⇤ > + < X⇠ |\⇤ >, where \⇤ represents an employed regime for describing the arrival tensor X⇠ . Since the model description cost is the number of bits X⇠ . To discover several latent groups in X⇠ automatically, we propose using the concept of topic modeling, which enables us to probabilistically assign each event entry to a latent group based on Dirichlet priors.
For incremental inference, a straightforward approach repeats decomposition in each tensor X⇠ ; however, this approach discards previous distributions and group allocations lose temporal consistency at every inference. Therefore, T C C tracks dynamics by conveying previous model parameters. We assume that participation strength uctuate over time, and their intensity at the current time C is the same as that at those previous time C 1 unless otherwise con rmed by the newly observed data. Speci cally, previous participation strength AˆC 1,D ,Bˆ C 1,: and CˆC 1,: are integrated in Dirichlet prior (e.g., Dirichlet(U0ˆC 1,8 )). Letting U , V, and W be the parameters of the Dirichlet priors for A, B, and C, respectively, the generative process of a matrices is: (1) (2) (3) (4) ⇡A0F A8 ⇠ ⇡8A82;⌘4C (⌃ ;!=1U0ˆC ;,8 ), ⇡A0F BA ⇠ ⇡8A82;⌘4C (⌃ ;!=1V1ˆC ;,A ), ⇡A0F CA ⇠ ⇡8A82;⌘4C (⌃ ;!=1W2ˆC ;,A ) .
By utilizing collapsed Gibbs sampling [
A =1 080,A + !U 1A0,9 + Õ;!=1 V1ˆ;,A,9 · ÕE 9=1 1A0,9 + !V 2A0,C + Õ;!=1 W2ˆ;,A,C , · Õ=
C=1 2A0,C + !W where 08,A , 1A,9 , and 2A,C are the total counts with which group A is assigned to the 8-th entity1, the 9 -th entity2, and time C , respectively. The prime (e.g., 080,A ) indicates that the summations which is excluded the count of the entry, G8,9,C . After the sampler has burned-in, we produce estimated participation matrices. A˜, B˜, and C˜ as follows: 0˜8,A / 08,A + Õ; U0ˆ;,8,A ÕA 08,A + !U , 1˜A,9 / 1A,9 + Õ; V1ˆ;,A,9 , 2˜A,C / 2A,C + Õ; W2ˆ;,A,C .
Õ9 1A,9 + !V ÕC 2A,C + !W Thanks to the introduction of previous participation strength for each group, we need not store previous tensors to represent dynamics. It thus omits memory space and time complexity. Algorithm 1 T where | · | describes non-zero elements when 1/:, 1/E, and, 1/= are subtracted and 2 is the oating point cost2.
The data encoding cost of X given \ is the negative log-likelihood in Hu man coding, computed by: < X |\ >= log % (X |A, B, C). Thus the total encoding cost of X given ⇥ is:
< < X |⇥ > = ’ log % ( X [A? ] |\? ), (8)
?=1 where, X [A? ] is a set of partial tensors assigned by the ?-th regime. 4
We evaluated the performance of our proposed method on the two real data streams. (#1) NY-Taxi 3 dataset is the records of Yellow Taxi trips in New York City, which contains Pick up location ID (D = 262), Drop o location ID (E = 263), and the hourly timestamp of each ride (= = 4368). (#2) NY-Bike 4 dataset is the history of a bicycle ride-share service in New York City, whose attributes include the user-age groups separated by every ve ages from10 to 100 (D = 19), the start station ID (E = 488), and, the start time per hour (= = 8760).
E ectiveness. We will answer the question that How well does our method provide meaningful summaries with latent dynamical patterns and groups? Figure 1 (a) shows T C can incrementally and automatically nd two regimes and these assignments. Concretely, 1Here, log⇤ is the universal code length for integers. 2We set 8 bits in our setting. 3https://www1.nyc.gov/site/tlc/about/tlc-trip-record-data.page 4https://www.citibikenyc.com/system-data our method rst discovers “Regime 1” based on the three latent groups. After the dynamics behind the data have been changed at time tick 80, our method automatically generates “Regime 2” for the new pattern because the two regimes give us better summarization of the stream. These two representations coincide with realistic activities that correspond to weekdays and weekends. The “weekend” regime (Regime 2) successfully recognizes a public holiday at time tick 630 despite a non-periodic event.
Furthermore, T C provides participation matrices which show common groups and their attributes-wise participation weights. Figure 1 (b) and (c) show the estimated participation matrices, where there are three latent activity groups (shown with three colors) and the darker locations indicate stronger participation in the groups, whereas each sequence in Figure 1 (a) describes the time-wise intensities of each group.
As an example, we focus on Group 3 (green), which has a high intensity when assigned into the weekend regime; therefore, it is strongly related to weekend. Also, red circle areas in Figure 1 (c) shift from Group 2 (orange) to Group 3 on weekends, suggesting that these areas possess di erent features from the ones on weekdays. Considering these areas are located around vast parks and Lower Manhattan with a large number of bars and restaurants, it is thus likely to represent a group related to amusement. Activity groups are common among attributes, so we can know taxi rides which related to amusement are occurred from green area (Group 3) on the right in Figure1 (b). In short, our dynamic approach provides sense-making insights.
Accuracy and scalability. We will answer the following questions:
How accurately does our method summarize complex events? How
does our method scale in terms of computational time? To conduct
quantitative evaluations in two real datasets, we evaluated how
accurate the model represents original streams by comparing
reconstruction accuracy in terms of 1) perplexity, and 2) RMSE. The
competitors consist of TriMine [
Figure 2 shows the average perplexity and the average root mean square error (RMSE) between the original tensor and estimated values using every current tensor X⇠ of length 24. With both of them, lower values indicate better model constructions. Overall, our proposed method outperforms the other o ine methods because it can capture high-level patterns, i.e., regimes. CoSTCo is capable of handling sparse tensors but it is not optimized for complex event streams with latent dynamics.
Also, we evaluate the performance of T C in terms of computational time by comparison with its competitors. Figure 3 indicates the wall clock time of an experiment performed on each datasets. In each dataset, our method is faster than its competitors by up to four orders of magnitude thanks to our incremental update. 5
In this paper, we presented T C , an e cient streaming method for tensor streams of time-evolving events. Our proposed method has the following advantages: (a) It is e ective: our experiments show that T C successfully discover both latent groups and typical patterns from huge yet complex events. (b) It is automatic: T C is carefully designed to summarize event tensor streams
Public holiday (a) Regime assignments and time-wise group intensity (b) Pick up location-speci c groups (c) Drop o location-speci c groups
for taxi ride events: (a) Given the event tensor stream, it incrementally identi es regimes, i.e., underlying distinct dynamics (shaded rectangle with yellow/gray), and also captures time-wise intensity sequences of each group. In addition, it reveals the attribute-speci c groups of (b) pick up and (c) drop o areas, in which the colors show their latent groups and depth of the colors show attribute-wise participation weights (too low degrees are not shown (< 0.4)). outperforms its baselines in accuracy (#1) : NY-Taxi
(#2) : NY-Bike without prior tuning. (c) It is scalable: thanks to incremental model updating by T
, the computational time is constant with regard to the entire length of the input tensor.
In future work, we will make the proposed method more general by evaluating it on various datasets such as e-commerce, web access, and medical records. In addition, we will also conduct extensive experiments on more than three order tensors. Finally, we aim to design a fully automatic and fast algorithm. Speci cally, we consider that it would automatically determine not only the number of regimes but also the number of groups.