Top > Search of Japanese Patents > MULTIVARIABLE DECISION TREE CONSTRUCTION SYSTEM, MULTIVARIABLE DECISION TREE CONSTRUCTION METHOD AND PROGRAM FOR CONSTRUCTING MULTIVARIABLE DECISION TREE

MULTIVARIABLE DECISION TREE CONSTRUCTION SYSTEM, MULTIVARIABLE DECISION TREE CONSTRUCTION METHOD AND PROGRAM FOR CONSTRUCTING MULTIVARIABLE DECISION TREE commons

Patent code P110002670
Posted date May 24, 2011
Application number P2006-034343
Publication number P2007-213441A
Patent number P4997524
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 DECISION TREE CONSTRUCTION SYSTEM, MULTIVARIABLE DECISION TREE CONSTRUCTION METHOD AND PROGRAM FOR CONSTRUCTING MULTIVARIABLE DECISION TREE commons
Abstract

PROBLEM TO BE SOLVED: To provide a multivariable decision tree construction system for shortening computational complexity and a calculation time for constructing a multivariable decision tree (MDT), and for easily understanding the decision content of the MDT.

SOLUTION: This multivariable decision tree construction system 1 is configured to construct a multivariable decision tree where multivariable test functions for dividing data are installed in every non-terminal end node by using a plurality of data for training equipped with element data. The multivariable decision tree construction system 1 is provided with a group label applying means 2 for applying the group label information showing groups into which the data should be divided in the non-terminal end nodes to data for training in every non-terminal end node. A multivariable test function generating means 2 corrects classification data, based on the group label information, and generates the multivariable test functions for every non-terminal node, based on the corrected classification data.

Outline of related art and contending technology (In Japanese)


近年、コンピュータを用いた判断処理が日常的に使用されるようになってきた。コンピュータによる一般的な判断方法には、いわゆるif-thenルールが用いられている。多数のif-thenルールを効率よく、理解しやすくまとめる方法の一つとして、決定木がある。



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



例えば、入力データ:X=(0.1、0.8)として、図22に示す決定木を用いてClass0又はClass1の分類を行う場合を考える。まず、コンピュータは、最上位にある非終端節点a1(ルート)におけるテスト関数:X1<0.5?に基づく判断を行う。入力データ:X=(0.1、0.8)より第1のX要素(x1)=0.1は、0.5よりも小さくなるのでx1<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ルールで示すことができるので、処理内容が理解しやすくなると共に、判断処理の修正を簡単に行うことができるという利点がある。



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



APDTの構築における終端節点の判別は、通常、割り当てられたデータが全て同じクラスに属しているか、あるいは大部分のデータが既に同じクラスに属しているかによって行う。終端節点のクラスは多数決で決められる。



非終端節点におけるテスト関数を評するためには、一般的に評価関数を用いた評価が行われている。評価関数は、現在まで何種類も提案されているが、どれを使っても構築された決定木の性能はあまり変わらないことが知られている(非特許文献1)。C4.5においては、評価関数として情報利得率(IGR: Information Gain Ratio)が使用されている。



情報利得率は、現在節点に割り当てた訓練用データの集合をS、そのうちi番目のクラスに属するデータの数をniとする。与えられたデータのクラスを識別するために必要とされる平均情報量は以下のように定義する:
【数式1】


・・・・・(1)
ただし、Ncはクラスの数、|S|はSのサイズである。



あるテスト関数Fを基にSをN個のグループS1,S2,・・・SNに分割した場合、情報利得(IG: Information Gain)は次式で求められる。
IG(F)=Info(S)-Info(F,S)
・・・・・(2)
ただし、
【数式2】


・・・・・(3)
と定義する。情報利得(IG)もテスト関数の分割能力を評価する一つの基準であるが、情報利得を用いて決定木の分割能力を評価すると、決定木のバランスがあまりよくならないことが知られている。



そのため、情報利得の代わりとなる評価関数として、IGRが提案されている。テスト関数FのIGRは以下の式で示される。
【数式3】


・・・・・(4)
ただし、
【数式4】


・・・・・(5)
APDTにおけるテスト関数は、上述のようにXi<aの形式を通常とることとなる。ここでXiはi番目の特徴で、aは閾値を意味している。従ってAPDTを構築する際にテスト関数を求めることは、評価関数を最適にするように、iとaとを求めることに等しい。この最も単純な方法は、全ての特徴とその特徴が取り得る全ての値を調べ尽す方法である。実際、最適なテスト関数を求めるための計算量は、
Cost(ADPT)=O(Nd×Nt×m)
・・・・・(6)
で示される。



ここでNdは特徴空間の次元(特徴の数)、Ntは現在節点に割り当てられたデータの数、mは特徴が取り得る値の数で、記号O()は「比例する」と読むことができる。最悪の場合はm=Ntである。



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



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


・・・・(7)



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



ODTを構築する方法がいくつか提案されているが、その中で最も効率がよいと思われる方法はOC1である(例えば、非特許文献4参照)。OC1では、まず最適なUTFを求め、そこから局所検索を行ってよりよいMTFを求める。局所検索が局所最適値(Local Optimal)におちついた場合、小さな外乱を用いてよりよい最適値を求めることによって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.

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

Field of industrial application (In Japanese)


本発明は、要素データを備えた複数の訓練用データを用いて、データの分割を行うための多変数テスト関数が非終端節点毎に設けられた多変数決定木を構築する多変数決定木構築システム、多変数決定木構築方法および多変数決定木を構築するためのプログラムに関する。

Scope of claims (In Japanese)
【請求項1】
 
要素データを備えた複数の訓練用データを用いて、データの分割を行うための多変数テスト関数が非終端節点毎に設けられた多変数決定木を構築する多変数決定木構築システムであって、
前記多変数テスト関数は、前記要素データに対応するデータ情報と、前記非終端節点においてデータが分割されるべきグループを示すグループラベルのラベル情報とを有する複数の分類データからなり、
前記多変数決定木構築システムは、
前記非終端節点においてデータが分割されるべきグループを示すグループラベル情報を、当該非終端節点毎に前記訓練用データに付与するグループラベル付与手段と、
前記要素データの要素数に基づいて当該要素数に対応する複数次元の特徴空間を構成し、前記訓練用データの要素データの値を前記特徴空間の空間座標として判断するとともに、前記分類データのデータ情報の値を前記特徴空間の空間座標として判断することによって、前記訓練用データの空間座標までの距離が最小となる最近傍の分類データを求め、前記訓練用データと求められた前記最近傍の分類データとが同一のグループラベルでない場合には、当該最近傍の分類データの空間座標を前記訓練用データの空間座標から遠ざけるように修正し、さらに、前記訓練用データと同一のグループラベルとなる分類データのうち最近傍となる分類データを求めて当該分類データの空間座標を前記訓練用データの空間座標に近づけるように修正することによって、最近傍の分類データが前記訓練用データと同一のグループラベルになるまで前記分類データの空間座標の修正を繰り返すことにより前記分類データのデータ情報の修正を行い、最近傍の分類データが前記訓練用データと同一のグループラベルになるまで修正がなされた分類データのデータ情報とラベル情報とに基づいて前記非終端節点毎に前記多変数テスト関数を生成する多変数テスト関数生成手段と
を備えることを特徴とする多変数決定木構築システム。

【請求項2】
 
前記訓練用データは前記多変数決定木により最終的に分割されるべきクラスを示すクラス情報を有し、
前記グループラベル付与手段は、前記クラス情報に基づいて前記訓練用データのグループラベルを決定し、当該クラス情報により前記グループラベルを決定することができない訓練用データが存在する場合には、既にグループラベルが付与された訓練用データであってグループラベルを決定することができない訓練用データに最近傍となる訓練用データと同じグループラベルを、前記グループラベルを決定できなかった訓練用データに付与する
ことを特徴とする請求項1に記載の多変数決定木構築システム。

【請求項3】
 
前記多変数テスト関数生成手段により生成された多変数テスト関数の分割性能を情報利得に基づいて判断し、当該分割性能が既定値未満である場合には当該多変数テスト関数が生成された非終端節点を終端節点に変更する早期停止判断手段
を備えることを特徴とする請求項1または請求項2に記載の多変数決定木構築システム。

【請求項4】
 
前記訓練用データは前記多変数決定木により最終的に分割されるべきクラスを示すクラス情報を有し、
前記グループラベル付与手段により前記訓練用データに前記グループラベルを付与する前に、該当する節点が終端節点であるか非終端節点であるかを判断し、当該節点が終端節点である場合には当該終端節点の分割結果を前記訓練用データが有するクラス情報に基づいて決定する終端節点判別手段
を備えることを特徴とする請求項1ないし請求項3のいずれか1項に記載の多変数決定木構築システム。

【請求項5】
 
前記多変数テスト関数生成手段は、生成される多変数テスト関数に含まれる分類データの数と分類データのラベル情報とが不明である場合に、該当する節点の多変数テスト関数をR4-Rule学習則を用いて生成する
ことを特徴とする請求項1ないし請求項4のいずれか1項に記載の多変数決定木構築システム。

【請求項6】
 
要素データを備えた複数の訓練用データを用いて、データの分割を行うための多変数テスト関数が非終端節点毎に設けられた多変数決定木を構築する多変数決定木構築方法であって、
前記非終端節点においてデータが分割されるべきグループを示すグループラベル情報を、当該非終端節点毎にグループラベル付与手段が前記訓練用データに付与するグループラベル付与ステップと、
多変数テスト関数生成手段が、前記訓練用データの前記要素データの要素数に基づいて当該要素数に対応する複数次元の特徴空間を構成し、前記訓練用データの要素データの値を前記特徴空間の空間座標として判断するとともに、前記要素データに対応するデータ情報と前記グループラベルを示すラベル情報とを有する分類データを、当該分類データのデータ情報の値に基づいて前記特徴空間の空間座標として判断し、前記訓練用データの空間座標と前記分類データの空間座標との距離が最小となる最近傍の分類データを求め、前記訓練用データと求められた前記最近傍の分類データとが同一のグループラベルでない場合には、当該最近傍の分類データの空間座標を前記訓練用データの空間座標から遠ざけるように修正し、さらに、前記訓練用データと同一のグループラベルとなる分類データのうち最近傍となる分類データを求めて当該分類データの空間座標を前記訓練用データの空間座標に近づけるように修正することによって、最近傍の分類データが前記訓練用データと同一のグループラベルになるまで前記分類データの空間座標の修正を繰り返すことにより前記分類データのデータ情報の修正を行い、最近傍の分類データが前記訓練用データと同一のグループラベルになるまで修正がなされた分類データのデータ情報とラベル情報とに基づいて前記非終端節点毎に前記多変数テスト関数を生成する多変数テスト関数生成ステップと
を備えることを特徴とする多変数決定木構築方法。

【請求項7】
 
前記訓練用データが前記多変数決定木により最終的に分割されるべきクラスを示すクラス情報を有し、
前記グループラベル付与ステップにおいて、前記グループラベル付与手段は、前記クラス情報に基づいて前記訓練用データのグループラベルを決定し、当該クラス情報により前記グループラベルを決定することができない訓練用データが存在する場合には、既にグループラベルが付与された訓練用データであってグループラベルを決定することができない訓練用データに最近傍となる訓練用データと同じグループラベルを、前記グループラベルを決定できなかった訓練用データに付与する
ことを特徴とする請求項6に記載の多変数決定木構築方法。

【請求項8】
 
早期停止判断手段が、前記多変数テスト関数生成手段により生成された多変数テスト関数の分割性能を情報利得に基づいて判断し、当該分割性能が既定値未満である場合には当該多変数テスト関数が生成された非終端節点を終端節点に変更する終端節点変更ステップ
を備えることを特徴とする請求項6または請求項7に記載の多変数決定木構築方法。

【請求項9】
 
前記訓練用データが前記多変数決定木により最終的に分割されるべきクラスを示すクラス情報を有し、
前記グループラベル付与ステップにおいて前記訓練用データに前記グループラベルを付与する前に、終端節点判別手段が該当する節点が終端節点であるか非終端節点であるかを判断し、当該節点が終端節点である場合には当該終端節点の分類結果を前記訓練用データが有するクラス情報に基づいて決定する終端節点判別ステップ
を備えることを特徴とする請求項6ないし請求項8のいずれか1項に記載の多変数決定木構築方法。

【請求項10】
 
前記多変数テスト関数生成ステップにおいて、生成される多変数テスト関数に含まれる分類データの数と分類データのラベル情報とが不明である場合には、前記多変数テスト関数生成手段が、該当する節点の多変数テスト関数をR4-Rule学習則を用いて生成する
ことを特徴とする請求項6ないし請求項9のいずれか1項に記載の多変数決定木構築方法。

【請求項11】
 
要素データを備えた複数の訓練用データを用いて、データの分割を行うための多変数テスト関数が非終端節点毎に設けられる多変数決定木を構築するために、コンピュータに、
前記非終端節点においてデータが分割されるべきグループを示すグループラベル情報を、当該非終端節点毎にグループラベル付与手段が前記訓練用データに付与するグループラベル付与ステップと、
多変数テスト関数生成手段が、前記訓練用データの前記要素データの要素数に基づいて当該要素数に対応する複数次元の特徴空間を構成し、前記訓練用データの要素データの値を前記特徴空間の空間座標として判断するとともに、前記要素データに対応するデータ情報と前記グループラベルを示すラベル情報とを有する分類データを、当該分類データのデータ情報の値に基づいて前記特徴空間の空間座標として判断し、前記訓練用データの空間座標と前記分類データの空間座標との距離が最小となる最近傍の分類データを求め、前記訓練用データと求められた前記最近傍の分類データとが同一のグループラベルでない場合には、当該最近傍の分類データの空間座標を前記訓練用データの空間座標から遠ざけるように修正し、さらに、前記訓練用データと同一のグループラベルとなる分類データのうち最近傍となる分類データを求めて当該分類データの空間座標を前記訓練用データの空間座標に近づけるように修正することによって、最近傍の分類データが前記訓練用データと同一のグループラベルになるまで前記分類データの空間座標の修正を繰り返すことにより前記分類データのデータ情報の修正を行い、最近傍の分類データが前記訓練用データと同一のグループラベルになるまで修正がなされた分類データのデータ情報とラベル情報とに基づいて前記非終端節点毎に前記多変数テスト関数を生成する多変数テスト関数生成ステップと
を実行させることを特徴とする多変数決定木を構築するためのプログラム。

【請求項12】
 
前記訓練用データが前記多変数決定木により最終的に分割されるべきクラスを示すクラス情報を有し、
前記コンピュータに、
前記グループラベル付与ステップにおいて、前記グループラベル付与手段により前記クラス情報に基づいて前記訓練用データのグループラベルを決定させ、当該クラス情報により前記グループラベルを決定させることができない訓練用データが存在する場合には、既にグループラベルが付与された訓練用データであってグループラベルを決定することができない訓練用データに最近傍となる訓練用データと同じグループラベルを、前記グループラベルを決定できなかった訓練用データに付与させる
ことを特徴とする請求項11に記載の多変数決定木を構築するためのプログラム。

【請求項13】
 
前記コンピュータに、
早期停止判断手段により前記多変数テスト関数生成手段によって生成された多変数テスト関数の分割性能を情報利得に基づいて判断させ、当該分割性能が既定値未満である場合には当該多変数テスト関数が生成された非終端節点を終端節点に変更させる終端節点変更ステップ
を実行させることを特徴とする請求項11または請求項12に記載の多変数決定木を構築するためのプログラム。

【請求項14】
 
前記訓練用データが前記多変数決定木により最終的に分類されるべきクラスを示すクラス情報を有し、
前記コンピュータに、
前記グループラベル付与ステップにおいて前記訓練用データに前記グループラベルを付与する前に、終端節点判別手段により該当する節点が終端節点であるか非終端節点であるかを判断させ、当該節点が終端節点である場合には当該終端節点の分類結果を前記訓練用データが有するクラス情報に基づいて決定させる終端節点判別ステップ
を実行させることを特徴とする請求項11ないし請求項13のいずれか1項に記載の多変数決定木を構築するためのプログラム。

【請求項15】
 
前記コンピュータに、
前記多変数テスト関数生成ステップにおいて、生成される多変数テスト関数に含まれる分類データの数と分類データのラベル情報とが不明である場合には、前記多変数テスト関数生成手段により該当する節点の多変数テスト関数をR4-Rule学習則を用いて生成させる
ことを特徴とする請求項11ないし請求項14のいずれか1項に記載の多変数決定木を構築するためのプログラム。
Industrial division
  • Computation controlling device
IPC(International Patent Classification)
Drawing

※Click image to enlarge.

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


PAGE TOP

close
close
close
close
close
close
close