(57)【要約】  分類木生成装置１０は、分類条件をそれぞれ表す１つ以上のノードで構成された木構造で表現される予測モデルである分類木に追加される新たな分類条件を複数の分類条件の候補から選択する分類木生成装置であって、分類条件の候補に関する情報利得を計算する第１計算部１１と、分類条件の候補と分類木に含まれている各分類条件との差分のうちの最小の差分の度合いを表す値を分類条件の候補に関するコストとして計算する第２計算部１２と、複数の分類条件の候補のうち計算された情報利得から計算されたコストが減算された値が最大である分類条件の候補を新たな分類条件に選択する選択部１３とを備える。
2019138584.tif 000002
【特許請求の範囲】
【請求項１】
分類条件をそれぞれ表す１つ以上のノードで構成された木構造で表現される予測モデルである分類木に追加される新たな分類条件を複数の分類条件の候補から選択する分類木生成装置で実行される分類木生成方法であって、
分類条件の候補に関する情報利得を計算し、
分類条件の候補と前記分類木に含まれている各分類条件との差分のうちの最小の差分の度合いを表す値を分類条件の候補に関するコストとして計算し、
前記複数の分類条件の候補のうち計算された情報利得から計算されたコストが減算された値が最大である分類条件の候補を前記新たな分類条件に選択する
ことを特徴とする分類木生成方法。
【請求項２】
分類木に含まれている分類条件と同一の分類条件の候補に関するコストを０と計算する
請求項１記載の分類木生成方法。
【請求項３】
分類条件の候補の内容に応じて前記分類条件の候補に関するコストを計算する
請求項１または請求項２記載の分類木生成方法。
【請求項４】
分類木を用いて予測処理を実行するシステムを表す論理回路を生成し、
生成された論理回路に含まれるAND 回路に応じて分類条件の候補に関するコストを計算する
請求項１から請求項３のうちのいずれか１項に記載の分類木生成方法。
【請求項５】
分類木の深さまたは前記分類木に含まれている分類条件の数に応じて計算された情報利得から減算される計算されたコストの重みを変更する
請求項１から請求項４のうちのいずれか１項に記載の分類木生成方法。
【請求項６】
分類木を用いて予測処理を実行するシステムの演算処理能力に応じて計算された情報利得から減算される計算されたコストの重みを変更する
請求項１から請求項５のうちのいずれか１項に記載の分類木生成方法。
【請求項７】
最小の差分の度合いが所定の閾値以下である分類条件の候補と分類木に含まれている分類条件とを前記分類条件の候補と前記分類条件とを基に生成された新たな条件にいずれも変更する
請求項１から請求項６のうちのいずれか１項に記載の分類木生成方法。
【請求項８】
複数の分類条件の候補を基に生成される可能性がある分類条件の候補をそれぞれ表す複数のノードで構成された木構造で表現される予測モデルである分類木の候補を全て生成し、
生成された分類木の候補に含まれている分類条件の候補に関する情報利得の総和を生成された分類木の候補を構成する全ノードに渡って計算し、
生成された分類木の候補が用いられた予測処理における分類条件の候補を入力とする計算処理のコストに応じた値である分類条件の候補に関するコストの総和を生成された分類木の候補を構成する全ノードに渡って計算し、
複数の分類木の候補のうち計算された情報利得の総和から計算されたコストの総和が減算された値が最大である分類木の候補を選択する
ことを特徴とする分類木生成方法。
【請求項９】
分類条件をそれぞれ表す１つ以上のノードで構成された木構造で表現される予測モデルである分類木に追加される新たな分類条件を複数の分類条件の候補から選択する分類木生成装置であって、
分類条件の候補に関する情報利得を計算する第１計算部と、
分類条件の候補と前記分類木に含まれている各分類条件との差分のうちの最小の差分の度合いを表す値を分類条件の候補に関するコストとして計算する第２計算部と、
前記複数の分類条件の候補のうち計算された情報利得から計算されたコストが減算された値が最大である分類条件の候補を前記新たな分類条件に選択する選択部とを備える
ことを特徴とする分類木生成装置。
【請求項１０】
複数の分類条件の候補を基に生成される可能性がある分類条件の候補をそれぞれ表す複数のノードで構成された木構造で表現される予測モデルである分類木の候補を全て生成する生成部と、
生成された分類木の候補に含まれている分類条件の候補に関する情報利得の総和を生成された分類木の候補を構成する全ノードに渡って計算する第１計算部と、
生成された分類木の候補が用いられた予測処理における分類条件の候補を入力とする計算処理のコストに応じた値である分類条件の候補に関するコストの総和を生成された分類木の候補を構成する全ノードに渡って計算する第２計算部と、
複数の分類木の候補のうち計算された情報利得の総和から計算されたコストの総和が減算された値が最大である分類木の候補を選択する選択部とを備える
ことを特徴とする分類木生成装置。
【請求項１１】
コンピュータに、
分類条件をそれぞれ表す１つ以上のノードで構成された木構造で表現される予測モデルである分類木に追加される新たな分類条件が複数の分類条件の候補から選択される際に分類条件の候補に関する情報利得を計算する第１計算処理、
分類条件の候補と前記分類木に含まれている各分類条件との差分のうちの最小の差分の度合いを表す値を分類条件の候補に関するコストとして計算する第２計算処理、および
前記複数の分類条件の候補のうち計算された情報利得から計算されたコストが減算された値が最大である分類条件の候補を前記新たな分類条件に選択する選択処理
を実行させるための分類木生成プログラム。
【請求項１２】
コンピュータに、
複数の分類条件の候補を基に生成される可能性がある分類条件の候補をそれぞれ表す複数のノードで構成された木構造で表現される予測モデルである分類木の候補を全て生成する生成処理、
生成された分類木の候補に含まれている分類条件の候補に関する情報利得の総和を生成された分類木の候補を構成する全ノードに渡って計算する第１計算処理、
生成された分類木の候補が用いられた予測処理における分類条件の候補を入力とする計算処理のコストに応じた値である分類条件の候補に関するコストの総和を生成された分類木の候補を構成する全ノードに渡って計算する第２計算処理、および
複数の分類木の候補のうち計算された情報利得の総和から計算されたコストの総和が減算された値が最大である分類木の候補を選択する選択処理
を実行させるための分類木生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分類木生成方法、分類木生成装置および分類木生成プログラムに関する。
【背景技術】
【０００２】
分類木（決定木）は、任意の事項に対する観察結果から、任意の事項の目標値に関する結論を導く予測モデルである（例えば、非特許文献１参照）。分類木を生成する既存手法として、例えば非特許文献２に記載されているID3(Iterative Dichotomiser 3) や、非特許文献３に記載されているC4.5がある。また、特許文献１には、決定木を用いてデータをカテゴリに分類する際、分類精度だけでなく計算コストも考慮して決定木を生成するデータ分類装置が記載されている。【０００３】
分類木を生成する既存手法のアルゴリズムを、図１３を参照して説明する。図１３は、分類木の生成対象の変数を示す説明図である。図１３（ａ）に示すグラフの縦軸は、属性Ａ（年齢）を表す。また、図１３（ａ）に示すグラフの横軸は、属性Ｂ（性別）を表す。属性Ａ（年齢）と属性Ｂ（性別）が、本例で生成される分類木の説明変数である。【０００４】
また、図１３（ａ）に示すグラフには、「Ｘ」と「Ｙ」が記載されている。「Ｘ」は商品Ｘを表し、「Ｙ」は商品Ｙを表す。商品Ｘと商品Ｙが、本例で生成される分類木の目的変数である。【０００５】
分類木を生成する処理は、図１３（ａ）に示すグラフ上のエリアを分割する処理に相当する。図１３（ｂ）に示すように、グラフ上のエリアで複数回分割が行われている。具体的には、エリアが上下に分割される１回目の分割が行われた後、上のエリアと下のエリアがそれぞれ左右に分割される２回目の分割が行われている。【０００６】
図１３（ｂ）に示す分割処理は、例えば図１４に示す分類木生成装置が行う。図１４は、一般的な分類木生成装置の構成例を示すブロック図である。【０００７】
図１４に示す分類木生成装置９００は、分類木学習用データ保存部９１０と、Score 計算部９２０と、分割点決定部９３０と、分割実行部９４０と、分割点保存部９５０とを備える。また、Score 計算部９２０は、InfoGain計算部９２１を含む。【０００８】
分類木生成装置９００は、図１３（ｂ）に示す分割処理を図１５に示すフローチャートに従って行う。図１５は、分類木生成装置９００による分類木生成処理の動作を示すフローチャートである。【０００９】
図１５に示す分割処理の入力は、分割対象のエリアである。最初に、Score 計算部９２０は、分類木学習用データ保存部９１０に記憶されている分割対象のエリアにおける説明変数に関する分割点の候補を分割候補として列挙する。Score 計算部９２０は、列挙された全ての説明変数の全ての分割候補を「全分割候補」に入力する（ステップS001）。【００１０】
全分割候補が０である場合（ステップS002におけるTrue）、分類木生成装置９００は、他の分割対象のエリアに対して分割処理を行う（ステップS009）。全分割候補が０でない場合（ステップS002におけるFalse ）、Score 計算部９２０は、全分割候補から未だScore が計算されていない分割候補を１つ取り出す。すなわち、分割候補ループに入る（ステップS003）。【００１１】
取り出された分割候補に関して、Score 計算部９２０のInfoGain計算部９２１は、Score としてInformationGain （情報利得）を計算する（ステップS004）。InformationGain は、取り出された分割候補で分割対象のエリアが分割された場合のInformationGain である。InfoGain計算部９２１は、計算されたScore を分割点決定部９３０に入力する。【００１２】
次いで、分割点決定部９３０は、入力されたScore が分割処理内で計算されたScore の中で最大であるか否かを判定する（ステップS005）。最大でない場合（ステップS005におけるNo）、ステップS007の処理が行われる。【００１３】
最大である場合（ステップS005におけるYes ）、分割点決定部９３０は、分割対象のエリアにおける分割点をステップS003で取り出された分割候補に更新する（ステップS006）。次いで、分割点決定部９３０は、更新された分割候補を分割点保存部９５０に保存する。【００１４】
全分割候補の中でScore が計算されていない分割候補が存在する間、ステップS004〜ステップS006の処理が繰り返し行われる。全分割候補の中の分割候補のScore が全て計算されたとき、分類木生成装置９００は、分割候補ループを抜ける（ステップS007）。【００１５】
次いで、分割実行部９４０は、分割点保存部９５０に保存されている分割点で分割対象のエリアを分割する（ステップS008）。【００１６】
次いで、分類木生成装置９００は、ステップS008で新たに生成された分割対象エリアを入力として分割処理を実行する（ステップS009）。例えば、ステップS008で新たに第１分割後エリアと第２分割後エリアとが生成された場合、分類木生成装置９００は、２つの分割後エリアに対して再帰的に分割処理を実行する。すなわち、分割処理（第１分割後エリア）と分割処理（第２分割後エリア）とが実行される。【００１７】
上記のように、分類木生成装置９００は、分割処理を分割対象の全エリアに対して実行する。再帰的に分割処理が呼び出されることによって、全エリアが徐々に分割される。エリア内に分割点の候補が無くなった時、分割処理が終了する。【００１８】
次に、InformationGain の計算方法を説明する。InformationGain は、以下のように計算される値である。【００１９】
InformationGain ＝
（分割される前のエリアの平均情報量）−（分割された後のエリアの平均情報量）【００２０】
非特許文献４に記載されているID3 でのInformationGain の計算アルゴリズムを以下に示す。なお、入力の独立変数をa1，・・・，anとおく。また、取り得る出力は集合D に格納されており、例題の集合C においてx ∈D が起こる割合をpx(C) で表す。【００２１】
例題集合C に対する平均情報量M(C)は、以下のように計算される。【００２２】
【数１】
2019138584.tif 000003
【００２３】
次いで、例題集合C を、独立変数aiの値に応じて分割する。aiがv1，・・・，vmのm 通りの値を持つ場合、以下のように分割する。【００２４】
Cij ⊂ C(ai = vj)【００２５】
分割されたCij に応じた平均情報量M(Cij)は、以下のように計算される。【００２６】
【数２】
2019138584.tif 000004
【００２７】
計算された平均情報量を基に、独立変数aiの平均情報量の期待値Miは、以下のように計算される。【００２８】
【数３】
2019138584.tif 000005
【００２９】
式（３）で計算されるMiが、InformationGain に相当する値である。以下、図１５に示す分割処理と、上記の計算アルゴリズムに従って分割対象のエリアを分割する例を説明する。図１６は、分類木生成装置９００による分割処理の例を示す説明図である。【００３０】
図１６（ａ）は、分割対象のエリアを示す。図１６（ａ）に示す分割対象のエリアに対して、Score 計算部９２０は、分割候補を列挙する（ステップS001）。図１６（ｂ）に示す第１候補〜第４候補が、列挙された全ての分割候補である。【００３１】
次いで、InfoGain計算部９２１は、各分割候補のScore としてInfomationGain を計算する（ステップS004）。例えば、InfoGain計算部９２１は、第１候補に関して以下のようにInfomationGain を計算する。【００３２】
分割される前のエリアには、x が７つ、y が５つの、合計で１２個の要素が存在する。第１候補で分割された後の左のエリアには、x が４つ、y が４つの、合計で８個の要素が存在する。また、第１候補で分割された後の右のエリアには、x が３つ、y が１つの、合計で４個の要素が存在する。【００３３】
上記の状況のエリアに対して、InfoGain計算部９２１は、第１候補に関するInfomationGain を計算する。まず、InfoGain計算部９２１は、分割される前のエリアの平均情報量を、式（１）に従って以下のように計算する。【００３４】
（分割される前のエリアの平均情報量）
＝ -1 × ( 7/12 × log(7/12) + 5/12 × log(5/12)) ≒ 0.29497【００３５】
次に、InfoGain計算部９２１は、分割された後の左のエリアの平均情報量と分割された後の右のエリアの平均情報量を、式（１）に従ってそれぞれ以下のように計算する。【００３６】
（分割された後の左のエリアの平均情報量）
= -1 × ( 4/8 × log(4/8) + 4/8 × log(4/8)) ≒ 0.30103
（分割された後の右のエリアの平均情報量）
= -1 × ( 3/4 × log(3/4) + 1/4 × log(1/4)) ≒ 0.244219【００３７】
以上の計算結果を基に、InfoGain計算部９２１は、第１候補のScore を、式（３）に従って以下のように計算する。【００３８】
Score = InformationGain
= （分割される前のエリアの平均情報量）?（分割された後のエリアの平均情報量）
= （分割される前のエリアの平均情報量）?
（ 8/12 × （分割された後の左のエリアの平均情報量）＋
4/12 × （分割された後の右のエリアの平均情報量）
= 0.29497 - 0.282093 = 0.012877【００３９】
InfoGain計算部９２１は、上記のように各分割候補のScore をそれぞれ計算する。計算された各分割候補のScore は、第１候補が0.012877、第２候補が0.003 、第３候補が0.002 、第４候補が0.003 である。よって、Score が最大の分割候補が第１候補であるため、分割点決定部９３０は、分割点を第１候補に決定する。【００４０】
分割点が第１候補に決定されたため、分割実行部９４０は、図１６に示す分割対象のエリアを第１候補で分割する（ステップS008）。第１候補で分割された分割対象のエリアを図１７に示す。図１７は、分類木生成装置９００による分割処理の他の例を示す説明図である。【００４１】
図１７に示すように、分割対象のエリアは、それぞれ破線で囲まれた左のエリアと右のエリアに分割される。次に、分類木生成装置９００は、左のエリアに対して再帰的に分割処理を実行する（ステップS009）。また、分類木生成装置９００は、右のエリアに対しても再帰的に分割処理を実行する（ステップS009）。【００４２】
図１８は、分類木生成装置９００による分割処理の他の例を示す説明図である。図１８に示すように、右のエリアにおける分割候補は、第５候補のみである。よって、分割実行部９４０は、図１８に示す破線で囲まれた分割対象のエリアを第５候補で分割する（ステップS008）。第５候補で分割された後の２つのエリアには分割候補が存在しないので、右のエリアにおける分割処理は終了する。【００４３】
図１９は、分類木生成装置９００による分割処理の他の例を示す説明図である。図１９に示すように、左のエリアにおける分割候補は、第６候補と、第７候補と、第８候補である。上記の方法で計算された各分割候補のScore は、第６候補が0.0 、第７候補が0.014 、第８候補が0.014 である。よって、Score が最大の分割候補は、第７候補と第８候補である。【００４４】
Score が最大の分割候補が複数存在する場合、分割点になる分割候補は、ランダムに選択されたり、上から順に選択されたりする。本例では、分割点決定部９３０は、横軸に最も近い候補である第８候補を分割点に決定する。よって、分割実行部９４０は、図１９に示す破線で囲まれた分割対象のエリアを第８候補で分割する（ステップS008）。【００４５】
図２０は、分類木生成装置９００による分割処理の他の例を示す説明図である。図２０に示す分割対象のエリアは、破線で分割されている。なお、図２０に示す状態のエリアに対して更に分割処理が実行される場合もあるが、本例では図２０に示す状態で分割処理が終了する。【００４６】
図２１は、分類木の例を示す説明図である。図２１に示す分類木は、図２０に示す分割対象のエリアを基に生成された分類木である。図２１に示す分類木は、深さが２の木である。また、図２１に示す分類木の葉ノード以外のノードは、分割処理で保存された分割点に対応する分類条件を表す。【００４７】
分類木を構成する分類条件は、分割処理で保存された分割点を基に生成される。例えば、「A=1 」の分割点に対して、「A>1 」の分類条件が生成される。【００４８】
また、図２１に示す分類木の葉ノードは、購買される商品の傾向を表す。例えば、「B>2, A>2」の場合、図２０に示すエリアに存在する要素は全てx であるため、葉ノードは「商品Ｘを買う傾向」を表す。また、「B>2, A≦2 」の場合、図２０に示すエリアに存在する要素は１つのx と１つのy であるため、葉ノードは、購買される商品の傾向として「わからない」を表す。【００４９】
また、「 B≦2, A>1」の場合、図２０に示すエリアにはy の方が多く存在するため、葉ノードは、「商品Ｙを買う傾向」を表す。また、「 B≦2, A≦1 」の場合、図２０に示すエリアにはx の方が多く存在するため、葉ノードは、「商品Ｘを買う傾向」を表す。【００５０】
以上のように説明した分類木は、例えば秘密計算技術で使用される。秘密計算を実現する手段には、非特許文献５に記載されているBen-Orらの秘密分散を使う方法や、非特許文献６に記載されているElGamal 暗号等の準同型暗号を用いる方法や、非特許文献７に記載されているGentryによって提案された完全準同型暗号を用いる方法等がある。【００５１】
本明細書における秘密計算を実現する手段は、Ben-Orらの秘密分散を利用したマルチパーティ計算(Multi-Party Computation:MPC) 方式である。図２２は、秘密計算技術の例を示す説明図である。図２２は、MPC 方式が採用されたシステムを示す。【００５２】
秘密分散型のマルチパーティ計算技術が使用されると、複数のサーバが、秘匿されたデータを分散して保持し、秘匿された状態のデータに対して任意の計算を実行できる。OR回路やAND 回路等の論理回路の集合として表現される任意の計算は、MPC 方式が採用されたシステムにおいて理論的には実行可能である。【００５３】
例えば図２２に示すように、機密データＡが複数のサーバに分散されて保持される。具体的には、機密データＡは、「Ａ＝Ｘ＋Ｙ＋Ｚ」を満たすＸ、Ｙ、Ｚ（Ｘ、Ｙは乱数）に秘密分散されて保持される。【００５４】
管理者ａ、管理者ｂ、管理者ｃは、元の機密データＡを一切知ることなく、サーバ間で協調して計算を行う、すなわちマルチパーティ計算を行う。マルチパーティ計算の結果、管理者ａ、管理者ｂ、管理者ｃは、それぞれＵ、Ｖ、Ｗを得る。【００５５】
次いで、分析者は、Ｕ、Ｖ、Ｗを基に計算結果を復元する。具体的には、分析者は、「Ｒ＝Ｕ＋Ｖ＋Ｗ」を満たす、秘密分散されたデータに対する計算結果Ｒを得る。【００５６】
図２２に示すシステムに対して、ハッカーは、１つのサーバをハッキングしてもランダムな分散データしか得ることができない。すなわち、サイバー攻撃によるデータ漏洩が防止されるため、システムのセキュリティが向上する。サーバ間でデータを流通させる等の管理者同士の結託が行われない限りデータの漏洩は発生しないため、分析者は、安全にデータを処理できる。【００５７】
図２３は、秘密計算技術の他の例を示す説明図である。図２３は、MPC 方式が採用されたシステムにおいて、秘密計算技術が用いられて複数の組織間でデータが結合され、分析される例を示す。【００５８】
図２３に示すように、組織Ａの機密データＡ、および組織Ｂの機密データＢが、それぞれ秘密分散される。具体的には、機密データＡは、ＸＡ、ＹＡ、ＺＡに秘密分散される。また、機密データＢは、ＸＢ、ＹＢ、ＺＢに秘密分散される。【００５９】
各サーバの管理者は、機密データを開示することなく、分析処理を実行する。分析処理が実行されることによって、ＸＡとＸＢからＵ、ＹＡとＹＢからＶ、ＺＡとＺＢからＷという分析結果がそれぞれ得られる。最後に、分析者は、Ｕ、Ｖ、Ｗを基に分析結果Ｒを復元する。【００６０】
すなわち、図２３に示すように、秘密計算技術が用いられて異なる組織の各データが秘密分散されたまま処理されることによって、組織外に元データや計算途中の内容が一切開示されることなく、結合データの分析結果が得られる。結合データが分析されると、単体のデータからは得られなかった新たな知見が獲得される可能性がある。【００６１】
特許文献２には、上述した秘密計算技術が使用されたシステムの例が記載されている。【００６２】
また、特許文献３には、複層サーバシステム等の複雑なネットワークシステムにおいて、性能異常の発生パターンを解析して明確にすることによって、性能異常の早期原因特定や早期異常解消を支援する性能異常分析装置が記載されている。【００６３】
また、特許文献４には、多次元データに内在する点同士の距離以外の傾向も適正に反映して、多次元データを複数のクラスタに分割できるデータ分割装置が記載されている。【００６４】
また、特許文献５には、質問の難易度または容易度を考慮して質問を配置した検索決定木の生成を可能にする検索決定木生成方法が記載されている。
【先行技術文献】
【特許文献】
【００６５】
【特許文献１】特開２０１１−０２８５１９号公報
【特許文献２】国際公開第２０１７／１２６４３４号
【特許文献３】国際公開第２００７／０５２３２７号
【特許文献４】特開２００６−３３０９８８号公報
【特許文献５】特開２００４−３４１９２８号公報
【非特許文献】
【００６６】
【非特許文献１】" 決定木" 、[online]、ウィキペディア、[ 平成29年12月07日検索] 、インターネット<https://ja.wikipedia.org/wiki/%E6%B1%BA%E5%AE%9A%E6%9C%A8>
【非特許文献２】Quinlan J. Ross, "Induction of decision trees," Machine learning 1.1, 1986, pages 81-106.
【非特許文献３】"C4.5"、[online]、ウィキペディア、[ 平成29年12月07日検索] 、インターネット<https://ja.wikipedia.org/wiki/C4.5>
【非特許文献４】"ID3" 、[online]、ウィキペディア、[ 平成29年12月07日検索] 、インターネット<https://ja.wikipedia.org/wiki/ID3>
【非特許文献５】M. Ben-Or, S. Goldwasser, and A. Wigderson, "Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract)," 20th Symposium on Theory of Computing (STOC), ACM, 1988, pages 1-10.
【非特許文献６】T. E. Gamal, "A public key cryptosystem and a signature scheme based on discrete logarithms," IEEE Transactions on Information Theory, 1985, 31(4), pages 469-472.
【非特許文献７】C. Gentry, "Fully homomorphic encryption using ideal lattices," In M. Mitzenmacher ed., Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, ACM, 2009, pages 169-178.
【発明の概要】
【発明が解決しようとする課題】
【００６７】
図２４は、MPC 方式が採用されたシステムでの分類木が用いられた予測処理の例を示す説明図である。図２４（ａ）に示す分類木は、図２１に示す分類木である。分類木が用いられた予測処理が実行される場合、例えば、MPC 方式が採用されたシステムに、事業者Ａが図２４（ａ）に示す分類木を入力する。【００６８】
また、事業者Ｂが、分類木の各分類条件の評価に使用される個人情報を入力する。図２４（ａ）に示す例では、事業者Ｂは、予測対象である個人の属性Ａの値、および属性Ｂの値をMPC 方式が採用されたシステムに入力する。例えば、事業者Ｂが「B=1,A=3 」を入力する。【００６９】
図２４（ｂ）は、MPC 方式が採用されたシステムによる予測処理を示す。図２４（ｂ）に示す二重線の矢印が、MPC 方式が採用されたシステムが各分類条件を評価した結果を表す。【００７０】
図２４（ｂ）に示すように、MPC 方式が採用されたシステムは、「B>2 」、「A>1 」、「A>2 」の、分類木の全ての分類条件を評価する。本例では、MPC 方式が採用されたシステムは、「B>2 がfalse 」、「A>1 がtrue」、「A>2 がtrue」とそれぞれ評価する。【００７１】
全ての分類条件の評価結果を基に、MPC 方式が採用されたシステムは、分類木のルートノードから葉ノードにたどり着く１つだけの経路を確認する。上記の評価結果に従って分類木のルートノードから葉ノード「商品Ｙを買う傾向」にたどり着く経路は、図２４（ｂ）に示すようにルートノード「B>2 」→ノード「A>1 」→葉ノード「商品Ｙを買う傾向」の１つだけである。確認した後、MPC 方式が採用されたシステムは、確認された経路の葉ノードを出力する。【００７２】
MPC 方式が採用されたシステムが全分類条件を評価する理由は、全分類条件が評価されないと評価されていない分類条件（ノード）を基に評価結果が推測される可能性があり、結果的に入力である個人情報が判明する可能性があるためである。【００７３】
評価結果が推測される理由は、総計算時間を基に評価された分類条件が特定される可能性があるためである。例えば、図２４に示す分類木の「B>2 」、「A>1 」、「A>2 」の各分類条件の評価に掛かる計算時間がそれぞれ１秒、２秒、３秒であるとする。【００７４】
総計算時間が３秒であれば、「B>2 」、「A>1 」の分類条件の評価で予測処理が終了したと推測され、葉ノードも「わからない」か「商品Ｘを買う傾向」のいずれかであると推測される。また、総計算時間が４秒であれば、「B>2 」、「A>2 」の分類条件の評価で予測処理が終了したと推測され、葉ノードも「商品Ｙを買う傾向」か「商品Ｘを買う傾向」のいずれかであると推測される。【００７５】
上記のように、分類条件のうち一部の分類条件だけが評価されると、計算過程の内容等が外部に漏れる可能性がある。よって、分類木を用いて予測処理を行う際、MPC 方式が採用されたシステムには、全ての分類条件を評価することが求められる。【００７６】
しかし、MPC 方式が採用されたシステムは、通常のシステムに比べて計算量や通信量が多いシステムである。分類木の全ての分類条件の評価も求められると、秘密計算処理の実行に掛かる時間がさらに長くなる。特許文献１〜特許文献５、および非特許文献２〜非特許文献４には、分類木の全ての分類条件が評価されることによって秘密計算処理が遅延するという課題を解決することが記載されていない。【００７７】
［発明の目的］
そこで、本発明は、上述した課題を解決する、MPC 方式が採用されたシステムにおける分類木が用いられた予測処理の計算量を削減できる分類木生成方法、分類木生成装置および分類木生成プログラムを提供することを目的とする。
【課題を解決するための手段】
【００７８】
本発明による分類木生成方法は、分類条件をそれぞれ表す１つ以上のノードで構成された木構造で表現される予測モデルである分類木に追加される新たな分類条件を複数の分類条件の候補から選択する分類木生成装置で実行される分類木生成方法であって、分類条件の候補に関する情報利得を計算し、分類条件の候補と分類木に含まれている各分類条件との差分のうちの最小の差分の度合いを表す値を分類条件の候補に関するコストとして計算し、複数の分類条件の候補のうち計算された情報利得から計算されたコストが減算された値が最大である分類条件の候補を新たな分類条件に選択することを特徴とする。【００７９】
本発明による分類木生成方法は、複数の分類条件の候補を基に生成される可能性がある分類条件の候補をそれぞれ表す複数のノードで構成された木構造で表現される予測モデルである分類木の候補を全て生成し、生成された分類木の候補に含まれている分類条件の候補に関する情報利得の総和を生成された分類木の候補を構成する全ノードに渡って計算し、生成された分類木の候補が用いられた予測処理における分類条件の候補を入力とする計算処理のコストに応じた値である分類条件の候補に関するコストの総和を生成された分類木の候補を構成する全ノードに渡って計算し、複数の分類木の候補のうち計算された情報利得の総和から計算されたコストの総和が減算された値が最大である分類木の候補を選択することを特徴とする。【００８０】
本発明による分類木生成装置は、分類条件をそれぞれ表す１つ以上のノードで構成された木構造で表現される予測モデルである分類木に追加される新たな分類条件を複数の分類条件の候補から選択する分類木生成装置であって、分類条件の候補に関する情報利得を計算する第１計算部と、分類条件の候補と分類木に含まれている各分類条件との差分のうちの最小の差分の度合いを表す値を分類条件の候補に関するコストとして計算する第２計算部と、複数の分類条件の候補のうち計算された情報利得から計算されたコストが減算された値が最大である分類条件の候補を新たな分類条件に選択する選択部とを備えることを特徴とする。【００８１】
本発明による分類木生成装置は、複数の分類条件の候補を基に生成される可能性がある分類条件の候補をそれぞれ表す複数のノードで構成された木構造で表現される予測モデルである分類木の候補を全て生成する生成部と、生成された分類木の候補に含まれている分類条件の候補に関する情報利得の総和を生成された分類木の候補を構成する全ノードに渡って計算する第１計算部と、生成された分類木の候補が用いられた予測処理における分類条件の候補を入力とする計算処理のコストに応じた値である分類条件の候補に関するコストの総和を生成された分類木の候補を構成する全ノードに渡って計算する第２計算部と、複数の分類木の候補のうち計算された情報利得の総和から計算されたコストの総和が減算された値が最大である分類木の候補を選択する選択部とを備えることを特徴とする。【００８２】
本発明による分類木生成プログラムは、コンピュータに、分類条件をそれぞれ表す１つ以上のノードで構成された木構造で表現される予測モデルである分類木に追加される新たな分類条件が複数の分類条件の候補から選択される際に分類条件の候補に関する情報利得を計算する第１計算処理、分類条件の候補と分類木に含まれている各分類条件との差分のうちの最小の差分の度合いを表す値を分類条件の候補に関するコストとして計算する第２計算処理、および複数の分類条件の候補のうち計算された情報利得から計算されたコストが減算された値が最大である分類条件の候補を新たな分類条件に選択する選択処理を実行させることを特徴とする。【００８３】
本発明による分類木生成プログラムは、コンピュータに、複数の分類条件の候補を基に生成される可能性がある分類条件の候補をそれぞれ表す複数のノードで構成された木構造で表現される予測モデルである分類木の候補を全て生成する生成処理、生成された分類木の候補に含まれている分類条件の候補に関する情報利得の総和を生成された分類木の候補を構成する全ノードに渡って計算する第１計算処理、生成された分類木の候補が用いられた予測処理における分類条件の候補を入力とする計算処理のコストに応じた値である分類条件の候補に関するコストの総和を生成された分類木の候補を構成する全ノードに渡って計算する第２計算処理、および複数の分類木の候補のうち計算された情報利得の総和から計算されたコストの総和が減算された値が最大である分類木の候補を選択する選択処理を実行させることを特徴とする。
【発明の効果】
【００８４】
本発明によれば、MPC 方式が採用されたシステムにおける分類木が用いられた予測処理の計算量を削減できる。
【図面の簡単な説明】
【００８５】
【図１】本発明による分類木生成装置の第１の実施形態の構成例を示すブロック図である。
【図２】分類木の生成対象の変数、分割点、および分割候補の例を示す説明図である。
【図３】分類木の生成対象の変数、分割点、および分割候補の他の例を示す説明図である。
【図４】分類木生成装置１００による分割処理の例を示す説明図である。
【図５】分類木生成装置１００による分割処理の他の例を示す説明図である。
【図６】分類木生成装置１００による分割処理の他の例と生成された分類木の例を示す説明図である。
【図７】Score 計算部１２０による分類条件の変更の例を示す説明図である。
【図８】本発明による分類木生成装置のハードウェア構成例を示す説明図である。
【図９】本発明による分類木生成装置の第２の実施形態の構成例を示す説明図である。
【図１０】第２の実施形態の分類木生成装置２００による分類木生成処理の動作を示すフローチャートである。
【図１１】本発明による分類木生成装置の概要を示すブロック図である。
【図１２】本発明による分類木生成装置の他の概要を示すブロック図である。
【図１３】分類木の生成対象の変数を示す説明図である。
【図１４】一般的な分類木生成装置の構成例を示すブロック図である。
【図１５】分類木生成装置９００による分類木生成処理の動作を示すフローチャートである。
【図１６】分類木生成装置９００による分割処理の例を示す説明図である。
【図１７】分類木生成装置９００による分割処理の他の例を示す説明図である。
【図１８】分類木生成装置９００による分割処理の他の例を示す説明図である。
【図１９】分類木生成装置９００による分割処理の他の例を示す説明図である。
【図２０】分類木生成装置９００による分割処理の他の例を示す説明図である。
【図２１】分類木の例を示す説明図である。
【図２２】秘密計算技術の例を示す説明図である。
【図２３】秘密計算技術の他の例を示す説明図である。
【図２４】MPC 方式が採用されたシステムでの分類木が用いられた予測処理の例を示す説明図である。
【発明を実施するための形態】
【００８６】
実施形態１．
［構成の説明］
以下、本発明の実施形態を、図面を参照して説明する。図１は、本発明による分類木生成装置の第１の実施形態の構成例を示すブロック図である。
【００８７】
図１に示す分類木生成装置１００は、分類木学習用データ保存部１１０と、Score 計算部１２０と、分割点決定部１３０と、分割実行部１４０と、分割点保存部１５０とを備えている。また、Score 計算部１２０は、InfoGain計算部１２１と、MPCCostUP 計算部１２２とを含む。
【００８８】
図１４に示す分類木生成装置９００と異なり、本実施形態の分類木生成装置１００は、MPCCostUP 計算部１２２を含む。MPCCostUP 計算部１２２以外の分類木生成装置１００の構成は、分類木生成装置９００の構成と同様である。
【００８９】
分類木が生成される際、本実施形態のScore 計算部１２０は、InformationGain だけでなく、MPC に関するコストであるMPCCostUP も含まれたScore を計算する。MPCCostUPには、MPC に関する計算量、通信量、メモリ使用量等が反映される。
【００９０】
図１５に示す処理では「Score = InformationGain 」であるが、本実施形態のScore は、以下のように計算される。
【００９１】
Score = α × InformationGain - β × MPCCostUP  ・・・式（４）
【００９２】
式（４）におけるα、βは、独立した変数である。InformationGain の計算方法は、上述した方法と同様である。
【００９３】
以下、MPCCostUP の計算方法を説明する。分類条件のMPCCostUP は、生成された分類木が用いられた予測処理における分類条件を入力とする計算処理のコストに応じた値である。
【００９４】
例えば、分割候補が分割点保存部１５０に保存されている分割点と同じであれば、MPCCostUP 計算部１２２は、「MPCCostUP = 0 」と計算する。
【００９５】
分割点保存部１５０に保存されている分割点と同じである場合に「MPCCostUP = 0 」と計算する理由を図２を参照して説明する。図２は、分類木の生成対象の変数、分割点、および分割候補の例を示す説明図である。
【００９６】
図２（ａ）に示す分割候補と分割点は、属性Ｂ軸において近い位置に存在する。すなわちそれぞれが対応する分類条件が類似しているため、分割候補が分割点と一致させられても、分類精度が大きくは低下しないと考えられる。
【００９７】
図２（ｂ）に示す分割候補と分割点は、属性Ｂ軸において同じ位置に存在する。図２（ｂ）に示すようにそれぞれが対応する分類条件が同じであると、分類精度は低下するが、予測処理の計算量は減る。
【００９８】
分類精度が大きくは低下しないのであれば、分割点に近い分割候補が、分割点と一致させられた方が、MPC 方式が採用されたシステムにおける分類木が用いられた予測処理の計算量が減る。その理由は、図２（ｂ）に示す例であれば、MPC 方式が採用されたシステムは、分割点に対応する分類条件を評価した際の計算結果を、分割候補に対応する分類条件の評価に再利用できるからである。
【００９９】
図３は、分類木の生成対象の変数、分割点、および分割候補の他の例を示す説明図である。例えば、第１分割候補が第１分割点と一致させられても、分類精度への影響は小さいように考えられる。しかし、第２分割候補が第２分割点と一致させられると、分類精度が低下しすぎるように考えられる。以上のように、分割候補の調整には、計算量と分類精度とのバランスを考慮することが求められる。
【０１００】
上記のように、分割が実行された分割点は分割点保存部１５０に保存されているため、MPCCostUP 計算部１２２は、分割候補が分割点保存部１５０に保存されている分割点と同じであれば、「MPCCostUP = 0 」と計算する。
【０１０１】
また、分割候補が分割点保存部１５０に保存されている分割点と異なるのであれば、MPCCostUP 計算部１２２は、MPCCostUP を各分類条件の種類に応じた値に計算する。
【０１０２】
例えば、MPCCostUP 計算部１２２は、属性に応じてMPCCostUP を計算してもよい。例えば、属性ｐが整数、属性ｑが浮動小数点であれば、MPCCostUP 計算部１２２は、分類条件「ｐ＞○」、「ｑ＞○」にそれぞれ対応する分割候補のMPCCostUP をそれぞれ「１」、「２」と計算してもよい。また、属性がカテゴリ値や値域の場合、MPCCostUP は、「１」、「２」以外の別の値に計算される。なお、○は任意の値を表す。
【０１０３】
また、MPCCostUP 計算部１２２は、演算子に応じてMPCCostUP を計算してもよい。例えば、MPCCostUP 計算部１２２は、分類条件「○＝○」、「○＞○」にそれぞれ対応する分割候補のMPCCostUP をそれぞれ「０．５」、「１」と計算してもよい。
【０１０４】
また、MPCCostUP 計算部１２２は、演算の複雑度に応じてMPCCostUP を計算してもよい。例えば、MPCCostUP 計算部１２２は、分類条件「Ａ＋Ｂ＞○」、「Ａ×Ｂ＞○」、「（Ａ＋Ｂ）×Ｃ＞○」にそれぞれ対応する分割候補のMPCCostUP を、乗算の負荷の大きさを反映させてそれぞれ「２」、「５」、「１０」と計算してもよい。
【０１０５】
以下、本実施形態の分類木生成装置１００による分類木の生成例を、図４〜図６を参照して説明する。図４は、分類木生成装置１００による分割処理の例を示す説明図である。
【０１０６】
図４は、分割が２回実行された後の分割対象のエリアを示す。分割実行部１４０は、１回目の分割を「B=2 」で実行している。分割候補は図１６（ｂ）に示す第１候補〜第４候補であるがMPCCostUP がどの分割候補も同じ値であるため、分割点決定部１３０は、InfomationGain に応じて第１候補を分割点に決定している。分割が実行された後、分割点保存部１５０には分割点「B=2 」が保存されている。
【０１０７】
分割実行部１４０は、２回目の分割を分割対象の右のエリアの「A=2 」で実行している。分割候補は図１８に示す第５候補のみであるため、分割点決定部１３０は、第５候補をそのまま分割点に決定している。分割が実行された後、分割点保存部１５０には分割点「B=2 」と分割点「A=2 」が保存されている。
【０１０８】
図５は、分類木生成装置１００による分割処理の他の例を示す説明図である。分類木生成装置１００は、分割対象の左のエリアにおいて２回目の分割を行う。図１９に示す例と同様に、左のエリアにおける分割候補は、第６候補と、第７候補と、第８候補である。
【０１０９】
Score 計算部１２０は、α＝0.99、β＝0.01の式（４）に従って各候補のScore を計算する。InfoGain計算部１２１は、第６候補、第７候補、および第８候補の各InformationGain をそれぞれ0.0 、0.014 、0.014 と計算する。
【０１１０】
また、MPCCostUP 計算部１２２は、第６候補、第７候補、および第８候補の各MPCCostUP をそれぞれ1 、0 、1 と計算する。第７候補のMPCCostUP が0 になる理由は、分割点保存部１５０に第７候補と同じ分割点「A=2 」が保存されているためである。
【０１１１】
計算された各候補のScore のうち第７候補のScore が最も大きいので、分割点決定部１３０は、第７候補を分割点に決定する。次いで、分割実行部１４０は、第７候補で分割対象の左のエリアを分割する。
【０１１２】
図６は、分類木生成装置１００による分割処理の他の例と生成された分類木の例を示す説明図である。図６（ａ）は、第７候補で分割された後の分割対象のエリアを示す。
【０１１３】
図６（ｂ）は、図６（ａ）に示す分割対象のエリアを基に生成された分類木である。図６（ｂ）に示す分類木には、分類条件「A>2 」のノードが２つ存在する。よって、例えば右のノードの分類条件が評価される際、左のノードの分類条件が評価された際の計算結果が再利用可能であるため、予測処理全体に掛かる計算量が削減可能である。
【０１１４】
上記のように、MPCCostUP 計算部１２２は、分割点保存部１５０に分割候補と同じ分割点が保存されていれば、MPCCostUP を0 と計算してもよい。また、MPCCostUP 計算部１２２は、分類条件の種類に応じてMPCCostUP の値を計算してもよい。例えば、MPCCostUP 計算部１２２は、分類条件における属性の種類（整数、浮動小数点、カテゴリ値）や演算子の種類（大小比較、一致）に応じてMPCCostUP の値を計算してもよい。
【０１１５】
また、MPCCostUP 計算部１２２は、分割候補に対応する分類条件が分割点保存部１５０に保存されている分割点に対応する分類条件と途中まで同じであれば、異なる部分のみに関するコストをMPCCostUP として計算してもよい。
【０１１６】
例えば、分割点保存部１５０に分類条件「（Ａ＋Ｂ）×Ａ＞１」に対応する分割点が保存されており、分割候補に対応する分類条件が「（Ａ＋Ｂ）×Ｂ＞２」である場合、共通部分である「（Ａ＋Ｂ）」の計算結果が再利用可能である。
【０１１７】
よって、MPCCostUP 計算部１２２は、「○×Ｂ＞２」に関する計算コスト分をMPCCostUP として計算してもよい。すなわち、MPCCostUP は、分類木に追加される分類条件の候補と分類木に含まれている分類条件との差分の度合いを表す値である。式（４）では、分類木に含まれている各分類条件との差分のうちの最小の差分の度合いを表す値がMPCCostUP として使用される。
【０１１８】
また、MPCCostUP 計算部１２２は、分類条件を評価するMPC 方式が採用されたシステムを表す論理回路中のAND 回路の深さに応じて、MPCCostUP を計算してもよい。MPC に関する計算量や通信量は、MPC 方式が採用されたシステムを表す論理回路中のAND 回路の深さに依存する。
【０１１９】
本実施形態では、Score 計算におけるInformationGain とMPCCostUP とのバランスを適切にとることが重要である。例えば、MPC に関する計算コストは、分類木が用いられた予測処理全体の計算量、すなわち分類木の分類条件の数に依存する。バランスをとるために、分類木の分類条件が増えるほどβをαよりも大きくすることによって、MPCCostUP の影響を大きくすることが考えられる。
【０１２０】
また、予測処理の実行環境が豊富な通信帯域幅が用意され高速なＣＰＵ（Central Processing Unit ）が搭載されている環境である場合、MPCCostUP の影響はあまり考慮されなくてもよい。よって、バランスをとるためにαをβよりも大きくすることによって、MPCCostUP の影響を小さくすることが考えられる。
【０１２１】
［動作の説明］
本実施形態の分類木生成装置１００による分割処理の動作は、図１５に示す動作と同様である。本実施形態では、ステップS004においてScore 計算部１２０が、InfomationGain とMPCCostUP とを基に分割候補のScore を計算する。
【０１２２】
なお、Score 計算部１２０は、分割点保存部１５０に保存されている分割点に対応する他のノードの分類条件と分割候補に対応する分類条件が類似している場合、以下のように各条件を変更してもよい。図７は、Score 計算部１２０による分類条件の変更の例を示す説明図である。
【０１２３】
Score を計算する際、Score 計算部１２０のMPCCostUP 計算部１２２は、分割点保存部１５０に保存されている分割点を参照する。参照した際、Score 計算部１２０は、参照された分割点の値と分割候補の値との中間値が含まれる条件に、それぞれが対応する各分類条件を変更してもよい。
【０１２４】
図７（ａ）は、分類条件が変更される前の分類木を示す。図７（ａ）に示す分割候補に対応する分類条件「A>4 」と、分類条件「A>6 」は類似している。図７（ａ）に示す分類木に対して、Score 計算部１２０は、両条件を中間値である５が含まれた「A>5 」に変更する。
【０１２５】
図７（ｂ）は、分類条件が変更された後の分類木を示す。分類条件が変更された後、図７（ｂ）に示す領域７１に対応するエリアでの分割処理は、新たな分割点で再度実行されることが求められる。なお、図７に示す分類条件の変更は、領域７１に対応するエリアで分割が再度実行されても領域７２に影響が及ばないような分類条件に限って実行可能である。
【０１２６】
またScore 計算の重みαの値、重みβの値に連動して、図７に示す分類条件の変更が実行される閾値が決定されてもよい。閾値は、要求される計算量の削減の程度に応じて決定される。図７に示す分類条件の変更が実行されると、同一の分類条件が少ない場合であっても強制的に分類条件が同じ分割候補が生成されるため、確実に予測処理の計算量が削減される。
【０１２７】
［効果の説明］
本実施形態の分類木生成装置１００は、MPC 方式が採用されたシステムにおける分類木が用いられた予測処理の計算量を削減できる。その理由は、Score 計算部１２０が既に分類木で使用されている分類条件に一致している条件、または類似している条件に対応する分割候補のScore が大きくなるようにScore を計算するため、生成される分類木中に同じ分類条件、または類似する分類条件が含まれやすくなるためである。
【０１２８】
以下、第１の実施形態の分類木生成装置１００のハードウェア構成の具体例を説明する。図８は、本発明による分類木生成装置のハードウェア構成例を示す説明図である。
【０１２９】
図８に示す分類木生成装置１００は、ＣＰＵ１０１と、主記憶部１０２と、通信部１０３と、補助記憶部１０４とを備える。また、ユーザが操作するための入力部１０５や、ユーザに処理結果または処理内容の経過を提示するための出力部１０６を備えてもよい。
【０１３０】
主記憶部１０２は、データの作業領域やデータの一時退避領域として用いられる。主記憶部１０２は、例えばＲＡＭ（Random Access Memory）である。
【０１３１】
通信部１０３は、有線のネットワークまたは無線のネットワーク（情報通信ネットワーク）を介して、周辺機器との間でデータを入力および出力する機能を有する。
【０１３２】
補助記憶部１０４は、一時的でない有形の記憶媒体である。一時的でない有形の記憶媒体として、例えば磁気ディスク、光磁気ディスク、ＣＤ−ＲＯＭ（Compact Disk Read Only Memory ）、ＤＶＤ−ＲＯＭ（Digital Versatile Disk Read Only Memory ）、半導体メモリが挙げられる。
【０１３３】
入力部１０５は、データや処理命令を入力する機能を有する。入力部１０５は、例えばキーボードやマウス等の入力デバイスである。
【０１３４】
出力部１０６は、データを出力する機能を有する。出力部１０６は、例えば液晶ディスプレイ装置等の表示装置、またはプリンタ等の印刷装置である。
【０１３５】
また、図８に示すように、分類木生成装置１００において、各構成要素は、システムバス１０７に接続されている。
【０１３６】
補助記憶部１０４は、例えば、図１に示すInfoGain計算部１２１、MPCCostUP 計算部１２２、分割点決定部１３０、および分割実行部１４０を実現するためのプログラムを記憶している。
【０１３７】
また、分類木学習用データ保存部１１０、および分割点保存部１５０は、主記憶部１０２であるＲＡＭで実現されてもよい。
【０１３８】
実施形態２．
［構成の説明］
次に、本発明の第２の実施形態を、図面を参照して説明する。図９は、本発明による分類木生成装置の第２の実施形態の構成例を示す説明図である。
【０１３９】
図９に示す分類木生成装置２００は、分類木学習用データ保存部２１０と、分類木全パターン計算部２２０と、Score 計算部２３０と、最適分類木決定部２４０と、分割点保存部２５０とを備える。また、Score 計算部２３０は、InfoGain計算部２３１と、MPCCostUP 計算部２３２とを含む。
【０１４０】
分類木学習用データ保存部２１０、InfoGain計算部２３１、MPCCostUP 計算部２３２、および分割点保存部２５０が有する各機能は、第１の実施形態の分類木学習用データ保存部１１０、InfoGain計算部１２１、MPCCostUP 計算部１２２、および分割点保存部１５０が有する各機能とそれぞれ同様である。
【０１４１】
第１の実施形態の分類木生成装置１００は、各分割候補のInfomationGain とMPCCostUP を考慮し、Score が最大の分割候補を分割点に決定し、分割点で分割する。すなわち、分類木生成装置１００は分割点が決定される度に分割（グリーディに分割）している。
【０１４２】
グリーディに分割が行われる分類木生成処理には、分類木の生成に掛かる計算量が少ないというメリットがあるが、必ずしも最適解が得られるとは限らないというデメリットがある。その理由は、全ての分類木の候補が検討されない可能性があるからである。
【０１４３】
本実施形態の分類木生成装置２００の分類木全パターン計算部２２０は、分割対象のエリアをグリーディに分割する代わりに、最初に分類木として考えられる全ての木構造を生成する。次いで、Score 計算部２３０は、生成された全ての木構造に対して、木全体のInfomationGain と木全体のMPCCost とをそれぞれ計算する。
【０１４４】
次いで、Score 計算部２３０は、計算された木全体のInfomationGain と計算された木全体のMPCCost とを基に全ての木構造に対してScore を計算する。次いで、最適分類木決定部２４０は、計算されたScore を基に、最適な分類木を選択する。上記の方法で分類木を選択することによって、分類木生成装置２００は、最適解である分類木をより確実に生成できる。
【０１４５】
［動作の説明］
以下、本実施形態の分類木生成装置２００の分類木を生成する動作を図１０を参照して説明する。図１０は、第２の実施形態の分類木生成装置２００による分類木生成処理の動作を示すフローチャートである。
【０１４６】
図１０に示す分割処理の入力は、分割対象のエリアである。最初に、分類木全パターン計算部２２０は、分類木学習用データ保存部２１０に記憶されている分割対象のエリアにおける説明変数に関する分割点の候補を分割候補として列挙する（ステップS101）。すなわち、分類木全パターン計算部２２０は、エリア全体に渡って全ての分割候補を列挙する。
【０１４７】
次いで、分類木全パターン計算部２２０は、全ての分割候補でエリアが分割されるように分割を繰り返し実行することによって、全ての分類木候補を生成する（ステップS102）。
【０１４８】
次いで、Score 計算部２３０は、全ての分類木候補から未だ木全体Score が計算されていない分類木候補を１つ取り出す。すなわち、分類木候補ループに入る（ステップS103）。
【０１４９】
取り出された分類木候補に関して、Score 計算部２３０のInfoGain計算部２３１は、木全体InfomationGain を、分類木候補の各ノードに渡って分類条件のInfomatioGain の総和をとることによって計算する（ステップS104）。
【０１５０】
次いで、Score 計算部２３０のMPCCostUP 計算部２３２は、取り出された分類木候補に関して、木全体MPCCostUP を、分類木候補の各ノードに渡って分類条件のMPCCostUP の総和をとることによって計算する（ステップS105）。異なるノードで分類条件が同じであれば、１つのノード分のMPCCostUP のみが木全体MPCCostUP に加算される。
【０１５１】
次いで、Score 計算部２３０は、木全体Score を以下のように計算する（ステップS106）。
【０１５２】
木全体Score = α × 木全体InfomationGain - β × 木全体MPCCostUP
・・・式（５）
【０１５３】
全ての分類木候補の中で木全体Score が計算されていない分類木候補が存在する間、ステップS104〜ステップS106の処理が繰り返し行われる。全ての分類木候補の木全体Score が計算されたとき、Score 計算部２３０は、分類木候補ループを抜ける（ステップS107）。
【０１５４】
次いで、最適分類木決定部２４０は、全ての分類木候補の中で木全体Score が最大である分類木候補を分類木に決定する（ステップS108）。分類木を決定した後、分類木生成装置２００は、分類木生成処理を終了する。
【０１５５】
［効果の説明］
本実施形態の分類木生成装置２００は、第１の実施形態の分類木生成装置１００に比べて最適解である分類木をより確実に生成できる。その理由は、分類木全パターン計算部２２０が最初に生成される可能性がある分類木候補を全て生成し、Score 計算部２３０が各分類木候補の木全体Score をそれぞれ計算するため、分類木候補の検討漏れが防止されるからである。
【０１５６】
なお、分類木生成装置２００のハードウェア構成は、図８に示すハードウェア構成と同様の構成でもよい。
【０１５７】
また、分類木生成装置１００、および分類木生成装置２００は、ハードウェアにより実現されてもよい。例えば、分類木生成装置１００、および分類木生成装置２００は、内部に図１に示すような機能、または図９に示すような機能を実現するプログラムが組み込まれたＬＳＩ（Large Scale Integration ）等のハードウェア部品が含まれる回路が実装されてもよい。
【０１５８】
また、分類木生成装置１００、および分類木生成装置２００は、図８に示すＣＰＵ１０１が図１に示す各構成要素が有する機能、または図９に示す各構成要素が有する機能を提供するプログラムを実行することによって、ソフトウェアにより実現されてもよい。
【０１５９】
ソフトウェアにより実現される場合、ＣＰＵ１０１が補助記憶部１０４に格納されているプログラムを、主記憶部１０２にロードして実行し、分類木生成装置１００、または分類木生成装置２００の動作を制御することによって、各機能がソフトウェアにより実現される。
【０１６０】
また、各構成要素の一部または全部は、汎用の回路（circuitry ）または専用の回路、プロセッサ等やこれらの組み合わせによって実現されてもよい。これらは、単一のチップによって構成されてもよいし、バスを介して接続される複数のチップによって構成されてもよい。各構成要素の一部または全部は、上述した回路等とプログラムとの組み合わせによって実現されてもよい。
【０１６１】
各構成要素の一部または全部が複数の情報処理装置や回路等により実現される場合には、複数の情報処理装置や回路等は集中配置されてもよいし、分散配置されてもよい。例えば、情報処理装置や回路等は、クライアントアンドサーバシステム、クラウドコンピューティングシステム等、各々が通信ネットワークを介して接続される形態として実現されてもよい。
【０１６２】
次に、本発明の概要を説明する。図１１は、本発明による分類木生成装置の概要を示すブロック図である。本発明による分類木生成装置１０は、分類条件をそれぞれ表す１つ以上のノードで構成された木構造で表現される予測モデルである分類木に追加される新たな分類条件を複数の分類条件の候補から選択する分類木生成装置であって、分類条件の候補に関する情報利得を計算する第１計算部１１（例えば、InfoGain計算部１２１）と、分類条件の候補と分類木に含まれている各分類条件との差分のうちの最小の差分の度合いを表す値を分類条件の候補に関するコストとして計算する第２計算部１２（例えば、MPCCostUP 計算部１２２）と、複数の分類条件の候補のうち計算された情報利得から計算されたコストが減算された値が最大である分類条件の候補を新たな分類条件に選択する選択部１３（例えば、分割点決定部１３０）とを備える。
【０１６３】
そのような構成により、分類木生成装置は、MPC 方式が採用されたシステムにおける分類木が用いられた予測処理の計算量を削減できる。
【０１６４】
また、第２計算部１２は、分類木に含まれている分類条件と同一の分類条件の候補に関するコストを０と計算してもよい。
【０１６５】
そのような構成により、分類木生成装置は、MPC 方式が採用されたシステムにおける分類木が用いられた予測処理の計算量を削減できる。
【０１６６】
また、第２計算部１２は、分類条件の候補の内容（例えば、分類条件に含まれる属性、演算子、属性の計算）に応じて分類条件の候補に関するコストを計算してもよい。
【０１６７】
そのような構成により、分類木生成装置は、MPC 方式が採用されたシステムにおける分類木が用いられた予測処理の計算量をコストに反映できる。
【０１６８】
また、第２計算部１２は、分類木を用いて予測処理を実行するシステムを表す論理回路を生成し、生成された論理回路に含まれるAND 回路に応じて分類条件の候補に関するコストを計算してもよい。
【０１６９】
そのような構成により、分類木生成装置は、MPC 方式が採用されたシステムにおける分類木が用いられた予測処理の計算量をより正確にコストに反映できる。
【０１７０】
また、第２計算部１２は、分類木の深さまたは分類木に含まれている分類条件の数に応じて計算された情報利得から減算される計算されたコストの重みを変更してもよい。
【０１７１】
そのような構成により、分類木生成装置は、MPC 方式が採用されたシステムにおける分類木が用いられた予測処理全体の計算量と情報利得とのバランスをとることができる。
【０１７２】
また、第２計算部１２は、分類木を用いて予測処理を実行するシステムの演算処理能力（例えば、通信帯域幅やＣＰＵ速度）に応じて計算された情報利得から減算される計算されたコストの重みを変更してもよい。
【０１７３】
そのような構成により、分類木生成装置は、MPC 方式が採用されたシステムの演算処理能力をコストに反映できる。
【０１７４】
また、第２計算部１２は、最小の差分の度合いが所定の閾値以下である分類条件の候補と分類木に含まれている分類条件とを分類条件の候補と分類条件とを基に生成された新たな条件にいずれも変更してもよい。
【０１７５】
そのような構成により、分類木生成装置は、分類木に分類条件の候補と同じ分類条件が含まれていない場合であっても分類木が用いられた予測処理の計算量を削減できる。
【０１７６】
図１２は、本発明による分類木生成装置の他の概要を示すブロック図である。本発明による分類木生成装置２０は、複数の分類条件の候補を基に生成される可能性がある分類条件の候補をそれぞれ表す複数のノードで構成された木構造で表現される予測モデルである分類木の候補を全て生成する生成部２１（例えば、分類木全パターン計算部２２０）と、生成された分類木の候補に含まれている分類条件の候補に関する情報利得の総和を生成された分類木の候補を構成する全ノードに渡って計算する第１計算部２２（例えば、InfoGain計算部２３１）と、生成された分類木の候補が用いられた予測処理における分類条件の候補を入力とする計算処理のコストに応じた値である分類条件の候補に関するコストの総和を生成された分類木の候補を構成する全ノードに渡って計算する第２計算部２３（例えば、MPCCostUP 計算部２３２）と、複数の分類木の候補のうち計算された情報利得の総和から計算されたコストの総和が減算された値が最大である分類木の候補を選択する選択部２４（例えば、最適分類木決定部２４０）とを備える。
【０１７７】
そのような構成により、分類木生成装置は、MPC 方式が採用されたシステムにおける分類木が用いられた予測処理の計算量を削減できる。
【０１７８】
以上、実施形態および実施例を参照して本願発明を説明したが、本願発明は上記実施形態および実施例に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０１７９】
また、上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下に限られない。
【０１８０】
（付記１）分類条件をそれぞれ表す１つ以上のノードで構成された木構造で表現される予測モデルである分類木に追加される新たな分類条件を複数の分類条件の候補から選択する分類木生成装置で実行される分類木生成方法であって、分類条件の候補に関する情報利得を計算し、分類条件の候補と前記分類木に含まれている各分類条件との差分のうちの最小の差分の度合いを表す値を分類条件の候補に関するコストとして計算し、前記複数の分類条件の候補のうち計算された情報利得から計算されたコストが減算された値が最大である分類条件の候補を前記新たな分類条件に選択することを特徴とする分類木生成方法。
【０１８１】
（付記２）分類木に含まれている分類条件と同一の分類条件の候補に関するコストを０と計算する付記１記載の分類木生成方法。
【０１８２】
（付記３）分類条件の候補の内容に応じて前記分類条件の候補に関するコストを計算する付記１または付記２記載の分類木生成方法。
【０１８３】
（付記４）分類木を用いて予測処理を実行するシステムを表す論理回路を生成し、生成された論理回路に含まれるAND 回路に応じて分類条件の候補に関するコストを計算する付記１から付記３のうちのいずれか１項に記載の分類木生成方法。
【０１８４】
（付記５）分類木の深さまたは前記分類木に含まれている分類条件の数に応じて計算された情報利得から減算される計算されたコストの重みを変更する付記１から付記４のうちのいずれか１項に記載の分類木生成方法。
【０１８５】
（付記６）分類木を用いて予測処理を実行するシステムの演算処理能力に応じて計算された情報利得から減算される計算されたコストの重みを変更する付記１から付記５のうちのいずれか１項に記載の分類木生成方法。
【０１８６】
（付記７）最小の差分の度合いが所定の閾値以下である分類条件の候補と分類木に含まれている分類条件とを前記分類条件の候補と前記分類条件とを基に生成された新たな条件にいずれも変更する付記１から付記６のうちのいずれか１項に記載の分類木生成方法。
【０１８７】
（付記８）複数の分類条件の候補を基に生成される可能性がある分類条件の候補をそれぞれ表す複数のノードで構成された木構造で表現される予測モデルである分類木の候補を全て生成し、生成された分類木の候補に含まれている分類条件の候補に関する情報利得の総和を生成された分類木の候補を構成する全ノードに渡って計算し、生成された分類木の候補が用いられた予測処理における分類条件の候補を入力とする計算処理のコストに応じた値である分類条件の候補に関するコストの総和を生成された分類木の候補を構成する全ノードに渡って計算し、複数の分類木の候補のうち計算された情報利得の総和から計算されたコストの総和が減算された値が最大である分類木の候補を選択することを特徴とする分類木生成方法。
【０１８８】
（付記９）分類条件をそれぞれ表す１つ以上のノードで構成された木構造で表現される予測モデルである分類木に追加される新たな分類条件を複数の分類条件の候補から選択する分類木生成装置であって、分類条件の候補に関する情報利得を計算する第１計算部と、分類条件の候補と前記分類木に含まれている各分類条件との差分のうちの最小の差分の度合いを表す値を分類条件の候補に関するコストとして計算する第２計算部と、前記複数の分類条件の候補のうち計算された情報利得から計算されたコストが減算された値が最大である分類条件の候補を前記新たな分類条件に選択する選択部とを備えることを特徴とする分類木生成装置。
【０１８９】
（付記１０）複数の分類条件の候補を基に生成される可能性がある分類条件の候補をそれぞれ表す複数のノードで構成された木構造で表現される予測モデルである分類木の候補を全て生成する生成部と、生成された分類木の候補に含まれている分類条件の候補に関する情報利得の総和を生成された分類木の候補を構成する全ノードに渡って計算する第１計算部と、生成された分類木の候補が用いられた予測処理における分類条件の候補を入力とする計算処理のコストに応じた値である分類条件の候補に関するコストの総和を生成された分類木の候補を構成する全ノードに渡って計算する第２計算部と、複数の分類木の候補のうち計算された情報利得の総和から計算されたコストの総和が減算された値が最大である分類木の候補を選択する選択部とを備えることを特徴とする分類木生成装置。
【０１９０】
（付記１１）コンピュータに、分類条件をそれぞれ表す１つ以上のノードで構成された木構造で表現される予測モデルである分類木に追加される新たな分類条件が複数の分類条件の候補から選択される際に分類条件の候補に関する情報利得を計算する第１計算処理、分類条件の候補と前記分類木に含まれている各分類条件との差分のうちの最小の差分の度合いを表す値を分類条件の候補に関するコストとして計算する第２計算処理、および前記複数の分類条件の候補のうち計算された情報利得から計算されたコストが減算された値が最大である分類条件の候補を前記新たな分類条件に選択する選択処理を実行させるための分類木生成プログラム。
【０１９１】
（付記１２）コンピュータに、複数の分類条件の候補を基に生成される可能性がある分類条件の候補をそれぞれ表す複数のノードで構成された木構造で表現される予測モデルである分類木の候補を全て生成する生成処理、生成された分類木の候補に含まれている分類条件の候補に関する情報利得の総和を生成された分類木の候補を構成する全ノードに渡って計算する第１計算処理、生成された分類木の候補が用いられた予測処理における分類条件の候補を入力とする計算処理のコストに応じた値である分類条件の候補に関するコストの総和を生成された分類木の候補を構成する全ノードに渡って計算する第２計算処理、および複数の分類木の候補のうち計算された情報利得の総和から計算されたコストの総和が減算された値が最大である分類木の候補を選択する選択処理を実行させるための分類木生成プログラム。
【産業上の利用の可能性】
【０１９２】
本発明は、秘密計算技術の分野に好適に適用される。
【符号の説明】
【０１９３】
１０、２０、１００、２００、９００  分類木生成装置
１１、２２  第１計算部
１２、２３  第２計算部
１３、２４  選択部
２１  生成部
１０１  ＣＰＵ
１０２  主記憶部
１０３  通信部
１０４  補助記憶部
１０５  入力部
１０６  出力部
１０７  システムバス
１１０、２１０、９１０  分類木学習用データ保存部
２２０  分類木全パターン計算部
１２０、２３０、９２０  Score 計算部
１２１、２３１、９２１  InfoGain計算部
１２２、２３２  MPCCostUP 計算部
１３０、９３０  分割点決定部
１４０、９４０  分割実行部
２４０  最適分類木決定部
１５０、２５０、９５０  分割点保存部
【図１】
2019138584.tif 000006
【図２】
2019138584.tif 000007
【図３】
2019138584.tif 000008
【図４】
2019138584.tif 000009
【図５】
2019138584.tif 000010
【図６】
2019138584.tif 000011
【図７】
2019138584.tif 000012
【図８】
2019138584.tif 000013
【図９】
2019138584.tif 000014
【図１０】
2019138584.tif 000015
【図１１】
2019138584.tif 000016
【図１２】
2019138584.tif 000017
【図１３】
2019138584.tif 000018
【図１４】
2019138584.tif 000019
【図１５】
2019138584.tif 000020
【図１６】
2019138584.tif 000021
【図１７】
2019138584.tif 000022
【図１８】
2019138584.tif 000023
【図１９】
2019138584.tif 000024
【図２０】
2019138584.tif 000025
【図２１】
2019138584.tif 000026
【図２２】
2019138584.tif 000027
【図２３】
2019138584.tif 000028
【図２４】
2019138584.tif 000029
【国際調査報告】
2019138584.tif 000030
2019138584.tif 000031
2019138584.tif 000032
2019138584.tif 000033