# SMM: Leveraging Metadata for Contextually Salient Multi-Variate Motif Discovery
## 4 SMM: Contextually Salient Multi-Variate Motif (CS-motif) Discovery
### Frequently Recurring Motif Search  
Once the salient multi-variate sub-sequences of the given multi-variate time series are identified and collected, the next step is to cluster these sub-sequences into recurring patterns, a _motif bag_. Since the number of distinct motifs in the time series or the number of sub-sequences in each of these motifs may not be known ahead of time, we need to leverage an adaptive clustering strategy, which not only automatically identifies the number of similarity clusters in the data, but also prunes away those multi-variate patterns that do not belong to any of the identified clusters. To search for the matching motifs across the same or different variate groups, we propose the two following strategies under two different scenarios:  
1. **Finding motifs across the same variate groups**, by considering all the features extracted from a multi-variate time series. This requires a three-step process: (a) Wecreate groups of features existing in the same or a similar variate scope; the results are clusters of features sharing the same or a similar variate scope. (b) To identify groups of features with similar behaviors, in each of the groups we apply one cluster (adaptive \(K\)-means). (c) In each group of these features, a pruning process is applied to clean the outlier instances from the clusters using standard deviation from the feature centroid. 2. **Targeting motifs across multiple (potentially different) variate groups**. Considering all the features extracted from a multi variate time series, we apply the following steps: (a) First, a clustering technique is applied; in our results, we use adaptive \(K\)-means. The clustering process would allow us to identify groups of instances with similar behaviors across potentially different variate groups. (b) For each cluster identified, a pruning step is applied, which takes each cluster centroid and the corresponding standard deviation into consideration. This would allow the proposed framework to arrive at bags of motifs, each containing instances from multiple variate sets. (c) The final step is sub-clustering (we group instances in each motif bag \(M_{i}\) having a similar or the same variate scope), which would be applied to the search for motifs existing on the same variate groups. While any clustering approach (e.g., density-based clustering, such as DBScan [35]) can be used for this purpose, in our implementation, we use an adaptive \(K\)-mean strategy, based on the Euclidean distance of the sub-sequence descriptors. Depending on the type of motifs being searched, additional constraints (such as being of a similar length, or being aligned along similar sets of variates) are considered when forming and maintaining the clusters. Intuitively, each of these clusters represents a potential motif. However, these clusters may contain sub-sequences that do not share the same pattern and, thus, do not belong to the corresponding motif. In order to eliminate these spurious sub-sequences, prune outliers from each cluster. More specifically, the pruning step works in the following way: for each cluster \(\mathcal{C}_{h}\) we identify the mean descriptor and the standard deviation  
\[D_{mean,h}=\underset{subseq_{i}\in\mathcal{C}_{h}}{AVG}(D_{i}),\]  
\[sdev_{h}=\underset{subseq_{i}\in\mathcal{C}_{h}}{STDEV}(\Delta(D_{i},D_{mean,h})),\]  
of the distances of the sub-sequences in the cluster from this mean descriptor. Once these are computed, we eliminate any sub-sequence \(subseq_{i}\) in \(\mathcal{C}_{h}\), such that  
\[\Delta(D_{i},D_{mean,h})>3\times sdev_{h}.\]  
Intuitively, assuming that the cluster represents a single motif pattern and that the distances of the descriptors (corresponding to a motif pattern) from the mean descriptor follow a normal distribution, this would help eliminate those sub-sequences that have less than 0.03% likelihood of being part of the corresponding motif. Once the initial descriptor-based clusters are obtained, we further partition these clusters based on variate overlaps. However, this is an optional step.