Automated Detection of Electric Energy Consumption Load Profile Patterns

Abstract

Load profiles of energy consumption from smart meters are becoming more and more available, and the amount of data to analyse is huge. In order to automate this analysis, the application of state-of-the-art data mining techniques for time series analysis is reviewed. In particular, the use of dynamic clustering techniques to obtain and visualise temporal patterns characterising the users of electrical energy is deeply studied. The performed review can be used as a guide for those interested in the automatic analysis and groups of behaviour detection within load profile databases. Additionally, a selection of dynamic clustering algorithms have been implemented and the performances compared using an available electric energy consumption load profile database. The results allow experts to easily evaluate how users consume energy, to assess trends and to predict future scenarios.

1. Introduction

The electricity sector liberalisation process led to investments both in improving existing measurement and communications infrastructure, and taking the measurement and actuation capacity to a more significant number of points in medium and low voltage networks. Therefore, the availability of data that informs about the state of the network is increasingly higher and more complete. All these systems are part of the so-called Smart Grids, or intelligent networks of the future, a future which is not so far. An important source of information comes from the energy consumption of customers, measured regularly (every hour, half hour or quarter hour) and sent to the Distribution System Operators from the Smart Meters making use of Advanced Metering Infrastructure (AMI). In this way, there is an increasing amount of information on the energy consumption of customers, being stored in Big Data systems. This growing source of information demands specialised data mining techniques which can take benefit from it, extracting automatically helpful and summarised knowledge.

Data mining techniques have been described as the intermediate step within a bigger process, called Knowledge Discovery in Databases or KDD, described as “the nontrivial process of identifying valid, novel, potentially useful and ultimately understandable patterns in data” [1]. This process covers the whole sequence of knowledge extraction in large datasets or, in recent years, in large amounts of data from the Internet of Things (IoT) [2] and from Big Data systems [3]. The KDD process comprehends the following steps [4]:

• Initially, the expert or data analyst studies the dataset and makes an assumption or states a hypothesis regarding the objective of the knowledge discovery process, or the model or relationship that may be found among the different variables or features of the data objects. The subsequent analysis of the data will be based on these initial hypotheses, which would at the end be validated upon the results obtained, or not. If the results are not satisfactory, the expert will perform new assumptions or hypotheses, therefore starting the KDD process again.
• Then, the data warehousing process [5] is performed. This step of the analysis comprises all the techniques and procedures to process erroneous or missing values in the data, filter noise, produce specific queries to access the data, and rearrange the information in the desired format to be analysed.
• Then, the selected data mining technique or techniques are applied, with the objective of extracting valuable relations or information from the data, in the form of patterns, models, association rules or other things.
• The next step is the visualisation of results, along with numerical and/or categorical indicators and information to help the expert to identify and evaluate the results.
• Finally, the expert has to perform an interpretation of the results. In this step, the expert will validate the initial hypothesis made concerning the underneath models or patterns able to summarize the data, obtain conclusions and extract knowledge from the results. In the case these results are not satisfactory, new hypotheses can be formulated, which will imply the need for further data mining analyses, therefore starting the KDD process again.

The KDD process makes use of many different algorithms and techniques from different research fields: Pattern recognition and classification, statistics, data visualisation, machine learning and artificial intelligence [6]. According to Mitra et al. [1], the issue that makes KDD different from other areas is that it is focused on knowledge discovery from large sets of data, including the overall process of “storage and accessing such data, scaling of algorithms to massive datasets, interpretation and visualisation of results, and the modelling and support of the overall human-machine interaction”. In recent years, the research field on KDD and data mining has started to move towards the analysis of data in Big Data systems using Big Data Analytics tools [7]. The objectives are kept the same, but the techniques have been adopted and have gone through an evolution process to be able to manage large amounts of unordered data from distributed sources, especially in the case of stream data mining, where the amount of available data per unit of time makes unavailable the traditional schema of loading the data and then performing a centralised analysis on them [7].

According to Mitra et al. [1], there are two main tasks performed by data mining algorithms: Descriptive and predictive tasks. The first deals with the description of the data, using patterns, for example, and the other with obtaining models that establish input–output relations among variables and predict future outcomes given the initial conditions and values of inputs. Beyond this division, further classifications can be given according to Han and Kamber [4], based on the type of data to be mined (and the type of database), and the specific objectives of the data mining process, or the kind of knowledge being mined. Regarding the types of databases, a detailed description can be found in the book by Han and Kamber [4] with the main types being: Relational, transactional, repositories, etc. Regarding the objectives of data mining, Han and Kamber group the techniques according to two main objectives: The static analysis of the data and the dynamic analysis of the data.

Static analysis includes all the techniques that aim to analyse data from a particular period, but without taking into account the temporal record in which the data were acquired as the objective of the analysis. The authors subdivide these techniques depending on the objective: Techniques for description and techniques for prediction. The description objective includes: The automated preparation of summaries of the resulting classes (summaries and class description); mining or obtaining frequent patterns (frequent pattern mining); the classification of objects clustering or segmentation analysis; and out-of-range data detection (outliers). As part of the prediction objective, the techniques included are: Association between variables, correlation and the development of prediction models, through regression, neural networks or other techniques.

Regarding dynamic analysis, the objective is to evaluate and analyse the trend of the data series, whether they are temporal or sequential. The same objectives described for the static analysis can also be applied to the dynamic case. However, it should be taken into account that the inclusion of the temporal dimension as an objective of the analysis may imply the modification of the techniques used in the static analysis, increasing its complexity (and its difficulty for an understandable visualisation of the results).

This work studies the application of state-of-the-art techniques for dynamic clustering of available databases of load profiles from Smart Meters energy consumption data. In particular, the use of data mining techniques to obtain and visualise temporal patterns characterising the users of electrical energy (grouping them according to these patterns in a small number of groups or clusters) is the main aim. This will allow the evaluation by experts of how users consume energy, both during the day and during a sequence of days, then it will be possible to assess trends and predict future scenarios.

The paper is structured as follows. First, a review is done about the most common clustering techniques (Section 2), describing both the most used similarity measures for static (Section 2.2), and dynamic (Section 2.3) data analysis. Secondly, the static clustering techniques (Section 3) are presented as an introduction. Then, the dynamic clustering techniques are further described (Section 4) in three subsections, taking into account the classification of the algorithms according to how the data are analysed: The direct analysis on the raw time series (Section 4.1), the analysis applied on a transformation of the original dataset (Section 4.2), and the analysis applied on the parameters of models obtained from the original data (Section 4.3). In Section 5, a set of these techniques is selected and applied to a database of hourly energy consumption values for a sample of residential customers, comparing the results among algorithms by defining quantitative indicators of validity and observing the resulting patterns (Section 5.2). Finally, Section 6 includes a summary with the main conclusions obtained.

Table 1. Notation.

$x_{ij}$	characteristic j of object i
$c_{kj}$	characteristic j of centroid k
N	number of objects
c	numer of centroids
$dist(i,k)$	function distance among two objects, i and k
d	number of characteristics (dimension) of the objects
${\mu }_{ki}$	fuzzy membership of the object i to the cluster k
U	fuzzy membership matrix, with c rows and N columns
m	fuzziness index, higher than 1 (usually 2)
J	cost index to minimize
p	total number of samples or time instants
$\overline{x}$	mean value (or vector of mean values per dimension) of a series x of objects or data

summarises the notation used throughout this document.

2. Clustering Techniques

Clustering is the “unsupervised learning task whose objective is to decompose a set of objects into subsets or clusters, based on a measure of similarity” [8]. The resulting classes or clusters are therefore groups of objects according to a mathematical measure of similarity (the most similar objects are grouped together). From each resulting class, an object is usually obtained that is the pattern, prototype or characteristic object of the class, and represents all the objects that belong to that class. This object is called centroid, and it can be calculated as the mean value of all the objects that belong to the class, or by other formulations. Figure 1 presents an example of clustering into classes a set of objects with two dimensions or characteristics, and their corresponding centroids, calculated in this case as the center of gravity of each class.

However, before choosing a specific clustering algorithm, it is essential to perform some selections according to the type of data to be analysed. The decisions are related to the static or dynamic nature of the data, and how similarity between the data must be understood. Section 2.1–Section 2.3 will give hints concerning this previous selection.

2.1. Taxonomy of Clustering Techniques

Clustering algorithms can be classified according to different criteria:

• The dynamic nature of data and classes. This criterion classifies algorithms based on whether they are designed for dynamic or static data, and for a fixed or time-varying number of classes.
• The way the data are analysed. This criterion classifies the algorithms according to the strategy or technique they use to analyse the data, and specifically if they carry out an initial transformation of the same into another set of data on which they perform the analysis.
• The number of dimensions or characteristics of the data. This criterion classifies algorithms according to the number of dimensions of the data they analyse.

The first criterion, the dynamic nature of the data and the resulting classes, classifies the segmentation algorithms into four types, as can be seen in

Table 2. Types of segmentation algorithms according to the dynamic nature of the data and classes.

Type	Data	Classes	Segmentation Type
1	Static	Static	Static (classic)
2	Static	Dynamic	Dynamic. Centroids and classes are updated with each new cycle
3	Dynamic	Static	Dynamic. The centroids are represented by trajectories of their dimensions. Fixed number of classes
4	Dynamic	Dynamic	Dynamic. The centroids are represented by trajectories of their dimensions. The number of classes is updated with each new cycle

, described by Weber [8] and they are the following:

• The data, although they can be time series, are treated as static. The segmentation algorithms are therefore focused on static analysis. This is the case of the example shown in Figure 1.
• While they can be time series, the data are treated as static. The number of classes, however, is variable. This is the case when the database is partitioned and batch processed sequentially, as the example in Figure 2 indicates. With each batch the number of classes may vary, showing a variation in the trend of the data and its composition. Therefore, it is necessary to implement techniques that make a correspondence between the classes of one batch and the next [9], taking into account the possibility of the formation of new classes, the disappearance of classes that had been formed previously, the merge of two or more classes, and the separation of a class into smaller classes.
• The data is treated as dynamic, varying with time; therefore the objects become trajectories of each characteristic of the object or data. The number of classes is fixed. The resulting centroids are defined by the trajectories of their dimensions, which represent the evolution in time of the objects belonging to each class. An example of this segmentation analysis is shown in Figure 3.
• The data is treated as dynamic, varying over time, as in Type 3. The number of classes is not fixed, and can vary with each batch or cycle. Therefore, the same techniques for Type 2 must be taken into account. Figure 4 shows an example of this type of analysis.

In a simplified way, the clustering techniques can be divided into static (types 1 and 2) and dynamic (types 3 and 4); then the basic techniques for types 1 and 3 are defined, and they are applied repeatedly (in batches) for types 2 and 4. Thus, Section 2 focuses on type 1 static techniques for the analysis of data in a particular time period, but without considering the analysis of the time variable of the data. Section 2.3 presents type 3 dynamic analysis techniques to analyse time trends in data series, both batch or time continuous.

As explained before, the measure of similarity is key for clustering; the most employed clustering is described for type 1 static in Section 3 and for type 3 dynamic in Section 4.

2.2. Similarity for Static Data

In order to select the most appropriate distance as a measure of similarity to compare two objects in a particular problem, the nature of the data and its characteristics or dimensions must be considered:

• If the objects include qualitative features or values selected from a list of categories, then previously described quantitative distances are not suitable to evaluate the similarity among the objects. In this case, a specific distance for qualitative data similarity must be used. For example, a measure can be used from the matching or coincident coefficient family of distances, which can only take two possible values (0 or 1) if the characteristics of both objects are coincident or not. Two of these distance measures are the simple matching coefficient [10], and the Jaccard distance [11].
• If all the characteristics or dimensions of the objects are quantitative or numerical, then quantitative similarity measures can be used, and the two more used are described next.

2.2.1. The Minkowski Metric

This measure of similarity for two objects $X_i$ and $X_k$ is described in (1), where d is the number of characteristics or dimensions of both objects, and r is a parameter that determines variants of this metric. The most known of these variants, defined in (2), is obtained when $r$ = 2, and is known as Euclidean distance. The Euclidean distance is the shortest distance among two points, and is one of the most used quantitative measures of similarity in literature clustering algorithms.

$$dist(i,k)={\left(\sum _{j=1}^d{|x_{ij}-x_{kj}|}^r\right)}^{\frac{1}{r}},r\ge 1$$

(1)

$$dis{t}_E(i,k)=\sqrt{{(x_i-x_k)}^T(x_i-x_k)}=\parallel x_i-x_k\parallel$$

(2)

2.2.2. The Mahalanobis Distance

The Mahalanobis distance normalises each one of the data characteristics of the objects to zero mean and unity variance. In order to do so the distance (3) includes the covariance matrix of the objects (4) in the term $\phi$.

$$D(i,k)=\sqrt{{(x_i-x_k)}^T{\phi }^{-1}(x_i-x_k)}$$

(3)

$$\phi =\frac{1}{N}\sum _{k=1}^N(x_k-\overline{x}){(x_k-\overline{x})}^T$$

(4)

If the case is given that ${\phi }^{-1}$ is the identity matrix, then the result is the previously described square of the Euclidean distance.

2.2.3. Selection of a Suitable Distance Measure

Therefore, to compare numerical characteristics of objects, like in the case of energy consumption load profiles, one of the measures defined above (or any of the others described in the literature) can be used.

The choice can be made based on the scale of the values in the different dimensions. If all the characteristics of the objects have a similar order of magnitude, the Euclidean distance can be applied directly to the data without normalising. In contrast, the Mahalanobis distance including the matrix of covariances must be used to apply automatically a normalisation of the values in all the dimensions of the objects.

In any case, it is always recommended to normalise the data before analysing it. If normalising is not possible, there are distance measures that allow clustering data without normalisation, although its dimensions have very different orders of magnitude. In this case, clusters with various geometrical forms [12] are obtained: The Euclidean distance lead to hyperspherical clusters, the Mahalanobis distance hyperellipsoidal clusters, and adaptive norms (as those of the GK Gustafson-Kessel [13] algorithm) obtain clusters with varying forms but constant volume.

2.3. Similarity for Dynamic Data: Time Series Clustering

Next, the three more common similarity measures used in the literature for time series clustering are presented: The coefficient of correlation (Section 2.3.1), the DTW distance (Section 2.3.2), and the Kullback–Leibler distance (Section 2.3.3).

2.3.1. Correlation

The analysis of correlation gives a measure of linear relation among two series of data. The more common coefficient of correlation for comparing two series of data i and k of the same longitude p, is the coefficient Pearson of linear correlation, described in (5), where $\overline{x}$ is the mean value of the series of data and s is the standard deviation of the corresponding series (6).

$$corr(i,k)=\frac{\frac{1}{p}{\sum }_{r=1}^p(x_{i_r}-{\overline{x}}_i)(x_{k_r}-{\overline{x}}_k)}{s_i{s}_k}$$

(5)

$$s=\sqrt{\frac{{\sum }_{r=1}^p{(x_r-\overline{x})}^2}{p}}$$

(6)

The correlation coefficient can take values between −1 and 1; 1 shows a perfect correlation between the two data series; −1 also indicates that the two objects are correlated, but his trend is reverse (if the value of an object increases, the value of the other is reduced in the same proportion). A coefficient of correlation 0 indicates that there is no correlation between the series of data, and therefore it can be said that both series are linearly independent.

2.3.2. Dynamic Time Warping

Dynamic Time Warping or DTW [14,15] is a technique used to compare two time series that can have different longitudes or sampling periods. DTW looks for the optimal correspondence between the two time series regarding this shape.

Given two time series, R and S, of length n and m, respectively, the matrix $d\left(nxm\right)$ of distances is defined, where each element $d(i,j)$ corresponds with the distance among $R_i$ and $S_j$ (calculated using the Euclidean distance, for example). It defines the warping path as a vector $W=w_1,w_2,\cdots w_k$ of distances among R and S that has to fulfil some conditions [16]:

• Delimitation: This condition establishes the principle and the end of the alignment in the vertices of the matrix $d\left(nxm\right)$, i.e., $w_1=[1,1]$ and $w_k=[n,m]$.
• Continuity: Given $w_{k-1}=[i_{k-1},j_{k-1}]$ and $w_k=[i_k,j_k]$, then $i_k-i_{k-1}\le$ 1 and $j_k-j_{k-1}\le$ 1. This condition ensures that the elements of the alignment are adjacent.
• Monotonicity: Given $w_{k-1}=[i_{k-1},j_{k-1}]$ and $w_k=[i_k,j_k]$, then $i_k-i_{k-1}\ge 0$ and $j_k-j_{k-1}\ge 0$, having to fulfil at least a strict inequality. This condition forces the alignment to advance towards the vertex of the matrix of distances.

The path of optimum alignment is the one that, fulfilling the previously described conditions, minimises the sum of the square distances for the complete path, as can be seen in (7).

$$DTW{(R,S)}^2=\underset{W}{\min }\left\{\sum _{i_k,j_kϵW}d{(i_k,j_k)}^2\right\}$$

(7)

This optimised sequence of distances can be obtained through the accumulated matrix D method [16], following the formulation in (8).

$$\left\{\begin{array}{c}D[i,1]=\sum _{k=1}^{i}d(r_k,s_1)\hfill \\ D[1,j]=\sum _{k=1}^{j}d(r_1,s_k)\hfill \\ D[i,j]=d[i,j]+\min \left\{\begin{array}{c}D[i-1,j-1]\hfill \\ D[i-1,j]\hfill \\ D[i,j-1]\hfill \end{array}\right.\hfill \end{array}\right.$$

(8)

From this matrix D, the points of optimum alignment are obtained recursively, starting from the last point ($p_L$) and following the formulation described in (9).

$$\begin{array}{c}{p}_L=(N,M)\hfill \\ p_{l-1}=\left\{\begin{array}{ll}(1,m-1)& \mathrm{if} n=1\\ (n-1,1)& \mathrm{if} m=1\\ \mathrm{argmin}\left\{\begin{array}{c}D[n-1,m-1]\hfill \\ D[n-1,m]\hfill \\ D[n,m-1]\hfill \end{array}\right.\hfill & \mathrm{in}\mathrm{any}\mathrm{other}\mathrm{case}\hfill \end{array}\right.\hfill \end{array}$$

(9)

2.3.3. Kullback–Leibler Distance

Given two distributions p and q in a series T, the relative entropy or distance of Kullback–Leibler [17] is defined as the divergence among two distributions of probability calculated using (10).

$$D_{KL}[p\parallel q]=\sum _{t\in T}p\left(t\right)\log \frac{p\left(t\right)}{q\left(t\right)}$$

(10)

The Kullback–Leibler distance is used as a dissimilarity measure. In [18], for example, it is used as a measure of the increase in divergence that would be produced when two clusters are merged.

2.3.4. Other Similarity Measures for Dynamic Data

There are other distances used as similarity measures in the literature to compare time series, and also distances very specific to application can be developed like those presented in [19] or [20]. The work of [21] is a good review, and the authors present an empirical evaluation of seven groups of similarity measures applied to 45 different time series. In any case, the distance selection requires a previous analysis of the nature of the available data by following the same rules explained for static data (Section 2.2) with this initial. In both cases, as will be seen next, the distance is one of the main characteristics within the static (Section 3) or dynamic clustering (Section 4), together with the clustering algorithm and the optimisation techniques.

3. Clustering Algorithms for Static Analysis

While the aim of the paper is the use of dynamic clustering techniques for time series load profiles as dynamic data, most dynamic algorithms are briefly described next. Most clustering algorithms for static analysis described in the literature are variations or modifications of these two algorithms: The K-means and the FCM. A complete review of clustering algorithms for static data in the literature is presented in the works of [22] or [4].

3.1. K-Means

The K-means algorithm [23] is one of the first and more used clustering algorithms. Its name refers to the number k of classes to look for in the set of data, and it is an input parameter for the algorithm. The algorithm minimises the cost function defined in (11). This cost function is calculated as the sum of all the sums of the distances of the centroids of the classes to the objects that belong to them. Therefore, the lower these distances, the more compact the clusters, and the lower the value of the function of cost. The algorithm procedure to achieve this aim is as follows:

• Select c objects of the dataset, which will be the initial centroids. This selection influences the final result. Therefore, a suitable representation of the existing patterns must be done for the algorithm convergence to a global optimum [6]. In order to do so, a heuristic selection or based on previous knowledge of the patterns must be done, or algorithms adapted for the initial selection of prototypes can be used, such as the algorithm K-means ++ [24].
• Compute all the Euclidean distances of the remaining objects to the centroids, and assign each object to the cluster with a lower distance.
• Recompute centroids as the mean value of all the objects belonging to each class.
• Go back to step 2, until some ending condition is fulfilled, like achieving a maximum number of iterations, or that the value of the cost function does not vary above some predefined threshold between two consecutive iterations.

$$J=\sum _{k=1}^c\left(\sum _{i,x_i\in c_i}{\parallel x_i-c_k\parallel }^2\right)$$

(11)

3.2. Fuzzy C-Means (FCM)

Bezdek and Dunn developed the FCM algorithm [25,26]. It applies fuzzy logic [27] to the K-means algorithm. The cost function defined in (11) is modified as presented in (12), so that the sum of distances is weighted by the fuzzy membership (${\mu }_{ki}$) of each object to each cluster subject to (13), i.e., the sum of all the fuzzy memberships of an object to all the clusters has to be 1.

$$J(Z;U,C)=\sum _{k=1}^c\sum _{i=1}^N{\left({\mu }_{ki}\right)}^m{\parallel x_i-c_k\parallel }_B^2$$

(12)

$$\sum _{k=1}^c{\mu }_{ki}=1$$

(13)

The expression $\parallel x_i-c_k{\parallel }_B^2$ is a measure of similarity described in (14), where matrix B defines the geometry of the clusters. If B is the identity matrix, then the similarity measure is the Euclidean distance (2). In contrast, if B is the inverse of the objects covariance, then the result is the Mahalanobis distance (3).

$$\parallel x_i-c_k{\parallel }_B^2 ={(x_i-c_k)}^{T}B(x_i-c_k)=D_{ikB}^2$$

(14)

The iterative minimisation of the objective function gives two formulas for centroids and fuzzy membership calculation described in (15) and (16). The procedure of the FCM algorithm is described next:

• Initialise fuzzy membership matrix U with random values.
• Calculate the centroids as described in (16).
• Calculate the distances of objects to the centroids of each class, according to the measure of similarity described in (14).
• Recompute fuzzy membership matrix U, according to (15).
• Go back to step 2, until some ending condition is fulfilled, like achieving a maximum number of iterations, or that the value of the fuzzy memberships do not vary above some predefined threshold between two consecutive iterations.

$${\mu }_{ki}=\frac{1}{{\sum }_{p=1}^c{\left(\frac{D_{ikB}^2}{D_{ipB}^2}\right)}^{\frac{2}{m-1}}},1\le k\le c,1\le i\le N$$

(15)

$$c_k=\frac{{\sum }_{i=1}^N{\left({\mu }_{ki}\right)}^m{x}_i}{{\sum }_{i=1}^N{\left({\mu }_{ki}\right)}^m},1\le k\le c$$

(16)

3.3. Selection of the Static Clustering Algorithm According to the Application

In general, the algorithm (or set of algorithms) to apply depends on the nature of the data to analyse. This previous study of the objects and their characteristics will lead to a good selection among the algorithms described in the literature, and the decision will depend on whether the employed similarity measure (distance) allows comparing the objects in the set of data. For example, in [12], the authors use fuzzy clustering algorithms for the identification of local models of non-linear processes. The algorithms implemented are the FCM, the GK, and other algorithms, like the AFCRC (Adaptive Fuzzy C-Regression models with Convexity enhancement) [28], which makes use of a weighted combination of distances including the minimisation of a prediction error of the model. In [29], the authors present a clustering algorithm for the online identification of fuzzy models. The algorithm is called the Method of Evolutionary–Agglomerative Clustering, and the Euclidean distance is used for each step of the incremental clustering every time new data are available for the analysis, and allowing merging and eliminating clusters.

The authors [30] use the K-means algorithm over an SOM (Self-Organizing Map) [31] classification of profiles of energetic consumption of 24 daily values in a sample of domestic clients. In this case, all the dimensions present the same scale (energy data with the same order of magnitude), and therefore the Euclidean distance can be applied as a measure of similarity to clusters concerningthe spatial distribution given by theSOM net.

In [32], K-means is applied on a set of quantitative indicators weighted by importance to detect possible sources of water pollution. Jeong, H. et al. [33] uses K-means clustering on load profiles of residential customers in combination with extreme points and demographic characteristics. On the other hand, in [34] presents a fuzzy clustering algorithm based in the Fuzzy K-Partition [35] that employs a specific measure to make possible the clustering of categorical or qualitative data.

For the analysis of visual information, the authors [36], for example, apply the MeanShift algorithm clustering [37] to identify and group three-dimensional objects of a cloud of points obtained by a LIDAR (Laser Imaging Detection and Ranging) sensor. The algorithm MeanShift clusters the objects according to probability density functions that explain the set of data. In [38] the Multi-Objective Fast Generalized Fuzzy C-Means or MOFGFCM clustering is used to analyse SAR (Synthetic Aperture Radar) images. This algorithm optimises two cost functions specifically defined for the analysis of images: The FGFCM algorithm [39] and the Xie-Beni or XB [40] index.

4. Clustering Algorithms for Dynamic Analysis

In this section, clustering algorithms with the aim of dynamic analysis of the data are presented, including among them time series data. These techniques are more complex than those presented in the previous section, although they are based on them, and the understandable visualisation of the results is much more difficult in this case.

Dynamic techniques can be classified depending on the number of characteristics or dimensions of the objects, and algorithms are typically classified into two types: Those that make segmentation of objects of only one dimension (like the values of an electrocardiogram), and those that make segmentation in objects of n dimensions. A more suitable classification of the algorithms is based on how the data are processed. Liao [41] detects three different methods of analysis in the clustering algorithms for dynamic analysis: Process the time series in its original form, transform the data into a reduced representation according to its characteristics and clustering, or obtain models that represent the data prior to the segmentation.

Next, the literature algorithms are described according to the way that the data are processed. Nevertheless, in the description of the algorithms this classification is also included according to the dynamic nature of the data and the clusters, and whether the algorithm is designed for data of one dimension or more. The following information has been extracted from previous reviews made by several authors, such as [41,42,43,44].

4.1. Raw Time Series Data Clustering

The algorithms that perform the clustering of the time series in its original (raw) form are in most cases modifications of an equivalent algorithm for static analysis, where the similarity measure is substituted by a distance suitable to compare two series on the data.

The first developments were done in the decade of 1990. In [45] the Ward Generalised criterion [46] was used to develop a procedure of cluster reorganization for the time where, from an initial partition, the objects were reassigned to the clusters in each iteration applying a measure of similarity by minimising the Ward function ($p\left(C\right)$, with p being a function representing the objects’ adequacy concerning the clusters they belong to). This process is repeated for all the characteristics or dimensions of the objects at each iteration, having therefore a matrix of similarity measures and obtaining a global value of similarity as the weighted sum of all matrix values. Other authors have used this approach [47] but applying other clustering techniques (for example, K-means, FCM or genetic algorithms) to analyse multivariable time series with different lengths.

In [48] modified FCM is presented where the correlation Pearson is used as a similarity measure to compare fMRI (functional images of magnetic resonance) time series. On the other hand, [49] uses two similarity measures (the distance Kullback–Leibler and the Chernoff measure) to classify time series with different patterns.

In [50] hierarchical clustering is applied to identify patterns and trends in different time periods (days, weeks, seasons) in one-dimensional time series, and it is applied to a laboratory energy consumption. The Euclidean distance is used to calculate similarities among load profiles and classify them into clusters.

The authors [51] develop a similarity measure to be used in the case of time series with noise. The measure is based on the seasonality concept: A normalised load profile is defined for each cluster as a function of the date (along the year) after deleting any external factors other than those that can influence the data evolution. The result is a distance equivalent to a weighted Euclidean distance where elements with high standard deviation have less importance in the calculation of the distance.

Other authors propose developing specific algorithms for time series clustering. In [52], for example, Vector Quantization (VQ) is presented for obtaining clusters in data fRMI. The algorithm, similar to SOM (Self-Organizing Map), gets representative patterns of the evolution of the data in greyscale.

In [53], the Computational Verb Theory [54] is used for stock market time series. The authors define three computational verbs: Increase, decrease and remain. The clustering algorithm calculates the distances among the series of data and these three verbs, and then makes the clustering.

In [55], the STS Short Time Series distance is used as a similarity measure to catch differences in the shape of time series. The authors develop the FSTS (fuzzy short time series) algorithm by modifying FCM with STS distance. This distance is defined as the square difference of the slopes of two time series in an interval of temporary series, and it is, therefore, a measure of the rate of change in the evolution of both time series.

In [56], a two-step clustering method is proposed. In the first step, multivariable data are converted into one-dimensional time series by applying a static clustering algorithm, like the K-means. This result is somehow similar to state variables of a process. In the second step, the clustering algorithm is applied again to cluster the variables in several classes. In the first step, the author uses the Euclidean distance, and, in the second step, different similarity measures are used, like DTW or the Kullback–Leibler distance [41].

Moreover, for the case of Type 3 clustering algorithms described in Table 2, Weber [8] describes the algorithm called FFCM or Functional Fuzzy C-Means. This algorithm is presented as a generalisation of FCM for the dynamic analysis. In the algorithm, the distance d between two trajectories, f and g, is computed as follows:

• Define the fuzzy membership function “almost zero” $\left(\mu \right(f\left(x\right)\left)\right)$. This membership function is symmetric, and achieves the maximum value of 1 when x equals zero. The form of the function can vary, although Weber defines a Gaussian function whose value rapidly decreases as the value of x increases.
• Compute the similarity function $s(f,g)$ between two trajectories f and g, as the fuzzification of the difference between them, i.e., $s(f,g)=\mu \left(f\right(x)-g(x\left)\right)$.
• Compute the distance between the two trajectories f and g as the inverse of the similarity, i.e., $d(f,g)=(1/s(f,g\left)\right)-$1.

The FFCM algorithm calculates the membership of an object i to a class j for each iteration using (17), where $x_i$ represents the feature vector of the object i, and $c_j$ and $c_k$ are the centroids of the classes j and k, respectively.

$${\mu }_{ij}=\frac{1}{{\sum }_{k=1}^c{\left(\frac{dist(x_i,c_j)}{dist(x_i,c_k)}\right)}^{\frac{2}{m-1}}}$$

(17)

In the description of the algorithm FFCM, Weber indicates that, if the trajectories are defined as sets of series of real values, a numerical distance can be applied, like the Euclidean distance, substituting, therefore, the operator of distance d.

Some interesting works for raw data analysis are those that present developments that look for a better interpretation of the time evolution of the identified patterns. For example, Meesrikamolkul et al. [57] propose a modified K-means clustering algorithm for time series, the Shape-Based Clustering, where the Euclidean distance is replaced by a Dynamic Time Warping (DTW) alignment between time series. Since the computational cost of the DTW is high, the authors present a method to obtain the representative element from each cluster called Ranking Shape-based Template Matching Framework (RSTMF), which can average a group of time series effectively but take as much as 400 times less computational time than that of a previous method called STMF (Shape-based Template Matching Framework).

In [58], the authors present a modification of the FCM algorithm for time series data, defining the key points in a time series as the group of points that describe, implicitly, how a series changes at a particular time. These points usually represent specific events, such as the start or the end in a tendency of upward or downward, the peak or the bottom of the series. The key points reveal the dynamic aspect of a given time series. The authors present a study of the dynamic switching of the time series among a fixed number of clusters, over time, based on the membership coefficient at each step.

In [59], the authors present a clustering algorithm for clustering spatio-temporal data where the Euclidean distance is replaced by an augmented distance, which is the weighted sum of two Euclidean distances: The comparison of the spatial components, and the comparison of the temporal features. This modification is later extended in [60] to n features or dimensions with the concept of blocks or groups of similar features, computing a weighted sum of Euclidean distances where the different weights are obtained by Particle Swarm Optimisation (PSO) [61].

A new modification is presented in [62], where the algorithms FCM, Fuzzy C-Medoids [63], and a third hybrid technique that uses both, are modified, and a DTW distance is used as the similarity measure to cluster one-dimensional time series data. The authors indicate that the use of the DTW is appropriate only in those cases when the similarity is sought between the shapes of the data objects, and depending on the nature of the data themselves.

Finally, Benítez, I. [64] proposes a framework where different static clustering techniques can be employed for dynamic analysis using the modification/substitution of the similarity measures by others, then allowing comparison between time series. The aim is to obtain clusters (and prototypes) showing the evolution of the data dimensions along time.

4.2. Feature-Based Time Series Data Clustering

As stated by Fu, T.C. [44], one of the objectives of time series processing is the transformation of the data to a reduced dimensionality or a summary or reduced amount of representative values before the clustering process.

In this sense, Wilpon, J. et al. [65] obtains clusters of spoken sentences by the combination of word patterns. The clusters evolve, combining different patterns. Different techniques to get the cluster centers such as minmax computation or averaging, are presented. A modified K-means algorithm is presented, where the similarity between time series is computed applying the log-likelihood distance proposed by Itakura [66], based on autocorrelation coefficients.

In [67], the authors perform clustering on vibration sensor time measures from industrial machine tools to serve as a predictive maintenance diagnosis. First, the time transients are identified from the raw data, by comparison with regular use steady state patterns. Then, this information is used to compute Self Organizing Feature Maps (SOFM).

Ref. [68] performs feature-based clustering on fMRI data, based on the cross-correlation function, presented in a previous work in [69]. The raw data are reduced in size by a selection process of only relevant data from the magnetic resonance that can be representative to form the different clusters. Cross-correlation is applied between the fMRI data and a function defined as the “excitation paradigm”. The resulting correlation indices are used for the clustering process, along with features or indices such as the strength of activation or the response delay.

Ref. [70] compresses the input patterns by a perceptually important point (PIP) identification algorithm, replacing the original data by a group of PIPs, thus reducing dimensionality. Then, the authors identify patterns making use of SOM applied to data sequences segmented by a sliding window, to mine frequent patterns in the temporal series.

The work in [71] applies dimensionality reduction on the time series data making use of the Haar wavelet transform. The authors present a modified incremental K-means clustering, where the Haar wavelet is applied to the data, and the centers from the clustering results are used as inputs for another clustering at a more satisfactory resolution level, proceeding this way until the termination criterion is met. The same approach, although with different techniques, is presented in the work of [72]: An incremental clustering for time series is shown, based on the identification of the Longest Common Subpaths (LCSS) from dimensionality reduced time series picked randomly. Then, a fuzzy clustering, such as the FCM, is applied, to create new classes dynamically, modify existing ones, and/or remove unchanged clusters. Ref. [73] finds groups in commercial and industrial weekly load patterns for long-term energy planning with a similar wavelet approach.

In [74], the multi-solution piecewise aggregate approximation (MPAA) transform is presented. The technique is an iterative segmentation of a time series in lower dimension sequences of the average values. In each level of dimensionality reduction, K-means clustering is applied, and the intra-cluster error is compared with the Hoeffding bound [75], as a stopping condition. The clustering algorithm is then used in this work for data stream clustering, by applying the nearest neighbour assignment of new incoming sequences to existing clusters, and then re-computing the MPAA clustering process only on the affected cluster.

The authors [76] propose clustering time series using kernel density-based clustering. The kernel-based clustering method comprises two parts: A nonlinear transformation that maps data points from a low-dimensional input space to a high-dimensional feature space induced by an inner product kernel or a Mercer kernel, and a learning algorithm to find linear patterns in that feature space. The use of a density-based clustering algorithm, such as DBSCAN (Density-Based Spatial Clustering of Applications with Noise) [77] avoids defining the number of clusters to be found as an input parameter. Ref. [78] performs a dimensionality reduction of the raw time series data by applying the Independent Component Analysis (ICA), a statistical method similar to Principal Component Analysis (PCA) [79] and Factor Analysis. This similarity measure is then used in a modified K-means algorithm.

In [80], the Symbolic Aggregate Approximation (SAX) is used to compute summaries of the time series in the form of histograms of SAX values, inspired by the bag-of-words summarisation of text documents [81]. The resulting summaries are then clustered by a hierarchical clustering algorithm.

Autocorrelation function coefficients are employed by [82] to determine similarity between time series data, computing the Euclidean distance between these coefficients. A modified fuzzy C-means is then applied iteratively to assign the cluster membership of the time series data dynamically.

In [83], a clustering process in two levels of granularity analysis is proposed. In a first level, the data is processed and summarised by applying the SAX. Then, these summaries are clustered, by applying the density-based CAST clustering algorithm [84]. On the resulting clusters, a second CAST clustering is then applied, making use of the DTW similarity to compare sequences of unequal length. A similar approach is presented in [85] to cluster vehicle trajectories in two steps: First by start-destination coordinates, and then applying DTW to cluster the entire trajectories by similarity.

The authors in [86] propose the Piecewise Cloud Approximation function (PWCA) to reduce the dimensionality of time series. The time series is first segmented into frames, and each frame is transformed into a cloud model representation, defined by three variables: Ex (the Expected value, or mean of the segment), En, which is the Entropy, or uncertainty in the measurements, and Hex, which is a hyper-entropy, or an uncertainty measurement of the entropy En, and reflects the cloud’s thickness.

The most interesting works regarding feature-based clustering are those focused on obtaining summaries for a better description (and therefore, interpretation) of the clusters. Fulcher and Jones [87] develop summaries from the analysis of the data object features applying a suite of techniques—correlation, entropy, etc.—to later perform a selection of the most representative features for the classification. In [88], the authors also compute summaries of the time series data by obtaining histogram representations of each feature or dimension. The data are then compared by applying a specific similarity measure for histograms, based on the Wasserstein distance [89]. The Wasserstein distance between two univariate distribution functions can be expressed as (18), where $F_i$ and $F_j$ are the cumulative distribution functions (CDFs) associated with the i and j histograms, and the functions $F_i^{-1}$ and $F_j^{-1}$ are the corresponding quartile functions (qfs).

$$d_m(An{d}_i,an{d}_j)={\left[{\int }_0^1{|F_i^{-1}\left(t\right)-F_j^{-1}\left(t\right)|}^{m}dt\right]}^{\frac{1}{m}}$$

(18)

4.3. Model-Based Time Series Data Clustering

These clustering techniques obtain, first of all, models representing the data, and then clustering techniques are applied to the models. For example, in [90] Hidden Markov Models (HMMs) for clustering temporal data. The HMM clustering method proposed by the authors can be summarised in terms of four levels of nested searches:

• The number of clusters in a partition.
• The structure for a given partition size.
• The HMM structure for each cluster.
• The parameters for each HMM structure.

Ref. [91] also models each cluster as an HMM, able to generate the temporal sequences that belong to that cluster; the first partition of the data (and also the number of clusters) is obtained by applying a hierarchical clustering algorithm which applies DTW as the dissimilarity distance. The result from this partition is used as the initialisation to train the HMM.

The authors in [92] fit the two time series to be compared to Auto-Regressive (AR) models of order k, and then compares the difference between the resulting AR models. An agglomerative hierarchical clustering algorithm is applied to the AR estimates to group them by similarity.

The paper [93] presents a Bayesian method for clustering dynamic processes. The method models dynamics as Markov chains and then applies an agglomerative clustering procedure to discover the most probable set of clusters capturing different dynamics. To increase efficiency, the method uses an entropy-based heuristic search strategy. The authors have also developed multivariate clustering dynamics [94], applying an average of the Kullback–Leibler distance between transition states to compute similarity.

In [95], the authors perform a classification of time series data into patterns using mixtures of autoregressive moving average (ARMA) models. Both mixing coefficients and model parameters are computed applying the Expectation Maximisation (EM) algorithm, by defining the probabilities of a time series as a mixture of several models. Ref. [96] also compares the coefficients from ARMA models of the time series data, but transforms first the time series into a discretised clipped data representation, where the new values are equal to 1 if the original time series is above the median, and 0 otherwise. The authors indicate that this discretisation removes outliers from the data, thus resulting in better clusters.

The authors in [97] propose to analyse the similarity between time series based on their cepstral coefficients, obtained from the spectral density functions of the equivalent ARMA models of two time series. Kalpakis et al. [98] perform clustering on time series by computing the similarity between parameters of the ARIMA models obtained of the data making use of a Linear Predictive Coding (LPC) cepstrum distance. The cepstrum is defined as the inverse Fourier transform of the short-time logarithmic amplitude spectrum. The dissimilarity between time series is measured using the Euclidean distance between their LPC cepstral coefficients. The Partitioning Around Medoids (PAM) clustering algorithm is used. The results show that cepstral coefficients have a high discriminatory power to separate time series generated by different models. A similar approach is presented by Maharaj and D’Urso [99], where the cepstral coefficients are obtained, and the fuzzy C-means is applied.

In [100], gene expressions are modelled as splines, thus reducing the size of the time series data, filtering noise and loss of information, and then applying an energy based similarity measure, called SimilB, described in [101]. This distance measures the non-linear interactions between two real-time functions, taking their first and second derivatives into account. Its formula is described in (19) and (20), given two curves, $f\left(t\right)$ and $g\left(t\right)$. The bigger the value of the distance SimilB, the higher the similarity between the functions, taking a value of 1 when $f\left(t\right)=g\left(t\right)$.

$$SimilB(f,g)=\frac{\sqrt{2}\int {\psi }_B(f,g)dt}{\int \sqrt{{\psi }_B{(f,f)}^2+{\psi }_B{(g,g)}^2}dt}$$

(19)

$${\psi }_B(f,g)=\frac{df\left(t\right)}{dt}\frac{dg\left(t\right)}{dt}-\frac{1}{2}\left(f\left(t\right)\frac{d^{2}g\left(t\right)}{d{t}^2}+g\left(t\right)\frac{d^{2}f\left(t\right)}{d{t}^2}\right)$$

(20)

The authors in [102] perform clustering of trajectories by developing complex-valued linear dynamical systems (CLDSs) to handle time lags and joint dynamics among trajectories. The system parameters are estimated following a procedure similar to the Expectation Maximisation (EM) algorithm [103].

Ref. [104] performs similarity between time series data by computing the Mahalanobis distance between regression coefficients and the Euclidean distance between Autoregressive weights. This metric is applied to time series hydrology observations from different locations.

4.4. Selection of the Dynamic Clustering Algorithm According to the Application

The review done confirms that the expert has a huge number of techniques to use for dynamic clustering. The method selection depends first on the decision of using the raw data for clustering or to reduce/model the data before clustering.

In the first case, the nature of the data and objective to achieve with the analysis are the keys for a correct choice. For example, if dynamic clustering is applied to biomedical signals, like fMRI, specifically developed techniques for analysing this type of signal can be used, as presented in [48] or [52]. The same applies to clustering the stock market time series [53]. If a specific method for the application does not exist and data is one dimensional, the FFCM ([53] algorithm can be applied, or [56] in the case of several dimensions. However, if the objective of the analysis is to observe data clusters with different time granularity, then hierarchical clustering described in [50] can be used.

In the case where reduced dimensionality of data is preferred, there exist specific algorithms for diagnostic in predictive maintenance [67] or for the analysis of biomedical signals [68]. For general applications, probabilistic models, as in [90] or in ([91]), are good options. For the comparison and clustering of one-dimensional data, the algorithms described in [80] or [82] can be used, whereas for multi-dimensional data, [83] or [85] are good choices. If the aim is the detection of frequent patterns in the time series, then the algorithms described in [70] or [72] can be used.

If the expert decides an equivalent model will represent the time series, the data of dynamic processes [93] are specific for this type of data. More recent works are devoted to self-regression techniques, as in [96] or in [104], or the cepstral analysis, as [97] or [105].

5. Comparative Analysis of Clustering Algorithms for Load Profile Pattern Analysis

In recent years, the visualisation and interpretation requirements of load profile patterns have increased to give the user a better understanding of results, and therefore to support decisions. The algorithm chosen will, of course, depend on the defined objective, the available data, and the expert opinion (Section 4.4). While new clustering approaches are constantly published, current dynamic clustering tendencies based on raw data analysis, feature-based dimensionality reduction, or models are quite similar to those previously described.

However, most of them are specific modifications of the seminal ideas presented in K-means or FCM. Therefore, to make a general and comprehensive comparison among techniques about their performances in the automated detection of electric energy consumption load profile patterns, the more generic approaches have been selected next.

The dynamic clustering methodology presented in [64], named END (Equal N-Dimensional), allows a common framework for the use of available algorithms and similarity measures. Then, the raw time series can be compared, clusters and prototypes obtained, and evolution of the data dimensions along the time visualised. Therefore, it is considered that a performance comparison between all the combinations of the dynamic versions of most used algorithms (K-means and FCM) and the most used distances (Euclidean, correlation and Hausdorff, using END) will be interesting for an expert needing information for a good clustering technique selection.

Therefore, in the following subsections, the END framework is first presented. Then, the available electric energy consumption load profile data are described, and the comparative analysis is presented. Finally, the results of the comparative analysis are shown.

5.1. Framework for Similarity Measures Comparison

END (Equal N-Dimensional) deals with objects with n dimensions and time series with similar or the same magnitude. Similarity measures used are “augmented” as described in [59] or in [60]. It can also be seen as an FFCM [8] modification where the d operator is substituted by other similarity measures, allowing to compare two time series along time. The author presents two modified similarity measures of the Euclidean distance and the correlation, and four clustering algorithms are modified for dynamic analysis: END-FCME (END FCM Euclidean-based), END-FCMC (END FCM Correlation-based), END-KME (END K-Means Euclidean-based), and END-KMC (END K-Means Correlation-based). The modified similarity measure to compare time series can be seen in (21), where B is the norm (identity matrix is used in the case of the Euclidean distance).

$$dist(x_i,c_k)=\frac{1}{d}\sum _{j=1}^d{\parallel x_{i_j}-c_{k_j}\parallel }_B^2=\frac{1}{d}\sum _{j=1}^d\left({(x_{i_j}-c_{k_j})}^{T}B(x_{i_j}-c_{k_j})\right)$$

(21)

If the correlation is used, the modified similarity measure based on the Pearson correlation can be seen in (22) and (23). The result is a measure of the linear relation between the two time series with values between −1 and 1, and this is then transformed into a similarity measure in (24).

$$corr(x_i,c_k)=\frac{1}{d}\sum _{j=1}^{d}corr(x_{i_j},c_{k_j})$$

(22)

$$corr(x_{i_j},c_{k_j})=\frac{{\sum }_{m=1}^p(x_{i_{j_m}}-\overline{x_{i_j}})(c_{k_{j_m}}-\overline{c_{k_j}})}{\sqrt{{\sum }_{m=1}^p{(x_{i_{j_m}}-\overline{x_{i_j}})}^2}\sqrt{{\sum }_{m=1}^p{(c_{k_{j_m}}-\overline{c_{k_j}})}^2}}$$

(23)

$$dist(x_i,c_k)=\frac{1-corr(x_i,c_k)}{2}$$

(24)

In addition to the modified distances, a clustering algorithm is presented that is able to compare two n-dimensional dynamic objects by considering them as two surfaces, and using a similarity measure based on the Hausdorff distance [106]. The algorithm is applied in two steps: First, the surfaces are decomposed into smaller linear surfaces, and then the Hausdorff distances between these surfaces are computed. The number of linear surfaces to be obtained is an input parameter, and is based on the expert’s previous knowledge about the data. The linear surfaces are obtained by least squares (25) in matrix form (26), where $(z_1,z_2,\cdots z_i,\cdots ,z_n)$ are the observations, and each $z_i$ value can be obtained as the linear combination of independent variables x and its coefficients w, and an error term ${\epsilon }_i$ (the difference between the estimated and the observed value).

$$z_i=w_0+w_1{x}_{i1}+w_2{x}_{i2}+{\epsilon }_i$$

(25)

$$Z=X{W}^t+\epsilon$$

(26)

The least-squares method minimises error function as the sum of the squared differences between the estimated and the observed values (27). From the minimisation of this expression, the coefficients of the linear function are obtained (28).

$$Error=\frac{1}{2}\sum _{i=1}^n{(z_i-f(x_i,w))}^2$$

(27)

$$W={\left(X^{t}X\right)}^{-1}{X}^{t}Z$$

(28)

Next, the linear surfaces obtained are compared by the Hausdorff distance as defined in [107]: Given a distance operator d, as the Euclidean distance, the distance of a generic point x to a closed subset $To$ (belonging both, x and $To$, to the p-dimensional subset of ℜ subsets) is obtained as the minimum of all the possible distances of x concerning all the points belonging to $To$, as can be seen in (29).

$$d(x,To)=mi{n}_{\widetilde{to}\in To}\left(d(x,\widetilde{to})\right)$$

(29)

The Hausdorff metric between two no empty subsets, $To$ and B, is defined as the maximum of all the possible distances $d(\widetilde{to},B)$ of a point $\widetilde{to}$ of $To$ to B (30). Since this relation is not necessarily symmetrical, the Hausdorff distance $d_H(To,B)$ between two subsets $To$ and B is defined as the maximum of the two metric Hausdorff between them, $h(To,B)$ and $h(B,To)$, as described in (31).

$$h(To,B)=ma{x}_{\widetilde{to}\in To}\left(d(\widetilde{to},B)\right)$$

(30)

$$d_H(To,B)=max(h(To,B),h(B,To))$$

(31)

5.2. Data and Analysis Description

The database analysed comprises the values of time electrical energy consumed by a sample of 708 real residential clients in Spain during the two years that followed, 2009 and 2010.

The dataset used in this analysis is obtained from two consecutive years of data, 2008 and 2009. After eliminating those load profiles with noise and erroneous (disproportionately high) values, a final dataset with 516,132 load profiles from 708 clients was analysed (i.e., hourly smart metering energy consumption values from 708 clients during 729 days). The dataset is organised as 708 temporary objects of 24 dimensions (corresponding to the 24 h of the day) and 729 measures (one per day during two years).

The algorithms compared are the following: A modified version of the K-means algorithm making it possible to compare two objects at each time instant [108], six classic algorithms implemented in the END platform (including variations of K-means and FCM, and two-step clustering using Hausdorff distance), and FFCM. The algorithms have a similar computational cost. K-means complexity is $O\left(ndci\right)$ (where n represents the number of data points, d is the dimension, c is the number of clusters, and i is the number of iterations), and fuzzy C-means complexity is $O\left(nd{c}^{2}i\right)$ (see [109]). FFCM complexity is $O\left(n{d}^2{c}^{2}i\right)$, because only a change in the distance of FCM (two steps instead of one step) is performed, and the same applies for the END framework (only adding an extra c complexity to the base algorithm). A summary of the tested algorithms is presented in

Table 3. Tested clustering algorithms for time series.

No.	Base Clustering Technique	Dynamic Similarity Measure	Clustering Algorithm
1	K-means	Euclidean distance	END-KME
2	K-means	Correlation	END-KMC
3	K-means	Distance Hausdorff	END-KMH
4	K-means	Euclidean distance	K-means (modified)
5	FCM	Euclidean distance	END-FCME
6	FCM	Correlation	END-FCMC
7	FCM	Hausdorff Distance	END-FCMH
8	FCM	Fuzzy membership functions	FFCM

.

The eight algorithms have been tested on the same database ten times each. The goodness of the clustering results is calculated by computing the Davies–Bouldin or DB [110] clustering validity index. This index is commonly used for evaluating quantitatively the clustering performance, and it has been used recently for residential load profiles (see, for example, [111] or [112]). The maximum number of iterations for each algorithm, if no other stop condition is fulfilled previously, has been limited to 10.

The number of clusters is an input parameter for this type of algorithm. As the number of classes increases then the clustering algorithm can identify more behaviours clustering them as different clusters, although an excessive number of clusters can cause the formation of two or more very similar or even identical clusters. In contrast, a very low number of clusters will decrease the algorithm capacity to detect uncommon behaviours of small groups of clients. The optimal number of clusters is usually determined by cluster validity indices (CVIs) [113] in combination with experts’ knowledge (if available). A CVI represents two indicators, namely compactness and separation. Compactness indicates the concentration of data points (pattern) in a specific cluster, and it is measured by the distance between each data point (pattern) and its centroid (prototype) in the same cluster. The smaller the distance, the better the compactness of the cluster. Separation indicates the degree of separation between clusters; it is measured by the distance between cluster centroids (prototypes). In this case, the larger the distance, the stronger the separation of clusters. Therefore, the balance between the two indicators is important for designing CVIs. A review of CVIs used in different clustering contexts can be found in different publications [114,115], and the Bayesian information criterion (BIC) [116] performed well in a previous classification work of the authors on the same dataset [30]. BIC gave good compactness/separation ratios in the range from 6 to 12 clusters. This information, combined with the expert’s knowledge and taking into account the human perception (a reasonable number of clusters must be chosen to observe global results at a glance to extract conclusions from the resulting patterns) led to 10 clusters as a balanced selection.

For those algorithms using the Hausdorff distance, the objects are first decomposed in several linear surfaces. The authors’ knowledge in the usual low voltage residential consumers in Spain suggests dividing the daily load profiles into 7 regions: The first region is from 0:00 to 5:00; the second from 5:00 to 8:00, when the first peak of the morning is expected (getting up for going to work); the third from 8:00 to 10:00, when the consumption decreases; the fourth from 10:00 to 15:00, when the second peak of energy consumption is expected (due to lunchtime in Spain); the fifth is from 15:00 to 18:00, when the energy consumption decreases again; the sixth is from 18:00 to 22:00, when the third (and maximum) peak of energy consumption in Spanish dwellings is reached; and finally the seventh is from 22:00 to 24:00. The time axis has been divided into 24 sections equal in length, corresponding to the 24 months during two consecutive years. The result is, therefore, the decomposition of each surface into ($7\times 24=168$) linear surfaces.

5.3. Results

Table 4. DB index clustering test results (best performance in bold).

Cycle	END-KME	END-KMC	END-KMH	K-Means	END-FCME	END-FCMC	END-FCMH	FFCM
1	2.348	5.918	3.204	NaN	4.131	NaN	6.181	8.114
2	3.151	5.650	2.680	2.285	3.848	NaN	7.449	7.050
3	2.314	5.836	3.039	1.594	2.792	NaN	5.201	NaN
4	1.894	5.674	3.759	NaN	5.801	NaN	5.103	NaN
5	2.967	5.674	3.136	2.421	3.699	NaN	4.184	NaN
6	2.589	5.267	3.049	NaN	3.175	NaN	6.444	6.527
7	2.336	5.951	3.497	2.183	8.750	NaN	6.552	NaN
8	2.501	5.854	3.202	NaN	4.143	NaN	5.881	NaN
9	2.483	5.758	3.204	1.390	4.866	NaN	16.863	9.270
10	2.689	5.878	2.995	NaN	2.909	NaN	4.738	NaN

shows the numerical results obtained for the DB validity index for all the tested algorithms (10 times each). The lower the DB value, the better the performed clustering.

It can be observed that the best results are obtained by the END-KME and the END-KMH algorithms, in all the 10 cycles. The worst result is obtained for the END-FCMC algorithm, where a NaN value in all the cycles indicates a division by zero or an error in numerical precision, probably due to the algorithm’s inability to produce well defined and separated clusters. The FCM-based algorithms, END-FCME and END-FCMH algorithms, provide worse results than K-means. Finally, the FFCM and the Extended K-means yield NaN values in some cycles and, therefore, their proficiency would be less trustworthy than the clustering algorithms with no NaN values. It can be concluded that, regarding the DB index, K-means-based dynamic clustering algorithms with Euclidean or Hausdorff-based distances provide the best results.

Figure 5 allows the visualisation of the results. Seasonality effects can be clearly observed, with generalised higher consumption in winter, lower energy consumption in summer, and the lowest values from autumn and spring.

The resulting clusters and how the partition should be is unknown. The expected results, however, should follow previous experiences concerning the classification of load profiles from residential or domestic electric energy users in Spain. There are mainly three types of energy consumption users according to their load profile patterns or prototypes, which are explained next:

• The first type of client (see classes 1, 5, 6 and 8 in the Figure) represents the majority of energy consumption residential users in Spain. It is characterised by a daily profile of energy consumption with three ascending peaks of energy consumption: One in the morning (about 8:00), another one at lunchtime (about 15 h), and the highest one at night, at approximately 22:00. The clustering technique groups these clients according to the shape of these peaks and the energy consumption level. Therefore this type of clients can be represented by two or more clusters that group clients of low and medium energy consumption (500–1500 Wh maximum).
• The second type of client (see classes 4, 7, and 9) represents a minority of users with a high level of energy consumption through the day. There are two different patterns in this type of client: One with the typical shape of energy consumption, described above, but with higher energy levels (from 2500 to 7000 Wh), and another group of users that present (more or less) an elevated energy consumption through the day, or other non-typical patterns of energy use.
• The third type comprehends a small group of clients with a higher consumption of energy at night, due to thermal energy accumulators used mainly at night, or in valley hours where the price of the energy is cheaper.

Therefore, an automatic global summarised description of different electric energy consumption load profiles of domestic clients with respect to time, day, and year is obtained.

6. Conclusions

The main aim of the paper was to provide a detailed review of automated detection of electric energy consumption load profile patterns by means of state-of-the-art techniques for clustering. More than one hundred references were analysed and reviewed, then an organized compilation of those data mining techniques was provided using clustering that can obtain and visualise temporal patterns characterising the users of electrical energy. Given the characteristics of the time series, only dynamic clustering techniques are applicable. However, the dynamic techniques are based on modified static techniques, so the more common static clustering techniques have also been presented.

The review confirms that there is a vast number of techniques to use for dynamic clustering (and new ones are constantly published) and that the method selected depends on the objective, the available data, and the expert opinion. This work can be used as a guide for those interested in the automated analysis and groups of behaviour detection within energy consumption load profile databases from Smart Meters. This will allow the evaluation by experts of how users consume energy, both during the day and during a sequence of days, it then being possible to assess trends and predict future scenarios.

While specific algorithms can be more suitable in a particular case, modifications of the seminal approaches (K-means or FCM) are usually applicable and give good results. Therefore, this work has also compared their performances in the automated detection of electric energy consumption load profiles patterns. The comparison was done using the END framework, which allows the use of any algorithm to cluster raw time series and compare results. The final algorithms have similar computational costs, allowing results comparison just looking at their performance.

A real database (data from 708 residential clients in Spain during two years) has been used to test performance, and algorithm performance has been measured using a quantitative index commonly used in clustering. Results showed that K-means-based dynamic clustering algorithms with Euclidean or Hausdorff-based distances provide the best results. Visualisation of the three-dimensional automatically detected prototypes of these algorithms provide a global summarised description of the different electric energy consumption load profiles of domestic clients, and the profile patterns make sense from the expert point of view.