# Transitional SAX Representation for Knowledge Discovery for Time Series
## 3 The Proposed Method, Transitional SAX
### Transitional Information in Sub Value Spaces  
We first assume that the values \(x(t)\) in time series \(X\) follow a normal distribution through normalization and detrending, widely adopted in the literature [7; 17]. Notice that we choose the original time series \(X\) rather than segment \(X_{p}\) to increase the validity of the assumption. We divide the value space into regions with equal probability. To describe the regions in detail, we define a sub value space to be an interval \(S_{k}=\ [y_{k-1},y_{k}),k=1,\ldots,\alpha\), such that \(\hat{\Phi}(y_{k})-\hat{\Phi}(y_{k-1})=1/\alpha\), in which \(\hat{\Phi}\) is the cumulative probability function of a normal distribution with the sample average and the sample variance of \(x(t)\). The parameter \(\alpha\) is the number of sub value spaces. In the following experiments, we show how to set \(\alpha\) through a cross-validation procedure with training datasets. Observe that \(y_{0}\) is the minimum of all values \(x(t)\) and \(y_{\alpha}\) is the maximum. Now given the sub value spaces \(S_{k}\), various feature reduction and extraction approaches are possible for expressing the time series \(X\). For example, the SAX method assigns a symbol for a sub value space, reducing a numerical piecewise approximation to a symbol. In this paper, we aim to include transitional trend information by extracting the transition counts. For segments \(X_{p}\), we count the number of transitions, denoted by \(\gamma_{i,j}\) where \(i,j=1,\ldots,\alpha\), from sub value space \(S_{i}\) to \(S_{j}\) as follows:  
\[\gamma_{i,j}=\sum\
olimits_{d=K(p-1)+1}^{Kp}\mathbf{I}(x(t)\in S_{i})\ \mathbf{I}(x(t+1)\in S_{j}), \tag{2}\]  
where \(\mathbf{I}(A)\) is \(1\) if the relation \(A\) is true, and \(0\) otherwise. Let us define \(\bar{x}^{(i)}\) to be the average of \(x(t)\) in sub value space \(S_{i}\): \(\bar{x}^{i}=1/|S_{i}|\sum_{t:x(t)\in S_{i}}x(t)\). When applying all combinations of sub value spaces, \(S_{1},S_{2},\ldots,S_{a}\), we form a transition matrix, \(\boldsymbol{\gamma}=[\gamma_{i,j}]\) of size \(\alpha\times\alpha\): element \(\gamma_{i,j}\) means the number of transitions from \(S_{i}\) to \(S_{j}\). The use of transition matrix \(\boldsymbol{\gamma}\) enables us to state terms relating to trend. We call the collection of \(\gamma_{i,j}\) in which \(|i-j|\) is constant a trend. In particular, \(\sum_{i=1}^{a}\gamma_{i,j}\) defines a sojourn trend as the sum of each piece of sojourn information \(\gamma_{i,j}\). In Figure 1, for instance, \(\alpha\) is set to \(3\), and three sub value spaces, \(S_{1}\), \(S_{2}\), and \(S_{3}\), exist. For the first segment \(X_{1}\), the transitional information of values moving in sub value spaces is stored in \(\mathbf{\gamma}=[[4,0,0],[1,16,1],[0,1,40]]\). While all transitional elements \(\gamma_{i,j}\) are worthwhile, we focus on one-step upward and downward transitional information with sojourn information. For example, \(\gamma_{2,1}(=1)\) represents the frequency of one-step upward transitions from the sub value space \(S_{2}\), and \(\gamma_{2,3}(=1)\) represents that of one-step downward transitions from \(S_{2}\). The diagonal elements, \(\gamma_{1,1}(=4)\), \(\gamma_{2,2}(=16)\), and \(\gamma_{3,3}(=40)\), represent the sojourn trends in the three subspace spaces, respectively. If the sum of one-step upward transitions \(\gamma_{2,1}+\gamma_{3,2}\) is zero, it means non-existence of upward trend and possible downward or steady trend. Observe that \(0\leq\gamma_{i,j}\leq n-1\) since the most continuous transition pattern is to remain in a sub value space. We apply the above-mentioned transitional information to SAX, denoting the proposed approach transitional SAX. The overall algorithm is summarized in Algorithm 1. We notice that, as shown in Algorithm 1, a new representation for time series \(X\) of size \(N\) is the output in Algorithm 1, \(V=[W,Z]\) of size \(n(1+\alpha^{2})\) since each segment produces a symbol for the local average plus \(\alpha^{2}\) of the transitional information.