# Similarity Measurement and Classification of Temporal Data Based on Double Mean Representation
## 3 Our Method, SAX-DM
### Lower Bound  
The SAX algorithm, when applied for dimensionality reduction, offers one of its most important features, that is providing a lower-bound distance measurement called the boundary distance. The lower bound is useful to control errors and accelerate computations. However, when performing spatial queries on the dimensionally reduced original sequence, there is a risk of false negatives. To reduce the occurrence of false negatives after dimensionality reduction, it is important to design algorithms that satisfy a good lower-bound property.  
Next, we will prove that the distance we propose also serves as a lower bound for the Euclidean distance.  
The lower bound of the PAA distance for the Euclidean distance is given by the following expression:  
\[\sqrt{\sum_{i=1}^{n}(q_{i}-c_{i})^{2}}\geq\sqrt{\frac{n}{w}}\sqrt{\sum_{i=1}^{ w}\left(\overline{q}_{i},\overline{c}_{i}\right)^{2}} \tag{15}\]  
To prove that DMIST is also a lower bound for the Euclidean distance, we reiterate some of the proofs here. Let \(Q\) and \(C\) be the means of the time series data \(Q\) and \(C\), respectively. Firstly, we consider the single-frame case (i.e., \(w=1\)), and according to Equation (15), we can obtain  
\[\sum_{i=1}^{n}(q_{i}-c_{i})^{2}\geq n\left(\overline{Q}-\overline{C}\right)^{2} \tag{16}\]Recall that \(q\) is the average value of the temporal data, so \(q_{i}\) can use \(q_{i}=\overline{Q}-\Delta q_{i}\). This also applies to each point \(c\) in \(c_{i}\). Equation (15) can be rewritten as follows:  
\[n\big{(}\overline{Q}-\overline{C}\big{)}^{2}+\sum_{i=1}^{n}(\Delta q_{i}- \Delta c_{i})^{2}\geq n\big{(}\overline{Q}-\overline{C}\big{)}^{2} \tag{17}\]  
Because \(\sum_{i=1}^{n}\big{(}\Delta q_{i}-\Delta c_{i}\big{)}^{2}\geq 0\) and \(\big{(}\Delta q(t)_{1}-\Delta C(t)_{1}\big{)}^{2}+\big{(}\Delta q(t)_{2}- \Delta C(t)_{2}\big{)}^{2}\), we can obtain the following inequality (which clearly exists in the boundary distance \(\Delta q_{i}\)):  
\[\sum_{i=1}^{n}(q_{i}-c_{i})^{2}\geq\big{(}\Delta q(t)_{1}-\Delta C(t)_{1} \big{)}^{2}+\big{(}\Delta q(t)_{2}-\Delta C(t)_{2}\big{)}^{2} \tag{18}\]  
Substituting Equation (16) into Equation (17), we obtain  
\[n\big{(}\overline{Q}-\overline{C}\big{)}^{2}+\sum_{i=1}^{n}(q_{i}-c_{i})^{2} \geq n\big{(}\overline{Q}-\overline{C}\big{)}^{2}+\sum_{i=1}^{n}(md(q_{i},c_{ i}))^{2} \tag{19}\]  
MINDIST conducted a lower-bound analysis of the PAA distance, namely,  
\[n\big{(}\overline{Q}-\overline{C}\big{)}^{2}\geq n\big{(}\hat{Q}-\hat{C} \big{)}^{2} \tag{20}\]  
In Equation (20), \(\hat{Q}\) and \(\hat{C}\) are, respectively, the symbolic representations of \(Q\) and \(C\) in the original SAX. By transitivity, the following inequality is correct:  
\[n\big{(}\overline{Q}-\overline{C}\big{)}^{2}+\sum_{i=1}^{n}(\Delta q_{i}- \Delta c_{i})^{2}\geq n\big{(}dist\big{(}\hat{Q}-\hat{C}\big{)}\big{)}^{2}+(md (q_{i},c_{i}))^{2} \tag{21}\]  
Recalling Equation (15), this means  
\[\sum_{i=1}^{n}(\Delta q_{i}-\Delta c_{i})^{2}\geq n((dist\big{(}\hat{Q}-\hat{ C}\big{)})^{2}+\frac{1}{n}(md(q_{i},c_{i}))^{2}) \tag{22}\]  
N frames can be obtained by applying a single-frame proof on each frame, namely,  
\[\sqrt{\sum_{i=1}^{n}(q_{i}-c_{i})^{2}}\geq\sqrt{\frac{n}{w}}\sqrt{\sum_{i=1}^ {w}\big{(}(dist(\hat{q},\hat{c})\big{)}^{2}+\frac{w}{n}(md(q_{i},c_{i}))^{2}} \tag{23}\]  
The quality of the lower boundary distances is usually measured by the compactness of the lower boundaries (_TLB_):  
\[TLB=\frac{Lower\ Bounding\ Distance(Q,C)}{Euclidean\ Distance(Q,C)} \tag{24}\]  
The value of _TLB_ is within the range [0, 1]. The higher the _TLB_ value, the better the quality. Recalling the distance metric in the equation, we can obtain that \(TLB(BDIST)\geq TLB(MINIDIST)\), which means that SAX-DM has a tighter lower bound than the original SAX distance.