# Time Series Clustering Model based on DTW for Classifying Car Parks
## 2 Data and methodology
### Framework for Classifying Car Parks
#### 2.2.3 Clustering Algorithm  
Clustering algorithm is to group objects into some clusters and makes the similarity between objects from the same cluster maximum and the similarity of objects from different clusters minimum. As analyzed above, \(k\)-medoids is a commonly used clustering method for time series data. The partitioning around medoids (PAM) clustering method [29] as one of the \(k\)-medoids algorithms is adopted in this paper. Due to the randomness and uncertainty of the PAM, a new clustering model, namely DBPAM, is proposed in this paper, whose process is carried out by the following steps.  
Step1: Calculate distance radius.  
Firstly, we calculate the distance between any two different time series objects to obtain an \(n\)-by-\(n\) matrix, where the \(i^{th}\) column of matrix represents the distance between the \(i^{th}\) time series object and all of time series objects. Then we sort the values of the \(i^{th}\) column of matrix in ascending order as shown in Equation (5). Secondly, the \(k^{th}\) distance of each time series object is selected and represented as \(e=\{e(1)\), \(e(2)\),..., \(e(n)\}\). Thirdly, we obtain the \(e^{\prime}\) by sorting the \(e\) in ascending order. \(e^{\prime}\) shows the trend of the \(k^{th}\) distance, which can be plotted as a curve. Fourthly, the value of the \(k^{th}\) distance where the curve changes sharply is defined as the value of the radius \(r\).  
\[D_{i}=\left\{d\left(1\right)_{i},d(2)_{i},\cdots,d(k-1)_{i},d(k)_{i},d(k+1)_{i },\cdots,d(n)_{i}\right\} \tag{5}\]  
here, \(k\) is the number of clusters, \(d(k)_{i}\) represents \(k^{th}\) distance of the \(i^{th}\) time series object.  
Step2: Calculate the density of the neighbor area of the \(i^{th}\) time series object \(x_{i}\) (i=1 to N) where the \(i^{th}\) time series object is taken as center and \(r\) as radius, which is obtained by counting the number of the time series objects in this neighbor area.  
Step3: Initialize \(k\) centers based on density.  
The \(k\) initial centers can be obtained by following steps. Above all, we select the time series object whose neighbor area has the largest density \(\delta_{imax}\) as the first cluster center \(c_{1}\) shown in Equation (6). Then, the time series object farthest from the first cluster center is chosen as the second cluster center \(c_{2}\) shown in Equation (7). Subsequently, the time series object who has the largest sum of distances to the first and second centers is considered as the third cluster center \(c_{3}\) defined in Equation (8). We repeat the steps mentioned above until the \(k^{th}\) cluster center \(c_{k}\) is obtained as shown in Equation (9).  
\[c_{1}=x_{i}\;and\;\delta_{imax}=\max_{j}\delta_{j}\;j=1,2,\cdots,n \tag{6}\]  
\[c_{2}=x_{i}\;and\;x_{i}\;satisfying\;DTW(c_{1},x_{i})\geq DTW\left(c_{1},x_{j} \right)\;\forall j=1,2,\cdots,n \tag{7}\]  
\[c_{3}=x_{i}\;and\;DTW(c_{1},x_{i})+DTW(c_{2},x_{i})\geq DTW\left(c_{1},x_{j} \right)+DTW\left(c_{2},x_{j}\right)\;\forall j=1,2,\cdots,n \tag{8}\]  
\[\begin{array}{l}c_{k}=x_{i}\;and\;x_{i}\;satisfies\;ying\;DTW(c_{1},x_{i})+ \cdots+DTW(c_{k-1},x_{i})\\ \geq DTW\left(c_{1},x_{j}\right)+\cdots+DTW\left(c_{k-1},x_{j}\right)\;\forall j =1,2,\cdots,n\end{array} \tag{9}\]  
Step4: Assign each non-central time series object \(x_{i}\) to its nearest cluster.  
Step5: Update each center with time series object which makes the loss function S of this cluster minimum, and the loss function of the \(i^{th}\) cluster is defined as Equation (10).  
\[S_{i}=\sum_{j=1}^{n}\tau_{ij}\big{|}x_{j}-c_{i}\big{|}^{2} \tag{10}\]  
here \(\tau_{ij}=\begin{cases}1&x_{j}\in M_{i}\\ 0&else\end{cases}\).  
where \(M_{i}\) indicates the set of objects in the \(i^{th}\) cluster, \(c_{i}\) is the center of \(M_{i}\), \(x_{j}\) is the \(j^{th}\) time series object, and \(n\) is the number of time series objects.  
Step6: Repeat Step4 and Step5 until the centers no longer change.