# Transitional SAX Representation for Knowledge Discovery for Time Series
## 3 The Proposed Method, Transitional SAX
### Distance Measure for Transitional SAX  
We evaluate the proposed method by how closely the new representation \(V=[W,Z]\) of a time series, \(X\), approximates the original time series \(X\). The new distance measure associated with the new representation needs to satisfy a lower-bounding property to ensure no false dismissals [17; 18]. For that purpose, we propose the following distance measure. Let us suppose that the transitional SAX method produces new representations \(V^{(1)}=[W^{(1)},Z^{(1)}]\) and \(V^{(2)}=[W^{(2)},Z^{(2)}]\) for \(X_{1}\) and \(X_{2}\), respectively, with the same size, in which \(\tau\) is the size of \(Z^{(1)}\) or \(Z^{(2)}\), \(\tau\ =|Z^{(1)}|=|Z^{(2)}|\); we define \(D(\cdot,\cdot)\) to be:  
\[D(V_{1},V_{2})=\sqrt{\sum_{i=1}^{n}K(W^{(1)}(i)-W^{(2)}(i))^{2}\cdot\sum_{j=1 }^{\tau}\frac{(Z^{(1)}(j)-Z^{(2)}(j))^{2}}{\tau(n-1)^{2}}}. \tag{4}\]We compare the distance measure (4) with the Euclidean distance of the original time series to verify that it satisfies the lower-bound condition: we show that \(D(V_{1},V_{2})\leq\ D_{Euclidean}(X_{1},X_{2})\). The right-hand side of the inequality becomes:  
\[\begin{split} D_{Euclidean}^{2}(X_{1},X_{2})=\sum\
olimits_{t=1}^{N }(x_{1}(t)-x_{2}(t))^{2}=\sum\
olimits_{p=1}^{n}\sum\
olimits_{t=K(p-1)+1}^ {Kp}(x_{1}-x_{2})^{2}\\ =\sum\
olimits_{p=1}^{n}\sum\
olimits_{t=K(p-1)+1}^{Kp}(x_{1}(t) -\bar{x}_{1,p}+\bar{x}_{1,p}-x_{2}(t)+\bar{x}_{2,p}-\bar{x}_{2,p})^{2}.\end{split} \tag{5}\]  
Since the sum of values centered by the average is zero, that is to say,  
\[\begin{split}\sum\
olimits_{p=1}^{n}\sum\
olimits_{t=K(p-1)+1}^ {Kp}(x_{1}(t)-\bar{x}_{1,p}-x_{2}(t)+\bar{x}_{2,p})\\ =\sum\
olimits_{p=1}^{n}\sum\
olimits_{t=K(p-1)+1}^{Kp}(x_{1}(t) -\bar{x}_{1,p})-\sum\
olimits_{p=1}^{n}\sum\
olimits_{t=K(p-1)+1}^{Kp}(x_{2} (t)-\bar{x}_{2,p})=0,\end{split}\]  
the right-hand side of Equation (5) becomes  
\[\begin{split}\sum\
olimits_{p=1}^{n}\sum\
olimits_{t=K(p-1)+1}^ {Kp}(x_{1}(t)-\bar{x}_{1,p}-x_{2}(t)+\bar{x}_{2,p})^{2}+\sum\
olimits_{p=1}^ {n}\sum\
olimits_{t=K(p-1)+1}^{Kp}(\bar{x}_{1,p}-\bar{x}_{2,p})^{2}\\ \geq\sum\
olimits_{p=1}^{n}\sum\
olimits_{t=K(p-1)+1}^{Kp}(\bar{ x}_{1,p}-\bar{x}_{2,p})^{2}\geq\sum\
olimits_{p=1}^{n}\sum\
olimits_{t=K(p-1)+1}^ {Kp}(W^{(1)}(p)-W^{(p)}(i))^{2}\end{split} \tag{6}\]  
The last inequality \((\bar{x}_{1,p}-\bar{x}_{2,p})^{2}\geq(W^{(1)}(p)-W^{(2)}(p))^{2}\) holds true by the letter-distance definition given in Equation (3). The value \(Z(j)\) difference is lower bounded by \(|Z^{(1)}(j)-Z^{(2)}(j)|\leq\max\left\{Z^{(1)}(j)\right\}-\min\left\{Z^{(2)}(j )\right\}=n-1\), \((Z^{(1)}(j)-Z^{(2)}(j))^{2}/(n-1)^{2}\leq 1\), and  
\[1\geq\sum\
olimits_{j=1}^{\tau}\frac{(Z^{(1)}(j)-Z^{(2)}(j))^{2}}{\tau(n-1)^ {2}}. \tag{7}\]  
The combination of the right-hand sides of equations and (6) and (7) produces  
\[\sum\
olimits_{p=1}^{n}\sum\
olimits_{t=K(p-1)+1}^{Kp}(W^{(1)}(i)-W^{(2)}(i) )^{2}\geq\ \sum\
olimits_{p=1}^{n}K(W^{(1)}(i)-W^{(2)}(i))^{2}\cdot\sum \
olimits_{j=1}^{\tau}\frac{(Z^{(1)}(j)-Z^{(2)}(j))^{2}}{\tau(n-1)^{2}},\]  
finalizing the proof of \(D(V_{1},V_{2})\leq D_{Euclidean}(X_{1},X_{2})\). By admitting that tight lower-bounds bring forth better contractive property, the lower-bound relation of the associated distance measure implies the utility of the proposed transitional information in distance computation. We will elaborate on its attributes in more detail in the Experiments section.