Coresets for Time Series Clustering
Authors: Lingxiao Huang
K. Sudhir
Nisheeth K Vishnoi
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: coresets
clustering
time series data
Gaussian mixture model
autocorrelation

Abstract: We study the problem of constructing coresets for clustering problems with time series data.  This problem has gained importance across many fields including biology, medicine, and economics due to the proliferation of sensors facilitating real-time measurement and rapid drop in storage costs.  In particular, we consider the setting where the time series data on $N$ entities is generated from a Gaussian mixture model with autocorrelations over $k$ clusters in $\mathbb{R}^d$. Our main contribution is an algorithm to construct coresets for the maximum likelihood objective for this mixture model. Our algorithm is efficient, and under a mild boundedness assumption on the covariance matrices of the underlying Gaussians, the size of the coreset is independent of the number of entities $N$ and the number of observations for each entity, and depends only polynomially on $k$, $d$ and $1/\varepsilon$, where $\varepsilon$ is the error parameter.  We empirically assess the performance of our coreset with synthetic data. 

Coresets for Time Series Clustering
Lingxiao Huang Tsinghua University
K. Sudhir Yale University
Nisheeth K. Vishnoi
Yale University
Abstract
We study the problem of constructing coresets for clustering problems with time series data. This problem has gained importance across many fields including biology, medicine, and economics due to the proliferation of sensors for real-time measurement and rapid drop in storage costs. In particular, we consider the setting where the time series data N entities is generated from Gaussian mixture model with autocorrelations over & clusters in Rdd Our main contribution an algorithm to construct coresets for the maximum likelihood objective for this mixture model. Our algorithm is efficient, and, under a mild assumption on the covariance matrices of the Gaussians, the size of the coreset is independent of the number of entities N and the number of observations for each entity, and depends only polynomially on and 1/e, where E the error parameter. We empirically assess the performance of our coresets with synthetic data.
Introduction
multivariate time series dataset, represented as X' = (X, ( Ti,T, C R i [N] where is the number of entities, T; is the number of time periods corresponding to entity and d is the number features, tracks features of cross-section of entities longitudinally over time. Such data is also referred to as panel data [8] and has seen rapid growth due to proliferation of sensors, IOT and wearables that facilitate real time measurement of various features associated with entities and the rapid drop in storage costs. Specific examples of time series data include biomedical measurements (e.g., blood pressure and electrocardiogram) epidemiology and diffusion through social networks, weather, consumer search, content browsing and purchase behaviors, mobility through cell phone and GPS locations, stock prices and exchange rates in finance (2]
Computational problems of interest with time series data include pattern discovery 49 regres-
sion/prediction [39]. forecasting [9), and clustering 47 31 2 which arises in applications such as anomaly detection [46]. Though clustering is central and well-studied problem in unsupervised learning, most standard treatments of clustering tend be on static data with one observation per entity [35 [ Time series clustering introduces a number of additional challenges and is an active area of research, with many types of clustering methods proposed [T3]; direct methods on raw data, indirect methods based on features generated from the raw data, and model based clustering where the data are assumed to be generated from model. For surveys of time series clustering, see [7]
We focus on model-based time series clustering using a likelihood framework that naturally extends clustering with static data [11] to time series data 47). where each multivariate time series is generated by one of l different parametrically specified models. For a survey of the importance of this sub- literature and its various
applications, [30] A prevalent approach is assume finite mixture of data generating models, with Gaussian mixture models being a common specification 50 53 Roughly, the problem partition X' probabilistically into k clusters, grouping those series
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

generated by the same time series model into one cluster. Generically, the model-based k-clustering problem can be formulated as: arg m00),,
ΣiE(N: In EiE(H] ay ))( where aj is the probability of a time series belonging to cluster and pi (2 the likelihood of the data of entity i, given that the data is generated from model 1 (with parameters )() Temporal relationships in time series are commonly modeled as autocorrelations (AR)/moving averages (MA) [20] 61] that account for correlations across observations, and hidden Markov models (HMM) where the underlying data generating process is allowed to switch periodically 21 62) data generation model for each segment E [A]] is a multivariate Gaussian with autocorrelations. More formally, the generative model for each cluster is from a Gaussian mixture: Iy := ye()) + eic. where Ca = (O, Σ()) + A e,,-,. where (0, Σ() captures the mixture of Gaussian distributions from which entity level observations are drawn, and A captures the correlation between two successive Overall, this model can be represented with cluster level model parameters (()) = (1 "D)) A0) and cluster probability ax.
This paper focuses on the case when the
observations through an AR(1) process
32
Time series datasets are also much larger than static datasets 47 For instance, as noted in [2] ECG (electrocardiogram) data requires GB/hour, typical weblog requires 5 GB/week. Such large sizes lead to high storage costs and also make it necessary to work with a subset of the data to conduct the clustering analysis to be computationally practical. Further, long time series data on entities also entails significant data security and privacy risks around the entity as it requires longer histories of entity behaviors to be stored and maintained [25] 41). Thus, there is significant value for techniques that can produce approximately similar clustering results with smaller samples as with complete data.
Coresets have emerged account the objective and carefully sampling from the full dataset in a way that any algorithm run on the sampled set returns an approximate solution for the original objective with guaranteed bounds on approximation error 34. Coresets have been developed for both unsupervised clustering (e.g.. k-means, Gaussian mixture models) and supervised machine learning (e.g., regression) methods for static data; for surveys on coresets for static data, see 22] A natural question is whether coresets can be also useful for addressing the time series clustering problem. Recently, there is evidence that small coresets can be efficiently constructed for time series data, albeit for regressions with time series (panel) data [37] However, we explain in Section 2 there are challenges in extending coresets for static data clustering and time series (panel) data regressions for time series clustering.
effective tool to both speed up and reduce data storage by taking into
Our contributions. We study coresets for general class of time series clustering in which all entities are drawn from Gaussian mixtures with autocorrelations (as described above; see Problem [3T].. We first present definition of coresets for the log-likelihood k-clustering objective for this mixture model. One issue is that this objective cannot be decomposed into a summation of entity- objectives due to the interaction of the In term from log- likeliheeood and the cxp term from Gaussians (Problem [.I.. To estimate this objective using a coreset, we introduce an analogous clustering objective on subset of data (Definition 3.3p. Our main result is an algorithm construct coresets for this objective for the aforementioned mixture model (Theorem 4.3) Our algorithm is efficient (linear on both N and Eie[N TQ) and, assuming that the condition number of the covariance matrices of the
Gaussians (E)) are bounded and the eigenvalues of the autocorrelation matrices (A()) are bounded away from (Assumption (4T), the size of our coreset is independent of the number of entities N and the number of observations T,s; it only polynomially depends on k, d and 1/2, where is the error paramcter (Theorem 4.3).
Our coreset construction (Algorithm Tp leverages the Feldman-Langberg (FL) framework 27 Due to multiple observations for each entity and associated autocorrelations, the objective is non-convex and quite complicated in contrast to the static setting where the objective only contains one observation drawn from Gaussian mixtures for each entity. Thus, bounding the "sensitivity" (Lemma (4.6) of each entity, which is a key step in coreset construction using the FL-framework, becomes challenging. We handle this technical difficulty by 1) upper-bounding the maximum effect of covariances and autocorrelations by using the observation that the gap between the clustering objectives with and without Σ and A is always constant, and 2) reducing the Gaussian mixture time series clustering problem to a certain k-means clustering problem whose total sensitivity is upper bounded.
Empirically, we assess the performance of our coreset on synthetic data for three cluster problem (Section 5) and compare the performance with two benchmarks: uniform sampling and static coreset benchmark (LFKF 48) ) in which we do not consider autocorrelations and regard time series

---

data as static. We find that our coreset performs better relative to uniform sampling and LFKF on both data storage and computation speed for a range of accuracy guarantees: To achieve similar fit with the full data, our coreset needs fewer entity-time observations (<40%); ); the computation time for a given level of accuracy reduces by 3x-22x factor when compared to uniform sampling and LFKF. Moreover, our coreset speeds up the computation time relative to the full data by 14x-171x, We note that the performance advantage of our coreset is greater when there is more time series data relative to entities (T; > N).
2 Related work
Time series or panel data analysis are important in many fields- biological [8]
engineering
3
economics [51] and the social sciences (59). Clustering has been central problem in unsupervised
learning and also has long history of use across many fields; for historical overview of applications
across fields, see [2] While most standard treatments clustering in machine learning tend to be
there is by now significant and rapidly growing literature time series clustering; recent surveys include [4 2). While there are many coresets for algorithms on static data (including for clustering), there has been little work on coresets time series data (see below).
on static data [35
Coresets for clustering. Coresets for various clustering objectives on static data have been well studied, including k-median [34
and present coreset constructions for clustering problems on static data generated using Gaussian mixture models. 48
55
38 19]. k-means
34
17
28
10
55
38
19
k-center [ 33
For surveys of static coresets, see [52
23).
48
26
constructs a coreset of size poly(k, d, 1/s) under the same boundedness assumption as ours. 26 remove this assumption and construct coreset whose size additionally depends on poly log N, but require another assumption that all r,s are integral and a bounded range. In contrast, we consider a generalized problem where each entity has multiple observations over time and accounts for autocorrelations across successive observations. The new idea is to reduce the GMM time series clustering problem (Problem 3.1 to a k-means clustering problem whose points are linear combinations of those in X; (Lemma 1.12). and show that the effect of autocorrelation parameters A on the entity objectives can be upper bounded (Lemma A.
Regression with time series data. 37 construct coresets for a regression problem, called GLSE,, for time-series data including autocorrelations and k-partition of entities. This is supervised learning task that includes an additional label yir for each entity-time pair. It aims to find a
partition of entities and additional regression vectors g()) E IRd for each partition I e [k] such that a certain linear combination of terms l/ - (B()) J 132ll3 minimized. In contrast, our problem is an unsupervised learning task, estimates points 2ąz by Gaussian means instead of 3, and includes covariances Σ between different features. The definitions of coresets in (37] and ours consist of entity-time pairs but our coresets need to include multiple weight functions (w for entities and (() for time periods of selected entity i; see Definition 3.3) instead of one weight function as in the regression problem. This is to deal with the interaction of the In term from the log- likelhoo and the exp term from the Gaussians. [37]'s result relies on an assumption that the regression objective of each entity is in bounded range over the parameter space. This may not be satisfied in our setting since the clustering objective of an entity may be unbounded when all Gaussian means (1) are far away from observations of this entity. To bypass this, we reduce our problem to k- k-means clustering problem (Definition 4.2) whose total sensitivity is provably O(k) (Lemma 12.1)). by upper bounding the affect of covariance and autocorrelation parameters on the clustering objectives of entities (Lemmal A. under the assumption that the condition number of covariance matrix is
bounded (Assumption 4.1 which provides an upper bound for the total sensitivity of entities on our
problem (Lemma 4.6
Another related direction is to consider coreset construction for k-segmentation with time series data [54]]]]] 29,, which aims to estimate the trace of an entity by a k-piecewise linear function (k- segment). Note that the case of l = equivalent to the línear regression problem. [54 29] proposed efficient coreset construction algorithms which accelerate the computation time of the k-segmentation problem. The main difference from our setting is that they consider a single entity observed at multiple time periods, and the objective is an additive function on all time periods. This enables them to relate the k-segmentation problem to the static setting. interesting to investigate coresct construction for more optimization problems with time scries data.
3

---

3 Clustering model and coreset definition
Given X' = (X; (si.1 ( ..... ....,,....,..,..))) RdxT: i [N]], we first model general class of time series clustering problems. Then we specify our setting with Gaussian mixture time series data (Problem 3.1). and define coresets accordingly (Definition (.3).
Clustering with time series data, Given an integer 2 1, let An C R denote a probability simplex satisfying that for any Ar. we have a; [0, [] for i E [K] and Σiela) Qi 1. Let P denote a parameter space where each 0 E P represents specific generative model of time series data. For each entity E [N] and model E P. define p; 8) := Pr [x; 8
to be the average likelihooddrealizeed probability of X; from model 0. The ratio 1/T; is used to normalize the contribution to the objective of entity due to different lengths T;. The time series clustering problem compute a E As and (0()) ...., O(k) p that minimizes the negative log-likelihood, i... - -EINN] In Eiejy ao Pe( (()) Here, for each I [ks] ay represents the probability that each time series is generated from model (l)) Note that the clustering objective depends the choice of model family P. In this paper, we consider the following specific model family P that each time series is generated from Gaussian mixtures.
GMM clustering with time series data. Let E A& be a given probability vector. Let S denote the collection of all symmetric positive definite matrices in Px probability (7 E [k]), let zu == n
For each i E [N], with for each & E [T:] where y1( E Rd represents Gaussian mean and Ext E Id represents the error vector drawn from the following normal distribution: Eie := e + (0, ) where A Std is an AR(1) autocorrelation matrix and ( E Sd is the covariance matrix of a multivariate Gaussian distribution. Now we let P == Rd x S x Sd and note that each Gaussian generative model can be represented by tuple (n, Σ, A) P. Moreover, we have that the realized probability of each entity i E [N] is
0) (2 M, Ex A) == expl- 2े, (.).)))) Px
(I)
(2m) p2p122
where Σ is the determinant of Σ and (1, Σ, A) = ExE(T:) theee (E, with
via (E, A) == (I - 14) - (zi,1 - 11) - (A(zi,1 -1)) Σー (A(zi,1 - -1)), and
(E, A) = (( - 14) ( (2.,--1--)) Σー ((x - 14) A(x - n)) .V 2 S 1 S Ti. We note that each sub-function Uhe contains at most two entity-time pairs: The and -i,-- Our Gaussian mixture time series model gives rise in the following clustering problem.
Problem 3.1 (Clustering with GMM time series data). Given a time series dataset X
{X+ (Zi,1,..., T.T,; E RdxT: l [N]] and integer k 2 1, the GMM time series clustering problem is to compute a E As and (1 E0,, ,AAAA))) )EE()) E ph that minimize
()a,0)= = EiEN Sı(a, = - -iE(N] In EiEn 04 PP(x (,,,,,,,00 (0))
From Equation 11 it follows that the coefficient of each Gaussian before the exp operation is (2 whose summation Z(a, 0) = ΣiE(H) (2=)4////11177 is not a fixed value and depends on 5.0s. To remove this dependence on the coefficients, we define a²(0) = (2177221001177 to be the normalized coefficient for 1 e [k]. define offset function Ø A x Pk + E to be á(a, 0) = -N In ((x, 0), and define (' 0) : EiE[M] In Iee(M) Oi an-exp( 27, th (n 0 A ()) whose summation of coefficients before the exp operations is 1, This idea of introducing f also appears
in [24, 26 which is useful for coreset construction. This leads to the following observation.
Observation 3.2. For any a A and 0 E pt, f(a, 0) = f'(a' (0), 0) c(a,
Our coreset definition. The clustering objective f can only be decomposed into the summation of fis instead of sub-functions w.r.t. entity-time pairs. A simple idea is to select a collection of weighted entities as a coreset. However, in doing so, the coreset size will depend on T,s and fail to be independent of both N and Tis. To address this problem, we define our coreset as a collection of
weighted entity-time pairs, which is similar to 37 Let Px = ((i, E [N), / E [T]]] denote the collection of indices of all TH. Given S C Px, we let Is == e [N] 3I E [T.). s.l., (i, 1) E S) denote the collection of entities that appear in S. Moreover, for each E Is. we let Js.: =
{t e [T]] (i,t) E S} denote the collection of observations for entity i in S.

---

Definition 3.3 (Coresets for GMM time series clustering). Given a time series dataset X'
{X; = (Z T., E R | [N]], constant E E (0, 1). integer k 2 L, and parameter space A X PR, an s-coreset for GMM time series clustering is a weighted set S S Pxx together with functions weight functions w Is + R22 and w(() Js., + R2ofor i Ig such that for any a E As and 0 =
(u01,500 ( (EEE -Pk ['s 0)
Eiery w(i) In Ete(m) or exp(= 2T. Σ EieJs, w (1)
Vi(( (nl), (0),A()) E (1 el) (a,
Combining the above definition with Observation 3.2 we note that for any a E D and 0 E pk. f's(a' (0), 0) + o(a, 0) E (1+ f' 0) + o(a, 0) E (1 f(a, 0) + 2c0(a, 0).
(2)
As E tends to O. (a) 8) + Φ(a, converges to f(a, Moreover, given such a coreset S. if we additionally have that Φb 0) S l(aa,)) 0), we can minimize l'((a'00)0) + s(a, 0) to solve Problem 3.1 Thus, if (( 0) - f(a, 0), we conclude that (0)) 0) + o 0) E (1+33). ((a, 0).
Note that we introduce multiple weight functions (w for entities and w(() for time periods of selected entity i) in Definition 3.3 unlike the coreset for time series regression in 37 which uses only one weight function. This is because S/ contains In and exp operators instead of linear combinations of dae it is unclear how to use single weight function to capture both the entity and time levels.
4 Theoretical results
We present our coreset algorithm (Algorithm D and the main result on its performance (Theorem 4.3) Theorem 4.3 needs the following assumptions on covariance and autocorrelation parameters.
maxte Amax (201)
Assumption 4.1. Assume (1) that there exists constant D Z such that minsete) Amin (Eany S D
where )max(() (-) represents the largest eigenvalue and > (-) represents the smallest eigenvalue, and (2) for E [ks). A =DA for some constant X E (0, 1). Here Dý is a collection of all diagonal matrix in Rdxd whose diagonal elements are at most 1 - VÀ
The first assumption requires that the condition number of each covariance matrix is upper-bounded which also appears in [60] [45] 48) that consider Gaussian mixture models with static data. The second assumption, roughly, requires that there exist autocorrelations only between the same features. The upper bound for diagonal elements ensures that the autocorrelation degrades as time period increases, which also assumed [37]. Note that both the eigenvalues of g and the positions of means ( affect cost function th.s. For instance, consider the case that all eigenvalues are 1 and all autocorrelations are 0, i..., for all E [k), (() Ia and A Og. In this case, is easy to see that max Rdd (a( min peRd (a) Ja, i.e., the value of t/a (u,, La, 0a) unbounded μ changes. Differently,
the component's 's cost functions are bounded in 37 since μ ((')ss do not appear in 37 that consider regression problems.
Let P = (R2d x sá x D denote the parameter space. For preparation, we propose the following k-means clustering problem.
Definition 4.2 (k-means clustering of entities). Given an integer ls 2 1, the goal of the k-means
clustering problem of entities of X is find a set C* (ct...., [ C. ERd of centers that
[2 zu c112 over all k center sets C' = (ci....,c*k C Rd. Let
minimizes Eie[M] mingej
1;
(P) denote the optimal k-means value C
Note that there exists ((2poly(k) Nd) time algorithm to compute nearly optimal solution for both (P) and C* [43] Another widely used algorithm called k-means++ (6) which provides an O(I k) approximattnn in O In N In k) time but performs well in practice. We also observe
that via (p,, Ta. 02) Exerry Zit
Erery auilé
1l2 + 3. Exerry ||
T for any Jr E Rd. This
T.
observation motivates us to consider a reduction from Problem 3.1 to Definition 4.2 which is useful for constructing Is.
Our coreset algorithm. We first give a summary of our algorithm (Algorithm D. The input to Algorithm ii time series dataset X, an error parameter of coreset E (0, 1), an integer & > 1 of
5

---

clusters, À E (0, 1) (vector norm bound), and a covariance eigenvalue gap D 2 1. We develop two-staged importance sampling framework which first samples subset 1s of entities (Lines 1-8)
and then samples a subset of time periods Js,; for each selected entity i E Ts (Lines 9-14).
In the first stage, first set M the number of selected entities [Ts] (Line 1). Then we solve the
k-means clustering problem over entity means b; (Definition 4.2 c.g., by k-means++ [6] (Lines 2-3), and obtain an (approximate) optimal clustering value OPT(O) k-center set C* := ........ o C
Rd and an offiet value for each i E [N] Next, based on the distances of points b; to C*, we partition [N] into & clusters where entity belongs to cluster S(3) (Line 4). Based on b; (p(s) and
OPT(O) we compute an upper bound s(t) for the sensitivity w.r.t. entity E [NT (Lines 5-6). Finally, we sample weighted subset Is of entities as our coreset for the entity level by importance sampling based on s(i) (Lines 7-8), which follows from the Teagben-Langberg framework (Theorem A.6).
In the second stage, we first set L as the number of time periods |Js,al for each selected entity i E Is (Line 9). Then for each selected entity E Is, we compute OPT as the optimal 1-means clustering objective of 2us (Line 10). Next, we compute an upper bound (t) for the sensitivity w.r.t. time period & [T]] (Lines 1 11-12) based on and OPT Finally, we sample a weighted subset Js,, of time periods by importance sampling based on (t) (Lines 13-14).
Algorithm 1: CRGMM: Coreset construction for GMM time series clustering
Input: X = {X, (aa.1...., Ft,,,) E [dx27 i [N]]. constant À E (0, 1). number of clusters & 2 1, dimension of autocorrelation vectors 2 0, constant of the variance gap D 1, and parameter space
PK ====(Re 5d D
Output: subset S S P together with weight functions Is - Rzu and w Js, + R20 for Is.
Constructing subset of entities
1: M + O ( kD (k*d* + k2 k²d") )²)) In )
2: For each i E [N]. compute point 6, E 2 byb: bi + Eicrr and value a; 2 by T.
a; x E || Eserry Fall Let A Σie[N] dz.
T
3: Compute (an (ap)-appro for) (P) and C* {ci...., cf C Rd for the k-means
clustering problem over points 6; (Definition 4.2 by 43 6.
4: For each E [N], compute index p(i) E [A] by p() arg mimee |b: 1/.
5: For each E (1)
=
6: For each E [N]. sii min {
1,4D
(41 OPT
3s na).
7: Pick random sample Is C [N] of size M, where each i Is is selected w.p. EveiN) s(P)
s(1)
8: For each E Is. w(1) E.ggN
M.s(s)
% Constructing subset of time periods for each selected entity
D4 in
9: <-
xsa
10: For each i E Is. compute OPT(") + Everyy || - b.ll.
11: For each i E Ig and E [T.]. (t) +- Alla - 6 OPT
T
12: For each i E Is and t E [2]]. (t) + min 4DX (s(()) + ")in((t sE(t 5)
13: For each i E Is. pick random sample Js,, of points, where each t Js.i is selected w.p. a.(4)
Eeerh '
14: For each i E and Js.,, " (t) Every (1())
(.4(0)
% Output coreset 5 of entity-time pairs
15: L.et S ((i,t) E Px :e:ie Ts, E Js.).
S, w. (1) iels
Output
'eere, we slightly abuse the notation by using (O) and C* to represent the obtained approximate solution.

---

Our main theorem. Our main theorem is as follows, which indicates that Algorithm ! provides an efficient coreset construction algorithm for GMM time series clustering.
Theorem 4.3 (Main result). Under Assumption 4.1 with probability at least 0.9, Algorithm
7
D in? $. X
outputs an e-coreset of size O Ndk In N In k) time.
for GMM time-series clustering in O(d OidEE
T
Note that the success probability in the theorem can be made 1 for any 8 (0. the expense of an additional factor log² 1/6 in the coreset size. The coreset size guaranteed by Theorem 4.3 has a polynomial dependence on factors k. d, 1/e, D, and 1/A and, importantly, does not depend on N or T.s. Compared to the clustering problem with GMM static data [48], the coreset has an additional dependence on 1/A due to autocorrelation parameters. Compared to the regression problem (GLSE;) with time series data 377 Theorem 5.2], the coreset does not contain the factor "M" that upper bounds the gap between the maximum and the minimum entity objective. The construction time linearly depends on the total number of observations ΣiE[N] T,, which is efficient. The proof of Theorem 4.3 can be found in Section
Proof overview of Theorem
The proof consists of three parts: 1) Bounding the size of the coreset, 2) proving the approximation guarantee of the coreset, and 3) bounding the running time.
Parts 1 & 2: Coresel size and correciness guarantee of Theorem 4.3 We first note that the coreset size in Theorem 4.3 is |S] M L. Here, M is the number of sampled entities [s|] that guarantee that Is is a coreset for J" at the entity level (Lemma 4.4). is the number of sampled observations [Js.kl for each E Is that guarantees that Js, is coreset for ui; the time level (Lemma (4.).
Lemma 4.4 (The 1st stage outputs an entity-level coreset). With probability at least 0.95, the output Is of Algorithm 1 with M := |Is| O Oza (k* dt + 1add)) In x) satisfies that for any Liers wo(i)-In EiE(a] or exp( 22; (1(()) ,()) (1+ f'(a)) (). Lemma 4.5 (The 2nd stage outputs time level coresets for each i E 1s). With probability least satisfies that for DD
A and E Pt.
0.95. for all i Is. the output Js,s of Algorithm with L == [Js 0
any (M, A) Px, ElEJs.
(t) (p, E) E (1 (H, 21 A).
From Lemmas 4.4 and 4.5 we can conclude that S an O(s) (co)-core for GMM time-series clustering, since the errors ε for the entity level and the time level are additively accumulated, and that the size of the coreset M L as claimed; see Section for a complete proof.
Both lemmas rely on the Feldman-Langie upper bound both the "pseudo "iseudo-dimension" dim (Definition A.5) that measures the complexity of the parameter space, and the total sensitivity G (Definition (A.4) that measures the sum of maximum influences of all sub-functions (f² for Lemma
framework [27 13 (Theorem A.6). The key is to
v/s for Lemma The coreset size guaranteed by the Feldman- Langberg framework then is o(e dim g)
For Lemma 4.5
we can upper bound the pseudo-dimension by dim Odd") (Lemma B. For the total sensitivity, a key step is to verify that 8; (Line 12) is a sensitivity function the This step uses a similar idea as in [37] and leads to showing a G = O(D/A) bound for the total sensitivity Ddd
(Lemma B.2). Then we verify that L = O dim In g) O
is enough for Lemma 4.5
x=²
by the Weldman-LLngbere framework (Theorem A.6). The proof can be found in Section
Lemma 4.4 is the most technical. The proof can be found in Section A and we provide a proof sketch.
Proof sketch of Lemma 4.4 By 4 58), the pseudo diiedddoii is determined by the number of parameters that is upper bounded by (kd?) and the number of operations on parameters that is upper bounded by O(kd including O(k) exponential functions. Then we can upper bound the pseudo-dimension by dim = O + 1 dd) (Lemma A.9 in Section|A. A.2
For the total sensitivity, the key is to verify that 8 (Line 6) is a sensitivity function w.r.t. f': this is established by Lemma bell. Then the total sensitivity is at most G = (16D + 12Dk) A, This
completes the proof of Lemma since M = -2g dim In 9) = O the (K 3 l In x is enough by the Feldman-Langberg framework (Theorem A.6).
Lemma 4.6 (s is sensitivity function w.r.t. f'). For each i E [N], we have s(i) N
max BEPt P(a,8)
(((00)
Moreover, EiEIn) si) S (16D + 12D1)/A
7

---

Proof sketch of Lemma 4.6
We first define u (0) (n) (n) EtE(Ti) I - for any J E R and define
(a, 0(0))= = - In EEEM [E a: exp 2T, mini))y)((s) Amina (x(1)) 2 (ul))). Based on f!²) we
define another sensitivity function 8 si) == max gRaxi fror (a, and want to reduce s to $ .Note that u/ (0(0) (4) = (p, Ia. Oa), i.e. // removes the covariance and autocorrelation
I (a,glo)
parameters from 1hx. Due to this observation, we have that s (1) 1 max f((a.0)
f((a,8) S
4D- (i)/A by upper bounding the affect of covariance parameters (controlled by factor D) and autocorrelation parameters (controlled by factor 1/A), summarized as Lemma A.11 Then to prove
Lemma 4.6 it suffices prove that s (i)) <
41b-Saoll (i) which implies that the total OP
sensitivity of (00)) is upper bounded by 4 + 3k (Lemma 12) due to fact that >iE(N] 5i) s k (Lemma A.13). Finally, the proof of Lemma A.12 is based on a reduction from v)((0) to the k-means clustering problem of entities (Definition 4.2) by rewriting 7: 1 (0))))()))))) (1) ||b; ==12 + a, and then projecting each 6, to its closest center in C The full proof of this lemma can be found in Section A.3
Part 3: Running time Theorem 4.3 The first stage costs O(d EiELN T, + Ndk In N In k) time.
The dominating steps are 1) to compute by in Line 2 which costs O E LiE[N] T:) time; 2) to solve the k-means clustering problem of entities (Line 3) which costs Ndk In N In k) time. The second stage costs at most (dd DiE(N T:) time. The dominating step is to compute OPT for all E Is
in Line 10, where it costs (dT;) time to compute each OPT(
Remark 4.7 (Technical comparison with prior works). Note that our entity coreset construction uses some ideas from (24 48| and also develops novel technical ideas. generalization of [24 48) to time series data is to treat all observations Tat independent and compute sensitivity for each Ta directly for importance sampling. However, this idea cannot capture the property that multiple observations P5.1....,T..T. are drawn from the same Gaussian model (certain E [Ke)). To handle multiple observations, we show that although each tú; consists of Ti sub-functions Vis it can be
approximated by single function on the average observation by Emery,
Tie specificalll, we T;
have (p,, la. 0a) = d(bi, 11)2 4 0(1). This property enables us to "reduce" " the representative complexity of 4b, and motivate two key steps of our construction: 1) For the sensitivity function, we of T,
give reduction to certain k-means clustering problem on average observations by Enerry zis
entities (Definition 4.2) by upper bounding the maximum effect of covariances and autocorrelations and applying the fact that up Ia, 02) = d(b;, 11)² + +(1). ) 2) For the bgeudo-dienssoo, we prove that there are only poly (ks d) intristic operators in th; between parameters @ and observations Tit. based on the reduction of the representative complexity of vi.
48 would be an interesting future direction since we may get rid of Assumption 4.1 Currently, it is unclear how to generalize the approach of (26) time series data since (26) assumes that each point is integral point within a bounded box, while we consider a continuous GMM generative model ( and hence, each coordinate of arbitrary observation Tstr is drawn from certain continuous GMM distribution which is not integral with probability Rs 1 and can be unbounded.
Generalizing our results in the same manner 126] does over 24
5 Empirical results
We compare the performance of our coreset algorithm CRGMM, with uniform sampling as a bench- mark using synthetic data. The experiments are conducted with PyCharm IDE on a computer with 8-core CPU and 32 GB RAM.
Datasets. We generate two sets of synthetic data all with 250K observations with different number of entities N and observations per individual Tą: (i) N = T; = 500 for all i E [N] and (ii) N = 200, T. 1250 for all i [N]. As cross-entity variance is greater than within entity variance, this helps to assess coreset performance sensitivity when there are more entities (high N) vs. more frequent measurement/ longer measurement period (high T;).
We fix d 2, k 3, À 0.01 and generate multiple datasets with model parameters randomly varied as follows: (i) Draw a from uniform distribution over Ak- (ii) For each / E [K)]. draw
8

---

1 E Rd from (O Ia). (iii) Draw ( by first generating a random matrix A E [0, 1]axd and then let 20 = (AA)
and (iv) draw all diagonal elements of A E D' from a uniform distribution over [0, 1 - vÁJ. Given these draws of parameters, we generate a GMM time-series dataset as
follows: For each i E [M], draw / E [k] given a. Then, for all E [T:] draw ext E Rd with covariance matrix Σ and autocorrelation matrix A (1) and compute x5. = ( + eqc E Rd.
Baseline and metrics. We use coresets based on uniform sampling (Uni) and based on [48] (LFKF) that constructs coreset for Gaussian mixture model with static data as the baseline, Given an integer r, uniformly sample a collection S of I entity-time pairs (i, t) E Px, let w(i) l/sl for each i E Is.
N
and let w (t) = T. for each & E Js,ú and LFKF regard all entity-time pairs as independent |Js.
points and sample collection S of T entity-time pairs (i, f) E Px via importance sampling. For comparability, we set I' to be the same as our coreset size. The goal of selecting LFKF as a baseline is to see the effect of autocorrelations to the objective and show the difference between static clustering and time series clustering.
Let V* (negative log-likelihood) denote the objective of Problem 3.1 with full data. Given weighted subset S S [N] x (T). we first compute (a* (*)) := arg min .EA...PP (a)()(()))))) 0) + o(a, 0) as the maximum likelihood solution over S Then V3 f(a",0" over the full dataset serves metric of model fit given model estimates from a weighted subset S. We use the likelihood ratio, i.e., Is 2(V3 V* as a measure of the quality of S [14). The running time for GMM clustering with full data (V*) and coreset (Vg) are Tx and Ts respectively. To is the coreset S construction time.
Empirical setup. We vary = 0.1, 0.2, 0.3, 0.4, 0.5. For each E, we run CRGMM and Uni to generate coresets each. We estimate the model with the full dataset X' and the coresets S and record V*, V and the run times.
Table 1: Performance of s-coresets for CRGMM w.r.t. varying s. We report model fit as the mean of V/S (negative log-likelihood) w.r.t. 5 repetitions for our algorithm CRGMM and Uni on two synthetic datasets. "Synthetic 1" (N 500 entities and T. 500 observations for each entity), and "Synthetic 2" (N 200, T:= 1250); Size (I'): number sampled entity-timn pairs for CRGMM, Uni, and LFKF; Te: construction time of coresets, which is at most 2s in our experiments. I's and Tx: computation time for GMM clustering time over coresets and full data respectively.
Model fit V/ of our coreset is very close relative to the optimal V with full data; and much better than Uni and LFKF. Our coreset fit also does decay as much as Uni and LFKF with larger error guarantees (0.1 0.5). Our coresct achieves 3x-22x acceleration in solving Problem sample size and a 14x-171x 171x acceleration relative to the full data.
3. compared Uni and LFKF using same
V
V'
S
size
To Ty Uni
Tx
CRGMM
LFKF
CRGMM
LFKF
LFKF
0.1
2050
2069
2041
22
56
1514
2416
1355
3436
Syuthette
0.2
2093
2264
104
1054
0.3
2194
2398
2384
306
714
686
[9]
62
419
392
0.4
2335
3963
2705
588
3844
1328
93
38
621
260
132
Symieeti 2
0.1
841
812
694
1859
1657
9787
824
118
1991
0.3
864
058
9944
104
292
364
199
51
527
832
0.4
860
1190
1114
96
756
604
43
408
450
1284
196
Results. Table I summarizes the quality quality-size-time size-time trade-offs of our coresets for different error guarantees E. The VğS achieved by our coreset is always close to the optimal value V and is always smaller than that of Uni and LFKF. We next assess coreset size. For the N T, = 500 case, the coreset achieves a likelihood ratio 7s = 684 with only 72 entity-time pairs (0.03%), but Uni/LFKF achieves the closest (but worse) likelihood ratio of 755 = 714/686, with 191 entity-time pairs (0.08%). Thus, our coreset achieves a better likelihood than uniform and LFKF with less than 40% of observations. Further, from Figure [ we that not only is the quality of our coreset (7s) superior, it has lower standard deviations suggesting lower variance in performance. In terms of total computation time relative to the full data Te+TT
Txx ), our coresets speed up by 14x-171x. Also, the
We solve this optimization problem using an EM algorithm similar to 5]. The M step in each iteration is based on IRLS 40) and the E-step involves an individual level Bayesian update for a.

---

= 500
N 200, 1250
4000
CRGMM
1200
CRGMM
Uni
Uni
LFKF
3000
2000
600
400
1000
200
0
0.1
0.2
0.3
0.4
0.5
0.1
0.2
0.3
0.4
0.5
Figure 1: Mean +/- std. of 7s. w.r.t varying e. 7s is the likelihood ratio (LR) for estimates from coresets relative to full data. CRGMM not only has better fit than Uni and LFKE, but much small std. performance. The std. for coreset is smaller for Synthetic with fewer entities.
computation time (Tc + T') of Uni and LFKF is always larger than that of our coreset (3x-22x) Finally, Vğ is lower for Synthetic given that there are fewer entities and cross-entity variance is greater than within entity variance. From Figure we also see that both the fit and std in performance for coresets much lower for Synthetic Thus, overall our coreset performs better when there is more time series data relative to entities (T; >> N) a feature of sensor based measurement that motivates this paper.
Limitations, conclusion, and future work
In this paper, we study the problem of constructing coresets for clustering problems with time series data; in particular, we address the problem of constructing coresets for time series data generated from Gaussian mixture models with auto-correlations across time. Our coreset construction algorithm is efficient under mild boundedness assumption the covariance matrices of the underlying Gaussians, and the size of the coreset is independent of the number of entities and the number of observations and depends only polynomially on the number of clusters, the number of variables and an error parameter. Through empirical analysis on synthetic data, we demonstrate that the coreset sampling is superior uniform sampling in computation time and accuracy.
Our work leaves several interesting directions for future work on time series clustering. While our current specification with autocorrelations assumes stable time series pattern over time, future work should extend it to a hidden Markov process, where the time series process may switch over time. Further, while our focus here is model-basee baaeedbbaedddde clustering, it would be useful to consider how coresets should be constructed for other clustering methods such as direct clustering of raw data and indirect clustering of features.
Overall, we hope the paper stimulates more research on coreset construction for time series data on variety of unsupervised and supervised machine learning algorithms. The savings in storage and computational cost without sacrificing accuracy is not only financially valuable, but also can have sustainability benefits through reduced energy consumption. Finally, recent research has shown that summaries (such as coresets) for static data need to include fairness constraints to avoid biased outcomes for mnder-representes groups based on gender and race when using the summary [16] 36); future research needs to extend such techniques for time series coresets.
Acknowledgments
This research was supported in part by an NSF C9F-1908347 grant.
A possible explanation is that our coreset selects is of entities that are more representative that Uni, and hence, achieves better convergence speed.
10

---

References
[1] Pankaj K Agarwal and Cecilia Magdalena Procopiuc. Exact and approximation algorithms for clustering. Algorithmica, 33(2):201 2266, 2002.
[2] Saeed Aghabozorgi, Ali Seyed Shirkhorshidi, and Teh Ying Wah. Time-series clustering-2 decade review. Information Systems, 53:16-38, 2015.
[3] Hirotugu Akaike and Genshiro Kitagawa. The practice of time series analysis. Springer Science & Business Media, 2012.
[4] Martin Anthony and Peter L Bartlett. Neural network learning: Theoretical foundations. Cambridge University press, 2009.
[5] Peter Arcidiacono and John Bailey Jones. Finite mixture distributions, sequential likelihood and the EM algorithm. Econometrica, 71(3):933 94699339966692 2003.
[6] David Arthur and Sergei Vassilvitskii. k-means++: the advantages of careful seeding. In Nikhil Bansal, Kirk Pruhs, and Clifford Stein, editors, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, pages 1027-1035. SIAM, 2007.
[7] Olivier Bachem, Mario Lucic, and Andreas Krause. Practical coreset constructions for machine learning, arXiv preprint arXiv: hao:::703..4444 06476, 2017.
[8] Badi Baltagi. Econometric analysis panel data. John Wiley & Sons, 2008
[9] Kasun Bandara, Christoph Bergmeir, and Slawek Smyl. Forecasting across time series databases using recurrent neural networks on groups of similar series: A clustering approach. Expert systems with applications, 140: 1et111229,,, 2020.
[10] Luca Becchetti, Marc Bury, Vincent Cohen-Addad, Fabrizio Grandoni, and Chris Schwiegelshohn. Oblivious dimension reduction for k-means: beyond subspaces and the Johnson--Lindenstraus lemma. In Proceedings of the 51st Annual ACM SIGACT Symposium Theory of Computing, pages 1039-1050. ACM, 2019.
[11] Avrim Blum, John Hopcroft, and Ravindran Kannan. Foundations of data science, Cambridge University Press, 2020.
[12] Hans-Hermamn Bock. Clustering methods: a history of k-means algorithms. Selected contribu- tions in data analysis and classification, pages 161-172, 2007.
[13] Vladimir Braverman, Dan Feldman. and Harry Lang. New frameworks for offline and streaming coreset constructions. CoRR, abs/1 f1s.//01120889 2016.
[14] Adolf Buse. The likelihood ratio, wald, and lagrange multiplier tests: An expository note. The American Statistician, 36(33):153-1577 1982.
[15] Jorge Caiado, Elizabeth A Maharaj, and Pierpaolo D'Urso. Time series clustering. Handbook of cluster analysis, pages 241 1-33, 2015.
[16] L Elisa Celis, Vijay Keswani, Damian Straszak, Amit Deshpande, Tarun Kathuria, and Nisheeth K. Vishnoi. Fair and diverse dpp-based data summarization. In ICML, 2018
[17] Ke Chen. On coresets for k-median and k-means clustering in metric and Euclidean spaces and their applications. SIAM J. Comput., 39(3):923 947799777799--- August 2009.
[18] Mike X Cohen. Analyzing neural time series data: theory and practice. MIT press, 2014.
[19] Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn. A new coreset framework for clustering. CoRR, abs/2104.06133 2021.
[20] Pierpaolo D'Ur and Elizabeth Ann Maharaj. Autocorrelation-base fuzzy clustering of time series. Fuzzy Sets and Systems, 160124):355-3388, 2009.

---

[21] Jason Ernst, Gerard Nau, and Ziv Bar-Joseph. Clustering short time series gene expression data. Bioinformatics, 21(pup 1):1199-11000 i168, 2005.
[22] Dan Feldman. Core-sets: Updated survey. Sampling Techniques for Supervised or Unsupervised Tasks, pages 23 44, 2020.
[23] Dan Feldman. Introduction to core-sets: an updated survey. CoRR, abs/2011.09353 2020.
[24] Dan Feldman, Matthew Faulkner, and Andreas Krause. Scalable training of mixture models via coresets. In Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 201 I. Proceedings of a meeting held 12-14 December
2011, Granada, Spain, pages 2142-2150, 2011.
(25] Dan Feldman, Amos Fiat, Haim Kaplan, and Kobbi Nissim. Private coresets. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 361-370, 2009.
[26] Dan Feldman, Zahi Kfir, and Xuan Wu. Coresets for Gaussian mixture models of any shape. arXiv preprint arXiv: 1906. 04895, 2019.
[27] Dan Feldman and Michael Langberg. unified framework for approximating and clustering data. In Proceedings of the forry-third annual ACM symposium Theory of computing, pages 569-578. ACM, 2011. https: //ttps:/aane awwivv..vvvv///////////x///aaav/ org/ abs/1106. 1379
[28] Dan Feldman, Melanie Schmidt, and Christian Sohler. Turning big data into tiny data: Constant- size coresets for k-means, PCA and projective clustering. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1434-1453. SIAM, 2013.
[29] Dan Feldman, Cynthia R. Sung, Andrew Sugaya, and Daniela Rus. idiary: From GPS signals to a text- searchable diary. ACM Trans. Sens. Networks, 16646660:-6:::1, 2015.
[30] Sylvia Srihhairth-cchnatee.. Panel data analysis: a survey on model-based clustering of time series. Adv. Data Anal. Classif., 5(4): 2011.
[31] Tak-chung Fu. A review on time series data mining. Engineering Applications of Artificial Intelligence, 24(1):164-181, 2011.
[32] John N Haddad. A simple method for computing the covariance matrix and its inverse of stationary autoregressive process. Communications in Statistics-Simulation and Computation, 27(3):617-623, 1998.
[33] Sariel Har-Peled. Clustering motion. Discrete & Computational Geometry, 31(4)5545-565 2004.
[34] Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k- k-median clustering, In 36th Annual ACM Symposium on Theory of Computing,, pages 291-300, 2004.
[35] Christian Hennig, Marina Meila, Fionn Murtagh, and Roberto Rocci. Handbook of cluster analysis. CRC Press, 2015.
[36] Lingxiao Huang, Shaofeng H-C Jiang, and Nisheeth K Vishnoi. Coresets for clustering with fairness constraints. In NeurIPS, 2019.
[37] Lingxiao Huang, K Sudhir, and Nisheeth Vishnoi. Coresets for regressions with panel data. Advances in Neural Information Processing Systems, 33, 2020.
[38] Lingxiao Huang and Nisheeth K. Vishnoi. Coresets for clustering in Euclidean spaces: Im- portance sampling nearly optimal. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020. pages 1416-1429 ACM, 2020.
[39] Jui-Long Hung, Morgan C Wang, Shuyan Wang, Maha Abdelrasoul, Yaohang Li, and Wu He. Identifying at-risk students for early interventions- time-series clustering approach. IEEE Transactions Emerging Topics in Computing, 5(1):45-55, 2015.
12

---

[40] Murray Jorgensen. Iteratively reweighted least squares. Encyclopedia of Environmetrics, 3, 2006.
[41] Tony Ke and Sudhir. Privacy rights and data security: GDPR and personal data driven markets. Available at SSRN 3643979, 2020.
[42] Eamonn Keogh. A decade of progress in indexing and mining large time series databases. In Proceedings of the 32nd international conference on Very large data bases, pages 1268-1268, 2006.
[43] Amit Kumar, Yogish Sabharwal, and Sandeep Sen. simple linear time aaproxxaiiinnaaaio algorithm for k-means clustering in any dimensions. In 45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proceedings, pages 454 462. IEEE Computer Society, 2004.
[44] James P LeSage The theory and practice of spatial econometrics. University of Toledo. Toledo, Ohio, 28(11), 1999.
[45] Jiao-fen Li, Wen Li, and Seak- Weng Vong. Efficient algorithms for solving condition number- constrained matrix minimization problems. Linear Algebra and its Applications, accepted, 08 2020.
[46] Jinbo Li, Hesam Izakian, Witold Pedrycz, and Iqbal Jamal. Clustering- based anomaly detection multivariate time series data. Applied Soft Computing, 100:106919, 19, 2021.
[47] Warren Liao. Clustering of time series data survey. Pattern recognition, 38(11):1857-1874 2005.
[48] Mario Lucic, Matthew Faulkner, Andreas Krause, and Dan Feldman. Training Gaussian mixture models at scale via coresets. The Journal of Machine Learning Research, 18(1):5885-5909 2017.
[49] Benjamin M Marlin, David C Kale, Robinder G Khemani, and Randall C. Wetzel. Unsupervised pattern discovery in electronic health care data using probabilistic clustering models. In Proceedings of the 2nd ACM SIGHIT international health informatics symposium, pages 389- 398, 2012.
[50] Ming Ouyang, William Welsh, and Panos Georgopoulos. Gaussian mixture clustering and imputation of microarray data. Bioinformatics, 20(6):917-922 2004.
[51] M Hashem Pesaran. Time series and panel data econometrics. Oxford University Press, 2015.
[52] Jeff M. Phillips. Coresets and sketches. CoRR, abs/ 2016.
[53] Aarthi Reddy, Meredith Ordway-Wer Melissa Lee, Matt Dugan, Joshua Whitney, Ronen Kahana, Brad Ford, Johan Muedsam, Austin Henslee, and Max Rao. Using gaussian mixture models to detect outliers in seasonal univariate network traffic. In 2017 IEEE Security and Privacy Workshops (SPW), pages 229-234. IEEE, 2017.
[54] Guy Rosman, Mikhail Volkov, Dan Feldman, John W. Fisher III, and Daniela Rus. Coresets for k- segmentation of streaming data. In Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger, editors, Advances in Neural Information Processing Systems 27: Annual Conference Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec. Canada, pages 559-567, 2014.
[55] Christian Sohler and David P. Woodruff. Strong coresets for k-median and subspace approxi- mation: Goodbye dimension. In FOCS, pages 013. IEEE Computer Society, 2018.
[56] VN Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2):264, 1971.
[57] Kasturi Varadarajan and Xin Xiao. On the sensitivity of shape fitting problems. In 32nd International Conference on Foundations of Software Technology and Theoretical Computer Science, page 486, 2012.
13

---

[58] Mathukumalli Vidyasagar. A theory of learning and generalization. Springer-Verlag. 2002.
[59] William WS Wei. Time series analysis. In The Oxford Handbook of Quantitative Methods in Psychology: Vol. 2. 2006.
[60] Joong-Ho Won, Johan Lim, Scung-Jean Kim, and Bala Rajaratnam. Condition-numble regularized covariance estimation. Journal of the Royal Statistical Society. Series B (Statistical Methodology), 75(3):427-44 2013.
[61] Yimin Xiong and Dit-Yan Yeung. Time series clustering with ARMA mixtures. Pattern Recognition, 3778):1675-1688 2004.
[62] Yun Yang and Jianmin Jiang. Hmm-based hybrid meta-clustering ensemble for temporal data. Knowledge-Bon Systems, 56:299-310, 2014.
14


Reviews:
[{"review_id": "n1PthJniQNB", "reviewer": "Reviewer_3r9a", "summary": "The paper suggests a coreset construction algorithm for a clustering time-series data.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In this paper, a coreset construction algorithm was provided for clustering time-series data, specifically speaking GMMs.\nThe coreset was achieved via reduction towards the $k$-means clustering problem. \n\nIn addition, I find it interesting that the paper suggests two different weight functions, one for the entities and one for the time periods whereas for traditional coresets, there is only one weight function that handles the only entities.\n\nI enjoyed reading the paper, however, due to time constraints, I was not able to go over the proofs of the presented theorems.\n\nComments:\n- Line 141, $\\Delta_k$ instead of $\\Delta^k$.\n- $e_{it}$ is not a scalar based on its definition at Line 150. Did you mean to write $e_{it} \\in \\mathbb{R}^{d}$?\n- Why didn't you apply your coreset on real-world panel data? \n- The coreset size depends heavily on the dimension of the data. See the limitation section for elaborated improvements.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "\nThe authors have addressed the limitations of the paper properly. \nSpecifically speaking, the coreset construction algorithm is performed well under a mild boundedness assumption on the covariance matrices of the underlying Gaussians. \n\nThe coreset size on the other hand depends polynomially on the dimension of the instances, i.e., the exponent is $16$. Thus in such cases, when dealing with big data where $d \\in \\Theta{M}$ or even $d \\in \\Theta{M^{1/16}}$, then the coreset basically contains $M$ points where $M$ denotes the total number of instances in the dataset. \n\nPlease provide a small discussion regarding the lower bound on the coreset size which is needed for GMMs on time-series data, i.e., \"how hard the problem is from a coreset point of view?\"\n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours "}, "extra_text": {}}, {"review_id": "cA3gNXQVdLV", "reviewer": "Reviewer_Wpms", "summary": "In this paper the authors provide the definition of a coreset for time series clustering for entities generated from a gaussian mixture model and then build a coreset for the same problem.  The coreset is independent of both the number of entities N and the the number of Time stamps T_i for each entity i. They demonstarte the accuracy and efficiency of their coreset by superior empirical perfromance over synthetic data as compared to uniform sampling.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In this paper the authors provide coreset for time series data generated from GMM with autocorrelations.\n\nSignificance: \n Clustering time series data has become an important problem in ML due to huge amounts of data available over time. For scalabiltiy of clustering, coresets provide a very good option. From this view point this is an interesting and important paper. The theoretical results will be insightful to the coreset community in particular and the overall results are interesting for the ML community in general.\n\nOriginality: \nTo the best of my knowledge, this is the first paper on coreset for time series data in the unsupervised setting. The defintion of coreset provided by the authors for GMM time series clustering is different from traditional coreset in sense that along with a tuple of entity and time stamp it has two weight functions : one for the entity other for time. \nThough the paper borrows heavily from existing coreset literature for e.g: 1)Feldman Langberg framework for constructing coresets, 2)the idea of introducing f' for the GMM clustering from [23][25] 3)the assumptions from [52,42,35,34] etc. ; I believe the application of these ideas to the setting of time series clustering for e.g bounding the sensitivities, pseudodimension etc. is non trivial. Overall I believe the paper has reasonable novelty.\n\n\nQuality and  Clarity:\nI have not checked the proofs in detail however the proofs look alright. \nHowever I think the writing specifically the mathematical writing can be improved. There are a lot of variables and symbols used in the paper. It would be useful if some convention is followed for writing these variables. For e.g. vectors in small bold letters, matrices in capital bold letters, scalars in small letters etc. In current state it becomes very difficult while reading and one has to go to and fro to check if a given variable is vector, scalar etc.\nI think there are minor typos at the following places: On line 183 eq. 2 should it not be f'(alpha(theta), theta) and not just alpha as a parameter.?\nWhat is P on line 174?\nWhat is tau in the input of algorithm 1 as subscripst of S?\n\nThe experiments show very positive results however they are only for synthetic data\n\nOverall I feel this paper has merits that outweigh the flaws and is a good candidate for publication.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have mentioned their restriction to the GMM with autocorrelation as generative model for the time series data as a limitation. \nHowever the main issue I have is that the experiments are only performed on synthetic data. It would be good if we can have some experiments with real datasets.\nAlso the only baseline used is uniform sampling. My question is, since the authors address the first part of coreset building procedure as a k-means clustering problem, is it also possible to atleast sample points in the frst part using some existing k-means coreset building procedure and compare with that?\n\nI do not see any major negative societal potential impact of this work.", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "ZoYiiKwYNML", "reviewer": "Reviewer_V91b", "summary": "The paper considers the problem of clustering time series data. The authors provide a coreset for this problem, under some assumptions. The coreset size depends polynomially on the number of clusters k, the dimension d, and 1/\\varepsilon and the parameters related to the assumption on the data, and requires near-linear time to compute. \nThe authors validate their coreset empirically on synthetic data, as compared to a uniform random sample. They show that the coreset: (i) achieves better results can the random sample, and (i) can help accelerate the computational time, relative to the full data, by 1-2 orders of magnitude, with only a small compromise in the accuracy.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n- The problem is indeed very interesting and relevant.\n- The paper is well organized. \n- The overviews provided are very helpful, as well as the detailed comparison of Theorem 4.3 to the related previous works.\n- In overall, I really like the paper and its results.\n\nCons:\n- The contributions paragraph is very high-level, and lacks the important details (e.g., coreset size, actual computation time, etc.).\n- The coreset obtains an additive error of epsilon times f', where f' is a different cost function. This relation should be investigated more thoroughly, both in theory and in the conducted experiments.\n- While the analysis and proofs are indeed deep and non-trivial, the novelty of the results is not fully clear; It is unclear if this is the first coreset for such time-series data, and unclear whether existing works, which handle the same cost function but with static data, can be easily adapted to the case of time series data. This concern arises since, eventually, the provided coreset for time series data is basically a union between a coreset for entity level data (ignoring the time-series data for each entity), and a separate coreset for each entity. Hence, one might think that the novelty of the paper lies mostly in the successful decoupling of the time-series problem into two sub-problems with static data. I would recommend that the authors add a \"hardness\" paragraph that discusses this topic.\n- The hardness of computing a coreset for time series clustering is not discussed. Is there a provable lower bound for the coreset size? This can better justify the coreset sizes obtained in the paper.\n- The problem seems, in some sense, related to the problem of clustering input sets, or clustering shapes, as e.g., \n(i) “Sets Clustering”, Jubran et al.\n(ii) \"k-Means Clustering of Lines for Big Data\", Merom and Feldman.\n(iii) Works that handle probabilistic databases (for example \"Smallest enclosing ball for probabilistic data\" by Munteanu et al.\nEstablishing a connection to those problems seems very relevant.\n- Regarding the experiments: \n(i) how was the optimization problem solved on the full data? was it done similarly to the EM solution applied on the coreset?\n(ii) It seems a bit strange that the the proposed coreset achieves a 2x-8x acceleration in solving Problem 3.1 compared to the uniform sampling, as the random sample is computed much faster, and is of the same size as the corese. Can the authors elaborate on this?\n(iii) The dimension d tested was only d=2 (probably due to the large dependency, in theory, on d).\nHowever, as the theory in most coreset papers is far too pessimistic, it would be interesting to see this effect in practice for d>2. \n\n\nOther detailed comments:\n- There are some typos / writing issues / undefined variables. For example: \n(i) In the definition of the input set X, the subscript of the first element x_{i1} of every Xi does not have a comma, while the last element x_{i,Ti} does have a comma. It should be consistent. Also, Xi is said to be a subset of R^{Ti x d}. However, as Xi is not a set, the \"\\subset\" should be replaced with \"\\in\", and it should be R^{d\\times Ti} as there are Ti columns and d rows in Xi.\n(ii) The argmax in Line 37: it is unclear over what set are we maximizing the expression.\n(iii) Line 38: missing closing bracket.\n(iv) Line 80: \"where objective\" -> \"where the objective\".\n(v) Line 91: \"compared to uniform\", sentence not complete.\n(vi) Line 174: If i'm not missing anything, then P is undefined (should be P_X). Similarly in Definition 3.3.\n(vii) Line 182: Extra closing bracket.\n- The organization of the column titles in Table 1 are very confusing. I would recommend either spacing the titles more, or placing some vertical dividers in between unrelated columns.\n- An illustration figure to demonstrate the \"GMM clustering with time series data\" problem (even for d=2) would be very appreciated.\n\nI am willing to re-evaluate my score after addressing the above concerns.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "OZ_ogfqg8Sh", "reviewer": "Reviewer_eQJc", "summary": "The authors propose a novel coreset construction framework for the problem of clustering multivariate time series. To my knowledge, this is the first construction of coresets in this setting. The framework, as well as the proof scheme, is close to the work in [45], in which Lucic et al. studied the problem of coreset constructions for the MLE task under the GMM model. \n\nHere, the authors add to the GMM model a temporality and thus an additional autocorrelation in the underlying model. The proof's scheme is similar to that of [45] in the sense that they also reduce the GMM time series clustering problem to a $k$-means clustering problem (and then use more classical results for $k$-means from the state-of-the-art).", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The additional temporal dimension compared to GMMs makes the coreset algorithm and the proofs of the theorems more involved. Given the information provided in the proof sketches (I did not read the supplementary material), I did not find any error in the reasoning or computation; but I could not guarantee that there are no errors.\n\nThe idea of first sampling entities, and then a subset of time periods for each selected entities is quite natural. The way I see it, the first stage of the algorithm is very close to the work in [45], with a k-means++ based routine to estimate upper bounds of the k-means' sensitivity. Then, the second part of the algorithm (selecting time periods for each sampled entity) is close to the work in [34]. This work is a mix of ideas from [45] and [34].\n\nI am frustrated by the experimental section in which you only compare your work with uniform sampling. \n- What if you keep all entities but sample only time? What if you keep all time periods but sample only entities? \n- What if you forget the time in your time series and directly apply the algorithm from [45]? What gain do you truly get with your approach?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "9qdGIr5DLx_", "reviewer": "Reviewer_xadL", "summary": "This paper uses the Feldman Langberg sensitivity framework to compute coresets for time series clustering under a Gaussian Mixture Model.\n\nThis imposes additional challenges since there is an instance domain as well as a time domain to approximate. The mixture model introduces covariances and to reflect the time dependence there is an additional autocorrelation introduced on the time domain.\n\nThose covariance and correlation structures are being bounded in order to bound their impact on the sensitivities and after getting rid of all those structures the problem is reduced to a simpler clustering model for which sensitivity bounds are obtained more easily. \n\nThe resulting coresets are assessed empirically on synthetic data.\n\nThe writing is very good and the main body provides all information to understand even on a technical level, although the details are in the appendix.\n\nIn principle I would tend to accept this paper but knowing the previous literature on GMM as well as a recent coreset work on \"panel data\" my main impression is that the submission is just a dejavu of those two works.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "My main concern for rejecting this paper is a lack of novelty and significance:\n\n1) The model (with the assumptions imposed to get small coresets) seems inappropriate: When the covariance matrices have constantly bounded condition and the autocorrelation AR(1) is used, then every time series is just a random walk concentrated around their mean. This is very well behaved time series data.\n\nWhy is there no comparison or related work for maybe more appropriate time series (polygonal curve) clustering eg under dynamic time-warping or Frechet distance, and where values can oscillate arbitrarily. See for example the recent series of works by K. Buchin or A. Driemel or D. Rhode.\n\n2) Technically there is not more than already seen in the papers [23] where coresets for GMMs (with bounded condition) are developed. Why is the more recent generalization without this bound [25] being dismissed? I would rather deal with more general covariances but loose the log n factor.\n\nThe submission uses the same techniques as [34] for getting rid of the autocorrelations (of order q, here only q=1 is considered). It is simply by assuming that the correlation is bounded away from 1 and by applying Cauchy-Schwarz. In [34] the two-stage coreset construction for clustering of regressions was one of the novelties but here it is just the same again.\n\nThe authors try to sell it as new or different by pointing out the two weighting functions w(i) and w_i(j) which due to non-linearities can't be combined, but in principle it was the same in [34] up to finally defining w(i,j) = w(i) * w_i(j).\n\nanother thing that they point out that the component's cost functions are not bounded as in [34] but the bound on the eigenvalues is just the same, noting that the eigenvalues are dominating the costs in the GMM.\n\n3) Even on synthetic data the coresets show only slight improvements over uniform sampling. Since the authors are free to model the data in any way, they could at least simulate one data set that is particularly hard for uniform sampling where coresets show their strength. Currently it looks like if data follows the generating model, sensitivities are pretty uniform. Also, why is there no real-world data comparison? Is there even any real data that can be modeled similarly to the GMM model described here?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "no", "review_text": "", "extra_scores": {"ethical_concerns": "no", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: 
The paper suggests a coreset for clustering in the context of signals.
Indeed, there are too few coresets in this very active area.
There were concern regarding experimental results and novelty that the authors should address in the final version.
In addition, there are few coresets for signals that the authors should cite in the final version:

https://papers.nips.cc/paper/5581-coresets-for-k-segmentation-of-streaming-data
https://dl.acm.org/doi/abs/10.1145/2814569

Decision: Accept (Spotlight)