# Sequence-Information Recognition Method Based on Integrated mDTW
## 3 Methodology
### Sequence Clustering
For a handwriting database with thousands of characters \((N_{c}>1000)\), this step could reduce more than 99.9% of total origin training time cost. Unlike the cluster methods based on Minkowski distances, a major problem within the sequence cluster domain is that it is very hard to generate a virtual sequence as a \"center\" in the corresponding space. Therefore, the proposed method should take some of the real samples as cluster centers by a hierarchical model. Then, the concrete steps for clustering a \(N_{c}\times N_{w}\) database of this work are arranged as follows:  
* Step 1 Separate the whole database into \(N_{c}\) groups by their characters. Thus, each group has \(N_{w}\) handwriting samples with the same character. * Step 2 Choose a cluster number \(n>0\in\mathcal{R}\) and then divide each group to \(cl_{n}\) clusters by minimizing Equation (7) \[\arg\min[\sum_{i=1}^{n}\sum_{k=1}^{cl_{i}}DTWdist(Cent_{i},Seq_{k})]\] (7) where \(Center_{i}\) is the center of \(i_{th}\) cluster, \(cl_{i}\) is the number of sequence samples in \(i_{th}\) cluster, \(Seq_{k}\) is the \(k_{th}\) sequence sample of \(i_{th}\) cluster. The significance of this step is finding a set of centers that could minimize the sum of DTW distances between training samples and the nearest appropriate centers. In other words, this step finds \(n\) real samples as the representation of a whole sample group. * step3 Repeat step2 \(N_{c}\) times to obtain all characters clustered. After that, we obtain a center set with \(N_{c}\times n\) sequence samples. Step 2 is the core content of the proposed cluster framework. To realize this, the following calculation steps were adopted, as listed in Algorithm 1. Where \(D\) is the storage of DTW distance for every two samples in the group, Equation (8) shows the computation of this process. \[D_{ij}=DTWdist(seq_{i},seq_{j}) \tag{8}\]  
where \(seq_{i}\) represents the ith time-series vector. It should be noted that for temporal information, its vector may be discontinuous. For example, in handwriting, a word may be composed of multiple strokes. Therefore, when performing mDTW calculation on two time series of text, we need to consider the matching relationships between different strokes. Figure 3: Digits are DTW values between the testing center and samples. For characters with high dissimilarities (gray samples), the value of DTW is much higher than similar ones (blue samples). The value destabilization covered by center changing could not affect the final results for gray samples but have a significant impact on similar samples. Noticing that \(D\) here is a symmetric matrix, and all the diagonal elements are 0. Then a temporal matrix \(D^{\prime}\) is generated from \(D\) by Equation (9). \[{D_{i}}^{\prime}=D_{i}\times\frac{iter}{iter+1}+D_{j} \tag{9}\]  
After the iteration process in line2-line6 of Algorithm 1, \(C\in\mathcal{R}^{n\times N_{w}}\) is calculated. Each line of \(C\) shows the sequence index of a cluster. Then, we calculate the centers of every cluster. For instance, the non-zero elements in \(i_{th}\) row of \(C\) are \(c_{i1},\dots,c_{im}\). Finally, find the center of this cluster by Equation (10). \[Cen(k)=\arg\min(\sum_{d=1}^{m}DTWdist(Seq_{k},Seq_{c_{i1}})) \tag{10}\]  
```
0: A group of training sequences \(SEQ\{seq_{1},\dots seq_{N_{c}}\}\)
0: Initialize a cluster index matrix \(C\in\mathcal{R}^{N_{c}\times N_{c}}\), set \(c_{i1}=i\) and others as 0
1: Compute a DTW distance matrix \(D\in\mathcal{R}^{N_{c}\times N_{c}}\) via Equation (8). 2:for iter in \(Nc-n\)
3: find the location \(i,j=argmin(D),(i<j)\)
4: compute a temporal matrix \(D^{\prime}\) by Equation (9) and replace \(D\) by \(D^{\prime}\)
5: merge the \(j_{th}\) cluster to the \(i_{th}\)
6:end for
7:for iter in \(n\)
8: find the sequence sample in \(iter\) row of \(C\) by Equation (10) and mark it as \(seq_{ct_{iter}}\)
9:end for
0:\(n\) sequences as centers \(Cen\{seq_{ct_{1}},\dots,seq_{ct_{n}}\}\)
```  
**Algorithm 1**Hierarchical cluster for a Chinese handwriting sample group