(57)【要約】【課題】同一値が頻出する場合の密度ベースの異常値が無限大化するのを防止する。【解決手段】ＬＯＦ計算装置１は、ｎ次元（ｎは１以上）の標本値を有する標本の集合Ｃを入力し、各標本に対し標本に固有の標本値（図２の説明における標本値t）を付与することで集合Ｃを集合Ｄ、つまり、ｎ＋１次元の標本値を有する標本の集合Ｄに変換する標本集合変換部１１と、集合Ｄと正の整数kを入力し、LOFを計算するＬＯＦ計算部１２とを備える。【選択図】図３
2016099863.tif 000002
【特許請求の範囲】
【請求項１】
ｎ次元（ｎは１以上）の標本値を有する標本の集合Ｃを入力し、当該各標本に対し当該標本に固有の標本値を付与することで前記集合Ｃをｎ＋１次元の標本値を有する標本の集合Ｄに変換する標本集合変換部と、
前記集合Ｄと正の整数kを入力し、当該集合Ｄと当該整数kを用いて異常値を計算する異常値計算部とを備えることを特徴とする異常値検出装置。
【請求項２】
前記固有の標本値は、当該標本値を付与される標本が観測された時刻を示すタイムスタンプであることを特徴とする請求項１記載の異常値検出装置。
【請求項３】
前記異常値計算部は、前記集合Ｄに含まれる標本x’1 ,x’2間の距離d(x’1,x’2)を次の式により計算する、
d(x’1 ,x’2)={a(d(t1 , t2))2+(d(x1 ,x2))2}1/2
ただし、d(x1 ,x2)は、集合Ｃにおいて標本x’1,x’2に対応する標本x1,x2間の距離;
d(t1, t2)は、標本x1 ,x2に付与された固有の標本値t1 , t2間の距離である
ことを特徴とする請求項１または２記載の異常値検出装置。
【請求項４】
d(t1 , t2)は、t1 = t2の場合はd(t1 , t2)=0, t1 ≠ t2の場合はd(t1 , t2)=1;
とすることを特徴とする請求項３記載の異常値検出装置。
【請求項５】
異常値検出装置が、ｎ次元（ｎは１以上）の標本値を有する標本の集合Ｃを入力し、当該各標本に対し当該標本に固有の標本値を付与することで前記集合Ｃをｎ＋１次元の標本値を有する標本の集合Ｄに変換する工程と、
前記異常値検出装置が、前記集合Ｄと正の整数kを入力し、当該集合Ｄと当該整数kを用いて異常値を計算する工程とを備えることを特徴とする異常値検出装置の動作方法。
【請求項６】
前記固有の標本値は、当該標本値を付与される標本が観測された時刻を示すタイムスタンプであることを特徴とする請求項５記載の異常値検出装置の動作方法。
【請求項７】
前記異常値計算部は、前記集合Ｄに含まれる標本x’1 ,x’2間の距離d(x’1,x’2)を次の式により計算する、
d(x’1 ,x’2)={a(d(t1 , t2))2+(d(x1 ,x2))2}1/2
ただし、d(x1 ,x2)は、集合Ｃにおいて標本x’1,x’2に対応する標本x1,x2間の距離;
d(t1, t2)は、標本x1 ,x2に付与された固有の標本値t1 , t2間の距離である
ことを特徴とする請求項５または６記載の異常値検出装置の動作方法。
【請求項８】
d(t1 , t2)は、t1 = t2の場合はd(t1 , t2)=0, t1 ≠ t2の場合はd(t1 , t2)=1;
とすることを特徴とする請求項７記載の異常値検出装置の動作方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、同一値が頻出する場合の密度ベースの異常値が無限大化するのを防止する技術に関し、詳しくは、異常値検出装置およびその動作方法に関する。
【背景技術】
【０００２】
現在、産業活動における様々な場面で情報システムが用いられている。情報システムに異常が生じると、産業活動に大きな悪影響を与える。そこで、情報システムの異常の早期検知や異常に陥る前に異常の予兆を検知する技術が求められている。
【０００３】
そのための技術のひとつとして、標本の集合の中から、異常な標本を検出する種々の異常値検出方法が提案されている。異常値検出方法は、次のような用途に用いることができる。情報システムでなんらかの量や状態を観測して得た値をログとして出力し、ログからこれらの量や状態の値を抽出して分析し、通常どのような値をとるかを認識して、通常と異なる値を得た場合になんらかの異常が起きていると認識して適切に予防保全を行い、情報システムの安定運用に役立てることができる。
【０００４】
異常値検出のために、Breunigらは、標本の集合の中において標本ごとに異常の程度を表すLOF(local outlier factor)という尺度を定義する方法を提案した（非特許文献１を参照）。
【０００５】
LOFは、以下の良好な性質を有しており、異常値検出方法として有用である。
【０００６】
・ 値の分布が複雑な場合でも異常値を検出できる。正常値のクラスタが複数あり、クラスタごとにばらつきの程度や標本の密度に差がある場合でも、正常値のクラスタから外れた標本を検出できる。  
【０００７】
・ 値の分布に対する事前知識が不要である。正常値の平均値やばらつきを知らなくても異常値検出ができる。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】Markus M. Breunig,  Hans-Peter Kriegel, Raymond T. Ng and Jorg Sander, "LOF: Identifying Density-Based Local Outliers," in Proc. ACM SIGMOD, 2000, pp. 93-104.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかし、LOFは、同一の値が一定数以上存在すると無限大になるという問題がある。
【００１０】
LOFは、標本の密度から計算される。密度を計算するにあたり、自然数MinPtsを定め、密度を計算したい標本pに対し、その近傍の標本の密度を計算する。密度を計算する近傍の標本の数はMinPtsに応じて定める。このような計算方法を採用するので、同一の値を有する標本がMinPts+1個存在すると、密度が無限大と計算され、LOFが無限大となるため、標本が正常なのか異常なのかの判定ができなくなる。
【００１１】
MinPts+1個以上の標本が同一値になるということは、現実的に起こり得ることであり、単にMinPtsを大きくするだけでは、標本数が増えれば同一値を持つ標本も増えるため、効果がない。
【００１２】
図４は、LOFのイメージを示す図である。
【００１３】
LOFは、評価したい標本とその近傍の標本から計算される。標本値が、他の標本に近しい値とみなせる場合には、LOFはおよそ1となる。ある標本値が、他の標本の値に対し外れ値とみなせる場合、すなわち、異常とみなせる場合には、LOFは1より大きい値となる。閾値を定め、ある標本のLOFが閾値より大きい場合には、その標本が異常であると判定することができる。
【００１４】
図は、標本を2次元のベクトルとして、平面上に点で表している。標本p1は、図中の他の標本の値から離れているとみなせる。標本p1のLOFは、1より大きな値をとる。標本p2の値は、図中の他の標本の値に近しいとみなせる。標本p2のLOFは、1に近い値となる。
【００１５】
図５は、パラメタMinPtsと近傍のイメージを示す図である。
【００１６】
LOFを計算するにあたり、パラメタMinPtsを定める必要がある。LOFを求めるために用いる近傍の標本の数は、パラメタMinPtsにより決まる。
【００１７】
標本pの近傍とする範囲は、パラメタMinPtsにより決まる。図はMinPts=m1に対応する標本pの近傍N1と、MinPts=m2に対応する標本pの近傍N2を図示している。m1＜m2であれば、近傍N2が含む標本数は近傍N1が含む標本数より多くなる（N1⊂N2）。
【００１８】
図６は、LOFが無限大となる場合を示す図である。
【００１９】
値が同一の標本数が多いと、LOFが無限大となり、評価対象の標本の異常度が不明となってしまう。
【００２０】
図は、2次元の標本の場合で、標本oと同一の値である標本がoを含めてのMinPts+1個ある場合を示しており、図では、１点に集中する。この場合、標本oの近傍の密度が無限大と計算され、LOFが無限大となる。すなわち、異常値が無限大となってしまう。
【００２１】
本発明は、上記の事情に鑑みてなされたものであり、同一値が頻出する場合の密度ベースの異常値が無限大化するのを防止する技術を提供することを目的とする。
【課題を解決するための手段】
【００２２】
上記課題を解決するために、第１の本発明に係る異常値検出装置は、ｎ次元（ｎは１以上）の標本値を有する標本の集合Ｃを入力し、当該各標本に対し当該標本に固有の標本値を付与することで前記集合Ｃをｎ＋１次元の標本値を有する標本の集合Ｄに変換する標本集合変換部と、前記集合Ｄと正の整数kを入力し、当該集合Ｄと当該整数kを用いて異常値を計算する異常値計算部とを備えることを特徴とする。
【００２３】
第２の本発明に係る異常値検出装置の動作方法は、異常値検出装置が、ｎ次元（ｎは１以上）の標本値を有する標本の集合Ｃを入力し、当該各標本に対し当該標本に固有の標本値を付与することで前記集合Ｃをｎ＋１次元の標本値を有する標本の集合Ｄに変換する工程と、前記異常値検出装置が、前記集合Ｄと正の整数kを入力し、当該集合Ｄと当該整数kを用いて異常値を計算する工程とを備えることを特徴とする。
【発明の効果】
【００２４】
本発明によれば、同一値が頻出する場合の密度ベースの異常値が無限大化するのを防止することができる。
【図面の簡単な説明】
【００２５】
【図１】LOFの計算の元になる標本の集合を例示する図である。
【図２】LOFの無限大化を防止する技術のイメージを示す図である。
【図３】本発明の実施の形態に係るＬＯＦ計算装置の構成図である。
【図４】LOFのイメージを示す図である。
【図５】パラメタMinPtsと近傍のイメージを示す図である。
【図６】LOFが無限大となる場合を示す図である。
【発明を実施するための形態】
【００２６】
以下、本発明の実施の形態について図面を参照して説明する。
【００２７】
本実施の形態では、同一値が頻出する場合の密度ベースの異常値であるLOF(local outlier factor)と称される値（以下、LOFという）が無限大化するのを防止する。
【００２８】
図１は、LOFの計算の元になる標本の集合を例示する図である。
【００２９】
図１（ａ）に示すように、温度を観測して異常を検出する場合、例えば、８５度が異常であること検出するために、それに先立ちLOFを計算する。この場合、図１（ａ）に示すような、温度を標本値とする１次元の標本の集合（後述の集合Ｃ）を変換し、変換後の集合（後述の集合Ｄ）からLOFを計算する。
【００３０】
図１（ｂ）に示すように、情報システムのログを観測して異常を検出する場合、例えば、memory exhaustedというログが異常であることを検出するために、それに先立ちLOFを計算する。この場合、図１（ｂ）に示すような、ログを数値化したもの標本値とする１次元の標本の集合（後述の集合Ｃ）を変換し、変換後の集合（後述の集合Ｄ）からLOFを計算する。
【００３１】
なお、集合Ｃの標本の次元数は２次元以上でもよい。
【００３２】
図２は、LOFの無限大化を防止する技術のイメージを示す図である。
【００３３】
LOFの無限大化を防止するには、各標本の次元数を1増やし、増やした次元の標本値として、固有な標本値を付与する。固有な標本値として、好ましくは、次元数を増やす前の標本を採取した時刻を示すタイムスタンプを用いる。これにより、標本の密度が無限大となることがなくなり、LOFの無限大化を防止できる。
【００３４】
図２は、標本が2次元のベクトルの場合の一例であり、ここでは、評価対象の標本pがあり、pの近傍に、標本oがあり、標本oと同一の標本値を有する標本がoを含めてMinPts+1個ある場合を表している。
【００３５】
ここで、LOFの無限大化を防止するには、標本を3次元のベクトルに変換する。元の2次元のベクトルの要素つまり標本値が(x, y)の場合、これを3次元の標本値(x, y, t)とする。tは、標本に固有な標本値、例えば、採取した時刻を示すタイムスタンプとする。
【００３６】
このようにすると、標本oの近傍の密度が有限となり、標本pのLOFが有限となる。
【００３７】
もともとの2次元の標本pと標本oの距離dに応じてLOFも変化することから、標本pが、標本oあるいは他の近傍の標本に対して外れている程度（異常度）を評価することができる。
【００３８】
LOFは、新たに加えた標本値tの距離の評価方法にも影響される。影響の程度は、後述の方法によって変更することができる。
【００３９】
なお、図は、標本が2次元のベクトルの場合の一例であるが、３次元以上でも同様である。
【００４０】
図３は、本発明の異常値検出装置の一例であるＬＯＦ計算装置の構成図である。
【００４１】
ＬＯＦ計算装置１は、ｎ次元（ｎは１以上）の標本値を有する標本の集合Ｃを入力し、各標本に対し標本に固有の標本値（図２の説明における標本値t）を付与することで集合Ｃを集合Ｄ、つまり、ｎ＋１次元の標本値を有する標本の集合Ｄに変換する標本集合変換部１１と、集合Ｄと正の整数kを入力し、LOFを計算するLOF計算部１２（異常値計算部）とを備える。kは、パラメタMinPtsとして、ＬＯＦ計算部１２に入力される。
【００４２】
標本値tには、好ましくは、標本を採取した時刻を示すイムスタンプを用いる。タイムスタンプは、例えば、標本であるログの発生時刻を表しており、通常、同一値とはならないか、もしくは、同一値をとる確率は小さい。タイムスタンプとしては、時刻を1個の数値で表してもよいし、文字列で表してもよい。数値で表すには、ある時点からの経過時間で表すという方法がある。文字列で表すには、たとえば、「2014年8月7日18時40分00.0秒」のような文字列とする方法がある。
【００４３】
情報システムのログにはタイムスタンプが付与されていることが多いため、情報システムのログを分析する際に適した方法である。
【００４４】
ＬＯＦ計算部１２は、以下のようにLOFを計算する。
【００４５】
ＬＯＦ計算部１２は、集合Ｄ内の任意の標本sの k-距離である k-distance(s)を、次の条件（１）、（２）を満たす標本 o∈D と、sの間の距離 d(s, o) として定義する。
【００４６】
（１）少なくとも k個の標本o'∈D＼{ s }に対して d(s, o') ≦ d(s, o)が成立する。
【００４７】
（２）高々k-1個の標本o' ∈D＼{ s }に対して d(s, o') ＜ d(s, o)が成立する。
【００４８】
ただし、o, o’は、集合Ｄに含まれる。
【００４９】
ＬＯＦ計算部１２は、標本値pの k-近傍であるNk(s) を次の式（３）により定義する。
【００５０】
Nk(s) = { q∈D＼{ s } | d(s, q) < k-distance(s) }                  （３）
また、ＬＯＦ計算部１２は、sのoに関するreachability distanceである reach-dist k(s, o) を次の式（４）により定義する。
【００５１】
reach-dist k(s, o)  = max { k-distance(s), d(s, o) }              （４）
ただし、max{}は、{}内に示す値の最大値。
【００５２】
また、ＬＯＦ計算部１２は、sのlocal reachability densityである lrd k(s) を次の式（５）のように定義する。
【００５３】
lrd k(s)  = | Nk(s) | ／Σo∈Nk(s) reach-dist k(s, o)            （５）
ただし、||は、||内に示す集合内の標本の個数。
【００５４】
また、ＬＯＦ計算部１２は、s の中の特定の標本pのLOFであるLOF k(p)を次の式（６）により計算する。
【００５５】
LOF k(p) = 1／| Nk(p) | Σs∈Nk(p) ( lrd k(s) ／ lrd k(p) )        （６）
ここで、LOF k(p)（以下、LOF）の計算方法の問題点、すなわち、本実施の形態において解決すべき問題点を、上記定義を用いて説明する。
【００５６】
標本pの近傍に標本が密集している場合には、reach-dist k (p, o)  の値は、o の k-距離であるk-distance(o) となる。標本pと同一の標本値を有する標本がpの他にk個以上ある場合、lrd k(p) が無限大となる。
【００５７】
式（６）より、lrd k(p)が無限大の場合、 LOF k(p)も無限大になり得る。LOF k(p)が無限大の場合、標本pが異常とみなし得るのか、正常とみなし得るのか評価できなくなってしまう。
【００５８】
標本値が複数の標本で同一となることは現実にはあり得る。
【００５９】
なぜなら、情報システムが取得する測定値は離散化されているからである。測定値のばらつきの大きさに対し、離散化の分解能が同程度である場合には、同一値が取得される確率が高い。
【００６０】
例えば、情報システムで、特定の処理に要した時間 TAT (turn around time)を測定することを考える。このTATが、たとえば、概ね 1 ミリ秒 程度であり、情報システムの時計機能の精度が1 ミリ秒程度であったとする。このような場合は、TATが 1 ミリ秒と測定される確率が高く、同一値が数多く測定され得る。
【００６１】
同一値となる標本数より大きな数をkとすれば lrd k(p) が無限大となることを避けられるが、同一値となる標本数がどの程度かを知ることは容易ではない。例えばそれを調べてkの値を決めたとしても、標本の収集を長時間行って標本数が増えれば、それだけ同一値の数が増え、同一値が数多く測定され得る。
【００６２】
近年、大量のデータを収集して分析するビッグデータ解析と呼ばれる技術の研究や活用が行われているが、その応用では、測定を終えることなくデータ収集と解析を続ける使い方も多く、標本数が増えても安定的に使える技術が求められる。
【００６３】
したがって、本実施の形態では、標本集合変換部１１が、各標本に対し、標本に固有の標本値を付与することで１次元多い標本値を有する標本とする。
【００６４】
例えば、ログなどから取得される標本はn次元の要素（標本値）を有するベクトルであり、これをx で表し、ベクトルx の要素（標本値）をxi で表すと、以下の式（７）が得られる。
【００６５】
x = (x1, x2, ... xn)                                          （７）
x1, x2, ... xnに新たな要素 t を付与することで、新たにn+1次元のベクトル x' = (x1, x2, ... xn, t ) が得られる。ただし、tは、標本に固有な要素（標本値）とする。
【００６６】
そうすると、集合Ｃの2つの標本x1, x2 が同一の標本値を有していても、新たな要素tの付与後の集合Ｄの標本x'1', x'2は同一の標本値を有しない。
【００６７】
よって、n+1次元の標本値を有する標本 x' の集合（集合Ｄ）でLOFを計算すれば、LOFの無限大化を防止できる。
【００６８】
新たな要素tによる標本間の距離や標本の密度の変化を抑えるためには、新たな要素tの距離の重み係数（後述のa）を小さくすればよい。
【００６９】
例えば、ＬＯＦ計算部１２は、集合Ｄの２標本x’1 ,x’2間の距離d(x’1 ,x 2)を次の式（８）により計算する。これは、上記のd(s, o)などの計算に使用される。
【００７０】
d(x’1 ,x’2)={a(d(t1 ,t2))2+(d(x1 ,x2))2}1/2                        （８）
ただし、d(t1,t2)は、集合Ｃにおいて標本x’1,x’2に対応する標本x1,x2間の距離である。d(t1,t2)は、標本x1 ,x2に付与された標本値t1 , t2間の距離である。aは、予め定められた重み係数である。
【００７１】
a に対し、１より小さな値を与えることによって、要素tの影響を小さくすることができる。
【００７２】
また、１例として、t1= t2の場合はd(t1 , t2)= 0、t1≠t2の場合はd(t1 , t2)=1と定義する。
【００７３】
このようにすると、d(t1, t2)の大小が影響しなくなる。例えば、tとしてタイムスタンプを用いている場合に、ログの発生時刻が離れているほどd(t1 , t2)が大きくなるという事態を防止できる。
【００７４】
また、タイムスタンプを文字列として表現している場合には、d(t1 , t2)を計算するにあたり文字列が一致するか否かを判定すればよいため、この計算方法が好適である。
【符号の説明】
【００７５】
１  ＬＤＦ計算装置（異常値検出装置）
１１  標本集合変換部
１２  ＬＤＦ計算部（異常値計算部）
【図１】
2016099863.tif 000003
【図２】
2016099863.tif 000004
【図３】
2016099863.tif 000005
【図４】
2016099863.tif 000006
【図５】
2016099863.tif 000007
【図６】
2016099863.tif 000008