DEIM Forum 2017 I2-4

動的なデータ集合に対応した対話的外れ値分析手法
坂詰

知完†

北川

博之††

天笠 俊之††† 筑波大学システム情報工学研究科 〒 305-8573 茨城県つくば市天王台 1-1-1†† 筑波大学計算科学研究センター 〒 305-8577 茨城県つくば市天王台 1-1-1
E-mail: †sakazume@kde.cs.tsukuba.ac.jp, ††{kitagawa,amagasa}@cs.tsukuba.ac.jp
あらまし

データマイニングにおいてデータ集合の中で他と大きく異なる値をもつ外れ値を検出することは重要なタスクとなっている．代表的な外れ値検出手法の一つとして距離に基づく手法があるが，ユーザが求める外れ値を検出するための適切なパラメタの選択が容易でないことが知られている．この問題に対し，ユーザが求める外れ値の検出に適切なパラメタ選択を支援する対話的な外れ値分析手法 ONION が提案されている．ONION では対象データ集合
を事前に分析し索引構造を構築することで，種々の対話的分析を支援する．しかし，索引構造の更新については考慮されていなく，データの追加や削除，更新が行われる場合は効率的な更新が不可欠である．本研究では ONION の索
引構造に加えて，グリッド索引とカウンタを組合せて用いることで，動的なデータ集合に対応した対話的外れ値分析手法を提案し，実験によりその有用性を評価する．
キーワード

外れ値分析，ONION，動的データ，索引構造

1. は じ め に法含めた 2 種類の手法と比較し，提案手法の有用性を評価する．
本論文の構成は以下の通りである．2. 章で関連研究について

データマイニングにおいてデータ集合の中で他と大きく異な説明し，3. 章では距離に基づく外れ値検出手法とその問題点にる特徴や値をもつデータを検出することは重要なタスクとなっついて述べる．4. 章では ONION の概要を説明し，5. 章で動的ている．Hawkins は外れ値を “異なるメカニズムで生成されたなデータ集合での外れ値検出の問題点とそれを ONION に適用

疑いを喚起するような他の観測値から大きく外れた観測値” としたときの問題点について述べる．6. 章では提案手法の詳細をしている [1]．外れ値検出は多くのアプリケーションで用いられ説明し，7. 章で評価実験について述べる．最後に 8. 章で本論ており，例えばクレジットカードの不正使用検出や科学データ

文をまとめる．

に対する測定誤差の識別，監視ビデオでの異常行動検出などがあげられる．

2. 関 連 研 究

現在まで様々な外れ値検出手法が提案されているが，代表的な

現在，様々な外れ値検出方法が提案されているが，最も古典手法として距離に基づく手法 [2] [3] [4] や最近傍に基づく手法 [5]，的な外れ値検出手法の 1 つとして距離に基づく手法 [2] がある．

密度に基づく手法 [6]，クラスタリンクに基づく手法 [7] [8] [9]，距離に基づく外れ値検出 [2] は，対象のオブジェクトを中心に統計に基づく手法 [10] [11]，角度に基づく手法 [12] [13] がある．

半径 r の円内にあるオブジェクト数が k 個未満のとき，対象のこれらの外れ値検出手法の中でも古典的で代表的な手法は距離

オブジェクトを外れ値とする手法である．最近傍に基づく外れに基づく手法 [2] である．しかし，適切な外れ値の検出をする

値検出 [5] では，対象のオブジェクトと k 近傍のオブジェクト

ためには適切なパラメタ設定が必要になる．この問題を解決す

間の距離を計算し，その距離に基づいてオブジェクトがランクるために，L.Cao らは ONION [14] を提案した．ONION は対付けされる．ランキング上位 n 個のオブジェクトが外れ値とな

話的な外れ値分析を提案しており，ユーザが求める外れ値を検る．密度に基づく外れ値検出 [6] では，外れ値度を示す局所外出するための適切なパラメタを示す．しかし，ONION は静的

れ値因子 (LOF) を用いる．LOF 値は各オブジェクトの k 近傍

なデータ集合を対象としており，動的なデータ集合には対応しオブジェクトとの密度差によって決まり，LOF 値が高いオブていない．近年の IoT やセンサ，ソーシャルメディアの発達にジェクトを外れ値とする．

伴い，動的なデータ集合が増加している．データ集合が変化す

また，近年の動的データやストリームデータの増加に伴い，ることによって外れ値も変化するため，外れ値検出にもリアル

それらに対する外れ値検出手法が研究されている．Angiulli ら

タイム性が求められている．

は距離に基づく外れ値検出手法をストリームデータに拡張した

そこで本研究では，動的なデータ集合に対応した対話的外手法 [15] を提案した．この手法では単位時間に 1 つの値が到着

れ値分析手法を提案する．データ集合の更新が行われた場合，するストリームデータを想定し，一定期間内に到着した値の集ONION の索引構造を更新するための計算を素朴な方法で行う合に対して外れ値検出を行う．石田らは時系列データストリーと多くの時間がかかってしまう．そのため，ONION を動的なム上の連続した外れ値検出手法 [16] を提案した．この手法では，データ集合に適用させるためには ONION の索引構造を効率的

現在のデータ集合は直前の時刻の集合が変化したものであり，に更新する必要がある．実験では提案手法に対して，素朴な方

その変化があまり大きくない場合が多いことを利用した差分計

算法を用いる．差分計算法では，直前時刻の集合における外れ値検出結果を利用して差分計算を行い，距離に基づく外れ値検
出手法により現在の集合における外れ値を検出する．
本研究では，動的なデータ集合に対して ONION の索引構造を用いた対話的な外れ値検出を行う．

3. 距離に基づく外れ値検出手法
図 2 オブジェクトの分布

本章では，本研究の基本となる外れ値検出手法での外れ値の

図 3 k=3，r=5 の場合

定義とその問題点について説明する．

3. 1 定義本研究では，外れ値の定義として Knorr らが提案した距離に基づく外れ値検出 [2] によるものを用いる．Knorr らは外れ値の定義を “対象のオブジェクトを中心に半径 r の円内にあるオブジェクト数が k 個未満のとき，対象のオブジェクトを外れ値とする” としている．図 1 は距離に基づく外れ値検出の例を示しており，左右の図は同じデータ集合である．k=3 ではオブ

図 4 k=2 と r=5 の場合

図 5 k=3 と r=10 の場合

ジェクト A は正常値になり，オブジェクト B は外れ値になる．

4. 1 概要ONION は L.Cao らが提案したもので，距離に基づく外れ値検出手法において適切なパラメタ選択を行うことが難しいという問題に対して，事前に対象のデータを索引付けすることで，パラメタを変化させたときに検出される外れ値がどのように変化するか，指定したオブジェクト集合を外れ値とするパラメタ
図 1 距離に基づく外れ値検出

範囲はどのような範囲か，等の対話的な外れ値分析を支援する．

ONION での外れ値分析はパラメタ k を [kmin ，kmax ]，パ
3. 2 適切なパラメタ設定の難しさ

ラメタ r を [rmin ，rmax ] の範囲で考え，ユーザが求める外れ

距離に基づく外れ値検出では各オブジェクトが外れ値である値を検出するための適切なパラメタを示す．kmin と rmin はか，または正常値であるかがパラメタ k と r によって決定すそれぞれの下限，kmax と rmax はそれぞれの上限である．各る．そのため，適切な外れ値を検出するためには適切なパラメ

オブジェクトは必ず正常値 (IL)，必ず外れ値 (OL)，外れ値候

タ選択が重要となる．パラメタによっては正常値とみなされる

補 (OC) のいずれかに分類される．IL のオブジェクトは k ∈べきオブジェクトが外れ値として検出されることや，その逆も[kmin , kmax ] と r ∈ [rmin , rmax ] の範囲内で必ず正常値であり，起こり得る．図 2，3，4，5 はパラメタ k と r の設定によって一方で OL のオブジェクトはその範囲内で必ず外れ値である．

検出される外れ値がどのように変化するかを示している．図

OC はパラメタによって正常値または外れ値になる．本論文で2 はオブジェクトの分布を示しており，ユーザが外れ値としては，オブジェクト O と O の k 番目の近傍オブジェクト間の距

検出したいオブジェクトをオブジェクト A と B とする．k=3，

kmax <k
離を DOと示す．もし，DO= rmin ならばオブジェクト O

r=5 の場合，図 3 で示されるようにオブジェクト A と B に加は IL であり，DOmin > rmax ならばオブジェクト O は OL でえて，オブジェクト C，D，E，F も外れ値として検出されてある．どちらの条件にも一致しないオブジェクトは OC である．

k

しまう．k=2，r=5 の場合，図 4 で示されるようにオブジェク

ONION は 4. 2 節で説明される索引構造を用いることによっト A と B のどちらも外れ値として検出されない．k=3，r=10て，k∈ [kmin , kmax ] と r ∈ [rmin , rmax ] の各選択 (k, r) に対の場合，図 5 に示されるようにオブジェクト A と B に加えて，して OC のどのオブジェクトが正常値または外れ値であるか

オブジェクト E が外れ値として検出される．ユーザの意図と一を効率よく識別する．ONION は OC に対して comparative

致し，ユーザが検出したいオブジェクトに類似した特徴をもつ

outlier analytics (CO) と outlier-centric parameter space ex-

オブジェクトを検出するためには，適切なパラメタを選ぶこと

ploration (PSE)，outlier detection (OD) の 3 種類の外れ値分が重要である．

析を提案している．CO はユーザが外れ値として検出したいオ

4. ONION

ブジェクト集合 Oin を入力とし，Oin が外れ値であるときに外れ値になる他のオブジェクト集合を識別する．PSE はユーザが本章では，はじめに本研究で用いる ONION [14] の概要につ外れ値として検出したいオブジェクト集合 Oin を入力とし，そいて説明する．その後，本研究で対象とする ONION の索引構れに近い外れ値集合とパラメタ集合のペア (k, r) を見つける．

造についての詳細を説明する．

OD はパラメタのペア (k, r) を入力とし，そのとき外れ値とな図6

オブジェクト表
図 8 オブジェクトの追加

図 9 オブジェクトの削除

図 10 オブジェクトの更新
図 7 P-Spaceをサポートする．ここでは例として outlier-centric parameter

space exploration (PSE) を用いた対話的外れ値分析を説明するオブジェクトを検出する．また，OD では NULL をパラメタる．上記で示したように，最初にユーザが外れ値として検出しとして与えることができ，その場合は全ての OL を出力する．

たいオブジェクト集合 Oin を指定する．ONION は P-Space を

4. 2 P-Space

用いて Oin に近いオブジェクト集合を外れ値として検出するた

OC に 対 す る 上 記 の 対 話 的 分 析 を サ ポ ー ト す る た め に ，めのパラメータを示す．近さは δ(−1 < δ < 1) によって決まONION は ONION 空間 (O-Space) とパラメタ空間 (P-Space)，

る．もし，検出された外れ値の数をユーザが多いと判断したら，データ空間 (D-Space) と呼ばれる 3 種類の索引構造を提案して

δ<= 0 で |Oj | = (1 + δ)|Oin | となるパラメタ k と r を示す．こいる．各索引構造は OC のオブジェクトを分析することが主な目的であるため，OC のみで構成されている．O-Space は各オ
ブジェクト O ∈ OC から ki (kmin <= ki <= kmax ) 番目に近いオk

ブジェクトまでの距離 DOi を計算し，OC ごとに kmax -kmin +1
個の距離の値を保持する．P-Space は kmax -kmin +1 個のテーkブルをもつ．i 番目のテーブルは全ての OC からの距離 DOi をのとき Oj ⊂=Oin である．もし，外れ値の数を少ないと判断したら，δ >= 0 で |Oj | = (1 + δ)|Oin | となるパラメタ k と r を示
す．このとき Oj ⊃=Oin である．

5. 動的データ集合での外れ値分析
データ集合が動的な場合，オブジェクトの追加や削除，更新

昇順で保持する．D-Space はオブジェクト間の支配関係に基づが起こり得る．データ集合の変化により，新しく追加または更いで構築される．データ集合の中で，外れ値候補 Oi は他のオ

新されたオブジェクトに加えて，既存オブジェクトの正常値とブジェクト Oj より外れ値度が大きい場合がある．すなわち，外れ値の判定が変化する可能性がある．本章では，例を用いて任意のパラメタに対して，Oi は Oj が外れ値であるときは常にオブジェクトの追加，削除，更新が行われた場合のオブジェク

外れ値になる．この関係を支配関係と呼ぶ．D-Space は全てのトの正常値と外れ値の判定の変化を示す．なお，ここでは k=3

OC を複数の支配グループに分割する．同じ支配グループに属とした場合を想定する．

するオブジェクトは支配関係をもつ．

OC に対して O-Space，P-Space，D-Space のいずれも上記

5. 1 データ集合の変化
図 8 ではオブジェクト H が追加された場合を示している．オの対話的分析が可能であるが，[14] で P-Space は O-Space より

ブジェクト B を中心とした半径 r の円内にあるオブジェクト数

良い性能を示しており，動的なデータ集合に対する D-Space のは 2 つであるため，オブジェクト B は外れ値である．しかし，更新は難しいということから，本研究では P-Space を用いる．

オブジェクトの追加によって，オブジェクト B は正常値になる．

データ集合の全てのオブジェクトはオブジェクト表に登録され，オブジェクト H は正常値である．図 9 ではオブジェクト G が図 6 で示されるように ID が与えられる．(簡略化のために 2 次削除された場合を示している．オブジェクト G が削除される以元のオブジェクトを例に用いているが，高次元であっても同様

前，オブジェクト C は正常値である．しかし，オブジェクト Gである．)P-Space は図 7 に示されるように kmax -kmin +1 個のが削除されることによって，オブジェクト C は外れ値になる．

テーブルから成る．i 番目のテーブルには OC のオブジェクト

図 10 ではオブジェクト G が更新される場合を示している．も

ki
ki
の昇順
) が保持されており，DO
Oj に対するペア (IDj , DOjj

で並んでいる．

4. 3 P-Space を用いた対話的外れ値分析
P-Space は上記に示した全ての対話的分析の効率的な処理

し，オブジェクト G が更新によって移動した場合，オブジェク
ト B は外れ値から正常値に変わり，オブジェクト C は正常値
から外れ値に変わる．オブジェクト G は正常値である．

5. 2 動的環境における ONION の問題点
ONION は与えられたデータ集合を分析し，初めにオブジェ
クトを IL，OL，OC のいずれかに分類する．データ集合が動的である場合，正常値と外れ値の判別は上記のようにデータ集合の更新に応じて変化し，IL や OL，OC へのオブジェクトの分類が変わる．例えば，新しいオブジェクトが 1 つ追加された
ときは OL のオブジェクトが OC になり，OC のオブジェクト
が IL になる可能性がある．同様に既存のオブジェクトが 1 つ削除されたときは IL のオブジェクトが OC になり，OC のオ
ブジェクトが OL になる可能性がある．オブジェクトの更新は

図 11

オブジェクトの追加と削除の組合せであるため，上記の全てのグリッド索引変化が起こり得る．また，複数のオブジェクトを同時に追加，削除，更新した場合，OL のオブジェクトが IL に，IL のオブジェクトが OL になる可能性もある．本論文では，このような変化を状態変化と呼ぶ．
動的なデータ集合で ONION のような対話的分析を可能にす
るには，P-Space を継続的に更新する必要がある．素朴な方法
で P-Space の再計算を行う場合，多くの距離計算とソートが必要になるため，更新に多くの時間がかかってしまう．P-Spaceの更新をするためには 2 つのステップがある．1 つ目がデータ

図 12 グリッド索引の内容

集合の更新によって状態変化があるオブジェクトを見つけることである．つまり，OC ではなくなるオブジェクトや新しく OCになるオブジェクトを調べる必要がある．2 つ目は現在の OCから成る P-Space の更新である．次の章ではこれらの 2 つのス
テップを効率的に行う手法を提案する．

6. 提 案 手 法

図 13拡張したオブジェクト表

提案する手法は以下の 2 つのステップから成る．(1) 状態 (IL，

OL，OC) が変化するオブジェクトを検出することと，(2) デー

新しいオブジェクトが追加された場合，そのオブジェクトをタの更新による P-Space の更新を行うことである．これらを中心に半径 rmin と rmax の円内にあるオブジェクト数を計算す

効率的に行うために，本研究ではグリッド索引と拡張したオブる必要がある．グリッド索引を用いることで，円内に含まれるジェクト表を用いる．素朴な方法はオブジェクトの状態変化をグリッドと円に重なっているグリッドに存在するオブジェクト

検出するために全てのオブジェクトのペアで距離の再計算をしのみに注目すればよい．その計算に基づいて，新しく追加されなければならない．グリッド索引と拡張したオブジェクト表はたオブジェクトは IL または OL，OC のいずれかに分類される．

P-Space を効率的に更新することを可能にする．

もし，IL か OL ならば P-Space で保持する距離の値を計算す

本研究では 1 つのオブジェクトまたは複数のオブジェクトのる必要はない．また，オブジェクトが追加されることによって追加と削除，更新を対象とする．P-Space に影響を与える状態

既存オブジェクトの状態変化を調べる必要がある．拡張された

変化は追加の場合，OL から OC と，OC から IL である．削除

オブジェクト表で保持するカウンタは，状態変化を調べるための場合は IL から OC と，OC から OL である．更新は追加と削の距離計算を減らす役割をもつ．状態変化の有無を確認しなけ

除の組合せであるため，上記の全ての状態変化が影響を与える．

ればならないオブジェクトは追加されたオブジェクトから距離

6. 1 グリッド索引とカウンタをもつ拡張したオブジェクト表

rmax 内にあるものである．そのオブジェクトの rmin カウンタ

グリッド索引は図 11 で示されるようにオブジェクト空間をと rmax カウンタは更新しなければならない．その後，OL か

分割し，各グリッドは図 12 のようにオブジェクト数とそのオ

ら OC と，OC から IL に状態変化したオブジェクトに注目し，ブジェクト ID を保持する．また，オブジェクト表は図 13 で示

P-Space の更新を行う．

されるように rmin カウンタと rmax カウンタ，オブジェクトの6. 2 状態変化を検出するアルゴリズム

状態が加わることによって拡張される．rmin カウンタと rmax

状態変化を検出するアルゴリズムをアルゴリズム 1 に示す．

カウンタは，それぞれ rmin と rmax 内にある近傍オブジェク

状態変化の有無を調べるために追加または削除されたオブジェ

ト数を表している．カウンタを保持することによって，データ

クトを中心に半径 rmin と rmax の円内にあるオブジェクトのカ集合の更新の際に必要になる計算を減らすことができる．種別

ウンタを更新しなければならない．オブジェクトの更新の場合の欄では各オブジェクトの状態 (IL，OL，OC) を保持する．

は，移動前のオブジェクト位置でオブジェクトが削除され，移Algorithm 1 状態変化アルゴリズム

Algorithm 2 P-Space の更新アルゴリズム

1: for each Grmin do

1: for each OC ではなくなったオブジェクト On do

2:rmin ，rmax カウンタと状態変化を更新する．

2:

3: end for

3:

4: for each Gormin do

4:

5:
6:
7:

for each Gormin にあるオブジェクト do
距離 (distmin ) を計算する．
< rmin thenif distmin =rmin ，rmax カウンタと状態変化を更新する．

8:
9:

else
rmax カウンタと状態変化を更新する．

10:

for i = 1 to kmax − kmin + 1 do
P-Space から On に関する情報を削除する．
end for

5: end for
6: if 新しいオブジェクトが追加される then
7:
8:
9:

for each OC のままだったオブジェクト O do
距離 (distnew ) を計算する．
<
if distins= distnew <= distinsmax then
min

10:

P-Space の O の情報を更新する．
else if distnew < distinsmin then11:

end if

11:

12:

end for

12:

P-Space の O の情報を更新する．

13: end for13:

end if

14: for each Grmax do

14:

end for15:

rmax カウンタと状態変化を更新する．

15: end if

16: end for

16: if 既存オブジェクトが削除される then

17: for each Gormax do

17:

18:
19:
20:

for each Gormax にあるオブジェクト do
距離 (distmax ) を計算する．
if distmax <= rmax thenrmax カウンタと状態変化を更新する．

21:
22:

end if23:

end for

24: end for

動後のオブジェクト位置にオブジェクトが追加されたとみなす．
半径 rmin の円に完全に含まれるグリッドを Grmin ，重なっているグリッドを Gormin とする．Grmax と Gormax も同様に定

18:
19:

for each OC のままだったオブジェクト O do
距離 (distdel ) を計算する．
then
if distdel <= distdel
max

P-Space の O の情報を更新する．

20:
21:

end if

22:

end for23: end if
24: for each 新しく OC になったオブジェクト do
25:

i 番目の近傍距離を計算する．

26:

for i = 1 to kmax − kmin + 1 do

27:
28:

P-Space に距離を加える．
end for

29: end for

義する．オブジェクトを 1 つ追加する場合はカウンタが 1 つ増加する．削除の場合はカウンタが 1 つ減少する．複数のオブジェクトが同じグリッドに追加や削除された場合は，そのオブジェクト数分だけカウンタを更新する．アルゴリズム 1 は以下の 4 つのフェーズに分かれる．

Phase 1: グリッド Grmin にあるオブジェクトの rmin と rmax
カウンタを更新する．

Phase 2: グリッド Gormin にあるオブジェクトと，追加または削除されたオブジェクト間の距離 distmin を計算する．もし，その距離が rmin 以下ならば，rmin と rmax カウンタを更新する．rmin より大きく，rmax 以下ならば，rmax カウンタのみ更新する．

Phase 3: Phase 2 までにチェックしたグリッドを除いてグ
リッド Grmax にあるオブジェクトの rmax カウンタを更新する．

Phase 4: グリッド Gormax にあるオブジェクトと，追加または削除されたオブジェクト間の距離 distmax を計算する．もし，その距離が rmax 以下ならば，rmax カウンタを更新する．

1 つのオブジェクトを追加したことにより，上記の処理でrmin カウンタが kmax になったオブジェクトは OC から IL に変化する．もし，rmax カウンタが kmin になった場合，オブジェクトは OL から OC に変化する．1 つのオブジェクトを削除したことにより，rmin カウンタが kmax -1 になったオブジェ
クトは IL から OC に変化する．もし，rmax カウンタが kmin -1になった場合，オブジェクトは OC から OL に変化する．複数のオブジェクトを同時に追加や削除，更新した場合は，OL から IL または IL から OL になる可能性もある．

6. 3 P-Space の更新アルゴリズム
P-Space を更新するアルゴリズムをアルゴリズム 2 に示す．
OC ではなくなったオブジェクトに関する情報は P-Space から削除し，OC になったオブジェクトに関する情報は P-Space に加える必要がある．さらに，OC のままだったオブジェクトのk 近傍が変化していないかを調べなければならない．アルゴリ
ズム 2 は 4 つのフェーズに分かれる．

Phase 1: OC から IL と，OC から OL に状態変化したオブ
ジェクトに関する情報を P-Space から削除する．

Phase 2: このフェーズは新しいオブジェクト Onew が追加されたときに実行され，OC のままだったオブジェクト O の情報を更新する．O と Onew 間の距離 distnew は P-Space で保持している O と O の i 番目 (i ∈ [kmin , kmax ]) の近傍オブジェクト間の距離に影響があるかもしれない．もし，distnew が O と Oの kmin 番目の近傍オブジェクト間の距離 distinsmin 以上かつ

O と O の kmax 番目の近傍オブジェクト間の距離 distinsmax
以下ならば，distnew は O の k 番目の近傍距離として P-Spaceに格納される．Onew が追加される前の O の i (k <= kmax )=i<番目の近傍距離は O の新しい (i+1) 番目の近傍距離になる．もし，distnew が distinsmin より小さいならば，O の新しい kmin

Denmark) Data Set を用いる．これは緯度，経度，標高を表す

番目の近傍オブジェクトを調べる必要がある．この場合，グ3 次元のデータであり，オブジェクト数は 434874 である．

リッド索引を用いて O を含むグリッドから徐々に検索範囲を拡

7. 4 実 験 結 果

大させることで，kmin 番目の近傍オブジェクトを探す．

7. 4. 1 実験

1Phase 3: このフェーズはオブジェクト Odel が削除されたと実験 1 の結果を図 14 ∼ 18 に示す．各パラメタは kmin =15，

きに実行され，OC のままだったオブジェクト O の情報を更新

rmin =50，rmax =150 とし，kmax を 20 から 30 まで 2 ずつ増する．もし，O と Odel 間の距離 distdel が O と O の kmax 番

やす．グリッドの対角線の長さは kmin /2 とする．データ集合を目の近傍オブジェクト間の距離 distdelmax 以下ならば，O の更新する前の各状態のオブジェクト数は kmax =20 で (IL, OC,(kmax +1) 番目の近傍オブジェクトを調べる必要がある．そのOL)=(97231, 966, 1803)，kmax =30 で (IL, OC, OL)=(96749,

オブジェクトは新しい kmax 番目の近傍オブジェクトになる．

1448, 1803) となっており，kmax が大きくなるほど OC の数が

その後，O と O の (kmax +1) 番目の近傍オブジェクト間の距増加し，IL の数が減少する．

離は O の新しい kmax 番目の近傍距離となり，O の他の近傍距離も更新される．

図 14 は IL，OC，OL に分類される各オブジェクトをそれぞれの手法で追加した場合，図 15 は IL，OC，OL に分類されてPhase 4: 新しく追加されたオブジェクト Onew が OC になっいる各オブジェクトをそれぞれの手法で削除した場合を示す．

た場合と，既存オブジェクトの状態が OL から OC または，IL

オブジェクトを追加した場合は，OL と OC のオブジェクトがから OC に変化したとき，それらのオブジェクトの i (kmin <=i<k)
番目の近傍距離を計算し，P-Spaceに距離を加える= max

状態変化するかを確認しなければならない．OL と OC のオブ必要がある．グリッド索引はこの計算にも活用される．

案手法とグリッド索引のみを用いる手法の差は小さい．一方で，7. 評 価 実 験

ジェクトは少ないため，IL のオブジェクトを追加した場合は提オブジェクトを削除した場合は IL と OC のオブジェクトが状態変化するかを確認しなければならない．IL のオブジェクトが

7. 1 実 験 概 要

多いため，IL に分類されているオブジェクトを削除した場合は本実験はオブジェクトの追加，削除，更新をした場合の P-

提案手法とグリッド索引のみを用いる手法の差は大きくなる．

Space の更新時間をそれぞれ計測する．実験 1 ∼ 3 は人工デー

OC のオブジェクトを追加した場合は IL のオブジェクトを追タを用いる．実験 1 では kmax ，実験 2 ではグリッドの対角線加した場合と比べて，多くの OC のオブジェクトに対して状態の長さをそれぞれ変化させて比較する．実験 3 ではバッチ処理

変化するかを確認しなければならない．そのため，グリッド索の有無による P-Space の更新時間を比較する．実験 4 では実引のみを用いる手法はより多くの時間がかかる．一方で，OCデータを用いて kmax を変化させて比較する．

のオブジェクトを削除した場合は IL に分類されているオブジェ

バッチ処理により，カウンタ更新と P-Space 更新の効率化

クトを削除した場合と比べて，状態変化を確認しなければならが可能になる．同じグリッドでオブジェクトが追加または削除

ない IL のオブジェクト数は減少するが，OC のオブジェクト数

された場合はカウンタ更新をオブジェクト数分だけ 1 度行えが増加する．グリッド索引のみを用いる手法で OC のオブジェ

ばよい．また，複数のオブジェクトの追加または削除によりクトの状態変化を調べるためには，OC のオブジェクトから半OC ではなくなる場合，毎回 P-Space で保持する値を更新せず，

径 rmax 内のオブジェクト数を確認する必要がある．IL のオブ

P-Space からそのオブジェクトに関する情報を削除すればよい．

ジェクトの状態変化の確認は半径 rmin 内を確認すればよいた

全ての実験で示す更新時間は 3 回試行した平均である．また，め，グリッド索引のみを用いる手法は多くの更新時間がかかる．

実験は Intel Core i7 3.70GHz の CPU と 64GB のメモリをもつ Windows 8 で行い，MATLAB で実装した．

7. 2 比 較 手 法

OL のオブジェクトを追加または削除した場合は，状態変化を確認しなければならないオブジェクト数が少ないため，提案手法とグリッド索引のみを用いる手法の差は小さい．

本実験では提案手法と他の 2 つの手法を比較する．1 つ目は

図 16 は IL に分類されているオブジェクト，図 17 は OC に

グリッド索引のみを用い，オブジェクト表では rmin と rmax カ

分類されているオブジェクト，図 18 は OL に分類されているウンタをもたない手法である．もし，オブジェクトの追加や削

オブジェクトをそれぞれの手法で更新した場合を示す．例えば，除，更新をした場合，再び既存オブジェクトから距離 rmin と

IL → OC は IL に分類されているオブジェクトが OC に分類さrmax 内にあるオブジェクトの数を調べなければならない．2 つれる位置に移動した場合を示している．IL → OC では IL のオ

目はグリッド索引とオブジェクト表の rmin と rmax カウンタ

ブジェクトを削除する処理と OC のオブジェクトを追加する処をもたない手法である．この手法では全てのオブジェクトのペ

理の組合せのため，更新時間はそれらの更新時間を合わせたもアで距離計算を行い，毎回 P-Space を再計算する必要がある．

のとほぼ等しい．図 16 と図 17 では，どの更新パターンにおい7. 3 実験データても提案手法の更新時間が最も短いことが確認できる．図 18

実験 1 ∼ 3 は平均 0，標準偏差 250 のガウス分布と範囲 [-では，状態変化を調べる対象となるオブジェクト数が少ないた

2500, 2500] の一様分布を組合せた 2 次元の人工データを用い

め，OL → OC の更新を行った場合を除いて提案手法とグリッる．オブジェクト数は 100000 である．実験 4 では UCI machine

ド索引のみ用いる手法での更新時間の差は小さい．P-Space を

learning repository から 3D Road Network (North Jutland,

再計算する手法では全オブジェクト間のペアで距離計算を行う

図 14 オブジェクトの追加

図 15

図 17 OC に分類されている

図 18 OL に分類されている

図 16 IL に分類されているオブジェクトの削除

オブジェクトの更新

オブジェクトの更新

図 19 オブジェクトの追加

オブジェクトの更新

ため，各更新で更新時間は同程度である．kmax の値が大きくブジェクト数が 2 つのときは 1 つのグリッドで 2 つのオブジェ

なるほど OC のオブジェクト数と P-Space のテーブル数が増

クト，オブジェクト数が 3 つのときは 2 つのグリッドでそれぞ加するため，kmax の増加とともに更新時間は増加する．

れオブジェクトを 2 つと 1 つ，オブジェクト数が 4 つのときは

なお，kmin を変化させ，オブジェクトの追加，削除，更新を

2 つのグリッドでそれぞれオブジェクトを 2 つずつ，オブジェ行った実験においても同じように提案手法の更新時間が短い傾

クト数が 5 つのときは 3 つのグリッドでそれぞれオブジェクト

向が見られた．kmin の値が大きくなるほど OC のオブジェク

を 2 つ，2 つ，1 つ追加または削除する．図 22 はオブジェク

ト数と P-Space のテーブル数が減少するため，P-Space を再計

トを追加した場合，図 23 はオブジェクトを削除した場合を示算する手法では kmin の増加とともに更新時間は減少する．

す．バッチ処理により，7. 1 節で述べたようにカウンタの更新

7. 4. 2 実

験2

実験 2 の提案手法に対する結果を図 19 ∼ 21 に示す．各パと P-Space 更新の効率化が可能になるため，バッチ処理を行わない場合よりも追加と削除ともに更新時間が短くなった．

ラメタは kmin =15，kmax =20，rmin =50，rmax =150 とし，グ

7. 4. 4 実験

リッドの対角線の長さは 2rmin ，rmin ，rmin /2，rmin /4 で比実験 4 の結果を図 24 と図 25 に示す．各パラメタは kmin =15，4較する．図 19 は IL，OC，OL に分類されるオブジェクトを追

rmin =0.2，rmax =0.6 とし，kmax を 20 から 28 まで 4 ずつ加した場合，図 20 は IL，OC，OL に分類されているオブジェ

増やす．グリッドの対角線の長さは rmin /2 とする．データ

クトを削除した場合，図 21 は各更新をした場合を示す．グリッ

集合を更新する前の各状態のオブジェクト数は kmax =20 でドの対角線の長さを rmin /4 と設定し，グリッドサイズを小さ(IL, OC, OL)=(428483, 6107, 284)，kmax =28 で (IL, OC,

くしすぎるとオブジェクトの状態変化を確認するために検索しOL)=(424535, 10055, 284) となっている．

なければならないグリッド数が増えるため，更新に時間がかか

図 24 は IL，OC，OL に分類される各オブジェクトをそれぞる．一方で，グリッドの対角線の長さを 2rmin と設定し，グれの手法で追加した場合，図 25 は IL，OC，OL に分類されてリッドサイズを大きくしすぎるとオブジェクト間の距離計算をいる各オブジェクトをそれぞれの手法で削除した場合を示す．

しなければならない回数が増加するため，更新に時間がかかる．

オブジェクトを追加する場合は OL と OC のオブジェクトが状用いるデータ集合に応じて適切なグリッドサイズにすることが態変化するかを確認する必要があるが，それらのオブジェクト重要と言える．

数が少ないため，IL と OC のオブジェクトを追加した場合は提7. 4. 3 実

験

3

案手法とグリッド索引のみ用いる手法の差は小さい．kmax =20

実験 3 の提案手法に対する結果を図 22 と図 23 に示す．各パ

では P-Space を再計算する手法でも更新にあまり大きな時間がラメタは kmin =15，kmax =20，rmin =50，rmax =150 とし，グかからない．しかし，kmax の値が大きくなるほど OC のオブ

リッドの対角線の長さは kmin /2 とする．追加または削除する

ジェクト数と P-Space のテーブル数が増加するため，再計算すオブジェクト数は 2 つ，3 つ，4 つ，5 つのそれぞれ行う．オ

る手法は時間がかるようになる．一方で，オブジェクトを削除

図 20 オブジェクトの削除

図 23 オブジェクトの削除

図 22 オブジェクトの追加
図 21

オブジェクトの更新

図 24

オブジェクトの追加

する場合は IL と OC のオブジェクトが状態変化するかを確認する必要がある．IL のオブジェクト数が多いため，グリッド索
引のみ用いる手法と再計算する手法では多くの時間がかかる．
なお，オブジェクトの更新はオブジェクトの追加と削除の組合せのため，追加や削除と同じように提案手法の更新時間が短い傾向が見られた．

8. ま と め
本研究では，動的なデータ集合での対話的外れ値分析を可能にする手法を提案した．提案手法ではグリッド索引とカウンタを用いて ONION の索引構造を更新し，オブジェクトが追加，削除，更新される環境での適用を可能にした．ONION の索引構造を更新するためには，追加や更新されたオブジェクトの状
態判別に加えて，既存オブジェクトの状態変化を調べる必要がある．グリッド索引を用いることで，状態が変化するオブジェ
クトを効率的に見つけることを可能にした．また，既存オブジェクトの状態変化を調べるためにカウンタを用いることで，距離計算を減らすことを可能にした．実験では，各環境でパラメタの値を変えて性能評価を行い，提案手法の有効性を確認した．性能比較のため，グリッド索引のみを用いる手法と，グリッド索引とカウンタをともにもたない手法を用いた．また，バッ
チ処理によるカウンタ更新と P-Space 更新の効率化に関して性
能比較を行った．
今後の課題としては，より多様な実データを用いた評価や，

P-Space で保持するテーブル数を kmax -kmin +1 個ではなく，多様に変化させた場合の評価等が挙げられる．
謝辞

本研究成果は，平成 28 年度共同研究 (SKY 株式会社)(CPE27116K)「機械学習の適用による SKYSEA Client

View のログ及び資産情報からの例外的状況の自動検出」により得られたものです．

図 25 オブジェクトの削除

文

献[1] D. Hawkins. Identification of Outliers. Chapman and Hall,
London, 1980.
[2] E. M. Knorr and R. T. Ng. Algorithms for mining distancebased outliers in large datasets. In Proc. VLDB, 1998.
[3] E. M. Knorr and R. T. Ng. Finding intensional knowledgeof distance-based outliers. VLDB, 1999.
[4] E. M. Knorr, R. T. Ng and V. Tucakov. Distance-based
outliers: algorithms and applications. VLDB, 2000.
[5] S. Ramaswamy, R. Rastogi, and K. Shim. Eﬃcient algorithms for mining outliers from large data sets. In Proc.
SIGMOD, 2000.
[6] M. M. Breunig, H.-P. Kriegel, R. Ng, and J. Sander. LOF:
Identifying density-based local outliers. In Proc. SIGMOD,
2000.
[7] R. T. Ng and J.Han. Eﬃcient and eﬀective clustering methods for spatial data mining. VLDB, 1994.
[8] M. Ester, H. P. Kriegel and X. Xu. A database interface forclustering in large spatial databases. KDD, 1995.
[9] T. Zhang, R. Ramakrishnan and M. Livny. Birch: an eﬃcient data clustering method for very large databases. SIGMOD, 1996.
[10] E. Eskin. Anomaly detection over noisy data using learned
probability distributions. ICML, 1994.
[11] V. Barret and T. Lewis. Outliers in statistical data, Wiley,
Chichester, 2001.
[12] H.-P. Kriegel, M. Schubert, and A. Zimek. Angle-based Outlier Detection in High-dimensional Data. In Proceedings
KDD’08, pages 444-452, 2008.
[13] R. P. N. PhamA. A near-linear time approximation algorithm for angle-based outlier detection in high-dimensional
data. Proc. ACM SIGKDD, pages 877-885, 2012.
[14] Lei Cao, MingruiWei, Di Yang, and Elke A. Rundensteiner.
Online Outlier Exploration Over Large Datasets. KDD’15,
2015.
[15] F.Angiulli and F.Fassetti. Detecting distance-based outliersin streams of data. CIKM 2007.
[16] K. Ishida and H. Kitagawa. Detecting current outliers:
Continuous outlier detection over time-series data streams.
Proc. DEXA, LNCS, 5181: 255-268, 2008.