## 4 Methodology
### Pattern Discovery Method  
Upon completion of data collection and time series preprocessing, the pattern discovery phase is activated. As described on Section 3, we rely on the SAX algorithm to discretize the input time series. Formally, for time series T of length \(m\) SAX obtains a lower-dimensional representation by initially performing a z-normalization and then dividing the time series into \(w\) equally-sized segments \(s\). Afterwards, for each segment, SAX computes a mean value and maps it to a symbol according to a predefined set of breakpoints, thus dividing the data space into A equiprobable regions, where A is the user-specified alphabet size. It is typical for pattern discovery applications to apply SAX to a set of subsequences, in order to capture local features, implemented via sliding windows. The process is finalized by applying Sequitur, a linear time and space algorithm that derives a context-free grammar from a string incrementally [17]. By identifying frequent subsequences in the input string, the algorithm builds a compact context-free grammar reflecting the input string specificity and outputs the patterns, represented as rules and expressed as vectors of time intervals. Each rule \(R_{i}\) is of the form:  
\[R1:[(ts_{start}^{1},ts_{end}^{1}),(ts_{start}^{2},ts_{end}^{2}),\ldots,(ts_{start }^{k},ts_{end}^{k})]\]  
where parentheses represent time periods and \(ts_{start}^{i}\), \(ts_{end}^{i}\) represent the beginning and end of the \(i\)-th appearance. For example, if a pattern rule R1 (\(R\#1\)) is represented as [(10, 28), (50, 70)], its meaning is that it starts at Timestamp 10 and finishes at Timestamp 28 the first time and then reappears at interval (50, 70). Due to the fact that pattern discovery methods cannot cope with multiple time series and find a similar pattern within a single one, we invented a pattern sharing method in order to verify whether a pattern appearing on one time series has a similar time appearance within another time series. For that reason, we compared pairs of time series, keeping the stock closing data a common factor and altering the other two, namely the sentiment score of financial news and the Tweets that were mentioning this stock. The pattern (rule) similarity estimator across the two time series algorithm operates as follows:  
1. Identify patterns within the stock closing price signal, of length \(N\). Each pattern \(p_{i}\) has the form of: \[p_{i}=[(t_{i},t_{j}),\ldots,(t_{k},t_{l})]\] where \(i,j,k,l\in[1,\ldots,N]\). 2. Compute the mean DTW distance of all extracted patterns, denoted by: \[MDTW_{all}\]
3. For each pattern: 1. Calculate the DTW distance between the two time series (closing--sentiment as well as closing--number of Tweets) in every space contained in the rule \(\pm 3\) days. Let each distance be \(MDTW_{i}^{m}\), where \(i\) refers to the pattern and \(m\) to the distinct number of rule spaces. 2. Average each \(MDTW_{i}^{m}\) to find the mean DTW distance for the whole pattern, denoted as \(MDTW_{i}\). 4. If \(MDTW_{i}<MDTW_{all}\), then the rule is considered as valid for both time series. 5. Return this pattern. Rules are further evaluated with regards to their validity by applying the following test: random windows of size \(w\) are selected, and the DTW distance is measured between the two signals. The mean distance of all windows \(DTW_{w}\) is compared against the mean distance \(DTW_{r}\), found by the rule extraction process. If \(DTW_{w}\leqslant DTW_{r}\), then the rule is not valid, since random windows were found to contain better time series correlations. On the other hand, if the inequality is not true, then the rules found better correlations between the two time series. The Figure 3 depicts the test outcome on a small segment of the Apple (AAPL) stock closing time series, accompanied by the corresponding sentiment signal for the same period. As we can see, the upper part contains a rule, as extracted from the previous process.