# Transitional SAX Representation for Knowledge Discovery for Time Series
## 3 The Proposed Method, Transitional SAX
### Transitional Information in Sub Value Spaces
Unless \(N\) is large enough, meaning a long time series, we recommend the use of one-step upward and downward transitions, \(\alpha-1\) counts for each, plus the sojourn transitions instead of all \(\alpha^{2}\) counts, which brings the dimensionality of \(V\) to \(n(3\alpha-1)\). In contrast with SAX which is able to handle incremental data, the proposed transitional SAS is not fully online but segment-wise online, since it is able to append a SAX word and a transition vector of a segment to its representation \(V\). One needs to avoid a quite large \(n\) to prevent possible delay for online usage. On the contrary, a quite small \(n\) hardly captures transitional movements in the sub value spaces. As shown in line 12 of Algorithm 1, we use letter symbols \(\alpha_{1}=k_{1}\) and \(\alpha_{2}=k_{2}\) if \(\bar{x}_{p_{1}}\in S_{k_{1}}=[y_{k_{1}-1},y_{k_{1}})\) and \(\bar{x}_{p_{2}}\in S_{k_{2}-2}=[y_{k_{2}-1},y_{k_{2}})\), respectively, and their distance is given by  
\[dist(\alpha_{1},\alpha_{2})=\max\{y_{\max\{k_{1},k_{2}\}-1}-y_{\min\{k_{1},k_{2 }\}},0\}. \tag{3}\]  
The letter distance, if located in either the same value sub space, is zero, and otherwise, it is set by the intermediary value spaces between two sub spaces \(S_{k_{1}}\) and \(S_{k_{2}}\). For example, if \(\bar{x}_{p_{1}}\in S_{3}\) and \(\bar{x}_{p_{2}}\in S_{3}\), i.e., in the same value sub space, the distance becomes zero. For value sub spaces right adjacent to each other, \(\bar{x}_{p_{1}}\in S_{3}\) and \(\bar{x}_{p_{2}}\in S_{4}\), the distance becomes zero since the in-between sub value space does not exist. For \(\bar{x}_{p_{1}}\geq\bar{x}_{p_{2}}\), it straightforwardly follows that \(k_{1}\geq k_{2}\), \(\bar{x}_{p_{1}}\geq y_{k_{1}-1}\), and \(\bar{x}_{p_{2}}\leq y_{k_{2}}\), leading to \(\bar{x}_{p_{1}}-\bar{x}_{p_{2}}\geq y_{k_{1}-1}-y_{k_{2}}=dist(\alpha_{1},\alpha _{2})\). Figure 1: Graphical description of transitional SAX. ```
1:Input: time series data \(X:=\{x(t)\}_{t=1,\ldots,N}\)

the length of a segment \(n\),

the number of sub value spaces \(\alpha\)
2:Output: transitional symbolic representation \(V\)
3:procedureTransitionalSAX(\(X,n,\alpha\))
4: Initialize \(V\leftarrow[]\), \(W\leftarrow[]\), \(Z\leftarrow[]\), and set \(K=N/n\)
5: Create sub value spaces \(S_{k},k=1,\ldots,\alpha\), with equal probability \(1/\alpha\) by fitting \(x(t)\) values to normal distribution
6:for\(p=1,\ldots,K\)do
7:\(X_{p}:=\{x(t)\}_{t=K(p-1)+1,\ldots,Kp}\)
8:\(\bar{x}_{p}=\frac{1}{K}\sum_{j=K(p-1)+1}^{Kp}x(j)\)
9:endfor
10: Set \(\rho=\min_{p,p^{\prime}=1,\ldots,K}\{|\bar{x}_{p}-\bar{x}_{p^{\prime}}|\}\)
11:for each segment \(X_{p}\), \(p=1,\ldots,K\)do
12: Compute local average \(\bar{x}_{p}\) and assign a symbol \(\alpha_{k}(=w)\) if \(\bar{x}_{p}\in S_{k}\)
13:\(W\leftarrow[W,w]\)
14:for each \(i,j=1,\ldots,\alpha\)do
15: Compute transitional information \(\gamma_{i,j}=\sum_{t=K(p-1)+1}^{Kp}\mathbf{I}(x(t)\in S_{i})\mathbf{I}(x(t+1 )\in S_{j})\)
16: Update \(Z\gets[Z,\gamma_{i,j}]\)
17:endfor
18:endfor
19: Update \(V\leftarrow[W,Z]\)return\(V\)
20:endprocedure
```  
**Algorithm 1** Transitional SAX.