(57)【特許請求の範囲】
【請求項１】
学習データに基づいて特徴量を生成する、特徴量生成部と、
前記特徴量と前記特徴量の数を示す複雑さ要件とに応じて分割条件を生成する、分割条件生成部と、
前記学習データを前記分割条件に基づいてグループに分割する、学習データ分割部と、
分割前後のグループを用いて、前記分割条件ごとに有意性を評価する、学習データ評価部と、
分割後のグループにおいて、前記分割条件に有意性がある場合、前記分割条件に関連する決定木のノードを生成する、ノード生成部と、
を有することを特徴とする学習装置。
【請求項２】
請求項１に記載の学習装置であって、
前記分割前後のグループにおいて、すべての前記分割条件に有意性がない場合、前記複雑さ要件が示す前記特徴量の数を増加させ、前記分割条件生成部に前記分割条件を追加させる、分割条件追加部と、
を有することを特徴とする学習装置。
【請求項３】
請求項１又は２に記載の学習装置であって、
前記分割条件生成部は、前記特徴量間の関係性を表す論理演算子を用いて、前記分割条件を生成する
ことを特徴とする学習装置。
【請求項４】
請求項３に記載の学習装置であって、
前記分割条件生成部は、前記複雑さ要件が示す、前記分割条件で使用する前記特徴量の数（Ｆ１、Ｆ２）が二つである場合、前記分割条件を、以下の条件を用いて生成する
Ｆ１  ａｎｄ  Ｆ２
ｎｏｔ  Ｆ１  ａｎｄ  Ｆ２
Ｆ１  ｏｒ  Ｆ２
Ｆ１  ａｎｄ  ｎｏｔ  Ｆ２
Ｆ１  ｘｏｒ  Ｆ２
ことを特徴とする学習装置。
【請求項５】
（ａ）学習データに基づいて特徴量を生成する、ステップと、
（ｂ）前記特徴量と前記特徴量の数を示す複雑さ要件とに応じて分割条件を生成する、ステップと、
（ｃ）前記学習データを前記分割条件に基づいてグループに分割する、ステップと、
（ｄ）分割前後のグループを用いて、前記分割条件ごとに有意性を評価する、ステップと、
（ｅ）分割後のグループにおいて、前記分割条件に有意性がある場合、前記分割条件に関連する決定木のノードを生成する、ステップと、
を有することを特徴とする学習方法。
【請求項６】
請求項５に記載の学習方法であって、
（ｆ）前記分割前後のグループにおいて、すべての前記分割条件に有意性がない場合、前記複雑さ要件が示す前記特徴量の数を増加させ、前記分割条件を追加させる、ステップと、
を有することを特徴とする学習方法。
【請求項７】
請求項５又は６に記載の学習方法であって、
前記（ｂ）のステップにおいて、前記特徴量間の関係性を表す論理演算子を用いて、前記分割条件を生成する
ことを特徴とする学習方法。
【請求項８】
請求項７に記載の学習方法であって、
前記（ｂ）のステップにおいて、前記複雑さ要件が示す、前記分割条件で使用する前記特徴量（Ｆ１、Ｆ２）の数が二つである場合、前記分割条件を、以下の条件を用いて生成する
Ｆ１  ａｎｄ  Ｆ２
ｎｏｔ  Ｆ１  ａｎｄ  Ｆ２
Ｆ１  ｏｒ  Ｆ２
Ｆ１  ａｎｄ  ｎｏｔ  Ｆ２
Ｆ１  ｘｏｒ  Ｆ２
ことを特徴とする学習方法。
【請求項９】
コンピュータに、
（ａ）学習データに基づいて特徴量を生成する、ステップと、
（ｂ）前記特徴量と前記特徴量の数を示す複雑さ要件とに応じて分割条件を生成する、ステップと、
（ｃ）前記学習データを前記分割条件に基づいてグループに分割する、ステップと、
（ｄ）分割前後のグループを用いて、前記分割条件ごとに有意性を評価する、ステップと、
（ｅ）分割後のグループにおいて、前記分割条件に有意性がある場合、前記分割条件に関連する決定木のノードを生成する、ステップと、
を実行させるプログラム。
【請求項１０】
請求項９に記載のプログラムであって、
前記プログラムが、前記コンピュータに、
（ｆ）前記分割前後のグループにおいて、すべての前記分割条件に有意性がない場合、前記複雑さ要件が示す前記特徴量の数を増加させ、前記分割条件を追加させる、ステップを実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、決定木による学習をする学習装置、学習方法に関し、更には、これらを実現するためのプログラムに関する。
【背景技術】
【０００２】
ＩＴ（Information Technology）システムにおいて、システムの構成管理及び構成変更は、大きく三つのフェーズに分けられる。そして、システムの構成管理及び構成変更は、三つのフェーズそれぞれにおいて行われ、次に示す（１）（２）（３）の作業を反復することにより実現される。【０００３】
（１）システム構成を把握する作業。（２）変更要件の定義をする作業。（３）現在運用中のシステム構成を、（１）（２）から導かれるシステムへ変更する操作手順の生成、及び、生成した操作手順を実行する作業。【０００４】
ところが、これら三つの作業のうち、（３）に示した作業には、多大な作業工数を費やしている。そこで、作業工数を削減するための技術が提案されている。【０００５】
関連する技術として、特許文献１には、システムを構成する要素の動作状態と、その動作状態間の制約とを定義することで、システムの変更に用いる操作手順を生成する技術が開示されている。【０００６】
特許文献２には、部品の状態と制約関係とを状態遷移図により表現する技術が開示されている。【０００７】
特許文献３には、決定木の学習を実行する前に、パラメータ間の交互作用を検証することで、依存関係がありそうなパラメータと、そうでないパラメータとを識別し、分割条件候補となるパラメータのセットを絞り込む手法が開示されている。【０００８】
非特許文献１及び非特許文献２には、操作手順を自動化するソフトウェアツールが開示されている。そのソフトウェアツールによれば、システム変更後の状態、又は操作手順を定義情報として入力し、自動的にシステムの変更、及び設定を行う。
【０００９】
非特許文献３及び４には、サーバ装置のリソース（ＣＰＵ（Central Processing Unit）やメモリ割当て量など）、アプリケーションの組み合わせを実際に様々なパターンで試行し評価、学習することで最適な変更手順、又は変更パラメータを導出する強化学習を用いた技術が開示されている。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開２０１５−２１５８８５号公報
【特許文献２】特開２０１５−２１５８８７号公報
【特許文献３】特開２００５−０６３３５３号公報
【非特許文献】
【００１１】
【非特許文献１】"Puppet"、［online］、［平成29年1月19日検索］、インターネット＜URL：https://puppet.com/＞
【非特許文献２】"Ansible"、［online］、［平成29年1月19日検索］、インターネッ ト＜URL：https://www.ansible.com/＞
【非特許文献３】J. Rao, X. Bu, C. Z. Xu and K. Wang、"A Distributed Self-Learning Approach for Elastic Provisioning of Virtualized Cloud Resources,"、［online］、［平成 29年1月19日検索］平成23年8月30日、IEEE Xplore、［平成29年1月19日検索］、インターネット＜URL：http://ieeexplore.ieee.org/abstract/document/6005367/＞
【非特許文献４】I. J. Jureta, S. Faulkner, Y. Achbany and M. Saerens、"Dynamic Web Service Composition within a Service-Oriented Architecture,"、［online］、［平成29年1月19日検索］平成19年7月30日、IEEE Xplore、［平成29年1月19日検索］、インターネット＜URL：http://ieeexplore.ieee.org/document/4279613/＞
【発明の概要】
【発明が解決しようとする課題】
【００１２】
しかしながら、非特許文献１及び非特許文献２に開示されている、操作手順を自動化するソフトウェアツールが自動化できるのは、操作手順の実行のみで、操作手順の作成は対象外である。【００１３】
そこで、非特許文献１又は非特許文献２に、操作手順の生成を自動化する、特許文献１又は特許文献２に開示の技術を適用することが考えられる。すなわち、特許文献１又は特許文献２に開示の技術を用いて、操作手順の実行を自動化するソフトウェアツールの入力の形式に合わせた、システムの構成を変更する操作手順を示す情報を生成する。そして、生成した操作手順を、非特許文献１又は非特許文献２に開示の技術に適用することで、操作手順の作成から実行までを自動化する。【００１４】
ところが、特許文献１及び特許文献２に開示された技術では、事前に（１）システム構成を把握する作業、（２）変更要件の定義をする作業を、手作業で行う必要があるため、多大な作業工数を費やすことになるという問題がある。【００１５】
そこで、上述した問題に対して、非特許文献３又は非特許文献４に開示された技術を用いることが考えられる。つまり、サーバ装置のリソース（例えば、ＣＰＵ、メモリ割当て量など）、又はアプリケーションの組み合わせを、実際に様々なパターンで試行し評価、学習することで、操作手順、及びパラメータを導出することが考えられる。【００１６】
しかし、上述した非特許文献３、４に開示された強化学習を用いた自動化は、特許文献１、２に開示されているような、システム内の構成要素間の依存関係を直接扱うアプローチと異なり、評価、学習の対象は、あるシステムの状態における特定の制御内容の好ましさである。制御内容は、例えば、システムの応答速度などの観測可能な値によって規定される。【００１７】
そのため、強化学習では、システムの状態を観測する手段と、実行可能な制御集合とを入力するだけで学習が実行可能となるため、適用が比較的容易である。ところが、強化学習では、学習結果から、依存性をはじめとした構成要素間の挙動に関する関係性を、一般には読み取ることができない。そのため、学習結果を別の制御タスクへ再利用することが困難である。【００１８】
そこで、こうした問題への対処方法として、強化学習にいわゆる関数近似を適用することが考えられる。強化学習における関数近似とは、学習の結果得られた具体的な制御に関する好ましさを示す情報を、より抽象的な条件から予測できる近似関数を求めることである。すなわち、抽象的な条件から予測できる近似関数を学習することである。【００１９】
上述した対処方法は、元々はロボット制御などの分野において、連続量（無限に選択肢が存在する）の制御を取り扱う際、すべての制御パターンをコンピュータの記憶領域で管理することが不可能なため、無限集合を有限集合へマッピングし、その有限集合における制御パターンを取り扱うために発展してきた手法である。また、上述した対処方法は、記憶領域の問題だけでなく、広大かつ雑多な選択肢を適切に抽象化することで学習結果の汎用性を高めることもできる。【００２０】
関数近似で用いる近似関数は、近似対象の性質や近似の目的に合わせて選択する必要がある。代表的な関数としては、線形多項式、又はニューラルネットワーク、又は決定木などが挙げられる。【００２１】
しかし、システムの設計、又は制御内容からその設計、制御の良し悪しを予測する問題においては、決定木による関数近似が有力な近似手法の一つと考えられる。その理由として、まず、パラメータ間に依存関係があることが挙げられる。すなわち、あるパラメータの最適値は、他のパラメータの値に依存して異なる値となるからである。また、非線形な挙動への対応ができることが挙げられる。設定値の些細な違いが好ましさに大きく影響するためである。更に、生成された関数の解釈性の高さが優れているからである。すなわち、その関数が制御特性をより良く表現できているかを、人間が評価できるためである。【００２２】
決定木の代表的な学習としてＣ４.５、ＣＡＲＴ（Classification And Regression Trees）、ＣＨＡＩＤ（Chi-squared Automatic Interaction Detection）などがある。これらは、木の分割条件を選択する際、使用する指標が異なることが特徴である。例えば、Ｃ４．５では、分割条件で分割したデータが、分割前のデータと比較してよりエントロピーを減少させる分割条件を採用する。【００２３】
決定木の学習により生成される分割条件は、設計や制御に関する単一のパラメータにより規定される論理式で表される。具体的に説明する。通信帯域、及びＣＰＵコア数といった二つのパラメータを調整することで、アプリケーションサーバのスループットを最適化するというタスクの場合、学習された決定木の節（ノード）に関連する分割条件は、例えば、「通信帯域＜１０Ｍｂｐｓ」、及び「ＣＰＵ数＞１」などが考えられる。【００２４】
また、パラメータが他のパラメータに依存する場合、分割条件の分割先で依存するパラメータに関する分割条件を採用することになる。例えば、「通信帯域≧１０Ｍｂｐｓ」の場合、ＣＰＵコア数がボトルネックとなる。また、ＣＰＵコア数がスループットに影響しないシステムの場合、決定木の頂点ノードで「通信帯域＜１０Ｍｂｐｓ」の分割条件を設定し、分割先のノードでＣＰＵコア数に関する分割条件を定義する。【００２５】
しかし、決定木の学習では、単一のパラメータごとにどれだけ学習データをうまく分類できるかを評価して分割条件を決定するため、複数のパラメータ間に依存関係がある場合、分割条件を適切に設定できないことがある。例えば、上述した通信帯域、及びＣＰＵコア数といったパラメータに加え、更にメモリサイズなどの単一のパラメータが制御の対象である場合、分割条件を適切に設定できない。具体的には、メモリサイズが、見かけ上最もスループットへ影響を与えるパラメータだったとすると、分割条件としてメモリサイズに関するものが採用されてしまう。【００２６】
そうすると、分割後の学習データは、メモリサイズによる分割条件で分断されてしまい、分断後の学習データそれぞれにおいて、上述したような通信帯域及びＣＰＵコア数の依存関係に従った分割条件が導かれる保証はない。このような問題は、パラメータ間の依存関係の実体が排他的論理和であるときに顕著である。【００２７】
図１は、学習データの一例を示す図である。図１に示す「Ａ」「Ｂ」「Ｃ」「Ｄ」は、パラメータ（真：１、偽：０のバイナリ値）を示している。また、「Ｙ」は、近似したい値（予測値）を示している。具体的には、予測値Ｙは、パラメータＡ、Ｂの排他的論理和（真：１、偽：０）を１０倍した実数値に［０， １］区間の一様乱数を加えた値である。なお、パラメータＣ、Ｄは、実際には予測には全く影響しないパラメータである。なお、「ｉｄ」「１」から「８」は、パラメータＡからＤと予測値Ｙとを有する行それぞれに付された識別番号である。【００２８】
従って、図１に示す学習データを用いて生成される決定木は、パラメータＣ、Ｄを分割条件に含まない、図２のような決定木になるのが理想的である。図２は、理想的な決定木の一例を示す図である。ところが、既存の決定木の学習を用いて生成した決定木は、図３のような決定木になる。図３は、既存の決定木の学習により生成された決定木の一例を示す図である。【００２９】
既存の決定木の学習では、単一のパラメータで評価するため、図２に示した決定木と比較すると、図３に示した決定木には不要な分割条件を含むため、予測精度の低い決定木が生成されてしまう。言い換えれば、本質的な分割条件が全体に適用されていない、複雑な決定木が生成されてしまう。【００３０】
具体的には、パラメータＣは予測値Ｙに影響を与えないパラメータであるにもかかわらず、最も予測値と相関があるパラメータであるため、最上位の分割条件となる。そのため、図３に示す左側（Ｆａｌｓｅ：Ｃ≠１）の部分木では、パラメータＡ、Ｂによる排他的論理和を表す決定木が生成されたものの、図３に示す右側（Ｔｒｕｅ：Ｃ＝１）の部分木では、パラメータＡ、Ｂによる排他的論理和を表す部分木が生成されない。【００３１】
そこで、特許文献３を用いることが考えられる。特許文献３では、決定木の学習を実行する前に、パラメータ間の交互作用を検証することで、依存関係がありそうなパラメータと、そうでないパラメータとを識別し、分割条件候補となるパラメータセットを絞り込んでいる。しかし、特許文献３は、決定木の学習前において、パラメータの品質を安定化させることを目的としており、上述した問題を解決するものではない。【００３２】
本発明の目的の一例は、決定木の予測精度を向上させる学習装置、学習方法、及びプログラムを提供することにある。
【課題を解決するための手段】
【００３３】
上記目的を達成するため、本発明の一側面における学習装置は、
学習データに基づいて特徴量を生成する、特徴量生成部と、
前記特徴量と前記特徴量の数を示す複雑さ要件とに応じて分割条件を生成する、分割条件生成部と、
前記学習データを前記分割条件に基づいてグループに分割する、学習データ分割部と、
分割前後のグループを用いて、前記分割条件ごとに有意性を評価する、学習データ評価部と、
分割前後のグループにおいて、前記分割条件に有意性がある場合、前記分割条件に関連する決定木のノードを生成する、ノード生成部と、
を有することを特徴とする。【００３４】
また、上記目的を達成するため、本発明の一側面における学習方法は、
（ａ）学習データに基づいて特徴量を生成する、ステップと、
（ｂ）前記特徴量と前記特徴量の数を示す複雑さ要件とに応じて分割条件を生成する、ステップと、 
（ｃ）前記学習データを前記分割条件に基づいてグループに分割する、ステップと、
（ｄ）分割前後のグループを用いて、前記分割条件ごとに有意性を評価する、ステップと、
（ｅ）分割後のグループにおいて、前記分割条件に有意性がある場合、前記分割条件に関連する決定木のノードを生成する、ステップと、
を有することを特徴とする。【００３５】
更に、上記目的を達成するため、本発明の一側面におけるプログラムは、
コンピュータに、
（ａ）学習データに基づいて特徴量を生成する、ステップと、
（ｂ）前記特徴量と前記特徴量の数を示す複雑さ要件とに応じて分割条件を生成する、ステップと、
（ｃ）前記学習データを前記分割条件に基づいてグループに分割する、ステップと、
（ｄ）分割前後のグループを用いて、前記分割条件ごとに有意性を評価する、ステップと、
（ｅ）分割後のグループにおいて、前記分割条件に有意性がある場合、前記分割条件に関連する決定木のノードを生成する、ステップと、
を実行させることを特徴とする。
【発明の効果】
【００３６】
以上のように本発明によれば、決定木の予測精度を向上させることができる。
【図面の簡単な説明】
【００３７】
【図１】図１は、学習データの一例を示す図である。
【図２】図２は、理想的な決定木の一例を示す図である。
【図３】図３は、既存の決定木の学習により生成された決定木の一例を示す図である。
【図４】図４は、学習装置の一例を示す図である。
【図５】図５は、学習装置を有するシステムの一例を示す図である。
【図６】図６は、複雑さ要件に対する分割条件の一例を示す図である。
【図７】図７は、分割結果の一例を示す図である。
【図８】図８は、評価結果の一例を示す図である。
【図９】図９は、評価結果の一例を示す図である。
【図１０】図１０は、学習装置の動作の一例を示す図である。
【図１１】図１１は、学習装置を実現するコンピュータの一例を示す図である。
【発明を実施するための形態】
【００３８】
（実施の形態）
以下、本発明の実施の形態について、図１から図１１を参照しながら説明する。
【００３９】
［装置構成］
最初に、図４を用いて、本実施の形態における学習装置１０の構成について説明する。図４は、学習装置の一例を示す図である。
【００４０】
図４に示すように、学習装置１０は、決定木の予測精度を向上させるための装置である。学習装置１０は、特徴量生成部１１と、分割条件生成部１２と、学習データ分割部１３と、学習データ評価部１４と、ノード生成部１５とを有する。
【００４１】
このうち、特徴量生成部１１は、学習データに基づいて特徴量を生成する。分割条件生成部１２は、特徴量と特徴量の数を示す複雑さ要件とに応じて分割条件を生成する。学習データ分割部１３は、学習データを分割条件に基づいてグループに分割する。学習データ評価部１４は、分割前のグループと分割後のグループとを用いて、分割条件ごとに有意性を評価する。ノード生成部１５は、分割前後のグループにおいて、分割条件に有意性がある場合、分割条件に関連する分割条件決定木のノードを生成する。
【００４２】
このように、本実施の形態では、特徴量と複雑さ要件とに応じて生成した分割条件を用いて、学習データをグループに分割して、分割前のグループと分割後のグループとを用いて、分割条件ごとに有意性を評価する。そして、分割前後のグループにおいて、分割条件に有意性がある場合、分割条件に関連する分割条件決定木のノードを生成する。そうすることで、決定木には不要な分割条件を含まない、予測精度の高い決定木を生成することができる。言い換えれば、本質的な分割条件を適用した決定木が生成できる。
【００４３】
続いて、図５を用いて、本実施の形態における学習装置１０の構成をより具体的に説明する。図５は、学習装置を有する学習システムの一例を示す図である。
【００４４】
図５に示すように、本実施の形態における学習装置１０は、特徴量生成部１１と、分割条件生成部１２と、学習データ分割部１３と、学習データ評価部１４と、ノード生成部１５と、分割条件追加部１６とを有する。
【００４５】
また、図５においては、システムは、学習装置１０に加え、学習装置１０へ学習データ２０を入力するための入力装置３０と、学習装置１０が生成した決定木データ５０を出力するための出力装置４０とを有する。学習データ２０は、決定木を生成するシステムに入力する、設計ルールを表現したデータである。
【００４６】
特徴量生成部１１は、入力装置３０を介して学習データ２０を取得した後、学習データ２０に基づいて、分割条件の要素となる特徴量（抽象的な特徴量）を生成する。その後、特徴量生成部１１は、生成した特徴量に基づいて、学習データ２０を変換する。
【００４７】
具体的には、図１に示した学習データを変換後の学習データとした場合、パラメータＡ、Ｂ、Ｃ、Ｄが特徴量（抽象的な特徴量）となり、Ａ列からＤ列までの各行の値は、その特徴量に関する元の学習データの評価値を表している。そして、図１において、一行目の学習データに該当する、変換前の学習データが「サーバ装置ＭのＣＰＵ数：１」「サーバ装置ＮのＣＰＵ数：３」「サーバ装置Ｍの通信帯域：２」「サーバ装置Ｎの通信帯域：１」で、抽象的な特徴量Ａが「サーバ装置ＭのＣＰＵ数＞サーバ装置ＮのＣＰＵ数」であるとする。その場合において、当該学習データは特徴量Ａの評価値として、特徴量Ａで示される論理式を満たさない（１＜３）ためＦａｌｓｅ（０）という評価値を得る。なお、上述したサーバ装置Ｍの通信帯域「２」、及びサーバ装置Ｎの通信帯域「１」は、例えば、通信帯域に割り付けられた番号を示す。
【００４８】
このように、サーバ装置間のＣＰＵ数の大小比較という特徴量Ａは、具体的な設計値ではなく、パラメータの相対的な関係性を示した例である。そのため、この考え方に基づいて、ＣＰＵ数に限定されずにＩＰアドレス、通信帯域、メモリ割り当て数など様々な設計、パラメータを相対的な関係性で評価できる。なお、予測値Ｙは、元の学習データと同じとし、変換は行わない。
【００４９】
分割条件生成部１２は、学習データに基づいて生成された特徴量と、指定された複雑さ要件とに応じて、分割条件（具体的な分割条件）を生成する。複雑さ要件は、一つの分割条件に使用する特徴量の数を示し、初期値は１である。また、段階的に複雑さを増やす場合、複雑さ要件に上限値も設定する。例えば、上限値は２とすることが考えられる。
【００５０】
また、具体的な分割条件は、複雑さ要件が１の場合、図１の学習データの分割条件は、「Ａ＝Ｔｒｕｅ（１）／Ｂ＝Ｔｒｕｅ（１）／Ｃ＝Ｔｒｕｅ（１）／Ｄ＝Ｔｒｕｅ（１）」の四つとなる。また、複雑さ要件が２の場合、分割条件は特徴量を二つ含む論理式となる。
【００５１】
図６は、複雑さ要件に対する分割条件を示す図である。図６には、複雑さ要件が２の場合（図６の分割条件６０）に、図１の学習データに対して生成される、分割条件６１が示されている。すなわち、図１に示した特徴量Ａ、Ｂ、Ｃ、Ｄから二つを選び、分割条件６０に示した五つの条件（Ｆ１  ａｎｄ  Ｆ２、ｎｏｔ  Ｆ１  ａｎｄ  Ｆ２、Ｆ１  ｏｒ
Ｆ２、Ｆ１  ａｎｄ  ｎｏｔ  Ｆ２、Ｆ１  ｘｏｒ  Ｆ２）を適用して、図６に示す３０通り（４Ｃ２×５通り）の分割条件６１を生成する。
【００５２】
また、複雑さ要件が３以上の場合、複雑さ要件の数だけ、特徴量を含んだ論理式を生成する。なお、初期動作では複雑さ要件の初期値に従い、上述した四つの分割条件「Ａ＝Ｔｒｕｅ（１）／Ｂ＝Ｔｒｕｅ（１）／Ｃ＝Ｔｒｕｅ（１）／Ｄ＝Ｔｒｕｅ（１）」が生成される。
【００５３】
学習データ分割部１３は、学習データと分割条件とを取得した後、学習データを分割条件に従い分割する。学習データの分割は、例えば、図１に示す学習データを、複雑さ要件が１の分割条件「Ａ＝Ｔｒｕｅ（１）／Ｂ＝Ｔｒｕｅ（１）／Ｃ＝Ｔｒｕｅ（１）／Ｄ＝Ｔｒｕｅ（１）」に従い分割した場合、図７に示すような分割結果７０となる。図７は、分割結果の一例を示す図である。
【００５４】
学習データ評価部１４は、分割結果を取得した後、分割結果がどの程度学習データをよりよく分割できるかを評価する。評価は、分割前後のグループ間の予測値の分散に統計的な有意差があるか否かを評価する。すなわち、分割前後のグループに対して等分散検定を行い、予め設定された基準となる有意水準を用いて算出される有意水準において、分割前後のグループの分散が等しいという帰無仮説が棄却できる場合、その分割条件を有効な分割条件と見做して決定木の枝の分割条件とする。
【００５５】
なお、上述したような単一論式による二分木の場合、分割後のグループは二つ生成されるため、実施される等分散検定は、分割前対分割後の二つのグループがあり、どちらかの検定が有意であれば、その分割条件は有効と見做す。
【００５６】
また、有効な分割条件が複数検出された場合、等分散検定におけるｐ値が、最小の分割条件を実際の決定木の分割条件として採用する。等分散検定は、予測値の確率分布に関する仮定の違いなどによりいくつかの手法が存在する。例えば、予測値に特定の確率分布を仮定しない場合にはBrown-Forsythe検定を用いる。なお、学習対象のデータの性質に応じて検定手法を選択してもよい。
【００５７】
図８に、図７における分割結果に基づく評価結果を示す。図８は、評価結果の一例を示す図である。有意水準は、予め設定された基準となる有意水準を、検定実施回数で割った値とする。すなわち、これは等分散検定の繰り返しによる偽陽性の発生確率の増大に対応するための措置である。図８においては、基準となる有意水準を０．０１とし、検定実施回数を４×２としているので、有意水準は０．０１／（４×２）＝０．００１２５となる。なお、この有意水準の設定は一例であり限定されない。
【００５８】
分割条件追加部１６は、評価結果を取得した後、すべての分割条件について有意性がない場合（ｐ値が有意水準以上である場合）、より複雑な分割条件で再評価を行うため、複雑さ要件を増加する。
【００５９】
具体的には、図８に示した評価結果８０の場合、分割条件追加部１６は、すべての分割条件について有意性がないので、現状の複雑さ要件を増加させる。例えば、現状の複雑さ要件は１であるので、複雑さ要件を２とする。
【００６０】
その後、分割条件生成部１２は、更新された複雑さ要件に従い分割条件を再生成する。続いて、分割条件生成部１２は、複雑さ要件が２であるので、図６に示した分割条件を生成する。以降、学習データ分割部１３、学習データ評価部１４は、新たな分割条件に対して、分割と評価とを実施する。
【００６１】
図９は、評価結果の一例を示す図である。図９では、有意性が認められる分割条件が複数検出されているが、ｐ値が最小の分割条件であるＡとＢとの排他的論理和「ＡｘｏｒＢ」が最適な分割条件として採用される。
【００６２】
また、学習データ評価部１４は、最適な分割条件が検出された場合、その最適な分割条件はノード生成部１５へ送られる。
【００６３】
ノード生成部１５は、その最適な分割条件に関連付けられた決定木のノードを一つ生成する。また、ノード生成部１５は、そのノードにおける分割条件により分割されたグループを分割条件生成部１２へ送る。なお、二分木の場合、二つのグループとなる。続いて、分割条件生成部１２は、分割されたグループを受けた場合、複雑さ要件を初期値である１に設定する。そして、分割条件生成部１２は、受け取ったグループを新たに分割前のグループと見做して上述した処理を継続する。
【００６４】
更に、ノード生成部１５は、有効な分割条件が検出されず、複雑さ要件を増加させていきその上限に達しても有効な分割条件が見つからない場合、その分割できなかったグループを終端ノードとしてノード生成の対象にする。図９に示した評価結果９０の場合、分割後のグループ１（真）（５，６，７，８）、グループ０（偽）（１，２，３，４）それぞれは複雑さ要件の上限値である２まで、分割条件を評価しても有意な分割条件が検出されない。その場合、分割条件の生成を停止して、ノード生成部１５は、当該グループを決定木の最下層ノード（葉）とする。
【００６５】
そして、すべてのグループに関して最下層ノードの生成が完了した場合、ノード生成部１５は、生成した決定木データ５０を、出力装置４０を介して出力する。その結果、図２に示した決定木が出力される。
【００６６】
［装置動作］
次に、本発明の実施の形態における学習装置の動作について図１０を用いて説明する。図１０は、学習装置の動作の一例を示す図である。以下の説明においては、適宜図１から図９を参酌する。また、本実施の形態では、学習装置を動作させることによって、学習方法が実施される。よって、本実施の形態における学習方法の説明は、以下の学習装置の動作説明に代える。
【００６７】
ステップＡ１において、特徴量生成部１１は、取得した学習データ２０に基づいて、分割条件の要素となる特徴量（抽象的な特徴量）を生成する。その後、特徴量生成部１１は、生成した特徴量に基づいて、学習データ２０を変換する。
【００６８】
ステップＡ２において、分割条件生成部１２は、変換した学習データに含まれる特徴量と、指定された分割条件の複雑さ要件とに応じて、分割条件（具体的な分割条件）を生成する。ステップＡ３において、学習データ分割部１３は、学習データと分割条件とを取得した後、学習データを分割条件に従い分割する。 
【００６９】
ステップＡ４において、学習データ評価部１４は、分割結果を取得した後、分割結果がどの程度学習データをよりよく分割できているか否かを評価する。例えば、分割前後のグループ間の予測値の分散に統計的な有意差があるか否かを評価する。
【００７０】
ステップＡ５において、学習データ評価部１４は、すべての分割条件について有意性があるか否かを判定する。有意性がない場合（ステップＡ５：Ｎｏ）、ステップＡ７において、分割条件追加部１６は、複雑さ要件が上限値であるか否かを判定する。
【００７１】
有意性がある場合（ステップＡ５：Ｙｅｓ）、又は、有意性がなく複雑さ要件が上限値である場合（ステップＡ７：Ｙｅｓ）、ステップＡ６において、ノード生成部１５は、有意性がある分割条件に関連付けられた決定木のノードを生成する。
【００７２】
ステップＡ８において、複雑さ要件が上限値でない場合（ステップＡ７：Ｎｏ）、分割条件追加部１６は、より複雑な分割条件で再評価を行うため、複雑さ要件を増加する。そして、増加した複雑さ要件において、再度ステップＡ２からＡ５の処理を行う。なお、現状の複雑さ要件が１であれば、複雑さ要件を２とする。
【００７３】
ステップＡ９において、ノード生成部１５は、すべてのグループに対して最下層ノードを生成したか否かを判定する。すべてのグループの最下層ノードを生成した場合（ステップＡ９：Ｙｅｓ）、この処理を終了する。すべてのグループの最下層ノードを生成していない場合（ステップＡ９：Ｎｏ）、ステップＡ１０において、分割条件生成部１２は、複雑さ要件を初期値である１に設定する。そして、分割条件生成部１２は、分割されたグループに対して新たに処理を実行する。
【００７４】
［本実施の形態の効果］
以上のように本実施の形態によれば、特徴量と複雑さ要件とに応じて生成した分割条件を用いて、学習データをグループに分割する。そして、分割前のグループと分割後のグループとを用いて、分割条件ごとに有意性を評価する。その結果、分割前後のグループにおいて、分割条件に有意性がある場合、分割条件に関連する分割条件決定木のノードを生成する。そうすることで、決定木には不要な分割条件を含まない、予測精度の高い決定木を生成することができる。言い換えれば、本質的な分割条件を適用した決定木が生成できる。
【００７５】
［プログラム］
本発明の実施の形態におけるプログラムは、コンピュータに、図１０に示すステップＡ１からＡ１０を実行させるプログラムであればよい。このプログラムをコンピュータにインストールし、実行することによって、本実施の形態における学習装置と学習方法とを実現することができる。この場合、コンピュータのプロセッサは、特徴量生成部１１、分割条件生成部１２、学習データ分割部１３、学習データ評価部１４、ノード生成部１５、分割条件追加部１６として機能し、処理を行なう。
【００７６】
また、本実施の形態におけるプログラムは、複数のコンピュータによって構築されたコンピュータシステムによって実行されてもよい。この場合は、例えば、各コンピュータが、それぞれ、特徴量生成部１１、分割条件生成部１２、学習データ分割部１３、学習データ評価部１４、ノード生成部１５、分割条件追加部１６のいずれかとして機能してもよい。
【００７７】
［物理構成］
ここで、実施の形態におけるプログラムを実行することによって、学習装置を実現するコンピュータについて図１１を用いて説明する。図１１は、学習装置を実現するコンピュータの一例を示す図である。
【００７８】
図１１に示すように、コンピュータ１１０は、ＣＰＵ１１１と、メインメモリ１１２と、記憶装置１１３と、入力インターフェイス１１４と、表示コントローラ１１５と、データリーダ／ライタ１１６と、通信インターフェイス１１７とを備える。これらの各部は、バス１２１を介して、互いにデータ通信可能に接続される。なお、コンピュータ１１０は、ＣＰＵ１１１に加えて、又はＣＰＵ１１１に代えて、ＧＰＵ（Graphics Processing Unit）、又はＦＰＧＡ（Field-Programmable Gate Array）を備えていてもよい。
【００７９】
ＣＰＵ１１１は、記憶装置１１３に格納された、本実施の形態におけるプログラム（コード）をメインメモリ１１２に展開し、これらを所定順序で実行することにより、各種の演算を実施する。メインメモリ１１２は、典型的には、ＤＲＡＭ（Dynamic Random Access Memory）等の揮発性の記憶装置である。また、本実施の形態におけるプログラムは、コンピュータ読み取り可能な記録媒体１２０に格納された状態で提供される。なお、本実施の形態におけるプログラムは、通信インターフェイス１１７を介して接続されたインターネット上で流通するものであってもよい。
【００８０】
また、記憶装置１１３の具体例としては、ハードディスクドライブの他、フラッシュメモリ等の半導体記憶装置があげられる。入力インターフェイス１１４は、ＣＰＵ１１１と、キーボード及びマウスといった入力機器１１８との間のデータ伝送を仲介する。表示コントローラ１１５は、ディスプレイ装置１１９と接続され、ディスプレイ装置１１９での表示を制御する。
【００８１】
データリーダ／ライタ１１６は、ＣＰＵ１１１と記録媒体１２０との間のデータ伝送を仲介し、記録媒体１２０からのプログラムの読み出し、及びコンピュータ１１０における処理結果の記録媒体１２０への書き込みを実行する。通信インターフェイス１１７は、ＣＰＵ１１１と、他のコンピュータとの間のデータ伝送を仲介する。
【００８２】
また、記録媒体１２０の具体例としては、ＣＦ（Compact Flash（登録商標））及びＳＤ（Secure Digital）等の汎用的な半導体記憶デバイス、フレキシブルディスク（Flexible Disk）等の磁気記録媒体、又はＣＤ−ＲＯＭ（Compact Disk Read Only Memory）などの光学記録媒体があげられる。
【００８３】
なお、本実施の形態における学習装置１０は、プログラムがインストールされたコンピュータではなく、各部に対応したハードウェアを用いることによっても実現可能である。更に、学習装置１０は、一部がプログラムで実現され、残りの部分がハードウェアで実現されていてもよい。
【００８４】
［付記］
以上の実施の形態に関し、更に以下の付記を開示する。上述した実施の形態の一部又は全部は、以下に記載する（付記１）から（付記１２）により表現することができるが、以下の記載に限定されるものではない。
【００８５】
（付記１）
学習データに基づいて特徴量を生成する、特徴量生成部と、
前記特徴量と前記特徴量の数を示す複雑さ要件とに応じて分割条件を生成する、分割条件生成部と、
前記学習データを前記分割条件に基づいてグループに分割する、学習データ分割部と、
分割前後のグループを用いて、前記分割条件ごとに有意性を評価する、学習データ評価部と、
分割前後のグループにおいて、前記分割条件に有意性がある場合、前記分割条件に関連する決定木のノードを生成する、ノード生成部と、
を有することを特徴とする学習装置。
【００８６】
（付記２）
付記１に記載の学習装置であって、
前記分割前後のグループにおいて、すべての前記分割条件に有意性がない場合、前記複雑さ要件が示す前記特徴量の数を増加させ、前記分割条件生成部に前記分割条件を追加させる、分割条件追加部と、
を有することを特徴とする学習装置。
【００８７】
（付記３）
付記１又は２に記載の学習装置であって、
前記分割条件生成部は、前記特徴量間の関係性を表す論理演算子を用いて、前記分割条件を生成する
ことを特徴とする学習装置。
【００８８】
（付記４）
付記３に記載の学習装置であって、
前記分割条件生成部は、前記複雑さ要件が示す、前記分割条件で使用する前記特徴量の数（Ｆ１、Ｆ２）が二つである場合、前記分割条件を、以下の条件を用いて生成する
Ｆ１  ａｎｄ  Ｆ２
ｎｏｔ  Ｆ１  ａｎｄ  Ｆ２
Ｆ１  ｏｒ  Ｆ２
Ｆ１  ａｎｄ  ｎｏｔ  Ｆ２
Ｆ１  ｘｏｒ  Ｆ２
ことを特徴とする学習装置。
【００８９】
（付記５）
（ａ）学習データに基づいて特徴量を生成する、ステップと、
（ｂ）前記特徴量と前記特徴量の数を示す複雑さ要件とに応じて分割条件を生成する、ステップと、
（ｃ）前記学習データを前記分割条件に基づいてグループに分割する、ステップと、
（ｄ）分割前後のグループを用いて、前記分割条件ごとに有意性を評価する、ステップと、
（ｅ）分割後のグループにおいて、前記分割条件に有意性がある場合、前記分割条件に関連する決定木のノードを生成する、ステップと、
を有することを特徴とする学習方法。
【００９０】
（付記６）
付記５に記載の学習方法であって、
（ｆ）前記分割前後のグループにおいて、すべての前記分割条件に有意性がない場合、前記複雑さ要件が示す前記特徴量の数を増加させ、前記分割条件を追加させる、ステップと、
を有することを特徴とする学習方法。
【００９１】
（付記７）
付記５又は６に記載の学習方法であって、
前記（ｂ）のステップにおいて、前記特徴量間の関係性を表す論理演算子を用いて、前記分割条件を生成する
ことを特徴とする学習方法。
【００９２】
（付記８）
付記７に記載の学習方法であって、
前記（ｂ）のステップにおいて、前記複雑さ要件が示す、前記分割条件で使用する前記特徴量（Ｆ１、Ｆ２）の数が二つである場合、前記分割条件を、以下の条件を用いて生成する
Ｆ１  ａｎｄ  Ｆ２
ｎｏｔ  Ｆ１  ａｎｄ  Ｆ２
Ｆ１  ｏｒ  Ｆ２
Ｆ１  ａｎｄ  ｎｏｔ  Ｆ２
Ｆ１  ｘｏｒ  Ｆ２
ことを特徴とする学習方法。
【００９３】
（付記９）
コンピュータに、
（ａ）学習データに基づいて特徴量を生成する、ステップと、
（ｂ）前記特徴量と前記特徴量の数を示す複雑さ要件とに応じて分割条件を生成する、ステップと、
（ｃ）前記学習データを前記分割条件に基づいてグループに分割する、ステップと、
（ｄ）分割前後のグループを用いて、前記分割条件ごとに有意性を評価する、ステップと、
（ｅ）分割前後のグループにおいて、前記分割条件に有意性がある場合、前記分割条件に関連する決定木のノードを生成する、ステップと、
を実行させるプログラム。
【００９４】
（付記１０）
付記９に記載のプログラムであって、
前記プログラムが、前記コンピュータは、
（ｆ）前記分割前後のグループにおいて、すべての前記分割条件に有意性がない場合、前記複雑さ要件が示す前記特徴量の数を増加させ、前記分割条件を追加させる、ステップを実行させるプログラム。
【００９５】
（付記１１）
付記９又は１０に記載のプログラムであって、
前記（ｂ）のステップにおいて、前記特徴量間の関係性を表す論理演算子を用いて、前記分割条件を生成する
ことを特徴とするプログラム。
【００９６】
（付記１２）
付記１１に記載のプログラムであって、
前記（ｂ）のステップにおいて、前記複雑さ要件が示す、前記分割条件で使用する前記特徴量（Ｆ１、Ｆ２）の数が二つである場合、前記分割条件を、以下の条件を用いて生成する
Ｆ１  ａｎｄ  Ｆ２
ｎｏｔ  Ｆ１  ａｎｄ  Ｆ２
Ｆ１  ｏｒ  Ｆ２
Ｆ１  ａｎｄ  ｎｏｔ  Ｆ２
Ｆ１  ｘｏｒ  Ｆ２
ことを特徴とするプログラム。
【００９７】
以上、実施の形態を参照して本願発明を説明したが、本願発明は上記実施の形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【００９８】
この出願は、２０１８年３月２９日に出願された日本出願特願２０１８−０６６０５７を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【００９９】
以上のように本発明によれば、決定木の予測精度を向上させることができる。本発明は、決定木の予測精度を向上させることが必要な分野において有用である。
【符号の説明】
【０１００】
１０  学習装置
１１  特徴量生成部
１２  分割条件生成部 
１３  学習データ分割部
１４  学習データ評価部
１５  ノード生成部
１６  分割条件追加部
２０  学習データ
３０  入力装置
４０  出力装置
５０  決定木データ
１１０  コンピュータ
１１１  ＣＰＵ
１１２  メインメモリ
１１３  記憶装置
１１４  入力インターフェイス
１１５  表示コントローラ
１１６  データリーダ／ライタ
１１７  通信インターフェイス
１１８  入力機器
１１９  ディスプレイ装置
１２０  記録媒体
１２１  バス
【図１】
0006888737.tif 000002
【図２】
0006888737.tif 000003
【図３】
0006888737.tif 000004
【図４】
0006888737.tif 000005
【図５】
0006888737.tif 000006
【図６】
0006888737.tif 000007
【図７】
0006888737.tif 000008
【図８】
0006888737.tif 000009
【図９】
0006888737.tif 000010
【図１０】
0006888737.tif 000011
【図１１】
0006888737.tif 000012