異常検知（変化検知）の詳細と特異変換スペクトルと動的時間伸縮法まとめ（機械学習）

異常検知とは、機械学習の一手法で、普通の値のデータの中から極端に大きかったり、小さい値の「異常」なデータを見つけ出すものだ。

異常検知の用途で有名どころは巷では以下のようなものがメインらしい

・マーケティング　＝＞流行のブレイクの検出
・コンプライアンス  ＝＞情報漏洩/不正検知
・製造系   ＝＞不具合発生検知
・機械系  ＝＞故障検出
・システム運用系  ＝＞障害検出
・ネットワーク運用系  ＝＞トラフィック異常検出
・WEB系  ＝＞トピック潮流変化検出
・セキュリティ系  ＝＞攻撃・侵入検出（コンピュータウィルスやDOS攻撃）
・サイバー犯罪に使うやつ＝＞情報潮流、なりすまし

いずれも普通じゃないデータとか、珍しいデータを検出するものだ。

異常検知の3種類
異常検知は主に3つのタイプに分かれる。機械学習シリーズの書籍とかに詳しく載ってるので、ここでは簡単に触れとく。

まず触れておきたいのは異常検知で扱うデータには「定常データ」と「非定常データ」がある。異常検知ではこの2つで使う手法が異なる。
定義は以下の通り

定常データ：同じ波形が続くような時系列データや、統計的にデータ分布図が正規分布（山が一つの単純な曲線）になる

非定常データ：同じ波形が続かない時系列データや、統計的なデータ分布図が正規分布にならない（山が２つ以上の曲線）

・外れ値検知
すでに持ってる（既存の）データから異常なデータや異常箇所を割り出す手法。
正常データと異常データの割合→99：1

くらいのデータ、つまり正常データがほとんどで異常データ少ししかないデータが対象になることが多い。

外れ値検出のほとんどのアルゴリズムは定常データを扱う。
その時は、マハラノビス距離で求められるアルゴリズムに限定させることが多い。代表的なものに、k-means、ランダムフォレスト、one class SVMなどがある

・変化検知
これは主に定常/非定常な時系列データなどに多く使うもので、データが大きく変化する点を検知する。googleである「急上昇ワード」が好例だ。扱うデータは非定常データであることが多い。

変化検知で、非定常データを扱うときのアルゴリズムには、いろいろある。メジャーなのは
・特異変換スペクトル
・動的伸縮法
・LSTMなどの時系列を予測するアルゴリズム

などを使うケースが多い。

・異常行動検知
これは多くのユーザーと違う行動をとるユーザーを検出するときに使う。
手法としては、同じ行動をとる多くのユーザーの行動を統計的に確率分布でパターン化し正常データとして扱う。逆に、その確率分布のパターンと異なる分布のデータになるユーザーを異常行動をしたユーザーとみなし、検出する。
ググるとLSTMとかがよく使われてる。

特異変換スペクトル（Singular Spectrum Transformation ：SST）について

特異変換スペクトルは主に非定常データにおける異常部位の検出に使う（もちろん定常データにも使える）

特異変換スペクトルは、非定常データでもデータが大きく変化してる点（異常箇所）を検出できる。訓練データやテストデータはいらず、検出したいデータだけ用意すれば、numpyで簡単に実装できる
詳しい数式や論理とかは専門書や論文に任せてここではコードで実装みる。

まず検出したいデータは約半年分の検索ワードを2つ（AとB）を取り出して、特異変換スペクトルにかけてみた。

ワードA、Bの可視化

ワードA
f:id:trafalbad:20180809154943p:plain

ワードB
f:id:trafalbad:20180809155015p:plain

特異変換スペクトルのメイン実装コードは以下のようになる。ついでに結果を可視化した。

from sklearn.preprocessing import MinMaxScaler
 
mss=MinMaxScaler()
train1_frame=pd.DataFrame(mss.fit_transform(df_train1))
train2_frame=pd.DataFrame(mss.fit_transform(df_train2))
 
defembed(lst,dim):
emb=np.empty*1
emb=np.append(emb,tmp,axis=0)
returnemb
 
train1=np.array(train1_frame[0],dtype='float64')
 
w=168# 部分時系列の要素数
m=2# 類似度算出に使用するSVDの次元数
k=int(w/2)# SVD算出に用いる部分時系列数
L=int(k/2)# # 類似度を比較する2つの部分時系列群間のラグ
Tt=train1.size
anomaly_score=np.zeros(Tt)
 
# 異常値のスコアを算出するメソッド
score_list=[]
fortinrange(w+k,Tt-L+1+1):
tstart=int(t-w-k+1)
tend=t-1
# t以前の部分時系列群
X1=embed(train1[tstart:tend],w).T[::-1,:]
# 異常度算出対象の部分時系列群(test matrix)
X2=embed(train1[(tstart+L):(tend+L)],w).T[::-1,:]
 
# X1にSVDを行い上位m次元を抜き出す
U1,s1,V1=np.linalg.svd(X1,full_matrices=True)
U1=U1[:,0:m]
# X2にSVDを行い上位m次元を抜き出す
U2,s2,V2=np.linalg.svd(X2,full_matrices=True)
U2=U2[:,0:m]
 
# U1とU2の最大特異値を取得
U,s,V=np.linalg.svd(U1.T.dot(U2),full_matrices=True)
sig1=s[0]
 
# 最大特異値の2ノルムを1から引くことで異常値を得る
anomaly_score[t]=1-np.square(sig1)
score_list.append(anomaly_score[t])
 
 
score_=np.reshape(score_list,(len(score_list),))
 
# 変化度をmax1にするデータ整形
mx=np.max(score_)
score_=score_/mx
 
# trainデータの異常部位plot
train_for_plot=np.array(train1_frame[0],dtype='float64')
fig=plt.figure()
ax1=fig.add_subplot(111)
ax2=ax1.twinx()
 
p1,=ax1.plot(score_,'-b')
ax1.set_ylabel('degree of change')
ax1.set_ylim(0,1.2)
p2,=ax2.plot(train_for_plot,'-g')
ax2.set_ylabel('original')
ax2.set_ylim(0,12.0)
plt.title("Singular Spectrum Transformation")
ax1.legend([p1,p2],["degree of change","original"])
plt.show()