(57)【要約】  学習装置は、複数の属性と既知のクラスとを含む訓練サンプルを複数取得し、識別器として学習するための決定木のルートノードに与え、前記決定木の親ノードから複数の子ノードを生成し、複数の前記訓練サンプルのうち、前記決定木の親ノードにおいて、クラス分けをするための分岐条件に対応する前記属性が欠損値ではない前記訓練サンプルを、前記分岐条件に従って前記複数の子ノードのいずれかに振り分け、前記属性が前記欠損値である前記訓練サンプルを、前記複数の子ノードのいずれか一つの前記子ノードに渡し、終了条件を満たすまで前記子ノードの生成と前記訓練サンプルの振り分けを行う。
2010100701.tif 000002
【特許請求の範囲】
【請求項１】
複数の属性と既知のクラスとを含む訓練サンプルを複数取得し、識別器として学習するための決定木のルートノードに与える訓練サンプル取得部と、
前記決定木の親ノードから複数の子ノードを生成する生成部と、
複数の前記訓練サンプルのうち、前記決定木の親ノードにおいて、クラス分けをするための分岐条件に対応する前記属性が欠損値ではない前記訓練サンプルを、前記分岐条件に従って前記複数の子ノードのいずれかに振り分け、前記属性が前記欠損値である前記訓練サンプルを、前記複数の子ノードのいずれか一つの前記子ノードに渡す振り分け部と、
終了条件を満たすまで前記子ノードの生成と前記訓練サンプルの振り分けを行う終了判定部と、
を備えることを特徴とする学習装置。
【請求項２】
前記分岐条件として用いる前記属性が前記欠損値ではない前記訓練サンプルによって、前記分岐条件を決めるための評価値を計算し、前記分岐条件として用いる前記属性が前記欠損値でない前記訓練サンプルが、前記全ての訓練サンプルに対して占める割合が大きい程に前記評価値を上げるように補正して前記分岐条件を決定する決定部をさらに有する、
ことを特徴とする請求項１に記載の学習装置。
【請求項３】
前記振り分け部は、前記分岐条件として用いる前記属性が前記欠損値である前記訓練サンプルを必ず決まった方向の前記子ノードに渡す、
ことを特徴とする請求項２に記載の学習装置。
【請求項４】
前記振り分け部は、前記分岐条件として用いる前記属性が前記欠損値である前記訓練サンプルを渡した前記子ノードを前記親ノードに記憶させる、
ことを特徴とする請求項２に記載の学習装置。
【請求項５】
前記振り分け部は、前記分岐条件として用いる前記属性が前記欠損値である前記訓練サンプルが一つもない場合は、前記欠損値を扱わなかったことを示す欠損値有無情報を前記親ノードに記憶させる、
ことを特徴とする請求項２に記載の学習装置。
【請求項６】
複数の属性と未知のクラスとを含む未知サンプルを取得し、請求項１から請求項６のいずれか一項に記載の学習装置で学習した識別器である決定木のルートノードに与える未知サンプル取得部と、
前記未知サンプルを、前記決定木に対してリーフノードまで進めるものであって、親ノードにおける分岐条件として用いる属性が欠損値ではない前記未知サンプルを、前記分岐条件に従って複数の子ノードのいずれかに振り分け、前記分岐条件で用いる前記属性が前記欠損値である前記未知サンプルを、前記学習時に、前記属性が欠損値である前記訓練データが渡された前記子ノードに進める分岐部と、
前記リーフノードに至った前記未知サンプルのクラス分布により、前記未知サンプルのクラスを推定する推定部と、
を備えることを特徴とする識別装置。
【請求項７】
訓練サンプル取得部が、複数の属性と既知のクラスとを含む訓練サンプルを複数取得し、識別器として学習するための決定木のルートノードに与える訓練サンプル取得ステップと、
生成部が、前記決定木の親ノードから複数の子ノードを生成する生成ステップと、
振り分け部が、複数の前記訓練サンプルのうち、前記決定木の親ノードにおいて、クラス分けをするための分岐条件に対応する前記属性が欠損値ではない前記訓練サンプルを、前記分岐条件に従って前記複数の子ノードのいずれかに振り分け、前記属性が前記欠損値である前記訓練サンプルを、前記複数の子ノードのいずれか一つの前記子ノードに渡す振り分けステップと、
終了判定部が、終了条件を満たすまで前記子ノードの生成と前記訓練サンプルの振り分けを行う終了判定ステップと、
備えることを特徴とする学習方法。
【請求項８】
未知サンプル取得部が、複数の属性と未知のクラスとを含む未知サンプルを取得し、請求項８に記載の学習方法で学習した識別器である決定木のルートノードに与える未知サンプル取得ステップと、
分岐部が、前記未知サンプルを、前記決定木に対してリーフノードまで進めるものであって、親ノードにおける分岐条件として用いる属性が欠損値ではない前記未知サンプルを、前記分岐条件に従って複数の子ノードのいずれかに振り分け、前記分岐条件で用いる前記属性が前記欠損値である前記未知サンプルを、前記学習時に、前記属性が欠損値である前記訓練データが渡された前記子ノードに進める分岐ステップと、
推定部が、前記リーフノードに至った前記未知サンプルのクラス分布により、前記未知サンプルのクラスを推定する推定ステップと、
を備えることを特徴とする識別方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、決定木を識別器として学習する学習技術、及び、その識別器を用いた識別技術に関する。
【背景技術】
【０００２】
従来より、欠損値を持つ訓練サンプルを用いた識別器の学習方法及びその識別器を用いた識別方法がある。【０００３】
特許文献１は、欠損値を補完した上で識別器の学習と識別を行う技術を開示している。具体的には、特許文献１では、欠損値推定処理のために識別器の学習後は本来不要な訓練サンプル自体を保存しておき、欠損値推定処理を行うため訓練サンプルと未知サンプルの距離計算を行う。【０００４】
これに対し、特許文献２及び非特許文献１は、欠損値を補完しないで識別器の学習と識別を行う技術をそれぞれ開示している。特許文献２では、決定木の各ノードにおいて学習時に割り当てられた訓練サンプルから代表事例を作成し、この代表事例を各ノードにおいて保存し、識別時において欠損値を用いた分岐条件判定の際に、未知サンプルと代表事例との距離計算を行う。非特許文献１では、分岐条件を評価できなかった訓練サンプルを無視して現在のノードで捨ててしまう方法と、分岐条件を評価できなかった訓練サンプルを全ての子ノードに対してそれぞれ渡す方法とが開示されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００８−２３４３５２号公報
【特許文献２】特開平６−９６０４４号公報
【非特許文献】
【０００６】
【非特許文献１】J. R. Quinlan, "Unknown attribute values in induction", Proceedings of the 6ｔｈ International Workshop on Machine Learning, 1989.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、従来の欠損値を補完する方法では、補完精度が最終結果に重要な影響を及ぼすため、補完処理のための記憶領域と補完処理コストの大幅な増加が伴う。欠損値を補完しない方法であっても、記憶領域の増加や処理速度が重視される識別時の処理コストの増加が避けられない。
【課題を解決するための手段】
【０００８】
本発明の一態様に係る学習装置は、複数の属性と既知のクラスとを含む訓練サンプルを複数取得し、識別器として学習するための決定木のルートノードに与える訓練サンプル取得部と、前記決定木の親ノードから複数の子ノードを生成する生成部と、複数の前記訓練サンプルのうち、前記決定木の親ノードにおいて、クラス分けをするための分岐条件に対応する前記属性が欠損値ではない前記訓練サンプルを、前記分岐条件に従って前記複数の子ノードのいずれかに振り分け、前記属性が前記欠損値である前記訓練サンプルを、前記複数の子ノードのいずれか一つの前記子ノードに渡す振り分け部と、終了条件を満たすまで前記子ノードの生成と前記訓練サンプルの振り分けを行う終了判定部と、備える。【０００９】
また、本発明の一態様に係る識別装置は、複数の属性と未知のクラスとを含む未知サンプルを取得し、前記学習装置で学習した識別器である決定木のルートノードに与える未知サンプル取得部と、前記未知サンプルを、前記決定木に対してリーフノードまで進めるものであって、親ノードにおける分岐条件として用いる属性が欠損値ではない前記未知サンプルを、前記分岐条件に従って複数の子ノードのいずれかに振り分け、前記分岐条件で用いる前記属性が前記欠損値である前記未知サンプルを、前記学習時に、前記属性が欠損値である前記訓練データが渡された前記子ノードに進める分岐部と、前記リーフノードに至った前記未知サンプルのクラス分布により、前記未知サンプルのクラスを推定する推定部と、を備える。
【発明の効果】
【００１０】
欠損値を持つサンプルであっても、識別処理のコストと記憶領域の増加を抑えることができる。
【図面の簡単な説明】
【００１１】
【図１】本発明の実施例１の学習装置のブロック図。
【図２】実施例１の動作を示すフローチャート。
【図３】実施例１のノードにおける訓練サンプルの振り分けを示す説明図。
【図４】実施例１の決定木を示す説明図。
【図５】本発明の実施例２の学習装置のブロック図。
【図６】実施例２の動作を示すフローチャート。
【図７】本発明の実施例５の識別装置のブロック図。
【図８】実施例５の識別装置のフローチャート。
【図９】訓練サンプルの第２の具体例に関する説明図。
【図１０】訓練サンプルの第３の具体例に関する説明図。
【発明を実施するための形態】
【００１２】
本発明の実施例について説明する前に、本実施例の説明で使われる用語の定義を行う。
【００１３】
「サンプル」とは、分類を表す「クラス」と、複数の「属性」とを含む。例えば、男女を分類する問題であれば、クラスとは男女を識別するための値であり、属性とは収集した身長、体重、体脂肪率などの男女を識別するために用いる値である。
【００１４】
「訓練サンプル」とは、識別器を学習するために収集されたサンプルでありクラスは既知である。
【００１５】
「未知サンプル」とは、属性は得られているがクラスが未知のサンプルであり、識別処理では識別器を使って未知サンプルのクラスを推定する。
【００１６】
「欠損値」とは、属性の値が不明であることを示す。
【実施例１】
【００１７】
実施例１の学習装置１０について、図１〜図４を参照して説明する。本実施例の学習装置１０は、欠損値を含む訓練サンプルを用いた決定木に基づく識別器を学習する。【００１８】
図１は、本実施例の学習装置１０のブロック図である。【００１９】
図１に示すように学習装置１０は、例えば、訓練サンプル取得部１２、生成部１４、振り分け部１６、終了判定部１８、記憶制御部２０とを有する。訓練サンプルとしては、身長、体重、体脂肪率などの属性と男女のクラス付けされたサンプルを用いる場合を例に挙げる。【００２０】
学習装置１０で学習する識別器としては、単一の決定木を用いる。また、識別器としては、ランダムフォレスト（random forests；Leo Breiman, 「RandomForests」, Machine Learning, vol. 45, pp.5-32, 2001.参照）、又は、エクストリームリーランダマイズドツリーズ（extremely randomized trees；Pierre Geurts, Damien Ernst and Louis Wehenkel, 「Extremely randomized trees」, Machine Learning, vol. 36, number 1, pp.3-42, 2001.参照、以下、「Pierre Geurts」という）を用いるとさらに好適である。これらは決定木の学習時に、ランダム性を持たせることによって得られる複数の決定木を有する識別器を構成する。なお、これらの決定木は、単一の決定木による識別器よりも識別能力が高い。【００２１】
学習装置１０の動作状態について図２と図３を参照して説明する。【００２２】
図２は、学習装置１０が、識別器の学習を行う方法の動作を示すフローチャートである。【００２３】
図３は、現在のノードにおける訓練サンプルの振り分けを示す説明図である。【００２４】
ステップＳ１では、訓練サンプル取得部１２は、図３に示すように、複数の訓練サンプルを外部から取得し、ルートノードに与える。ルートノード以下の各ノードには、分岐条件が予め定められている。各訓練サンプルは｛ｘ１，ｘ２，・・・，ｘｎ｝のｎ個の属性を持ち、クラスｙは既知である。各訓練サンプルの各属性は連続値、又は、離散値を持つか、もしくは欠損値であることを示す値を持っている。なお、訓練サンプルは、訓練サンプル取得部１２に予め記憶していてもよい。【００２５】
ステップＳ２では、生成部１４は、前記ルートノードを含む親ノードに対して子ノードを２つ生成する。すなわち、図２に示すように、分岐条件がｘ２＞６１と定められたとき、欠損値の存在を無視すれば、分岐条件を満たすか満たさないかの２つの選択肢があるので、生成部１４は子ノードを２つ生成する。しかし、実際には親ノードに渡された訓練サンプルは大きく３つに分けられる。第１は分岐条件を満たす訓練サンプル、第２は分岐条件を満たさない訓練サンプル、第３は分岐条件として用いる属性ｘ２が欠損しているため分岐条件を判断できない訓練サンプルである。ここで、分岐条件は、クラス分けをするための条件であり、例えば、訓練サンプルのクラスの分離度合を用い、この分離度合いとしては、information gainなどの指標を用いる。このinformation gainは、Pierre Geurtsに記載されたinformation gainであり、本明細書では「評価値」という。そして、生成部１４は、複数の分岐条件を試行し、それらの中で評価値が最も良いものを分岐条件として定める。これによって分岐条件として用いる属性が決定される。【００２６】
ステップＳ３では、振り分け部１６は、分岐条件を満たす訓練サンプルと、分岐条件を満たさない訓練サンプルをそれぞれ対応する子ノードに振り分ける。【００２７】
ステップＳ４では、振り分け部１６は、分岐条件を評価できなかった訓練サンプルをどちらか一方の子ノードに渡す。なお、ステップＳ３とステップＳ４の処理の順番は逆でもよい。【００２８】
ステップＳ５では、終了判定部１８は、以下、再帰的に終了条件を満たすまでこの分割を繰り返す。終了条件としては、次の条件を採用する。第１の条件は、ノードに含まれる訓練サンプルの数が予め定めておいた数よりも小さいときである。第２の条件は、木構造の深さが予め定めておいた値よりも大きいときである。第３の条件は、分割の良さを表す指標の減少が予め定めておいた値よりも小さいときである。【００２９】
ステップＳ６では、記憶制御部２０が、上記のように学習した各ノードから構成される決定木を識別器として記憶部に記憶させる。【００３０】
上記学習装置１０の効果について説明する。【００３１】
本実施例の学習装置１０では、分岐条件によって評価できなかった訓練サンプルは、一つの子ノードに全て渡される。図４に示すように、親ノードにおいて訓練サンプルの振り分けが終わった後、訓練サンプルが渡された子ノードにおいて別の分岐条件により訓練サンプルの振り分けを行う。そのため、親ノードにおいて分岐条件を評価できなかった訓練サンプルも、渡された子ノード以降の部分木によって分類方法を学習することができる。なお、部分木は決定木全体と比べれば分岐条件による判断回数が少ないため、分類すべきクラスの種類が少ない方が好適である。例えば、男か女か、正解か非正解か、などの２クラスの識別問題であれば、小さな部分木でもリーフノードにおいてどちらの判断も下せる可能性が残るからである。【００３２】
また、本実施例の学習装置１０では、特許文献１に記載の欠損値を補完する方法や、特許文献２に記載の代表例で判断する方法など、分岐条件以外に識別に必要な情報を記憶しておく必要がないため、欠損値を考慮しない方法と同等の記憶領域で辞書を構成することができる。【００３３】
また、非特許文献１には、分岐条件を評価できなかった訓練サンプルを無視して現在のノードで捨ててしまう方法が開示されている。しかし、この学習方法では、識別時の性能が良くないということが同文献に示されている。【００３４】
また、非特許文献１には、分岐条件を評価できなかった訓練サンプルを全ての子ノードに対してそれぞれ渡す方法が開示されている。しかし、この学習方法では、子ノードに渡す訓練サンプル数が増加して決定木全体が大きくなる。そのため、決定木の記憶領域が大きくなり、識別処理にも時間がかかる。本実施例の学習装置１０では、子ノードに渡す訓練サンプル数が増加することがなく、また、すべての訓練サンプルを使って学習できるため、欠損値を考慮しない方法と同等の記憶領域で辞書を構成しながら、欠損値を考慮した学習を行うことができる。【００３５】
また、本実施例の学習装置１０は、ある属性が欠損値である訓練サンプルのクラス分布に大きな偏りがある場合には、より好適である。例えば、男女の識別問題で、体重を属性とした場合とする。このとき、回答が得られず体重という属性の値が欠損している訓練サンプルは女性のものがほとんどであるとすると、その属性が欠損していること自体が識別のために重要な情報となり得る。そのため、これら欠損値をもつ訓練サンプルを一つにまとめておくのは、分類の精度向上に寄与できる。【００３６】
このように、本実施例の学習装置１０によれば、分岐条件として用いる属性が欠損値である訓練サンプルを、分岐条件として用いる属性が欠損値でない訓練サンプルを渡す子ノードのいずれか一つに対して全て渡すことで、欠損値を考慮しない学習方法で生成される決定木と同様の構成で識別能力の高い決定木を学習することができる。【００３７】
上記実施例では、訓練サンプルとして、身長、体重、体脂肪率などの属性と男女のクラス付けされたサンプルを第１の具体例として用いたが、これ以外の、欠損値を含む訓練サンプルの第２の具体例について図９を参照して説明する。【００３８】
図９に示すように、画像１００の全体の一部を切り出す場合、切り出し画像１０２が画像１００の外にはみ出てしまうと、その画像外の部分１０４には情報がないため、値を得ることができない。よって、この画像外の部分１０４に対応する属性を欠損値とする。【００３９】
以下では、画像１００中から人間の顔を検出し、その位置と姿勢を推定するような顔検出を例として説明する。【００４０】
この顔検出では、画像１００の全体から一部を切り出し、切り出した画像１０２の画素の輝度値や、輝度値から計算される勾配などの特徴量｛ｘ１，ｘ２，・・・，ｘ２５｝を一列に並べて１次元ベクトル化することによって、この切り出し画像１０２に顔の有無を判断する。【００４１】
画像外の部分１０４を含むように切り出した画像１０２は、欠損値を含む属性の列となるため、これを学習する際には本実施例が有効となる。【００４２】
また、このような顔検出では、顔・非顔のサンプルを集めて２クラスの分類を行う識別器を学習することとなり、属性の数は切り出し画素数に応じて多くなる。したがって、第１の具体例は、属性の欠損値を扱う追加の記憶領域が少なく、部分木で欠損値を持つ訓練サンプルの学習を行う本実施例には好適な応用例である。【００４３】
なお、この第１の具体例の訓練サンプルを用いた場合には、後から説明する未知サンプルも同様の画像を用いる。【００４４】
欠損値を含む訓練サンプルの第３の具体例について図１０を参照して説明する。【００４５】
第３の具体例は、図１０に示すように、画像２００の全体の一部に無効な領域２０２を含む画像から一部を切り出す場合である。この切り出し部分画像２０４に無効な領域を含む場合、その無効部分から得られる属性を欠損値として扱う。【００４６】
超音波画像を例として説明する。【００４７】
矩形の画像２００全体は、超音波ビームの情報によって構成された扇型の部分２０６と、超音波ビームが走査されていない部分２０２とが存在する。画像２００全体から一部を切り出し、切り出した画像２０４の画素の輝度値や輝度値から計算される特徴量｛ｘ１，ｘ２，・・・，ｘｎ｝を一列に並べて１次元ベクトル化した属性とする。これは、欠損値を含む属性の列となるため、これを学習する際には本実施例が有効となる。【００４８】
なお、画像２００は２次元画像だけでなく、３次元画像を扱っても良い。医用分野において、ＣＴ、ＭＲＩ、超音波画像などのモダリティでは３次元のボリュームデータが得られる。特定部位や物体の位置・姿勢推定問題（例えば左心室中心を中心とし、心尖方向と右心室方向を特定する問題）は、正しい位置・姿勢で切り出されたサンプルを正解サンプルとし、間違った位置・姿勢で切り出されたサンプルを非正解サンプルとして２クラスの学習を行う。切り出しを３次元で行った場合は２次元画像に比べて属性数がさらに多くなる。したがって、第２の具体例は、属性の欠損値を扱う追加の記憶領域が少なく、部分木で欠損値を持つ訓練サンプルの学習を行う本実施例には好適な応用例である。【００４９】
なお、この第２の具体例の訓練サンプルを用いた場合には、後から説明する未知サンプルも同様の画像を用いる。
【実施例２】
【００５０】
実施例２の学習装置１０について図５と図６を参照して説明する。【００５１】
本実施例の学習装置１０は、実施例１で説明した欠損値をもつ訓練サンプルの振り分けだけでなく、それに加えて欠損値をもつ訓練サンプルを用いた分岐条件の補正も行う。【００５２】
図５は、実施例２の学習装置１０のブロック図である。【００５３】
図５に示すように、学習装置１０は、例えば、実施例１の訓練サンプル取得部１２、生成部１４、振り分け部１６、終了判定部１８、記憶制御部２０に加えて、決定部２２を有する。【００５４】
学習装置１０の動作状態について図６を参照して説明する。図６は、本実施例に係わる学習装置１０の動作を示すフローチャートである。【００５５】
ステップＳ１１では、訓練サンプル取得部１２は、複数の訓練サンプルを取得し、ルートノードに与える。【００５６】
ステップＳ１２では、決定部２２は、適当な属性に閾値を設定することにより定められる分岐条件の評価を行う。属性が欠損値である訓練サンプルを除き、残りの訓練サンプルを用いて設定した分岐条件により、訓練サンプルのクラスの分離度合として、実施例１における評価値を用いる。ここで、設定する分岐条件は、訓練サンプルをクラス毎に分離でき、かつ、分岐条件として用いる属性が欠損値である訓練サンプルが少ない方が良い。その理由は、より多くの訓練サンプルが正しく分類できる分岐条件を選択した方が、決定木全体をコンパクトにすることができ、記憶領域の削減、識別処理の削減が達成できるからである。【００５７】
ステップＳ１３では、決定部２２は、分岐条件で用いる属性が欠損値でない訓練サンプルが親ノードに割り当てられた訓練サンプル全体に占める割合が大きい程、評価値を上げるように補正する。具体的には、上記の割合で評価値を重み付けする方法などが考えられる。評価値をＨ、属性が欠損値でない訓練サンプルの数をａ、属性が欠損値である訓練サンプルの数をｂとすると、補正した評価値Ｈ’＝ａ／（ａ＋ｂ）＊Ｈとする。【００５８】
ステップＳ１４では、決定部２２は、複数の分岐条件を試行し、それらの中で上記の補正した評価値Ｈ’が最も良いものを分岐条件として定める。これによって分岐条件として用いる属性が決定される。【００５９】
ステップＳ１５では、生成部１４は、前記ルートノードを含む親ノードに対して、決定部２２で決定された分岐条件に基づいて、属性が欠損値でない訓練サンプルを渡す子ノードを２つ作成する。【００６０】
ステップＳ１６では、振り分け部１６は、欠損値でない訓練サンプルを子ノードに分岐条件に基づいて振り分ける。【００６１】
ステップＳ１７では、振り分け部１６は、分岐条件で用いる属性が欠損値である訓練サンプルをいずれか一つの子ノードに渡す。なお、ステップＳ１６とステップＳ１７の処理の順番は逆でもよい。【００６２】
ステップＳ１８では、終了判定部１８は、以下、再帰的に終了条件を満たすまでこの分割を繰り返す。終了条件は、実施例１のステップＳ５と同様である。【００６３】
ステップＳ１９では、記憶制御部２０が、上記のように学習した決定木の各ノードを識別器として記憶部に記憶させる。【００６４】
本実施例の学習装置１０の効果について説明する。【００６５】
分岐条件の選択において、できるだけ欠損値を持つ訓練サンプルの少ない属性で、かつ、クラスの分離度合が良い属性を選択することによって、決定木全体を小さくすることができ、記憶領域の削減、識別処理の削減ができる。【００６６】
一方、欠損値を持つ訓練サンプルの少ない属性が選択されることは、分岐条件で用いる属性が欠損値を持つ訓練サンプルの数を少なくすることを意味する。ここで、非特許文献１に記載されているような分岐条件を評価できなかった訓練サンプルを特別なノードに割り当てる方法をとる場合は、特別な子ノードにおいて、割り当てられた少数の訓練サンプルのみで以降の部分木を作る必要があり、学習が不安定となりやすい。そのため、同じ属性に欠損値を持つ未知サンプルに対する識別能力が損なわれる。しかし、本実施例の学習装置１０では、分岐条件で用いる属性が欠損値を持つ訓練サンプルが少数であっても、欠損値でない訓練サンプルと合わせて以降の学習を進めることができるため学習が安定する。【００６７】
このように本実施例に係わる学習装置１０によれば、クラス分離が良く、かつ、欠損値を持つサンプルが少ない属性を使った分岐条件を選択することにより、効果的な決定木を学習できる。【００６８】
また、本実施例に係わる学習装置１０によれば、分岐条件として用いる属性が欠損値を持つ訓練サンプルを少なくなくすることと、分岐条件として用いる属性が欠損値でない訓練サンプルと合わせて、子ノードでの学習を進めることにより、訓練サンプルが少数であることに起因する学習の不安定性を回避できる。
【実施例３】
【００６９】
実施例３の学習装置１０について説明する。【００７０】
本実施例の学習装置１０では、訓練サンプル取得部１２において、訓練サンプルの属性が欠損値であることを属性の値に記憶させる。【００７１】
属性において、欠損値ではない値の値域が既知の場合、値域より小さい値を欠損値であるとすれば、実施例１におけるステップＳ３とステップＳ４の処理を同時に行うことができる。【００７２】
例えば、属性ｘが０から１００までの値をとることがわかっている場合に、ｘがマイナスの値を持つ場合は欠損値であると定義しておく。これにより分岐条件がｘ＞５０とすると、ｘが欠損値である訓練サンプルはｘ＞５０を満たす訓練サンプルと同じ子ノードに渡される。全ての属性において値域より小さい値を欠損値としておけば、分岐条件で用いる属性が欠損値である訓練サンプルは、必ず決まった方向の子ノードに渡される。【００７３】
本実施例によれば、欠損値を考慮するための記憶領域を追加することなく、欠損値を考慮した決定木を学習できる。【００７４】
なお、属性の値域より大きな値を欠損値と定義した場合も上記と効果が得られる。
【実施例４】
【００７５】
実施例４の学習装置１０について説明する。【００７６】
本実施例の学習装置１０では、振り分け部１６において、分岐条件で用いる属性が欠損値である訓練サンプルを渡した子ノードを親ノードに記憶させる。この情報を記憶しておけば、ノード毎に欠損値である訓練サンプルを渡す子ノードの方向を制御できる。【００７７】
これにより得られる効果は次の通りである。【００７８】
ステップＳ３の後に、振り分け部１６が、子ノードに渡された訓練サンプルの数が少ない方の子ノードに対して、欠損値を持つ訓練サンプルを渡せば、特定の枝のみが成長することを防止でき、バランスのとれた決定木の学習ができる。【００７９】
また、振り分け部１６は、子ノードに渡された訓練サンプルのクラス分布と、欠損値を持つ訓練サンプルのクラス分布を比較し、クラス分布の近い方の子ノードに欠損値を持つ訓練サンプルを渡せば、以降の枝の成長を小さくできる。【００８０】
また、各ノードにおいて欠損値を持つ訓練サンプルが渡された子ノードの方向は、一つの値のみで記憶しておくことができるため、少しの記憶領域の増加で、欠損値を持つ訓練サンプルを考慮した決定木の学習ができる。
【実施例５】
【００８１】
実施例５では、実施例１の学習装置１０で学習された識別器を用いた識別装置２４について図７と図８を参照して説明する。【００８２】
図７は、本実施例の識別装置２４のブロック図である。【００８３】
識別装置２４は、未知サンプル取得部２６、分岐部２８、推定部３０とを有している。【００８４】
識別装置２４の動作について図８のフローチャートを参照して説明する。【００８５】
ステップＳ２１では、未知サンプル取得部２６は、クラス推定を行いたい未知サンプルを外部から取得し、実施例１の学習装置１０で学習された識別器である決定木のルートノードに与える。【００８６】
ステップＳ２２では、分岐部２８は、前記決定木に対して、未知サンプルを分岐条件に従ってルートノードから順にリーフノードまで進める。すなわち、親ノードにおける分岐条件として用いる属性が欠損値ではない未知サンプルを、分岐条件に従って複数の子ノードのいずれかに振り分ける。また、親ノードにおける分岐条件で用いる属性が未知サンプルにおいて欠損値であった場合、実施例１の学習装置１０における学習時に、この属性が欠損値であった訓練データが渡された子ノードに対して未知サンプルを進める。【００８７】
ステップＳ２３では、推定部３０は、決定木のリーフノードに至った未知サンプルのクラス分布により、未知サンプルのクラスを推定する。【００８８】
これにより、本実施例の識別装置２４であると、学習装置１０における学習時と同じ属性が欠損値であった訓練サンプルが進んだ方向に未知サンプルを進めるため、クラス推定を高い精度で行うことができる。【００８９】
実施例２の学習装置１０で学習された識別器を用いる場合も、上記と同様の識別装置２４を用いることにより、未知サンプルのクラス推定を行うことができる。
【実施例６】
【００９０】
実施例６では、実施例３の学習装置１０で学習された識別器を用いた識別装置２４について説明する。【００９１】
実施例３の学習装置１０で学習した場合は、識別装置２４の分岐部２８は、学習時と同様に未知サンプルの欠損値にも属性の値域より外の値を入れて処理を行うことにより、欠損値による分岐条件による振り分けの際に、自動的に欠損値を持った訓練サンプルが進んだ方向に未知サンプルを進めることができる。
【実施例７】
【００９２】
実施例７では、実施例４の学習装置１０で学習された識別器を用いた識別装置２４について説明する。【００９３】
実施例４の学習装置１０で学習した場合は、分岐部２８は、欠損値による分岐条件の振り分けの際に、指定された子ノードの方向に未知サンプルを進めることができる。
【実施例８】
【００９４】
実施例８の学習装置１０と識別装置２４について説明する。【００９５】
本実施例の学習装置１０の振り分け部１６では、決定木の学習において、分岐条件で用いる属性が欠損値である訓練サンプルが全くなかったことを表す欠損値有無情報を親ノードに記憶させる。【００９６】
これにより得られる効果は次の通りである。【００９７】
未知サンプルのクラス推定時には、各親ノードの分岐条件で未知サンプルを進める子ノードの方向を判断する。分岐条件に用いる属性が未知サンプルにおいて欠損値であった場合、この属性が欠損値であった訓練サンプルが渡された子ノードに進むべきである。しかし、この親ノードにおいて、学習時に欠損値を持つ訓練サンプルがなかったことを示す欠損値有無情報が存在した場合、その親ノードでは未知サンプルの分岐条件の振り分けが正しく行われない可能性が高い。【００９８】
そこで、本実施例の識別装置２４では、親ノードにおける分岐条件で用いる属性が未知サンプルにおいて欠損値であり、かつ、そのノードにおいて欠損値を持つ訓練サンプルが全くなかったことを欠損値有無情報からわかった場合には、次の処理を追加する。【００９９】
例えば、この追加の処理としては、未知サンプルを全ての子ノードにそれぞれ進め、至った全てのリーフノードにあるクラス分布を統合して、未知サンプルのクラスを推定する。未知サンプルは、どの子ノードに進めばよいかの指針がないので、全ての子ノードに進むことは、それより先の全ての部分木を使って識別処理を行えるため識別精度向上につながる。また、未知サンプルのラベル推定がうまくいかない可能性が高いことを知らせることもできる。
【変更例】
【０１００】
なお、本発明は上記実施例そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施例に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施例に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施例にわたる構成要素を適宜組み合わせてもよい。
【０１０１】
例えば、上記各実施例における学習装置の生成部１４では、１つの親ノードに対して、２つの子ノードを生成したが、これに限らず３つ以上の子ノードを生成してもよい。
【０１０２】
また、学習装置１０と識別装置２４は、例えば、汎用のコンピュータを基本ハードウェアとして用いることでも実現することが可能である。すなわち、学習装置１０及び識別装置２４の各部の構成は、上記のコンピュータに搭載されたプロセッサにプログラムを実行させることにより実現することができる。このとき、学習装置１０と識別装置２４の各部の機能は、上記のプログラムをコンピュータに予めインストールすることで実現してもよいし、ＣＤ−ＲＯＭなどの記憶媒体に記憶して、又はネットワークを介して上記のプログラムを配布して、このプログラムをコンピュータに適宜インストールすることで実現してもよい。
【符号の説明】
【０１０３】
１０・・・学習装置、１２・・・訓練サンプル取得部、１４・・・生成部、１６・・・振り分け部、１８・・・終了判定部、２０・・・記憶制御部、２２・・・決定部、２４・・・識別装置、２６・・・未知サンプル取得部、２８・・・分岐部、３０・・・推定部
【図１】
2010100701.tif 000003
【図２】
2010100701.tif 000004
【図３】
2010100701.tif 000005
【図４】
2010100701.tif 000006
【図５】
2010100701.tif 000007
【図６】
2010100701.tif 000008
【図７】
2010100701.tif 000009
【図８】
2010100701.tif 000010
【図９】
2010100701.tif 000011
【図１０】
2010100701.tif 000012
【手続補正書】
【提出日】平成22年5月17日(2010.5.17)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数の属性と既知のクラスとを含む訓練サンプルによって識別器として学習された決定木を用いる識別装置であって、
複数の属性と未知のクラスとを含む未知サンプルを取得し、決定木のルートノードに与える未知サンプル取得部と、
前記未知サンプルを、前記決定木に対してリーフノードまで進めるものであって、親ノードにおける分岐条件で用いる前記未知サンプルの属性が欠損値ではない場合には、前記分岐条件に従って複数の子ノードのいずれかに振り分け、前記分岐条件で用いる前記属性が前記欠損値である場合には前記未知サンプルを、前記親ノード毎に予め定められた前記子ノードに進める分岐部と、
前記リーフノードに至った前記未知サンプルのクラス分布により、前記未知サンプルのクラスを推定する推定部と、
を備えることを特徴とする識別装置。
【請求項２】
前記分岐部は、前記分岐条件として用いる前記属性が前記欠損値である前記訓練サンプルを学習時に扱わなかったことを示す欠損値有無情報を前記親ノードが記憶していることを特徴とする請求項１記載の識別装置。
【請求項３】
前記分岐部は、前記欠損有無情報が記憶されている前記親ノードにおいて、前記分岐条件として用いる前記未知サンプルの前記属性が前記欠損値である場合には、全ての前記子ノードに進めることを特徴とする請求項２記載の識別装置。
【請求項４】
前記分岐部は、前記欠損有無情報が記憶されている前記親ノードにおいて、前記分岐条件として用いる前記未知サンプルの前記属性が前記欠損値である場合には、前記未知サンプルのクラス推定の精度が低いことを通知することを特徴とする請求項２記載の識別装置。
【請求項５】
複数の属性と既知のクラスとを含む訓練サンプルを複数取得し、請求項１の識別装置に用いられる決定木のルートノードに与える訓練サンプル取得部と、
前記決定木の親ノードから複数の子ノードを生成する生成部と、
複数の前記訓練サンプルのうち、前記決定木の親ノードにおいて、クラス分けをするための分岐条件に対応する前記属性が欠損値ではない前記訓練サンプルを、前記分岐条件に従って前記複数の子ノードのいずれかに振り分け、前記属性が前記欠損値である前記訓練サンプルを、前記複数の子ノードのいずれか一つの前記子ノードに渡すと共に、前記属性が前記欠損値である前記訓練サンプルが渡された前記子ノードを前記親ノードに記憶させる振り分け部と、
終了条件を満たすまで前記子ノードの生成と前記訓練サンプルの振り分けを行う終了判定部と、
を備えることを特徴とする学習装置。
【請求項６】
前記分岐条件として用いる前記属性が前記欠損値ではない前記訓練サンプルによって、前記分岐条件を決めるための評価値を計算し、前記分岐条件として用いる前記属性が前記欠損値でない前記訓練サンプルが、前記全ての訓練サンプルに対して占める割合が大きい程に前記評価値を上げるように補正して前記分岐条件を決定する決定部をさらに有する、
ことを特徴とする請求項５記載の学習装置。
【請求項７】
（削除）
【請求項８】
複数の属性と既知のクラスとを含む訓練サンプルによって学習された決定木を用いる識別方法であって、
複数の属性と未知のクラスとを含む未知サンプルを取得し、決定木のルートノードに与える未知サンプル取得ステップと、
前記未知サンプルを、前記決定木に対してリーフノードまで進めるものであって、親ノードにおける分岐条件で用いる前記未知サンプルの属性が欠損値ではない場合には、前記分岐条件に従って複数の子ノードのいずれかに振り分け、前記分岐条件で用いる前記属性が前記欠損値である場合には前記未知サンプルを、前記親ノード毎に予め定められた前記子ノードに進める分岐ステップと、
前記リーフノードに至った前記未知サンプルのクラス分布により、前記未知サンプルのクラスを推定する推定ステップと、
を備えることを特徴とする識別方法。
【国際調査報告】
2010100701.tif 000013
2010100701.tif 000014
2010100701.tif 000015
2010100701.tif 000016
2010100701.tif 000017