![](https://csdnimg.cn/release/download_crawler_static/11340076/bg5.jpg)
for each time-series,) and then a suitable model distance
and a clustering algorithm (usually conventional clustering
algorithms) is chosen and applied to the extracted model
parameters [16]. However, it is shown that usually model-
based approaches has scalability problems [78], and its
performance reduces when the clusters are close to each
other [79].
Reviewing existing works in the literature, it is implied
that essentially time-series clustering has four components:
dimensionality reduction or representation method, dis-
tance measurement, clustering algorithm, prototype defini-
tion, and evaluation. Fig. 3 shows an overview of these
components.
The general process in the time-series clustering uses
some or all of these components depending on the problem.
Usually, data is approximated using a representation
method in such a way that can fit in memory. Afterwards,
a clustering algorithm is applied on data by using a distance
measure. In the clustering process, usually a prototype is
required for summarization of the time-series. At last, the
clusters are evaluated using criteria. In the following sub-
sections, each component is discussed, and several related
works and methods are reviewed.
1.4. Organization of the review
In the rest of this paper, we will provide a state-of-the-
art review on main components available in time-series
clustering plus the evaluation methods and measures avail-
able for validating time-series clustering. In Section 2, time-
series representation is discussed. Similarity and dissimilar-
ity measures are represented in Section 3. Sections 4 and 5
are dedicated to clustering prototypes and clustering algo-
rithms respectively. In section 6 evaluation measures is
discussed and finally the paper is concluded in Section 7.
2. Representation methods for time series clustering
The first component of time-series clustering explained
here is dimension reduction which is a common solution for
most whole time-series clustering approaches proposed in
the literature [9,80–82]. This section reviews methods of
time-series dimension reduction which is known as time-
series representation as well. Dimensionality reduction r epre-
sents the raw time-series in another space by transforming
time-series to a lower dimensional space or by feature
extraction. The reason that dimensionality reduction is
greatly important in clustering of time-series is firstly because
itreducesmemoryrequirementsasallrawtime-series
cannot fit in the main memory [9,24]. Secondly, distance
calculation among raw data is computationally expensive,
and dimensionality reduction significantly speeds up cluster-
ing [9,24]. Finally, when measuring the distance between two
raw time-series, highly unintuitive results may be garnered,
because some distance measures are highly sensitive to some
“distortions” in the data [3,83], and consequently, by using
raw time-series, one may cluster time-series which are
similar in noise instead of clustering them based on similarity
in shape. The potential to obtain a different type of cluster is
the reason why choosing the appropriate approach for
dimension reduction (feature extr action) and its ratio is a
challenging task [26]. In fact, it is a trade-off between speed
and quality and all efforts must be made to obtain a proper
balance point between quality and execution time.
Definition 2:. Time-series representation, given a time-
series data F
i
¼ f
1
; ::; f
t
; ::; f
T
, representation is transform-
ing the time-series to another dimensionality reduced
vector F
'
i
¼ f
'
1
; ::; f
'
x
no
where xo T and if two series are
similar in the original space, then their representations
should be similar in the transformation space too.
According to [83], choosing an appropriate data representa-
tion method can be considered as the key component which
effects the efficiency and accuracy of the solution. High
dimensionality and noise are characteristics of most time-
series data [6], consequentl y , dimensionality reduction meth-
ods are usuall y used in whole time-series cluster ing in or der to
address these issues and promote the performance. Time-
series dimensionality reduction techniques have progr essed a
long wa y and are widel y used with larg e scale time-series
dataset and each has its own features and drawbac ks. Accord-
ingly , many researches had been carried out focusing on
representation and dimensionality reduction [84–90].Itis
worth here to mention about the one of the recent compar -
isons on representation methods. H. Ding et al. [91] hav e
performed a comprehensive comparison of 8 representation
methods on 38 datasets. Although, they had investigated the
indexing effectiveness of representation methods, the results
are advantag eous for clustering purpose as well. They use
tightness of lo wer bounds to compar e representation methods.
They show that there is very little difference between recent
representatio n methods. In tax onom y of representations, ther e
are generally four representation types [9,83,92,93]:data
adaptive, non-data adaptive, model-based and data dictated
representation approaches as are depicted in Fig. 4.
Fig. 3. An overview of four components of whole time-series clustering.
Fig. 4. Hierarchy of different time-series representation approaches.
S. Aghabozorgi et al. / Information Systems 53 (2015) 16–3820