(57)【要約】【課題】  分類精度の高い分類木の生成を効率的に実行することを可能とした装置および方法を提供する。【解決手段】  分類木作成部の生成した分類木から分類精度向上に対する寄与度の低い属性を除外対象属性として決定し、除外対象属性を除く属性に基づく入力データ生成処理、分類木生成処理、および分類精度測定処理とを繰り返し実行して、繰り返し処理の中で生成する複数の分類木から分類精度のもっとも高い分類木を選択して出力する。本構成により、例えば分割数の大きい属性の除去による分類精度の向上が図られ、分類処理対象データの知識を持たない未知データに対しても、自動的に分類精度の高い分類木を効率的に生成することが可能となる。【選択図】  図１
2005208709.tif 000002
【特許請求の範囲】
【請求項１】
分類処理対象レコードに基づく分類木の生成に適用する属性情報データを生成する入力データ作成部と、
前記入力データ作成部の生成する属性情報データに基づく分類木を生成する分類木作成部と、
前記分類木作成部の生成した分類木の分類精度を測定する分類精度測定部と、
前記分類木作成部の生成した分類木から分類精度向上に対する寄与度の低い属性を除外対象属性として決定する除外対象属性決定部とを有し、
前記除外対象属性決定部における除外対象属性の決定処理と、除外対象属性を除く属性に基づく前記入力データ作成部における入力データ生成処理と、前記分類木作成部における分類木生成処理と、前記分類精度測定部における分類精度測定処理とを繰り返し実行し、
該繰り返し処理の中で生成する複数の分類木から分類精度のもっとも高い分類木を選択して出力する構成を有することを特徴とするデータ分類処理装置。
【請求項２】
前記分類木作成部は、
分類処理対象データから選択された学習用データに基づいて分類木を生成する構成であり、
前記分類精度測定部は、
前記学習用データに基づいて生成した分類木について、分類処理対象データから選択されたテスト用データを適用して分類精度を測定する構成であることを特徴とする請求項１に記載のデータ分類処理装置。
【請求項３】
前記分類木作成部は、
分類木作成処理プログラムに設定するパラメータＣ（枝刈りＣＦ値）を順次変更した複数の分類木の生成処理を実行する構成であり、
前記類精度測定部は、
前記分類木作成部の作成した異なるパラメータの値に対応する複数の分類木の分類精度測定処理を実行し、最高の分類精度を持つ分類木の分類精度が、異なる属性設定条件の下で生成した最高の分類精度を持つ分類木の分類精度より高い精度である場合に該分類木の情報を前記除外対象属性決定部に出力する構成であり、
前記除外対象属性決定部は、
前記分類木作成部の生成した分類木から分類精度向上に対する寄与度の低い属性を除外対象属性として決定する処理を実行する構成であることを特徴とする請求項１に記載のデータ分類処理装置。
【請求項４】
前記除外対象属性決定部は、
前記分類木作成部の生成した分類木の非葉構成ノードから、比較分割情報量が最大のノードを選択し、該選択ノードの子ノード作成時の適用属性を除外対象属性として決定する処理を実行する構成であることを特徴とする請求項１に記載のデータ分類処理装置。
【請求項５】
分類処理対象レコードに基づく分類木の生成に適用する属性情報データを生成する入力データ作成ステップと、
前記入力データ作成ステップにおいて生成する属性情報データに基づく分類木を生成する分類木作成ステップと、
前記分類木作成ステップにおいて生成した分類木の分類精度を測定する分類精度測定ステップと、
前記分類木作成ステップにおいて生成した分類木から分類精度向上に対する寄与度の低い属性を除外対象属性として決定する除外対象属性決定ステップとを有し、
前記除外対象属性決定ステップにおける除外対象属性の決定処理と、除外対象属性を除く属性に基づく前記入力データ作成ステップにおける入力データ生成処理と、前記分類木作成ステップにおける分類木生成処理と、前記分類精度測定ステップにおける分類精度測定処理とを繰り返し実行し、
該繰り返し処理の中で生成する複数の分類木から分類精度のもっとも高い分類木を選択して出力するステップと、
を有することを特徴とするデータ分類処理方法。
【請求項６】
前記分類木作成ステップは、
分類処理対象データから選択された学習用データに基づいて分類木を生成するステップであり、
前記分類精度測定ステップは、
前記学習用データに基づいて生成した分類木について、分類処理対象データから選択されたテスト用データを適用して分類精度を測定するステップであることを特徴とする請求項５に記載のデータ分類処理方法。
【請求項７】
前記分類木作成ステップは、
分類木作成処理プログラムに設定するパラメータＣ（枝刈りＣＦ値）を順次変更した複数の分類木の生成処理を実行するステップであり、
前記類精度測定ステップは、
前記分類木作成ステップにおいて作成した異なるパラメータの値に対応する複数の分類木の分類精度測定処理を実行し、最高の分類精度を持つ分類木の分類精度が、異なる属性設定条件の下で生成した最高の分類精度を持つ分類木の分類精度より高い精度である場合に該分類木の情報を前記除外対象属性決定部に出力するステップを含み、
前記除外対象属性決定ステップは、
前記分類木作成ステップにおいて生成した分類木から分類精度向上に対する寄与度の低い属性を除外対象属性として決定する処理を実行するステップであることを特徴とする請求項５に記載のデータ分類処理方法。
【請求項８】
前記除外対象属性決定ステップは、
前記分類木作成ステップにおいて生成した分類木の非葉構成ノードから、比較分割情報量が最大のノードを選択し、該選択ノードの子ノード作成時の適用属性を除外対象属性として決定する処理を実行するステップであることを特徴とする請求項５に記載のデータ分類処理方法。
【請求項９】
分類木の生成処理を実行するコンピュータ・プログラムであり、
分類処理対象レコードに基づく分類木の生成に適用する属性情報データを生成する入力データ作成ステップと、
前記入力データ作成ステップにおいて生成する属性情報データに基づく分類木を生成する分類木作成ステップと、
前記分類木作成ステップにおいて生成した分類木の分類精度を測定する分類精度測定ステップと、
前記分類木作成ステップにおいて生成した分類木から分類精度向上に対する寄与度の低い属性を除外対象属性として決定する除外対象属性決定ステップとを有し、
前記除外対象属性決定ステップにおける除外対象属性の決定処理と、除外対象属性を除く属性に基づく前記入力データ作成ステップにおける入力データ生成処理と、前記分類木作成ステップにおける分類木生成処理と、前記分類精度測定ステップにおける分類精度測定処理とを繰り返し実行し、
該繰り返し処理の中で生成する複数の分類木から分類精度のもっとも高い分類木を選択して出力するステップと、
を有することを特徴とするコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、帰納学習によってデータにより多数の情報レコードの分類のための分類木を作成する手法に関する。特に、複数の属性を持つ未知のレコードに対する分類精度を高めた分類木作成を可能としたデータ分類処理装置、およびデータ分類処理方法、並びにコンピュータ・プログラムに関する。
【背景技術】
【０００２】
大量の情報が流通している情報産業界では、効率的で精度の高いデータの分類方法や装置が求められている。中でも、多数のレコードの分類のための分類木を作成する分類器を用いたデータ分類法は、分類木がユーザにとって理解しやすく、ユーザのフィードバックによるさらなる精度の向上が望めるという理由で、文書の分類、医療診断、与信審査、マーケティング等の広範囲の分野で使用されている。
【０００３】
データ分類処理を行なう１つの手法である帰納学習法では、与えられた多くの事例からその事例間に成立する因果関係又は一般法則を生成する。知識獲得における帰納学習法では、事例を属性及びクラス（結果属性）で表現し、観測属性値からクラスを推定するルールを生成する。ルールの生成手法の代表的手法として分割統治（ｄｉｖｉｄｅ−ａｎｄ−ｃｏｎｑｕｅｒ）法が知られている。
【０００４】
分割統治（ｄｉｖｉｄｅ−ａｎｄ−ｃｏｎｑｕｅｒ）法の代表的なアルゴリズムには、ＩＤ３，Ｃ４．５，  ＣＡＲＴ，  ＡＳＳＩＳＴＡＮＴ等がある。これらはルールとして分類木を出力する。
【０００５】
分割統治法のアルゴリズムの概要について説明する。アルゴリズムは以下の通りである。
（１）分類木を設定し、木のノード（分岐点）に事例を割り当てる。なお、初期的には、分類木はルート（頂点ノード）のみからなる。
（２）
（２−１）分類木のあるノードに設定した複数の事例が同じクラスに属するなら、そのノードはそのクラスでラベル付けされる。
（２−２）分類木のあるノードに設定した複数の事例が異なるクラスを含むなら、
（２−２−１）よい分類に適した属性を決定し、
（２−２−２）その属性値により事例を分類して、そのノードの子供のノードに割り当てる
（２−２−３）子供のノードについて（２）を繰り返し実行する。
【０００６】
分割統治法の代表的なアルゴリズムであるＩＤ３では、分類に適した属性を決定する際、例えば、上述のステップ（２−２−１）における分類属性決定処理において、情報エントロピーを利用した属性決定処理を行なっている。ＩＤ３では分類木を求める際に、事例数から求められる情報エントロピー（情報量の期待値）を効率の指標とする。分類木上の点での分岐属性は、ある属性による分岐前後の情報エントロピーの差（獲得情報量）を最大とする属性を選択することで求める。
【０００７】
なお、分割統治法アルゴリズムとしてのＩＤ３、Ｃ４．５については、例えば、非特許文献１、特許文献１に記載されている。特許文献１に記載の例を用いて、分割統治法アルゴリズムとしてのＩＤ３に基づく分類木生成処理の概要について説明する。
【０００８】
例えば、図１４に示されるレコード（Ｃ）３０を分類する場合を考える。この図１４に示されるように、レコード（Ｃ）３０においては、レコード（Ｃ）３０に属する対象（この場合は人）の背丈、髪の色、目の色、という属性、及び好き［＋］、嫌い［−］という分類クラスがあるものとする。この母集団：レコード（Ｃ）３０を属性に基づいて、好き［＋］、嫌い［−］のクラスに分類する。
【０００９】
このクラス分類を実行する方法には様々な方法がある。すなわち、属性：背丈、髪の色、目の色をどのように選択して、レコード（Ｃ）３０の分類を行なうかについては複数の手法が存在する。例えば最初に髪の色でレコード（Ｃ）３０を分類し、次に目の色、背丈で分類する方法や、最初に背丈で分類し、次に髪の色、目の色で分類する方法等が考えられる。
【００１０】
レコード（Ｃ）３０を最初に髪の色で分類し、次に目の色の順で分類すると、その結果は図１５のような木構造として示される。
【００１１】
この場合、髪の色が黒色の集合（Ｃ１）３１においては、どの要素も［−］のクラスに属しているので、これ以上分類する必要はない。このように、すべての要素が同じクラスに属する場合、その集合を葉ノードと呼び、そのエントロピーは０となる。
【００１２】
髪の色が赤色の集合（Ｃ２）３２においても［＋］のクラスしかないので、これ以上分類しないでよい。このように、適当な属性によって母集合をすべて葉ノードである部分集合に分類すると、分類が終了したことになる。
【００１３】
また、髪の色がブロンドの集合（Ｃ３）３３においては、次の分類を目の色の属性により行って集合３４（目の色：茶）、集合３５（目の色：青）に分けると、集合３４は［−］のクラスのみ、集合３５は［＋］のクラスのみの集合になる。
【００１４】
このように、レコード（Ｃ）３０を最初に髪の色で分類し、次に目の色の順で分類すると、すべての要素が同じクラスに属する葉ノードである部分集合に分類することが可能となり、分類が終了する。
【００１５】
これに対し、レコード（Ｃ）３０を最初に背丈で分類し、次に髪の色、目の色で分類すると、分類結果は図１６と図１７に示す分類木となる。
【００１６】
先に説明した図１５に示す分類木では、
ステップ１：髪の色で分類
ステップ２：髪の色［ブロンド］の集合を目の色で分類
上記２つのステップの分類によって母集合をすべて葉ノードである部分集合、すなわちクラス（＋）またはクラス（−）のみからなる部分集合に分類できた。
【００１７】
しかし、図１６と図１７に示す分類木では、
ステップ１：背丈で分類
ステップ２：背丈［高い］の集合を髪の色で分類
ステップ３：背丈［高い］＆髪の色［ブロンド］の集合を目の色で分類
ステップ５：背丈［低い］の集合を髪の色で分類
ステップ５：背丈［低い］＆髪の色［ブロンド］の集合を目の色で分類
上記５つのステップの分類処理を行なうことが、母集合をすべて葉ノードである部分集合、すなわちクラス（＋）またはクラス（−）のみからなる部分集合を生成するために必要となっている。
【００１８】
このように、図１６と図１７に示す分類木生成、すなわち、同一のレコード（Ｃ）３０を対象とした分類を行なう場合であっても、最初に背丈で分類し、次に髪の色、目の色で分類すると好き（＋）又は嫌い（−）のみの部分集合に分類するには分類回数を非常に多くする必要があることがわかる。
【００１９】
このように、母集団を分類する際にはどの属性から分類するかによって分類木の木構造が単純にも複雑にもなる。有用な属性を選択し、最終的にできる分類木をいかに単純な構成とするかが、母集団の効率的な分類処理を実現することになる。
【００２０】
ＩＤ３においては最小の分類木が得られるような属性選択にたいして情報理論的なアプローチをとっており、ある対象を分類するときのテスト回数の期待値を最小にすることを狙っている。
【００２１】
分類木は、分類対象としての母集団が与えられたときに、その対象がどのクラス（上記例においては＋と−）に属しているかの情報（メッセージ）を提示するための情報源であると考えることができる。ＩＤ３の属性選択の処理部分は、分類木の複雑さがこのメッセージによってもたらされる情報量と密接に関連している、とする仮定に基づいて属性選択を行う。
【００２２】
具体的には、例えば上述した図１４〜図１６に示す母集団としてのレコード（Ｃ）３０において、レコード（Ｃ）３０中の対象が［＋］のクラスに属している確率（この場合は相対頻度）を［ｐ＋］、［−］のクラスに属する確率を［ｐ−］としてこの情報量の期待値（エントロピー）Ｍ（Ｃ）を下式のように表す。
【００２３】
Ｍ（Ｃ）＝−（ｐ＋）×ｌｏｇ２（ｐ＋）−（ｐ−）×ｌｏｇ２（ｐ−）
・・・・・（式１）
【００２４】
なお、レコード（Ｃ）３０が空集合の場合はＭ（Ｃ）＝０とする。
上記定義によれば、レコード（Ｃ）３０に含まれる８種の要素のうち、＋に属するのは３種、−に属するのは５種なので、上式において、
（ｐ＋）＝３／８、
（ｐ−）＝５／８
となり、
Ｍ（Ｃ）＝−（３／８）×ｌｏｇ２（３／８）−（５／８）×ｌｏｇ２（５／８）
＝０．９５４（ビット）
・・・・・（式２）
となる。
【００２５】
次に、上記処理を一般化した例として説明する。
Ａという属性によりレコードＣをｎ個の互いに素な部分集合Ｃ１、Ｃ２、…Ｃｎに分類を行った後の情報量について評価を行う。この新規の情報量の期待値をＢ（Ｃ，Ａ）とおくと、Ｂ（Ｃ，Ａ）は以下のように定義される。尚、Σ（シグマ）はｉ＝１〜ｎの総和を表すものとする。
【００２６】
Ｂ（Ｃ，Ａ）＝Σ（Ｃの要素がＣｉに分類される確率）×Ｍ（Ｃｉ）
・・・・・（式３）
となる。
【００２７】
具体的には、図１６に示す例においては、属性［背丈］によりレコードＣを分類しており、属性［背丈］＝高いと分類される確率は５／８、属性［背丈］＝低いと分類される確率は３／８である。
【００２８】
また、背が高いという部分集合Ｃ'１における情報量期待値Ｍ（Ｃ'１）、及び背が低いという部分集合Ｃ'２における情報量期待値Ｍ（Ｃ'２）は、それぞれ下式のように表される。
【００２９】
Ｍ（Ｃ'１）＝−（２／５）×ｌｏｇ２（２／５）−（３／５）×ｌｏｇ２（３／５）
＝０．９７１（ビット）
・・・・・（式４）
Ｍ（Ｃ'２）＝−（１／３）×ｌｏｇ２（１／３）−（２／３）×ｌｏｇ２（２／３）
＝０．９１８（ビット）
・・・・・（式５）
【００３０】
従って、情報量の期待値Ｂ（Ｃ，背丈）は下式のように表される。
Ｂ（Ｃ，背丈）＝（５／８）×Ｍ（Ｃ'１）＋（３／８）×Ｍ（Ｃ'２）
＝（５／８）×０．９７１＋（３／８）×０．９１８
＝０．９５１（ビット）
・・・・・（式６）
【００３１】
上記のように、集合Ｃの情報量Ｍ（Ｃ）は０．９５４（ビット）、属性を背丈として分類を行った後の情報量Ｂ（Ｃ，背丈）は０．９５１（ビット）である。従って背丈で分類を行って得られる情報量は、０．９５４−０．９５１＝０．００３（ビット）となり、この属性による分類では殆ど情報が得られていないことがわかる。
【００３２】
これに対し、図１５に示されるように髪の色の属性にて集合Ｃを分類すると、上記計算と同様にしてＢ（Ｃ，髪の色）は以下のように計算される。
【００３３】
Ｍ（Ｃ１）＝−（３／３）×ｌｏｇ２（３／３）−０＝０
Ｍ（Ｃ２）＝−（１／１）×ｌｏｇ２（１／１）−０＝０
Ｍ（Ｃ３）＝−（２／４）×ｌｏｇ２（２／４）−（２／４）×ｌｏｇ２（２／４）
＝（１／２）＋（１／２）＝１
Ｂ（Ｃ，髪の色）＝（３／８）×０＋（１／８）×０＋（４／８）×１
＝０．５
・・・・・（式７）
【００３４】
上記のように、髪の色で集合Ｃを分類して得られる情報量は、
０．９５４−０．５＝０．４５４（ビット）
となり、背丈でＣを分類した場合に比べて非常に大きな情報量が得られることがわかる。
【００３５】
さらに、同様にして目の色により得られる情報量を計算するとその結果は０．３４７（ビット）となる。これらの結果より、集合Ｃを分類する場合には、まず髪の色の属性にて分類を行うと、多くの情報が得られることがわかる。
【００３６】
このように、ＩＤ３においてはｎ種の属性（Ｘ１，Ｘ２，・・・，Ｘｎ）を有する母集合を分類するには、母集合の情報量をＭ（Ｃ）、属性Ｘｉにより分類を行って得られる情報量期待値をＢ（Ｃ，Ｘｉ）として下式の値を最も大きくする属性を選択して分類を行う。
Ｍ（Ｃ）−Ｂ（Ｃ，Ｘｉ）
・・・・・（式８）
【００３７】
順次、異なる属性を適用して分類を行う場合は、上記と同様に得られる情報量が最も大きい属性を選択し、その属性によって分類を行う。
【００３８】
先に説明した図１５に示す分類木は母集合としてのレコード（Ｃ）３０をＩＤ３を用いて分類したものであり、前述の様に最初に分類を行う属性として髪の色を選択し、２回目の分類は属性として目の色を選択して分類を行っている。
【００３９】
また、図１６、図１７に示す分類木は、最初の分類の属性として背丈を選択し、次に髪の色、目の色によって分類を行った例を示している。
【００４０】
このような２つの分類木生成手法を比較することで、ＩＤ３を適用することにより、母集合としてのレコード（Ｃ）３０集合Ｃの分類が効率的になされることがわかる。
【００４１】
ＩＤ３アルゴリズムは、このようにして作成された分類木が、分類木作成時に用いられたレコード以外のレコード（未知レコード）の分類クラスも正確に予測できるという仮定に基づいている。しかし、多くの場合にこの仮定は成り立たず、ＩＤ３アルゴリズムには改善の余地が残されていることが知られている。
【００４２】
たとえば、レコードが分割数の多い属性を持つ場合には、この仮定が成立しないことが多い。ＩＤ３アルゴリズムは、分割数の多い属性を優先して選択する傾向がある一方、このような属性を用いた分類木は、未知レコードを正確に分類できないことが多いためである。
【００４３】
たとえば、レコード番号は、すべてのレコードを別々の部分集合に分割する。このレコード番号を分類の属性として選択すると、分割による情報量が最大になるため、ＩＤ３アルゴリズムはこの属性を最初に選択して分類木の作成を完了する。しかし、この分類木は未知レコードの分類には役立たない。新たなレコードには、新たなレコード番号が割り振られるからである。
【００４４】
Ｃ４．５アルゴリズムは、この問題の解決策を含むアルゴリズムである。このアルゴリズムでは、分類を行う属性選択時の指標として、情報利得（属性でレコード集合を分類して得られる情報量）の代わりに下記の情報利得比を用いる。
（情報利得比）＝（情報利得）／（分割情報量）
（分割情報量）＝−Σ（＃Ｃｉ／＃Ｃ）×ｌｏｇ２（＃Ｃｉ／＃Ｃ）
ただし、＃Ｃｉと＃Ｃは、それぞれＣｉとＣの要素数である。
【００４５】
情報利得比は、属性による分割数で情報利得を正規化したものである。属性による分割数が大きくなるほどその分割情報量も大きくなるので、分割数の多い属性による情報利得比は、情報利得ほどは大きくならず、結果的にそのような属性が選択されにくくなる。
【００４６】
Ｃ４．５アルゴリズムは、代表的な分類木作成アルゴリズムとして広く用いられているが、分割数の多い属性による影響をさらに抑えるための手法が提案されている。
【００４７】
たとえば、特許文献１には、有意水準と呼ばれる数値をあらかじめ設定しておく方法が示されている。ＩＤ３アルゴリズムにおいて、ある属性による分割後の集合の要素数がこの有意水準より小さい場合はその属性を選択しないようにして、分割数の多い属性による影響を抑えている。
【非特許文献１】ＪＲ  キンラン著、古川康一監訳、ＡＩによるデータ解析、トッパン、１９９５
【特許文献１】特開平６−４４２０６号公報
【発明の開示】
【発明が解決しようとする課題】
【００４８】
しかし、上述した、Ｃ４．５アルゴリズムを適用した分類木生成処理、あるいは、特許文献１の手法のいずれも、未知データの正確な分類を効率的に行なう点では問題がある。
【００４９】
たとえば、Ｃ４．５アルゴリズムで分類木を作成すると、葉ノードに近いノードでは利用できる属性が限られてくるので、分割数の大きい属性が選択されてしまうことがある。
【００５０】
また、特許文献１に示された手法では、有意水準があらかじめ決定されていることが前提となるが、この有意水準の決定処理をいかに行なうかが問題である。特許文献１には、この有意水準の決定方法は示されていない。
【００５１】
この有意水準の決定には、レコードの属性値に関する十分な知識が事前に必要となるが、多くの場合、分析者がそのような知識を持つことは少ない。
【００５２】
本発明はこのような問題点に鑑みてなされたものであり、複数の属性を持つレコードを分類する分類木の精度、特にレコードの属性値に関する十分な知識を持たない未知のレコードに対する分類精度を高めることを可能とするデータ分類処理装置、およびデータ分類処理方法、並びにコンピュータ・プログラムを提供することを目的とする。
【課題を解決するための手段】
【００５３】
本発明の第１の側面は、分類処理対象レコードに基づく分類木の生成に適用する属性情報データを生成する入力データ作成部と、前記入力データ作成部の生成する属性情報データに基づく分類木を生成する分類木作成部と、前記分類木作成部の生成した分類木の分類精度を測定する分類精度測定部と、前記分類木作成部の生成した分類木から分類精度向上に対する寄与度の低い属性を除外対象属性として決定する除外対象属性決定部とを有し、前記除外対象属性決定部における除外対象属性の決定処理と、除外対象属性を除く属性に基づく前記入力データ作成部における入力データ生成処理と、前記分類木作成部における分類木生成処理と、前記分類精度測定部における分類精度測定処理とを繰り返し実行し、該繰り返し処理の中で生成する複数の分類木から分類精度のもっとも高い分類木を選択して出力する構成を有することを特徴とするデータ分類処理装置にある。
【００５４】
本構成によれば、分類木作成部の生成した分類木から分類精度向上に対する寄与度の低い属性を除外対象属性として決定し、除外対象属性を除く属性に基づく入力データ生成処理、分類木生成処理、および分類精度測定処理とを繰り返し実行して、繰り返し処理の中で生成する複数の分類木から分類精度のもっとも高い分類木を選択して出力する構成としたので、分類処理対象データの知識を持たない未知データに対しても、自動的に分類精度の高い分類木を効率的に生成することが可能となる。
【００５５】
さらに、本発明のデータ分類処理装置の一実施態様において、前記分類木作成部は、分類処理対象データから選択された学習用データに基づいて分類木を生成する構成であり、前記分類精度測定部は、前記学習用データに基づいて生成した分類木について、分類処理対象データから選択されたテスト用データを適用して分類精度を測定する構成であることを特徴とする。
【００５６】
本構成によれば、学習用データに基づいて分類木を生成し、学習用データに基づいて生成した分類木について、分類処理対象データから選択されたテスト用データを適用して分類精度を測定する構成としたので、分類処理対象データに基づく精度の高い分類精度測定が実現される。
【００５７】
さらに、本発明のデータ分類処理装置の一実施態様において、前記分類木作成部は、分類木作成処理プログラムに設定するパラメータＣ（枝刈りＣＦ値）を順次変更した複数の分類木の生成処理を実行する構成であり、前記類精度測定部は、前記分類木作成部の作成した異なるパラメータの値に対応する複数の分類木の分類精度測定処理を実行し、最高の分類精度を持つ分類木の分類精度が、異なる属性設定条件の下で生成した最高の分類精度を持つ分類木の分類精度より高い精度である場合に該分類木の情報を前記除外対象属性決定部に出力する構成であり、前記除外対象属性決定部は、前記分類木作成部の生成した分類木から分類精度向上に対する寄与度の低い属性を除外対象属性として決定する処理を実行する構成であることを特徴とする。
【００５８】
本構成によれば、分類木作成処理プログラムに設定するパラメータを変更した複数の分類木を生成して、異なるパラメータの値に対応する複数の分類木の分類精度測定処理を実行し、最高の分類精度を持つ分類木の分類精度が、異なる属性設定条件の下で生成した最高の分類精度を持つ分類木の分類精度より高い精度である場合に分類木の情報を除外対象属性決定部に出力して、除外属性を決定する処理を行なう構成であるので、分類精度の高い分類木の集合を生成し、該集合から、さらに分類精度の高い分類木を選択することが可能となる。
【００５９】
さらに、本発明のデータ分類処理装置の一実施態様において、前記除外対象属性決定部は、前記分類木作成部の生成した分類木の非葉構成ノードから、比較分割情報量が最大のノードを選択し、該選択ノードの子ノード作成時の適用属性を除外対象属性として決定する処理を実行する構成であることを特徴とする。
【００６０】
本構成によれば、除外対象属性決定部において、分類木作成部の生成した分類木の非葉構成ノードから、比較分割情報量が最大のノードを選択して、そのノードの子ノード作成時の適用属性を除外対象属性として決定する構成としたので、分類精度向上に対する寄与度の低い属性を正確に選択することが可能となる。
【００６１】
さらに、本発明の第２の側面は、分類処理対象レコードに基づく分類木の生成に適用する属性情報データを生成する入力データ作成ステップと、前記入力データ作成ステップにおいて生成する属性情報データに基づく分類木を生成する分類木作成ステップと、前記分類木作成ステップにおいて生成した分類木の分類精度を測定する分類精度測定ステップと、前記分類木作成ステップにおいて生成した分類木から分類精度向上に対する寄与度の低い属性を除外対象属性として決定する除外対象属性決定ステップとを有し、前記除外対象属性決定ステップにおける除外対象属性の決定処理と、除外対象属性を除く属性に基づく前記入力データ作成ステップにおける入力データ生成処理と、前記分類木作成ステップにおける分類木生成処理と、前記分類精度測定ステップにおける分類精度測定処理とを繰り返し実行し、該繰り返し処理の中で生成する複数の分類木から分類精度のもっとも高い分類木を選択して出力するステップと、を有することを特徴とするデータ分類処理方法にある。
【００６２】
本構成によれば、分類木作成部の生成した分類木から分類精度向上に対する寄与度の低い属性を除外対象属性として決定し、除外対象属性を除く属性に基づく入力データ生成処理、分類木生成処理、および分類精度測定処理とを繰り返し実行して、繰り返し処理の中で生成する複数の分類木から分類精度のもっとも高い分類木を選択して出力する構成としたので、分類処理対象データの知識を持たない未知データに対しても、自動的に分類精度の高い分類木を効率的に生成することが可能となる。
【００６３】
さらに、本発明のデータ分類処理方法の一実施態様において、前記分類木作成ステップは、分類処理対象データから選択された学習用データに基づいて分類木を生成するステップであり、前記分類精度測定ステップは、前記学習用データに基づいて生成した分類木について、分類処理対象データから選択されたテスト用データを適用して分類精度を測定するステップであることを特徴とする。
【００６４】
本構成によれば、学習用データに基づいて分類木を生成し、学習用データに基づいて生成した分類木について、分類処理対象データから選択されたテスト用データを適用して分類精度を測定する構成としたので、分類処理対象データに基づく精度の高い分類精度測定が実現される。
【００６５】
さらに、本発明のデータ分類処理方法の一実施態様において、前記分類木作成ステップは、分類木作成処理プログラムに設定するパラメータＣ（枝刈りＣＦ値）を順次変更した複数の分類木の生成処理を実行するステップであり、前記類精度測定ステップは、前記分類木作成ステップにおいて作成した異なるパラメータの値に対応する複数の分類木の分類精度測定処理を実行し、最高の分類精度を持つ分類木の分類精度が、異なる属性設定条件の下で生成した最高の分類精度を持つ分類木の分類精度より高い精度である場合に該分類木の情報を前記除外対象属性決定部に出力するステップを含み、前記除外対象属性決定ステップは、前記分類木作成ステップにおいて生成した分類木から分類精度向上に対する寄与度の低い属性を除外対象属性として決定する処理を実行するステップであることを特徴とする。
【００６６】
本構成によれば、分類木作成処理プログラムに設定するパラメータを変更した複数の分類木を生成して、異なるパラメータの値に対応する複数の分類木の分類精度測定処理を実行し、最高の分類精度を持つ分類木の分類精度が、異なる属性設定条件の下で生成した最高の分類精度を持つ分類木の分類精度より高い精度である場合に分類木の情報を除外対象属性決定部に出力して、除外属性を決定する処理を行なう構成であるので、分類精度の高い分類木の集合を生成し、該集合から、さらに分類精度の高い分類木を選択することが可能となる。
【００６７】
さらに、本発明のデータ分類処理方法の一実施態様において、前記除外対象属性決定ステップは、前記分類木作成ステップにおいて生成した分類木の非葉構成ノードから、比較分割情報量が最大のノードを選択し、該選択ノードの子ノード作成時の適用属性を除外対象属性として決定する処理を実行するステップであることを特徴とする。
【００６８】
本構成によれば、除外対象属性決定部において、分類木作成部の生成した分類木の非葉構成ノードから、比較分割情報量が最大のノードを選択して、そのノードの子ノード作成時の適用属性を除外対象属性として決定する構成としたので、分類精度向上に対する寄与度の低い属性を正確に選択することが可能となる。
【００６９】
さらに、本発明の第３の側面は、
分類木の生成処理を実行するコンピュータ・プログラムであり、
分類処理対象レコードに基づく分類木の生成に適用する属性情報データを生成する入力データ作成ステップと、
前記入力データ作成ステップにおいて生成する属性情報データに基づく分類木を生成する分類木作成ステップと、
前記分類木作成ステップにおいて生成した分類木の分類精度を測定する分類精度測定ステップと、
前記分類木作成ステップにおいて生成した分類木から分類精度向上に対する寄与度の低い属性を除外対象属性として決定する除外対象属性決定ステップとを有し、
前記除外対象属性決定ステップにおける除外対象属性の決定処理と、除外対象属性を除く属性に基づく前記入力データ作成ステップにおける入力データ生成処理と、前記分類木作成ステップにおける分類木生成処理と、前記分類精度測定ステップにおける分類精度測定処理とを繰り返し実行し、
該繰り返し処理の中で生成する複数の分類木から分類精度のもっとも高い分類木を選択して出力するステップと、
を有することを特徴とするコンピュータ・プログラムにある。
【００７０】
本構成によれば、分類木作成部の生成した分類木から分類精度向上に対する寄与度の低い属性を除外対象属性として決定し、除外対象属性を除く属性に基づく入力データ生成処理、分類木生成処理、および分類精度測定処理とを繰り返し実行して、繰り返し処理の中で生成する複数の分類木から分類精度のもっとも高い分類木を選択して出力する構成としたので、分類処理対象データの知識を持たない未知データに対しても、自動的に分類精度の高い分類木を効率的に生成することが可能となる。
【００７１】
なお、本発明のコンピュータ・プログラムは、例えば、様々なプログラム・コードを実行可能なコンピュータシステムに対して、コンピュータ可読な形式で提供する記憶媒体、通信媒体、例えば、ＣＤやＦＤ、ＭＯなどの記録媒体、あるいは、ネットワークなどの通信媒体によって提供可能なコンピュータ・プログラムである。このようなプログラムをコンピュータ可読な形式で提供することにより、コンピュータシステム上でプログラムに応じた処理が実現される。
【００７２】
本発明のさらに他の目的、特徴や利点は、後述する本発明の実施例や添付する図面に基づくより詳細な説明によって明らかになるであろう。なお、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【発明の効果】
【００７３】
本発明の構成によれば、分類木作成部の生成した分類木から分類精度向上に対する寄与度の低い属性を除外対象属性として決定し、除外対象属性を除く属性に基づく入力データ生成処理、分類木生成処理、および分類精度測定処理とを繰り返し実行して、繰り返し処理の中で生成する複数の分類木から分類精度のもっとも高い分類木を選択して出力する構成としたので、分類処理対象データの知識を持たない未知データに対しても、自動的に分類精度の高い分類木を効率的に生成することが可能となる。
【００７４】
本発明の構成によれば、従来の分類木生成アルゴリズムＣ４．５を適用した場合の問題、すなわち、分類木の葉ノード近くで分割数の大きい属性が選択されてしまうと、未知レコードに対する分類精度が低下してしまうといった問題を解決することができる。すなわち、本発明の構成においては、分類の寄与度の低い属性を除外して分類木を再作成し、さらに分類精度を測定し、より分類精度の高い分類木を生成する構成であるので、分類精度の低下を防止することができる。また、前述した特許文献１（特開平６−４４２０６号公報）に記載の手法のように、事前に有意水準を決定する必要もなく、効率的な分類精度の高い分類木生成が可能となる。
【発明を実施するための最良の形態】
【００７５】
以下、図面を参照しながら本発明のデータ分類処理装置、およびデータ分類処理方法、並びにコンピュータ・プログラムの詳細について説明する。
【００７６】
図１は本発明のデータ分類処理装置としてのデータマイニングシステム１００の構成図である。図１に示すように、データ分類処理装置（データマイニングシステム）１００は、データベース１０１、入力データ作成部１０２、分類木作成・分類精度測定部１０３、および、除外対象属性決定部１０４から構成される。本発明のデータ分類処理装置としてのデータマイニングシステム１００は、データベース１０１に格納されたデータを対象としてデータ分類処理を実行し分類木１５０を生成して出力する。
【００７７】
データベース１０１は、入力データ作成部１０２に入力するデータを保持する。このデータベース１０１は、一般的な関係データベースやファイルシステムとして実現可能である。
【００７８】
図２に、入力データ作成部１０２に入力されるデータ、すなわち、データベース１０１に保持されるデータの例を示す。
【００７９】
図２に示すように、データベース中のデータは、各列を属性とし、各行をレコードとする表形式データとして表現されている。各レコードは、属性ａ１から属性ｃｌａｓｓまで、合計３２の属性を持つ。また、図２では３つのレコードのみを示しているが、本実施例では、一例として７，０７２のレコードが入力データ作成部１０２に入力されるものとする。
【００８０】
入力データ作成部１０２は、データベース１０１から学習対象のデータを読み込み、分類木作成・分類精度測定部１０３に対する入力データへの変換処理を実行する。
【００８１】
入力データ作成部１０２は、この処理において、除外対象属性決定部１０４から除外対象の属性が出力されている場合は、その属性を除外して入力データを作成する。入力データ作成部１０２は、ｐｅｒｌやＪａｖａなどの一般的なプログラミング言語によるプログラムの実行部として実現される。
【００８２】
図３に、入力データ作成部１０２が、データベース１０１の格納データ（例えば図２参照）に基づいて、ｐｅｒｌやＪａｖａなどの一般的なプログラミング言語によるプログラムを実行して生成するデータ、すなわち、分類木作成・分類精度測定部１０３に対する入力データの例を示す。
【００８３】
図３に示すように、入力データ作成部１０２が生成する分類木作成・分類精度測定部１０３への入力データは、"＠ｄａｔａ"より前に位置する行からなる属性宣言部２０１と、"＠ｄａｔａ"以降に位置する行からなるデータ部２０２から構成される。
【００８４】
属性宣言部２０１は、各属性ごとに、属性名と、その属性が取り得る値を示す。たとえば、データ２１１は、すべてのレコードにおいて、属性［ａ１］の値は実数（ｒｅａｌ）であることを示す。
【００８５】
また、データ２１２は、すべてのレコードにおいて、
属性ａ５＿１の値は、［未知語］、［副詞］、［感動詞］、［形容詞］、［名詞］、［接続詞］、［フィラー］、［動詞］、［記号］、［連体詞］のいずれかであることを示す。
【００８６】
データ部２０２は、各レコードの属性値のデータを順次並べた構成を持つ。各レコードの属性値が、属性宣言部２０１での出現順にカンマ区切りで順次並べられて示される。レコード間の区切り文字には改行記号が用いられる。
【００８７】
図４は、入力データ作成部１０２の処理の流れの一例を示すフローチャートである。各処理ステップについて説明する。ステップＳ１０１では、データベース１０１に格納されたデータ（例えば図２に示すデータ）が持つ属性のうち、除外対象属性決定部１０４が出力している属性を除くすべての属性名によって属性リストＡを生成する。属性リストＡは、データベース１０１に格納されたデータ（例えば図２に示すデータ）が持つ属性のうち、除外対象属性決定部１０４が出力している属性を除くすべての属性名を、データベース１０１での出現順に格納したリストである。
【００８８】
ステップＳ１０２では、データ部リストＲを空とする。また、すべての属性Ａｉについて、属性宣言部集合Ｄ（Ａｉ）を空とする。属性：Ａｉは、属性リストＡに設定された属性であり、ｉ＝１〜ｎ（ただしｎは、属性リストＡに設定された属性数）である。
【００８９】
ステップＳ１０３では、データベース１０１中の全レコードが処理されたか判定し、処理された場合にはステップＳ１０９に処理を進め、そうでない場合にはステップＳ１０４に処理を進める。
【００９０】
ステップＳ１０４では、未処理のレコードのうち先頭のレコードＲｉを選択し、データ部リストＲに追加する。このとき、レコードＲｉの各属性値は、カンマを区切り文字として結合される。図３に示すデータ部２０２の態様である。
【００９１】
なお、レコードＲｉにおいて、ｉ＝１〜ｍ（ただし、ｍは、データベース中のレコード数）である。なお、ここでレコード数は、処理対象となるレコード数である。例えば図２に示すデータが処理対象として設定されるレコードとなる。本実施例では、７，０７２のレコードが入力データ作成部１０２に入力されるものとする。
【００９２】
ステップＳ１０５では、すべての属性について属性宣言部集合Ｄ（Ａｉ）への追加処理を行ったか判定し、行った場合にはステップＳ１０３へ処理を進め、そうでない場合にはステップＳ１０６に処理を進める。
【００９３】
ステップＳ１０６では、追加処理をおこなっていない属性のうち先頭の属性Ａｊを選択する。ステップＳ１０７では、属性宣言部集合Ｄ（Ａｉ）が、レコードＲｉにおける属性Ａｊの値（ａｉｊ）を含むか判定し、含む場合は処理をステップＳ１０８へ、そうでない場合は処理をステップＳ１０５に進める。ステップＳ１０８では、属性宣言部集合Ｄ（Ａｉ）に属性Ａｊの値（ａｉｊ）を追加し、処理をステップＳ１０５に進める。
【００９４】
ステップＳ１０９では、リストＡ、すなわち、ステップＳ１０１において設定したデータベース１０１に格納されたデータが持つ属性のうち、除外対象属性決定部１０４が出力している属性を除くすべての属性名からなるリストＡ中の属性Ａｉごとに、属性宣言部集合Ｄ（Ａｉ）に基づいて、図３に示す属性宣言部２０１の記述を作成して出力する。ステップＳ１１０では、図３のデータ部２０２の構成データとして、データ部リストＲ中のレコードを順次出力し、処理を終了する。
【００９５】
分類木作成・分類精度測定部１０３は、入力データ作成部１０２から入力する入力データ（例えば図３に示す入力データ）を学習データとテストデータに分割し、学習データから分類木を作成する。また、作成した分類木で正しく分類されたデータ数と誤って分類されたデータ数から分類精度を算出する。分類精度は、学習データとテストデータについてそれぞれ算出される。
【００９６】
分類木作成・分類精度測定部１０３は、ＩＤ３アルゴリズムやＣ４．５アルゴリズムを実装したデータマイニングツールＷＥＫＡの分類木作成モジュール、および、ｐｅｒｌやＪａｖａなどの一般的なプログラミング言語によるプログラムの組合せとして実現される。
【００９７】
分類木作成・分類精度測定部１０３は、分類処理対象データから選択された学習用データに基づいて分類木を生成し、学習用データに基づいて生成した分類木について、分類処理対象データから選択されたテスト用データを適用して分類精度を測定する。
【００９８】
図５は、分類木作成・分類精度測定部１０３から出力されるデータの例である。図５のデータは、分類木部３０１と統計情報部３０２からなる。
【００９９】
分類木部３０１は、分類木をテキストデータとして表現したものである。分類木部３０１中の各行は分類木を構成する各ノードの情報に対応する。各行の表記規則は以下の通りである。
【０１００】
＜行＞：：＝＜親ノード数＞？（＜非葉ノード情報＞｜＜葉ノード情報＞）
＜親ノード数＞：：＝（"｜"）＊
＜非葉ノード情報＞：：＝＜ノード条件＞
＜葉ノード情報＞：：＝＜ノード条件＞＜分類レコード情報＞
＜ノード条件＞：：＝＜属性名＞＜比較演算子＞＜属性値＞
＜分類レコード情報＞：：＝＜クラス属性値＞"（"＜分類レコード数＞（"／"＜誤分類レコード数＞）？"）"
【０１０１】
あるノードＡの［親ノード数］は、ノードＡの親ノードの数（文字列"｜"の数）である。あるノードＡの親ノードに対応する行は、ノードＡに対応する行の前に位置する行で、"親ノード数"がノードＡよりも１つ少ない行のうち、ノードＡに最も近い行である。"親ノード数"を含まないノードは、ルートノード直下のノードである。
【０１０２】
たとえば、"ａ５＿２＝使用する"は、"｜ａ６＿２＜＝０．６３６３"の親ノードである。また、"｜ａ６＿２＝＜０．６３６３"は、"｜｜ａ１４＿２＜＝０．２５：−（４９．０／４．０）"の親ノードである。したがって、ノード"｜｜ａ１４＿２＜＝０．２５：−（４９．０／４．０）"には、属性ａ５＿２の値が"使用する"であり、属性ａ６＿２の値が０．６３６３以下であり、属性ａ１４＿２の値が０．２５以下であるレコードが分類される。
【０１０３】
ノードＡの［ノード条件］は、ノードＡの親ノードに分類されるレコードのうち、ノードＡに分類されるものが満たすべき条件である。また、葉ノードＢの"分類レコード情報"は、葉ノードＢの分類クラス（［＋］または［−］）と、その分類クラスのレコード数からなる。"分類レコード情報"は、葉ノードＢの分類クラス以外のクラスのレコード（誤分類レコード）が分類されているときは、それらの数も含む。
【０１０４】
たとえば、ノード"｜｜ａ１４＿２＜＝０．２５：−（４９．０／４．０）"の分類クラスは［−］である。このノードには、分類クラス［−］に属する４９レコードと、分類クラス［＋］に属する４レコードが分類されている。
【０１０５】
統計情報部３０２は、分類木部３０１に示された分類木の葉ノード数、ノード数、学習データ・テストデータに対する分類精度を含む。たとえば、"＝＝＝Ｅｒｒｏｒ  ｏｎ  ｔｒａｉｎｉｎｇ  ｄａｔａ＝＝＝"の次の行とその次の行はそれぞれ学習データに対する分類率と誤分類率を示す。同様に、"＝＝＝Ｓｔｒａｔｉｆｉｅｄ  ｃｒｏｓｓ−ｖａｌｉｄａｔｉｏｎ＝＝＝"の次の行とその次の行はそれぞれテストデータに対する分類率と誤分類率を示す。
【０１０６】
図６は、分類木作成・分類精度測定部１０３の処理の流れの一例を示すフローチャートである。ステップＳ２０１では、分類木作成時にプログラムに与えるパラメータＣ（枝刈りＣＦ値）についての初期設定を実行する。
【０１０７】
パラメータＣの最小値としてのＣｍｉｎ、
パラメータＣの最大値としてのＣｍａｘ、
パラメータＣの更新量としてのＣｓｔｅｐ、
最適パラメータＣの値としてのＣｂｅｓｔ、
のそれぞれについて、
Ｃｍｉｎ＝０．０５、
Ｃｍａｘ＝０．８、
Ｃｓｔｅｐ＝０．０５、
Ｃｂｅｓｔ＝０
を設定する。
さらに、初期パラメータＣ＝Ｃｍｉｎ＝０．０５を代入する。
なお、上記パラメータＣの最小値、最大値、更新量の設定値は一例を示すものであり、これらの設定に限らず、様々な設定が可能である。
【０１０８】
以下のフローの処理は、Ｃ＝Ｃｍｉｎ＝０．０５から、Ｃｓｔｅｐ＝０．０５毎に、順次、パラメータＣを変更して、Ｃｍａｘ＝０．８まで、パラメータを変更して設定される分類木についての分類精度を算出し、その中から最も分類精度の高い分類木に対応するパラメータＣを最適パラメータＣの値としてのＣｂｅｓｔとして決定し、この最適パラメータＣｂｅｓｔによって設定される分類木を最終的な分類木とする処理である。
【０１０９】
ステップＳ２０２以下の処理の詳細について説明する。ステップＳ２０２では、分類木の集合Ｔを空集合とし、分類精度一覧表ＴＢＬをクリアする。分類精度一覧表ＴＢＬは、図７に示すように、パラメータＣの値に応じて、学習事例分類精度（Ｐｌｅａｒｎ）と、テスト事例分類精度（Ｐｅｖａｌ）を対応付けたデータである。初期的には、この分類精度一覧表ＴＢＬはクリアされ、データは格納されていない。
【０１１０】
ステップＳ２０３では、パラメータＣが、パラメータＣの最大値としてのＣｍａｘより大きいか判定し、大きい場合は処理をステップＳ２０８に進め、そうでない場合は処理をステップＳ２０４に進める。
【０１１１】
ステップＳ２０４では、パラメータＣに基づく分類木Ｔ（Ａ，Ｃ）を作成する。ここでＡは、分類木作成・分類精度測定部１０３への入力データが持つ属性の集合であり、Ｃは、この時点で設定されているパラメータＣ（枝刈りＣＦ値）である。
【０１１２】
ステップＳ２０４の処理は、たとえば、データマイニングツールＷＥＫＡの分類木作成モジュールを利用して実現できる。ＷＥＫＡの分類木作成モジュールは、たとえば以下のコマンドを実行することで起動できる。
【０１１３】
％  ｊａｖａ−Ｘｍｘ１０２４ｍ−Ｘｓｓ１０２４ｍ  ｗｅｋａ．ｃｌａｓｓｉｆｉｅｒｓ．ｊ４８．Ｊ４８−ｔ（入力データファイル名）−Ｃ（Ｐ値）＞（Ｔ（Ｐ）に対応するファイル名）
【０１１４】
ｔ（入力データファイル名）は、分類木生成に適用する入力データのファイル名であり、入力データ作成部１０２が生成したデータ、例えば、図３に示す属性宣言部２０１と、データ部２０２からなる入力データのファイル名である。
Ｃ（Ｐ値）は、現時点で設定されているパラメータＣの値、すなわち、Ｃ＝０．０５（Ｃｍｉｎ）〜０．８（Ｃｍａｘ）の、Ｃｓｔｅｐ＝０．０５刻みのいずれかの値である。
（Ｔ（Ｐ）に対応するファイル名）は、入力データと、設定パラメータに基づいて生成されるデータ、すなわち、図５に示す分類木部３０１と、統計情報部３０２からなるデータのファイル名である。
【０１１５】
上記情報を設定したコマンドをＷＥＫＡの分類木作成モジューに入力することで、図５に示す分類木部３０１と、統計情報部３０２からなるデータのファイルＴ（Ｐ）が出力される。
【０１１６】
ＷＥＫＡの分類木作成モジュールは、入力データを自動的に学習データとテストデータに分け、学習データから分類木を作成し、学習データとテストデータに対する分類精度ＰｌｅａｒｎとＰｅｖａｌを算出して出力する。
【０１１７】
ステップＳ２０５では、ステップＳ２０４で作成した分類木による学習データとテストデータの分類精度（Ｐｌｅａｒｎ、Ｐｅｖａｌ）を測定する。ＷＥＫＡの分類木作成モジュールの出力ファイルＴ（Ｐ）の統計情報部には、これらの分類精度の記載が含まれているので、これらの記載を入手する。なお、ステップＳ２０４で作成した分類木Ｔ（Ａ，Ｃ）に分類精度が出力されていない場合であっても、生成した分類木の葉ノードごとに、そのノードに正しく分類されるレコード数と誤分類されるレコード数を算出し、以下の式によって分類精度を算出することができる。
【０１１８】
（Ｐｌｅａｒｎ）＝（正しく分類された学習データのレコード数）／（全学習データのレコード数）
（Ｐｅｖａｌ）＝（正しく分類されたテストデータのレコード数）／（全テストデータのレコード数）
【０１１９】
ステップＳ２０６では、ステップＳ２０５で算出した分類精度を分類精度一覧表ＴＢＬに追加する。分類精度一覧表の例を図７に示す。分類精度一覧表ＴＢＬは、図７に示すように、パラメータＣの値に応じて、学習事例分類精度（Ｐｌｅａｒｎ）と、テスト事例分類精度（Ｐｅｖａｌ）を対応付けたデータである。
【０１２０】
ステップＳ２０７では、パラメータＣに、パラメータの更新量Ｃｓｔｅｐ（この例では、Ｃｓｔｅｐ＝０．０５）を加算し、パラメータＣの値の更新処理を実行して、処理をステップＳ２０３に戻す。
【０１２１】
ステップＳ２０３〜Ｓ２０７の処理をパラメータＣ＝０．０５（Ｃｍｉｎ）〜０．８（Ｃｍａｘ）において、Ｃｓｔｅｐ＝０．０５刻みで繰り返し実行することで、各パラメータＣ：０．０５，０．１０，０．１５・・・０．８０に対応する分類木が生成され、パラメータＣの値に応じた学習事例分類精度（Ｐｌｅａｒｎ）と、テスト事例分類精度（Ｐｅｖａｌ）を算出して、図７に示す分類精度一覧表ＴＢＬを完成させる。
【０１２２】
ステップＳ２０８では、分類精度一覧表ＴＢＬからテストデータに対する分類精度（Ｐｅｖａｌ）がもっとも高いレコードのパラメータＣの値を、最適パラメータＣの値としての最適パラメータＣｂｅｓｔとして特定する。
【０１２３】
ステップＳ２０９では、これまでのテストデータ分類精度最高値Ｐｅｖａｌ（Ｔｂｅｓｔ）と、今回作成した分類木でのテストデータ分類精度最高値Ｐｅｖａｌ（Ｔ（Ａ，Ｃｂｅｓｔ））を比較し、前者が後者より大きい場合は処理をステップＳ２１０に進め、そうでない場合は処理をステップＳ２１１に進める。
【０１２４】
ステップＳ２１０では、分類木Ｔｂｅｓｔを出力してデータマイニングシステムの処理を終了する。
【０１２５】
ステップＳ２１１では、ＴｂｅｓｔにＴ（Ａ，Ｃｂｅｓｔ）を代入する。Ｔ（Ａ，Ｃｂｅｓｔ）は、今回の処理、すなわち、入力データ作成部１０２から入力したデータに基づいて生成される分類木の中で最適な分類木である。
【０１２６】
ステップＳ２１２では、除外対象属性決定部１０４にＴ（Ａ，Ｃｂｅｓｔ）を出力して処理を終了する。
【０１２７】
分類木作成・分類精度測定部１０３は、このように、作成した異なるパラメータの値に対応する複数の分類木の分類精度測定処理を実行し、最高の分類精度を持つ分類木の分類精度が、異なる属性設定条件の下で生成した最高の分類精度を持つ分類木の分類精度より高い精度である場合に該分類木の情報を除外対象属性決定部１０４に出力する構成である。
【０１２８】
除外対象属性決定部１０４は、分類木作成・分類精度測定部１０３から出力される分類木を入力とし、分類精度向上にもっとも寄与していない属性を特定して、入力データ作成部１０２に出力する。
【０１２９】
図８は、除外対象属性決定部１０４の処理の流れの一例を示すフローチャートである。ステップＳ３０１では、分類木作成・分類精度測定部１０３から入力された分類木Ｔ、すなわち、Ｔ（Ａ，Ｃｂｅｓｔ）のすべての非葉ノードを集合Ｎに代入する。
【０１３０】
ステップＳ３０２では、分類木Ｔ（Ａ，Ｃｂｅｓｔ）のすべての非葉ノードを集合Ｎが空であるか判定し、空である場合は処理をステップＳ３０５へ進め、そうでない場合は処理をステップＳ３０３に進める。ステップＳ３０３では、集合Ｎ中のノードを１つ（Ｎｉ）選択する。
【０１３１】
ステップＳ３０４では、ノードＮｉの分割情報量Ｄを算出して分割情報量一覧表に追加する。なお、
分割情報量Ｄ＝−Σ（＃Ｃｉ／＃Ｃ）×ｌｏｇ２（＃Ｃｉ／＃Ｃ）
ただし、＃Ｃｉと＃Ｃは、それぞれＣｉとＣの要素数である。
【０１３２】
ステップＳ３０５では、分割情報量Ｄ値が最大のノードＮｍａｘを特定する。ステップＳ３０６では、Ｎｍａｘの子ノード作成時に用いられている属性を、入力データ作成部１０２に、除外対象属性として出力して処理を終了する。
【０１３３】
図９に、図８のステップＳ３０５開始時点での非葉ノードごとの分割情報量一覧表の例を示す。図９では、"非葉ノードのルール表現"で、各ノードに分類されるレコードが満たすべき条件を述語論理形式で記載している。
たとえば、データ４０１に示す
ｃｌａｓｓ（Ａ，"＋"）：−ａ５＿２（Ａ，Ｖｅｒ．４．１），ａ１６＿１＿ｌｅｓｓ＿ｔｈａｎ（Ａ，０．２５）．
は、そのノードに分類されるレコードの属性ａ５＿２の値が［Ｖｅｒ．４．１］であり、属性ａ１６＿１の値が０．２５より小さいことを示す。この非葉ノードの分割情報量Ｄは、０．４６８９である。
【０１３４】
図９の例では、ルートノード（一覧表末尾の行）の分割情報量が約８．２９と最も大きい。したがって、この例では、ルートノード直下のノード作成時に用いられる属性（属性ａ５＿２）がステップＳ３０６で、入力データ作成部１０２に除外対象属性として出力される。
【０１３５】
入力データ作成部１０２は、除外対象属性決定部１０４から入力する属性を除外した処理を実行した上で、再度、先に説明した図４に示す処理を実行して、分類木作成・分類精度測定部１０３に対する出力データ、すなわち、図３に示す属性宣言部２０１とデータ部２０２からなるデータを生成し、分類木作成・分類精度測定部１０３に出力する。
【０１３６】
分類木作成・分類精度測定部１０３は、入力データ作成部１０２から新たに入力するデータに基づいて、再度、図６に示す処理を実行し、パラメータＣの値を変更しながら複数の分類木を生成し、図７に示す分類精度一覧表ＴＢＬを生成する。さらに、図６に示すステップＳ２０８において、分類精度一覧表ＴＢＬからテストデータに対する分類精度がもっとも高いレコードのパラメータＣの値を、最適パラメータＣの値としての最適パラメータＣｂｅｓｔとして特定する。
【０１３７】
ステップＳ２０９では、これまでに生成済みのテストデータ分類精度最高値Ｐｅｖａｌ（Ｔｂｅｓｔ）と、今回作成した分類木でのテストデータ分類精度最高値Ｐｅｖａｌ（Ｔ（Ａ，Ｃｂｅｓｔ））を比較し、前者が後者より大きい場合、すなわち、
Ｐｅｖａｌ（Ｔｂｅｓｔ）＞Ｐｅｖａｌ（Ｔ（Ａ，Ｃｂｅｓｔ））
が成立する場合は、処理をステップＳ２１０に進め、そうでない場合は処理をステップＳ２１１に進める。
【０１３８】
ステップＳ２１１では、ＴｂｅｓｔにＴ（Ａ，Ｃｂｅｓｔ）を代入する。Ｔ（Ａ，Ｃｂｅｓｔ）は、今回の処理、すなわち、入力データ作成部１０２から入力したデータに基づいて生成される分類木の中で最適な分類木である。
【０１３９】
この処理を繰り返し実行することによって、ステップＳ２０９の判定において、これまでのテストデータ分類精度最高値Ｐｅｖａｌ（Ｔｂｅｓｔ）と、今回作成した分類木でのテストデータ分類精度最高値Ｐｅｖａｌ（Ｔ（Ａ，Ｃｂｅｓｔ））を比較し、前者が後者より大きくなり、処理がステップＳ２１０に進んだ時点で、この分類木を最終的な最適分類木Ｔｂｅｓｔとして出力してデータマイニングシステムの処理を終了する。
【０１４０】
本発明のデータ分類処理装置の全体処理のシーケンスを図１０のフローを参照して説明する。
【０１４１】
まず、ステップＳ４０１において、入力データ作成部１０２が、データベース１０１に格納された分類処理対象データ（図２参照）に基づいて、分類木作成・分類精度測定部１０３に対する入力データ（図３参照）を生成（詳細フローは図４）する。なお、この際、除外対象属性決定部１０４から除外対象属性が入力されている場合は、その属性を除いてデータ生成を行なう。
【０１４２】
次に、ステップＳ４０２において、分類木作成・分類精度測定部１０３が、入力データ作成部１０２からの入力データ（図３参照）に基づいて、パラメータＣを変更しながら、分類木を含むデータ（図５参照）を生成し、分類精度一覧表ＴＢＬ（図７）を生成する。
【０１４３】
次に、ステップＳ４０３において、分類木作成・分類精度測定部１０３が、分類精度一覧表ＴＢＬ（図７）から、テストデータ分類精度最高値を持つものを選択し、その分類木をＴ（Ａ，Ｃｂｅｓｔ）とする。
【０１４４】
次に、ステップＳ４０４において、分類木作成・分類精度測定部１０３が、これまでに生成済みのテストデータ分類精度最高値Ｐｅｖａｌ（Ｔｂｅｓｔ）と、今回作成した分類木でのテストデータ分類精度最高値Ｐｅｖａｌ（Ｔ（Ａ，Ｃｂｅｓｔ））を比較する。
【０１４５】
ステップＳ４０５において、
Ｐｅｖａｌ（Ｔｂｅｓｔ）＞Ｐｅｖａｌ（Ｔ（Ａ，Ｃｂｅｓｔ））
が成立すると判定される場合は、ステップＳ４０７に進み、Ｔｂｅｓｔを最終出力分類木として設定し、出力する。
【０１４６】
ステップＳ４０５において、
Ｐｅｖａｌ（Ｔｂｅｓｔ）＞Ｐｅｖａｌ（Ｔ（Ａ，Ｃｂｅｓｔ））
が成立しないと判定される場合は、ステップＳ４０６に進み、除外対象属性決定部１０４において、Ｐｅｖａｌ（Ｔ（Ａ，Ｃｂｅｓｔ））から比較分割情報量Ｄ値が最大のノードＮｍａｘを特定し、Ｎｍａｘの子ノード作成時に用いられている属性を、入力データ作成部１０２に、除外対象属性として出力する。
【０１４７】
以下、ステップＳ４０５において、
Ｐｅｖａｌ（Ｔｂｅｓｔ）＞Ｐｅｖａｌ（Ｔ（Ａ，Ｃｂｅｓｔ））
が成立するまで、ステップＳ４０１〜４０６の処理を繰り返し実行して、ステップＳ４０５において、
Ｐｅｖａｌ（Ｔｂｅｓｔ）＞Ｐｅｖａｌ（Ｔ（Ａ，Ｃｂｅｓｔ））
が成立したことを条件として、ステップＳ４０７に進み、Ｔｂｅｓｔを最終出力分類木として設定し、出力する。
【０１４８】
なお、この処理フローによって、除外対象属性決定部１０４において除外対象の属性を選択して生成する分類木の変遷の概要について、図１１を参照して説明する。
【０１４９】
除外対象属性決定部１０４では、分類木作成・分類精度測定部１０３から出力される分類木を入力とし、分類精度向上にもっとも寄与していない属性を特定して出力する。分類木作成・分類精度測定部１０３から入力された分類木Ｔ、すなわち、Ｔ（Ａ，Ｃｂｅｓｔ）の非葉ノードから、分割情報量Ｄ値が最大のノードＮｍａｘを特定し、Ｎｍａｘの子ノード作成時に用いられている属性を、入力データ作成部１０２に、除外対象属性として出力する。
【０１５０】
図１１において、例えば、図１１（ａ）は、第１ステップで、分類木作成・分類精度測定部１０３から出力される分類木、すなわち、最大分類精度を持つ分類木（Ｔ（Ａ，Ｃｂｅｓｔ））と、属性を示している。この図１１（ａ）に示す分類木の構成非葉ノードから、分割情報量Ｄ値が最大のノードＮｍａｘを特定し、Ｎｍａｘの子ノード作成時に用いられている属性を、入力データ作成部１０２に、除外対象属性として出力する。この例では、ノードＣ（属性Ｃに基づく分類を実行しているノード）が分割情報量Ｄ値最大のノードＮｍａｘとして選択され、属性Ｃが、除外対象属性として入力データ作成部１０２に通知される。
【０１５１】
入力データ作成部１０２、および分類木作成・分類精度測定部１０３では、属性Ｃを除くデータに基づいて分類木生成、分類精度測定が実行され、この条件で、最大精度を持つ分類木（Ｔ（Ａ，Ｃｂｅｓｔ））として、図１１（ｂ）に示す分類木が生成される。
【０１５２】
除外対象属性決定部１０４では、この図１１（ｂ）に示す分類木の構成非葉ノードから、分割情報量Ｄ値が最大のノードＮｍａｘを特定し、Ｎｍａｘの子ノード作成時に用いられている属性を、入力データ作成部１０２に、除外対象属性として出力する。この例では、ノードＢ（属性Ｂに基づく分類を実行しているノード）が分割情報量Ｄ値最大のノードＮｍａｘとして選択され、属性Ｂが、除外対象属性として入力データ作成部１０２に通知される。
【０１５３】
入力データ作成部１０２、および分類木作成・分類精度測定部１０３では、属性Ｂを除くデータに基づいて分類木生成、分類精度測定が実行され、この条件で、最大精度を持つ分類木（Ｔ（Ａ，Ｃｂｅｓｔ））として、図１１（ｃ）に示す分類木が生成される。
【０１５４】
このように、除外対象属性決定部１０４では、分類木の構成非葉ノードから、分割情報量Ｄ値が最大のノードＮｍａｘを特定し、Ｎｍａｘの子ノード作成時に用いられている属性を、入力データ作成部１０２に、除外対象属性として出力し、じゅんじ異なる構成の分類木を生成し、それぞれの条件での分類木の分類精度の最高値を比較して、その中の最高分類精度を持つ分類木を最終出力分類木とするものである。
【０１５５】
図１に示すデータ分類処理装置１００のデータベース１０１に図２に示すデータが格納されている場合に、データ分類処理装置１００の各構成要素が入力・出力するデータ例を図１２に示す。
【０１５６】
図１２は、
［入力データ作成部１０２が利用する属性］
［分類木作成・分類木精度測定部１０３でのテストデータ分類精度最高値］
［除外対象属性決定分１０４が除外対象として決定し出力する属性］
の各データについて、各処理サイクル毎のデータを示した図である。
【０１５７】
図１２に示す各処理サイクルの処理は以下の通りである。
サイクル１
すべての属性が利用されて分類木が作成され、分類精度６３．０８％が得られる。
除外対象属性決定部１０４は、除外対象属性として属性ａ５＿２を決定し、入力データ作成部１０２に出力する。
サイクル２
サイクル１で除外対象属性決定部が出力した属性ａ５＿２と、属性ａ５＿１以外の属性が利用されて分類木が作成され、分類精度は６３．６９％に改善される。
除外対象属性決定部１０４は、除外対象属性として属性ａ１５＿１を決定し、入力データ作成部１０２に出力する。
サイクル３
サイクル１で除外対象属性決定部が出力した属性ａ５＿２と、属性ａ５＿１、サイクル２で除外対象属性決定部が出力した属性ａ１５＿１と、属性ａ１５＿２以外の属性が利用されて分類木が作成され、分類精度は６５．９６％に改善される。
除外対象属性決定部１０４は、除外対象属性として属性ａ８＿２を決定し、入力データ作成部１０２に出力する。
サイクル４
サイクル１で除外対象属性決定部が出力した属性ａ５＿２と、属性ａ５＿１、サイクル２で除外対象属性決定部が出力した属性ａ１５＿１と、属性ａ１５＿２、サイクル３で除外対象属性決定部が出力した属性ａ８＿２以外の属性が利用されて分類木が作成され、分類精度が６５．２６％に悪化する
【０１５８】
この結果として、サイクル３で作成された分類木が、最高の分類精度を持つことが判明し、この分類木、すなわち、サイクル１で除外対象属性決定部が出力した属性ａ５＿２と、属性ａ５＿１、サイクル２で除外対象属性決定部が出力した属性ａ１５＿１と、属性ａ１５＿２以外の属性が利用されて生成した分類木を出力して処理が終了する。
【０１５９】
なお、図１２に示す例では、入力データ作成部１０２は、除外対象属性決定部１０４が出力する属性以外の属性も除外して入力データを作成している。たとえばサイクル２では、属性ａ５＿２以外にａ５＿１も除外して入力データを作成する。これは、あらかじめ属性ａ５＿２とａ５＿１が同種の属性であり、一方が除外対象となったときには他方も除外されるようにあらかじめ設定されていたためである。
【０１６０】
このように、除外対象属性決定部１０４が出力する属性と、実際に除外される属性の集合との組を１つ以上あらかじめ入力データ作成部１０２に保持しておき、除外対象属性決定部１０４が出力する属性と前者の属性が一致するときには、入力データ作成部１０２で後者の属性の集合を一括して削除するよう構成してもよい。
【０１６１】
また、上記の実施例では、除外対象属性決定部が出力する属性を決定するのに、分類木作成・分類精度測定部１０３が出力した分類木が利用された。具体的には、分類木の各ノードに分類されたデータを対象にし、データの分割情報量がもっとも大きいノードで利用された属性を除外対象とした。しかし、除外対象属性の決定方法はこの方法に限定されるものではない。たとえば、分類木作成・分類精度測定部１０３に入力された属性ごとに、その属性で全データを分類したときの分割情報量を算出し、分割情報量がもっとも大きい属性を除外対象属性として決定するよう構成してもよい。
【０１６２】
さらに、上記の実施例では、除外対象属性決定時に分割情報量を利用したが、分割前後のエントロピーの差や比など、他の指標を利用して除外対象属性を決定するよう構成してもよい。
【０１６３】
本発明は、上述した処理によって最適な分類木、すなわち、分類精度がより高い分類木を効率よく生成することができる。
本発明の処理では、
（１）レコードを学習用レコードとテスト用レコードに分ける。
（２）学習用レコードから分類木Ｔｎを作成し、テスト用レコードの分類精度（Ｐｎ）を測定する。
（３）テスト用レコードの分類精度（Ｐｎ）が、先に生成した分類木におけるテスト用レコードの分類精度（Ｐｎ−１）より低い場合、分類木（Ｔｎ−１）を出力して処理を終了する。
そうでない場合、以下の処理を行なう。
（４）Ｔｎでの分枝に用いられた属性で、分類精度に対する寄与度がもっとも小さいものを特定し、特定した属性を学習用レコードから除外し、（２）に処理を進める。
【０１６４】
なお、（１）のレコード分割処理では、広く用いられている交差検定の手順を採用してもよい。また（２）における分類木作成手法は、ＩＤ３またはＣ４．５でもよいが、他の手法でも構わない。さらに、（４）における、属性の分類精度に対する寄与度は、たとえば以下のように定義される。
（属性の寄与度）＝１／（その属性が選択された全ノードでの分割情報量の最小値）
【０１６５】
上記のように、本発明においては、作成した分類木で分類精度向上にもっとも寄与していない属性を除外して再度分類木を作成することを繰り返し、未知データに対する分類精度がもっとも高いものを選択する。したがって、Ｃ４．５のように、分類木の葉ノード近くで分割数の大きい属性が選択されてしまった結果、未知レコードに対する分類精度が低下してしまう場合でも、その属性を除外して分類木を作成し直すことにより、この問題を回避できる。また、特開平６−４４２０６号公報に記載の手法のように、事前に有意水準を決定する必要もない。
【０１６６】
次に、上述したデータ分類処理装置のハードウェア構成例について、図１３を参照して説明する。
【０１６７】
ＣＰＵ（Central Processing Unit）５０１は、ＯＳ（Operating System)、通信制御プログラム、図２、図５を参照して説明したデータ分類、ルール生成処理プログラム等、各種コンピュータ・プログラムに従った処理を実行する制御部である。
【０１６８】
ＲＯＭ（Read Only Memory）５０２は、ＣＰＵ５０１が使用するプログラムや演算パラメータ等を格納する。ＲＡＭ（Random Access Memory）５０３は、ＣＰＵ５０１の実行において使用するプログラムや、その実行において適宜変化するパラメータ等を格納する。これらはＣＰＵバスなどから構成されるホストバス５０４により相互に接続されている。
【０１６９】
ホストバス５０４は、ブリッジ５０５を介して、ＰＣＩ(Peripheral Component Interconnect/Interface)バスなどの外部バス５０６に接続されている。
【０１７０】
キーボード５０８、ポインティングデバイス５０９は、ユーザにより操作される入力デバイスである。ディスプレイ５１０は、液晶表示装置またはＣＲＴ（Cathode Ray Tube）などから成り、各種情報をテキストやイメージで表示する。
【０１７１】
ＨＤＤ（Hard Disk Drive）５１１は、ハードディスクを内臓し、ハードディスクを駆動し、ＣＰＵ５０１によって実行するプログラムや情報を記録または再生させる。ハードディスクは、図１に示すデータベース１０１に格納された分類処理対象となるデータ、例えば図２に示すデータが格納される。また、図４、図６、図８、図１０を参照して説明したデータ処理プログラム等、各種コンピュータ・プログラムが格納される。
【０１７２】
ドライブ５１２は、装着されている磁気ディスク、光ディスク、光磁気ディスク、または半導体メモリ等のリムーバブル記録媒体５２１に記録されているデータまたはプログラムを読み出して、そのデータまたはプログラムを、インタフェース５０７、外部バス５０６、ブリッジ５０５、およびホストバス５０４を介して接続されているＲＡＭ５０３に供給する。
【０１７３】
接続ポート５１４は、外部接続機器５２２を接続するポートであり、ＵＳＢ，ＩＥＥＥ１３９４等の接続部を持つ。接続ポート５１４は、インタフェース５０７、および外部バス５０６、ブリッジ５０５、ホストバス５０４等を介してＣＰＵ５０１等に接続されている。通信部５１５は、ネットワークに接続され、ＣＰＵ５０１、またはＨＤＤ５１１等からの供給データの送信、データ受信を実行する。
【０１７４】
なお、図１３に示すデータ分類処理装置のハードウェア構成例は、ＰＣを適用して構成したデータ分類処理装置の一例であり、本発明のデータ分類処理装置は、図１３に示す構成に限らず、図１に示す処理ブロックに対応する構成が実現され、図４、図６、図８、図１０に示すフローチャートに従った処理を実行可能な構成であればよい。
【０１７５】
以上、特定の実施例を参照しながら、本発明について詳解してきた。しかしながら、本発明の要旨を逸脱しない範囲で当業者が該実施例の修正や代用を成し得ることは自明である。すなわち、例示という形態で本発明を開示してきたのであり、限定的に解釈されるべきではない。本発明の要旨を判断するためには、冒頭に記載した特許請求の範囲の欄を参酌すべきである。
【０１７６】
なお、明細書中において説明した一連の処理はハードウェア、またはソフトウェア、あるいは両者の複合構成によって実行することが可能である。ソフトウェアによる処理を実行する場合は、処理シーケンスを記録したプログラムを、専用のハードウェアに組み込まれたコンピュータ内のメモリにインストールして実行させるか、あるいは、各種処理が実行可能な汎用コンピュータにプログラムをインストールして実行させることが可能である。
【０１７７】
例えば、プログラムは記録媒体としてのハードディスクやＲＯＭ（Read Only Memory)に予め記録しておくことができる。あるいは、プログラムはフレキシブルディスク、ＣＤ−ＲＯＭ(Compact Disc Read Only Memory)，ＭＯ(Magneto optical)ディスク，ＤＶＤ(Digital Versatile Disc)、磁気ディスク、半導体メモリなどのリムーバブル記録媒体に、一時的あるいは永続的に格納（記録）しておくことができる。このようなリムーバブル記録媒体は、いわゆるパッケージソフトウエアとして提供することができる。
【０１７８】
なお、プログラムは、上述したようなリムーバブル記録媒体からコンピュータにインストールする他、ダウンロードサイトから、コンピュータに無線転送したり、ＬＡＮ(Local Area Network)、インターネットといったネットワークを介して、コンピュータに有線で転送し、コンピュータでは、そのようにして転送されてくるプログラムを受信し、内蔵するハードディスク等の記録媒体にインストールすることができる。
【０１７９】
なお、明細書に記載された各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【産業上の利用可能性】
【０１８０】
以上、説明したように、本発明の構成によれば、分類木作成部の生成した分類木から分類精度向上に対する寄与度の低い属性を除外対象属性として決定し、除外対象属性を除く属性に基づく入力データ生成処理、分類木生成処理、および分類精度測定処理とを繰り返し実行して、繰り返し処理の中で生成する複数の分類木から分類精度のもっとも高い分類木を選択して出力する構成としたので、分類処理対象データの知識を持たない未知データに対しても、自動的に分類精度の高い分類木を効率的に生成することが可能となる。
【０１８１】
本発明の構成によれば、従来の分類木生成アルゴリズムＣ４．５を適用した場合の問題、すなわち、分類木の葉ノード近くで分割数の大きい属性が選択されてしまうと、未知レコードに対する分類精度が低下してしまうといった問題を解決することができる。すなわち、本発明の構成においては、分類の寄与度の低い属性を除外して分類木を再作成し、さらに分類精度を測定し、より分類精度の高い分類木を生成する構成であるので、分類精度の低下を防止することができる。また、前述した特許文献１（特開平６−４４２０６号公報）に記載の手法のように、事前に有意水準を決定する必要もなく、効率的な分類精度の高い分類木生成が可能となる。
【図面の簡単な説明】
【０１８２】
【図１】本発明に係るデータ分類処理装置（データマイニングシステム）の構成を示す図である。
【図２】本発明に係るデータ分類処理装置の分類処理対象となるデータ例を示す図である。
【図３】本発明に係るデータ分類処理装置における入力データ作成部が生成するデータ例を示す図である。
【図４】本発明に係るデータ分類処理装置における入力データ作成部の実行する処理シーケンスを説明するフローチャートである。
【図５】本発明に係るデータ分類処理装置における分類木作成・分類精度測定部が生成するデータ例を示す図である。
【図６】本発明に係るデータ分類処理装置における分類木作成・分類精度測定部の実行する処理シーケンスを説明するフローチャートである。
【図７】本発明に係るデータ分類処理装置における分類木作成・分類精度測定部の生成する分類精度一覧表ＴＢＬの例を示す図である。
【図８】本発明に係るデータ分類処理装置における除外対象属性決定部の実行する処理シーケンスを説明するフローチャートである。
【図９】本発明に係るデータ分類処理装置における除外対象属性決定部の実行する除外対象属性決定処理に適用する非葉ノードごとの分割情報量一覧表の例を示す図である。
【図１０】本発明に係るデータ分類処理装置（データマイニングシステム）の処理シーケンスを説明するフローチャートである。
【図１１】本発明に係るデータ分類処理装置における除外対象属性決定部の実行する除外属性の例、および分類木の例を示す図である。
【図１２】本発明に係るデータ分類処理装置（データマイニングシステム）の処理シーケンスを説明する図である。
【図１３】本発明に係るデータ分類処理装置（データマイニングシステム）のハードウェア構成例について説明する図である。
【図１４】データ分類処理に適用するレコードの例を説明する図である。
【図１５】分類木の例を示す図である。
【図１６】分類木の例を示す図である。
【図１７】分類木の例を示す図である。
【符号の説明】
【０１８３】
１００  データ分類処理装置（データマイニングシステム）
１０１  データベース
１０２  入力データ作成部
１０３  分類木作成・分類精度測定部
１０４  除外対象属性決定部
１５０  分類木
２０１  属性宣言部
２０２  データ部
３０１  分類木部
３０２  統計情報部
５０１  ＣＰＵ(Central processing Unit)
５０２  ＲＯＭ（Read-Only-Memory）
５０３  ＲＡＭ（Random Access Memory）
５０４  ホストバス
５０５  ブリッジ
５０６  外部バス
５０７  インタフェース
５０８  キーボード
５０９  ポインティングデバイス
５１０  ディスプレイ
５１１  ＨＤＤ（Hard Disk Drive）
５１２  ドライブ
５１４  接続ポート
５１５  通信部
５２１  リムーバブル記録媒体
５２２  外部接続機器
【図１】
2005208709.tif 000003
【図２】
2005208709.tif 000004
【図３】
2005208709.tif 000005
【図４】
2005208709.tif 000006
【図５】
2005208709.tif 000007
【図６】
2005208709.tif 000008
【図７】
2005208709.tif 000009
【図８】
2005208709.tif 000010
【図９】
2005208709.tif 000011
【図１０】
2005208709.tif 000012
【図１１】
2005208709.tif 000013
【図１２】
2005208709.tif 000014
【図１３】
2005208709.tif 000015
【図１４】
2005208709.tif 000016
【図１５】
2005208709.tif 000017
【図１６】
2005208709.tif 000018
【図１７】
2005208709.tif 000019