[[research/tsifter/TSifter]]のステップ１のアイデア。
[[線形回帰]]での回帰線と実線の交点間を積分区間とした面積に偏りがあれば、異常であるととらえる[[異常検知]]法。
正常メトリクス削除のための単変量時系列データの異常検知への要件を次に列挙する。
検知対象の異常パターンは１３種類（[[PatternMatcher メトリクスの典型的な13種類の異常パターン]]）である。
[[メトリクスの変化開始時刻と障害発生時刻との間の遅延]]より、時系列の解析期間は障害検知時から遡って50分前までとする。
期間内に単一の時系列に含まれる異常箇所は1個とする。
メトリクス数の増大の背景からメトリクスごとにモデルの仮定やチューニングを不要とする。
そこで、我々は線形トレンド定常モデルの残差和に基づく異常検知法AD-LPRS（Anomaly Detection with Liner Trend based Residual Sum）を提案する。
時刻$t$の値を$y_t$、傾きを$a$、切片を$b$、時刻tの誤差を$\epsilon_t$とすると、線形トレンド定常モデルは式（\ref{eq:trend_stationality_model}）のように定義される。
$
\label{eq:trend_stationality_model}
y_t = at + b + \epsilon_t
$
AD-LPRSは、実測線と線形トレンド線との交点、または、実測線の端点を通る時間軸に垂直な直線と線形トレンド線との交点により区切られる$u$番目の区画の残差和$S_{u}$を異常度とする。
式（\ref{eq:trend_stationality_model}）の係数$a$と$b$の値は、メトリクスの時系列データを用いて式（\ref{eq:trend_stationality_model}）を最小二乗法で解くことで近似的に算出される。
時刻$t$における残差を$\epsilon_t$、区画$u$の標準偏差を$\sigma_u$、u番目の区画の開始点を$t_u$とすると異常度$S_{u}$を以下のように表す。
$
S_u = \sum_{t=t_{u-1}}^{t_u-1}\left(\frac{\epsilon_t}{\sigma_u}\right)^2
$
$S_i$の最大値に対して、閾値を設定し、閾値を超えると異常が検知される。
AD-LPRSの直感的理解は、１ヶ月や１年の長期の大域的な変化のうち直近の局所的な変化を線形近似可能であると仮定した上で、線形トレンドから逸脱する領域の広さを異常度とみなすことである。
本異常検知法により、ノイズ部位は交点が多くなるため、ノイズ部位で異常が検出されにくくなる。
```tex
\begin{algorithm}[tb]
\caption{AD-LPRS}
\label{algo:liner-trend-ad}
\begin{algorithmic}[1]
\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}
\Require{The time series values of a metric, $\{x_t\}$}
\Ensure{Anomaly degree, $a$}
\State $\{r_t\} \gets$ calculate residuals from ${\{x_t\}}$ with ordinaly least square
\State $std \gets$ calculate standard deviation of $\{r_{t}\}$
\State \textbf{for} \textbf{any} $t$ \textbf{let} $\{r_t\} \gets r_t/std$
\State \textbf{new} $\{t_u\}$
\For{$i = 0;$ $i < |\{r_{t}\}|;$ $i\plus\plus$}
\If{$(r_i > 0$ \textbf{and} $r_{i+1} <= 0)$ \textbf{or} $(r_i < 0$ \textbf{and} $r_{i+1} >= 0)$}
\State append $i$ into $\{t_u\}$
\EndIf
\EndFor
\State $\{s_{u,v}\} \gets$ split $\{r_t\}$ with $\{t_u\}$ indices
\State \textbf{new} $\{rs_u\}$
\For{$j = 0;$ $j < |\{s_{u,v}\}|;$ $j\plus\plus$}
\State \textbf{new} $\{s'_{v}\}$
\For{$k = 0;$ $k < |\{s_{j,v}\}|;$ $k\plus\plus$}
\State append $s_{j,k}^2$ into $\{s'_{v}\}$
\EndFor
\State append Sum($\{s'_{v}\}$) into $\{rs_u\}$
\EndFor
\State $a \gets$ Max(${\{rs_u\}})$
\end{algorithmic}
\end{algorithm}
```