(57)【要約】【課題】  理解可能であって更に構築のための計算量および計算時間を短縮させることが可能な多変数テスト関数を生成すること。【解決手段】  本発明に係る多変数テスト関数生成システム１は、複数要素の要素データを有する入力データを複数のクラスに分類するための多変数テスト関数を生成するシステムである。多変数テスト関数生成システム１は、訓練用データを記録する訓練用データ記録手段２と、訓練用データに基づいて分類データの修正を行い、修正された分類データに基づいて多変数テスト関数を生成する多変数テスト関数生成手段３と、生成された多変数テスト関数を記録する多変数テスト関数記録手段４とを備えている。【選択図】  図１
2007213442.tif 000002
【特許請求の範囲】
【請求項１】
複数要素の要素データを有する複数の入力データを複数のクラスに分類するための多変数テスト関数を生成する多変数テスト関数生成装置であって、
予め要素データと分類されるべきクラスとが既知である入力データからなる訓練用データを取得する訓練用データ取得手段と、
前記要素データに対応するデータ情報と前記クラスを示すクラス情報とを有する複数の分類データを記録する分類データ記録手段と、
前記要素データの要素数に基づいて当該要素数に対応する複数次元の特徴空間を構成し、前記訓練用データの要素データの値を前記特徴空間の空間座標として判断するとともに、前記分類データ記録手段に記録される前記分類データのデータ情報の値を前記特徴空間の空間座標として判断し、前記訓練用データの空間座標と前記分類データの空間座標との距離が最小となる分類データを求める最近傍分類データ検出手段と、
該最近傍分類データ検出手段により求められた分類データのクラス情報と前記訓練用データのクラスとが同一クラスであるか否かを判断するクラス判断手段と、
該クラス判断手段により前記分類データのクラス情報と前記訓練用データのクラスとが異なるクラスであると判断された場合に、前記分類データ記録手段に記録される当該分類データのデータ情報を前記要素データの空間座標から遠ざかるように修正するとともに、前記クラス判断手段により前記訓練用データと同一クラスであると判断される他の分類データを前記最近傍分類データ検出手段により検出させ、前記分類データ記録手段に記録される当該他の分類データのデータ情報を前記要素データの空間座標に近づくように修正する分類データ修正手段と、
前記最近傍分類データ検出手段により検出された最近傍となる前記分類データのクラス情報が前記クラス判断手段により前記訓練用データのクラスと同一であると判断された場合に値が減少する使用確率変数を、前記訓練用データ毎に付与する使用確率変更手段と、
前記分類データ修正手段により修正がなされた分類データのデータ情報とクラス情報とに基づいて前記多変数テスト関数を生成するテスト関数生成手段と
を有し、
前記最近傍分類データ検出手段は、前記使用確率変数の値が所定値以上を示す前記訓練用データのみを用いて前記分類データの検出を行うこと
を特徴とする多変数テスト関数生成装置。
【請求項２】
複数要素の要素データを有する複数の入力データを複数のクラスに分類するための多変数テスト関数を生成する多変数テスト関数生成装置であって、
予め要素データと分類されるべきクラスとが既知である入力データからなる訓練用データを取得する訓練用データ取得手段と、
前記要素データに対応するデータ情報と前記クラスを示すクラス情報とを有する複数の分類データを記録する分類データ記録手段と、
前記要素データの要素数に基づいて当該要素数に対応する複数次元の特徴空間を構成し、前記訓練用データの要素データの値を前記特徴空間の空間座標として判断するとともに、前記分類データ記録手段に記録される前記分類データのデータ情報の値を前記特徴空間の空間座標として判断し、前記訓練用データの空間座標と前記分類データの空間座標との距離が最小となる分類データを求める最近傍分類データ検出手段と、
該最近傍分類データ検出手段により求められた分類データのクラス情報と前記訓練用データのクラスとが同一クラスであるか否かを判断するクラス判断手段と、
該クラス判断手段により前記分類データのクラス情報と前記訓練用データのクラスとが同一クラスであると判断された場合に、前記分類データ記録手段に記録される当該分類データのデータ情報を前記要素データの空間座標に近づくように修正する分類データ修正手段と、
前記最近傍分類データ検出手段により検出された最近傍となる前記分類データのクラス情報が前記クラス判断手段により前記訓練用データのクラスと同一であると判断された場合に値が減少する使用確率変数を、前記訓練用データ毎に付与する使用確率変更手段と、
前記分類データ修正手段により修正がなされた分類データのデータ情報とクラス情報とに基づいて前記多変数テスト関数を生成するテスト関数生成手段と
を有し、
前記最近傍分類データ検出手段は、前記使用確率変数の値が所定値以上を示す前記訓練用データのみを用いて前記分類データの検出を行うこと
を特徴とする多変数テスト関数生成装置。
【請求項３】
複数要素の要素データを有する入力データを複数のクラスに分類するための多変数テスト関数を生成する多変数テスト関数生成システムであって、
予め要素データと分類されるべきクラスとが既知である入力データを訓練用データとして記録する訓練用データ記録手段と、
前記多変数テスト関数は、前記要素データに対応するデータ情報と前記クラスを示すクラス情報とを有する複数の分類データからなり、前記要素データの要素数に基づいて当該要素数に対応する複数次元の特徴空間を構成し、前記訓練用データの要素データの値を前記特徴空間の空間座標として判断するとともに、前記分類データのデータ情報の値を前記特徴空間の空間座標として判断することによって、前記訓練用データの空間座標までの距離が最小となる最近傍の分類データを求め、当該訓練用データと求められた最近傍の分類データとが同一のクラスとなるように前記分類データの空間位置を修正することにより前記分類データのデータ情報の修正を行い、修正がなされた分類データのデータ情報とクラス情報とに基づいて前記多変数テスト関数を生成する多変数テスト関数生成手段と、
生成された多変数テスト関数を記録する多変数テスト関数記録手段と
を備え、
前記多変数テスト関数生成手段は、最近傍となる前記分類データのクラス情報が前記訓練用データのクラスと同一であった場合に値が減少する使用確率変数を前記訓練用データ毎に付与し、前記使用確率変数が所定値以上を示す前記訓練用データを用いて前記分類データのデータ情報の修正処理を行う
ことを特徴とする多変数テスト関数生成システム
【請求項４】
前記多変数テスト関数生成手段は、
前記訓練用データの要素データにおける空間座標から最近傍となる分類データのクラス情報が前記訓練用データのクラスと異なる場合に、当該分類データのデータ情報を前記要素データの空間座標から遠ざかるように修正し、
さらに前記訓練用データと同一クラスのクラス情報を有する分類データのうち、前記要素データの空間座標に最近傍となる他の分類データを求めて、当該他の分類データのデータ情報を前記要素データの空間座標に近づくように修正する
ことを特徴とする請求項３に記載の多変数テスト関数生成システム。
【請求項５】
前記多変数テスト関数生成手段は、
前記訓練用データの要素データにおける空間座標から最近傍となる分類データのクラス情報が前記訓練用データのクラスと同一の場合に、当該分類データのデータ情報を前記要素データの空間座標に近づくように修正する
ことを特徴とする請求項３に記載の多変数テスト関数生成システム。
【請求項６】
複数要素の要素データを有する複数の入力データを複数のクラスに分類するための多変数テスト関数を生成する多変数テスト関数生成方法であって、
訓練用データ取得手段が、予め要素データと分類されるべきクラスとが既知である入力データからなる訓練用データを取得する訓練用データ取得ステップと、
最近傍分類データ検出手段が、前記訓練用データ取得手段により取得された前記要素データの要素数に基づいて、当該要素数に対応する複数次元の特徴空間を構成し、前記訓練用データの要素データの値を前記特徴空間の空間座標として判断するとともに、前記要素データに対応するデータ情報と前記クラスを示すクラス情報とを有する複数の分類データを、当該分類データのデータ情報の値に基づいて前記特徴空間の空間座標として判断し、前記訓練用データの空間座標と前記分類データの空間座標との距離が最小となる分類データを求める最近傍分類データ検出ステップと、
クラス判断手段が、最近傍分類データ検出手段により求められた分類データのクラス情報と前記訓練用データのクラスとが同一クラスであるか否かを判断するクラス判断ステップと、
前記クラス判断手段により前記分類データのクラス情報と前記訓練用データのクラスとが異なるクラスであると判断された場合に、分類データ修正手段が当該分類データのデータ情報を前記要素データの空間座標から遠ざかるように修正するとともに、前記クラス判断手段により前記訓練用データと同一クラスであると判断される他の分類データを前記最近傍分類データ検出手段により検出させ、当該他の分類データのデータ情報を前記要素データの空間座標に近づくように修正する分類データ修正ステップと、
前記最近傍分類データ検出手段により検出された最近傍となる前記分類データのクラス情報が前記クラス判断手段により前記訓練用データのクラスと同一であると判断された場合に値を減少させる使用確率変数を、使用確率変更手段が前記訓練用データ毎に付与する使用確率変更ステップと、
テスト関数生成手段が、前記分類データ修正手段により修正がなされた分類データのデータ情報とクラス情報とに基づいて入力データの分類を行う多変数テスト関数を生成するテスト関数生成ステップと
を有し、
最近傍分類データ検出ステップにおいて、前記使用確率変数の値が所定値以上を示す前記訓練用データのみを用いて前記最近傍分類データ検出手段が前記分類データの検出を行うこと
を特徴とする多変数テスト関数生成方法。
【請求項７】
複数要素の要素データを有する複数の入力データを複数のクラスに分類するための多変数テスト関数を生成する多変数テスト関数生成方法であって、
訓練用データ取得手段が、予め要素データと分類されるべきクラスとが既知である入力データからなる訓練用データを取得する訓練用データ取得ステップと、
最近傍分類データ検出手段が、前記訓練用データ取得手段により取得された前記要素データの要素数に基づいて、当該要素数に対応する複数次元の特徴空間を構成し、前記訓練用データの要素データの値を前記特徴空間の空間座標として判断するとともに、前記要素データに対応するデータ情報と前記クラスを示すクラス情報とを有する複数の分類データを、当該分類データのデータ情報の値に基づいて前記特徴空間の空間座標として判断し、前記訓練用データの空間座標と前記分類データの空間座標との距離が最小となる分類データを求める最近傍分類データ検出ステップと、
クラス判断手段が、最近傍分類データ検出手段により求められた分類データのクラス情報と前記訓練用データのクラスとが同一クラスであるか否かを判断するクラス判断ステップと、
該クラス判断手段により前記分類データのクラス情報と前記訓練用データのクラスとが同一クラスであると判断された場合に、分類データ修正手段が当該分類データのデータ情報を前記要素データの空間座標に近づくように修正する分類データ修正ステップと、
前記最近傍分類データ検出手段により検出された最近傍となる前記分類データのクラス情報が前記クラス判断手段により前記訓練用データのクラスと同一であると判断された場合に値を減少させる使用確率変数を、使用確率変更手段が前記訓練用データ毎に付与する使用確率変更ステップと、
テスト関数生成手段が、前記分類データ修正手段により修正がなされた分類データのデータ情報とクラス情報とに基づいて入力データの分類を行う多変数テスト関数を生成するテスト関数生成ステップと
を有し、
前記最近傍分類データ検出ステップにおいて、前記使用確率変数の値が所定値以上を示す前記訓練用データのみを用いて前記最近傍分類データ検出手段が前記分類データの検出を行うこと
を特徴とする多変数テスト関数生成方法。
【請求項８】
複数要素の要素データを有する複数の入力データを複数のクラスに分類するための多変数テスト関数を生成するために、コンピュータに、
予め要素データと分類されるべきクラスとが既知である入力データからなる訓練用データを、訓練用データ取得手段により取得させる訓練用データ取得ステップと、
該訓練用データ取得ステップにおいて取得された前記要素データの要素数に基づいて、最近傍分類データ検出手段により当該要素数に対応する複数次元の特徴空間を構成させ、前記訓練用データの要素データの値を前記特徴空間の空間座標として判断させるとともに、前記要素データに対応するデータ情報と前記クラスを示すクラス情報とを有する複数の分類データを、当該分類データのデータ情報の値に基づいて前記特徴空間の空間座標として判断させ、前記訓練用データの空間座標と前記分類データの空間座標との距離が最小となる分類データを求めさせる最近傍分類データ検出ステップと、
該最近傍分類データ検出ステップにおいて求められた分類データのクラス情報と前記訓練用データのクラスとが同一クラスであるか否かを、クラス判断手段により判断させるクラス判断ステップと、
該クラス判断ステップにおいて前記分類データのクラス情報と前記訓練用データのクラスとが異なるクラスであると判断された場合に、分類データ修正手段により当該分類データのデータ情報を前記要素データの空間座標から遠ざかるように修正させるとともに、前記クラス判断ステップにおいて前記訓練用データと同一クラスであると判断される他の分類データを前記最近傍分類データ検出ステップにより検出させ、当該他の分類データのデータ情報を前記要素データの空間座標に近づくように修正させる分類データ修正ステップと、
前記最近傍分類データ検出ステップにおいて検出された最近傍となる前記分類データのクラス情報が前記クラス判断ステップにおいて前記訓練用データのクラスと同一であると判断された場合に値を減少させる使用確率変数を、使用確率変更手段により前記訓練用データ毎に付与させる使用確率変更ステップと、
前記分類データ修正ステップにおいて修正がなされた分類データのデータ情報とクラス情報とに基づいて入力データの分類を行う多変数テスト関数を、テスト関数生成手段により生成させるテスト関数生成ステップと
を実行させ、
さらに、前記最近傍分類データ検出ステップにおいて、前記使用確率変数の値が所定値以上を示す前記訓練用データのみを用いて前記最近傍分類データ検出手段に前記分類データの検出を行わせる
ことを特徴とする多変数テスト関数を生成するためのプログラム。
【請求項９】
複数要素の要素データを有する複数の入力データを複数のクラスに分類するための多変数テスト関数を生成するために、コンピュータに、
予め要素データと分類されるべきクラスとが既知である入力データからなる訓練用データを、訓練用データ取得手段により取得させる訓練用データ取得ステップと、
該訓練用データ取得ステップにおいて取得された前記要素データの要素数に基づいて、最近傍分類データ検出手段により当該要素数に対応する複数次元の特徴空間を構成させ、前記訓練用データの要素データの値を前記特徴空間の空間座標として判断させるとともに、前記要素データに対応するデータ情報と前記クラスを示すクラス情報とを有する複数の分類データを、前記分類データのデータ情報の値に基づいて前記特徴空間の空間座標として判断させ、前記訓練用データの空間座標と前記分類データの空間座標との距離が最小となる分類データを求める最近傍分類データ検出ステップと、
該最近傍分類データ検出ステップにおいて求められた分類データのクラス情報と前記訓練用データのクラスとが同一クラスであるか否かを、クラス判断手段により判断させるクラス判断ステップと、
該クラス判断ステップにおいて前記分類データのクラス情報と前記訓練用データのクラスとが同一クラスであると判断された場合に、分類データ修正手段により当該分類データのデータ情報を前記要素データの空間座標に近づくように修正させる分類データ修正ステップと、
前記最近傍分類データ検出ステップにおいて検出された最近傍となる前記分類データのクラス情報が前記クラス判断ステップにおいて前記訓練用データのクラスと同一であると判断された場合に値を減少させる使用確率変数を、使用確率変更手段により前記訓練用データ毎に付与させる使用確率変更ステップと、
前記分類データ修正ステップにおいて修正がなされた分類データのデータ情報とクラス情報とに基づいて入力データの分類を行う多変数テスト関数を、テスト関数生成手段により生成させるテスト関数生成ステップと
を実行させ、
さらに、前記最近傍分類データ検出ステップにおいて、前記使用確率変数の値が所定値以上を示す前記訓練用データのみを用いて前記最近傍分類データ検出手段に前記分類データの検出を行わせる
ことを特徴とする多変数テスト関数を生成するためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数要素の要素データを有する複数の入力データを複数のクラスに分類する多変数テスト関数を生成するための多変数テスト関数生成装置、多変数テスト関数生成システム、多変数テスト関数生成方法および多変数テスト関数を生成するためのプログラムに関する。
【背景技術】
【０００２】
近年、コンピュータを用いた判断処理が日常的に使用されるようになってきた。コンピュータによる一般的な判断方法には、いわゆるｉｆ−ｔｈｅｎルールが用いられている。
【０００３】
複数のｉｆ−ｔｈｅｎルールを効率よく、わかりやすくまとめる方法としては、決定木（ツリー構造）がある。図5は、決定木の一例を示している。図５に示す決定木は決定結果（クラス）Ｃｌａｓｓ０，Ｃｌａｓｓ１を持つ終端節点（ｃ１〜ｃ４）と単一変数テスト関数（ＵＴＦ：Univariate Test Function）を使って局所的な判断を行う非終端節点（ａ１、ｂ１，ｂ２）とにより構成されている。コンピュータが何らかの判断を行う場合には、最上位にある非終端節点ａ１（ルート）より単一テスト関数による判断に基づいて子節点（下位節点）へと判断分類を行い、最終的に終端節点における決定結果に基づいて判断を行う。
【０００４】
例えば、入力データ：Ｘ＝（０．１、０．８）として、図５に示す決定木を用いてＣｌａｓｓ０又はＣｌａｓｓ１の分類を行う場合を考える。まず、コンピュータは、最上位にある非終端節点ａ１（ルート）におけるテスト関数：Ｘ１＜０．５？に基づく判断を行う。入力データ：Ｘ＝（０．１、０．８）より第１のＸ要素（Ｘ１）＝０．１は、０．５よりも小さくなるのでＸ１＜０．５の条件を満たすものと判断され、ルートの下位の非終端節点であってルートのテスト関数を満たす場合に次の判断が求められる非終端節点ｂ１へと処理が移行する。
【０００５】
そしてコンピュータは、非終端節点ｂ１におけるテスト関数：Ｘ２＜０．５？に基づく判断を行う。入力データ：Ｘ＝（０．１、０．８）より第２のＸ要素（Ｘ２）＝０．８は、０．５よりも大きいので、Ｘ２＜０．５？の条件を満たさず、非終端節点ｂ１の下位の終端節点であって決定結果としてＣｌａｓｓ１を備える終端節点Ｃ２へと処理が移行する。コンピュータは終端節点ｃ２において決定結果としてＣｌａｓｓ１の決定結果を取得して、入力データ：ＸがＣｌａｓｓ１であると判断する。
【０００６】
このように、各非終端節点で単一変数テスト関数を用いて判断を行わせることによって、判断内容をｉｆ−ｔｈｅｎルールで示すことができるので、理解しやすいという特徴がある。
【０００７】
なお、このような単一変数テスト関数に対応する決定結果の境界は、座標軸に平行なものとなる（図６参照）ので、通常の決定木はＡＰＤＴ(Axis-Parallel Decision Tree)とも呼ばれる。ＡＤＴＰを構築する既存の方法として、ＣＡＲＴ（例えば、特許文献１参照）やＣ４．５（例えば、非特許文献２参照）等が知られている。
【０００８】
しかしながら、単一変数テスト関数を用いて判断処理を行うＡＰＤＴでは、判断を行うためのデータ数が一定以上になると性能（認識率など）が飽和してしまうとともに、決定木のサイズ（節点の数等）がデータ数に比例して大きくなってしまう（例えば、非特許文献３参照）。このため、決定木のサイズが大きくなり節点数が増加すると、対応するｉｆ−ｔｈｅｎルールが非常に長くなり、理解が困難なものとなってしまうという問題があった。
【０００９】
一方で、決定木のサイズを減らす方法として、各非終端節点において多変数テスト関数（ＭＴＦ：Multivariate Test function）を用いることにより節点数を減らす方法も提案されている。多変数テスト関数を利用した決定木の中でよく知られているものがＯＤＴ（Oblique Decision Tree）である。ＯＤＴでは次式に示す式１のようなテスト関数が用いられている。
【数１】
2007213442.tif 000003
・・・・・（１）
ここで、Ｎｄは特徴（テスト関数において分類が行われる入力データの要素）の数、ｘｉはｉ番目の特徴、ｗｉはｉ番目の重み係数、θは閾値である。通常、Ｆ（Ｘ）＜０の場合、ｘを左子節点に割り当て、Ｆ（Ｘ）≧０の場合、ｘを右子節点に割り当てる。このようなＦ（Ｘ）に対応する決定境界は一般の超平面となるので、ＡＰＤＴよりもＯＤＴの方が効率よくデータを分類することができる。
【非特許文献１】L. Brieman, J. H. Friedman, R. A. Olshen and C. J. Stong, Classification and Regression Trees, Pacific Grove, CA: Wadsworth & Brooks Advanced Books and Software, 1984.
【非特許文献２】J. R. Quinlan, C4.5: Programs for Machine Learning, Morgan Kauffman Publishers, 1993.
【非特許文献３】T. Oates and D. Jensen, "The effects of training set size on decision tree complexity," The 14-th International Conference on Machine Learning, pp. 254-262, 1997.
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、ＯＤＴのような多変数テスト関数を利用する決定木（多変数決定木（ＭＤＴ：Multivariate Decision Tree）では、その判断方法がブラックボックス化してしまうという問題があった。例えば、式１に示す多変数テスト関数では、データＸが超平面の下側（Ｆ（Ｘ）＜０）ならばクラス０と判断され、超平面の上（Ｆ（Ｘ）≧０）ならばクラス１と分類される場合、この分類自体は正しいものであっても、それが何を意味するか判断することは容易ではない。
【００１１】
さらに、多変数テスト関数を用いて決定木を構築するために莫大な計算量が必要とされるという問題があった。例えば、最も簡単多変数決定木であるＯＤＴを構築する場合でさえ、最適な多変数テスト関数を求める問題はＮＰ−完全問題となり、計算量がパラメータの数に対して指数関数的に増大してしまうという問題があった。
【００１２】
ＯＤＴを構築する方法がいくつか提案されているが、その中で最も効率がよいと思われる方法はＯＣ１である（例えば、非特許文献「S. K. Murthy, S. Kasif and S. Salzber, "A system for induction of oblique decision trees," Journal of Artificial Intelligence Research, No. 2, pp. 112, 1994」）。ＯＣ１では、まず最適なＵＴＦを求め、そこから局所検索を行ってよりよいＭＴＦを求める。局所検索が局所最適値（Local Optimal）におちついた場合、小さな外乱を用いてよりよい最適値を求めることによってＯＤＴを構築する。しかしながら、ＯＣ１の中に確率的方法が含まれるので、実際の計算量が非常に大きくなる場合がある。また、ＯＣ１に使われている方法は、ＯＤＴを求めるのに提案されていたものであり、一般のＭＤＴの構築には使えない。
【００１３】
本発明は、上記問題に鑑みてなされたものであり、理解可能であって更に構築のための計算量および計算時間を短縮させることが可能な多変数テスト関数を生成するための多変数テスト関数生成装置、多変数テスト関数生成システム、多変数テスト関数生成方法および多変数テスト関数を生成するためのプログラムを提供することを課題とする。
【課題を解決するための手段】
【００１４】
上記課題を解決するために、本発明に係る多変数テスト関数生成装置は、複数要素の要素データを有する複数の入力データを複数のクラスに分類するための多変数テスト関数を生成する多変数テスト関数生成装置であって、予め要素データと分類されるべきクラスとが既知である入力データからなる訓練用データを取得する訓練用データ取得手段と、前記要素データに対応するデータ情報と前記クラスを示すクラス情報とを有する複数の分類データを記録する分類データ記録手段と、前記要素データの要素数に基づいて当該要素数に対応する複数次元の特徴空間を構成し、前記訓練用データの要素データの値を前記特徴空間の空間座標として判断するとともに、前記分類データ記録手段に記録される前記分類データのデータ情報の値を前記特徴空間の空間座標として判断し、前記訓練用データの空間座標と前記分類データの空間座標との距離が最小となる分類データを求める最近傍分類データ検出手段と、該最近傍分類データ検出手段により求められた分類データのクラス情報と前記訓練用データのクラスとが同一クラスであるか否かを判断するクラス判断手段と、該クラス判断手段により前記分類データのクラス情報と前記訓練用データのクラスとが異なるクラスであると判断された場合に、前記分類データ記録手段に記録される当該分類データのデータ情報を前記要素データの空間座標から遠ざかるように修正するとともに、前記クラス判断手段により前記訓練用データと同一クラスであると判断される他の分類データを前記最近傍分類データ検出手段により検出させ、前記分類データ記録手段に記録される当該他の分類データのデータ情報を前記要素データの空間座標に近づくように修正する分類データ修正手段と、前記最近傍分類データ検出手段により検出された最近傍となる前記分類データのクラス情報が前記クラス判断手段により前記訓練用データのクラスと同一であると判断された場合に値が減少する使用確率変数を、前記訓練用データ毎に付与する使用確率変更手段と、前記分類データ修正手段により修正がなされた分類データのデータ情報とクラス情報とに基づいて前記多変数テスト関数を生成するテスト関数生成手段とを有し、前記最近傍分類データ検出手段は、前記使用確率変数の値が所定値以上を示す前記訓練用データのみを用いて前記分類データの検出を行うことを特徴とする。
【００１５】
一方で、本発明に係る多変数テスト関数生成装置は、複数要素の要素データを有する複数の入力データを複数のクラスに分類するための多変数テスト関数を生成する多変数テスト関数生成装置であって、予め要素データと分類されるべきクラスとが既知である入力データからなる訓練用データを取得する訓練用データ取得手段と、前記要素データに対応するデータ情報と前記クラスを示すクラス情報とを有する複数の分類データを記録する分類データ記録手段と、前記要素データの要素数に基づいて当該要素数に対応する複数次元の特徴空間を構成し、前記訓練用データの要素データの値を前記特徴空間の空間座標として判断するとともに、前記分類データ記録手段に記録される前記分類データのデータ情報の値を前記特徴空間の空間座標として判断し、前記訓練用データの空間座標と前記分類データの空間座標との距離が最小となる分類データを求める最近傍分類データ検出手段と、該最近傍分類データ検出手段により求められた分類データのクラス情報と前記訓練用データのクラスとが同一クラスであるか否かを判断するクラス判断手段と、該クラス判断手段により前記分類データのクラス情報と前記訓練用データのクラスとが同一クラスであると判断された場合に、前記分類データ記録手段に記録される当該分類データのデータ情報を前記要素データの空間座標に近づくように修正する分類データ修正手段と、前記最近傍分類データ検出手段により検出された最近傍となる前記分類データのクラス情報が前記クラス判断手段により前記訓練用データのクラスと同一であると判断された場合に値が減少する使用確率変数を、前記訓練用データ毎に付与する使用確率変更手段と、前記分類データ修正手段により修正がなされた分類データのデータ情報とクラス情報とに基づいて前記多変数テスト関数を生成するテスト関数生成手段とを有し、前記最近傍分類データ検出手段は、前記使用確率変数の値が所定値以上を示す前記訓練用データのみを用いて前記分類データの検出を行うことを特徴とする。
【００１６】
本発明に係る多変数テスト関数生成システムは、複数要素の要素データを有する入力データを複数のクラスに分類するための多変数テスト関数を生成する多変数テスト関数生成システムであって、予め要素データと分類されるべきクラスとが既知である入力データを訓練用データとして記録する訓練用データ記録手段と、前記多変数テスト関数は、前記要素データに対応するデータ情報と前記クラスを示すクラス情報とを有する複数の分類データからなり、前記要素データの要素数に基づいて当該要素数に対応する複数次元の特徴空間を構成し、前記訓練用データの要素データの値を前記特徴空間の空間座標として判断するとともに、前記分類データのデータ情報の値を前記特徴空間の空間座標として判断することによって、前記訓練用データの空間座標までの距離が最小となる最近傍の分類データを求め、当該訓練用データと求められた最近傍の分類データとが同一のクラスとなるように前記分類データの空間位置を修正することにより前記分類データのデータ情報の修正を行い、修正がなされた分類データのデータ情報とクラス情報とに基づいて前記多変数テスト関数を生成する多変数テスト関数生成手段と、生成された多変数テスト関数を記録する多変数テスト関数記録手段とを備え、前記多変数テスト関数生成手段は、最近傍となる前記分類データのクラス情報が前記訓練用データのクラスと同一であった場合に値が減少する使用確率変数を前記訓練用データ毎に付与し、前記使用確率変数が所定値以上を示す前記訓練用データを用いて前記分類データのデータ情報の修正処理を行うことを特徴とする。
【００１７】
また、多変数テスト関数生成システムは、前記多変数テスト関数生成手段が、前記訓練用データの要素データにおける空間座標から最近傍となる分類データのクラス情報が前記訓練用データのクラスと異なる場合に、当該分類データのデータ情報を前記要素データの空間座標から遠ざかるように修正し、さらに前記訓練用データと同一クラスのクラス情報を有する分類データのうち、前記要素データの空間座標に最近傍となる他の分類データを求めて、当該他の分類データのデータ情報を前記要素データの空間座標に近づくように修正することを特徴とするものであってもよい。
【００１８】
さらに、多変数テスト関数生成システムは、前記多変数テスト関数生成手段が、前記訓練用データの要素データにおける空間座標から最近傍となる分類データのクラス情報が前記訓練用データのクラスと同一の場合に、当該分類データのデータ情報を前記要素データの空間座標に近づくように修正することを特徴とするものであってもよい。
【００１９】
本発明に係る多変数テスト関数生成方法は、複数要素の要素データを有する複数の入力データを複数のクラスに分類するための多変数テスト関数を生成する多変数テスト関数生成方法であって、訓練用データ取得手段が、予め要素データと分類されるべきクラスとが既知である入力データからなる訓練用データを取得する訓練用データ取得ステップと、最近傍分類データ検出手段が、前記訓練用データ取得手段により取得された前記要素データの要素数に基づいて、当該要素数に対応する複数次元の特徴空間を構成し、前記訓練用データの要素データの値を前記特徴空間の空間座標として判断するとともに、前記要素データに対応するデータ情報と前記クラスを示すクラス情報とを有する複数の分類データを、当該分類データのデータ情報の値に基づいて前記特徴空間の空間座標として判断し、前記訓練用データの空間座標と前記分類データの空間座標との距離が最小となる分類データを求める最近傍分類データ検出ステップと、クラス判断手段が、最近傍分類データ検出手段により求められた分類データのクラス情報と前記訓練用データのクラスとが同一クラスであるか否かを判断するクラス判断ステップと、前記クラス判断手段により前記分類データのクラス情報と前記訓練用データのクラスとが異なるクラスであると判断された場合に、分類データ修正手段が当該分類データのデータ情報を前記要素データの空間座標から遠ざかるように修正するとともに、前記クラス判断手段により前記訓練用データと同一クラスであると判断される他の分類データを前記最近傍分類データ検出手段により検出させ、当該他の分類データのデータ情報を前記要素データの空間座標に近づくように修正する分類データ修正ステップと、前記最近傍分類データ検出手段により検出された最近傍となる前記分類データのクラス情報が前記クラス判断手段により前記訓練用データのクラスと同一であると判断された場合に値を減少させる使用確率変数を、使用確率変更手段が前記訓練用データ毎に付与する使用確率変更ステップと、テスト関数生成手段が、前記分類データ修正手段により修正がなされた分類データのデータ情報とクラス情報とに基づいて入力データの分類を行う多変数テスト関数を生成するテスト関数生成ステップとを有し、最近傍分類データ検出ステップにおいて、前記使用確率変数の値が所定値以上を示す前記訓練用データのみを用いて前記最近傍分類データ検出手段が前記分類データの検出を行うことを特徴とする。
【００２０】
また、本発明に係る多変数テスト関数生成方法は、複数要素の要素データを有する複数の入力データを複数のクラスに分類するための多変数テスト関数を生成する多変数テスト関数生成方法であって、訓練用データ取得手段が、予め要素データと分類されるべきクラスとが既知である入力データからなる訓練用データを取得する訓練用データ取得ステップと、最近傍分類データ検出手段が、前記訓練用データ取得手段により取得された前記要素データの要素数に基づいて、当該要素数に対応する複数次元の特徴空間を構成し、前記訓練用データの要素データの値を前記特徴空間の空間座標として判断するとともに、前記要素データに対応するデータ情報と前記クラスを示すクラス情報とを有する複数の分類データを、当該分類データのデータ情報の値に基づいて前記特徴空間の空間座標として判断し、前記訓練用データの空間座標と前記分類データの空間座標との距離が最小となる分類データを求める最近傍分類データ検出ステップと、クラス判断手段が、最近傍分類データ検出手段により求められた分類データのクラス情報と前記訓練用データのクラスとが同一クラスであるか否かを判断するクラス判断ステップと、該クラス判断手段により前記分類データのクラス情報と前記訓練用データのクラスとが同一クラスであると判断された場合に、分類データ修正手段が当該分類データのデータ情報を前記要素データの空間座標に近づくように修正する分類データ修正ステップと、前記最近傍分類データ検出手段により検出された最近傍となる前記分類データのクラス情報が前記クラス判断手段により前記訓練用データのクラスと同一であると判断された場合に値を減少させる使用確率変数を、使用確率変更手段が前記訓練用データ毎に付与する使用確率変更ステップと、テスト関数生成手段が、前記分類データ修正手段により修正がなされた分類データのデータ情報とクラス情報とに基づいて入力データの分類を行う多変数テスト関数を生成するテスト関数生成ステップとを有し、前記最近傍分類データ検出ステップにおいて、前記使用確率変数の値が所定値以上を示す前記訓練用データのみを用いて前記最近傍分類データ検出手段が前記分類データの検出を行うことを特徴とする。
【００２１】
本発明に係る多変数テスト関数を生成するためのプログラムは、複数要素の要素データを有する複数の入力データを複数のクラスに分類するための多変数テスト関数を生成するために、コンピュータに、予め要素データと分類されるべきクラスとが既知である入力データからなる訓練用データを、訓練用データ取得手段により取得させる訓練用データ取得ステップと、該訓練用データ取得ステップにおいて取得された前記要素データの要素数に基づいて、最近傍分類データ検出手段により当該要素数に対応する複数次元の特徴空間を構成させ、前記訓練用データの要素データの値を前記特徴空間の空間座標として判断させるとともに、前記要素データに対応するデータ情報と前記クラスを示すクラス情報とを有する複数の分類データを、当該分類データのデータ情報の値に基づいて前記特徴空間の空間座標として判断させ、前記訓練用データの空間座標と前記分類データの空間座標との距離が最小となる分類データを求めさせる最近傍分類データ検出ステップと、該最近傍分類データ検出ステップにおいて求められた分類データのクラス情報と前記訓練用データのクラスとが同一クラスであるか否かを、クラス判断手段により判断させるクラス判断ステップと、該クラス判断ステップにおいて前記分類データのクラス情報と前記訓練用データのクラスとが異なるクラスであると判断された場合に、分類データ修正手段により当該分類データのデータ情報を前記要素データの空間座標から遠ざかるように修正させるとともに、前記クラス判断ステップにおいて前記訓練用データと同一クラスであると判断される他の分類データを前記最近傍分類データ検出ステップにより検出させ、当該他の分類データのデータ情報を前記要素データの空間座標に近づくように修正させる分類データ修正ステップと、前記最近傍分類データ検出ステップにおいて検出された最近傍となる前記分類データのクラス情報が前記クラス判断ステップにおいて前記訓練用データのクラスと同一であると判断された場合に値を減少させる使用確率変数を、使用確率変更手段により前記訓練用データ毎に付与させる使用確率変更ステップと、前記分類データ修正ステップにおいて修正がなされた分類データのデータ情報とクラス情報とに基づいて入力データの分類を行う多変数テスト関数を、テスト関数生成手段により生成させるテスト関数生成ステップとを実行させ、さらに、前記最近傍分類データ検出ステップにおいて、前記使用確率変数の値が所定値以上を示す前記訓練用データのみを用いて前記最近傍分類データ検出手段に前記分類データの検出を行わせることを特徴とする。
【００２２】
また、本発明に係る多変数テスト関数を生成するためのプログラムは、複数要素の要素データを有する複数の入力データを複数のクラスに分類するための多変数テスト関数を生成するために、コンピュータに、予め要素データと分類されるべきクラスとが既知である入力データからなる訓練用データを、訓練用データ取得手段により取得させる訓練用データ取得ステップと、該訓練用データ取得ステップにおいて取得された前記要素データの要素数に基づいて、最近傍分類データ検出手段により当該要素数に対応する複数次元の特徴空間を構成させ、前記訓練用データの要素データの値を前記特徴空間の空間座標として判断させるとともに、前記要素データに対応するデータ情報と前記クラスを示すクラス情報とを有する複数の分類データを、前記分類データのデータ情報の値に基づいて前記特徴空間の空間座標として判断させ、前記訓練用データの空間座標と前記分類データの空間座標との距離が最小となる分類データを求める最近傍分類データ検出ステップと、該最近傍分類データ検出ステップにおいて求められた分類データのクラス情報と前記訓練用データのクラスとが同一クラスであるか否かを、クラス判断手段により判断させるクラス判断ステップと、該クラス判断ステップにおいて前記分類データのクラス情報と前記訓練用データのクラスとが同一クラスであると判断された場合に、分類データ修正手段により当該分類データのデータ情報を前記要素データの空間座標に近づくように修正させる分類データ修正ステップと、前記最近傍分類データ検出ステップにおいて検出された最近傍となる前記分類データのクラス情報が前記クラス判断ステップにおいて前記訓練用データのクラスと同一であると判断された場合に値を減少させる使用確率変数を、使用確率変更手段により前記訓練用データ毎に付与させる使用確率変更ステップと、前記分類データ修正ステップにおいて修正がなされた分類データのデータ情報とクラス情報とに基づいて入力データの分類を行う多変数テスト関数を、テスト関数生成手段により生成させるテスト関数生成ステップとを実行させ、さらに、前記最近傍分類データ検出ステップにおいて、前記使用確率変数の値が所定値以上を示す前記訓練用データのみを用いて前記最近傍分類データ検出手段に前記分類データの検出を行わせることを特徴とする。
【発明の効果】
【００２３】
本発明に係る多変数テスト関数生成装置、多変数テスト関数生成システム、多変数テスト関数生成方法および多変数テスト関数を生成するためのプログラムを用いることによって、各訓練用データに対して使用確率変数を付与し、最近傍の分類データ検出において検出されたなる前記分類データのクラス情報が訓練用データのクラスと同一であると判断された場合、つまり最近傍となる分類データにより正しくクラスの分類が行われた場合に、訓練用データの使用確率変数の値を減少させることによって、訓練用データの個別の誤判断率を求めている。このため、使用確率変数が所定値以上の訓練用データのみ、つまり誤判断率の高い訓練用データのみを繰り返し用いて分類データのデータ情報を修正（更新）することによって、データ情報の更新に使用する訓練用データ量を減らしつつ、効率よく分類データの修正（更新）を行うことができ、全ての訓練用データを複数回使用して分類データの更新を行う場合に比べて処理量を減少させ、処理スピードを高めることが可能となる。
【００２４】
また、データの要素データに基づく空間位置と分類データのデータ情報に基づく空間位置との距離により最適な分類データを求めて、その分類データのクラス情報に基づいてデータの分類を行うので、多変数テスト関数を用いた判断方法を容易に理解することができ、ＯＤＴのように判断方法がブラックボックス化してしまうことを回避することができる。
【００２５】
さらに、本発明に係る多変数テスト関数生成装置等を用いることによって、多変数決定木の構築を高速に行うことが可能となる。
【発明を実施するための最良の形態】
【００２６】
以下、本発明に係る多変数テスト関数生成システムを、図面を用いて説明する。図１は、本発明に係る多変数テスト関数生成システム１の概略構成を示したブロック図である。
【００２７】
多変数テスト関数生成システム１は、多変数テスト関数を生成するために用いられる訓練用データが記録される訓練用データ記録部部（訓練用データ記録手段）２と、多変数テスト関数を生成するための演算処理部３と、演算処理部３により作成された多変数テスト関数を記録する多変数テスト関数記録部（多変数テスト関数記録手段）４とを有している。
【００２８】
訓練用データ記録部２は、メモリ、ハードディスク、フレキシブルディスク、光学記録装置（例えば、ＣＤ−ＲＯＭ、ＤＶＤＲＯＭ等）等のデータを記録・読み出し可能な装置で構成され、必要に応じてこれらに記録された訓練用データを読み出すことが可能な構成となっている。
【００２９】
訓練用データは、多変数テスト関数を作成するために必要とされるデータ群であり、各データは、（ｘ１，ｘ２、・・・ｘｎ、クラス）の形で記録される。ここで、ｘ１、ｘ２・・・は、分類を行うために用いられる要素データであり、クラスは分類（分割）されるべき分類情報を示している。演算処理部３は、各データを読み取り、例えばデータの第１要素＝ｘ１，第２要素＝ｘ２、・・・、第ｎ要素＝ｘｎとなる場合には、決定結果としてクラスＣが求められるような多変数テスト関数を生成する。つまり、演算処理部３は、訓練用データの要素データとしての判断条件（ｘ１，ｘ２、・・・ｘｎ）と、これらの判断条件（ｘ１，ｘ２、・・・ｘｎ）に基づいて求められる判断結果（クラス）とにより、判断条件から判断結果を算出する多変数テスト関数を生成する。
【００３０】
多変数テスト関数記録部４も、訓練用データ記録部２と同様に、メモリ、ハードディスク、フレキシブルディスク、光学記録装置等等のデータを記録・読み出し可能な記録装置で構成され、演算処理部３によって作成された多変数テスト関数を格納する構成となっている。
【００３１】
なお、説明の便宜上、訓練用データ記録部２と多変数テスト関数記録部４とを別々の記録装置として図示したが、両方を同一の記録装置によって構成しても良い。さらに、訓練用データ記録部２や多変数テスト関数記録部４は、必ずしも物理的に演算処理部３に繋がっているものである必要はなく、訓練用データ記録部２は、演算処理部３に対して訓練用データを出力することができ、多変数テスト関数記録部４は、演算処理部３により作成された多変数テスト関数を受信して記録することができれば良いので、ネットワークを介してデータの送受信ができるような関係であっても良い。
【００３２】
演算処理部３は、計算・制御処理全般を司るＣＰＵ、演算処理において必要なデータを一時的に記録するＲＡＭ（図１に示す分類データ記録機能５としての役割）、ＣＰＵにおける演算処理をプログラムとして記録するＲＯＭ等を備える。なお、これらのＲＡＭやＲＯＭ等は、上述した訓練用データ記録部２や多変数テスト関数記録部４等に用いられる記録装置と兼用するものであっても良い。
【００３３】
演算処理部３は、最近傍識別器（以下、ＮＮＣという）という多変数テスト関数を生成する。「背景技術」において説明したように、多変数テスト関数を利用した決定木の中でよく知られているＯＤＴ（Oblique Decision Tree）の多変数テスト関数は（１）式で示されるものである。このテスト関数はブラックボックス化してしまうという問題があり、分類自体が正しいものであっても、それが何を意味するか判断することは容易ではなかった。本発明に係る多変数テスト関数生成システムで生成するＮＮＣは、人間らしい判断が可能な多変数テスト関数である。
【００３４】
まず、ＮＮＣについて説明する。ＮＮＣは複数のプロトタイプ（分類データ）により構成される。プロトタイプとは、分類を行うための訓練用データ（入力データ）と同様の（対応する）データ形式からなるデータ情報を有している。データ情報は、特徴空間における空間座標として表すことができる。また、各プロトタイプはクラス（ＮＮＣを用いて非終端節点において分類（分割）されるべきグループの情報、分類結果）を備えており、この点で、プロトタイプは既知のデータであるともいえる。
【００３５】
未知のデータＸを分類する場合、演算処理部３は、Ｘに最も類似しているプロトタイプＹを探し出してＸをＹと同じクラスに分類する。類似するか否かの判断は、特徴空間におけるＸとＹとの距離（通常、ユークリッド距離を使うが、他の距離を利用してもかまわない）Ｄによって求める。特徴空間の次元はＮｄとして、ＸとＹとの２点間のユークリッド距離Ｄは次の式で示される。
【数２】
2007213442.tif 000004
・・・・・（２）
この２点間距離が短ければ短いほどＸとＹとが類似する度合いが高いと判断できる。
【００３６】
図２は、式２により入力データＸに最適なプロトタイプＹを求める過程を説明するために示した図であり、理解しやすいように２次元の特徴空間を一例として示している。入力データＸ＝（０．１、０．８）とし、プロトタイプＹとしてＰ１〜Ｐ４の４つの既知のタイプを用いる。なお、Ｐ１とＰ４とはクラス１、Ｐ２とＰ３とはクラス０のクラスを備えるものとする。
【００３７】
まず、演算処理部３は、入力データＸと全てのプロトタイプＰ１〜Ｐ４との距離を求める。図２から明らかなように、入力データＸからの距離が最も近いプロトタイプ（Ｘの最近傍）はＰ１であるため、入力データＸはプロトタイプＰ１と同じクラス１に属することとなり、演算処理部３は、入力データＸはクラス１という分類結果（決定結果）を判断する。
【００３８】
このように、ＮＮＣを利用したデータの分類・認識では、プロトタイプを前例として捉え、入力データとプロトタイプとの２点間距離（類似度）に基づいてクラスを判断（分類）することができる。即ち、未知の入力データＸが前例（プロトタイプＹ）に似ていれば、入力データＸはその前例（プロトタイプＹ）と同じクラスに分類されると判断することができる。従って、ＮＮＣは「人間らしい」判断ができ、判断基準を理解しやすい多変数テスト関数であるといえる。なお、ＮＮＣは、多数の単一テスト関数（ＵＴＦ）の集まりに相当するので、非終端節点においてＮＮＣをテスト関数として用いることによって決定木における節点数を少なくすることができ、理解しやすい決定木を構築することが可能となる。
【００３９】
次に、演算処理部３において、ＮＮＣを生成する方法をより詳細に説明する。
【００４０】
まず、本実施形態において演算処理部３により作成するＮＮＣは、予め作成されるＮＮＣのサイズ（プロトタイプの数）とプロトタイプのクラス（ここでのクラスとはＮＮＣにより分類されるグループのラベルを示す）が既知のものとする。ＮＮＣのサイズとプロトタイプのクラスとが既知のものであれば、サイズとクラスが決まっていないものよりも速くＮＮＣを構築することができる。ただし、サイズとクラスが既知のものでない場合には、通常十分に大きいＮＮＣのサイズを仮定し、ランダムにプロトタイプのクラスを決めるか又は各クラスに同じ数のプロトタイプを割り振る方法が用いられる。このようにしてサイズを仮定し、クラスを決定した場合であっても、訓練用データを用いてＮＮＣを修正（更新）することによってＮＮＣの精度を向上させることができる。
【００４１】
ＮＮＣを改善して精度を向上させるために、演算処理部３は複数エポック（全ての訓練用データを１回使用することを１エポックという）訓練用データを訓練用データ記録部２より読み出してプロトタイプの修正（更新）を繰り返し実行する。演算処理部３は、エポック数が規定値より多くなった場合にプロトタイプの修正（更新）を終了して、ＮＮＣの生成を完了する。
【００４２】
また、演算処理部３は、各プロトタイプを修正（更新）する方法として、学習率αという概念を用いて、プロトタイプの修正を行う。この学習率αは通常、０＜α＜１の初期値を取り、更新により徐々に減少する値である。
【００４３】
演算処理部３が、プロトタイプの修正（更新）を行う場合、まず演算処理部３は、入力データＸ（訓練用データの１つ）の最近傍となるプロトタイプＰ０を求め、求められたプロトタイプのクラスと入力データＸのクラスとを比較する。プロトタイプＰ０のクラスと入力データＸのクラスとが同じである場合には、このプロトタイプＰ０の修正（更新）を行うことなく、次の入力データを読み取り同様の処理を続ける。プロトタイプＰ０のクラスと入力データＸのクラスとが異なる場合、演算処理部３は、最近傍のプロトタイプＰ０以外のプロトタイプとして、入力データＸのクラスと同じクラスを持つプロトタイプの中から入力データＸに最も近いプロトタイプＰ１を求める。そして、演算処理部３は、プロトタイプＰ０とプロトタイプＰ１とを、
Ｐ０new＝Ｐ０old−α（Ｘ−Ｐ０old）          ・・・・・（３）
Ｐ１new＝Ｐ１old＋α（Ｘ−Ｐ１old）          ・・・・・（４）
に修正（更新）する。なお、αは０＜α＜１の値を示している。
【００４４】
（３）式は、プロトタイプＰ０を入力データＸの要素データとプロトタイプＰ０のデータ情報との差のα倍だけ入力データＸの空間位置より遠ざける計算式を示し、（４）式は、プロトタイプＰ１を入力データＸの要素データとプロトタイプＰ１のデータ情報との差のα倍だけ入力データＸの空間位置に近づける計算式を示している。
【００４５】
このように、１つの入力データＸを用いて、クラスの等しいプロトタイプＰ１が入力データＸに近づくようにプロトタイプＰ１の修正を行うと共に、クラスの異なるプロトタイプＰ０が入力データＸから遠ざかるようにプロトタイプＰ０の修正を行うことによって、ＮＮＣの認識（分類）精度の向上を図り、さらに各プロトタイプが最適な位置に修正される速度（収束速度）を向上させる。
【００４６】
また演算処理部３は、さらに効率よくプロトタイプの修正（更新）を行うために、全ての訓練用データに対して使用確率ｐを導入し、プロトタイプの修正（更新）に使用する訓練用データの使用回数の調整を行う。
【００４７】
具体的に演算処理部３は、入力データＸの使用確率ｐ（Ｘ）の初期値をｐ（Ｘ）＝１とし、入力データＸがそのときのＮＮＣにより正しく分類された場合（最近傍のプロトタイプのクラスが入力データＸのクラスと等しい場合）に、
ｐ（Ｘ）new＝β・ｐ（Ｘ）old
となるように使用確率ｐ（Ｘ）を更新する。ただし、βは０＜β＜１の定数である。
【００４８】
演算処理部３がプロトタイプの修正（更新）を行う場合、演算処理部３がある入力データＸを用いてプロトタイプの修正（更新）を行うか否かは、使用確率ｐ（Ｘ）の値によって決定される。βは０＜β＜１の定数であるため、入力データＸが何回も正しく認識された場合には、ｐ（Ｘ）が非常に小さくなる。実際にＮＮＣの生成において演算処理部３における処理負担の重い計算は、入力データとプロトタイプとの距離を求める計算である。このため、使用確率を導入することによって、正しく認識されやすい入力データの使用を少なくし、正しく認識されにくい入力データだけに着目して距離計算を行うことによって、演算処理部３の処理負担を軽減させて処理速度の向上を図ることが可能となる。
【００４９】
次に、フローチャートを用いて、演算処理部３におけるＮＮＣの生成方法を説明する。図３は、演算処理部３におけるＮＮＣの生成過程を示したフローチャートである。
【００５０】
まず演算処理部３は、初期設定を行う（ステップＳ１）。演算処理部３は、全て（ｎ個）の入力データの使用率ｐ（ｉ）（ただし、ｉ＝１，２，３・・・ｎ）の初期値に１を代入し、さらにエポック数を示す変数ｋの初期値に０を代入する。
【００５１】
続いて演算処理部３は、入力データＸの番号を示す変数ｉに１を代入し（ステップS２）、さらに０から１までの値を示す乱数ｒ発生させる（ステップＳ３）。そして、演算処理部３は、ｉ番目の入力データＸ（ｉ）の使用確率ｐ（ｉ）が乱数ｒよりも大きいか否かの比較を行う（ステップＳ４）。乱数ｒと使用確率ｐ（ｉ）とを比較することにより、乱数ｒよりも値が小さい使用確率ｐ（ｉ）の入力データＸ（ｉ）、つまり正しく認識されることにより値が減少してしまった使用確率ｐ（ｉ）の入力データＸ（ｉ）を用いて、プロトタイプの修正（更新）を行うことを回避する。
【００５２】
ここで、使用確率ｐ（ｉ）との比較を乱数ｒではなく０から１までの定数により行っても良いが、数エポック（このフローチャートにおいてはＫエポック）回だけ入力データＸ（ｉ）を繰り返し使ってプロトタイプの修正（更新）処理を行うため、エポック毎に異なる基準で使用確率ｐ（ｉ）の選別を行うべく、乱数ｒを用いることとしている。乱数ｒを用いることによって、使用確率ｐ（ｉ）の値が小さくなってプロトタイプの修正（更新）に使用されなくなった入力データＸ（ｉ）を、次のエポックの際に再度利用する可能性が生ずるため、プロトタイプの修正（更新）に使用される入力データが偏ってしまうことを防止することができる。
【００５３】
ｉ番目の入力データＸ（ｉ）の使用確率ｐ（ｉ）が乱数ｒよりも小さい場合（ステップＳ４においてＮｏ場合）、演算処理部３は、プロトタイプの更新を行うことなく、次述する変数ｉが入力データ数ｎよりも小さいか否かの判断を行う処理（ステップＳ１１）へ移行する。
【００５４】
入力データＸ（ｉ）の使用確率ｐ（ｉ）が乱数ｒよりも大きい場合（ステップＳ４においてＹｅｓの場合）、演算処理部３は、入力データＸ（ｉ）の最近傍となるプロトタイプを求めて、そのプロトタイプをＹ（ｊ１）とする（ステップＳ５）。そして演算処理部３は、求められたプロトタイプＹ（ｊ１）と入力データＸ（ｉ）とのクラスが同じか否かの判断を行う（ステップＳ６）。
【００５５】
プロトタイプＹ（ｊ１）と入力データＸ（ｉ）とのクラスが同じである場合（ステップＳ６においてＹｅｓの場合）、演算処理部３は、入力データＸ（ｉ）の最近傍のプロトタイプにより求められるクラスが入力データＸ（ｉ）のクラスとして最適なクラスであるため、ＮＮＣにより適正に入力データＸ（ｉ）が分類されたものと判断する。そして演算処理部３は、入力データＸ（ｉ）の使用確率ｐ（ｉ）に対してβを掛け合わせることによって（ｐ（ｉ）＝β・ｐ（ｉ））、使用確率ｐ（ｉ）がより小さい値となるように修正を行い（ステップＳ７）、次述するステップ１１へ処理を進める。
【００５６】
プロトタイプＹ（ｊ１）と入力データＸ（ｉ）とのクラスが異なる場合（ステップＳ６においてＮｏの場合）、演算処理部３は、入力データＸ（ｉ）の最近傍のプロトタイプにより求められるクラスが入力データＸ（ｉ）のクラスと異なるクラスであるため、ＮＮＣにより誤って入力データＸ（ｉ）が分類されたものと判断する。そして演算処理部３は、入力データＸ（ｉ）の使用確率ｐ（ｉ）に１を代入する（ステップＳ８）。使用確率ｐ（ｉ）に１を代入することにより、次にこの入力データＸ（ｉ）が使用される場合には、ステップＳ４においてＹｅｓと判断され、確実にプロトタイプの更新（変更）に使用されることとなる。
【００５７】
その後、演算処理部３は、入力データＸ（ｉ）と同じクラスを持つプロトタイプであっての最近傍となるプロトタイプを求め、そのプロトタイプをＹ（ｊ２）とする（ステップＳ９）。そして、演算処理部３は、プロトタイプＹ（ｊ１）とプロトタイプＹ（ｊ２）とを、
Ｙ（ｊ１）＝Ｙ（ｊ１）−α（Ｘ（ｉ）−Ｙ（ｊ１））
Ｙ（ｊ２）＝Ｙ（ｊ２）＋α（Ｘ（ｉ）−Ｙ（ｊ２））
に修正（更新）し、ＮＮＣの判断精度の向上を図る（ステップＳ１０）。
【００５８】
そして、演算処理部３は、変数ｉが入力データの全数ｎよりも小さいか否かの判断を行う（ステップＳ１１）。変数ｉがｎより小さい場合には、まだプロトタイプの修正（更新）処理に用いられていない入力データＸ（ｉ）が存在することとなるため、変数ｉの値に１を追加して（ｉ＝ｉ＋１）（ステップＳ１２）、上述した乱数の発生処理（ステップＳ３）からの処理を繰り返し実行する。
【００５９】
変数ｉがｎより小さくない場合には、全ての入力データＸが一通りプロトタイプの修正（更新）に使用されたものと判断できるため、１エポック分の処理が完了したものと判断する。
【００６０】
そして演算処理部３は、変数ｋが所定の値Ｋよりも小さいか否かの判断を行う（ステップＳ１３）。変数Ｋは、上述したようにプロトタイプの修正（更新）を行ったエポック数を示すため、ステップＳ１３では、多変数テスト関数生成に必要とされるエポック数であるＫ回だけ、プロトタイプの修正（更新）が行われたか否かの判断を行うこととなる。
【００６１】
プロトタイプの修正（更新）回数がＫエポック数よりも少ない場合（ステップＳ１３でＹｅｓの場合）、演算処理部３は、変数ｋの値に１を追加した後（ｋ＝ｋ＋１）（ステップＳ１４）、ステップＳ２に示す変数ｉに１を代入する処理以降の処理を繰り返し実行する。
【００６２】
プロトタイプの修正（更新）回数がＫエポック数に達した場合（ステップＳ１３でＮｏの場合）、演算処理部３は、訓練用データを用いたプロトタイプの修正（更新）処理を終了する。演算処理部３は、これらの処理により求められたプロトタイプの座標位置とそのクラスとを基準として入力データに最適な分類結果（クラス）を求める。つまり、演算処理部３は、プロトタイプのデータ情報（＝座標位置を示す情報）とクラス情報とを基準として最適なクラスを求める演算処理関数を多変数テスト関数として生成する。このようにして生成された多変数テスト関数は、多変数テスト関数記録部４に格納される。生成された多変数テスト関数を利用する場合には、利用しようとするシステム、例えば、文字認識、音声認識、交通状況予測等に適した形式にデータ形式を変更して、各システムの判断に用いられる。
【００６３】
以上説明したように、本発明に係る多変数テスト関数生成システムを用いることによって、訓練用データにおける入力データＸの空間位置に対して最も近い位置（最近傍の位置）に存在するプロトタイプのクラス情報が、訓練データのクラスと等しくなるようにプロトタイプが修正（更新）される。このため、訓練用データを用いて繰り返し（本実施例においてはＫエポック回数）プロトタイプを修正（更新）することによって分類精度の高いプロトタイプを生成することができ、このプロトタイプに基づいて入力データの分類を行うＮＮＣを生成することによって分類精度の高い多変数テスト関数を生成することが可能となる。
【００６４】
また、入力データＸの空間位置とプロトタイプの空間位置との距離により最適なプロトタイプを求め、そのプロトタイプのクラス情報に基づいて入力データＸの分類を行うので、多変数テスト関数を用いた判断方法を容易に理解することができ、ＯＤＴのように判断方法がブラックボックス化してしまうことを回避することができる。
【００６５】
また、多変数テスト関数生成装システムでは、各訓練用データ（入力データ）に対して使用確率変数を付与し、最近傍のプロトタイプ検出において検出されたプロトタイプのクラス情報が訓練用データのクラスと同一であると判断された場合、つまり最近傍となるプロトタイプにより正しくクラスの分類が行われた場合に、正しく判断された訓練用データの使用確率変数の値を減少させることによって、訓練用データの個別の誤判断率を求めている。このため、使用確率変数が所定値以上の訓練用データ、つまり誤判断率の高い訓練用データのみを繰り返し用いてプロトタイプのデータ情報を修正（更新）することによって、データ情報の更新に使用する訓練用データ量を減らしつつ、効率よくプロトタイプの修正（更新）を行うことができ、全ての訓練用データを複数回使用してプロトタイプの更新を行う場合に比べて処理量を減少させ、処理スピードを高めることが可能となる。
【００６６】
以上、本発明に係る多変数テスト関数生成システム１について、図面を用いて詳細に説明を行ったが、本発明に係る多変数テスト関数生成手段は、上述した実施形態に記載されるものに限定されるものではない。いわゆる当業者であれば、特許請求の範囲に記載された範疇内において、各種の変更例または修正例を想定し得ることは明らかであり、それらについても当発明の技術的範囲に属するものと了解される。
【００６７】
例えば、上記実施形態では、演算処理部３がプロトタイプの修正（更新）を行う場合、まず演算処理部３は、入力データＸ（ｉ）（ｉ番目の訓練用データ）の最近傍となるプロトタイプＹ（ｊ１）のクラスと入力データＸ（ｉ）のクラスとを比較し、プロトタイプＹ（ｊ１）クラスと入力データＸ（ｉ）のクラスとが異なる場合にのみ新たなプロトタイプＹ（ｊ２）を求めて（３）式、（４）式に示すようなプロトタイプの修正（更新）を行っているが、プロトタイプの修正（更新）方法はこの方法に限定されるものではない。
【００６８】
図４は、他のプロトタイプの修正方法を示したフローチャートである。図４に示すプロトタイプの修正方法は、図３のステップＳ９、ステップＳ１０に示す処理がなくなり、ステップＳ６とステップＳ７との間にステップＳ１５に示す処理が追加される点で相違する。
【００６９】
図４に示す処理では、入力データＸ（ｉ）の最近傍となるプロトタイプＹ（ｊ１）のクラスと入力データＸ（ｉ）のクラスとを比較し、プロトタイプＹ（ｊ１）のクラスと入力データＸ（ｉ）のクラスとが同じクラスの場合（ステップＳ６でＹｅｓの場合）に、プロトタイプＹ（ｊ１）のデータ情報を、
Ｙ（ｊ１）＝Ｙ（ｊ１）＋α（Ｘ（ｉ）−Ｙ（ｊ１））
に修正する（ステップＳ１５）。このように、同一クラスとなるプロトタイプ（ｊ１）が入力データＸ（ｉ）に近づくようにプロトタイプの修正を行うことによって、上述した実施形態と同様にＮＮＣの認識（分類）精度の向上を図り、各プロトタイプが最適な位置に修正される速度（収束速度）を向上させることが可能となる。
【００７０】
また、上述したように、同一クラスとなる最近傍のプロトタイプを入力データＸに近づくように修正するだけでなく、異なるクラスであって最近傍となるプロトタイプを求めて、求められたプロトタイプを入力データＸより遠ざかるように修正してもよい。このように修正を行うことによって、上述と同様にＮＮＣの認識（分類）精度の向上を図り、各プロトタイプが最適な位置に修正される速度（収束速度）を向上させることが可能となる。
【００７１】
さらに、本発明に係る発明は、上述した多変数テスト関数生成システム１に限定されるものではなく、上述した多変数テスト関数生成システム１を構成する演算処理部３部分を多変数テスト関数生成装置として抽出したものであっても、本発明に係る効果を奏することができ、さらに、上述した多変数テスト関数を生成するために演算処理部が上記処理を実行するためのコンピュータプログラムや、その処理を実現させる多変数テスト関数生成方法も同様に本発明に含まれるものである。
【００７２】
また、上述した実施形態では、演算処理部３が、図１に示すように、訓練用データを取得するための訓練用データ取得手段としての機能（訓練用データ取得機能６）や、最近傍となる分類データ（プロトタイプ）を求める最近傍分類データ検出手段としての機能（最近傍分類データ検出機能７）や、取得した分類データ（プロトタイプ）と訓練用データ（入力データ）とのクラスの同一性を判断するクラス判断手段としての機能（クラス判断機能８）や、クラスが同一か否かによって分類データ（プロトタイプ）の修正を行う分類データ修正手段としての機能（分類データ修正機能９）や、使用確率変数を各訓練用データに付与する使用確率変更手段としての機能（使用確率変更機能１０）や、修正が行われた分類データ（プロトタイプ）を用いて多変数テスト関数を生成するテスト関数生成手段としての機能（テスト関数生成機能１１）を果たすこととしたが、必ずしも全ての機能を１つの演算処理部が処理する必要はなく、物理的に異なる複数の演算処理部を用いて処理を行っても良いし、いくつかの処理を１つの演算処理部でまとめることによって２〜３個の演算処理部により上述した処理を行うような構成としても良い。
【００７３】
さらに、本発明は、多変数テスト関数生成装置、多変数テスト関数生成システム、多変数テスト関数生成方法および多変数テスト関数を生成するためのプログラムに関するものであるが、本発明に係るこれらの装置などは、多変数決定木の構築のみならず、通常の最近傍識別器（ＮＮＣ）の設計及びＮＮＣに基づく各種ニューラルネットワークの学習に利用することも可能である。
【図面の簡単な説明】
【００７４】
【図１】本発明に係る多変数テスト関数生成システムを示したブロック図である。
【図２】演算制御部が訓練用データに最適なプロトタイプを求める過程を説明するために用いた図である。
【図３】演算制御部がＮＮＣを生成する過程を示したフローチャートである。
【図４】演算制御部がＮＮＣを生成する過程を示した他のフローチャートである。
【図５】一般的なｉｆ−ｔｈｅｎルールに基づいて判断がなされる決定木の構造を示した図である。
【図６】図５に示した決定木における決定境界を２次元の平面により示した図である。
【符号の説明】
【００７５】
１     …多変数テスト関数生成システム
２     …訓練用データ記録部
３     …演算処理部（多変数テスト関数生成装置、訓練用データ取得手段、分類データ記録手段、最近傍分類データ検出手段、クラス判断手段、分類データ修正手段、使用確率変更手段、テスト関数生成手段）
４     …多変数テスト関数記録部
【図１】
2007213442.tif 000005
【図２】
2007213442.tif 000006
【図３】
2007213442.tif 000007
【図４】
2007213442.tif 000008
【図５】
2007213442.tif 000009
【図６】
2007213442.tif 000010