Unlike conventional clustering, fuzzy cluster analysis allows data elements to belong to more than one cluster by assigning membership degrees of each data to clusters. This work proposes a fuzzy C{ medoids algorithm to cluster time series based on comparing their estimated quantile autocovariance functions. The behaviour of the proposed algorithm is studied on di erent simulated scenarios and its e ectiveness is concluded by comparison with alternative approaches.
In classical cluster analysis each datum is assigned to exactly one cluster, thus producing a \hard" partition of the data set into several disjoint subsets. This approach can be inadequate in the presence of data objects that are equally distant to two ore more clusters. Fuzzy cluster analysis allows gradual memberships of data objects to clusters, thus providing versatility to re ect the certainty with which each data is assigned to the di erent clusters. An interesting overview of present fuzzy clustering methods is provided by [3]. Interest in this approach has increased in recent years. Proof of this is the large amount of publications in this eld (e.g. [6] and [5]).
In this paper, a fuzzy C{medoids algorithm to cluster time series using the quantile autocovariance functions is proposed. Motivation behind this approach is twofold. First, quantile autocovariances have shown a high capability to cluster time series generated from a broad range of dependence models [10]. On the other hand, the use of a fuzzy approach for clustering time series is justi ed in order to gain adaptivity for constructing the centroids and to obtain a better characterization of the temporal pattern of the series (see discussion in [7]). To illustrate the merits of the proposed algorithm, an extensive simulation study comparing our fuzzy approach with other fuzzy procedures has been carried out. Speci cally, we have focused on the classi cation of heteroskedastic models, which are of great importance in many applications (e.g. to model many nancial time series) and have received relatively little attention in the clustering literature.
Consider a set of p series S =
X (
Let X1; : : : ; XT an observed stretch of a strictly stationary process fXt; t 2
Zg. Denote by F the marginal distribution of Xt and by q = F 1( ), 2 [0; 1],
the corresponding quantile function. Fixed l 2 Z and an arbitrary couple of
quantile levels ( ; 0) 2 [0; 1]2, consider the cross-covariance of the indicator
functions I (Xt q ) and I (Xt+l q 0 ) given by
l( ; 0) = cov fI (Xt q ) ; I (Xt+l q 0 )g = P (Xt q ; Xt+l q 0 ) 0:
(
Function l( ; 0), with ( ; 0) 2 [0; 1]2, is called quantile autocovariance
function of lag l. Replacing in (
T 1 l
T l X I (Xt t=1 q^ ) I (Xt+l q^ 0 ) 0: (2)
As the quantile autocovariances are able to account for high level dynamic
features, a simple dissimilarity criterion between two series Xt(
dQAF
Xt(
Computing dQAF for all pairs of series in S allows us to set a pairwise dissimilarity matrix, which can be taken as starting point of a conventional hierarchical clustering algorithm. Alternatively, a partitioning clustering, such as the k-means algorithm, can be performed averaging the representations to determine the centroids. Then, dQAF is also used to calculate the distances between series and centroids involved in the iterative re nement of the cluster solution. 3
Time series are dynamic objects and therefore di erent temporal patterns may be necessary to characterize the serial behaviour in di erent periods of time. In other words, the series are not distributed accurately within a given number of clusters, but they can belong to two or even more clusters. This problem can be adequately treated using a fuzzy clustering procedure, which associates a fuzzy label vector to each element stating its memberships to the set of clusters. In this section we propose a fuzzy C-medoids clustering algorithm for time series by plugging the QAF-dissimilarity introduced in Section 2.
Let S = X (
p C min X X uimc ~; Each uic 2 [0; 1] represents the membership degree of the i-th series to the c-th cluster and the parameter m > 1 controls the fuzziness of the partition. As the value of m increases, the boundaries between clusters become softer and therefore the classi cation is fuzzier. If m = 1, the hard version of the clustering procedure is obtained, i.e. uic 2 f0; 1g, that leads to a classical K-means partition of S. The constraints PcC=1 uic = 1 and uic 0 ensure that no cluster is empty and that all series are included in the cluster partition.
The objective function (5) cannot be minimized directly, and an iterative algorithm that alternately optimizes the membership degrees and the medoids must be used. The update formula for the membership degrees is given by uic = 4 2 C
X c0=1 (i) (i) (c) 2 ! m1 1 3 1
2 (c0) 2 5 2 ; for i = 1; : : : ; p: (6)
Then, the QAF-based fuzzy C{medoids clustering algorithm is implemented as follows.
i. Pick an initial set of medoids e = n e(
p q = argmin1 i0<p X uim00c (i00) (i0) 2
2 i00=1
If the value of q is lower than the one obtained with e, then e = b. v. If eOLD = e or a maximum number of iterations is achieved then end algorithm. Otherwise, return to step ii.
The total number of clusters C has to be preset. For this task classical indexes
such as silhouette width or Krazanowski-Lai index can be used.
The proposed fuzzy algorithm was tested against two other fuzzy clustering
algorithms via simulation. In particular, the classi cation of heteroskedastic
time series was considered by simulating two di erent scenarios formed by (i)
GARCH(
R X (brk r=1 brk0 )2 ; with brz an estimator of the r-th coe cient r = ( r + r)+Pjm=in1(q;r) j r j , for the series z, z = k; k0. Parameter R determines the maximum number of autoregressive coe cients r. A GARCH{based fuzzy C-medoids clustering is proposed in [4] by considering the optimization problem:
p C R min X X uimc X (bri ^ ; i=1 c=1 r=1 brc)2 ; subject to 2. GARCH-based distance measure [1] given by dGARCH(X (k); X (k0)) = (Lk
Lk0 )0 (Vk + Vk0 ) 1 (Lk
Lk0 ) (9) with Lj = bj ; bj the vector of estimated parameters and Vj the estimated covariance matrix for Lj , for j = k; k0. An alternative GARCH-based fuzzy C-medoids clustering is proposed in [4] by minimizing:
p C X X uimc h(Li i=1 c=1
Lc)0 (Vi + Vc) 1 (Li
i Lc) ; (10) subject to PC c=1 uic = 1 and uic
0.
The three fuzzy clustering algorithms were performed using a fuzziness parameter m = 1:5 on N = 100 trials for each scenario. At each trial, the quality of the clustering procedure was evaluated comparing the experimental cluster solution with the true cluster partition. Two di erent agreement measures were used, namely the Gavrilov index [8] and the adjusted Rand index [9]. The mean values and standard deviations of these indexes based on the 100 trials using both hard and fuzzy cluster analysis are provided in Table 1.
Results from Table 1 show that the metrics based on quantile autocovariances and on the AR representation led to the best scores in Scenario 1 when the hard cluster is carried out. When the fuzzy approaches were considered, the behaviour of the dAR substantially worsened, while the very similar (even somewhat higher) results were obtained with dQAF . The worst results were obtained with the GARCH-based dissimilarity both for the hard and the fuzzy versions.
The metric based on quantile autocovariances also obtained the best results in Scenario 2, with indexes of agreement above 0:8 and a slight improvement by using the fuzzy clustering. The GARCH-based metrics, dAR and dGARCH where strongly a ected by the model misspeci cation and produced the worst results for both the hard and the fuzzy versions of the cluster analysis.
To assess the e ect of the fuzziness parameter in the partitions the algorithm was implemented for several values of m. However this results were here omitted due to the limitation of space. 5
In this section, the proposed fuzzy C{medoids clustering algorithm is used to perform clustering on a set of series of electricity demand. Speci cally, our database consists of hourly electricity demand in the Spanish market from 1st January 2011 to 31th December 2012. All data are sourced from the o cial website of Operador del Mercado Iberico de Energia1. Records corresponding to Saturdays and Sundays have been removed from the database because electricity demand is lower in the weekends. Thus we have 24 time series (one for each hour of the day) of length T = 731. Since all series are non{stationary in mean, the original series are transformed taking one regular di erence.
Table 2 presents the membership degrees for the case with two and three clusters. The results obtained for the two{cluster partition formed by C1 = fH24; H1; H2; H3; H4; H5; H6; H7g and C2 grouping the remaining series. The cluster C1 corresponds with the hours of the day where the electricity demand is low, while the C2 identi es the time of the day when the power consumption is greater. In the case of the three{cluster partition, the cluster C1 is divided in two subclusters. One formed with the hours of the day with the lowest demand of electricity, and a second cluster with an intermediate electricity consumption. 6
In this paper, we focus on the classi cation of time series featuring a fuzzy clustering algorithm in the framework of a partitioning around medoids. A dissimilarity{based approach is considered. In particular, we propose a C{medoids fuzzy clustering algorithm using an innovative dissimilarity measure based on the quantile autocovariances (dQAF ).
The simulation study shows that the proposed dissimilarity produces satisfactory results by performing fuzzy cluster analysis. The proposed clustering algorithm was tested against two GARCH{based fuzzy clustering algorithm present in the literature in two di erent heteroskedastic scenarios. The fuzzy clustering algorithm based on dQAF led to the best results. In fact, apart from dQAF , none 1 http://http://www.omel.es/files/flash/ResultadosMercado.swf ing heteroskedastic processes, thus emphasizing the usefulness of dQAF in this framework.
Note that a limitation of our procedure is that series are assumed to be strictly stationary and hence further research must be carried out. Although we have followed a dissimilarity-based approach, it is worthy to emphasize that model-based techniques can be also an interesting alternative. Likewise the fuzzy approach, the use of probabilistic models such as mixture models (see e.g. [2]) allows us to assign each datum to one single cluster although this assignment relies on a probabilistic approach since the mixing proportions are estimated from the data. Unlike the fuzzy approach, no fuzziness parameter is required by using mixture models, although the model selection problem must be solved in the latter case. International stock markets evidence. Mpra paper, University Library of Munich, Germany (2007), http://EconPapers.repec.org/RePEc:pra:mprapa:2074 2. Chen, W.C., Maitra, R.: Model-based clustering of regression time series data via apecman aecm algorithm sung to an even faster beat. Statistical Analysis and Data