Top > Search of Japanese Patents > MULTIVARIABLE TEST FUNCTION GENERATION DEVICE, MULTIVARIABLE TEST FUNCTION GENERATION SYSTEM, MULTIVARIABLE TEST FUNCTION GENERATION METHOD AND PROGRAM FOR GENERATING MULTIVARIABLE TEST FUNCTION

MULTIVARIABLE TEST FUNCTION GENERATION DEVICE, MULTIVARIABLE TEST FUNCTION GENERATION SYSTEM, MULTIVARIABLE TEST FUNCTION GENERATION METHOD AND PROGRAM FOR GENERATING MULTIVARIABLE TEST FUNCTION commons

Patent code P110002671
Posted date May 24, 2011
Application number P2006-034344
Publication number P2007-213442A
Patent number P4997525
Date of filing Feb 10, 2006
Date of publication of application Aug 23, 2007
Date of registration May 25, 2012
Inventor
  • (In Japanese)趙 強福
Applicant
  • (In Japanese)公立大学法人会津大学
Title MULTIVARIABLE TEST FUNCTION GENERATION DEVICE, MULTIVARIABLE TEST FUNCTION GENERATION SYSTEM, MULTIVARIABLE TEST FUNCTION GENERATION METHOD AND PROGRAM FOR GENERATING MULTIVARIABLE TEST FUNCTION commons
Abstract

PROBLEM TO BE SOLVED: To generate understandable multivariable test functions for shortening a calculation amount and a calculation time for construction.

SOLUTION: This multivariable test function generation system 1 is configured to generate multivariable test functions for classifying input data having the element data of a plurality of elements into a plurality of clusters. The multivariable test function generation system 1 is provided with: a data for training recording means 2 for recording data for training; a multivariable test function generation means 3 for correcting classification data, based on the data for training, and for generating multivariable test functions, based on the corrected classification data; and a multivariable test function recording means 4 for recording the generated multivariable test functions.

Outline of related art and contending technology (In Japanese)


近年、コンピュータを用いた判断処理が日常的に使用されるようになってきた。コンピュータによる一般的な判断方法には、いわゆるif-thenルールが用いられている。



複数のif-thenルールを効率よく、わかりやすくまとめる方法としては、決定木(ツリー構造)がある。図5は、決定木の一例を示している。図5に示す決定木は決定結果(クラス)Class0,Class1を持つ終端節点(c1~c4)と単一変数テスト関数(UTF:Univariate Test Function)を使って局所的な判断を行う非終端節点(a1、b1,b2)とにより構成されている。コンピュータが何らかの判断を行う場合には、最上位にある非終端節点a1(ルート)より単一テスト関数による判断に基づいて子節点(下位節点)へと判断分類を行い、最終的に終端節点における決定結果に基づいて判断を行う。



例えば、入力データ:X=(0.1、0.8)として、図5に示す決定木を用いてClass0又はClass1の分類を行う場合を考える。まず、コンピュータは、最上位にある非終端節点a1(ルート)におけるテスト関数:X1<0.5?に基づく判断を行う。入力データ:X=(0.1、0.8)より第1のX要素(X1)=0.1は、0.5よりも小さくなるのでX1<0.5の条件を満たすものと判断され、ルートの下位の非終端節点であってルートのテスト関数を満たす場合に次の判断が求められる非終端節点b1へと処理が移行する。



そしてコンピュータは、非終端節点b1におけるテスト関数:X2<0.5?に基づく判断を行う。入力データ:X=(0.1、0.8)より第2のX要素(X2)=0.8は、0.5よりも大きいので、X2<0.5?の条件を満たさず、非終端節点b1の下位の終端節点であって決定結果としてClass1を備える終端節点C2へと処理が移行する。コンピュータは終端節点c2において決定結果としてClass1の決定結果を取得して、入力データ:XがClass1であると判断する。



このように、各非終端節点で単一変数テスト関数を用いて判断を行わせることによって、判断内容をif-thenルールで示すことができるので、理解しやすいという特徴がある。



なお、このような単一変数テスト関数に対応する決定結果の境界は、座標軸に平行なものとなる(図6参照)ので、通常の決定木はAPDT(Axis-Parallel Decision Tree)とも呼ばれる。ADTPを構築する既存の方法として、CART(例えば、特許文献1参照)やC4.5(例えば、非特許文献2参照)等が知られている。



しかしながら、単一変数テスト関数を用いて判断処理を行うAPDTでは、判断を行うためのデータ数が一定以上になると性能(認識率など)が飽和してしまうとともに、決定木のサイズ(節点の数等)がデータ数に比例して大きくなってしまう(例えば、非特許文献3参照)。このため、決定木のサイズが大きくなり節点数が増加すると、対応するif-thenルールが非常に長くなり、理解が困難なものとなってしまうという問題があった。



一方で、決定木のサイズを減らす方法として、各非終端節点において多変数テスト関数(MTF:Multivariate Test function)を用いることにより節点数を減らす方法も提案されている。多変数テスト関数を利用した決定木の中でよく知られているものがODT(Oblique Decision Tree)である。ODTでは次式に示す式1のようなテスト関数が用いられている。
【数式1】


・・・・・(1)
ここで、Ndは特徴(テスト関数において分類が行われる入力データの要素)の数、xiはi番目の特徴、wiはi番目の重み係数、θは閾値である。通常、F(X)<0の場合、xを左子節点に割り当て、F(X)≧0の場合、xを右子節点に割り当てる。このようなF(X)に対応する決定境界は一般の超平面となるので、APDTよりもODTの方が効率よくデータを分類することができる。

【非特許文献1】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.

【非特許文献2】J. R. Quinlan, C4.5: Programs for Machine Learning, Morgan Kauffman Publishers, 1993.

【非特許文献3】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.

Field of industrial application (In Japanese)


本発明は、複数要素の要素データを有する複数の入力データを複数のクラスに分類する多変数テスト関数を生成するための多変数テスト関数生成装置、多変数テスト関数生成システム、多変数テスト関数生成方法および多変数テスト関数を生成するためのプログラムに関する。

Scope of claims (In Japanese)
【請求項1】
 
複数要素の要素データを有する複数の入力データを複数のクラスに分類するための多変数テスト関数を生成する多変数テスト関数生成装置であって、
予め要素データと分類されるべきクラスとが既知である入力データからなる訓練用データを取得する訓練用データ取得手段と、
前記要素データに対応するデータ情報と前記クラスを示すクラス情報とを有する複数の分類データを記録する分類データ記録手段と、
前記要素データの要素数に基づいて当該要素数に対応する複数次元の特徴空間を構成し、前記訓練用データの要素データの値を前記特徴空間の空間座標として判断するとともに、前記分類データ記録手段に記録される前記分類データのデータ情報の値を前記特徴空間の空間座標として判断し、前記訓練用データの空間座標と前記分類データの空間座標との距離が最小となる分類データを求める最近傍分類データ検出手段と、
該最近傍分類データ検出手段により求められた分類データのクラス情報と前記訓練用データのクラスとが同一クラスであるか否かを判断するクラス判断手段と、
該クラス判断手段により前記分類データのクラス情報と前記訓練用データのクラスとが異なるクラスであると判断された場合に、前記分類データ記録手段に記録される当該分類データのデータ情報を前記要素データの空間座標から遠ざかるように修正するとともに、前記クラス判断手段により前記訓練用データと同一クラスであると判断される他の分類データを前記最近傍分類データ検出手段により検出させ、前記分類データ記録手段に記録される当該他の分類データのデータ情報を前記要素データの空間座標に近づくように修正する分類データ修正手段と、
前記最近傍分類データ検出手段により検出された最近傍となる前記分類データのクラス情報が前記クラス判断手段により前記訓練用データのクラスと同一であると判断された場合に値が減少する使用確率変数を、前記訓練用データ毎に付与する使用確率変更手段と、
前記分類データ修正手段により修正がなされた分類データのデータ情報とクラス情報とに基づいて前記多変数テスト関数を生成するテスト関数生成手段と
を有し、
前記最近傍分類データ検出手段は、前記使用確率変数の値が所定値以上を示す前記訓練用データのみを用いて前記分類データの検出を行うこと
を特徴とする多変数テスト関数生成装置。

【請求項2】
 
複数要素の要素データを有する複数の入力データを複数のクラスに分類するための多変数テスト関数を生成する多変数テスト関数生成装置であって、
予め要素データと分類されるべきクラスとが既知である入力データからなる訓練用データを取得する訓練用データ取得手段と、
前記要素データに対応するデータ情報と前記クラスを示すクラス情報とを有する複数の分類データを記録する分類データ記録手段と、
前記要素データの要素数に基づいて当該要素数に対応する複数次元の特徴空間を構成し、前記訓練用データの要素データの値を前記特徴空間の空間座標として判断するとともに、前記分類データ記録手段に記録される前記分類データのデータ情報の値を前記特徴空間の空間座標として判断し、前記訓練用データの空間座標と前記分類データの空間座標との距離が最小となる分類データを求める最近傍分類データ検出手段と、
該最近傍分類データ検出手段により求められた分類データのクラス情報と前記訓練用データのクラスとが同一クラスであるか否かを判断するクラス判断手段と、
該クラス判断手段により前記分類データのクラス情報と前記訓練用データのクラスとが同一クラスであると判断された場合に、前記分類データ記録手段に記録される当該分類データのデータ情報を前記要素データの空間座標に近づくように修正する分類データ修正手段と、
前記最近傍分類データ検出手段により検出された最近傍となる前記分類データのクラス情報が前記クラス判断手段により前記訓練用データのクラスと同一であると判断された場合に値が減少する使用確率変数を、前記訓練用データ毎に付与する使用確率変更手段と、
前記分類データ修正手段により修正がなされた分類データのデータ情報とクラス情報とに基づいて前記多変数テスト関数を生成するテスト関数生成手段と
を有し、
前記最近傍分類データ検出手段は、前記使用確率変数の値が所定値以上を示す前記訓練用データのみを用いて前記分類データの検出を行うこと
を特徴とする多変数テスト関数生成装置。

【請求項3】
 
複数要素の要素データを有する入力データを複数のクラスに分類するための多変数テスト関数を生成する多変数テスト関数生成システムであって、
前記多変数テスト関数は、前記要素データに対応するデータ情報と前記クラスを示すクラス情報とを有する複数の分類データからなり、
前記多変数テスト関数生成システムは、
予め要素データと分類されるべきクラスとが既知である入力データを訓練用データとして記録する訓練用データ記録手段と、
前記要素データの要素数に基づいて当該要素数に対応する複数次元の特徴空間を構成し、前記訓練用データの要素データの値を前記特徴空間の空間座標として判断するとともに、前記分類データのデータ情報の値を前記特徴空間の空間座標として判断することによって、前記訓練用データの空間座標までの距離が最小となる最近傍の分類データを求め、当該訓練用データと求められた最近傍の分類データとが同一のクラスとなるように前記分類データの空間位置を修正することにより前記分類データのデータ情報の修正を行い、修正がなされた分類データのデータ情報とクラス情報とに基づいて前記多変数テスト関数を生成する多変数テスト関数生成手段と、
生成された多変数テスト関数を記録する多変数テスト関数記録手段と
を備え、
前記多変数テスト関数生成手段は、最近傍となる前記分類データのクラス情報が前記訓練用データのクラスと同一であった場合に値が減少する使用確率変数を前記訓練用データ毎に付与し、前記使用確率変数が所定値以上を示す前記訓練用データを用いて前記分類データのデータ情報の修正処理を行う
ことを特徴とする多変数テスト関数生成システム。



【請求項4】
 
前記多変数テスト関数生成手段は、
前記訓練用データの要素データにおける空間座標から最近傍となる分類データのクラス情報が前記訓練用データのクラスと異なる場合に、当該分類データのデータ情報を前記要素データの空間座標から遠ざかるように修正し、
さらに前記訓練用データと同一クラスのクラス情報を有する分類データのうち、前記要素データの空間座標に最近傍となる他の分類データを求めて、当該他の分類データのデータ情報を前記要素データの空間座標に近づくように修正する
ことを特徴とする請求項3に記載の多変数テスト関数生成システム。

【請求項5】
 
前記多変数テスト関数生成手段は、
前記訓練用データの要素データにおける空間座標から最近傍となる分類データのクラス情報が前記訓練用データのクラスと同一の場合に、当該分類データのデータ情報を前記要素データの空間座標に近づくように修正する
ことを特徴とする請求項3に記載の多変数テスト関数生成システム。

【請求項6】
 
複数要素の要素データを有する複数の入力データを複数のクラスに分類するための多変数テスト関数を生成する多変数テスト関数生成方法であって、
訓練用データ取得手段が、予め要素データと分類されるべきクラスとが既知である入力データからなる訓練用データを取得する訓練用データ取得ステップと、
最近傍分類データ検出手段が、前記訓練用データ取得手段により取得された前記要素データの要素数に基づいて、当該要素数に対応する複数次元の特徴空間を構成し、前記訓練用データの要素データの値を前記特徴空間の空間座標として判断するとともに、前記要素データに対応するデータ情報と前記クラスを示すクラス情報とを有する複数の分類データを、当該分類データのデータ情報の値に基づいて前記特徴空間の空間座標として判断し、前記訓練用データの空間座標と前記分類データの空間座標との距離が最小となる分類データを求める最近傍分類データ検出ステップと、
クラス判断手段が、最近傍分類データ検出手段により求められた分類データのクラス情報と前記訓練用データのクラスとが同一クラスであるか否かを判断するクラス判断ステップと、
前記クラス判断手段により前記分類データのクラス情報と前記訓練用データのクラスとが異なるクラスであると判断された場合に、分類データ修正手段が当該分類データのデータ情報を前記要素データの空間座標から遠ざかるように修正するとともに、前記クラス判断手段により前記訓練用データと同一クラスであると判断される他の分類データを前記最近傍分類データ検出手段により検出させ、当該他の分類データのデータ情報を前記要素データの空間座標に近づくように修正する分類データ修正ステップと、
前記最近傍分類データ検出手段により検出された最近傍となる前記分類データのクラス情報が前記クラス判断手段により前記訓練用データのクラスと同一であると判断された場合に値を減少させる使用確率変数を、使用確率変更手段が前記訓練用データ毎に付与する使用確率変更ステップと、
テスト関数生成手段が、前記分類データ修正手段により修正がなされた分類データのデータ情報とクラス情報とに基づいて入力データの分類を行う多変数テスト関数を生成するテスト関数生成ステップと
を有し、
最近傍分類データ検出ステップにおいて、前記使用確率変数の値が所定値以上を示す前記訓練用データのみを用いて前記最近傍分類データ検出手段が前記分類データの検出を行うこと
を特徴とする多変数テスト関数生成方法。

【請求項7】
 
複数要素の要素データを有する複数の入力データを複数のクラスに分類するための多変数テスト関数を生成する多変数テスト関数生成方法であって、
訓練用データ取得手段が、予め要素データと分類されるべきクラスとが既知である入力データからなる訓練用データを取得する訓練用データ取得ステップと、
最近傍分類データ検出手段が、前記訓練用データ取得手段により取得された前記要素データの要素数に基づいて、当該要素数に対応する複数次元の特徴空間を構成し、前記訓練用データの要素データの値を前記特徴空間の空間座標として判断するとともに、前記要素データに対応するデータ情報と前記クラスを示すクラス情報とを有する複数の分類データを、当該分類データのデータ情報の値に基づいて前記特徴空間の空間座標として判断し、前記訓練用データの空間座標と前記分類データの空間座標との距離が最小となる分類データを求める最近傍分類データ検出ステップと、
クラス判断手段が、最近傍分類データ検出手段により求められた分類データのクラス情報と前記訓練用データのクラスとが同一クラスであるか否かを判断するクラス判断ステップと、
該クラス判断手段により前記分類データのクラス情報と前記訓練用データのクラスとが同一クラスであると判断された場合に、分類データ修正手段が当該分類データのデータ情報を前記要素データの空間座標に近づくように修正する分類データ修正ステップと、
前記最近傍分類データ検出手段により検出された最近傍となる前記分類データのクラス情報が前記クラス判断手段により前記訓練用データのクラスと同一であると判断された場合に値を減少させる使用確率変数を、使用確率変更手段が前記訓練用データ毎に付与する使用確率変更ステップと、
テスト関数生成手段が、前記分類データ修正手段により修正がなされた分類データのデータ情報とクラス情報とに基づいて入力データの分類を行う多変数テスト関数を生成するテスト関数生成ステップと
を有し、
前記最近傍分類データ検出ステップにおいて、前記使用確率変数の値が所定値以上を示す前記訓練用データのみを用いて前記最近傍分類データ検出手段が前記分類データの検出を行うこと
を特徴とする多変数テスト関数生成方法。

【請求項8】
 
複数要素の要素データを有する複数の入力データを複数のクラスに分類するための多変数テスト関数を生成するために、コンピュータに、
予め要素データと分類されるべきクラスとが既知である入力データからなる訓練用データを、訓練用データ取得手段により取得させる訓練用データ取得ステップと、
該訓練用データ取得ステップにおいて取得された前記要素データの要素数に基づいて、最近傍分類データ検出手段により当該要素数に対応する複数次元の特徴空間を構成させ、前記訓練用データの要素データの値を前記特徴空間の空間座標として判断させるとともに、前記要素データに対応するデータ情報と前記クラスを示すクラス情報とを有する複数の分類データを、当該分類データのデータ情報の値に基づいて前記特徴空間の空間座標として判断させ、前記訓練用データの空間座標と前記分類データの空間座標との距離が最小となる分類データを求めさせる最近傍分類データ検出ステップと、
該最近傍分類データ検出ステップにおいて求められた分類データのクラス情報と前記訓練用データのクラスとが同一クラスであるか否かを、クラス判断手段により判断させるクラス判断ステップと、
該クラス判断ステップにおいて前記分類データのクラス情報と前記訓練用データのクラスとが異なるクラスであると判断された場合に、分類データ修正手段により当該分類データのデータ情報を前記要素データの空間座標から遠ざかるように修正させるとともに、前記クラス判断ステップにおいて前記訓練用データと同一クラスであると判断される他の分類データを前記最近傍分類データ検出ステップにより検出させ、当該他の分類データのデータ情報を前記要素データの空間座標に近づくように修正させる分類データ修正ステップと、
前記最近傍分類データ検出ステップにおいて検出された最近傍となる前記分類データのクラス情報が前記クラス判断ステップにおいて前記訓練用データのクラスと同一であると判断された場合に値を減少させる使用確率変数を、使用確率変更手段により前記訓練用データ毎に付与させる使用確率変更ステップと、
前記分類データ修正ステップにおいて修正がなされた分類データのデータ情報とクラス情報とに基づいて入力データの分類を行う多変数テスト関数を、テスト関数生成手段により生成させるテスト関数生成ステップと
を実行させ、
さらに、前記最近傍分類データ検出ステップにおいて、前記使用確率変数の値が所定値以上を示す前記訓練用データのみを用いて前記最近傍分類データ検出手段に前記分類データの検出を行わせる
ことを特徴とする多変数テスト関数を生成するためのプログラム。

【請求項9】
 
複数要素の要素データを有する複数の入力データを複数のクラスに分類するための多変数テスト関数を生成するために、コンピュータに、
予め要素データと分類されるべきクラスとが既知である入力データからなる訓練用データを、訓練用データ取得手段により取得させる訓練用データ取得ステップと、
該訓練用データ取得ステップにおいて取得された前記要素データの要素数に基づいて、最近傍分類データ検出手段により当該要素数に対応する複数次元の特徴空間を構成させ、前記訓練用データの要素データの値を前記特徴空間の空間座標として判断させるとともに、前記要素データに対応するデータ情報と前記クラスを示すクラス情報とを有する複数の分類データを、前記分類データのデータ情報の値に基づいて前記特徴空間の空間座標として判断させ、前記訓練用データの空間座標と前記分類データの空間座標との距離が最小となる分類データを求める最近傍分類データ検出ステップと、
該最近傍分類データ検出ステップにおいて求められた分類データのクラス情報と前記訓練用データのクラスとが同一クラスであるか否かを、クラス判断手段により判断させるクラス判断ステップと、
該クラス判断ステップにおいて前記分類データのクラス情報と前記訓練用データのクラスとが同一クラスであると判断された場合に、分類データ修正手段により当該分類データのデータ情報を前記要素データの空間座標に近づくように修正させる分類データ修正ステップと、
前記最近傍分類データ検出ステップにおいて検出された最近傍となる前記分類データのクラス情報が前記クラス判断ステップにおいて前記訓練用データのクラスと同一であると判断された場合に値を減少させる使用確率変数を、使用確率変更手段により前記訓練用データ毎に付与させる使用確率変更ステップと、
前記分類データ修正ステップにおいて修正がなされた分類データのデータ情報とクラス情報とに基づいて入力データの分類を行う多変数テスト関数を、テスト関数生成手段により生成させるテスト関数生成ステップと
を実行させ、
さらに、前記最近傍分類データ検出ステップにおいて、前記使用確率変数の値が所定値以上を示す前記訓練用データのみを用いて前記最近傍分類データ検出手段に前記分類データの検出を行わせる
ことを特徴とする多変数テスト関数を生成するためのプログラム。
Industrial division
  • Computation controlling device
IPC(International Patent Classification)
Drawing

※Click image to enlarge.

JP2006034344thum.jpg
State of application right Right is in force
(In Japanese)本技術について、ライセンスや共同研究等をご希望の方は、下記「問合せ先」まで直接お問い合わせください。


PAGE TOP

close
close
close
close
close
close
close