外れ値検出装置、外れ値検出方法、プログラム及び車両故障診断システム
【課題】非線形のデータセットに対して、パラメータチューニング作業を行うことなく、実用的な時間内に外れ値の検出を支援又は実行する外れ値検出装置等を提供する。
【解決手段】外れ値検出装置１が、データセットに含まれる各データを次元ごとにビット列に変換し、ビット列に基づいて、データセットの観測領域を構築する。次に、外れ値検出装置１が、データセットに含まれるデータの中から着目データを１つずつ決定し、観測領域から着目データに相当する領域を除去したときの着目データの周辺のデータ密度に基づいて、着目データの外れ度合を算出する。
【解決手段】外れ値検出装置１が、データセットに含まれる各データを次元ごとにビット列に変換し、ビット列に基づいて、データセットの観測領域を構築する。次に、外れ値検出装置１が、データセットに含まれるデータの中から着目データを１つずつ決定し、観測領域から着目データに相当する領域を除去したときの着目データの周辺のデータ密度に基づいて、着目データの外れ度合を算出する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データの次元数が１又は複数、かつデータ数が複数のデータセットから外れ値の検出を支援又は実行する外れ値検出装置等に関するものである。
【背景技術】
【０００２】
外れ値検出問題は、与えられたデータセットの中から、データ密度が低い領域に属するデータを外れ値として見つける問題と考えられる。外れ値検出問題を解く技術の応用例としては、データセットに含まれるノイズデータの除去処理（データスクリーニングの前処理）、クレジット取引のデータセットの中から通常行われていない取引を行っている顧客を検出する処理、生産ラインにおける生産物のデータセットの中から不良品を検出する処理などが考えられる。
【０００３】
外れ値検出問題を解く技術としては、例えば、以下の３つが知られている。
・マハラノビス距離
・One−Class Support Vector Machine（以下、「ＯＣ−ＳＶＭ」と省略。）
・Local
Outlier Factor（以下、「ＬＯＦ」と省略。）
【０００４】
非特許文献１には、マハラノビス距離について記載されている。非特許文献１では、与えられたデータセットの全体の重心（平均）と共分散行列を求め、各データに対して共分散行列を用いて正規化した重心との距離を求め、距離が大きいデータを外れ値とみなす。
マハラノビス距離では、データセットが多変量正規分布に従うことを仮定しており、データセットが多変量正規分布では記述できない場合、すなわちデータセットが非線形の場合、適切な外れ値を検出することができない。
【０００５】
非特許文献２には、ＯＣ−ＳＶＭについて記載されている。非特許文献２では、入力されるデータセットを非線形写像によって高次の特徴空間Ｆに写像し、写像されたデータ群と原点を分離する超平面のうち、原点からの距離が最大のものを選択する。ＯＣ−ＳＶＭを外れ値検出問題に適用する場合には、一定割合のデータが超平面よりも原点側に分類されることを許すように超平面を決定し、原点側に分類されたデータを外れ値とみなす。
ＯＣ−ＳＶＭでは、解が求まり易い凸最適化問題を解くことによって、超平面を求めることができる。また、非線形写像を用いるので、非線形なデータセットに適用できる。
【０００６】
非特許文献３には、ＬＯＦについて記載されている。非特許文献３では、まず、各データｘに対し、データｘ自身に近いｋ個のデータとの距離の平均値を、データｘのｋ近傍距離として求める。次に、｛データｘのｋ近傍距離÷周辺のデータｋ個のｋ近傍距離の平均値｝を、データｘのＬＯＦとして求める。これらの処理から分かるように、データｘ自身のｋ近傍距離よりも、周辺のデータｋ個のｋ近傍距離の平均値が小さい程、ＬＯＦは大きな値を取る。そして、ＬＯＦが大きいデータを、外れ値とみなす。
ＬＯＦも、非線形なデータセットに適用できる。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Mahalanobis, P.C., On the generalized distance in statistics,Proceedings of the National Institute of Science, 49-55, 1936
【非特許文献２】Scholkopf, B. et. al., Estimating the Support of a High-DimensionalDistribution, Neural computation, 7, 1443-1471, 2001
【非特許文献３】Breunig, M.M. et. al., LOF: Identifying Density-Based LocalOutliers, SIGMOD Conference, 93-104, 2000
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、前述の３つの従来技術は、以下の問題がある。
前述の通り、マラハノビス距離は、データセットが非線形の場合、適切な外れ値を検出することができないという問題がある。
【０００９】
ＯＣ−ＳＶＭは、適切な非線形写像を選ぶことが難しいという未解決の問題がある。これは、非線形写像を決めるパラメータを人間が試行錯誤によって決定するパラメータチューニング作業が必要という課題に帰結する。
また、ＯＣ−ＳＶＭは、データ数が多い場合、最適化問題を解く為に時間がかかる。データ数をＮとすると、何ら工夫をしなければ、ＯＣ−ＳＶＭの計算量のオーダーはО（Ｎの３乗）である。
【００１０】
ＬＯＦは、適切なｋを選ぶことが難しいという未解決の問題がある。これも、ＯＣ−ＳＶＭと同様、パラメータチューニング作業が必要という課題に帰結する。
また、ＬＯＦは、計算負荷も比較的高い。データ数をＮとすると、何ら工夫をしなければ、ＬＯＦの計算量のオーダーはО（Ｎの２乗）である。
【００１１】
本発明は、前述した問題点に鑑みてなされたもので、その目的とすることは、非線形のデータセットに対して、パラメータチューニング作業を行うことなく、実用的な時間内に外れ値の検出を支援又は実行する外れ値検出装置等を提供することである。
【課題を解決するための手段】
【００１２】
前述した目的を達成するために第１の発明は、データの次元数が１又は複数、かつデータ数が複数のデータセットから外れ値の検出を支援又は実行する外れ値検出装置であって、前記データセットに含まれる各データを次元ごとにビット列に変換し、前記ビット列に基づいて、前記データセットの観測領域を構築する構築手段と、前記データセットに含まれるデータの中から着目データを１つずつ決定し、前記観測領域から前記着目データに相当する領域を除去したときの前記着目データの周辺のデータ密度に基づいて、前記着目データの外れ度合を算出する算出手段と、を具備する外れ値検出装置である。
第１の発明によって、非線形のデータセットに対して、パラメータチューニング作業を行うことなく、実用的な時間内に外れ値の検出を支援又は実行することができる。
【００１３】
第１の発明における前記構築手段は、前記観測領域を二分決定グラフとして構築し、前記算出手段は、各ノードにおける局所密度から単一データの密度換算値を引いた値を単一データ除外局所密度とし、更に、前記単一データ除外局所密度に基づいて、前記着目データの外れ度合を算出することが望ましい。
これによって、データ数をＮ、ノード数をＤとすると、少なくとも、第１の発明の計算量のオーダーは、О（Ｎ×Ｄ）であり、ＯＣ−ＳＶＭやＬＯＦよりも優位である。
【００１４】
また、第１の発明における前記構築手段は、数値属性の次元に係る前記ビット列群を最上位ビットから最下位ビットの順に並び変えて、前記二分決定グラフを階層的に構築し、前記算出手段は、前記二分決定グラフでの前記着目データを表すパスを探索し、階層が変化するノードに係る前記単一データ除外局所密度に基づいて、前記着目データの外れ度合を算出することが望ましい。
これによって、データセットの特性について事前に何も情報を持っていない場合にも、適切な外れ度合を算出することができる。
【００１５】
また、前記算出手段は、例えば、階層が変化するノードに係る前記単一データ除外局所密度の一部若しくは全部の最大値、中央値又は平均値を、前記着目データの外れ度合とする。
また、第１の発明は、例えば、前記外れ度合と閾値を比較することによって、外れ値を検出する検出手段、を更に具備しても良い。
【００１６】
第２の発明は、データの次元数が１又は複数、かつデータ数が複数のデータセットから外れ値の検出を支援又は実行する外れ値検出方法であって、前記データセットに含まれる各データを次元ごとにビット列に変換し、前記ビット列に基づいて、前記データセットの観測領域を構築する構築ステップと、前記データセットに含まれるデータの中から着目データを決定し、前記観測領域において、前記着目データ自身が占める領域を除く前記着目データ周辺のデータ密度である着目データ除去局所密度を算出する算出ステップと、を含む外れ値検出方法である。
【００１７】
第３の発明は、コンピュータを、データの次元数が１又は複数、かつデータ数が複数のデータセットから外れ値の検出を支援又は実行し、前記データセットに含まれる各データを次元ごとにビット列に変換し、前記ビット列に基づいて、前記データセットの観測領域を構築する構築手段と、前記データセットに含まれるデータの中から着目データを決定し、前記観測領域において、前記着目データ自身が占める領域を除く前記着目データ周辺のデータ密度である着目データ除去局所密度を算出する算出手段と、を具備する外れ値検出装置として機能させる為のプログラムである。
【００１８】
第４の発明は、データの次元数が１又は複数、かつデータ数が複数のデータセットから外れ値の検出を支援又は実行する外れ値検出装置と、車両データを収集するデータ収集装置と、を含む車両故障診断システムであって、前記外れ値検出装置は、前記データ収集装置によって収集される前記車両データを前記データセットとし、前記データセットに含まれる各データを次元ごとにビット列に変換し、前記ビット列に基づいて、前記データセットの観測領域を構築する構築手段と、前記データセットに含まれるデータの中から着目データを１つずつ決定し、前記観測領域から前記着目データに相当する領域を除去したときの前記着目データの周辺のデータ密度に基づいて、前記着目データの外れ度合を算出する算出手段と、前記外れ度合と閾値を比較することによって、外れ値を検出する検出手段と、を具備する車両故障診断システムである。
【発明の効果】
【００１９】
本発明により、非線形のデータセットに対して、パラメータチューニング作業を行うことなく、実用的な時間内に外れ値の検出を支援又は実行する外れ値検出装置等を提供することができる。
【図面の簡単な説明】
【００２０】
【図１】外れ値検出装置のハードウエア構成図
【図２】外れ値検出装置の処理の詳細を示すフローチャート
【図３】データセットの変換処理を説明する図
【図４】カルノー図を示す図
【図５】二分決定グラフを示す図
【図６】最小項の数の算出処理を説明する図
【図７】最小項の数の算出結果を示す図
【図８】局所密度の算出処理を説明する図
【図９】局所密度の算出結果を示す図
【図１０】ＬＯＯ密度の算出結果を示す図
【図１１】二分決定グラフにおける着目データを表すパスを示す図
【図１２】カルノー図における着目データを表す領域を示す図
【図１３】抽出されるＬＯＯ密度を説明する図
【図１４】実施例１及び比較例に用いたデータセットを示す図
【図１５】実施例１における外れ値の検出結果を示す図
【図１６】比較例１における外れ値の検出結果を示す図
【図１７】比較例２における外れ値の検出結果を示す図
【図１８】比較例３における外れ値の検出結果を示す図
【図１９】比較例４における外れ値の検出結果を示す図
【図２０】実施例２における車両故障診断システムの構成図
【図２１】実施例２における車両故障診断システムの処理を示すフローチャート
【図２２】実施例２における外れ値の検出結果を示す図
【発明を実施するための形態】
【００２１】
以下図面に基づいて、本発明の実施形態を詳細に説明する。
本発明の実施形態では、与えられたデータセットの中から、データ密度が低い領域に属するデータを外れ値として見つける外れ値検出問題を解く。
最初に、クレジット取引を例にして、「データセット」について説明する。例えば、クレジット取引のデータセットとして、顧客の性別、顧客の年齢、取引金額の３種類の情報の組み合わせが単一のデータとして与えられる場合を考える。そして、ｘ１＝（男性、２５歳、１万円）、ｘ２＝（女性、３０歳、２万円）の２個のデータが、データセットとして与えられる場合を考える。
【００２２】
上記の例では、データの次元数が「３」かつデータ数が「２」のデータセットが与えられていることになる。データの次元は、変量とも呼ばれる（例えば、多変量解析とは、多次元のデータを解析することを意味する。）。また、データ数は、サンプル数とも呼ばれる。
データの各次元は、カテゴリ属性又は数値属性のいずれかである。上記の例では、顧客の性別がカテゴリ属性、顧客の年齢や取引金額が数値属性である。
【００２３】
また、データセットの他の例として、自動車の車載装置によって取得されるデータセットなどが考えられる。この場合、ある時刻に観測された車速、回転数、ＡＣＣ（Auto Cruse Control）のＯＮ／ＯＦＦなどが、各次元（各変量）となる。車速、回転数は数値属性、ＡＣＣのＯＮ／ＯＦＦはカテゴリ属性である。そして、複数の時刻に観測される複数のデータが、データセットとして与えられる。
【００２４】
以下では、データの次元数が１又は複数、かつデータ数が複数のデータセットから外れ値の検出を支援又は実行する外れ値検出装置について説明する。本発明の実施の形態における外れ値検出装置は、非線形のデータセットに対して、パラメータチューニング作業を行うことなく、実用的な時間内に外れ値の検出を支援又は実行することができる。
【００２５】
図１は、外れ値検出装置のハードウエア構成図である。尚、図１のハードウエア構成は一例であり、用途、目的に応じて様々な構成を採ることが可能である。
【００２６】
外れ値検出装置１は、制御部１１、記憶部１２、メディア入出力部１３、通信制御部１４、入力部１５、表示部１６、周辺機器Ｉ／Ｆ部１７等が、バス１８を介して接続される。
【００２７】
制御部１１は、ＣＰＵ（Central Processing Unit）、ＲＯＭ（Read Only
Memory）、ＲＡＭ（Random Access Memory）等によって構成される。
【００２８】
ＣＰＵは、記憶部１２、ＲＯＭ、記録媒体等に格納されるプログラムをＲＡＭ上のワークメモリ領域に呼び出して実行し、バス１８を介して接続された各装置を駆動制御し、外れ値検出装置１が行う後述する処理を実現する。
ＲＯＭは、不揮発性メモリであり、外れ値検出装置１のブートプログラムやＢＩＯＳ等のプログラム、データ等を恒久的に保持している。
ＲＡＭは、揮発性メモリであり、記憶部１２、ＲＯＭ、記録媒体等からロードしたプログラム、データ等を一時的に保持するとともに、制御部１１が各種処理を行う為に使用するワークエリアを備える。
【００２９】
記憶部１２は、ＨＤＤ（ハードディスクドライブ）であり、制御部１１が実行するプログラム、プログラム実行に必要なデータ、ＯＳ（オペレーティングシステム）等が格納される。プログラムに関しては、ＯＳ（オペレーティングシステム）に相当する制御プログラムや、後述する処理を外れ値検出装置１に実行させるためのアプリケーションプログラムが格納されている。
これらの各プログラムコードは、制御部１１により必要に応じて読み出されてＲＡＭに移され、ＣＰＵに読み出されて各種の手段として実行される。
【００３０】
メディア入出力部１３（ドライブ装置）は、データの入出力を行い、例えば、ＣＤドライブ（−ＲＯＭ、−Ｒ、−ＲＷ等）、ＤＶＤドライブ（−ＲＯＭ、−Ｒ、−ＲＷ等）等のメディア入出力装置を有する。
通信制御部１４は、通信制御装置、通信ポート等を有し、外れ値検出装置１とネットワーク間の通信を媒介する通信インタフェースであり、ネットワークを介して、他のコンピュータ間との通信制御を行う。ネットワークは、有線、無線を問わない。
【００３１】
入力部１５は、データの入力を行い、例えば、キーボード、マウス等のポインティングデバイス、テンキー等の入力装置を有する。
入力部１５を介して、外れ値検出装置１に対して、操作指示、動作指示、データ入力等を行うことができる。
表示部１６は、液晶パネル等のディスプレイ装置、ディスプレイ装置と連携して外れ値検出装置１のビデオ機能を実現するための論理回路等（ビデオアダプタ等）を有する。
【００３２】
周辺機器Ｉ／Ｆ（インタフェース）部１７は、外れ値検出装置１に周辺機器を接続させるためのポートであり、周辺機器Ｉ／Ｆ部１７を介して外れ値検出装置１は周辺機器とのデータの送受信を行う。周辺機器Ｉ／Ｆ部１７は、ＵＳＢやＩＥＥＥ１３９４やＲＳ−２３２Ｃ等で構成されており、通常複数の周辺機器Ｉ／Ｆを有する。周辺機器との接続形態は有線、無線を問わない。
バス１８は、各装置間の制御信号、データ信号等の授受を媒介する経路である。
【００３３】
以上、外れ値検出装置１のハードウエア構成について説明したが、外れ値検出装置１として実装される装置は、この例に限定されない。例えば、外れ値検出装置１は、自動車などの車載装置、家電などの制御装置、生産ラインの不良品を検出する検品装置などに、後述する処理を実現する為のプログラムをインストールすることによって、自動車、家電、生産ラインなどの一部として実装されることもある。また、例えば、外れ値検出装置１は、複数のコンピュータから構成されるサーバ装置として実装されることもある。
以下では、外れ値検出装置１が単一のコンピュータによって実装されるものとして説明する。
【００３４】
図２は、外れ値検出装置の処理の詳細を示すフローチャートである。以下では、必要に応じて図３〜図１３を参照し、データセットの一例に対する処理の詳細を説明する。
【００３５】
図２に示すように、外れ値検出装置１の制御部１１は、入力手段（メディア入出力部１３、通信制御部１４、入力部１５、周辺機器Ｉ／Ｆ部１７等）を介して、データセットを入力する（Ｓ１）。また、制御部１１は、記憶部１２にファイルとして記憶されているデータセットを入力しても良い。
【００３６】
図３は、データセットの変換処理を説明する図である。図３には、データセット２１が図示されている。データセット２１は、データの次元数が「２」、データ数が「１９」である。各次元は数値属性であり、取り得る値は、０〜７の整数値である。
【００３７】
制御部１１は、図３に示されるデータセット２１のように、正規化されたデータセットを入力する場合に限らず、生のデータセットを入力して正規化処理を行っても良い。例えば、制御部１１は、生のデータセットに対して様々な加工処理を施して所定の範囲の整数値とする。
生のデータセットに含まれる一部の次元（変量）が数値属性の場合、制御部１１は、細かく区切って離散化し、デジタル化する。制御部１１は、例えば、実数値を小数点第１位において四捨五入して整数値とし、コンピュータがｉｎｔ型として扱うことが可能な値に変換する。取り得る範囲が極端に狭い、または広い場合、制御部１１は、適当な係数をかけて想定する範囲に満遍なく収まるようにする。また、尺度が異なるデータが混ざっている場合、制御部１１は、平均０、分散１に標準化する。また、分布が極端に偏っている場合、制御部１１は、対数変換なども行う。
また、数値属性の次元（変量）の場合であっても、取り得る値が少ない場合、例えば０〜３の整数値しか取らない場合、制御部１１は、カテゴリ属性の次元（変量）として取り扱っても良い。また、カテゴリ属性の次元（変量）の場合であっても、取り得る値に何らかの距離の概念が導入できる場合、制御部１１は、数値属性の次元（変量）として取り扱っても良い。
【００３８】
図２の説明に戻る。次に、制御部１１は、各データを次元（変量）ごとにビット列に変換する（Ｓ２）。図３には、データｘ１に対するビット列２２ａ、データｘ２に対するビット列２２ｂが図示されている。例えば、データｘ１＝６に対するビット列２２ａは、（ｄ１，ｄ２，ｄ３）＝（１，１，０）である。また、例えば、データｘ２＝２に対するビット列２２ｂは、（ｅ１，ｅ２，ｅ３）＝（０，１，０）である。
【００３９】
次に、制御部１１は、数値属性のビット列群を最上位ビットから最下位ビットの順に並び替える（Ｓ３）。図３には、並び替え後ビット列２３が図示されている。例えば、（ｄ１，ｄ２，ｄ３）＝（１，１，０）のビット列２２ａ、及び（ｅ１，ｅ２，ｅ３）＝（０，１，０）のビット列２２ｂに対して、並び替え後ビット列２３は、（ｄ１，ｅ１，ｄ２，ｅ２，ｄ３，ｅ３）＝（１，０，１，１，０，０）である。
以下では、ｄ１とｅ１のように最も左端のビットを「最上位ビット」（ＭＳＢ：Most Significant Bit）、ｄ３とｅ３のように最も右端のビットを「最下位ビット」（ＬＳＢ：Least Significant Bit）とする。
【００４０】
尚、Ｓ３における並び替えの処理は、必ずしも必須ではない。Ｓ３における並び替えの処理は、全ての次元（変量）を同等に扱うことになるので、データセットの特性について事前に何らかの情報を持っている場合、並び替えを行わない方が良いこともある。例えば、ｘ１の次元（変量）は、データの特徴を良く表しており、ｘ２の次元（変量）は、ほとんど変化がなく、データの特徴をあまり表していないことが分かっている場合には、Ｓ３における並び替えの処理を行わず、両者を同等に扱わない方が良い。
Ｓ３における並び替えの処理は、データセットの特性について事前に何も情報を持っていない場合に有効である。
【００４１】
また、カテゴリ属性のビット列群は、数値属性のビット列群と区別し、カテゴリ属性のビット列が上位、数値属性のビット列が下位となるように並べることが望ましい。例えば、図３に示す数値属性のｘ１、ｘ２の他に、カテゴリ属性のｘ３を含むデータを考え、カテゴリ属性のｘ３を変換したビット列を（ｆ１，ｆ２，ｆ３）とする。この場合、制御部１１は、（ｆ１，ｆ２，ｆ３，ｄ１，ｅ１，ｄ２，ｅ２，ｄ３，ｅ３）の順に並び替えることが望ましい。
カテゴリ属性と数値属性を分けた理由は、一般にカテゴリ属性の取り得る値に対して距離の概念を導入することができず、数値属性と一緒に取り扱うことが困難だからである。
データセットの特性について事前に何も情報を持っていない場合、カテゴリ属性同士や数値属性同士は、どちらが上位になっても構わない。
【００４２】
図２の説明に戻る。次に、制御部１１は、観測領域Ｆとして二分決定グラフを構築する（Ｓ４）。制御部１１は、観測領域Ｆとして、二分決定グラフ（ＢＤＤ：Binary Decision Diagram）ではなく、カルノー図などを構築しても良い。二分決定グラフ及びカルノー図のいずれも、論理関数を表現するために使われるデータ構造の１つである。つまり、観測領域Ｆは、論理関数を表現できれば良い。
【００４３】
尚、後述するように、観測領域Ｆとして二分決定グラフを構築する場合、外れ値検出装置１は、データ数が増大しても、実用的な時間内に外れ値の検出を支援又は実行することができる。以下では、混乱を避ける為に、外れ値検出装置１が、観測領域Ｆとして二分決定グラフを構築する場合について説明する。また、外れ値検出装置１の処理を分かり易く説明する為に、カルノー図も例示する。
【００４４】
図４は、カルノー図を示す図である。
図４に示すカルノー図３０ａは、図３に示すビット列２２ａの（ｄ１，ｄ２，ｄ３）を縦、図３に示すビット列２２ｂの（ｅ１，ｅ２，ｅ３）を横に配置している。黒の正方形の１個分が、１個のデータに対応する。従って、図４に示すカルノー図３０ａには、１９個の黒の正方形が図示されている。
【００４５】
図５は、二分決定グラフを示す図である。図５に示す二分決定グラフ３１は、図３の並び替え後ビット列２３に基づいて構築されたものである。
二分決定グラフは、コンピュータにおいてポインタの配列で表現されるので、必要な記憶容量を減らすことができる。また、既約な順序付き二分決定グラフの場合、論理関数同士の演算がグラフのサイズにほぼ比例する程度の計算時間によって実行できる。グラフのサイズは、ノード数である。
図５に示す例では、楕円形状の３２などがノードである。図３に示す並び替え後ビット列２３の各ビットは、ブーリアン変数（「真」と「偽」のいずれかを取る変数）とみなすことができる。例えば、１番目のビットｄ１は、ノード３２ａに対応している。
順序付き二分決定グラフとは、（１）ノード同士に全順序関係が定義されている、（２）最上位ノードから定数ノードに至る全てのパスについて変数の出現順序が、全順序関係に矛盾しない、二分決定グラフである。ここで、図５に示す例では、３３が最上位ノード（ルートノード）、３４が定数ノードである。図５に示す例では、定数ノードは、「１」（「真」を意味する。）である。尚、最上位ノード及び定数ノードは特別なノードである為、通常のノードと符号を区別する。
既約な二分決定グラフとは、（１）冗長なノードを全て削除、（２）等価なノードを全て共有、という２つの簡約化規則がこれ以上適用できなくなるまで適用されている二分決定グラフである。
図５に示す二分決定グラフは、既約な順序付き二分決定グラフである。
【００４６】
図５に示す二分決定グラフは、実線によって示されるＴｈｅｎ枝、間隔が広い点線によって示されるＥｌｓｅ枝、「＊」（アスタリスク）を付した間隔が狭い点線によって示される否定Ｅｌｓｅ枝の３つを用いている。否定Ｅｌｓｅ枝を用いると、否定演算が短い時間によって実行できる。例えば、枝３５ａは、Ｅｌｓｅ枝である。
【００４７】
図２の説明に戻る。次に、制御部１１は、二分決定グラフの各ノードにおける最小項の数を算出する（Ｓ５）。最小項の数の算出処理は、図６、図７を参照して説明する。
【００４８】
図６は、最小項の数の算出処理を説明する図である。図７は、最小項の数の算出結果を示す図である。
最小項（Ｍｉｎｔｅｒｍ）とは、ブーリアン変数の集合が与えられたとき、全てのブーリアン変数のリテラルを含む積項である。例えば、ブーリアン変数の集合が（ａ、ｂ、ｃ）のとき、ａ¬ｂｃは最小項であり、ａ¬ｂは最小項ではない。尚、「¬ｂ」は、ｂの否定を意味する。
【００４９】
制御部１１は、ノードごとに、Ｐ：最上位ノードから辿って否定枝を偶数回通る場合の最小項の数、及び、Ｎ：最上位ノードから辿って否定枝を奇数回通る場合の最小項の数、を算出する。
最初に、制御部１１は、定数ノードの最小項の数を算出する。定数ノードのＰは２のｎ乗（ｎはブーリアン変数の数、すなわち、並び替え後ビット列２３のビット数）であり、Ｎは０である。図３に示す通り、並び替え後ビット列２３のビット数は「６」なので、定数ノードのＰ＝２の６乗＝６４となる。従って、図７に示す定数ノード３４については、Ｐ＝６４、Ｎ＝０となる。
【００５０】
次に、制御部１１は、深さ優先探索によって、定数ノード以外の各ノードの最小項の数を再帰的に算出する。
制御部１１は、図６に示すように、（ａ）Ｅｌｓｅ枝が否定枝ではない場合と、（ｂ）Ｅｌｓｅ枝が否定枝の場合に分けて、各ノードにおける最小項の数を算出する。
まず、図６（ａ）の場合について説明する。図６（ａ）では、ノード３２ｄが算出対象のノード、Ｔｈｅｎ枝によって接続された下位のノード３２ｂのＰの値がｔ_ｐ（既知）及びＮの値がｔ_ｎ（既知）、並びに、Ｅｌｓｅ枝によって接続された下位のノード３２ｃのＰの値がｅ_ｐ（既知）及びＮの値がｅ_ｎ（既知）である。このとき、制御部１１は、下位のノード３２ｂと３２ｃの算出結果を用いて、Ｐ＝ｔ_ｐ／２＋ｅ_ｐ／２、Ｎ＝ｔ_ｎ／２＋ｅ_ｎ／２の式によって、ノード３２ｄの最小項の数を算出する。
次に、図６（ｂ）の場合について説明する。図６（ｂ）では、ノード３２ｇが算出対象のノード、Ｔｈｅｎ枝によって接続された下位のノード３２ｅのＰの値がｔ_ｐ（既知）及びＮの値がｔ_ｎ（既知）、並びに、否定Ｅｌｓｅ枝によって接続された下位のノード３２ｆのＰの値がｅ_ｐ（既知）及びＮの値がｅ_ｎ（既知）である。このとき、制御部１１は、下位のノード３２ｅと３２ｆの算出結果を用いて、Ｐ＝ｔ_ｐ／２＋ｅ_ｎ／２、Ｎ＝ｔ_ｎ／２＋ｅ_ｐ／２の式によって、ノード３２ｇの最小項の数を算出する。
【００５１】
例えば、図７に示すノード３２ｈの場合、下位のノード（＝定数ノード３４）と接続されたＥｌｓｅ枝が否定枝であるから、図６（ｂ）の算出方法によって最小項の数を算出する。つまり、ノード３４については、Ｐ＝６４／２＋０／２＝３２、Ｎ＝６４／２＋０／２＝３２となる。
【００５２】
また、例えば、図７に示すノード３２ｉの場合、下位のノードと接続されたＥｌｓｅ枝が否定枝ではないことから、図６（ａ）の算出方法によって最小項の数を算出する。つまり、ノード３２ｉについては、Ｐ＝３２／２＋６４／２＝４８、Ｎ＝３２／２＋０／２＝１６となる。
【００５３】
図２の説明に戻る。次に、制御部１１は、二分決定グラフの各ノードにおける局所密度を算出する（Ｓ６）。局所密度の算出処理は、図８、図９を参照して説明する。
【００５４】
図８は、局所密度の算出処理を説明する図である。図９は、局所密度の算出結果を示す図である。尚、図９に示すＰ及びＮの数値の意味と、図７に示すＰ及びＮの数値の意味は異なることに留意する。
【００５５】
図８（ａ）は、図７のノード３２ｊのＰ接続の局所密度を、便宜的にカルノー図３０ｂによって示している。また、図８（ｂ）は、図７のノード３２ｋのＰ接続の局所密度を、便宜的にカルノー図３０ｃによって示している。
ここで、最上位ノードから辿って着目しているノードまでに否定枝を偶数回通るパスのことを、「Ｐ接続」という。また、最上位ノードから辿って着目しているノードまでに否定枝を奇数回通るパスのことを、「Ｎ接続」という。
【００５６】
まず、ノード３２ｊについて考える。
図７を参照すると分かるように、最上位ノード３３からノード３２ｊまでのパスは、枝３５ａ、枝３５ｂを順に通るパスのみである。
枝３５ａはＥｌｓｅ枝であり、ブーリアン変数ｄ１が「０」であることに対応する。同様に、枝３５ｂはＥｌｓｅ枝であり、ブーリアン変数ｅ１が「０」であることに対応する。それ以外のブーリアン変数ｄ２、ｅ２、ｄ３、ｅ３については、ドントケア（「ドントケア」とは、値が「０」でも「１」でも良いことを意味する。）となる。図８（ａ）に示す点線の矩形領域４１ａは、この領域を示しており、ｄ１が「０」、ｅ１が「０」、それ以外がドントケアの領域である。
更に、図８（ａ）に示すカルノー図３０ｂは、カルノー図３０ａにおける矩形領域４１ａのパターンを４個繰り返したものである。そして、ノード３２ｊのＰ接続の局所密度は、カルノー図３０ｂの全体密度と一致する。つまり、図９に示すように、ノード３２ｊのＰ接続の局所密度は、「０．２５」である。
【００５７】
次に、ノード３２ｋについて考える。
図７を参照すると分かるように、最上位ノード３３からノード３２ｋまでのパスは、枝３５ａ、枝３５ｂ、枝３５ｃ、枝３５ｄを順に通る第１のパスと、枝３５ａ、枝３５ｂ、枝３５ｅ、枝３５ｆを順に通る第２のパスの２つである。
第１のパスについては、ブーリアン変数ｄ１が「０」、ｅ１が「０」、ｄ２が「１」、ｅ２が「０」に対応する。それ以外のブーリアン変数ｄ３、ｅ３については、ドントケアとなる。図８（ｂ）に示す点線の矩形領域４１ｂは、この領域を示している。
また、第２のパスについては、ブーリアン変数ｄ１が「０」、ｅ１が「０」、ｄ２が「０」、ｅ２が「１」に対応する。それ以外のブーリアン変数ｄ３、ｅ３については、ドントケアとなる。図８（ｂ）に示す点線の矩形領域４１ｃは、この領域を示している。
更に、図８（ｂ）に示すカルノー図３０ｃは、カルノー図３０ａにおける矩形領域４１ｂ（又は４１ｃ）のパターンを１６個繰り返したものである。そして、ノード３２ｋのＰ接続の局所密度は、カルノー図３０ｃの全体密度と一致する。つまり、図９に示すように、ノード３２ｋのＰ接続の局所密度は、「０．２５」である。
【００５８】
本発明の実施の形態では、制御部１１は、Ｓ５において、二分決定グラフ３１の各ノードにおける最小項の数を算出している。従って、制御部１１は、ビット列のビット数をｎとしたとき、「二分決定グラフ３１の各ノードにおける最小項の数÷２のｎ乗」を各ノードにおけるＰ接続の局所密度として算出することができる。つまり、制御部１１は、各ノードにおける最小項の数を用いることによって、図８に示すカルノー図３０ｂ、３０ｃの構築処理を実行する必要はない。
例えば、ノード３２ｊのＰ接続の局所密度＝ノード３２ｊにおける最小項の数÷２のｎ乗＝１６／２の６乗＝０．２５である。また、例えば、ノード３２ｋのＰ接続の局所密度＝ノード３２ｋにおける最小項の数÷２のｎ乗＝１６／２の６乗＝０．２５である。他のノードについても同様である。
尚、各ノードのＮ接続の局所密度は、「１−各ノードのＰ接続の局所密度」である。
【００５９】
図２の説明に戻る。次に、制御部１１は、局所密度から単一データの密度換算値を引いた値を単一データ除外局所密度として算出する（Ｓ７）。
以下、単一データ除外局所密度を、「ＬＯＯ（Ｌｅａｖｅ−Ｏｎｅ−Ｏｕｔ）密度」と省略して記載する。ＬＯＯ密度の算出処理は、図１０を参照して説明する。
【００６０】
図１０は、ＬＯＯ密度の算出結果を示す図である。尚、図１０に示すＰ及びＮの数値の意味と、図７、図９に示すＰ及びＮの数値の意味は異なることに留意する。
【００６１】
ＬＯＯ密度は、「局所密度−単一データの密度換算値」である。また、次元数をＭ、局所密度に対応するノードのレベルをＬとしたとき、各ノードの密度換算値は、「｛２の（Ｌ×Ｍ）乗｝の逆数」と定義する。纏めると、ＬＯＯ密度＝局所密度−｛２の（Ｌ×Ｍ）乗｝の逆数、となる。
そして、制御部１１は、ノードごとにＬＯＯ密度を算出する。
【００６２】
ここで、レベルＬについて説明する。図１０に示すように、定数ノード３４を「レベル０」、「最下位ビット」（ＬＳＢ）であるｄ３、ｅ３に対応するノードを「レベル１」、次の階層のビットであるｄ２、ｅ２に対応するノードを「レベル２」、「最上位ビット」（ＭＳＢ）であるｄ１、ｅ１に対応するノードを「レベル３」とする。つまり、数値属性の次元（変量）を表すのに用いたビット列の長さＫとレベルＬの最大値が一致し、レベルＬは０〜Ｍの整数値を取る。
【００６３】
図１０を参照しながら、ＬＯＯ密度の算出例を説明する。
例えば、ノード３２ｊのＰ接続のＬＯＯ密度は、０．２５−１／（２の（２×２）乗）＝０．２５−１／１６＝３／１６≒０．１９となる。
また、例えば、ノード３２ｊのＮ接続のＬＯＯ密度は、０．７５−１／（２の（２×２）乗）＝０．７５−１／１６＝１１／１６≒０．６９となる。
また、例えば、ノード３２ｋのＰ接続のＬＯＯ密度は、０．２５−１／（２の（１×２）乗）＝０．２５−１／４＝０となる。
また、例えば、ノード３２ｋのＮ接続のＬＯＯ密度は、０．７５−１／（２の（１×２）乗）＝０．７５−１／４＝０．５となる。
尚、定数ノード３４については、ＬＯＯ密度＝ｍａｘ｛０，局所密度−｛２の（Ｌ×Ｍ）乗｝の逆数｝の式によって算出している。これは、ＬＯＯ密度が負の値になることを避ける為である。但し、このことは本質的なことではなく、ＬＯＯ密度が負の値になっても、本発明では特に問題はない。
【００６４】
図２の説明に戻る。次に、制御部１１は、ＬＯＯ密度に基づいて、各データの外れ度合を算出する（Ｓ８）。外れ度合の算出処理は、図１１〜図１３を参照して説明する。
【００６５】
図１１は、二分決定グラフにおける着目データを表すパスを示す図である。図１２は、カルノー図における着目データを表す領域を示す図である。図１３は、抽出されるＬＯＯ密度を説明する図である。
制御部１１は、データセットの中から１つずつ着目データを決定し、着目データごとに処理を実行する。以下では、着目データｘとして、（ｄ１，ｅ１，ｄ２，ｅ２，ｄ３，ｅ３）＝（１，０，０，１，１，０）の例を示す。
【００６６】
制御部１１は、二分決定グラフでの着目データｘを表すパスを探索し、レベル（階層）が変化するノードに係るＬＯＯ密度を抽出し、抽出されたＬＯＯ密度に基づいて、着目データｘの外れ度合を算出する。
【００６７】
図１１に示す例であれば、レベル（階層）が変化するノードは、ノード３２ａ、３２ｌ、３２ｍ、３４の４つである。
Ｐ接続のＬＯＯ密度を抽出するか、それとも、Ｎ接続のＬＯＯ密度を抽出するかについては、最上位ノードから辿って否定枝を通る回数によって決まる。つまり、制御部１１は、最上位ノードから辿って否定枝を偶数回通る場合にはＰ接続のＬＯＯ密度を抽出し、最上位ノードから辿って否定枝を奇数回通る場合にはＮ接続のＬＯＯ密度を抽出する。
制御部１１は、ノード３２ａについては、否定枝を１回通ることから、Ｎ接続のＬＯＯ密度「０．２８」を抽出する。また、制御部１１は、ノード３２ｌについても、否定枝を１回通ることから、Ｎ接続のＬＯＯ密度「０．３８」を抽出する。また、制御部１１は、ノード３２ｍについても、否定枝を１回通ることから、Ｎ接続のＬＯＯ密度「０．２５」を抽出する。また、制御部１１は、定数ノード３４については、否定枝を２回通ることから、Ｐ接続のＬＯＯ密度「０」を抽出する。
結局、制御部１１は、（０．２８、０．３８、０．２５、０）を抽出する。
【００６８】
図１３を参照しながら、抽出された各ＬＯＯ密度の意味について説明する。
図１３（ａ）に示すように、レベル０のＬＯＯ密度、すなわち定数ノード３４のＬＯＯ密度は、１個の単位領域（＝着目データｘ自身が占める領域）である矩形領域４１ｄを全体領域としたときに、着目データｘ自身を除外したときのデータ密度に相当する。
また、図１３（ｂ）に示すように、レベル１のＬＯＯ密度、すなわちノード３２ｍのＬＯＯ密度は、４個の単位領域である矩形領域４１ｅを全体領域としたときに、着目データｘ自身を除外したときのデータ密度に相当する。
また、図１３（ｃ）に示すように、レベル２のＬＯＯ密度、すなわちノード３２ｌのＬＯＯ密度は、１６個の単位領域である矩形領域４１ｆを全体領域としたときに、着目データｘ自身を除外したときのデータ密度に相当する。
また、図１３（ｄ）に示すように、レベル３のＬＯＯ密度、すなわちノード３２ａのＬＯＯ密度は、６４個の単位領域である矩形領域４１ｇを全体領域としたときに、着目データｘ自身を除外したときのデータ密度に相当する。
このように、抽出されたＬＯＯ密度は、階層局所密度（ＨＬＤ：Hierarchical Local Densities）と言える。
【００６９】
制御部１１は、例えば、抽出されたＬＯＯ密度（階層局所密度）の最大値を、着目データの外れ度合とする。図１１に示す例では、制御部１１は、（０．２８、０．３８、０．２５、０）の最大値「０．３８」を、着目データｘの外れ度合とする。
また、制御部１１は、抽出されたＬＯＯ密度の最大値に代えて、抽出されたＬＯＯ密度の平均値や中央値などを、着目データの外れ度合としても良い。
【００７０】
また、制御部１１は、抽出されたＬＯＯ密度の全部に基づいて外れ度合を算出するのではなく、抽出されたＬＯＯ密度の一部に基づいて外れ度合を算出しても良い。
例えば、制御部１１は、抽出されたＬＯＯ密度の中から、高いレベル（階層）のノードに係るＬＯＯ密度に基づいて、外れ度合を算出しても良い。図１１に示す例であれば、制御部１１は、「レベル３」、「レベル２」のノードに係るＬＯＯ密度（０．２８、０．３８）に基づいて外れ度合を算出しても良い。この場合も、制御部１１は、最大値、平均値、中央値などを、着目データの外れ度合とすることができる。
【００７１】
前述の説明では、観測領域を２分決定グラフとして構築したが、観測領域をカルノー図やその他のデータ構造によって構築した場合も、本発明を適用することが可能である。
制御部１１は、データセットに含まれるデータの中から着目データを１つずつ決定し、観測領域から着目データに相当する領域を除去したときの着目データの周辺のデータ密度に基づいて、着目データの外れ度合を算出すれば良い。ＬＯＯ密度は、観測領域から着目データに相当する領域を除去したときの着目データの周辺のデータ密度の１例である。
【００７２】
図２の説明に戻る。次に、制御部１１は、Ｓ８によって算出された外れ度合と、予め定められた閾値を比較することによって、外れ値を検出する（Ｓ９）。尚、Ｓ９は必須ではない。例えば、制御部１１は、出力手段（メディア入出力部１３、通信制御部１４、表示部１６、周辺機器Ｉ／Ｆ部１７等）を介して、Ｓ８によって算出された外れ度合の一覧を出力しても良い。そして、ユーザが、外れ度合の一覧を参照して、外れ値を検出しても良い。
【００７３】
図２に示す処理の中で最も計算負荷が高い処理は、Ｓ４の二分決定グラフの構築処理である。データセットのデータ数をＮ、二次元グラフのノード数をＤとすると、二分決定グラフの構築処理の計算量のオーダーは、О（Ｎ×Ｄ）である。
ところで、データセットの次元数が小さい場合、ノード数Ｄはあまり大きくならないことが多い。そこで、与えられたデータセットの次元数が大きい場合、次元縮約の手法を用いて次元数を小さくしても良い。適切な次元縮約を行えば、結果に影響を与えることなく、次元数を小さくすることができる。また、数値属性のデータを丸めて、ビット数を制限することによって、ノード数Ｄを小さくすることもできる。
従って、Ｓ４の二分決定グラフの構築処理を行う前に、適切な前処理を行うことによって、Ｄ≪Ｎとみなすことができる。つまり、計算量のオーダーは、О（Ｎの１乗）とみなすことができる。
【００７４】
また、図２の各ステップを見れば分かるように、ユーザがチューニングすべきパラメータは、Ｓ９の閾値のみである。ここで、Ｓ９の閾値は、外れ値か否かを判定する為のパラメータであって、外れ度合を算出する為のパラメータではない。つまり、外れ値検出装置１は、パラメータチューニング作業を行わなくても、外れ度合を算出することができる。
そして、Ｓ９の閾値を変更しても、Ｓ１〜Ｓ８の処理を再度実行する必要はなく、Ｓ９の処理の計算負荷は無視できる程度に小さいことから、外れ値検出装置１は、実用的な時間内に外れ値の検出を支援又は実行することができる。
【００７５】
以上、本発明の実施の形態では、外れ値検出装置１が、データセットに含まれる各データを次元ごとにビット列に変換し、ビット列に基づいて、データセットの観測領域を構築する。次に、外れ値検出装置１が、データセットに含まれるデータの中から着目データを１つずつ決定し、観測領域から着目データに相当する領域を除去したときの着目データの周辺のデータ密度に基づいて、着目データの外れ度合を算出する。
これによって、非線形のデータセットに対して、パラメータチューニング作業を行うことなく、実用的な時間内に外れ値の検出を支援又は実行することができる。
【実施例１】
【００７６】
以下では、図１４〜図１９を参照しながら、本発明の実施例１及び比較例について説明する。
図１４は、実施例１及び比較例に用いたデータセットを示す図である。図１４に示すデータセットは、２次元空間において、夜空の月（Moon）と星（Star）の光を模式的にプロットしたものである。以下では、図１４に示すデータセットを、MoonStarデータセットと呼ぶ。MoonStarデータセットの性質は、以下の通りである。
・人工的に発生させたデータ
・次元数Ｍ＝２
・データの９５％は三日月形状の領域内に分布し、残り５％はランダムに分布
・データ数Ｎ＝１０００、５０００
図１４（ａ）は、データ数Ｎ＝１０００のデータセットであり、MoonStar1000と呼ぶ。図１４（ｂ）は、データ数Ｎ＝５０００のデータセットであり、MoonStar5000と呼ぶ。いずれも、「○」が各データを示している。
【００７７】
判定精度を適切に比較できるように、後述する通り、いずれの例においても、データセットの５％を外れ値（Star）と判定した。また、計算時間も適切に比較できるように、全て同じコンピュータによって実行した。
【００７８】
実施例１では、外れ値検出装置１によって外れ度合を算出し、値の小さかった５％（Ｓ９の閾値）を外れ値と判定した。
比較例１では、ＯＣ−ＳＶＭ（One−Class Support Vector Machine）において、非線形写像を決めるカーネルパラメータγを「０．５」、外れ値の割合を指定するパラメータｖを「０．０５」とした。
比較例２では、ＯＣ−ＳＶＭにおいて、非線形写像を決めるカーネルパラメータγを「２」、外れ値の割合を指定するパラメータｖを「０．０５」とした。
比較例３では、ＬＯＦ（Local Outlier Factor）において、パラメータｋを「１０」とし、値の大きかった５％を外れ値と判定した。
比較例４では、ＬＯＦにおいて、パラメータｋを「１００」とし、値の大きかった５％を外れ値と判定した。
尚、ＯＣ−ＳＶＭの計算では、いずれも、統計計算言語Ｒのe1071ライブラリに含まれるsvm関数を使用した。また、ＬＯＦの計算では、いずれも、統計計算言語Ｒのdprepライブラリに含まれるlofactor関数を使用した。
【００７９】
図１５は、実施例１における外れ値の検出結果を示す図である。図１５（ａ）はMoonStar1000、図１５（ｂ）はMoonStar5000の結果である。いずれも、「×」が外れ値（Star）として検出されたデータ、「○」がMoonと判定されたデータを示している。尚、「×」（外れ値）の視認性を上げる為、「○」の色を淡いグレーによって図示している。以下、図１６〜図１９も同様である。
【００８０】
以下に示す表１、表２は、それぞれ、実施例１におけるMoonStar1000、MoonStar5000の判別結果を示している。
【００８１】
【表１】
【００８２】
【表２】
【００８３】
ここで、４つのマスのうち、左上のマスは、「Moon」を「Moon」と検出した数を示している。右上のマスは、「Moon」を「Star」と検出した数を示している。左下のマスは、「Star」を「Moon」と検出した数を示している。右下のマスは、「Star」を「Star」と検出した数を示している。左上と右下の合計が、正しく検出した数である。左下と右上の合計が、誤って検出した数である。以下、表３〜表１０も同様である。
【００８４】
実施例１では、MoonStar1000に対して計算時間が０．０３秒、MoonStar5000に対して計算時間が０．１７秒であった。つまり、データ数が５倍の増加に対して、計算時間の増加率は約５．７倍であることから、データ数Ｎに対して、実施例１の計算時間のオーダーはО（Ｎの１乗）と言える。
【００８５】
図１６は、比較例１における外れ値の検出結果を示す図である。また、以下に示す表３、表４は、それぞれ、比較例１におけるMoonStar1000、MoonStar5000の判別結果を示している。
【００８６】
【表３】
【００８７】
【表４】
【００８８】
比較例１では、MoonStar1000に対して計算時間が０．０７秒、MoonStar5000に対して計算時間が１．３０秒であった。つまり、データ数が５倍の増加に対して、計算時間は約１８．６倍の増加であることから、実施例１と比較すると、明らかに、データ数の増加に対する計算時間の増加率が高い。
【００８９】
図１７は、比較例２における外れ値の検出結果を示す図である。また、以下に示す表５、表６は、それぞれ、比較例２におけるMoonStar1000、MoonStar5000の判別結果を示している。
【００９０】
【表５】
【００９１】
【表６】
【００９２】
比較例２では、MoonStar1000に対して計算時間が０．１１秒、MoonStar5000に対して計算時間が１．６９秒であった。つまり、データ数が５倍の増加に対して、計算時間は約１５．４倍の増加であることから、実施例１と比較すると、明らかに、データ数の増加に対する計算時間の増加率が高い。
【００９３】
図１８は、比較例３における外れ値の検出結果を示す図である。また、以下に示す表７、表８は、それぞれ、比較例３におけるMoonStar1000、MoonStar5000の判別結果を示している。
【００９４】
【表７】
【００９５】
【表８】
【００９６】
比較例３では、MoonStar1000に対して計算時間が２．０５秒、MoonStar5000に対して計算時間が３４．９５秒であった。つまり、データ数が５倍の増加に対して、計算時間は約１７．０倍の増加であることから、実施例１と比較すると、明らかに、データ数の増加に対する計算時間の増加率が高い。
【００９７】
図１９は、比較例４における外れ値の検出結果を示す図である。また、以下に示す表９、表１０は、それぞれ、比較例４におけるMoonStar1000、MoonStar5000の判別結果を示している。
【００９８】
【表９】
【００９９】
【表１０】
【０１００】
比較例４では、MoonStar1000に対して計算時間が６．３８秒、MoonStar5000に対して計算時間が１５０．４７秒であった。つまり、データ数が５倍の増加に対して、計算時間は約２３．６倍の増加であることから、実施例１と比較すると、明らかに、データ数の増加に対する計算時間の増加率が高い。
【０１０１】
以上から、計算時間は、ＯＣ−ＳＶＭやＬＯＦよりも、本発明の外れ値検出装置１の方が優位であることが分かった。
以下では、計算精度についても、本発明の外れ値検出装置１の方が、ＯＣ−ＳＶＭやＬＯＦよりも優位であることについて説明する。
【０１０２】
実施例１と比較例１〜４の計算精度を比較する為、以下に示す表１１では、実施例１と比較例１〜４のＡＵＣ（area under the ＲＯＣ curve）を示している。ここで、ＲＯＣは、receiver operating characteristic（受診者操作特性）の略である。ＡＵＣは０〜１の値を取り、１に近い程、精度が良いことを示している。
【０１０３】
【表１１】
【０１０４】
表１１に示すように、本発明では、MoonStar1000とMoonStar5000の両方ともＡＵＣが０．９以上であり、安定して高い精度を達成している。これに対して、ＯＣ−ＳＶＭでは、MoonStar1000とMoonStar5000の両方ともＡＵＣが０．９以下であり、十分な精度が達成できていない。また、ＬＯＦについては、パラメータ次第で結果が大きく左右されており、パラメータチューニング作業が不可欠であることが分かる。
【実施例２】
【０１０５】
以下では、図２０〜図２２を参照しながら、本発明の実施例２について説明する。実施例２は、外れ値検出装置１を車両故障診断システムに適用する例である。
【０１０６】
図２０は、実施例２における車両故障診断システムの構成図である。図２０に示すように、車両故障診断システム１００は、故障診断の対象となる車両システム１０１、データ収集装置１０２、及び外れ値検出装置１によって構成される。
【０１０７】
車両システム１０１は、自動車等の車両に搭載されるシステムである。車両システム１０１は、複数のＥＣＵ（Electronic Control Unit：電子制御装置）、複数のセンサ、複数のアクチュエータ等が車載ネットワークを介して接続されている。
【０１０８】
データ収集装置１０２は、走行中の車両データを収集する装置である。データ収集装置１０２は、車載ネットワークに流れる信号、各コンポーネント（ＥＣＵ、センサ、アクチュエータ等）の状態値等を車両データとして収集する。そして、データ収集装置１０２は、無線又は有線によって接続される外れ値検出装置１に車両データを送信する。
【０１０９】
データ収集装置１０２は、例えば、車両システム１０１の内部に設置されても良いし、外付け装置として設置されても良い。また、データ収集装置１０２は、例えば、車両システム１０１から物理的に離れた場所に設置されるコンピュータ（外れ値検出装置１を含む。）でも良い。データ収集装置１０２が車両システム１０１から物理的に離れた場所に設置される場合、車両システム１０１は、無線通信によってデータ収集装置１０２に車両データを送信する。
【０１１０】
外れ値検出装置１は、データ収集装置１０２によって収集される車両データから外れ値を検出する。これに対して、車両の故障診断を行う専門家は、検出される外れ値を詳細に確認し、車両に異常が発生しているか否かを確認する。
【０１１１】
図２１は、実施例２における車両故障診断システムの処理を示すフローチャートである。図２１に示すように、データ収集装置１０２は、車両システム１０１から、走行中の車両データを収集する（Ｓ１１）。
【０１１２】
次に、外れ値検出装置１は、前述の図２に示すフローチャートに従って、データ収集装置１０２によって収集される車両データから外れ値を検出する（Ｓ１２）。
【０１１３】
車両の故障診断を行う専門家は、外れ値検出装置１によって検出される外れ値を詳細に確認する。対処が必要な異常が発生している場合（Ｓ１３のＹ）、専門家は運転者に通知し、修理を促す（Ｓ１４）。又は、外れ値検出装置１が無線通信によって車両システム１０１に異常がある旨のメッセージを送信し、車両システム１０１が出力装置（表示装置や音声出力装置等）によって警報を出力しても良い。
【０１１４】
図２２は、実施例２における外れ値の検出結果を示す図である。図２２は、アクセル操作量、エンジン回転数、変速位置の３次元（３変量）のデータセットに対して、外れ値検出装置１が外れ値の検出を行った結果を示している。
【０１１５】
アクセル操作量及びエンジン回転数は、数値属性の変量である。変速位置は、「Ｌｏｗ」、「２ｎｄ」、「３ｒｄ」の３つの値を取り得ることから、カテゴリ属性の変量とも言えるし、数値属性の変量とも言える。
【０１１６】
図２２では、「×」が外れ値として検出されたデータ、「○」が外れ値ではないと判定されたデータを示している。図２２に示す例では、変速位置が「Ｌｏｗ」のとき、１つの外れ値が検出されている。これは、「アクセル操作量に対してエンジンの吹け上がりが悪い」という異常を示すものである。このように、本発明の外れ値検出装置１を車両故障診断システム１００に適用すれば、車両の故障診断を精度良く行うことができる。
【０１１７】
以上、添付図面を参照しながら、本発明に係る外れ値検出装置等の好適な実施形態について説明したが、本発明はかかる例に限定されない。当業者であれば、本願で開示した技術的思想の範疇内において、各種の変更例又は修正例に想到し得ることは明らかであり、それらについても当然に本発明の技術的範囲に属するものと了解される。
【符号の説明】
【０１１８】
１………外れ値検出装置
２１………データセット
２２ａ、２２ｂ………ビット列
２３………並び替え後ビット列
３０ａ〜３０ｃ………カルノー図
３１………二分決定グラフ
３２ａ〜３２ｍ………ノード
３３………最上位ノード
３４………定数ノード
３５ａ〜３５ｆ………枝
４１ａ〜４１ｇ………矩形領域
【技術分野】
【０００１】
本発明は、データの次元数が１又は複数、かつデータ数が複数のデータセットから外れ値の検出を支援又は実行する外れ値検出装置等に関するものである。
【背景技術】
【０００２】
外れ値検出問題は、与えられたデータセットの中から、データ密度が低い領域に属するデータを外れ値として見つける問題と考えられる。外れ値検出問題を解く技術の応用例としては、データセットに含まれるノイズデータの除去処理（データスクリーニングの前処理）、クレジット取引のデータセットの中から通常行われていない取引を行っている顧客を検出する処理、生産ラインにおける生産物のデータセットの中から不良品を検出する処理などが考えられる。
【０００３】
外れ値検出問題を解く技術としては、例えば、以下の３つが知られている。
・マハラノビス距離
・One−Class Support Vector Machine（以下、「ＯＣ−ＳＶＭ」と省略。）
・Local
Outlier Factor（以下、「ＬＯＦ」と省略。）
【０００４】
非特許文献１には、マハラノビス距離について記載されている。非特許文献１では、与えられたデータセットの全体の重心（平均）と共分散行列を求め、各データに対して共分散行列を用いて正規化した重心との距離を求め、距離が大きいデータを外れ値とみなす。
マハラノビス距離では、データセットが多変量正規分布に従うことを仮定しており、データセットが多変量正規分布では記述できない場合、すなわちデータセットが非線形の場合、適切な外れ値を検出することができない。
【０００５】
非特許文献２には、ＯＣ−ＳＶＭについて記載されている。非特許文献２では、入力されるデータセットを非線形写像によって高次の特徴空間Ｆに写像し、写像されたデータ群と原点を分離する超平面のうち、原点からの距離が最大のものを選択する。ＯＣ−ＳＶＭを外れ値検出問題に適用する場合には、一定割合のデータが超平面よりも原点側に分類されることを許すように超平面を決定し、原点側に分類されたデータを外れ値とみなす。
ＯＣ−ＳＶＭでは、解が求まり易い凸最適化問題を解くことによって、超平面を求めることができる。また、非線形写像を用いるので、非線形なデータセットに適用できる。
【０００６】
非特許文献３には、ＬＯＦについて記載されている。非特許文献３では、まず、各データｘに対し、データｘ自身に近いｋ個のデータとの距離の平均値を、データｘのｋ近傍距離として求める。次に、｛データｘのｋ近傍距離÷周辺のデータｋ個のｋ近傍距離の平均値｝を、データｘのＬＯＦとして求める。これらの処理から分かるように、データｘ自身のｋ近傍距離よりも、周辺のデータｋ個のｋ近傍距離の平均値が小さい程、ＬＯＦは大きな値を取る。そして、ＬＯＦが大きいデータを、外れ値とみなす。
ＬＯＦも、非線形なデータセットに適用できる。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Mahalanobis, P.C., On the generalized distance in statistics,Proceedings of the National Institute of Science, 49-55, 1936
【非特許文献２】Scholkopf, B. et. al., Estimating the Support of a High-DimensionalDistribution, Neural computation, 7, 1443-1471, 2001
【非特許文献３】Breunig, M.M. et. al., LOF: Identifying Density-Based LocalOutliers, SIGMOD Conference, 93-104, 2000
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、前述の３つの従来技術は、以下の問題がある。
前述の通り、マラハノビス距離は、データセットが非線形の場合、適切な外れ値を検出することができないという問題がある。
【０００９】
ＯＣ−ＳＶＭは、適切な非線形写像を選ぶことが難しいという未解決の問題がある。これは、非線形写像を決めるパラメータを人間が試行錯誤によって決定するパラメータチューニング作業が必要という課題に帰結する。
また、ＯＣ−ＳＶＭは、データ数が多い場合、最適化問題を解く為に時間がかかる。データ数をＮとすると、何ら工夫をしなければ、ＯＣ−ＳＶＭの計算量のオーダーはО（Ｎの３乗）である。
【００１０】
ＬＯＦは、適切なｋを選ぶことが難しいという未解決の問題がある。これも、ＯＣ−ＳＶＭと同様、パラメータチューニング作業が必要という課題に帰結する。
また、ＬＯＦは、計算負荷も比較的高い。データ数をＮとすると、何ら工夫をしなければ、ＬＯＦの計算量のオーダーはО（Ｎの２乗）である。
【００１１】
本発明は、前述した問題点に鑑みてなされたもので、その目的とすることは、非線形のデータセットに対して、パラメータチューニング作業を行うことなく、実用的な時間内に外れ値の検出を支援又は実行する外れ値検出装置等を提供することである。
【課題を解決するための手段】
【００１２】
前述した目的を達成するために第１の発明は、データの次元数が１又は複数、かつデータ数が複数のデータセットから外れ値の検出を支援又は実行する外れ値検出装置であって、前記データセットに含まれる各データを次元ごとにビット列に変換し、前記ビット列に基づいて、前記データセットの観測領域を構築する構築手段と、前記データセットに含まれるデータの中から着目データを１つずつ決定し、前記観測領域から前記着目データに相当する領域を除去したときの前記着目データの周辺のデータ密度に基づいて、前記着目データの外れ度合を算出する算出手段と、を具備する外れ値検出装置である。
第１の発明によって、非線形のデータセットに対して、パラメータチューニング作業を行うことなく、実用的な時間内に外れ値の検出を支援又は実行することができる。
【００１３】
第１の発明における前記構築手段は、前記観測領域を二分決定グラフとして構築し、前記算出手段は、各ノードにおける局所密度から単一データの密度換算値を引いた値を単一データ除外局所密度とし、更に、前記単一データ除外局所密度に基づいて、前記着目データの外れ度合を算出することが望ましい。
これによって、データ数をＮ、ノード数をＤとすると、少なくとも、第１の発明の計算量のオーダーは、О（Ｎ×Ｄ）であり、ＯＣ−ＳＶＭやＬＯＦよりも優位である。
【００１４】
また、第１の発明における前記構築手段は、数値属性の次元に係る前記ビット列群を最上位ビットから最下位ビットの順に並び変えて、前記二分決定グラフを階層的に構築し、前記算出手段は、前記二分決定グラフでの前記着目データを表すパスを探索し、階層が変化するノードに係る前記単一データ除外局所密度に基づいて、前記着目データの外れ度合を算出することが望ましい。
これによって、データセットの特性について事前に何も情報を持っていない場合にも、適切な外れ度合を算出することができる。
【００１５】
また、前記算出手段は、例えば、階層が変化するノードに係る前記単一データ除外局所密度の一部若しくは全部の最大値、中央値又は平均値を、前記着目データの外れ度合とする。
また、第１の発明は、例えば、前記外れ度合と閾値を比較することによって、外れ値を検出する検出手段、を更に具備しても良い。
【００１６】
第２の発明は、データの次元数が１又は複数、かつデータ数が複数のデータセットから外れ値の検出を支援又は実行する外れ値検出方法であって、前記データセットに含まれる各データを次元ごとにビット列に変換し、前記ビット列に基づいて、前記データセットの観測領域を構築する構築ステップと、前記データセットに含まれるデータの中から着目データを決定し、前記観測領域において、前記着目データ自身が占める領域を除く前記着目データ周辺のデータ密度である着目データ除去局所密度を算出する算出ステップと、を含む外れ値検出方法である。
【００１７】
第３の発明は、コンピュータを、データの次元数が１又は複数、かつデータ数が複数のデータセットから外れ値の検出を支援又は実行し、前記データセットに含まれる各データを次元ごとにビット列に変換し、前記ビット列に基づいて、前記データセットの観測領域を構築する構築手段と、前記データセットに含まれるデータの中から着目データを決定し、前記観測領域において、前記着目データ自身が占める領域を除く前記着目データ周辺のデータ密度である着目データ除去局所密度を算出する算出手段と、を具備する外れ値検出装置として機能させる為のプログラムである。
【００１８】
第４の発明は、データの次元数が１又は複数、かつデータ数が複数のデータセットから外れ値の検出を支援又は実行する外れ値検出装置と、車両データを収集するデータ収集装置と、を含む車両故障診断システムであって、前記外れ値検出装置は、前記データ収集装置によって収集される前記車両データを前記データセットとし、前記データセットに含まれる各データを次元ごとにビット列に変換し、前記ビット列に基づいて、前記データセットの観測領域を構築する構築手段と、前記データセットに含まれるデータの中から着目データを１つずつ決定し、前記観測領域から前記着目データに相当する領域を除去したときの前記着目データの周辺のデータ密度に基づいて、前記着目データの外れ度合を算出する算出手段と、前記外れ度合と閾値を比較することによって、外れ値を検出する検出手段と、を具備する車両故障診断システムである。
【発明の効果】
【００１９】
本発明により、非線形のデータセットに対して、パラメータチューニング作業を行うことなく、実用的な時間内に外れ値の検出を支援又は実行する外れ値検出装置等を提供することができる。
【図面の簡単な説明】
【００２０】
【図１】外れ値検出装置のハードウエア構成図
【図２】外れ値検出装置の処理の詳細を示すフローチャート
【図３】データセットの変換処理を説明する図
【図４】カルノー図を示す図
【図５】二分決定グラフを示す図
【図６】最小項の数の算出処理を説明する図
【図７】最小項の数の算出結果を示す図
【図８】局所密度の算出処理を説明する図
【図９】局所密度の算出結果を示す図
【図１０】ＬＯＯ密度の算出結果を示す図
【図１１】二分決定グラフにおける着目データを表すパスを示す図
【図１２】カルノー図における着目データを表す領域を示す図
【図１３】抽出されるＬＯＯ密度を説明する図
【図１４】実施例１及び比較例に用いたデータセットを示す図
【図１５】実施例１における外れ値の検出結果を示す図
【図１６】比較例１における外れ値の検出結果を示す図
【図１７】比較例２における外れ値の検出結果を示す図
【図１８】比較例３における外れ値の検出結果を示す図
【図１９】比較例４における外れ値の検出結果を示す図
【図２０】実施例２における車両故障診断システムの構成図
【図２１】実施例２における車両故障診断システムの処理を示すフローチャート
【図２２】実施例２における外れ値の検出結果を示す図
【発明を実施するための形態】
【００２１】
以下図面に基づいて、本発明の実施形態を詳細に説明する。
本発明の実施形態では、与えられたデータセットの中から、データ密度が低い領域に属するデータを外れ値として見つける外れ値検出問題を解く。
最初に、クレジット取引を例にして、「データセット」について説明する。例えば、クレジット取引のデータセットとして、顧客の性別、顧客の年齢、取引金額の３種類の情報の組み合わせが単一のデータとして与えられる場合を考える。そして、ｘ１＝（男性、２５歳、１万円）、ｘ２＝（女性、３０歳、２万円）の２個のデータが、データセットとして与えられる場合を考える。
【００２２】
上記の例では、データの次元数が「３」かつデータ数が「２」のデータセットが与えられていることになる。データの次元は、変量とも呼ばれる（例えば、多変量解析とは、多次元のデータを解析することを意味する。）。また、データ数は、サンプル数とも呼ばれる。
データの各次元は、カテゴリ属性又は数値属性のいずれかである。上記の例では、顧客の性別がカテゴリ属性、顧客の年齢や取引金額が数値属性である。
【００２３】
また、データセットの他の例として、自動車の車載装置によって取得されるデータセットなどが考えられる。この場合、ある時刻に観測された車速、回転数、ＡＣＣ（Auto Cruse Control）のＯＮ／ＯＦＦなどが、各次元（各変量）となる。車速、回転数は数値属性、ＡＣＣのＯＮ／ＯＦＦはカテゴリ属性である。そして、複数の時刻に観測される複数のデータが、データセットとして与えられる。
【００２４】
以下では、データの次元数が１又は複数、かつデータ数が複数のデータセットから外れ値の検出を支援又は実行する外れ値検出装置について説明する。本発明の実施の形態における外れ値検出装置は、非線形のデータセットに対して、パラメータチューニング作業を行うことなく、実用的な時間内に外れ値の検出を支援又は実行することができる。
【００２５】
図１は、外れ値検出装置のハードウエア構成図である。尚、図１のハードウエア構成は一例であり、用途、目的に応じて様々な構成を採ることが可能である。
【００２６】
外れ値検出装置１は、制御部１１、記憶部１２、メディア入出力部１３、通信制御部１４、入力部１５、表示部１６、周辺機器Ｉ／Ｆ部１７等が、バス１８を介して接続される。
【００２７】
制御部１１は、ＣＰＵ（Central Processing Unit）、ＲＯＭ（Read Only
Memory）、ＲＡＭ（Random Access Memory）等によって構成される。
【００２８】
ＣＰＵは、記憶部１２、ＲＯＭ、記録媒体等に格納されるプログラムをＲＡＭ上のワークメモリ領域に呼び出して実行し、バス１８を介して接続された各装置を駆動制御し、外れ値検出装置１が行う後述する処理を実現する。
ＲＯＭは、不揮発性メモリであり、外れ値検出装置１のブートプログラムやＢＩＯＳ等のプログラム、データ等を恒久的に保持している。
ＲＡＭは、揮発性メモリであり、記憶部１２、ＲＯＭ、記録媒体等からロードしたプログラム、データ等を一時的に保持するとともに、制御部１１が各種処理を行う為に使用するワークエリアを備える。
【００２９】
記憶部１２は、ＨＤＤ（ハードディスクドライブ）であり、制御部１１が実行するプログラム、プログラム実行に必要なデータ、ＯＳ（オペレーティングシステム）等が格納される。プログラムに関しては、ＯＳ（オペレーティングシステム）に相当する制御プログラムや、後述する処理を外れ値検出装置１に実行させるためのアプリケーションプログラムが格納されている。
これらの各プログラムコードは、制御部１１により必要に応じて読み出されてＲＡＭに移され、ＣＰＵに読み出されて各種の手段として実行される。
【００３０】
メディア入出力部１３（ドライブ装置）は、データの入出力を行い、例えば、ＣＤドライブ（−ＲＯＭ、−Ｒ、−ＲＷ等）、ＤＶＤドライブ（−ＲＯＭ、−Ｒ、−ＲＷ等）等のメディア入出力装置を有する。
通信制御部１４は、通信制御装置、通信ポート等を有し、外れ値検出装置１とネットワーク間の通信を媒介する通信インタフェースであり、ネットワークを介して、他のコンピュータ間との通信制御を行う。ネットワークは、有線、無線を問わない。
【００３１】
入力部１５は、データの入力を行い、例えば、キーボード、マウス等のポインティングデバイス、テンキー等の入力装置を有する。
入力部１５を介して、外れ値検出装置１に対して、操作指示、動作指示、データ入力等を行うことができる。
表示部１６は、液晶パネル等のディスプレイ装置、ディスプレイ装置と連携して外れ値検出装置１のビデオ機能を実現するための論理回路等（ビデオアダプタ等）を有する。
【００３２】
周辺機器Ｉ／Ｆ（インタフェース）部１７は、外れ値検出装置１に周辺機器を接続させるためのポートであり、周辺機器Ｉ／Ｆ部１７を介して外れ値検出装置１は周辺機器とのデータの送受信を行う。周辺機器Ｉ／Ｆ部１７は、ＵＳＢやＩＥＥＥ１３９４やＲＳ−２３２Ｃ等で構成されており、通常複数の周辺機器Ｉ／Ｆを有する。周辺機器との接続形態は有線、無線を問わない。
バス１８は、各装置間の制御信号、データ信号等の授受を媒介する経路である。
【００３３】
以上、外れ値検出装置１のハードウエア構成について説明したが、外れ値検出装置１として実装される装置は、この例に限定されない。例えば、外れ値検出装置１は、自動車などの車載装置、家電などの制御装置、生産ラインの不良品を検出する検品装置などに、後述する処理を実現する為のプログラムをインストールすることによって、自動車、家電、生産ラインなどの一部として実装されることもある。また、例えば、外れ値検出装置１は、複数のコンピュータから構成されるサーバ装置として実装されることもある。
以下では、外れ値検出装置１が単一のコンピュータによって実装されるものとして説明する。
【００３４】
図２は、外れ値検出装置の処理の詳細を示すフローチャートである。以下では、必要に応じて図３〜図１３を参照し、データセットの一例に対する処理の詳細を説明する。
【００３５】
図２に示すように、外れ値検出装置１の制御部１１は、入力手段（メディア入出力部１３、通信制御部１４、入力部１５、周辺機器Ｉ／Ｆ部１７等）を介して、データセットを入力する（Ｓ１）。また、制御部１１は、記憶部１２にファイルとして記憶されているデータセットを入力しても良い。
【００３６】
図３は、データセットの変換処理を説明する図である。図３には、データセット２１が図示されている。データセット２１は、データの次元数が「２」、データ数が「１９」である。各次元は数値属性であり、取り得る値は、０〜７の整数値である。
【００３７】
制御部１１は、図３に示されるデータセット２１のように、正規化されたデータセットを入力する場合に限らず、生のデータセットを入力して正規化処理を行っても良い。例えば、制御部１１は、生のデータセットに対して様々な加工処理を施して所定の範囲の整数値とする。
生のデータセットに含まれる一部の次元（変量）が数値属性の場合、制御部１１は、細かく区切って離散化し、デジタル化する。制御部１１は、例えば、実数値を小数点第１位において四捨五入して整数値とし、コンピュータがｉｎｔ型として扱うことが可能な値に変換する。取り得る範囲が極端に狭い、または広い場合、制御部１１は、適当な係数をかけて想定する範囲に満遍なく収まるようにする。また、尺度が異なるデータが混ざっている場合、制御部１１は、平均０、分散１に標準化する。また、分布が極端に偏っている場合、制御部１１は、対数変換なども行う。
また、数値属性の次元（変量）の場合であっても、取り得る値が少ない場合、例えば０〜３の整数値しか取らない場合、制御部１１は、カテゴリ属性の次元（変量）として取り扱っても良い。また、カテゴリ属性の次元（変量）の場合であっても、取り得る値に何らかの距離の概念が導入できる場合、制御部１１は、数値属性の次元（変量）として取り扱っても良い。
【００３８】
図２の説明に戻る。次に、制御部１１は、各データを次元（変量）ごとにビット列に変換する（Ｓ２）。図３には、データｘ１に対するビット列２２ａ、データｘ２に対するビット列２２ｂが図示されている。例えば、データｘ１＝６に対するビット列２２ａは、（ｄ１，ｄ２，ｄ３）＝（１，１，０）である。また、例えば、データｘ２＝２に対するビット列２２ｂは、（ｅ１，ｅ２，ｅ３）＝（０，１，０）である。
【００３９】
次に、制御部１１は、数値属性のビット列群を最上位ビットから最下位ビットの順に並び替える（Ｓ３）。図３には、並び替え後ビット列２３が図示されている。例えば、（ｄ１，ｄ２，ｄ３）＝（１，１，０）のビット列２２ａ、及び（ｅ１，ｅ２，ｅ３）＝（０，１，０）のビット列２２ｂに対して、並び替え後ビット列２３は、（ｄ１，ｅ１，ｄ２，ｅ２，ｄ３，ｅ３）＝（１，０，１，１，０，０）である。
以下では、ｄ１とｅ１のように最も左端のビットを「最上位ビット」（ＭＳＢ：Most Significant Bit）、ｄ３とｅ３のように最も右端のビットを「最下位ビット」（ＬＳＢ：Least Significant Bit）とする。
【００４０】
尚、Ｓ３における並び替えの処理は、必ずしも必須ではない。Ｓ３における並び替えの処理は、全ての次元（変量）を同等に扱うことになるので、データセットの特性について事前に何らかの情報を持っている場合、並び替えを行わない方が良いこともある。例えば、ｘ１の次元（変量）は、データの特徴を良く表しており、ｘ２の次元（変量）は、ほとんど変化がなく、データの特徴をあまり表していないことが分かっている場合には、Ｓ３における並び替えの処理を行わず、両者を同等に扱わない方が良い。
Ｓ３における並び替えの処理は、データセットの特性について事前に何も情報を持っていない場合に有効である。
【００４１】
また、カテゴリ属性のビット列群は、数値属性のビット列群と区別し、カテゴリ属性のビット列が上位、数値属性のビット列が下位となるように並べることが望ましい。例えば、図３に示す数値属性のｘ１、ｘ２の他に、カテゴリ属性のｘ３を含むデータを考え、カテゴリ属性のｘ３を変換したビット列を（ｆ１，ｆ２，ｆ３）とする。この場合、制御部１１は、（ｆ１，ｆ２，ｆ３，ｄ１，ｅ１，ｄ２，ｅ２，ｄ３，ｅ３）の順に並び替えることが望ましい。
カテゴリ属性と数値属性を分けた理由は、一般にカテゴリ属性の取り得る値に対して距離の概念を導入することができず、数値属性と一緒に取り扱うことが困難だからである。
データセットの特性について事前に何も情報を持っていない場合、カテゴリ属性同士や数値属性同士は、どちらが上位になっても構わない。
【００４２】
図２の説明に戻る。次に、制御部１１は、観測領域Ｆとして二分決定グラフを構築する（Ｓ４）。制御部１１は、観測領域Ｆとして、二分決定グラフ（ＢＤＤ：Binary Decision Diagram）ではなく、カルノー図などを構築しても良い。二分決定グラフ及びカルノー図のいずれも、論理関数を表現するために使われるデータ構造の１つである。つまり、観測領域Ｆは、論理関数を表現できれば良い。
【００４３】
尚、後述するように、観測領域Ｆとして二分決定グラフを構築する場合、外れ値検出装置１は、データ数が増大しても、実用的な時間内に外れ値の検出を支援又は実行することができる。以下では、混乱を避ける為に、外れ値検出装置１が、観測領域Ｆとして二分決定グラフを構築する場合について説明する。また、外れ値検出装置１の処理を分かり易く説明する為に、カルノー図も例示する。
【００４４】
図４は、カルノー図を示す図である。
図４に示すカルノー図３０ａは、図３に示すビット列２２ａの（ｄ１，ｄ２，ｄ３）を縦、図３に示すビット列２２ｂの（ｅ１，ｅ２，ｅ３）を横に配置している。黒の正方形の１個分が、１個のデータに対応する。従って、図４に示すカルノー図３０ａには、１９個の黒の正方形が図示されている。
【００４５】
図５は、二分決定グラフを示す図である。図５に示す二分決定グラフ３１は、図３の並び替え後ビット列２３に基づいて構築されたものである。
二分決定グラフは、コンピュータにおいてポインタの配列で表現されるので、必要な記憶容量を減らすことができる。また、既約な順序付き二分決定グラフの場合、論理関数同士の演算がグラフのサイズにほぼ比例する程度の計算時間によって実行できる。グラフのサイズは、ノード数である。
図５に示す例では、楕円形状の３２などがノードである。図３に示す並び替え後ビット列２３の各ビットは、ブーリアン変数（「真」と「偽」のいずれかを取る変数）とみなすことができる。例えば、１番目のビットｄ１は、ノード３２ａに対応している。
順序付き二分決定グラフとは、（１）ノード同士に全順序関係が定義されている、（２）最上位ノードから定数ノードに至る全てのパスについて変数の出現順序が、全順序関係に矛盾しない、二分決定グラフである。ここで、図５に示す例では、３３が最上位ノード（ルートノード）、３４が定数ノードである。図５に示す例では、定数ノードは、「１」（「真」を意味する。）である。尚、最上位ノード及び定数ノードは特別なノードである為、通常のノードと符号を区別する。
既約な二分決定グラフとは、（１）冗長なノードを全て削除、（２）等価なノードを全て共有、という２つの簡約化規則がこれ以上適用できなくなるまで適用されている二分決定グラフである。
図５に示す二分決定グラフは、既約な順序付き二分決定グラフである。
【００４６】
図５に示す二分決定グラフは、実線によって示されるＴｈｅｎ枝、間隔が広い点線によって示されるＥｌｓｅ枝、「＊」（アスタリスク）を付した間隔が狭い点線によって示される否定Ｅｌｓｅ枝の３つを用いている。否定Ｅｌｓｅ枝を用いると、否定演算が短い時間によって実行できる。例えば、枝３５ａは、Ｅｌｓｅ枝である。
【００４７】
図２の説明に戻る。次に、制御部１１は、二分決定グラフの各ノードにおける最小項の数を算出する（Ｓ５）。最小項の数の算出処理は、図６、図７を参照して説明する。
【００４８】
図６は、最小項の数の算出処理を説明する図である。図７は、最小項の数の算出結果を示す図である。
最小項（Ｍｉｎｔｅｒｍ）とは、ブーリアン変数の集合が与えられたとき、全てのブーリアン変数のリテラルを含む積項である。例えば、ブーリアン変数の集合が（ａ、ｂ、ｃ）のとき、ａ¬ｂｃは最小項であり、ａ¬ｂは最小項ではない。尚、「¬ｂ」は、ｂの否定を意味する。
【００４９】
制御部１１は、ノードごとに、Ｐ：最上位ノードから辿って否定枝を偶数回通る場合の最小項の数、及び、Ｎ：最上位ノードから辿って否定枝を奇数回通る場合の最小項の数、を算出する。
最初に、制御部１１は、定数ノードの最小項の数を算出する。定数ノードのＰは２のｎ乗（ｎはブーリアン変数の数、すなわち、並び替え後ビット列２３のビット数）であり、Ｎは０である。図３に示す通り、並び替え後ビット列２３のビット数は「６」なので、定数ノードのＰ＝２の６乗＝６４となる。従って、図７に示す定数ノード３４については、Ｐ＝６４、Ｎ＝０となる。
【００５０】
次に、制御部１１は、深さ優先探索によって、定数ノード以外の各ノードの最小項の数を再帰的に算出する。
制御部１１は、図６に示すように、（ａ）Ｅｌｓｅ枝が否定枝ではない場合と、（ｂ）Ｅｌｓｅ枝が否定枝の場合に分けて、各ノードにおける最小項の数を算出する。
まず、図６（ａ）の場合について説明する。図６（ａ）では、ノード３２ｄが算出対象のノード、Ｔｈｅｎ枝によって接続された下位のノード３２ｂのＰの値がｔ_ｐ（既知）及びＮの値がｔ_ｎ（既知）、並びに、Ｅｌｓｅ枝によって接続された下位のノード３２ｃのＰの値がｅ_ｐ（既知）及びＮの値がｅ_ｎ（既知）である。このとき、制御部１１は、下位のノード３２ｂと３２ｃの算出結果を用いて、Ｐ＝ｔ_ｐ／２＋ｅ_ｐ／２、Ｎ＝ｔ_ｎ／２＋ｅ_ｎ／２の式によって、ノード３２ｄの最小項の数を算出する。
次に、図６（ｂ）の場合について説明する。図６（ｂ）では、ノード３２ｇが算出対象のノード、Ｔｈｅｎ枝によって接続された下位のノード３２ｅのＰの値がｔ_ｐ（既知）及びＮの値がｔ_ｎ（既知）、並びに、否定Ｅｌｓｅ枝によって接続された下位のノード３２ｆのＰの値がｅ_ｐ（既知）及びＮの値がｅ_ｎ（既知）である。このとき、制御部１１は、下位のノード３２ｅと３２ｆの算出結果を用いて、Ｐ＝ｔ_ｐ／２＋ｅ_ｎ／２、Ｎ＝ｔ_ｎ／２＋ｅ_ｐ／２の式によって、ノード３２ｇの最小項の数を算出する。
【００５１】
例えば、図７に示すノード３２ｈの場合、下位のノード（＝定数ノード３４）と接続されたＥｌｓｅ枝が否定枝であるから、図６（ｂ）の算出方法によって最小項の数を算出する。つまり、ノード３４については、Ｐ＝６４／２＋０／２＝３２、Ｎ＝６４／２＋０／２＝３２となる。
【００５２】
また、例えば、図７に示すノード３２ｉの場合、下位のノードと接続されたＥｌｓｅ枝が否定枝ではないことから、図６（ａ）の算出方法によって最小項の数を算出する。つまり、ノード３２ｉについては、Ｐ＝３２／２＋６４／２＝４８、Ｎ＝３２／２＋０／２＝１６となる。
【００５３】
図２の説明に戻る。次に、制御部１１は、二分決定グラフの各ノードにおける局所密度を算出する（Ｓ６）。局所密度の算出処理は、図８、図９を参照して説明する。
【００５４】
図８は、局所密度の算出処理を説明する図である。図９は、局所密度の算出結果を示す図である。尚、図９に示すＰ及びＮの数値の意味と、図７に示すＰ及びＮの数値の意味は異なることに留意する。
【００５５】
図８（ａ）は、図７のノード３２ｊのＰ接続の局所密度を、便宜的にカルノー図３０ｂによって示している。また、図８（ｂ）は、図７のノード３２ｋのＰ接続の局所密度を、便宜的にカルノー図３０ｃによって示している。
ここで、最上位ノードから辿って着目しているノードまでに否定枝を偶数回通るパスのことを、「Ｐ接続」という。また、最上位ノードから辿って着目しているノードまでに否定枝を奇数回通るパスのことを、「Ｎ接続」という。
【００５６】
まず、ノード３２ｊについて考える。
図７を参照すると分かるように、最上位ノード３３からノード３２ｊまでのパスは、枝３５ａ、枝３５ｂを順に通るパスのみである。
枝３５ａはＥｌｓｅ枝であり、ブーリアン変数ｄ１が「０」であることに対応する。同様に、枝３５ｂはＥｌｓｅ枝であり、ブーリアン変数ｅ１が「０」であることに対応する。それ以外のブーリアン変数ｄ２、ｅ２、ｄ３、ｅ３については、ドントケア（「ドントケア」とは、値が「０」でも「１」でも良いことを意味する。）となる。図８（ａ）に示す点線の矩形領域４１ａは、この領域を示しており、ｄ１が「０」、ｅ１が「０」、それ以外がドントケアの領域である。
更に、図８（ａ）に示すカルノー図３０ｂは、カルノー図３０ａにおける矩形領域４１ａのパターンを４個繰り返したものである。そして、ノード３２ｊのＰ接続の局所密度は、カルノー図３０ｂの全体密度と一致する。つまり、図９に示すように、ノード３２ｊのＰ接続の局所密度は、「０．２５」である。
【００５７】
次に、ノード３２ｋについて考える。
図７を参照すると分かるように、最上位ノード３３からノード３２ｋまでのパスは、枝３５ａ、枝３５ｂ、枝３５ｃ、枝３５ｄを順に通る第１のパスと、枝３５ａ、枝３５ｂ、枝３５ｅ、枝３５ｆを順に通る第２のパスの２つである。
第１のパスについては、ブーリアン変数ｄ１が「０」、ｅ１が「０」、ｄ２が「１」、ｅ２が「０」に対応する。それ以外のブーリアン変数ｄ３、ｅ３については、ドントケアとなる。図８（ｂ）に示す点線の矩形領域４１ｂは、この領域を示している。
また、第２のパスについては、ブーリアン変数ｄ１が「０」、ｅ１が「０」、ｄ２が「０」、ｅ２が「１」に対応する。それ以外のブーリアン変数ｄ３、ｅ３については、ドントケアとなる。図８（ｂ）に示す点線の矩形領域４１ｃは、この領域を示している。
更に、図８（ｂ）に示すカルノー図３０ｃは、カルノー図３０ａにおける矩形領域４１ｂ（又は４１ｃ）のパターンを１６個繰り返したものである。そして、ノード３２ｋのＰ接続の局所密度は、カルノー図３０ｃの全体密度と一致する。つまり、図９に示すように、ノード３２ｋのＰ接続の局所密度は、「０．２５」である。
【００５８】
本発明の実施の形態では、制御部１１は、Ｓ５において、二分決定グラフ３１の各ノードにおける最小項の数を算出している。従って、制御部１１は、ビット列のビット数をｎとしたとき、「二分決定グラフ３１の各ノードにおける最小項の数÷２のｎ乗」を各ノードにおけるＰ接続の局所密度として算出することができる。つまり、制御部１１は、各ノードにおける最小項の数を用いることによって、図８に示すカルノー図３０ｂ、３０ｃの構築処理を実行する必要はない。
例えば、ノード３２ｊのＰ接続の局所密度＝ノード３２ｊにおける最小項の数÷２のｎ乗＝１６／２の６乗＝０．２５である。また、例えば、ノード３２ｋのＰ接続の局所密度＝ノード３２ｋにおける最小項の数÷２のｎ乗＝１６／２の６乗＝０．２５である。他のノードについても同様である。
尚、各ノードのＮ接続の局所密度は、「１−各ノードのＰ接続の局所密度」である。
【００５９】
図２の説明に戻る。次に、制御部１１は、局所密度から単一データの密度換算値を引いた値を単一データ除外局所密度として算出する（Ｓ７）。
以下、単一データ除外局所密度を、「ＬＯＯ（Ｌｅａｖｅ−Ｏｎｅ−Ｏｕｔ）密度」と省略して記載する。ＬＯＯ密度の算出処理は、図１０を参照して説明する。
【００６０】
図１０は、ＬＯＯ密度の算出結果を示す図である。尚、図１０に示すＰ及びＮの数値の意味と、図７、図９に示すＰ及びＮの数値の意味は異なることに留意する。
【００６１】
ＬＯＯ密度は、「局所密度−単一データの密度換算値」である。また、次元数をＭ、局所密度に対応するノードのレベルをＬとしたとき、各ノードの密度換算値は、「｛２の（Ｌ×Ｍ）乗｝の逆数」と定義する。纏めると、ＬＯＯ密度＝局所密度−｛２の（Ｌ×Ｍ）乗｝の逆数、となる。
そして、制御部１１は、ノードごとにＬＯＯ密度を算出する。
【００６２】
ここで、レベルＬについて説明する。図１０に示すように、定数ノード３４を「レベル０」、「最下位ビット」（ＬＳＢ）であるｄ３、ｅ３に対応するノードを「レベル１」、次の階層のビットであるｄ２、ｅ２に対応するノードを「レベル２」、「最上位ビット」（ＭＳＢ）であるｄ１、ｅ１に対応するノードを「レベル３」とする。つまり、数値属性の次元（変量）を表すのに用いたビット列の長さＫとレベルＬの最大値が一致し、レベルＬは０〜Ｍの整数値を取る。
【００６３】
図１０を参照しながら、ＬＯＯ密度の算出例を説明する。
例えば、ノード３２ｊのＰ接続のＬＯＯ密度は、０．２５−１／（２の（２×２）乗）＝０．２５−１／１６＝３／１６≒０．１９となる。
また、例えば、ノード３２ｊのＮ接続のＬＯＯ密度は、０．７５−１／（２の（２×２）乗）＝０．７５−１／１６＝１１／１６≒０．６９となる。
また、例えば、ノード３２ｋのＰ接続のＬＯＯ密度は、０．２５−１／（２の（１×２）乗）＝０．２５−１／４＝０となる。
また、例えば、ノード３２ｋのＮ接続のＬＯＯ密度は、０．７５−１／（２の（１×２）乗）＝０．７５−１／４＝０．５となる。
尚、定数ノード３４については、ＬＯＯ密度＝ｍａｘ｛０，局所密度−｛２の（Ｌ×Ｍ）乗｝の逆数｝の式によって算出している。これは、ＬＯＯ密度が負の値になることを避ける為である。但し、このことは本質的なことではなく、ＬＯＯ密度が負の値になっても、本発明では特に問題はない。
【００６４】
図２の説明に戻る。次に、制御部１１は、ＬＯＯ密度に基づいて、各データの外れ度合を算出する（Ｓ８）。外れ度合の算出処理は、図１１〜図１３を参照して説明する。
【００６５】
図１１は、二分決定グラフにおける着目データを表すパスを示す図である。図１２は、カルノー図における着目データを表す領域を示す図である。図１３は、抽出されるＬＯＯ密度を説明する図である。
制御部１１は、データセットの中から１つずつ着目データを決定し、着目データごとに処理を実行する。以下では、着目データｘとして、（ｄ１，ｅ１，ｄ２，ｅ２，ｄ３，ｅ３）＝（１，０，０，１，１，０）の例を示す。
【００６６】
制御部１１は、二分決定グラフでの着目データｘを表すパスを探索し、レベル（階層）が変化するノードに係るＬＯＯ密度を抽出し、抽出されたＬＯＯ密度に基づいて、着目データｘの外れ度合を算出する。
【００６７】
図１１に示す例であれば、レベル（階層）が変化するノードは、ノード３２ａ、３２ｌ、３２ｍ、３４の４つである。
Ｐ接続のＬＯＯ密度を抽出するか、それとも、Ｎ接続のＬＯＯ密度を抽出するかについては、最上位ノードから辿って否定枝を通る回数によって決まる。つまり、制御部１１は、最上位ノードから辿って否定枝を偶数回通る場合にはＰ接続のＬＯＯ密度を抽出し、最上位ノードから辿って否定枝を奇数回通る場合にはＮ接続のＬＯＯ密度を抽出する。
制御部１１は、ノード３２ａについては、否定枝を１回通ることから、Ｎ接続のＬＯＯ密度「０．２８」を抽出する。また、制御部１１は、ノード３２ｌについても、否定枝を１回通ることから、Ｎ接続のＬＯＯ密度「０．３８」を抽出する。また、制御部１１は、ノード３２ｍについても、否定枝を１回通ることから、Ｎ接続のＬＯＯ密度「０．２５」を抽出する。また、制御部１１は、定数ノード３４については、否定枝を２回通ることから、Ｐ接続のＬＯＯ密度「０」を抽出する。
結局、制御部１１は、（０．２８、０．３８、０．２５、０）を抽出する。
【００６８】
図１３を参照しながら、抽出された各ＬＯＯ密度の意味について説明する。
図１３（ａ）に示すように、レベル０のＬＯＯ密度、すなわち定数ノード３４のＬＯＯ密度は、１個の単位領域（＝着目データｘ自身が占める領域）である矩形領域４１ｄを全体領域としたときに、着目データｘ自身を除外したときのデータ密度に相当する。
また、図１３（ｂ）に示すように、レベル１のＬＯＯ密度、すなわちノード３２ｍのＬＯＯ密度は、４個の単位領域である矩形領域４１ｅを全体領域としたときに、着目データｘ自身を除外したときのデータ密度に相当する。
また、図１３（ｃ）に示すように、レベル２のＬＯＯ密度、すなわちノード３２ｌのＬＯＯ密度は、１６個の単位領域である矩形領域４１ｆを全体領域としたときに、着目データｘ自身を除外したときのデータ密度に相当する。
また、図１３（ｄ）に示すように、レベル３のＬＯＯ密度、すなわちノード３２ａのＬＯＯ密度は、６４個の単位領域である矩形領域４１ｇを全体領域としたときに、着目データｘ自身を除外したときのデータ密度に相当する。
このように、抽出されたＬＯＯ密度は、階層局所密度（ＨＬＤ：Hierarchical Local Densities）と言える。
【００６９】
制御部１１は、例えば、抽出されたＬＯＯ密度（階層局所密度）の最大値を、着目データの外れ度合とする。図１１に示す例では、制御部１１は、（０．２８、０．３８、０．２５、０）の最大値「０．３８」を、着目データｘの外れ度合とする。
また、制御部１１は、抽出されたＬＯＯ密度の最大値に代えて、抽出されたＬＯＯ密度の平均値や中央値などを、着目データの外れ度合としても良い。
【００７０】
また、制御部１１は、抽出されたＬＯＯ密度の全部に基づいて外れ度合を算出するのではなく、抽出されたＬＯＯ密度の一部に基づいて外れ度合を算出しても良い。
例えば、制御部１１は、抽出されたＬＯＯ密度の中から、高いレベル（階層）のノードに係るＬＯＯ密度に基づいて、外れ度合を算出しても良い。図１１に示す例であれば、制御部１１は、「レベル３」、「レベル２」のノードに係るＬＯＯ密度（０．２８、０．３８）に基づいて外れ度合を算出しても良い。この場合も、制御部１１は、最大値、平均値、中央値などを、着目データの外れ度合とすることができる。
【００７１】
前述の説明では、観測領域を２分決定グラフとして構築したが、観測領域をカルノー図やその他のデータ構造によって構築した場合も、本発明を適用することが可能である。
制御部１１は、データセットに含まれるデータの中から着目データを１つずつ決定し、観測領域から着目データに相当する領域を除去したときの着目データの周辺のデータ密度に基づいて、着目データの外れ度合を算出すれば良い。ＬＯＯ密度は、観測領域から着目データに相当する領域を除去したときの着目データの周辺のデータ密度の１例である。
【００７２】
図２の説明に戻る。次に、制御部１１は、Ｓ８によって算出された外れ度合と、予め定められた閾値を比較することによって、外れ値を検出する（Ｓ９）。尚、Ｓ９は必須ではない。例えば、制御部１１は、出力手段（メディア入出力部１３、通信制御部１４、表示部１６、周辺機器Ｉ／Ｆ部１７等）を介して、Ｓ８によって算出された外れ度合の一覧を出力しても良い。そして、ユーザが、外れ度合の一覧を参照して、外れ値を検出しても良い。
【００７３】
図２に示す処理の中で最も計算負荷が高い処理は、Ｓ４の二分決定グラフの構築処理である。データセットのデータ数をＮ、二次元グラフのノード数をＤとすると、二分決定グラフの構築処理の計算量のオーダーは、О（Ｎ×Ｄ）である。
ところで、データセットの次元数が小さい場合、ノード数Ｄはあまり大きくならないことが多い。そこで、与えられたデータセットの次元数が大きい場合、次元縮約の手法を用いて次元数を小さくしても良い。適切な次元縮約を行えば、結果に影響を与えることなく、次元数を小さくすることができる。また、数値属性のデータを丸めて、ビット数を制限することによって、ノード数Ｄを小さくすることもできる。
従って、Ｓ４の二分決定グラフの構築処理を行う前に、適切な前処理を行うことによって、Ｄ≪Ｎとみなすことができる。つまり、計算量のオーダーは、О（Ｎの１乗）とみなすことができる。
【００７４】
また、図２の各ステップを見れば分かるように、ユーザがチューニングすべきパラメータは、Ｓ９の閾値のみである。ここで、Ｓ９の閾値は、外れ値か否かを判定する為のパラメータであって、外れ度合を算出する為のパラメータではない。つまり、外れ値検出装置１は、パラメータチューニング作業を行わなくても、外れ度合を算出することができる。
そして、Ｓ９の閾値を変更しても、Ｓ１〜Ｓ８の処理を再度実行する必要はなく、Ｓ９の処理の計算負荷は無視できる程度に小さいことから、外れ値検出装置１は、実用的な時間内に外れ値の検出を支援又は実行することができる。
【００７５】
以上、本発明の実施の形態では、外れ値検出装置１が、データセットに含まれる各データを次元ごとにビット列に変換し、ビット列に基づいて、データセットの観測領域を構築する。次に、外れ値検出装置１が、データセットに含まれるデータの中から着目データを１つずつ決定し、観測領域から着目データに相当する領域を除去したときの着目データの周辺のデータ密度に基づいて、着目データの外れ度合を算出する。
これによって、非線形のデータセットに対して、パラメータチューニング作業を行うことなく、実用的な時間内に外れ値の検出を支援又は実行することができる。
【実施例１】
【００７６】
以下では、図１４〜図１９を参照しながら、本発明の実施例１及び比較例について説明する。
図１４は、実施例１及び比較例に用いたデータセットを示す図である。図１４に示すデータセットは、２次元空間において、夜空の月（Moon）と星（Star）の光を模式的にプロットしたものである。以下では、図１４に示すデータセットを、MoonStarデータセットと呼ぶ。MoonStarデータセットの性質は、以下の通りである。
・人工的に発生させたデータ
・次元数Ｍ＝２
・データの９５％は三日月形状の領域内に分布し、残り５％はランダムに分布
・データ数Ｎ＝１０００、５０００
図１４（ａ）は、データ数Ｎ＝１０００のデータセットであり、MoonStar1000と呼ぶ。図１４（ｂ）は、データ数Ｎ＝５０００のデータセットであり、MoonStar5000と呼ぶ。いずれも、「○」が各データを示している。
【００７７】
判定精度を適切に比較できるように、後述する通り、いずれの例においても、データセットの５％を外れ値（Star）と判定した。また、計算時間も適切に比較できるように、全て同じコンピュータによって実行した。
【００７８】
実施例１では、外れ値検出装置１によって外れ度合を算出し、値の小さかった５％（Ｓ９の閾値）を外れ値と判定した。
比較例１では、ＯＣ−ＳＶＭ（One−Class Support Vector Machine）において、非線形写像を決めるカーネルパラメータγを「０．５」、外れ値の割合を指定するパラメータｖを「０．０５」とした。
比較例２では、ＯＣ−ＳＶＭにおいて、非線形写像を決めるカーネルパラメータγを「２」、外れ値の割合を指定するパラメータｖを「０．０５」とした。
比較例３では、ＬＯＦ（Local Outlier Factor）において、パラメータｋを「１０」とし、値の大きかった５％を外れ値と判定した。
比較例４では、ＬＯＦにおいて、パラメータｋを「１００」とし、値の大きかった５％を外れ値と判定した。
尚、ＯＣ−ＳＶＭの計算では、いずれも、統計計算言語Ｒのe1071ライブラリに含まれるsvm関数を使用した。また、ＬＯＦの計算では、いずれも、統計計算言語Ｒのdprepライブラリに含まれるlofactor関数を使用した。
【００７９】
図１５は、実施例１における外れ値の検出結果を示す図である。図１５（ａ）はMoonStar1000、図１５（ｂ）はMoonStar5000の結果である。いずれも、「×」が外れ値（Star）として検出されたデータ、「○」がMoonと判定されたデータを示している。尚、「×」（外れ値）の視認性を上げる為、「○」の色を淡いグレーによって図示している。以下、図１６〜図１９も同様である。
【００８０】
以下に示す表１、表２は、それぞれ、実施例１におけるMoonStar1000、MoonStar5000の判別結果を示している。
【００８１】
【表１】
【００８２】
【表２】
【００８３】
ここで、４つのマスのうち、左上のマスは、「Moon」を「Moon」と検出した数を示している。右上のマスは、「Moon」を「Star」と検出した数を示している。左下のマスは、「Star」を「Moon」と検出した数を示している。右下のマスは、「Star」を「Star」と検出した数を示している。左上と右下の合計が、正しく検出した数である。左下と右上の合計が、誤って検出した数である。以下、表３〜表１０も同様である。
【００８４】
実施例１では、MoonStar1000に対して計算時間が０．０３秒、MoonStar5000に対して計算時間が０．１７秒であった。つまり、データ数が５倍の増加に対して、計算時間の増加率は約５．７倍であることから、データ数Ｎに対して、実施例１の計算時間のオーダーはО（Ｎの１乗）と言える。
【００８５】
図１６は、比較例１における外れ値の検出結果を示す図である。また、以下に示す表３、表４は、それぞれ、比較例１におけるMoonStar1000、MoonStar5000の判別結果を示している。
【００８６】
【表３】
【００８７】
【表４】
【００８８】
比較例１では、MoonStar1000に対して計算時間が０．０７秒、MoonStar5000に対して計算時間が１．３０秒であった。つまり、データ数が５倍の増加に対して、計算時間は約１８．６倍の増加であることから、実施例１と比較すると、明らかに、データ数の増加に対する計算時間の増加率が高い。
【００８９】
図１７は、比較例２における外れ値の検出結果を示す図である。また、以下に示す表５、表６は、それぞれ、比較例２におけるMoonStar1000、MoonStar5000の判別結果を示している。
【００９０】
【表５】
【００９１】
【表６】
【００９２】
比較例２では、MoonStar1000に対して計算時間が０．１１秒、MoonStar5000に対して計算時間が１．６９秒であった。つまり、データ数が５倍の増加に対して、計算時間は約１５．４倍の増加であることから、実施例１と比較すると、明らかに、データ数の増加に対する計算時間の増加率が高い。
【００９３】
図１８は、比較例３における外れ値の検出結果を示す図である。また、以下に示す表７、表８は、それぞれ、比較例３におけるMoonStar1000、MoonStar5000の判別結果を示している。
【００９４】
【表７】
【００９５】
【表８】
【００９６】
比較例３では、MoonStar1000に対して計算時間が２．０５秒、MoonStar5000に対して計算時間が３４．９５秒であった。つまり、データ数が５倍の増加に対して、計算時間は約１７．０倍の増加であることから、実施例１と比較すると、明らかに、データ数の増加に対する計算時間の増加率が高い。
【００９７】
図１９は、比較例４における外れ値の検出結果を示す図である。また、以下に示す表９、表１０は、それぞれ、比較例４におけるMoonStar1000、MoonStar5000の判別結果を示している。
【００９８】
【表９】
【００９９】
【表１０】
【０１００】
比較例４では、MoonStar1000に対して計算時間が６．３８秒、MoonStar5000に対して計算時間が１５０．４７秒であった。つまり、データ数が５倍の増加に対して、計算時間は約２３．６倍の増加であることから、実施例１と比較すると、明らかに、データ数の増加に対する計算時間の増加率が高い。
【０１０１】
以上から、計算時間は、ＯＣ−ＳＶＭやＬＯＦよりも、本発明の外れ値検出装置１の方が優位であることが分かった。
以下では、計算精度についても、本発明の外れ値検出装置１の方が、ＯＣ−ＳＶＭやＬＯＦよりも優位であることについて説明する。
【０１０２】
実施例１と比較例１〜４の計算精度を比較する為、以下に示す表１１では、実施例１と比較例１〜４のＡＵＣ（area under the ＲＯＣ curve）を示している。ここで、ＲＯＣは、receiver operating characteristic（受診者操作特性）の略である。ＡＵＣは０〜１の値を取り、１に近い程、精度が良いことを示している。
【０１０３】
【表１１】
【０１０４】
表１１に示すように、本発明では、MoonStar1000とMoonStar5000の両方ともＡＵＣが０．９以上であり、安定して高い精度を達成している。これに対して、ＯＣ−ＳＶＭでは、MoonStar1000とMoonStar5000の両方ともＡＵＣが０．９以下であり、十分な精度が達成できていない。また、ＬＯＦについては、パラメータ次第で結果が大きく左右されており、パラメータチューニング作業が不可欠であることが分かる。
【実施例２】
【０１０５】
以下では、図２０〜図２２を参照しながら、本発明の実施例２について説明する。実施例２は、外れ値検出装置１を車両故障診断システムに適用する例である。
【０１０６】
図２０は、実施例２における車両故障診断システムの構成図である。図２０に示すように、車両故障診断システム１００は、故障診断の対象となる車両システム１０１、データ収集装置１０２、及び外れ値検出装置１によって構成される。
【０１０７】
車両システム１０１は、自動車等の車両に搭載されるシステムである。車両システム１０１は、複数のＥＣＵ（Electronic Control Unit：電子制御装置）、複数のセンサ、複数のアクチュエータ等が車載ネットワークを介して接続されている。
【０１０８】
データ収集装置１０２は、走行中の車両データを収集する装置である。データ収集装置１０２は、車載ネットワークに流れる信号、各コンポーネント（ＥＣＵ、センサ、アクチュエータ等）の状態値等を車両データとして収集する。そして、データ収集装置１０２は、無線又は有線によって接続される外れ値検出装置１に車両データを送信する。
【０１０９】
データ収集装置１０２は、例えば、車両システム１０１の内部に設置されても良いし、外付け装置として設置されても良い。また、データ収集装置１０２は、例えば、車両システム１０１から物理的に離れた場所に設置されるコンピュータ（外れ値検出装置１を含む。）でも良い。データ収集装置１０２が車両システム１０１から物理的に離れた場所に設置される場合、車両システム１０１は、無線通信によってデータ収集装置１０２に車両データを送信する。
【０１１０】
外れ値検出装置１は、データ収集装置１０２によって収集される車両データから外れ値を検出する。これに対して、車両の故障診断を行う専門家は、検出される外れ値を詳細に確認し、車両に異常が発生しているか否かを確認する。
【０１１１】
図２１は、実施例２における車両故障診断システムの処理を示すフローチャートである。図２１に示すように、データ収集装置１０２は、車両システム１０１から、走行中の車両データを収集する（Ｓ１１）。
【０１１２】
次に、外れ値検出装置１は、前述の図２に示すフローチャートに従って、データ収集装置１０２によって収集される車両データから外れ値を検出する（Ｓ１２）。
【０１１３】
車両の故障診断を行う専門家は、外れ値検出装置１によって検出される外れ値を詳細に確認する。対処が必要な異常が発生している場合（Ｓ１３のＹ）、専門家は運転者に通知し、修理を促す（Ｓ１４）。又は、外れ値検出装置１が無線通信によって車両システム１０１に異常がある旨のメッセージを送信し、車両システム１０１が出力装置（表示装置や音声出力装置等）によって警報を出力しても良い。
【０１１４】
図２２は、実施例２における外れ値の検出結果を示す図である。図２２は、アクセル操作量、エンジン回転数、変速位置の３次元（３変量）のデータセットに対して、外れ値検出装置１が外れ値の検出を行った結果を示している。
【０１１５】
アクセル操作量及びエンジン回転数は、数値属性の変量である。変速位置は、「Ｌｏｗ」、「２ｎｄ」、「３ｒｄ」の３つの値を取り得ることから、カテゴリ属性の変量とも言えるし、数値属性の変量とも言える。
【０１１６】
図２２では、「×」が外れ値として検出されたデータ、「○」が外れ値ではないと判定されたデータを示している。図２２に示す例では、変速位置が「Ｌｏｗ」のとき、１つの外れ値が検出されている。これは、「アクセル操作量に対してエンジンの吹け上がりが悪い」という異常を示すものである。このように、本発明の外れ値検出装置１を車両故障診断システム１００に適用すれば、車両の故障診断を精度良く行うことができる。
【０１１７】
以上、添付図面を参照しながら、本発明に係る外れ値検出装置等の好適な実施形態について説明したが、本発明はかかる例に限定されない。当業者であれば、本願で開示した技術的思想の範疇内において、各種の変更例又は修正例に想到し得ることは明らかであり、それらについても当然に本発明の技術的範囲に属するものと了解される。
【符号の説明】
【０１１８】
１………外れ値検出装置
２１………データセット
２２ａ、２２ｂ………ビット列
２３………並び替え後ビット列
３０ａ〜３０ｃ………カルノー図
３１………二分決定グラフ
３２ａ〜３２ｍ………ノード
３３………最上位ノード
３４………定数ノード
３５ａ〜３５ｆ………枝
４１ａ〜４１ｇ………矩形領域
【特許請求の範囲】
【請求項１】
データの次元数が１又は複数、かつデータ数が複数のデータセットから外れ値の検出を支援又は実行する外れ値検出装置であって、
前記データセットに含まれる各データを次元ごとにビット列に変換し、前記ビット列に基づいて、前記データセットの観測領域を構築する構築手段と、
前記データセットに含まれるデータの中から着目データを１つずつ決定し、前記観測領域から前記着目データに相当する領域を除去したときの前記着目データの周辺のデータ密度に基づいて、前記着目データの外れ度合を算出する算出手段と、
を具備する外れ値検出装置。
【請求項２】
前記構築手段は、前記観測領域を二分決定グラフとして構築し、
前記算出手段は、各ノードにおける局所密度から単一データの密度換算値を引いた値を単一データ除外局所密度とし、更に、前記単一データ除外局所密度に基づいて、前記着目データの外れ度合を算出する
請求項１に記載の外れ値検出装置。
【請求項３】
前記構築手段は、数値属性の次元に係る前記ビット列群を最上位ビットから最下位ビットの順に並び変えて、前記二分決定グラフを階層的に構築し、
前記算出手段は、前記二分決定グラフでの前記着目データを表すパスを探索し、階層が変化するノードに係る前記単一データ除外局所密度に基づいて、前記着目データの外れ度合を算出する
請求項２に記載の外れ値検出装置。
【請求項４】
前記算出手段は、階層が変化するノードに係る前記単一データ除外局所密度の一部若しくは全部の最大値、中央値又は平均値を、前記着目データの外れ度合とする
請求項３に記載の外れ値検出装置。
【請求項５】
前記外れ度合と閾値を比較することによって、外れ値を検出する検出手段、
を更に具備する請求項１乃至請求項４のいずれかに記載の外れ値検出装置。
【請求項６】
データの次元数が１又は複数、かつデータ数が複数のデータセットから外れ値の検出を支援又は実行する外れ値検出方法であって、
前記データセットに含まれる各データを次元ごとにビット列に変換し、前記ビット列に基づいて、前記データセットの観測領域を構築する構築ステップと、
前記データセットに含まれるデータの中から着目データを決定し、前記観測領域において、前記着目データ自身が占める領域を除く前記着目データ周辺のデータ密度である着目データ除去局所密度を算出する算出ステップと、
を含む外れ値検出方法。
【請求項７】
コンピュータを、
データの次元数が１又は複数、かつデータ数が複数のデータセットから外れ値の検出を支援又は実行し、
前記データセットに含まれる各データを次元ごとにビット列に変換し、前記ビット列に基づいて、前記データセットの観測領域を構築する構築手段と、
前記データセットに含まれるデータの中から着目データを決定し、前記観測領域において、前記着目データ自身が占める領域を除く前記着目データ周辺のデータ密度である着目データ除去局所密度を算出する算出手段と、
を具備する外れ値検出装置として機能させる為のプログラム。
【請求項８】
データの次元数が１又は複数、かつデータ数が複数のデータセットから外れ値の検出を支援又は実行する外れ値検出装置と、車両データを収集するデータ収集装置と、を含む車両故障診断システムであって、
前記外れ値検出装置は、
前記データ収集装置によって収集される前記車両データを前記データセットとし、前記データセットに含まれる各データを次元ごとにビット列に変換し、前記ビット列に基づいて、前記データセットの観測領域を構築する構築手段と、
前記データセットに含まれるデータの中から着目データを１つずつ決定し、前記観測領域から前記着目データに相当する領域を除去したときの前記着目データの周辺のデータ密度に基づいて、前記着目データの外れ度合を算出する算出手段と、
前記外れ度合と閾値を比較することによって、外れ値を検出する検出手段と、
を具備する車両故障診断システム。
【請求項１】
データの次元数が１又は複数、かつデータ数が複数のデータセットから外れ値の検出を支援又は実行する外れ値検出装置であって、
前記データセットに含まれる各データを次元ごとにビット列に変換し、前記ビット列に基づいて、前記データセットの観測領域を構築する構築手段と、
前記データセットに含まれるデータの中から着目データを１つずつ決定し、前記観測領域から前記着目データに相当する領域を除去したときの前記着目データの周辺のデータ密度に基づいて、前記着目データの外れ度合を算出する算出手段と、
を具備する外れ値検出装置。
【請求項２】
前記構築手段は、前記観測領域を二分決定グラフとして構築し、
前記算出手段は、各ノードにおける局所密度から単一データの密度換算値を引いた値を単一データ除外局所密度とし、更に、前記単一データ除外局所密度に基づいて、前記着目データの外れ度合を算出する
請求項１に記載の外れ値検出装置。
【請求項３】
前記構築手段は、数値属性の次元に係る前記ビット列群を最上位ビットから最下位ビットの順に並び変えて、前記二分決定グラフを階層的に構築し、
前記算出手段は、前記二分決定グラフでの前記着目データを表すパスを探索し、階層が変化するノードに係る前記単一データ除外局所密度に基づいて、前記着目データの外れ度合を算出する
請求項２に記載の外れ値検出装置。
【請求項４】
前記算出手段は、階層が変化するノードに係る前記単一データ除外局所密度の一部若しくは全部の最大値、中央値又は平均値を、前記着目データの外れ度合とする
請求項３に記載の外れ値検出装置。
【請求項５】
前記外れ度合と閾値を比較することによって、外れ値を検出する検出手段、
を更に具備する請求項１乃至請求項４のいずれかに記載の外れ値検出装置。
【請求項６】
データの次元数が１又は複数、かつデータ数が複数のデータセットから外れ値の検出を支援又は実行する外れ値検出方法であって、
前記データセットに含まれる各データを次元ごとにビット列に変換し、前記ビット列に基づいて、前記データセットの観測領域を構築する構築ステップと、
前記データセットに含まれるデータの中から着目データを決定し、前記観測領域において、前記着目データ自身が占める領域を除く前記着目データ周辺のデータ密度である着目データ除去局所密度を算出する算出ステップと、
を含む外れ値検出方法。
【請求項７】
コンピュータを、
データの次元数が１又は複数、かつデータ数が複数のデータセットから外れ値の検出を支援又は実行し、
前記データセットに含まれる各データを次元ごとにビット列に変換し、前記ビット列に基づいて、前記データセットの観測領域を構築する構築手段と、
前記データセットに含まれるデータの中から着目データを決定し、前記観測領域において、前記着目データ自身が占める領域を除く前記着目データ周辺のデータ密度である着目データ除去局所密度を算出する算出手段と、
を具備する外れ値検出装置として機能させる為のプログラム。
【請求項８】
データの次元数が１又は複数、かつデータ数が複数のデータセットから外れ値の検出を支援又は実行する外れ値検出装置と、車両データを収集するデータ収集装置と、を含む車両故障診断システムであって、
前記外れ値検出装置は、
前記データ収集装置によって収集される前記車両データを前記データセットとし、前記データセットに含まれる各データを次元ごとにビット列に変換し、前記ビット列に基づいて、前記データセットの観測領域を構築する構築手段と、
前記データセットに含まれるデータの中から着目データを１つずつ決定し、前記観測領域から前記着目データに相当する領域を除去したときの前記着目データの周辺のデータ密度に基づいて、前記着目データの外れ度合を算出する算出手段と、
前記外れ度合と閾値を比較することによって、外れ値を検出する検出手段と、
を具備する車両故障診断システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２０】
【図２１】
【図２２】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２０】
【図２１】
【図２２】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【公開番号】特開２０１２−２５６３１１（Ｐ２０１２−２５６３１１Ａ）
【公開日】平成２４年１２月２７日（２０１２．１２．２７）
【国際特許分類】
【出願番号】特願２０１２−３２７２（Ｐ２０１２−３２７２）
【出願日】平成２４年１月１１日（２０１２．１．１１）
【出願人】（０００００３６０９）株式会社豊田中央研究所 (4,200)
【Ｆターム（参考）】
【公開日】平成２４年１２月２７日（２０１２．１２．２７）
【国際特許分類】
【出願日】平成２４年１月１１日（２０１２．１．１１）
【出願人】（０００００３６０９）株式会社豊田中央研究所 (4,200)
【Ｆターム（参考）】
[ Back to top ]